title page
Contents
Abstract 11
1. Introduction 13
1.1. IP Address Lookup 13
1.2. Packet Classification 14
1.3. Organization of the Dissertation 15
2. Related Work 17
2.1. IP Address Lookup Schemes 17
2.2. Packet Classification Schemes 19
2.2.1. Characteristics of Real Classifiers 19
2.2.2. Existing Schemes 22
3. Parallel Multiple Hashing for IP Address Lookup 24
3.1. Address Lookup using Multiple Hashing 24
3.2. Parallel Multiple Hashing for IP Address Lookup 25
3.2.1. Parallel Lookup 27
3.2.2. Multiple Hashing using CRC 27
3.2.3. Forwarding Table Construction 29
3.2.4. Searching Forwarding Tables 33
3.2.5. Overflow Table 36
3.2.6. Update and Expansion to IPv6 36
4. Parallel Multiple Hashing for Packet Classification 37
4.1. Tuple Space 37
4.2. Hash Function 40
4.3. Two Step Process 42
4.4. Building Procedure 43
4.5. Searching Procedure 47
4.6. Overflow 49
4.7. Update 49
5. Two-Dimensional Binary Prefix Tree for racket Classification 51
5.1. Binary Prefix Tree 53
5.2. Two-Dimensional Binary Prefix Tree 55
5.2.1. Codeword Generation 55
5.2.2. Multiple Balanced Tree 57
5.2.3. Conversion to Longest Matching 58
5.2.4. Building Procedure 59
5.2.5. Searching Procedure 66
6. Simulation Result and Performance Comparison 68
7. Conclusion 81
Reference 83
Appendix 85
감사의 글 100
Table 2.1. Variety in each field 20
Table 2.2. The number of collisions according to different cases 21
Table 4.1. Hash Key Extraction 39
Table 5.1. Example Classifier 52
Table 6.1. PMH-IP - Memory size and Entry efficiency Analysis 71
Table 6.2. Performance Comparison of IP Address Lookup Schemes 72
Table 6.3. PMH-PC - Memory Accesses and Size 75
Table 6.4. 2D-BPT - The Number of Memory Access 77
Table 6.5. 2D-BPT - Required Memory Size 78
Table 6.6. Performance Comparison of packet Classification Schemes… 80
Figure 3.1. Routing table construction using multiple hash functions 24
Figure 3.2. Proposed hardware structure - Parallel Multiple Hashing 26
Figure 3.3. CRC-32 28
Figure 3.4. Entry structure of the forwarding table of PMH-IP 29
Figure 3.5. Building Algorithm of PMH-IP 31
Figure 3.6. Construction procedure of forwarding table 32
Figure 3.7. Searching Algorithm of PMH-IP 34
Figure 3.8. Search procedure of forwarding table 35
Figure 4.1. Tuple group for hash functions 41
Figure 4.2. Hash key for each tuples 41
Figure 4.3. Two Step Process 42
Figure 4.4. Table structures of PMH-PC 44
Figure 4.5. Flowchart of building procedure of PMH-PC 46
Figure 4.6. Flowchart of searching procedure of PMH-PC 48
Figure 4.7. Flowchart of deleting procedure of PMH-PC 50
Figure 5.1. Definition of Binary prefix Tree 54
Figure 5.2. Codeword Generation 56
Figure 5.3. Procedure for 2D-BPT Construction 58
Figure 5.4. Conversion to Longest Matching using Stack Pointer 59
Figure 5.5. Proposed Scheme -2D-BPT 61
Figure 5.6. Hierarchical Trie 62
Figure 5.7. AQT 63
Figure 5.8. Table structures of 2D-BPT 65
Figure 6.1. Prefixes Distribution of MAE-WEST Router 69
Figure 6.2. Rule Distribution for each tuple 74