Fast Scalable Level Four Switching

查找发送消息的路由是传统互联网路由器的主要瓶颈。传统的路由器只使用消息中的目的地址来决定如何转发消息。然而，在过去的几年里，有人提出了更复杂的路由器，能够实现所谓的第4层交换。我们相信，第4层交换在安全性、服务质量和有保障的服务方面提供的能力将使第4层交换成为下一代互联网不可或缺的一部分。在第四层交换中，分配给数据包的路由和资源由目的地址以及数据包的其他报头字段（如源地址，TCP端口号等）决定。第四层交换将许多最新趋势（如防火墙处理、资源预留、提供虚拟专用网）统一到一个框架中。这种新型路由器的转发数据库由潜在的大量关键报头字段过滤器组成。一个给定的包头可以匹配多个过滤器；因此，每个过滤器都有一个开销，并且使用与包头匹配的最小开销过滤器转发数据包。第4层交换提供的灵活性和服务差异化是有代价的。考虑到仅基于目的地址的传统互联网转发本身就是实现千兆速度的挑战，千兆速度的第4层交换对下一代路由器来说是一个难题。在本提案中，我们解决了为第4层交换设计和实现快速算法的问题，即使使用数十万个滤波器，也可以以千兆速度实现。我们介绍了三种有前途的候选算法（交叉生成、Gridof Tries和元组搜索）。我们建议实现、评估和微调这些新想法，考虑组合方案，并寻找其他快速滤波器匹配的快速算法。作为我们提案的一部分，我们计划设计一个能够以千兆速度进行第4层交换的芯片。

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.