Files in this item



application/pdfJi_Tianxiong.pdf (1MB)
(no description provided)PDF


Title:The delay performance of adaptive routing and scheduling in communication networks
Author(s):Ji, Tianxiong
Director of Research:Srikant, Rayadurgam
Doctoral Committee Chair(s):Srikant, Rayadurgam
Doctoral Committee Member(s):Basar, Tamer; Coleman, Todd P.; Sreenivas, Ramavarapu S.; Vaidya, Nitin H.
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Communication Networks
Delay performance
Throughput optimal
Abstract:Throughput and latency are two important QoS metrics in communication networks. Ideally, we would like to deliver a large amount of data from a source to its destination within a short time period. During the past decades, researchers have designed a number of network-layer routing algorithms and MAC-layer scheduling algorithms to deliver good QoS performance under various network conditions. In this dissertation, we study the delay performance of routing and scheduling algorithms in communication networks. A collection of algorithms called MaxWeight Scheduling (MWS) algorithms is known to be throughput optimal. A particular algorithm in this class was conjectured to be delay-optimal as well. We disprove this conjectured by constructing a delay-optimal algorithm for a specific network and show that it outperforms the particular MWS algorithm. Next, we propose a packet-by-packet adaptive routing and scheduling algorithm for multi-hop traffic which dramatically reduces delays in the network, while maintaining near throughput optimality. This algorithm uses a particular routing table, called a probabilistic routing table, to adaptively find a route for every packet. The probabilistic routing table is generated by running an emulated network, called the shadow network, which is essentially a model of the real network with a slightly higher traffic load. The scheduling decisions are also determined by the shadow system. Our joint routing and scheduling algorithm reduces the capacity region slightly, but provides low delay performance everywhere in this reduced region. In addition, the queueing and routing architecture is more consistent with the architecture of current routers and switches. We also extend our results to the case where network coding is used to improved the throughput in the network. Our algorithm provides a low-complexity solution to optimally exploit the routing-coding tradeoff. Lastly, we consider wireless ad hoc networks in which each connection (file) traverses only one hop. We assume files arrive for service at each link and a file departs when all its packets have been transmitted. We consider two cases: one in which the file size distribution is arbitrary but has bounded support; another in which the file size distribution is a mixture of geometric distributions. The only assumption we make about the window flow control protocol is that the window size is always greater than zero. We show the following result: for an appropriately chosen MAC-layer scheduling algorithm, the network is stable for all file arrival rates within the capacity region. In other words, the MAC-layer scheduling algorithm, by only knowing the MAC-layer information, can achieve throughput optimality independently of the window flow control protocol used.
Issue Date:2012-05-22
Rights Information:Copyright 2012 Tianxiong Ji
Date Available in IDEALS:2012-05-22
Date Deposited:2012-05

This item appears in the following Collection(s)

Item Statistics