title page
Contents
Abstract 12
1. Introduction 14
2. Related Work 16
2.1. Address Lookup 16
2.1.1. Trie 17
2.1.2. Yazdani's tree 20
2.1.2.1. Basic Idea 20
2.1.2.2. Building in Yazdani's tree 22
2.1.2.3. Searching in Yazdani's tree 27
2.1.2.4. Updating in Yazdani's tree 27
2.1.3. Weighted Binary Prefix tree 29
2.1.3.1. Basic Idea 29
2.1.3.2. Building WBPT 31
2.1.3.3. Searching WBPT 33
2.2. Packet Classification 36
2.2.1. Trie-based packet classification 37
2.2.2. Range search based packet classification 40
2.2.3. Heuristic Packet classification 41
3. 2-way Binary Prefix Tree(2-way BPT) 42
3.1. Basic Idea 42
3.2. Building in 2-way BPT 45
3.3. Searching in 2-way BPT 48
3.4. Updating in 2-way BPT 50
3.5. Structure of 2-way BPT 51
4. Multiway BPT 52
4.1. Basic Idea 52
4.2. Building in Multiway BPT 52
4.3. Searching in Multiway BPT 55
4.4. Structure of Multiway BPT 56
5. EnBiT 57
5.1. Basic Idea 57
5.2. Building in EnBiT 57
5.3. Searching in EnBiT 61
5.4. Updating in EnBiT 63
5.5. Structure of EnBiT 65
6. DPT_PC 72
6.1. Basic idea 72
6.2. Building in DPT_PC 75
6.3. Searching in DPT_PC 79
6.4. Structure of DPT_PC 80
7. Simulation Result 81
7.1. 2-way BPT 81
7.2. Multiway BPT 82
7.3. EnBiT 83
7.4. DPT_PC 86
7.5. Comparison with related work 89
8. Conclusion 95
Reference 97
감사의 글 99
Table 7.1. Simulation results of the 2-way BPT 81
Table 7.2. Simulation results of the Multiway BPT 82
Table 7.3. Prefix distribution of route data 84
Table 7.4. Required memory size and main tree height for type1, 2 EnBiT 85
Table 7.5. Number of rules of different values in source or/and destination prefix fields 87
Table 7.6. Number of memory accesses in DPT_PC 87
Table 7.7. Required memory size in DPT_PC (KByte) 88
Table 7.8. Comparison between software-based architecture with other existing software-based architecture 92
Table 7.9. Comparison between EnBiT architecture with other existing hardware-based architecture 92
Fig 2.1. Sample prefixes 18
Fig 2.2. Binary trie using sample prefix in Fig.2.1 19
Fig 2.3. Definition in Yazdani's tree 21
Fig 2.4. Sort procedure for Yazdani's tree 22
Fig 2.5. Build procedure for Yazdani's tree 23
Fig 2.6. Yazdani's tree using prefixes in Fig.2.1 24
Fig 2.7. Entry structure of Yazdani's tree 25
Fig 2.8. Yazdani's tree routing table 26
Fig 2.9. Search procedure in Yazdani's tree 27
Fig 2.10. Update procedure for Yazdani's tree 28
Fig 2.11. Definition of WBPT 29
Fig 2.12. WBPT using prefixes in Fig.2.1 34
Fig 2.13. WBPT routing table 35
Fig 2.14. Sample rule set for previous work 38
Fig 2.15. 2-D Hierarchical Trie using sample rule set in Fig.2.14 38
Fig 2.16. 2-D Set Pruning Trie using sample rule set in Fig.2.14 39
Fig 2.17. 2-D Grid of Trie using sample rule set in Fig.2.14 39
Fig 2.18. 2-D Cross-Producting using sample rule set in Fig.2.14 40
Fig 2.19. HiCuts tree using sample rule set in Fig.2.14 41
Fig 3.1. Prefix sorting 43
Fig 3.2. 2-way BPT using sample prefix in Fig.2.1 44
Fig 3.3. Routing table of 2-way BPT using range table 46
Fig 3.4. 2-way BPT using range table 47
Fig 3.5. Search flow chart for 2-way BPT 49
Fig 3.6. Update flow chart for 2-way BPT 50
Fig 3.7. Entry structure for 2-way BPT 51
Fig 4.1. Multiway BPT using sample prefix in Fig.2.1 53
Fig 4.2. Routing table for Multiway BPT 54
Fig 4.3. Usage of child valid bits 55
Fig 4.4. 4-way BPT using range table 55
Fig 4.5. Entry structure of Multiway BPT 56
Fig 5.1. Sample prefix fur EnBiT 58
Fig 5.2. Yazdani's tree using sample prefix in Fig.5.1 59
Fig 5.3. EnBiT using the sample prefix in Fig.5.1 60
Fig 5.4. Search flow chart for EnBiT 62
Fig 5.5. Update flow chart for EnBiT 64
Fig 5.6. Pipelining structure of Yazdani's tree 66
Fig 5.7. The first type EnBiT architecture 68
Fig 5.8. The second type EnBiT architecture 70
Fig 5.9. Entry structure for the first type EnBiT 71
Fig 5.10. Entry structure for the second type EnBiT 71
Fig 6.1. DPT_PC Architecture 73
Fig 6.2. Source-destination prefix pairs 74
Fig 6.3. 요ample rule set for DPT_PC 76
Fig 6.4. Examples of DPT 77
Fig 6.5. Example of main memory and rule memory fur DPT_PC 78
Fig 6.6. Entry structure for DPT_PC 80
Fig 7.1. Comparison of the average number of memory access between previous works and several… 89
Fig 7.2. Comparison of the maximum number of memory access between previous work and… 90
Fig 7.3. Comparison of the memory size between previous work and several proposed work 90
Fig 7.4. Comparison between previous packet classification architecture and proposed DPT_PC… 94
Fig 7.5. Comparison between previous packet classification architecture and proposed BPT_PC… 94