{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20036"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20036","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Communication with few buffers: Analysis and design","abstract":"Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:41:07Z Item is restricted indefinitely.","abstract_html":"Item marked as restricted to the &#x27;UIUC Users [automated]&#x27; Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:41:07Z Item is restricted indefinitely.","abstract_has_math":false,"creators":["Krishna, Arvind"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":["Hajek, Bruce"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:26:46Z","date_published":"2011-05-07T12:26:46Z","updated_at":"2026-07-22T22:25:15Z","subjects":["Engineering, Electronics and Electrical","Operations Research","Computer Science"],"languages":["eng"],"rights":["Copyright 1991 Krishna, Arvind"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9124446","(UMI)AAI9124446"],"render_values":[{"text":"AAI9124446","href":null,"code":true},{"text":"(UMI)AAI9124446","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20036","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hajek, Bruce"]},{"key":"dc:creator","label":"Author","values":["Krishna, Arvind"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:26:46Z","10000-01-01","1991"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"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":["Engineering, Electronics and Electrical","Operations Research","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1991 Krishna, Arvind"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9124446","(UMI)AAI9124446","http://hdl.handle.net/2142/20036"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:41:07Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:17:45-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","Various schemes for routing in high speed networks with few buffers are investigated. Deflection routing is an adaptive strategy for datagram routing which tries to diffuse congestion wherever it arises in the network. Deflection routing on a shuffle-exchange network under uniform traffic is analyzed by using approximate state equations to predict the distribution of packet states. Whenever two packets simultaneously attempt to traverse a link, a conflict resolution rule is invoked to determine which packet is deflected. It is shown that giving priority to packets closest to their destinations is the optimal conflict resolution rule, in a certain sense. The state equations, for two different priority rules, are also used to derive bounds on the probable amount of time needed for the network to empty and to explore the relationship between delay and throughput in steady state. It is demonstrated that the choice of priority rule greatly influences the performance of the network. Deflection routing is also studied on some other networks based on shuffle interconnections.","The second topic is concerned with circuit-switched communication networks in which each route is two links long, and each link can carry one call at a time. No symmetry assumption is made. Simple bounds, depending on the maximum call arrival rate and the maximum sum of rates at a link, are given on the blocking probabilities. An implication is that if the maximum per-route arrival rate converges to zero with a fixed bound on the sum of rates at links, then the well-known reduced-load blocking approximation is asymptotically exact, uniformly over all network topologies.","The third and final topic studied is packet routing on bounded degree networks, where the size of the buffers at each node is constrained to be small. An algorithm is presented which does packet routing on an N-node butterfly in time O(log N) with small constants. The algorithm is based on Ranade's probabilistic PRAM emulation. Bounds on performance of the algorithm are proven for permutation routing and partially balanced traffic. The network is divided into 2$\\sp n$ disjoint sets of n nodes, N = n2$\\sp n$, and k-partially balanced traffic is such that no given set of nodes has to send or receive more than kn packets. The main results are upper bounds on the probability that the routing time exceeds t for a fixed queue size. It is shown that if t = $\\Omega$(log N), then the probability is less than $c\\alpha\\sp t$, where $c$,$\\alpha$ $<$ 1. Bounds on the routing time for uniform, random traffic follow as a special case of partially balanced traffic.","Made available in DSpace on 2011-05-07T12:26:46Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9124446.pdf: 4959057 bytes, checksum: bccb257f0fce6c3111ad683602c56f85 (MD5) Previous issue date: 1991","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Communication with few buffers: Analysis and design"]}]}],"canonical_facts":{"dc:contributor":["Hajek, Bruce"],"dc:creator":["Krishna, Arvind"],"dc:date":["2011-05-07T12:26:46Z","10000-01-01","1991"],"dc:description":["Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:41:07Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:17:45-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","Various schemes for routing in high speed networks with few buffers are investigated. Deflection routing is an adaptive strategy for datagram routing which tries to diffuse congestion wherever it arises in the network. Deflection routing on a shuffle-exchange network under uniform traffic is analyzed by using approximate state equations to predict the distribution of packet states. Whenever two packets simultaneously attempt to traverse a link, a conflict resolution rule is invoked to determine which packet is deflected. It is shown that giving priority to packets closest to their destinations is the optimal conflict resolution rule, in a certain sense. The state equations, for two different priority rules, are also used to derive bounds on the probable amount of time needed for the network to empty and to explore the relationship between delay and throughput in steady state. It is demonstrated that the choice of priority rule greatly influences the performance of the network. Deflection routing is also studied on some other networks based on shuffle interconnections.","The second topic is concerned with circuit-switched communication networks in which each route is two links long, and each link can carry one call at a time. No symmetry assumption is made. Simple bounds, depending on the maximum call arrival rate and the maximum sum of rates at a link, are given on the blocking probabilities. An implication is that if the maximum per-route arrival rate converges to zero with a fixed bound on the sum of rates at links, then the well-known reduced-load blocking approximation is asymptotically exact, uniformly over all network topologies.","The third and final topic studied is packet routing on bounded degree networks, where the size of the buffers at each node is constrained to be small. An algorithm is presented which does packet routing on an N-node butterfly in time O(log N) with small constants. The algorithm is based on Ranade's probabilistic PRAM emulation. Bounds on performance of the algorithm are proven for permutation routing and partially balanced traffic. The network is divided into 2$\\sp n$ disjoint sets of n nodes, N = n2$\\sp n$, and k-partially balanced traffic is such that no given set of nodes has to send or receive more than kn packets. The main results are upper bounds on the probability that the routing time exceeds t for a fixed queue size. It is shown that if t = $\\Omega$(log N), then the probability is less than $c\\alpha\\sp t$, where $c$,$\\alpha$ $<$ 1. Bounds on the routing time for uniform, random traffic follow as a special case of partially balanced traffic.","Made available in DSpace on 2011-05-07T12:26:46Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9124446.pdf: 4959057 bytes, checksum: bccb257f0fce6c3111ad683602c56f85 (MD5) Previous issue date: 1991","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9124446","(UMI)AAI9124446","http://hdl.handle.net/2142/20036"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Krishna, Arvind"],"dc:subject":["Engineering, Electronics and Electrical","Operations Research","Computer Science"],"dc:title":["Communication with few buffers: Analysis and design"],"dc:type":["text"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:15Z"}