Traffic characterization, admission control and packet scheduling are important traffic management functions needed for provisioning QoS in Integrated Services Networks. In my thesis I have done a preliminary examination of traffic characterization and admission control and extensive examination of packet scheduling algorithms in the context of hard real-time quality of service (QoS) guarantees. Such QoS guarantees, also called Deterministic QoS Guarantees, provide a mathematically provable guarantee on end-to-end packet delays, delay jitters, and throughput. I have also discussed QoS, scheduling and capacity allocation issues in the context of Virtual Private Networks (VPNs).
In a QoS enabled network, in addition to carrying out switching, the packet switches/routers also need to carry scheduling of packets on their communication lines. Communication technologies are getting faster day by day and the underlying switching technologies are struggling to catch up with these improvements. Packet scheduling adds an overhead to the basic switching functionality of these switches/routers. Therefore, the time available to make a scheduling decision is very small (of the order of a few CPU cycles).
Packet Scheduling Algorithms: A major contribution in my thesis is a new scheduling algorithm called the Recursive Round Robin (RRR) scheduler. Most of the existing packet scheduling algorithms are either too simple (FCFS, simple priorities) and cannot provide reasonable QoS guarantees, or very elaborate (WFQ, WF2Q, SCFQ, EDF etc.) providing extensive QoS guarantees but are difficult to implement in a high speed network. Visit the following link for a comprehensive list of papers on packet scheduling algorithms (with Internet pointers).
RRR is able to provide deterministic QoS guarantees and at the same time is simpler to implement than most other schedulers that provide similar QoS guarantees. RRR operates on fixed sized packets and needs simple bit manipulation operations to make scheduling decisions. Thus it can operate at very high speeds. There are several variants of the basic scheduler, including the variable size packet scheduler. RRR seeks a good balance between simplicity of implementation and the extent of QoS guarantees.
Virtual Private Networks: Another trend is communication networks is the evolution of virtual private networks (VPNs). Virtual private networks replace the traditional private networks, by replacing the dedicated leased communication lines, by shared virtual lines. Traffic of multiple virtual leased lines is aggregated and carried on a single physical link thereby improving the utilization and lowering the costs. QoS in virtual leased lines will become more and more important in the future. My thesis presents a generic framework for packet schedulers providing deterministic guarantees in VPNs. It also suggests two variants of the RRR scheduler for virtual networks.
Capacity Resizing: Finally the thesis contains a discussion of a capacity resizing approach to dynamically provision the capacities of virtual links. This dynamic capacity resizing approach improves sharing in virtual networks thereby lowering the costs. However, there are important admission control, fairness, pricing and SLA issues that need to be discussed in this context. My thesis suggests a new trunk-reservation based admission control technique called Stochastic Fair Sharing (SFS). Most of the earlier trunk reservation schemes used in telecommunication networks attempt to increase utilization and/or maximize revenues. SFS aims towards fair sharing of the resources. Since the theoretical treatment of the subject is a difficult problem, the thesis evaluates the proposed scheme using simulations.
Click for abstract,
synopsis and thesis (5MB).
Here are the postscript versions of synopsis and thesis.