| In recent years the Internet has transformed from an early day low speed network connecting predominantly educational institutions to a fast growing commercial infrastructure. The diverse users of the Internet now range from ordinary home users to large corporations conducting sensitive transactions. The expectations in terms of security, privacy, performance, and reliability of these diverse users are dramatically different.Realizing this, Internet Service Providers (ISP) not only improve the speed of the backbone network, but also envision new differentiated network services such as Virtual Private Networks (VPN) that can meet demands of the full spectrum of clients. The link speed hasn't been performance bottleneck because of improving in Fiber Optics and DWDM, but IP routers can be main performance bottleneck because of requiring many complex operations such as fast packet classification.Packet classification is a technique to match each incoming packet at a router against a database of classifier and specify forwarding rules for the packets. The classifiers are a powerful and uniform way to implement new network services. The IP routing lookups belongs to one-dimension packet classification, and two-dimension packet classification is executed according to on IP source address and IP destination address, and five-dimension packet classification is executed according to on IP source address, IP destination address, source port, denstination port and protocol field. IP routing lookups is time-consuming because the part of an IP address used in the lookup, i.e. the network address portion, is variable in length, and packet classifications is also time-consuming because the keys used in the lookup is long.In this thesis an algorithm of IP routing lookups based on LSO (Lengthen Segment table and Lengthen Offset table) is proposed. The LSO algorithm is a ways to use 2 level table, but the length of each level is variable, the lengthen segment table can adapt to the changes in capacity of SRAM or memory in FPGA, the lengthen offset table can reduce memory space according to the prefix length of routing table. When the size of segment table is small and the memory that offset table occupied is large, graph theory compression techniques can be used to reduce the memory space. The best size of segment table can be computed according to actual routing table to minimize memory space. Also the size of segment table can be negotiated when the LSO algorithm is implemented by hardware. The LSO algorithm has characteristics such as fast search time, fast update time, small memory space and easy implementation, so it can be used in core routers that have lOGbps interfaces.In this thesis an algorithm of multi-dimension packet classification based on the SPLS (Shorter Prefix Length Splitting) is also proposed. The SPLS is realized by splitting a larger database of classifier into many smaller databases of classifier according to the shorter prefix length between the IP source address and IP destination address. After splitting it, the IP routing lookup algorithm can be used to the smaller database of classifier. Multi-bit trie (or n-ary trie) is the basic data structure for SPLS. In this thesis the performance when implementing SPLS in 2-ary trie, 4-ary trie, 8-ary trie and 16-ary trie has also been examined, and is found that the 4-ary trie is best. To improve the performance of SPLS, all children node of a node can be stored using continuous memory. In this way, the performance is found to be improved rapidly, and the lookup speed can be up to 4Mpps and the storage can be reduced to 3MB-6.5MB. To further improve the performance of SPLS, Path-Compress and Level-Compress techniques can be used. The algorithm has characteristics such as fast average search time, fast update time, allowing dynamic update, small memory space and suiting for large classifiers, so it is a better algorithm for Internet routers.In this thesis the design and implement action of a network layer output control component of a core router...
|
PDF Full Text Request