표제지
목차
약어목록 10
1. 서론 12
1.1. 연구 배경 및 목적 27
1.2. 연구 범위 29
1.3. 논문 구성 31
2. 관련 연구 32
2.1. 선형 검색 및 캐쉬 기반 기법 32
2.2. TCAM (Ternary CAM) 기법 33
2.3. 계층적 트라이(Hierarchical Tries) 기법 35
2.4. Grid-of-Tries 기법 38
2.5. Crossproducting 기법 40
2.6. Bitmap-Intersection 기법 42
2.7. Tuple Space Search 기법 45
2.8. Rectangle Search 기법 46
2.9. RFC(Recursive Flow Classification) 기법 49
3. 트리 비트맵 기법 53
3.1. 트리 비트맵 구조 53
3.2. 트리 비트맵 기반 검색 62
4. 트리 비트맵 기반 룰 검색 기법 65
4.1. 룰 검색 구조 65
4.2. 룰 검색 70
4.2.1. 인덱스 테이블 구성 및 검색 70
4.2.2. 멀티 비트 트리 비트맵 테이블 검색 72
4.2.3. 백트랙킹 룰 검색 78
4.2.4. 마커 프레픽스 기반 룰 검색 81
4.2.5. 경로 축약 룰 검색 85
4.3. 룰 구축 93
4.3.1. 룰 엔트리 추가 93
4.3.1.1. 인덱스 테이블 갱신 94
4.3.1.2. 멀티 비트 트리 비트맵 테이블 갱신 95
4.3.2. 룰 엔트리 삭제 103
4.4. 패킷 분류 엔진 설계 108
4.4.1. IP 주소 추출 및 인덱싱 제어 108
4.4.2. Stride 선택 및 Comparand 비트맵 생성 109
4.4.3. 룰 데이터 유형 분석 및 LPM 프레픽스 검색 112
4.4.4. 멀티 비트 노드 옵셋 계수기 113
4.4.5. 멀티 비트 노드 포인터 선택기 114
4.4.6. 룰 테이블 주소 제어 및 데이터 래치기 115
4.4.7. 룰 검색 타이밍 시뮬레이션 115
5. 메모리 소요 및 성능 분석 118
5.1. 인덱스 테이블 118
5.2. 멀티 비트 트리 비트맵 정보 테이블 119
5.3. 랜덤 룰 셋 생성 및 메모리 소요량 120
5.4. 룰 검색 성능 132
6. 결론 138
참고문헌 141
Abstract 147
표 1.1. 패킷 분류 기능을 이용한 서비스 종류 20
표 1.2. R1의 링크 X를 통한 서비스를 수행하기 위한 관련 패킷 헤더 필드 21
표 1.3. 4차원 패킷 분류를 위한 룰 구성 예 23
표 1.4. 표 1.3의 룰에 대한 패킷 분류의 예 23
표 2.1. 필드 F1, F2로 구성되는 2차원 패킷 분류 룰 셋 예 37
표 2.2. 패킷 P1=(10100, 11100)이 수신되는 경우 검색 과정 49
표 3.1. 프레픽스 엔트리 예 54
표 4.1. {F1, F2} 필드로 구성되는 2차원 룰의 예 71
표 4.2. 8비트 길이의 필드 {F1, F2}로 구성되는 2차원 룰의 예 78
표 4.3. S_CNT 카운터의 각 비트에 따른 의미 및 동작 110
표 4.4. 4비트의 비교키에 대한 cIPB와 비교 cEPB 생성 112
표 5.1. 주요 프레픽스 길이에 대한 엔트리 수 비율 121
표 5.2. Stride 길이별 해당 프레픽스 분포 비율 123
표 5.3. AADS/PB 룰 셋 수에 따른 멀티 비트 노드에 대한 메모리 용량 126
표 5.4. 패킷 분류 기법의 검색 시간 및 소요 메모리 복잡도에 대한 요약 137
그림 1.1. 라우터 기반의 인터넷 구성 13
그림 1.2. 목적지 주소 기반의 패킷 처리 기법에서 데이터 흐름 14
그림 1.3. 플로우 기반의 패킷 처리 기법에서 데이터 흐름 15
그림 1.4. IP 패킷의 헤더 구성 17
그림 1.5. 패킷 분류와 트래픽 제어를 위한 기능 구조 18
그림 1.6. ISP간 연결된 인터넷 구성 예 19
그림 2.1. TCAM 을 이용한 룰 검색 34
그림 2.2. 이진 트라이 구조 36
그림 2.3. F1, F2의 2필드로 구성되는 계층적 트라이 구조 및 검색 38
그림 2.4. Grid-of-Trie 검색 구조 39
그림 2.5. 수신 패킷 (000, 100)에 대한 grid-of-trie 검색 40
그림 2.6. 2차원 패킷 분류를 위한 기하학적 표현과 crossproduct 테이블 42
그림 2.7. Bitmap-Intersection 패킷 분류를 위한 구간별 룰 비트맵 생성 44
그림 2.8. Bitmap-Intersection과 best matching 룰 검색 과정 44
그림 2.9. 튜플 공간에 따른 헤쉬 테이블 생성 45
그림 2.10. Marker와 Precomputation 48
그림 2.11. RFC 기법의 구조와 동작 51
그림 3.1. 표 3.1에 대한 이진 트라이 구조 55
그림 3.2. 그림 3.1에 대한 멀티 비트 트라이 구조(4비트 stride) 57
그림 3.3. IPB 와 EPB 의 비트맵 코드화 59
그림 3.4. 4 비트 비교키 0101에 대한 cIPB와 cEPB 생성 63
그림 3.5. 멀티 비트 노드 비트맵과 comparand 비트맵을 이용한 LPM 검색 64
그림 4.1. 트리 비트맵 기반 룰 검색을 위한 주소 분해 구조 66
그림 4.2. 2차원 멀티 필드 패킷 분류를 위한 룰 검색 구조 68
그림 4.3. IP 패킷의 DA와 SA 인덱스 구성과 stride별 계층적 비교 검색 순서 69
그림 4.4. 표 4.1의 룰에 대한 인덱스 테이블 구성 예 71
그림 4.5. 2차원 멀티 비트 트리 비트맵 기본 룰 구조 예(4 비트 stride) 73
그림 4.6. 그림 4.5에 대한 멀티 비트 트리 비트맵 및 포인터 연결 77
그림 4.7. 백트랙킹을 가지는 경우 검색 방법 79
그림 4.8. 마커 프레픽스를 이용한 룰 검색 구조 82
그림 4.9. 마커 프레픽스에 대한 비트맵 및 switch pointer를 이용한 포인터 연결 82
그림 4.10. 백트랙킹이 없는 경우 노드 비트맵 및 룰 검색 구조 83
그림 4.11. 2차원 패킷 분류를 위한 경로 축약 룰 검색 알고리즘 87
그림 4.12. 경로 축약 적용 룰 검색 구조 88
그림 4.13. 경로 축약 룰 검색의 멀티 비트 트리 비트맵 및 포인터 연결 예 90
그림 4.14. 경로 축약 전과 축약 후의 룰 검색 홉 92
그림 4.15. 룰 R1, R2, R3에 대하여 구축된 인덱스 테이블 구조 96
그림 4.16. 멀티 비트 노드내의 프레픽스간 상하위 구분 97
그림 4.17. 룰 추가 흐름도 101
그림 4.18. 룰 R1, R2, R3에 대한 룰 추가 과정 102
그림 4.19. 룰 삭제 흐름도 105
그림 4.20. 룰 R1, R2, R3로부터 R1, R2에 대한 삭제 과정 107
그림 4.21. 멀티 비트 트리 비트맵 기반 패킷 분류 엔진 구조 109
그림 4.22. Stride 선택 및 Comparand 비트맵 생성 기능 블록 110
그림 4.23. 룰 데이터 유형 분석 및 LPM 프레픽스 검색 기능 블록 113
그림 4.24. 멀티 비트 노드 옵셋 개수 계산 블록 114
그림 4.25. 룰 검색 타이밍 시뮬레이션 117
그림 5.1. 라우팅 테이블에 대한 프레픽스 길이별 엔트리 수 분포 121
그림 5.2. 목적지 주소 및 발신지 주소로 구성된 2차원 룰 셋 생성 과정 122
그림 5.3. AADS 랜덤 룰 셋의 프레픽스 길이별 분포(4 bit stride, 룰 수: 10,000) 124
그림 5.4. PB 랜덤 룰 셋의 프레픽스 길이별 분포(4bit stride, 룰 수: 10,000) 124
그림 5.5. 멀티 비트 노드 레벨별 노드 수 분포 125
그림 5.6. 인덱스 길이별 stride 크기에 대한 메모리 소요량 127
그림 5.7. Stride 길이와 인덱스 길이에 따른 메모리 소요량 128
그림 5.8. 룰 수의 증가에 따른 룰 구축에 소요되는 메모리량 129
그림 5.9. 트리 비트맵 기법과 기존 기법과의 메모리량 비교 130
그림 5.10. Stride 길이와 인덱스 길이에 따른 액세스 횟수(memwidth=64bit) 133
그림 5.11. Stride 길이와 인덱스 길이에 따른 액세스 횟수(memwidth=128bit) 133
그림 5.12. 인덱스 길이와 stride 길이에 따른 최적화 지수(memwidth=64bit) 135
그림 5.13. 인덱스 길이와 stride 길이에 따른 최적화 지수(memwidth=128bit) 136