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.