{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/85760"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/85760","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Practical algorithms for distributed network control","abstract":"Optimal routing and scheduling algorithms have been studied for decades, however several practical issues prevent the adoption of these network control policies on the Internet. This thesis considers two distinct topics in distributed network control: (i) maximizing throughput in wireless networks using network coding, and (ii) deploying controllable nodes in legacy networks. Network coding is a relatively new technique that allows for an increase in throughput under certain topological and routing conditions. The first part of this thesis considers jointly optimal routing, scheduling, and network coding strategies to maximize throughput in wireless networks. We introduce a simple network coding strategy and fully characterize the region of arrival rates supported. We propose a centralized dynamic control policy for routing, scheduling, and our network coding strategy, and prove this policy to be throughput optimal subject to our coding constraint. We further propose a distributed control policy based on random access that optimizes for routing, scheduling, and pairwise coding, where pairwise coding captures most of the coding opportunities on random topologies. We prove this second policy to also be throughput optimal subject to the coding constraint. Finally, we reduce the gap between theory and practice by identifying and solving several problems that may occur in system implementations of these policies. Throughput optimal policies typically require every device in the network to make dynamic routing decisions. In the second part of this thesis, we propose an overlay routing architecture such that only a subset of devices (overlay nodes) need to make dynamic routing decisions, and yet maximum throughput can still be achieved. We begin by formulating an optimization problem that searches for the minimum overlay node placement that achieves maximum throughput. We devise an efficient placement algorithm which solves this problem optimally for networks not subject to interference constraints. Then we propose a heuristic control policy for use at overlay nodes, and show by simulation that this policy performs optimally in all studied scenarios.","abstract_html":"Optimal routing and scheduling algorithms have been studied for decades, however several practical issues prevent the adoption of these network control policies on the Internet. This thesis considers two distinct topics in distributed network control: (i) maximizing throughput in wireless networks using network coding, and (ii) deploying controllable nodes in legacy networks. Network coding is a relatively new technique that allows for an increase in throughput under certain topological and routing conditions. The first part of this thesis considers jointly optimal routing, scheduling, and network coding strategies to maximize throughput in wireless networks. We introduce a simple network coding strategy and fully characterize the region of arrival rates supported. We propose a centralized dynamic control policy for routing, scheduling, and our network coding strategy, and prove this policy to be throughput optimal subject to our coding constraint. We further propose a distributed control policy based on random access that optimizes for routing, scheduling, and pairwise coding, where pairwise coding captures most of the coding opportunities on random topologies. We prove this second policy to also be throughput optimal subject to the coding constraint. Finally, we reduce the gap between theory and practice by identifying and solving several problems that may occur in system implementations of these policies. Throughput optimal policies typically require every device in the network to make dynamic routing decisions. In the second part of this thesis, we propose an overlay routing architecture such that only a subset of devices (overlay nodes) need to make dynamic routing decisions, and yet maximum throughput can still be achieved. We begin by formulating an optimization problem that searches for the minimum overlay node placement that achieves maximum throughput. We devise an efficient placement algorithm which solves this problem optimally for networks not subject to interference constraints. Then we propose a heuristic control policy for use at overlay nodes, and show by simulation that this policy performs optimally in all studied scenarios.","abstract_has_math":false,"creators":["Jones, Nathaniel Matthew"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Aeronautics and Astronautics.","school":null,"contributors":[],"advisors":["Eytan Modiano and Brooke Shrader."],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013","date_published":"2013","updated_at":"2026-07-22T22:20:52Z","subjects":["Aeronautics and Astronautics."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/85760","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Eytan Modiano and Brooke Shrader."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Aeronautics and Astronautics."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Aeronautics and Astronautics."]},{"key":"dc:creator","label":"Author","values":["Jones, Nathaniel Matthew"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-19T15:43:29Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-19T15:43:29Z"]},{"key":"dc:date.issued","label":"Date","values":["2013"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Aeronautics and Astronautics."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/85760"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2013.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 135-138)."]},{"key":"dc:description.abstract","label":"Abstract","values":["Optimal routing and scheduling algorithms have been studied for decades, however several practical issues prevent the adoption of these network control policies on the Internet. This thesis considers two distinct topics in distributed network control: (i) maximizing throughput in wireless networks using network coding, and (ii) deploying controllable nodes in legacy networks. Network coding is a relatively new technique that allows for an increase in throughput under certain topological and routing conditions. The first part of this thesis considers jointly optimal routing, scheduling, and network coding strategies to maximize throughput in wireless networks. We introduce a simple network coding strategy and fully characterize the region of arrival rates supported. We propose a centralized dynamic control policy for routing, scheduling, and our network coding strategy, and prove this policy to be throughput optimal subject to our coding constraint. We further propose a distributed control policy based on random access that optimizes for routing, scheduling, and pairwise coding, where pairwise coding captures most of the coding opportunities on random topologies. We prove this second policy to also be throughput optimal subject to the coding constraint. Finally, we reduce the gap between theory and practice by identifying and solving several problems that may occur in system implementations of these policies. Throughput optimal policies typically require every device in the network to make dynamic routing decisions. In the second part of this thesis, we propose an overlay routing architecture such that only a subset of devices (overlay nodes) need to make dynamic routing decisions, and yet maximum throughput can still be achieved. We begin by formulating an optimization problem that searches for the minimum overlay node placement that achieves maximum throughput. We devise an efficient placement algorithm which solves this problem optimally for networks not subject to interference constraints. Then we propose a heuristic control policy for use at overlay nodes, and show by simulation that this policy performs optimally in all studied scenarios."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["Practical algorithms for distributed network control"]}]}],"canonical_facts":{"dc:contributor.advisor":["Eytan Modiano and Brooke Shrader."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Aeronautics and Astronautics."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Aeronautics and Astronautics."],"dc:creator":["Jones, Nathaniel Matthew"],"dc:date.accessioned":["2014-03-19T15:43:29Z"],"dc:date.available":["2014-03-19T15:43:29Z"],"dc:date.issued":["2013"],"dc:description":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2013.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 135-138)."],"dc:description.abstract":["Optimal routing and scheduling algorithms have been studied for decades, however several practical issues prevent the adoption of these network control policies on the Internet. This thesis considers two distinct topics in distributed network control: (i) maximizing throughput in wireless networks using network coding, and (ii) deploying controllable nodes in legacy networks. Network coding is a relatively new technique that allows for an increase in throughput under certain topological and routing conditions. The first part of this thesis considers jointly optimal routing, scheduling, and network coding strategies to maximize throughput in wireless networks. We introduce a simple network coding strategy and fully characterize the region of arrival rates supported. We propose a centralized dynamic control policy for routing, scheduling, and our network coding strategy, and prove this policy to be throughput optimal subject to our coding constraint. We further propose a distributed control policy based on random access that optimizes for routing, scheduling, and pairwise coding, where pairwise coding captures most of the coding opportunities on random topologies. We prove this second policy to also be throughput optimal subject to the coding constraint. Finally, we reduce the gap between theory and practice by identifying and solving several problems that may occur in system implementations of these policies. Throughput optimal policies typically require every device in the network to make dynamic routing decisions. In the second part of this thesis, we propose an overlay routing architecture such that only a subset of devices (overlay nodes) need to make dynamic routing decisions, and yet maximum throughput can still be achieved. We begin by formulating an optimization problem that searches for the minimum overlay node placement that achieves maximum throughput. We devise an efficient placement algorithm which solves this problem optimally for networks not subject to interference constraints. Then we propose a heuristic control policy for use at overlay nodes, and show by simulation that this policy performs optimally in all studied scenarios."],"dc:description.degree":["Ph. D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/85760"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Aeronautics and Astronautics."],"dc:title":["Practical algorithms for distributed network control"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:20:52Z"}