;

XORs in The Air: Practical Wireless Network Coding


View PaperPublic Review (by Scott Shenker)

Sachin Katti, MIT
Hariharan Rahul, MIT
Wenjun Hu, University of Cambridge
Dina Katabi, MIT
Muriel Medard, MIT
Jon Crowcroft, University of Cambridge

Abstract
This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic and potentially bursty flows, and practical issues facing the integration of network coding in the current network stack. We evaluate our design on a 20-node wireless network, and discuss the results of the first testbed deployment of wireless network coding. The results show that COPE largely increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.

Comments

  1. Posted by Nick McKeown on Thursday August 31, 2:55pm
    This is really cool - I am really surprised by the results.

    Part of the benefit seems to come from TCP and the implementation of the MAC both being poorly suited to your environment. Can you separate out the benefit of COPE in a general from the inadequacies of these two protocols?
  2. Posted by Sachin Katti on Friday September 1, 7:30am
    Thanks for the comment. I think you meant UDP and the 802.11 MAC above. The pure benefit of COPE independent of the transport layer and the MAC is simply the reduction in the number of transmissions required in the wireless network. The paper shows specific topologies where this gain (which we define as Coding Gain) is 2, i.e we can expect upto 100% throughput improvement. We still do not know an upper bound for arbitrary topologies and traffic demands, but it is atleast 2. As for the experiments themselves, this gain varies depending on the traffic demand.
  3. Posted by Bhaskaran Raman on Saturday September 9, 7:46am
    Comments from the Network Reading Group discussion, IIT-Kanpur, 2006-08-31

    * Overall this was an interesting paper and generated good discussion. Among the questions which arose was: whether more sophisticated coding than XORs can be used in the sort of scenarios described in the paper.

    * An aspect which is not clear from the paper is whether network coding gain is applicable when routing gain is applicable. Similarly, is network coding gain applicable when the number of hops required for routing is reduced by using a few directional links?

    * Related to the above comment is the scenario used in the evaluation. If nodes can hear each other (no hidden nodes), why not send packets directly to one another? It appears as though the bottleneck is first created (by poor routing) and then removed (by network coding). It is not clear what this implies conceptually.

    * Another aspect which is not clear in the evaluation is why the authors used only 6Mbps transmissions. Were there any specific issues with higher data rate transmissions, or with auto-rate?
  4. Posted by Dina Katabi on Tuesday September 12, 5:37am
    It is great to learn that you have read the paper in your reading group at IIT-Kanpur.
    Let me try to answer your questions.

    - Can one use more sophisticated codes than XOR?
    Yes. For example, you can use general linear codes, which most other network coding schemes use. Given their low complexity, we felt that XOR codes are a good starting point. The extra complexity of general linear codes did not seem to add substantial new benefits to COPE.

    - Do you get network coding gain when routing gain is applicable?
    Yes you do. COPE is a forwarding architecture. You can use the routing you like. Please check our Allerton’05 paper to see one possible interaction of COPE with opportunistic routing. This issue however is definitely worth further research to investigate how much extra gain you can get from the interaction of COPE with opportunistic routing.

    - Does COPE work with directional antennas?
    No. The gains come from the broadcast nature of the medium. This does not mean that network coding does not work with directional antennas. Traditional network coding is for point-to-point links.


    - If nodes can hear each other (no hidden nodes), why not send packets directly to one another?
    It seems you are confused about the results. All of our results are with hidden terminals except for TCP over a large dense mesh network. Thus, in general, with or without hidden terminals, COPE reduces the number of transmissions and thus increases throughput. The issue however is that when you have a dense and large testbed like the one we have, you see about 15% to 40% packet loss rate, even after you activate MAC retransmissions. As a result of this high loss rate, TCP does not send much. Thus, the medium becomes underutilized. Thus, you have no coding opportunities. As you can see the problem has nothing to do with coding -- it occurs with and without coding. Namely, TCP interacts badly with current 802.11 MAC implementations, which do not properly hide collision-based losses. To check that this problem is caused by the interaction of TCP and 802.11 MAC, and is independent of coding, we recreated the same environment but without hidden terminals. As you see in the paper, the problem disappears and TCP utilizes the medium properly, in which case you get coding opportunities. Said differently, current wireless mesh networks suffer because we have a MAC that does not properly hide collision-based losses from the transport and we have a congestion control protocol that is very sensitive to high loss rate. This is a research problem that we need to fix whether we use coding or not.

    - Why did you use only 6Mbps bit rate?
    We had to use 802.11a because 802.11b interferes with our operational wireless network and thus it becomes hard to measure the actual gains. Our Allerton paper shows results with 802.11 and various bit rates. Designing an auto-rate alg. for COPE is beyond the scope of the SIGCOMM paper. We are currently looking at this issue.
  5. Posted by Shiv Kalyanaraman on Wednesday September 13, 7:46am
    Hi,

    I was confused by the claim of unbounded gain in the Coding + MAC case. How does this relate to the Gupta/Kumar asymptotic capacity results in wireless networks?

    -Shiv
  6. Posted by Raghu Ganti on Wednesday September 13, 1:47pm
    Hi,
    With respect to the coding procedure algorithm, it seems that you are trying to code the small and large packets immaterial of the packet size. Although, preference is given to the packets that fall under the same category (in terms of size). So, at the end, you are trying to check if all the packets are codable. I do not clearly understand what is the advantage of giving preference to similar size packets?

    Thanks
    -Raghu
  7. Posted by Sachin Katti on Thursday September 14, 2:29am
    Hi Shiv,

    Thanks for your comment. The result for infinite gain is not inconsistent with Gupta and Kumar result. What happens is that the performance with no coding grows worse and worse, while coding achieves the network capacity. Hence the gain itself grows in an unbounded fashion.

    Sachin Katti
  8. Posted by Sachin Katti on Thursday September 14, 2:32am
    Hi Raghu,

    Thanks for the comment. The preference is not for small or large packets, COPE just tries to code packets of the same size together. For ex. if you code a small packet of 200 bytes with a large packet of 1500 bytes, you have just managed to sneak out 200 extra bytes on one transmission. Instead if you coded two packets of 1500 bytes together, then you have a much larger gain since you sneaked out 500 extra bytes. Therefore COPE, gives preference to code packets of the same size together, since that maximizes the gain of coding. Now the Internet packet size distribution is bi-modal, you essentially have small and large packets, hence we group packets in that fashion. So COPE checks first if it can code a packet of the same size, if not it will code packets of different sizes together.

    Sachin Katti
  9. Posted by Sachin Katti on Thursday September 14, 7:46am
    Small correction in the previous post. Instead of "since you sneaked out 500 extra bytes", it should be "since you sneaked out 1500 extra bytes".

    Sachin
  10. Posted by Jon Crowcroft on Friday September 15, 3:06am
    btw, the gupta kumar result is not the end of the story with regard to capacity of many-to-many in wireless nets- there are assumptions in the receiver-interference-limitation analysis they produce which are not always applicable (both tse/grossglauser's result on using mobility, but also using mimo break the assumption, and the limits in practice have not been reached) - however thats orthongal to this work (for now:)
  11. Posted by 2sw2r sss on Tuesday September 22, 3:34am
    http://www.2sw2r.com/vb/t109333.html">الحلقه الاخيره مسلسل وعد مش
    مكتوب
    http://www.2sw2r.com/vb/t109331.html">الحلقه الاخيره مسلسل بوجي
    وطمطم 2
    http://www.2sw2r.com/vb/t109330.html">الحلقه الاخيره مسلسل فؤش
    http://www.2sw2r.com/vb/t109329.html">الحلقه الاخيره مسلسل نوسه
    وبسبوسه
    http://www.2sw2r.com/vb/t109328.html">الحلقه الاخيره مسلسل حرمت يا
    بابا
    http://www.2sw2r.com/vb/t109326.html">الحلقه الاخيره مسلسل الحصرم
    الشامي 3
    http://www.2sw2r.com/vb/t109325.html">الحلقه الاخيره مسلسل البوابة
    الثانية
    http://www.2sw2r.com/vb/t109324.html">الحلقه الاخيره مسلسل احلام
    نبيله
    http://www.2sw2r.com/vb/t109323.html">الحلقه الاخيره مسلسل نساء
    تعرف الندم
    http://www.2sw2r.com/vb/t109314.html">الحلقه الاخيره مسلسل ميدان
    التحرير 6
    http://www.2sw2r.com/vb/t109313.html">الحلقه الاخيره مسلسل عشان
    مليش غيرك
    http://www.2sw2r.com/vb/t109312.html">الحلقه الاخيره مسلسل سفر
    الحجارة
    http://www.2sw2r.com/vb/t109310.html">الحلقه الاخيره مسلسل على قيد
    الحياة
    http://www.2sw2r.com/vb/t109309.html">الحلقه الاخيره مسلسل تحت
    المداس البوليسي
    http://www.2sw2r.com/vb/t109307.html">الحلقه الاخيره مسلسل بهلول
    اعقل المجانين 3
    http://www.2sw2r.com/vb/t109305.html">الحلقه الاخيره مسلسل حقي
    برقبتي
    http://www.2sw2r.com/vb/t109304.html">الحلقه الاخيره مسلسل راجل وست
    ستات
    http://www.2sw2r.com/vb/t109303.html">الحلقه الاخيره مسلسل عصابة
    بابا وماما
    http://www.2sw2r.com/vb/t109302.html">الحلقه الاخيره مسلسل قانون
    المراغى
    http://www.2sw2r.com/vb/t109301.html">الحلقه الاخيره مسلسل قلوب
    صغيره
    http://www.2sw2r.com/vb/t109299.html">الحلقه الاخيره مسلسل هدوء
    نسبي
    http://www.2sw2r.com/vb/t109296.html">الحلقه الاخيره مسلسل فتيات
    صغيرات
    http://www.2sw2r.com/vb/t109293.html">الحلقه الاخيره مسلسل اصوات
    خافته
    http://www.2sw2r.com/vb/t109292.html">الحلقه الاخيره مسلسل
    سوق واجف
    http://www.2sw2r.com/vb/t109290.html">الحلقه الاخيره مسلسل بشرى
    ساره
    http://www.2sw2r.com/vb/t109289.html">الحلقه الاخيره مسلسل اسماعيل
    يس ابو ضحكه جنان
    http://www.2sw2r.com/vb/t109286.html">الحلقه الاخيره مسلسل صبيان
    وبنات
    http://www.2sw2r.com/vb/t109285.html">الحلقه الاخيره مسلسل العياده
    الجزء التانى
    http://www.2sw2r.com/vb/t109284.html">الحلقه الاخيره مسلسل فطوطه
    وتيتا مظبوطه
    http://www.2sw2r.com/vb/t109282.html">الحلقه الاخيره مسلسل قاع
    المدينة
    http://www.2sw2r.com/vb/t109280.html">الحلقه الاخيره مسلسل قاتل بلا
    اجر
    http://www.2sw2r.com/vb/t109279.html">الحلقه الاخيره مسلسل حكايات
    بنعيشها
    http://www.2sw2r.com/vb/t109278.html">الحلقه الاخيره مسلسل قلبي
    معكم
    http://www.2sw2r.com/vb/t109277.html">الحلقه الاخيره مسلسل طريق
    النحل
    http://www.2sw2r.com/vb/t109276.html">الحلقه الاخيره 30 مسلسل
    العقيد شمه
    http://www.2sw2r.com/vb/t109275.html">الحلقه الاخيره مسلسل بوقتادة
    وبو نبيل 3
    http://www.2sw2r.com/vb/t109274.html">الحلقه الاخيره مسلسل ماتخافوش
    http://www.2sw2r.com/vb/t109273.html">الحلقه الاخيره 30 مسلسل أم
    السعف جتكم 2
    http://www.2sw2r.com/vb/t109272.html">الحلقه الاخيره مسلسل صدق وعده
    http://www.2sw2r.com/vb/t109271.html">الحلقه الاخيره مسلسل بسنت
    ودياسطي 3
    http://www.2sw2r.com/vb/t109270.html">الحلقه الاخيره مسلسل الدوامه
    تحميل الحلقه الاخيره
    http://www.2sw2r.com/vb/t109269.html">الحلقه الاخيره مسلسل القبطان
    عزوز
    http://www.2sw2r.com/vb/t109268.html">الحلقه الاخيره مسلسل تاجر
    السعاده
    http://www.2sw2r.com/vb/t109267.html">الحلقه الاخيره مسلسل انا قلبي
    دليلي
    http://www.2sw2r.com/vb/t109266.html">الحلقه الاخيره 30 مسلسل
    الجيران
    http://www.2sw2r.com/vb/t109265.html">الحلقه الاخيره 30 مسلسل
    للاسرار خيوط
    http://www.2sw2r.com/vb/t109264.html">الحلقه الاخيره 30 مسلسل عقاب
    3
    http://www.2sw2r.com/vb/t109263.html">الحلقه الاخيره 30 مسلسل رسائل
    من صدف
    http://www.2sw2r.com/vb/t109262.html">الحلقه الاخيره مسلسل بلقيس
    http://www.2sw2r.com/vb/t109261.html">الحلقه الاخيره 30 مسلسل حنه
    ورنه
    http://www.2sw2r.com/vb/t109258.html">الحلقه الاخيره مسلسل وكاله
    عطيه
    http://www.2sw2r.com/vb/t109257.html">الحلقه الاخيره مسلسل صبايا
    http://www.2sw2r.com/vb/t109256.html">الحلقه الاخيره مسلسل بيت جدي
    2
    http://www.2sw2r.com/vb/t109255.html">الحلقه الاخيره مسلسل شتاء
    ساخن
    http://www.2sw2r.com/vb/t109253.html">الحلقه الاخيره مسلسل ونيس
    الجزء السادس
    http://www.2sw2r.com/vb/t109251.html">الحلقه الاخيره مسلسل افراح
    ابليس
    http://www.2sw2r.com/vb/t109250.html">الحلقه الاخيره مسلسل
    المصراويه 2
    http://www.2sw2r.com/vb/t109249.html">الحلقه الاخيره مسلسل الاشرار
    http://www.2sw2r.com/vb/t109248.html">الحلقه الاخيره مسلسل الرحايا
    http://www.2sw2r.com/vb/t109247.html">الحلقه الاخيره مسلسل تامر و
    شوقية 4
    http://www.2sw2r.com/vb/t109246.html">الحلقه الاخيره 30 مسلسل هديل
    الليل
    http://www.2sw2r.com/vb/t109245.html">الحلقه الاخيره مسلسل هانم بنت
    باشا
    http://www.2sw2r.com/vb/t109244.html">الحلقه الاخيره مسلسل خاص جدا
    http://www.2sw2r.com/vb/t109243.html">الحلقه الاخيره 30 مسلسل
    عماكور
    http://www.2sw2r.com/vb/t109242.html">الحلقه الاخيره مسلسل سيت كوم
    بيت العيله
    http://www.2sw2r.com/vb/t109241.html">الحلقه الاخيره مسلسل ليالي
    http://www.2sw2r.com/vb/t109240.html">الحلقه الاخيره برنامج خواطر 5
    http://www.2sw2r.com/vb/t109239.html">الحلقه الاخيره مسلسل عبودة
    ماركة
    http://www.2sw2r.com/vb/t109238.html">الحلقه الاخيره مسلسل الباطنيه
    http://www.2sw2r.com/vb/t109237.html">الحلقه الاخيره من برنامج عيني
    عينك 2
    http://www.2sw2r.com/vb/t109235.html">الحلقه الاخيره 30 مسلسل غشمشم
    4
    http://www.2sw2r.com/vb/t109234.html">الحلقه الاخيره 30 مسلسل موزه
    ولوزه
    http://www.2sw2r.com/vb/t109232.html">الحلقه الاخيره 30 هوامير
    الصحراء
    http://www.2sw2r.com/vb/t109231.html">الحلقه الاخيره مسلسل حرب
    الجواسيس
    http://www.2sw2r.com/vb/t109230.html">الحلقه الاخيره 30 مسلسل دمعه
    يتيم
    http://www.2sw2r.com/vb/t109229.html">الحلقه الاخيره مسلسل 30 عجيب
    غريب
    http://www.2sw2r.com/vb/t109228.html">الحلقه الاخيره برنامج مسلسلات
    حليمه
    http://www.2sw2r.com/vb/t109227.html">الحلقه الاخيره مسلسل كريمه
    كريمه
    http://www.2sw2r.com/vb/t109226.html">الحلقه الاخيره من برنامج
    حيلهم بينهم كمان وكمان
    http://www.2sw2r.com/vb/t109225.html">الحلقه الاخيره برنامج
    الاسنصيد
    http://www.2sw2r.com/vb/t109224.html">الحلقه الاخيره برنامج شطار
    اكاديمي
    http://www.2sw2r.com/vb/t109223.html">الحلقه الاخيره 30 مسلسل ام
    حاله
    http://www.2sw2r.com/vb/t109222.html">الحلقه الاخيره 30 برنامج طول
    بالك
    http://www.2sw2r.com/vb/t109221.html">الحلقه الاخيره مسلسل ادهم
    الشرقاوي
    http://www.2sw2r.com/vb/t109220.html">الحلقه الاخيره من برنامج دي
    تيوب
    http://www.2sw2r.com/vb/t109219.html">الحلقه الاخيره 30 مسلسل عوانس
    ستي
    http://www.2sw2r.com/vb/t109217.html">الحلقه الاخيره مسلسل رجال
    الحسم
    http://www.2sw2r.com/vb/t109216.html">الحلقه الاخيره 30 مسلسل سدره
    البيت
    http://www.2sw2r.com/vb/t109215.html">الحلقه الاخيره من برنامج شوجي
    http://www.2sw2r.com/vb/t109214.html">الحلقه الاخيره مسلسل حدف
    البحر
    http://www.2sw2r.com/vb/t109213.html">مشاهده الحلقه الاخيره 30
    مسلسل شر النفوس 2
    http://www.2sw2r.com/vb/t109212.html">شر النفوس 2 الجزء الثاني
    الحلقه الاخيره
    http://www.2sw2r.com/vb/t109211.html">الحلقه الاخيره 30 مسلسل شر
    النفوس الجزء الثاني
    http://www.2sw2r.com/vb/t109210.html">الحلقه الاخيره 30 مسلسل
    الهدامه
    http://www.2sw2r.com/vb/t109209.html">الحلقه الاخيره 30 مسلسل فنجان
    الدم
    http://www.2sw2r.com/vb/t109208.html">مشاهده الحلقه الاخيره 30 بيني
    وبينك 3
    http://www.2sw2r.com/vb/t109207.html">بيني وبينك 3 الحلقه الاخيره
    شي ماشفتوه
    http://www.2sw2r.com/vb/t109205.html">الحلقه الاخيره 30 مسلسل بيني
    وبينك 3
    http://www.2sw2r.com/vb/t109204.html">الحلقه الاخيره برنامج ولا
    كلمه 3
    http://www.2sw2r.com/vb/t109203.html">الحلقه الاخيره مسلسل كلام
    نسوان
    http://www.2sw2r.com/vb/t109201.html">الحلقه الاخيره مسلسل قبائل
    شرق
    http://www.2sw2r.com/vb/t109199.html">الحلقه الاخيره 30 مسلسل امراه
    واخرى
    http://www.2sw2r.com/vb/t109198.html">مشاهده الحلقه الاخيره 30
    مسلسل قلوب للايجار
    http://www.2sw2r.com/vb/t109197.html">قلوب للايجار الحلقه الاخيره
    30
    http://www.2sw2r.com/vb/t109196.html">الحلقه الاخيره 30 مسلسل قلوب
    للايجار
    http://www.2sw2r.com/vb/t109195.html">الحلقه الاخيره 30 مسلسل اخر
    صفقه حب
    http://www.2sw2r.com/vb/t109194.html">الحلقه الاخيره 30 مسلسل الى
    متى
    http://www.2sw2r.com/vb/t109193.html">الحلقه الاخيره 30 مسلسل عمر
    الشقا
    http://www.2sw2r.com/vb/t109191.html">الحلقه الاخيره مسلسل زمن
    العار
    http://www.2sw2r.com/vb/t109190.html">الحلقه الاخيره مسلسل ابن
    الارندلى
    http://www.2sw2r.com/vb/t109189.html">الحلقه الاخيره مسلسل الادهم
    http://www.2sw2r.com/vb/t109188.html">الحلقه الاخيره 30 مسلسل وعاد
    الماضي
    http://www.2sw2r.com/vb/t109187.html">مشاهده الحلقه الاخيره 30 باب
    الحاره 4
    http://www.2sw2r.com/vb/t109186.html">باب الحاره 4 الحلقه الاخيره
    http://www.2sw2r.com/vb/t109185.html">الحلقه الاخيره 30 مسلسل باب
    الحاره الجزء الرابع
    http://www.2sw2r.com/vb/t109182.html">الحلقه الاخيره 30 مسلسل الحب
    الكبير
    http://www.2sw2r.com/vb/t109180.html">الحلقه الاخيره 30 مسلسل سوالف
    طفاش
    http://www.2sw2r.com/vb/t109179.html">مشاهده الحلقه الاخيره 30
    مسلسل ام البنات
    http://www.2sw2r.com/vb/t109177.html">ام البنات الحلقه الاخيره
    http://www.2sw2r.com/vb/t109175.html">الحلقه الاخيره 30 مسلسل ام
    البنات
    http://www.2sw2r.com/vb/t96590.html">الحلقه الاخيره مسلسل ام البنات
    http://www.2sw2r.com/vb/t26902.html">مسلسل عاصي -
    http://www.2sw2r.com/vb/t26902.html">صور مسلسل عاصي -
    http://www.2sw2r.com/vb/t26902.html">حلقات مسلسل عاصي -
    http://www.2sw2r.com/vb/t109923.html">صور ابطال مسلسل عاصي -
    http://www.2sw2r.com/vb/t26902.html">حلقات عاصي -
    http://www.2sw2r.com/vb/t109969.html">الحلقه 8 مسلسل عاصي -
    http://www.2sw2r.com/vb/t109961.html">الحلقه 7 مسلسل عاصي -
    http://www.2sw2r.com/vb/t109967.html">الحلقه 6 مسلسل عاصي -
    http://www.2sw2r.com/vb/t109965.html">الحلقه 4 مسلسل عاصي -
    http://www.2sw2r.com/vb/t109963.html">الحلقه 3 مسلسل عاصي -
    http://www.2sw2r.com/vb/t109960.html">الحلقه 2 مسلسل عاصي -
    http://www.2sw2r.com/vb/t109962.html">الحلقه 1 مسلسل عاصي -
    http://www.2sw2r.com/vb/t109903.html">اغاني مسلسل عاصي -
    http://www.2sw2r.com/vb/t106455.html">قصه مسلسل عاصي -

Login to post a comment