Efficient Fair Queuing and Load Balancing

由于万维网和新的多媒体服务（如视频会议）的广泛普及，互联网流量正在迅速增长。增加的通信量需要更高的速度（千兆位/秒或更高）的链路，而一些新的流量品种（如音频和视频）也要求服务质量保证。该方案解决了通过组合多个低速链路并进行负载均衡来提供高速链路的问题。通过设计高效的公平排队算法，解决了高速链路的服务质量保证问题。该提案是有关设计，评估和实现新的和有效的公平排队和负载平衡算法。虽然这两个问题乍一看可能完全不同，但Pis表明，公平排队算法可以使用时间反转参数转换为负载平衡算法。现有的公平排队机制要么在计算上很昂贵，要么无法提供许多应用程序所需的必要的服务保证（例如，延迟和吞吐量的良好界限）。pi开发了一种新的公平排队方案，称为串联时钟公平排队，它提供了与以前最好的方案（如加权公平排队）相当的服务质量保证，并且似乎承认有效的实现。现有的负载平衡方法在存在可变长度的数据包时不能提供足够的负载共享，如果不允许修改数据包头，则可能导致数据的非fifo交付。pi描述了新的负载平衡方案，通过将公平排队方案转换为负载平衡方案，并使用逻辑接收和发送方模拟的孪生机制来解决这两个问题。研究人员建议完善和扩展公平排队和负载平衡算法的这些新方向，使其成为可以在互联网和其他真实网络中部署的完整可行的方案。他们计划使用数学分析、模拟和使用测试平台的实际实现的组合来评估和改进我们的方案。

Internet traffic is growing rapidly due to the immense popularity of the World Wide Web and new multimedia services such as video-conferencing. The increased traffic volume requires higher speed (Gigabit/sec or higher) links, while some of the new traffic varieties (such as audio and video) also demand quality-of-service guarantees. This proposal addresses the problem of providing high speed links by combining multiple low speed links and performing load balancing. It also address the problem of providing quality of service guarantees for high speed links through the design of efficient fair queuing algorithms. The proposal is concerned with the design, evaluation, and implementation of new and efficient fair queuing and load balancing algorithms. Although these two problems may look quite different at a first glance, the Pis show that fair queuing algorithms can be converted into load balancing algorithms using a time-reversal argument. Existing mechanisms for fair queuing either are computationally expensive, or they fail to provide the necessary service guarantees (e.g., good bounds on latency and throughput) required by many applications. The PIs develop a new fair queuing scheme called Tandem Clock Fair Queuing, which offers quality-of-service guarantees comparable to those of the best previous schemes (such as Weighted Fair Queuing), and yet appears to admit efficient implementations. Existing methods for load balancing provide inadequate load sharing in the presence of variable length packets, and may result in non-FIFO delivery of data if packet headers are not allowed to be modified. The PIs describe new load balancing schemes that solve these two problems by transforming fair queuing schemes into load balancing schemes, and by using the twin mechanisms of logical reception and sender simulation. The investigators propose to refine and extend these new directions in fair queuing and load balancing algorithms into complete and workable schem es that can be deployed in the Internet and other real networks. They plan to evaluate and refine our schemes using a combination of mathematical analysis, simulations, and actual implementation using a testbed.