Multiclass Scheduling and Congestion Control in Communication Networks

通信网络中的多类调度和拥塞控制

• 批准号: 9980544
• 负责人: Bruce Hajek
• 金额: $ 29.96万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-08-15 至 2006-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9980544&HistoricalAwards=false
• 关键词: Multiclass; Scheduling; Congestion; Control; Communication

Research on multiclass scheduling and congestion control for computer communication networksis proposed. Emphasis is placed on multiple qualities of service, including throughput and delay,and on multiple classes of packet data. Two complementary research topics are addressed. Thefirst topic is causal scheduling of packets with multiple priority classes and deadlines. The goalis to investigate a new scheduling criterion and related algorithms for dealing with conflictingrequirements for throughput and delay for multiclass traffic with deadlines. The second topic is multiclass implementations of end-to-end congestion control, with pricingbased on explicit congestion notification. Recently Gibbens and Kelly proposed the idea of chargingnetwork users for marks placed on packets by network routers. A mark on a packet is an indicationthat the packet caused congestion. This research explores the use of this pricing mechanism withthe addition of a small number of packet classes and a multiclass service discipline at the routers,based on the classes. Limited or no use of per flow state information will be made at the routers. The approach will be to perform modeling, analysis, and design. Models will be based on current and anticipated future technology, and cover a broad spectrum of user demands and networktopologies. The analysis techniques will include simulation, asymptotic analysis based on fluid limits, diffusion limits, and large deviation theory, and stability analysis based on Lyapunov functionsderived from convex analysis. Methods for optimization, such as convex programming methods andcombinatorial optimization, and classical scheduling theory will be used. Nonstochastic methodssuch as investigation of sample path optimality properties and competitively optimal schedulingwill also be considered. Successful completion of the proposed research will provide (1) improved algorithms for scheduling multiclass traffic with strict time constraints, (2) an improved understanding of the implementation choices and the value of congestion based pricing using a small number of packet classes for the purpose of end-to-end congestion control in large scale networks, and (3) new mechanisms for end-to-end congestion control in large-scale computer communication networks.

提出了计算机通信网络多类调度和拥塞控制的研究。 重点放在多种服务质量上，包括吞吐量和延迟，以及多种分组数据类别。 解决了两个互补的研究主题。 第一个主题是具有多个优先级类别和截止时间的数据包的因果调度。 目标是研究一种新的调度标准和相关算法，以处理具有截止日期的多类流量的吞吐量和延迟的冲突要求。 第二个主题是端到端拥塞控制的多类实现，其定价基于显式拥塞通知。 最近，吉本斯和凯利提出了向网络用户收取网络路由器在数据包上标记的费用的想法。 数据包上的标记表明该数据包导致了拥塞。 本研究探索了这种定价机制的使用，并在路由器上添加了少量数据包类别和基于类别的多类别服务规则。 路由器将有限地使用或不使用每个流状态信息。 该方法将执行建模、分析和设计。 模型将基于当前和预期的未来技术，并涵盖广泛的用户需求和网络拓扑。 分析技术将包括模拟、基于流体极限、扩散极限和大偏差理论的渐近分析，以及基于凸分析导出的李亚普诺夫函数的稳定性分析。 将使用凸规划方法和组合优化等优化方法以及经典调度理论。 还将考虑非随机方法，例如样本路径最优性研究和竞争性最优调度。 成功完成所提出的研究将提供（1）在严格时间限制下调度多类流量的改进算法，（2）更好地理解实现选择和使用少量数据包类别的基于拥塞的定价的价值大规模网络中的端到端拥塞控制，以及（3）大规模计算机通信网络中端到端拥塞控制的新机制。