Efficient distributed medium access algorithm
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2010.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/64604 |
| _version_ | 1826197292306137088 |
|---|---|
| author | Shin, Jinwoo |
| author2 | Devavrat Shah. |
| author_facet | Devavrat Shah. Shin, Jinwoo |
| author_sort | Shin, Jinwoo |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2010. |
| first_indexed | 2024-09-23T10:45:48Z |
| format | Thesis |
| id | mit-1721.1/64604 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:45:48Z |
| publishDate | 2011 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/646042019-04-10T18:23:06Z Efficient distributed medium access algorithm Shin, Jinwoo Devavrat Shah. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2010. Cataloged from PDF version of thesis. Includes bibliographical references (p. 153-157). Allocation or scheduling of resources among various entities contending for their access is one of the fundamental problem in engineering and operations research. To design a large, scalable networked systems, scheduling algorithms are required to be computationally very simple and distributed (or message passing). In this thesis, we present a novel method to design performance optimal, simple and distributed algorithms for a variety of scheduling problems. The algorithmic method is explained in detail in the context of wireless medium access. However, it naturally extends to essentially any instance of stochastic processing network (cf. [23]). In a wireless network, multiple transmitters are attempting to utilize common wireless medium for the purpose of communication. Due to nature of wireless communication, two simultaneous transmissions may interfere with each other. To avoid such destructive interference, a scheduling algorithm, known as medium access control (MAC), is required. The question of (design efficient MAC has been extensively studied starting with the ALOHA network [1]. Although certain types of MAC algorithms are used in practice (e.g. those confirming to IEEE 802.11)., a provably performance efficient algorithm has remained mystery for more than four decades. As an important contribution of this thesis, we resolve this challenge by presenting a novel, randomized medium access control (MAC) that is provably performance optimal. Like the solutions utilized in practice, it is a "randomized" or "back-off-like" algorithm and uses "carrier sense" information. This is the first instance of MAC that is proven to be performance optimal for general interference topology. Our solution blends the classical Metropolis-Hastings sampling mechanism with insights obtained from analysis of time-varying queueing dynamics. Methodically, our theoretical framework is applicable to design of efficient distributed scheduling algorithms for a wide class of combinatorial resource allocation problem in stochastic processing networks, including scheduling in input-queued switches and optical core network. by Jinwoo Shin. Ph.D. 2011-06-20T15:58:58Z 2011-06-20T15:58:58Z 2010 2010 Thesis http://hdl.handle.net/1721.1/64604 727146241 eng 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. http://dspace.mit.edu/handle/1721.1/7582 157 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Shin, Jinwoo Efficient distributed medium access algorithm |
| title | Efficient distributed medium access algorithm |
| title_full | Efficient distributed medium access algorithm |
| title_fullStr | Efficient distributed medium access algorithm |
| title_full_unstemmed | Efficient distributed medium access algorithm |
| title_short | Efficient distributed medium access algorithm |
| title_sort | efficient distributed medium access algorithm |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/64604 |
| work_keys_str_mv | AT shinjinwoo efficientdistributedmediumaccessalgorithm |