The Abstract MAC Layer
A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an Abstract MAC Layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection o...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Language: | English |
| Published: |
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/45515 |
| _version_ | 1811079051353260032 |
|---|---|
| author | Kuhn, Fabian Newport, Calvin Lynch, Nancy |
| author2 | Nancy Lynch |
| author_facet | Nancy Lynch Kuhn, Fabian Newport, Calvin Lynch, Nancy |
| author_sort | Kuhn, Fabian |
| collection | MIT |
| description | A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an Abstract MAC Layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract \emph{delay functions} applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the Abstract MAC Layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the Abstract MAC Layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast, in which any number of messages arrive at any processes at any times.We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks. |
| first_indexed | 2024-09-23T11:09:16Z |
| id | mit-1721.1/45515 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:09:16Z |
| publishDate | 2009 |
| record_format | dspace |
| spelling | mit-1721.1/455152019-04-11T00:32:19Z The Abstract MAC Layer Kuhn, Fabian Newport, Calvin Lynch, Nancy Nancy Lynch Theory of Computation network modeling mobile networks wireless networks medium-acccess protocols A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an Abstract MAC Layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract \emph{delay functions} applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the Abstract MAC Layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the Abstract MAC Layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast, in which any number of messages arrive at any processes at any times.We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks. 2009-05-11T17:30:04Z 2009-05-11T17:30:04Z 2009-05-11 http://hdl.handle.net/1721.1/45515 en MIT-CSAIL-TR-2009-021 MIT-CSAIL-TR-2009-009 http://hdl.handle.net/1721.1/44620 27 p. application/pdf application/postscript |
| spellingShingle | network modeling mobile networks wireless networks medium-acccess protocols Kuhn, Fabian Newport, Calvin Lynch, Nancy The Abstract MAC Layer |
| title | The Abstract MAC Layer |
| title_full | The Abstract MAC Layer |
| title_fullStr | The Abstract MAC Layer |
| title_full_unstemmed | The Abstract MAC Layer |
| title_short | The Abstract MAC Layer |
| title_sort | abstract mac layer |
| topic | network modeling mobile networks wireless networks medium-acccess protocols |
| url | http://hdl.handle.net/1721.1/45515 |
| work_keys_str_mv | AT kuhnfabian theabstractmaclayer AT newportcalvin theabstractmaclayer AT lynchnancy theabstractmaclayer AT kuhnfabian abstractmaclayer AT newportcalvin abstractmaclayer AT lynchnancy abstractmaclayer |