{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/45341"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/45341","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fundamental limits of random access in wireless networks","abstract":"Random access schemes are simple and inherently distributed, yet could provide the striking capability to match the optimal throughput performance (maximum stability region) of centralized scheduling mechanisms. The throughput optimality however has been established for activation rules that are relatively sluggish, and may yield excessive queues and delays. More aggressive/persistent access schemes have the potential to improve the delay performance, but it is not clear if they can offer any universal throughput optimality guarantees. In this thesis, we identify a fundamental limit on the aggressiveness of nodes, beyond which instability is bound to occur in a broad class of networks. We will mainly consider adapting transmission lengths by considering a weight for each node as a function of its queue size. The larger the weight, the longer the node will hold on to the channel once it starts a transmission. We first show that it is sufficient for weights to behave as logarithmic functions of the queue sizes, divided by an arbitrarily slowly increasing function. This result indicates that the maximum-stability guarantees are preserved for weights that are essentially logarithmic for all practical queue sizes, although asymptotically the weight must grow slower than any logarithmic function of the queue size. We then demonstrate instability for weights that grow faster than logarithmic functions of queue sizes in networks with sufficiently many nodes. Our stability and instability results hence imply that the ``near-logarithmic growth condition'' on the weights is a fundamental limit on the aggressiveness of nodes to ensure maximum stability in any general topology. We will conduct simulation experiments to illustrate and validate the analytical results. Finally, we will combine the random access scheme with window-based flow control mechanisms to provide maximum throughput and Quality-of-Service in multihop wireless networks with dynamic flows.","abstract_html":"Random access schemes are simple and inherently distributed, yet could provide the striking capability to match the optimal throughput performance (maximum stability region) of centralized scheduling mechanisms. The throughput optimality however has been established for activation rules that are relatively sluggish, and may yield excessive queues and delays. More aggressive/persistent access schemes have the potential to improve the delay performance, but it is not clear if they can offer any universal throughput optimality guarantees. In this thesis, we identify a fundamental limit on the aggressiveness of nodes, beyond which instability is bound to occur in a broad class of networks. We will mainly consider adapting transmission lengths by considering a weight for each node as a function of its queue size. The larger the weight, the longer the node will hold on to the channel once it starts a transmission. We first show that it is sufficient for weights to behave as logarithmic functions of the queue sizes, divided by an arbitrarily slowly increasing function. This result indicates that the maximum-stability guarantees are preserved for weights that are essentially logarithmic for all practical queue sizes, although asymptotically the weight must grow slower than any logarithmic function of the queue size. We then demonstrate instability for weights that grow faster than logarithmic functions of queue sizes in networks with sufficiently many nodes. Our stability and instability results hence imply that the ``near-logarithmic growth condition'' on the weights is a fundamental limit on the aggressiveness of nodes to ensure maximum stability in any general topology. We will conduct simulation experiments to illustrate and validate the analytical results. Finally, we will combine the random access scheme with window-based flow control mechanisms to provide maximum throughput and Quality-of-Service in multihop wireless networks with dynamic flows.","abstract_has_math":false,"creators":["Ghaderi Dehkordi, Javad"],"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","Hajek, Bruce","Nedich, Angelia","Shroff, Ness B.","Viswanath, Pramod"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-08-22T16:37:10Z","date_published":"2013-08-22T16:37:10Z","updated_at":"2026-07-22T22:25:34Z","subjects":["Wireless Networks","Distributed Algorithms","Scheduling","Stability","Instability","Markov Chains","Mixing Time","Fluid Limits"],"languages":["en"],"rights":["Copyright 2013 Javad Ghaderi Dehkordi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/45341","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Srikant, Rayadurgam","Hajek, Bruce","Nedich, Angelia","Shroff, Ness B.","Viswanath, Pramod"]},{"key":"dc:creator","label":"Author","values":["Ghaderi Dehkordi, Javad"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-08-22T16:37:10Z","2013-08"]},{"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":["Wireless Networks","Distributed Algorithms","Scheduling","Stability","Instability","Markov Chains","Mixing Time","Fluid Limits"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Javad Ghaderi Dehkordi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/45341"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Random access schemes are simple and inherently distributed, yet could provide the striking capability to match the optimal throughput performance (maximum stability region) of centralized scheduling mechanisms. The throughput optimality however has been established for activation rules that are relatively sluggish, and may yield excessive queues and delays. More aggressive/persistent access schemes have the potential to improve the delay performance, but it is not clear if they can offer any universal throughput optimality guarantees. In this thesis, we identify a fundamental limit on the aggressiveness of nodes, beyond which instability is bound to occur in a broad class of networks. We will mainly consider adapting transmission lengths by considering a weight for each node as a function of its queue size. The larger the weight, the longer the node will hold on to the channel once it starts a transmission. We first show that it is sufficient for weights to behave as logarithmic functions of the queue sizes, divided by an arbitrarily slowly increasing function. This result indicates that the maximum-stability guarantees are preserved for weights that are essentially logarithmic for all practical queue sizes, although asymptotically the weight must grow slower than any logarithmic function of the queue size. We then demonstrate instability for weights that grow faster than logarithmic functions of queue sizes in networks with sufficiently many nodes. Our stability and instability results hence imply that the ``near-logarithmic growth condition'' on the weights is a fundamental limit on the aggressiveness of nodes to ensure maximum stability in any general topology. We will conduct simulation experiments to illustrate and validate the analytical results. Finally, we will combine the random access scheme with window-based flow control mechanisms to provide maximum throughput and Quality-of-Service in multihop wireless networks with dynamic flows.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-06-24T18:46:15Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Ghaderi Dehkordi-Javad.pdf: 2567540 bytes, checksum: eea531df6b0b4da7c8cb9c20f3891d16 (MD5) Ghaderi Dehkordi_Javad.pdf: 2567540 bytes, checksum: eea531df6b0b4da7c8cb9c20f3891d16 (MD5)","Made available in DSpace on 2013-08-22T16:37:10Z (GMT). No. of bitstreams: 2 Javad_Ghaderi Dehkordi.pdf: 2567540 bytes, checksum: eea531df6b0b4da7c8cb9c20f3891d16 (MD5) license.txt: 4072 bytes, checksum: 10fc1c7c58c726152a787b05a459cb72 (MD5)"]},{"key":"dc:title","label":"Title","values":["Fundamental limits of random access in wireless networks"]}]}],"canonical_facts":{"dc:contributor":["Srikant, Rayadurgam","Hajek, Bruce","Nedich, Angelia","Shroff, Ness B.","Viswanath, Pramod"],"dc:creator":["Ghaderi Dehkordi, Javad"],"dc:date":["2013-08-22T16:37:10Z","2013-08"],"dc:description":["Random access schemes are simple and inherently distributed, yet could provide the striking capability to match the optimal throughput performance (maximum stability region) of centralized scheduling mechanisms. The throughput optimality however has been established for activation rules that are relatively sluggish, and may yield excessive queues and delays. More aggressive/persistent access schemes have the potential to improve the delay performance, but it is not clear if they can offer any universal throughput optimality guarantees. In this thesis, we identify a fundamental limit on the aggressiveness of nodes, beyond which instability is bound to occur in a broad class of networks. We will mainly consider adapting transmission lengths by considering a weight for each node as a function of its queue size. The larger the weight, the longer the node will hold on to the channel once it starts a transmission. We first show that it is sufficient for weights to behave as logarithmic functions of the queue sizes, divided by an arbitrarily slowly increasing function. This result indicates that the maximum-stability guarantees are preserved for weights that are essentially logarithmic for all practical queue sizes, although asymptotically the weight must grow slower than any logarithmic function of the queue size. We then demonstrate instability for weights that grow faster than logarithmic functions of queue sizes in networks with sufficiently many nodes. Our stability and instability results hence imply that the ``near-logarithmic growth condition'' on the weights is a fundamental limit on the aggressiveness of nodes to ensure maximum stability in any general topology. We will conduct simulation experiments to illustrate and validate the analytical results. Finally, we will combine the random access scheme with window-based flow control mechanisms to provide maximum throughput and Quality-of-Service in multihop wireless networks with dynamic flows.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-06-24T18:46:15Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Ghaderi Dehkordi-Javad.pdf: 2567540 bytes, checksum: eea531df6b0b4da7c8cb9c20f3891d16 (MD5) Ghaderi Dehkordi_Javad.pdf: 2567540 bytes, checksum: eea531df6b0b4da7c8cb9c20f3891d16 (MD5)","Made available in DSpace on 2013-08-22T16:37:10Z (GMT). No. of bitstreams: 2 Javad_Ghaderi Dehkordi.pdf: 2567540 bytes, checksum: eea531df6b0b4da7c8cb9c20f3891d16 (MD5) license.txt: 4072 bytes, checksum: 10fc1c7c58c726152a787b05a459cb72 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/45341"],"dc:language":["en"],"dc:rights":["Copyright 2013 Javad Ghaderi Dehkordi"],"dc:subject":["Wireless Networks","Distributed Algorithms","Scheduling","Stability","Instability","Markov Chains","Mixing Time","Fluid Limits"],"dc:title":["Fundamental limits of random access in wireless 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:34Z"}