Scalable Algorithms for Communication Networks.
dc.contributor.author | Chen, Li-Yen | en_US |
dc.date.accessioned | 2010-08-27T15:07:46Z | |
dc.date.available | NO_RESTRICTION | en_US |
dc.date.available | 2010-08-27T15:07:46Z | |
dc.date.issued | 2010 | en_US |
dc.date.submitted | en_US | |
dc.identifier.uri | https://hdl.handle.net/2027.42/77713 | |
dc.description.abstract | Network scalability has emerged as the essential problem in designing architectures and protocols for large-scale communication systems. Minor efficiencies, that can be tolerated in small networks, can accumulate and become a dominant factor determining the performance of large networks. In this thesis, we consider three problems that are related to scalability. First, we examine the size of routing tables as the number of nodes in the network increases. It is shown that the widely used shortest-path and straightline routing algorithm can be implemented only when nodes’ memory increases with the network size. On the other hand, it is established that there exist information-efficient algorithms, e.g., column-first routing protocol, that route packets correctly even if each node in the network is capable of storing information on a fixed number of destinations only. In the second part, we present a novel computational model utilizing time encoding, that enables a distributed scheduling mechanism. The scheduling algorithm we propose achieves performance comparable to centralized algorithms under uniform traffic. Exploiting a connection between switch scheduling and interval packing, we argue that the distributed nature of the algorithm limits the maximum relative load to 1 − e^−2 under the worst-case scenario. The stability of the algorithm can be improved by enabling reversibility in distributed decision making. Finally, we discuss the bandwidth sharing problem for multi-hop networks. A buffer management policy that utilizes only simple packet attributes delivers a constant fraction of the maximum possible throughput. Moreover, the policy is robust to heavy traffic loads in the sense that the throughput does not degrade due to congestion. | en_US |
dc.format.extent | 1354445 bytes | |
dc.format.extent | 1373 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | en_US |
dc.subject | Scalable Algorithms | en_US |
dc.subject | Routing | en_US |
dc.subject | Switch Scheduling | en_US |
dc.subject | Bandwidth Sharing | en_US |
dc.title | Scalable Algorithms for Communication Networks. | en_US |
dc.type | Thesis | en_US |
dc.description.thesisdegreename | PhD | en_US |
dc.description.thesisdegreediscipline | Electrical Engineering: Systems | en_US |
dc.description.thesisdegreegrantor | University of Michigan, Horace H. Rackham School of Graduate Studies | en_US |
dc.contributor.committeemember | Momcilovic, Petar | en_US |
dc.contributor.committeemember | Liu, Mingyan | en_US |
dc.contributor.committeemember | Teneketzis, Demosthenis | en_US |
dc.contributor.committeemember | Van Oyen, Mark Peter | en_US |
dc.subject.hlbsecondlevel | Computer Science | en_US |
dc.subject.hlbsecondlevel | Electrical Engineering | en_US |
dc.subject.hlbtoplevel | Engineering | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/77713/1/liyen_1.pdf | |
dc.owningcollname | Dissertations and Theses (Ph.D. and Master's) |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.