Fast Scalable Level Four Switching

点击翻译按钮获取中文摘要

Looking up the route to send a message is a major bottleneck in traditionalInternet Routers. Traditional routers only use the destination address ina message to determine how to forward the message. However, in the lastfew years, there have been proposals for more sophisticated routers thatare capable of what is called Layer 4 Switching. We believe that thecapabilities provided by Layer 4 Switching in terms of security, quality ofservice, and guaranteed service will make Layer 4 Switching an integralpart of the Next Generation Internet.In Layer Four switching, the route and resources allocated to a packet aredetermined by the destination address as well as other header fields of thepacket (such as source address, TCP port numbers etc.). Layer FourSwitching unifies a number of recent trends (such as firewall processing,resource reservation, providing virtual private networks) into a singleframework. The forwarding database of this new kind of router consists ofa potentially large number of filters on key header fields. A given packetheader can match multiple filters; thus each filter is given a cost, andthe packet is forwarded using the least cost filter that matches the packetheaders.The flexibility and service differentiation provided by Layer 4 Switchingcomes at a cost. Given that traditional Internet forwarding based only ondestination addresses is itself a challenge to implement at Gigabit speeds,Layer 4 Switching at Gigabit speeds is a difficult problem for nextgeneration routers. In this proposal, we address the question of designingand implementing fast algorithms for Layer 4 Switching that can beimplemented at Gigabit speeds even with hundreds of thousands of filters.We introduce three promising candidate algorithms (cross-producting, Gridof Tries, and Tuple Search). We propose to implement, evaluate, andfine-tune these new ideas, consider combination schemes, and to search forother fast algorithms for fast filter matching. As part of our proposal weplan to design a chip capable of doing Layer 4 Switching at Gigabit speeds.