Beyond Network Equivalence
In earlier work, we described an equivalence result for network capacity. Roughly, that result is as follows. Given a network of noisy, memoryless, point-to-point channels, replace each channel by a noiseless, memoryless bit pipe of the same capacity yields a new network such that any collection of...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/59467 https://orcid.org/0000-0003-4059-407X |
| _version_ | 1826188442923433984 |
|---|---|
| author | Koetter, Ralf Effros, Michelle Medard, Muriel |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Koetter, Ralf Effros, Michelle Medard, Muriel |
| author_sort | Koetter, Ralf |
| collection | MIT |
| description | In earlier work, we described an equivalence result for network capacity. Roughly, that result is as follows. Given a network of noisy, memoryless, point-to-point channels, replace each channel by a noiseless, memoryless bit pipe of the same capacity yields a new network such that any collection of demands can be met on the network of noisy links if and only if the same demands can be met on the network of noiseless links. We here expand on these ideas to provide a framework for studying more general networks, including networks containing memoryless broadcast, multiple access, and interference channels. For each network in this broader class, we design two corresponding networks of noiseless, memoryless point-to-point links. These two networks provide upper and lower bounds in the following sense. Fix an arbitrary collection of demands. If the given demands can be met on the lower bounding network, then they can also be met on the original network. Likewise, if the given demands can be met on the original network, then they can also be met on the upper bounding network. |
| first_indexed | 2024-09-23T07:59:24Z |
| format | Article |
| id | mit-1721.1/59467 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T07:59:24Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/594672022-09-30T01:32:20Z Beyond Network Equivalence Koetter, Ralf Effros, Michelle Medard, Muriel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Medard, Muriel Medard, Muriel In earlier work, we described an equivalence result for network capacity. Roughly, that result is as follows. Given a network of noisy, memoryless, point-to-point channels, replace each channel by a noiseless, memoryless bit pipe of the same capacity yields a new network such that any collection of demands can be met on the network of noisy links if and only if the same demands can be met on the network of noiseless links. We here expand on these ideas to provide a framework for studying more general networks, including networks containing memoryless broadcast, multiple access, and interference channels. For each network in this broader class, we design two corresponding networks of noiseless, memoryless point-to-point links. These two networks provide upper and lower bounds in the following sense. Fix an arbitrary collection of demands. If the given demands can be met on the lower bounding network, then they can also be met on the original network. Likewise, if the given demands can be met on the original network, then they can also be met on the upper bounding network. California Institute of Technology. Lee Center for Advanced Networking United States. Defense Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks Program (Flows project under Grant W911NF-07-10029) 2010-10-22T14:39:17Z 2010-10-22T14:39:17Z 2010-01 2009-09 Article http://purl.org/eprint/type/JournalArticle 978-1-4244-5871-4 978-1-4244-5870-7 INSPEC Accession Number: 11089500 http://hdl.handle.net/1721.1/59467 Koetter, R., M. Effros, and M. Meadard. “Beyond network equivalence.” Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on. 2009. 997-1004. ©2010 Institute of Electrical and Electronics Engineers. https://orcid.org/0000-0003-4059-407X en_US http://dx.doi.org/10.1109/ALLERTON.2009.5394886 47th Annual Allerton Conference on Communication, Control, and Computing, 2009. Allerton 2009 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Koetter, Ralf Effros, Michelle Medard, Muriel Beyond Network Equivalence |
| title | Beyond Network Equivalence |
| title_full | Beyond Network Equivalence |
| title_fullStr | Beyond Network Equivalence |
| title_full_unstemmed | Beyond Network Equivalence |
| title_short | Beyond Network Equivalence |
| title_sort | beyond network equivalence |
| url | http://hdl.handle.net/1721.1/59467 https://orcid.org/0000-0003-4059-407X |
| work_keys_str_mv | AT koetterralf beyondnetworkequivalence AT effrosmichelle beyondnetworkequivalence AT medardmuriel beyondnetworkequivalence |