Efficient Fair Queuing and Load Balancing

由于万维网和视频会议等新的多媒体服务的极大普及，互联网流量正在迅速增长。业务量的增加需要更高的速度(千兆位/秒或更高)的链路，而一些新的业务量(如音频和视频)也需要服务质量保证。该方案解决了通过组合多个低速链路并执行负载平衡来提供高速链路的问题。它还通过设计高效的公平排队算法来解决为高速链路提供服务质量保证的问题。该提案涉及设计、评估和实现新的、高效的公平排队和负载平衡算法。尽管这两个问题乍一看可能完全不同，但PI表明，公平排队算法可以使用时间反转参数转换为负载平衡算法。用于公平排队的现有机制要么在计算上昂贵，要么它们不能提供许多应用所需的必要服务保证(例如，延迟和吞吐量的良好界限)。PI开发了一种称为串联时钟公平排队的新的公平排队方案，其提供的服务质量保证可与先前最好的方案(例如加权公平排队)的那些方案相媲美，但似乎允许有效的实现。现有的负载平衡方法在存在可变长度分组的情况下提供不充分的负载共享，并且如果不允许修改分组报头，则可能导致数据的非FIFO传递。PI描述了新的负载平衡方案，通过将公平排队方案转换为负载平衡方案，并通过使用逻辑接收和发送器模拟的双重机制来解决这两个问题。研究人员建议将公平排队和负载平衡算法中的这些新方向进行提炼和扩展，使其成为可以部署在Internet和其他真实网络中的完整和可行的方案。他们计划使用数学分析、模拟和使用试验床的实际实施相结合的方式来评估和改进我们的方案。

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.