[e2e] Why Buffering?

Jon Crowcroft Jon.Crowcroft at cl.cam.ac.uk
Sat Jun 20 02:36:30 PDT 2009


at the physical layer
you've got an asyncronous net for some time now
so you've had to store and forward each packet 

in the link layer we do error detection
so you need the whole packet to compute the final cjeck to see if you
discard before sending on

in the IP layer, we do statistical multiplexing and
work conservation (at least by convention anyhow)
so burstiness propagates (slow down in one flow 
speeds up other flows), and we dont do admission control
so unless by some random luck, all senders send in a traffic matrix
perfectly matched to the network provisioning, you will get
packets arriving on multiple interfaces destined for one output interface
which isn't fast enough, even just with 1 packet per RTT (i.e. just a
set of clients sending a connection setup/TCP SYN packet alone to one
server)

so irrespective of end-to-end error correction,
flow and congestion control, you have to have _some_ buffers

the question then is how many more than the absolute minumum
and for that, see yashar ganjali's comprehensive reference list
for the latest thinking ...

of course, we could implement a hop-by-hop error and flow control
and determinisically go for the small buffer case (except there are
other reasons people don't like the hop-by-hop designs)
or we could have rate controlled sources and admission control
and get determinstically small buffers...but that too would lead to a
lot more complexity in the network (a question never satisfactorally
answered is what the relative cost of computational complexity in
switches for either of these two architectures, compared with the cost
of the currently, apparently, oversized buffers in core routers is...
of course, this cost is a moving target as is the end-to-end behaviour
of the net so its a hard problem).

there are lots of larger, longer term buffers in the net too - CDNs
and P2P systems act as whole or partial file buffers to deal with
mismatched timing between senders and recipients ...one might consider
a network architecture where distribution of new content (e.g.
software updates, or new films and music and games) to caches on
a CDN was completely scheduled (some do this a bit to avoid
overloading the net already)

on the other hand, the _resource pooling_ and
law of large numbrs getting you small buffering seems 
to be a smarter way for the internet to evolve
(assuming one's goal is to scale the net up
but get latency (and jitter) to go down to something
a bit more pleasing for interactive (human-human) apps like voip and
games...

In missive <2ff1f08a0906191220x4de051d1w18e5285d3ef6abf5 at mail.gmail.com>, Paddy
 Ganti typed:

 >>--001e680f1b406effbc046cb8699c
 >>Content-Type: text/plain; charset=ISO-8859-1
 >>Content-Transfer-Encoding: 7bit
 >>
 >>For the question of "why do routers buffer", Vadim Antonov provided the
 >>following rationale (http://www.irbs.net/internet/nanog/0204/0298.html)
 >>---------------------------------------------------------------------------------------------------------------------------------------------------------
 >>Well, so far nobody provided a valid explanation for the necessity of
 >>buffering in routers (and any other stochastically multiplexing devices).
 >>
 >>The real reason for having buffers is the fact that information about
 >>congestions takes some time to propagate. (In TCP/IP congestion are
 >>detected by seeing lost packets).
 >>
 >>If buffers are not sufficient to hold packets until TCP speakers see
 >>congestion and slow down, the system becomes unstable. Buffers are,
 >>essentially, inertial elements in the delayed negative-feedback control
 >>loop. Insufficient inertia causes oscillations in such systems, which is
 >>sometimes useful, but in case of networks leads to decreased througoutput
 >>because the wire is utilized fully only at upswings and underutilized on
 >>downswings (collapsed TCP windows aggravate the effect futher).
 >>
 >>Consequently, the holding capacity of buffers should be sufficient to
 >>bring the inertia of the system up to the reaction time of the negative
 >>feedback (this is a simplification, of course). This reaction time is
 >>about one round-trip time for end-to-end packets.
 >>
 >>In real networks, the RTTs differ for different paths, so some
 >>"characteristic" RTT is used. So, to hold packets until TCPs slow down a
 >>router needs cRTT * BW bits of buffer memory (where BW is the speed of the
 >>interface). This rule can be somewhat relaxed if congestion control loop
 >>is engaged proactively before congestion occured (by using Random Early
 >>Detection), but not much.
 >>
 >>Even with properly sized buffers, sessions with longer RTTs suffer from
 >>congestions disproportionately because TCPs on the ends never get enough
 >>time to recover fully (i.e. to bring windows to large enough size to
 >>maintain steady stream of packets), while small-RTT sessions recover
 >>quickly, and, therefore, get bigger share of bandwidth. But I'm
 >>digressing :)
 >>
 >>--vadim
 >>--------------------------------------------------------------------------------------------------------------------------------
 >>
 >>My question to the group is : what other reasons not mentioned here can be
 >>reasons to buffer in a router?
 >>
 >>-Paddy
 >>
 >>--001e680f1b406effbc046cb8699c
 >>Content-Type: text/html; charset=ISO-8859-1
 >>Content-Transfer-Encoding: quoted-printable
 >>
 >><div>For the question of &quot;why do routers buffer&quot;, Vadim Antonov p=
 >>rovided the following rationale (<a href=3D"http://www.irbs.net/internet/na=
 >>nog/0204/0298.html">http://www.irbs.net/internet/nanog/0204/0298.html</a>)<=
 >>/div>
 >><div>----------------------------------------------------------------------=
 >>---------------------------------------------------------------------------=
 >>--------</div><div>Well, so far nobody provided a valid explanation for the=
 >> necessity of <br>
 >>buffering in routers (and any other stochastically multiplexing devices). <=
 >>br><br>The real reason for having buffers is the fact that information abou=
 >>t <br>congestions takes some time to propagate. (In TCP/IP congestion are <=
 >>br>
 >>detected by seeing lost packets). <br><br>If buffers are not sufficient to =
 >>hold packets until TCP speakers see <br>congestion and slow down, the syste=
 >>m becomes unstable. Buffers are, <br>essentially, inertial elements in the =
 >>delayed negative-feedback control <br>
 >>loop. Insufficient inertia causes oscillations in such systems, which is <b=
 >>r>sometimes useful, but in case of networks leads to decreased througoutput=
 >> <br>because the wire is utilized fully only at upswings and underutilized =
 >>on <br>
 >>downswings (collapsed TCP windows aggravate the effect futher). <br><br>Con=
 >>sequently, the holding capacity of buffers should be sufficient to <br>brin=
 >>g the inertia of the system up to the reaction time of the negative <br>
 >>feedback (this is a simplification, of course). This reaction time is <br>a=
 >>bout one round-trip time for end-to-end packets. <br><br>In real networks, =
 >>the RTTs differ for different paths, so some <br>&quot;characteristic&quot;=
 >> RTT is used. So, to hold packets until TCPs slow down a <br>
 >>router needs cRTT * BW bits of buffer memory (where BW is the speed of the =
 >><br>interface). This rule can be somewhat relaxed if congestion control loo=
 >>p <br>is engaged proactively before congestion occured (by using Random Ear=
 >>ly <br>
 >>Detection), but not much. <br><br>Even with properly sized buffers, session=
 >>s with longer RTTs suffer from <br>congestions disproportionately because T=
 >>CPs on the ends never get enough <br>time to recover fully (i.e. to bring w=
 >>indows to large enough size to <br>
 >>maintain steady stream of packets), while small-RTT sessions recover <br>qu=
 >>ickly, and, therefore, get bigger share of bandwidth. But I&#39;m <br>digre=
 >>ssing :) <br><br>--vadim<br>-----------------------------------------------=
 >>---------------------------------------------------------------------------=
 >>------=A0</div>
 >><div><br></div><div>My question to the group is : what other reasons not me=
 >>ntioned here can be reasons to buffer in a router?</div><div><br></div><div=
 >>>-Paddy=A0</div>
 >>
 >>--001e680f1b406effbc046cb8699c--

 cheers

   jon



More information about the end2end-interest mailing list