{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/30890"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/30890","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"The delay performance of adaptive routing and scheduling in communication networks","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ji, Tianxiong"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Srikant, Rayadurgam","Basar, Tamer","Coleman, Todd P.","Sreenivas, Ramavarapu S.","Vaidya, Nitin H."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-05-22T00:13:31Z","date_published":"2012-05-22T00:13:31Z","updated_at":"2026-07-22T22:25:29Z","subjects":["Routing","Scheduling","Communication Networks","Delay performance","Connection-level","Adaptive","Throughput optimal"],"languages":["en"],"rights":["Copyright 2012 Tianxiong Ji"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/30890","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Srikant, Rayadurgam","Basar, Tamer","Coleman, Todd P.","Sreenivas, Ramavarapu S.","Vaidya, Nitin H."]},{"key":"dc:creator","label":"Author","values":["Ji, Tianxiong"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-05-22T00:13:31Z","2012-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Routing","Scheduling","Communication Networks","Delay performance","Connection-level","Adaptive","Throughput optimal"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 Tianxiong Ji"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/30890"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-01-09T18:37:30Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Ji_Tianxiong_Latex.zip: 122961 bytes, checksum: 51b5ed815362bbe29a2224be31e03dec (MD5) Ji_Tianxiong.pdf: 1434447 bytes, checksum: 181f582fcf1a9035aac667dd22929bf6 (MD5)","Made available in DSpace on 2012-05-22T00:13:31Z (GMT). No. of bitstreams: 3 Ji_Tianxiong.pdf: 1434447 bytes, checksum: 181f582fcf1a9035aac667dd22929bf6 (MD5) Ji_Tianxiong_Latex.zip: 122961 bytes, checksum: 51b5ed815362bbe29a2224be31e03dec (MD5) license.txt: 4058 bytes, checksum: 5d732b1db6185429acbdab67a61becb9 (MD5)"]},{"key":"dc:title","label":"Title","values":["The delay performance of adaptive routing and scheduling in communication networks"]}]}],"canonical_facts":{"dc:contributor":["Srikant, Rayadurgam","Basar, Tamer","Coleman, Todd P.","Sreenivas, Ramavarapu S.","Vaidya, Nitin H."],"dc:creator":["Ji, Tianxiong"],"dc:date":["2012-05-22T00:13:31Z","2012-05"],"dc:description":["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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-01-09T18:37:30Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Ji_Tianxiong_Latex.zip: 122961 bytes, checksum: 51b5ed815362bbe29a2224be31e03dec (MD5) Ji_Tianxiong.pdf: 1434447 bytes, checksum: 181f582fcf1a9035aac667dd22929bf6 (MD5)","Made available in DSpace on 2012-05-22T00:13:31Z (GMT). No. of bitstreams: 3 Ji_Tianxiong.pdf: 1434447 bytes, checksum: 181f582fcf1a9035aac667dd22929bf6 (MD5) Ji_Tianxiong_Latex.zip: 122961 bytes, checksum: 51b5ed815362bbe29a2224be31e03dec (MD5) license.txt: 4058 bytes, checksum: 5d732b1db6185429acbdab67a61becb9 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/30890"],"dc:language":["en"],"dc:rights":["Copyright 2012 Tianxiong Ji"],"dc:subject":["Routing","Scheduling","Communication Networks","Delay performance","Connection-level","Adaptive","Throughput optimal"],"dc:title":["The delay performance of adaptive routing and scheduling in communication networks"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:29Z"}