QoS support in large-scale computer networks based on aggregate scheduling and BGP routing enhancement

Packet scheduling and routing are two basic functions of a data network. Packet scheduling determines the order of packets to be transmitted from a network device to its neighbor, while routing selects a path between two network devices. To provide Quality of Service (QoS) in the current Internet to support emerging real-time, multimedia applications such as voice over IP (VoIP) and Internet Protocol Television (IPTV), it is important to have high-performance, low-cost scheduling algorithms, as well as efficient routing algorithms that converge to new routes quickly when network changes occur. This thesis focuses on QoS support in packet scheduling and routing. For scheduling, we evaluate, via both analysis and simulation, the end-to-end (e2e) delay performance of aggregate scheduling with guaranteed-rate (GR) algorithms. Aggregate scheduling is shown theoretically to provide bounded e2e delays, and practically to provide excellent e2e delay performance. Moreover, it incurs lower scheduling and state-maintenance overheads at routers than per-flow scheduling. For routing, we enhance Border Gateway Protocol (BGP), the de facto inter-domain routing protocol in the Internet. We propose a simple and novel idea of differentiated processing of BGP updates to reduce routers' load and improve routing convergence. Based on a set of criteria, BGP updates are grouped into different priority classes. Higher-priority updates are processed and propagated sooner, while lower-priority ones, not affecting routing decisions, can be delayed to both reduce routers' load and improve routing convergence. This scheme is shown to be very effective for large networks, yielding 30% fewer updates and reducing convergence time by 80%. We also study the impact of BGP routing changes on application traffic, showing that (1) for busy prefixes with high traffic volumes, the amount of routing changes are generally smaller confirming previous studies and (2) the number of route withdrawals is generally much smaller for busy prefixes. We propose an improved BGP route selection algorithm to reduce the number of routing changes globally so that the resulting traffic shift is also reduced. We evaluate the effectiveness of this algorithm with a local ISP's data and demonstrate that for busy prefixes it can reduce as much as 30% of routing changes.