Network coding for data dissemination: it is not what you know, but what your neighbors don't know
We propose a linear network coding scheme to disseminate a finite number of data packets in arbitrary networks. The setup assumes a packet erasure channel, slotted time, and that nodes cannot transmit and receive information simultaneously. The dissemination process is completed when all terminals c...
| 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/59975 https://orcid.org/0000-0003-4059-407X |
| _version_ | 1826203507385958400 |
|---|---|
| author | Lucani, Daniel Enrique Medard, Muriel Stojanovic, Milica Fitzek, Frank H. P. |
| 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 Lucani, Daniel Enrique Medard, Muriel Stojanovic, Milica Fitzek, Frank H. P. |
| author_sort | Lucani, Daniel Enrique |
| collection | MIT |
| description | We propose a linear network coding scheme to disseminate a finite number of data packets in arbitrary networks. The setup assumes a packet erasure channel, slotted time, and that nodes cannot transmit and receive information simultaneously. The dissemination process is completed when all terminals can decode the original data packets. We also assume a perfect knowledge of the information at each of the nodes, but not necessarily a perfect knowledge of the channel. A centralized controller decides which nodes should transmit, to what set of receiver nodes, and what information should be broadcasted. We show that the problem can be thought of as a scheduling problem, which is hard to solve. Thus, we consider the use of a greedy algorithm that only takes into account the current state of the system to make a decision. The proposed algorithm tries to maximize the impact on the network at each slot, i.e. maximize the number of nodes that will benefit from the coded packet sent by each active transmitter. We show that our scheme is considerably better, in terms of the number of slots to complete transmission, than schemes that choose the node with more information as the transmitter at every time slot. |
| first_indexed | 2024-09-23T12:38:07Z |
| format | Article |
| id | mit-1721.1/59975 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:38:07Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/599752022-10-01T10:11:52Z Network coding for data dissemination: it is not what you know, but what your neighbors don't know Lucani, Daniel Enrique Medard, Muriel Stojanovic, Milica Fitzek, Frank H. P. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Medard, Muriel Lucani, Daniel Enrique Medard, Muriel We propose a linear network coding scheme to disseminate a finite number of data packets in arbitrary networks. The setup assumes a packet erasure channel, slotted time, and that nodes cannot transmit and receive information simultaneously. The dissemination process is completed when all terminals can decode the original data packets. We also assume a perfect knowledge of the information at each of the nodes, but not necessarily a perfect knowledge of the channel. A centralized controller decides which nodes should transmit, to what set of receiver nodes, and what information should be broadcasted. We show that the problem can be thought of as a scheduling problem, which is hard to solve. Thus, we consider the use of a greedy algorithm that only takes into account the current state of the system to make a decision. The proposed algorithm tries to maximize the impact on the network at each slot, i.e. maximize the number of nodes that will benefit from the coded packet sent by each active transmitter. We show that our scheme is considerably better, in terms of the number of slots to complete transmission, than schemes that choose the node with more information as the transmitter at every time slot. National Science Foundation (U.S.) (No. 0831728) National Science Foundation (U.S.) (CNS-0627021) United States. Office of Naval Research (MURI Grant No. NOOOI4-07-1-0738, subcontract # 060786) Bae Systems National Security Solutions Inc. United States. Defense Advanced Research Projects Agency Space and Naval Warfare Systems Center San Diego (U.S.) (Contract No. N66001-06-C-2020 (CBMANET)) Stanford University (subcontract # 1887074037362- C) Denmark. Ministry of Science, Technology and Innovation 2010-11-12T19:23:50Z 2010-11-12T19:23:50Z 2009-10 2009-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-4919-4 INSPEC Accession Number: 10941712 http://hdl.handle.net/1721.1/59975 Lucani, D.E. et al. “Network coding for data dissemination: it is not what you know, but what your neighbors don't know.” Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, 2009. WiOPT 2009. 7th International Symposium on. 2009. 1-8. ©2009 IEEE. https://orcid.org/0000-0003-4059-407X en_US http://dx.doi.org/10.1109/WIOPT.2009.5291585 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, 2009. WiOPT 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 | Lucani, Daniel Enrique Medard, Muriel Stojanovic, Milica Fitzek, Frank H. P. Network coding for data dissemination: it is not what you know, but what your neighbors don't know |
| title | Network coding for data dissemination: it is not what you know, but what your neighbors don't know |
| title_full | Network coding for data dissemination: it is not what you know, but what your neighbors don't know |
| title_fullStr | Network coding for data dissemination: it is not what you know, but what your neighbors don't know |
| title_full_unstemmed | Network coding for data dissemination: it is not what you know, but what your neighbors don't know |
| title_short | Network coding for data dissemination: it is not what you know, but what your neighbors don't know |
| title_sort | network coding for data dissemination it is not what you know but what your neighbors don t know |
| url | http://hdl.handle.net/1721.1/59975 https://orcid.org/0000-0003-4059-407X |
| work_keys_str_mv | AT lucanidanielenrique networkcodingfordatadisseminationitisnotwhatyouknowbutwhatyourneighborsdontknow AT medardmuriel networkcodingfordatadisseminationitisnotwhatyouknowbutwhatyourneighborsdontknow AT stojanovicmilica networkcodingfordatadisseminationitisnotwhatyouknowbutwhatyourneighborsdontknow AT fitzekfrankhp networkcodingfordatadisseminationitisnotwhatyouknowbutwhatyourneighborsdontknow |