Multiclass Scheduling and Congestion Control in Communication Networks

本文研究了计算机通信网络的多级调度和拥塞控制问题。 重点放在多个服务质量，包括吞吐量和延迟，并在多个类别的分组数据。 两个互补的研究课题得到解决。 第一个主题是具有多优先级和截止期的包的因果调度。 本文的目标是研究一种新的调度准则和相关算法，以处理具有截止期的多类业务的吞吐量和延迟的冲突要求。 第二个主题是端到端拥塞控制的多类实现，基于显式拥塞通知定价。 最近，Gibbens和Kelly提出了一个想法，即对网络路由器放置在数据包上的标记向网络用户收费。 数据包上的标记表示该数据包导致了拥塞。 本研究探讨了使用这种定价机制与增加了少量的数据包类和多类服务纪律的路由器，类的基础上。 在路由器处将对每个流的状态信息进行有限的使用或不使用。 该方法将执行建模、分析和设计。 模型将基于当前和预期的未来技术，并涵盖广泛的用户需求和网络拓扑。 分析技术将包括模拟，基于流体极限，扩散极限和大偏差理论的渐近分析，以及基于凸分析的Lyapunov函数的稳定性分析。 优化方法，如凸规划方法和组合优化，以及经典的调度理论将被使用。 非随机方法，如调查的样本路径的最优性能和竞争最优schooling也将被考虑。 所提出的研究的成功完成将提供（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.