Multiclass Scheduling and Congestion Control in Communication Networks

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

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.