[e2e] Do we need congestion control for unicast traffic with intra-session network coding

[Jon Crowcroft]

A lot of people who looked at Mesh Networks a while back concluded
that building a multihop network with contention MACs at each hop
was a losing proposition - your reasoning below is a major part of
why - probably one of my fave bits of work was Ed Knightly's system
at Rice University, which basically did resource allocation of some
kind or other - there's a sequence of papers of his
http://www.informatik.uni-trier.de/~ley/pers/hd/k/Knightly:Edward_W=.html
[some interesting ones on modifying 802.11 too)

there's a lot of other work in similar space, but just mentioning
one i've read more of...

one way to picture this is that 
contention nets fare badly under load, 
so if you go through several contended hops towards the
center of an urban mesh network, 
the residual goodput after n hops is gonna look like 1/nth
(or worse) of what you'd get  at the edges (for a uniform random
traffic matrix) due to traffic concentration - if your peak
capacity is 1/e, and decreases as you exceed the peak load,
then 1/ne is going to look pretty terrible..

of course, a lot of mesh networks are actually multihop access
networks, and might be a lot more tree structured, so you might do
better (or a lot worse if the tree is upside down:)

In missive <CANZhn5HXzv-u+3QZsPGMMFOs2kYqYmRp0OC=jWguLeWjX4RV3A at mail.gmail.c
om>, shun cai typed:

 >>Hi,
 >>
 >>    I am thinking of the congestion control problem for  MORE-like traffic
 >>in Wireless Mesh networks, and get perplexed by some questions. I do
 >>apprecitate for your kind help.
 >>
 >>   1. MORE-like unicast  traffic uses multipath routing with intra-session
 >>network coding, in which packets are randomly linearly encoded at both the
 >>source and the intermediates nodes.  Specifically, Source s first divides
 >>the original message into batches, each containing K packets of the same
 >>length. It then generates and broadcasts random linearly combined packets
 >>within the current batch. Intermediates buffer the overheard packets, and
 >>then re-encode them before forwarding. Destination t recovers the original
 >>batch by collecting sufficient number of encoded packets, and then sends
 >>ACK to s so as to trigger the next batch until the whole message is
 >>delivered.
 >>
 >>  2. Packets belong to current batch  should buffered at intermediate
 >>nodes, does  the buffer here refer to the MAC queue or a cache at upper
 >>layer (e.g. socket buffer, or  a cache in memory) .
 >>     In my opinion,  the received belong to a current batch will occupy the
 >>MAC queue  for  quite a long time before the whole batch is delivered to
 >>the destionation, which causes  the  MAC queue overflow very easily.  So
 >>the better way is to buffer thesed packets at upper layer, right ?
 >>
 >>3. If the packets are buffered at upper layer,  the MORE traffic is less
 >>likely to be the reason of the congestion at routers, right?  As the coded
 >>packets is  generated and sent to MAC queue  only when the MAC is able to
 >>transmit , at any time, there is at most one packet for each coded traffic
 >>in the MAC queue.
 >>
 >>3. If the conjecture in item 2 is true, do we need any congestion control
 >>for MORE-like traffic?
 >>
 >>
 >>
 >>Regards,
 >>Kara
 >>
 >>--bcaec51d20a41ba85004d7c632c5
 >>Content-Type: text/html; charset=ISO-8859-1
 >>Content-Transfer-Encoding: quoted-printable
 >>
 >>Hi, <br><br>=A0=A0=A0  I am thinking of the congestion control problem for=
 >>=A0 MORE-like traffic in Wireless Mesh networks, and get=20
 >>perplexed by some questions. I do apprecitate for your kind help. <br><br>=
 >>=A0=A0 1. MORE-like unicast=A0 traffic uses multipath routing with intra-se=
 >>ssion network coding, in which packets are randomly linearly encoded at bot=
 >>h the source and the intermediates nodes.=A0 Specifically, Source s first d=
 >>ivides the original message into batches, each containing K packets of the =
 >>same length. It then generates and broadcasts random linearly combined pack=
 >>ets within the current batch. Intermediates buffer the overheard packets, a=
 >>nd then re-encode them before forwarding. Destination t recovers the origin=
 >>al batch by collecting sufficient number of encoded packets, and then sends=
 >> ACK to s so as to trigger the next batch until the whole message is delive=
 >>red.<br>
 >>
 >><br>=A0 2. Packets belong to current batch=A0 should buffered at=20
 >>intermediate nodes, does=A0 the buffer here refer to the MAC queue
 >> or a cache at upper layer (e.g. socket buffer, or=A0 a cache in memory) .
 >> <br>=A0=A0=A0=A0 In my opinion,=A0 the received belong to a current batch =
 >>will=20
 >>occupy the MAC queue=A0 for=A0 quite a long time before the whole batch is=
 >>=20
 >>delivered to the destionation, which causes=A0 the=A0 MAC queue overflow=20
 >>very easily.=A0 So the better way is to buffer thesed packets at upper=20
 >>layer, right ? <br>
 >><br>3. If the packets are buffered at upper layer,=A0 the MORE traffic is=
 >>=20
 >>less likely to be the reason of the congestion at routers, right?=A0 As=20
 >>the coded packets is=A0 generated and sent to MAC queue=A0 only when the MA=
 >>C is able to
 >> transmit , at any time, there is at most one packet for each coded=20
 >>traffic in the MAC queue. <br>
 >><br>3. If the conjecture in item 2 is true, do we need any congestion contr=
 >>ol for MORE-like traffic? <br><br><br><br>Regards,<br>Kara <br><h1><span><b=
 >>r></span></h1>
 >>
 >>--bcaec51d20a41ba85004d7c632c5--

 cheers

   jon