[e2e] RES: Why Buffering?
Jon Crowcroft
Jon.Crowcroft at cl.cam.ac.uk
Tue Jun 23 04:15:02 PDT 2009
the naive argument for bw*delay buffer
was that AIMD involves rate halving
so by corollary, just before the rate halved
it was twice the bottleneck's capacity
operating point, and to avoid
wasting the bw*delay (-1 lost) of packets just sent
you'd like to have them buffered.
if the bottleneck is usually at the edge
(e.g. the router in the home or just after the dslam
and the "core" (some fictional middle of the internet)
never sees packet loss,
then you are right...
if there's lots of flows
and the individual flows are all even reasonably
unsynchronised in their AIMD phase
(very good chance due to random local perturbation)
(law of large number argument says..)
then you are right (well, nick mckeown's right:)
if you use some smart queue management and ECN
then you're right
if most flows stop before reaching their operating point
your right
(well actually, there's a way to be wrong
in a quite ghastly way if you have many sy cnhronised flows
in "slow start", heading thru the same bottleneck...
but it ought to be quite a rare event - like
black swans and mrket meltdowns:-)
In missive <!&!AAAAAAAAAAAYAAAAAAAAAKzwMewNc4dBs78TsHJg5glClAAAEAAAALI5AvAXD7dEgGoj4UaQOacBAAAAAA==@rnp.br>, "Alexandre
Grojsgold" typed:
>>I=92m sorry, but I am afraid I have to strongly disagree with =
>>Antonov=B4s view
>>on buffer length needs, and perhaps with most people=B4s opinion on this =
>>list.
>>
>>=20
>>
>>About buffer sizes on routers, I suggest you look for Nick McKeown=92s
>>presentation =93Buffers: How we fell in love with them, and why we need =
>>a
>>divorce=94. It makes sense to me.
>>
>>=20
>>
>>IMHO, most of you seem to make confusion between buffers needed at the
>>*ends* of a TCP connection, and buffers needed middle way. At the ends,
>>where congestion is detected, and TCP anti-congestion mechanisms act, =
>>large
>>buffers are necessary when you want to obtain a high bit rate over a =
>>long
>>round trip delay path.
>>
>>=20
>>
>>This has nothing to do with buffers within routers. A lot of flows flow
>>through a backbone router. Some of them have large BW, same have very =
>>little
>>BW. Some of them have very very far endpoints, some of them come from =
>>the
>>host in the other side of the town. The router has no clue on the =
>>BW.delay
>>product of each flow, and cannot buffer accordingly =96 supposing this =
>>could
>>help someway.
>>
>>=20
>>
>>In his text, Antonov says that buffers add =93inertia=94. This does not =
>>seem
>>true. In physical systems, inertia is added by mass. Buffers are more =
>>like
>>springs. If you think of a car suspension, a buffer too long is like a
>>suspension too soft. Maybe good to isolate from road irregularities, but
>>quite unstable.
>>
>>=20
>>
>>As buffers grow large, the information about congestion takes longer =
>>time to
>>come back to a TCP sender, what makes the system less stable (not more
>>stable), and more prone to oscillatory behavior.
>>
>>=20
>>
>>My vision of what a router does: what a router sees are output =
>>interfaces,
>>with a given bandwidth and some characteristics. Under light traffic, =
>>the
>>output queue will be almost always empty, at most with a sending packet =
>>and
>>another waiting. If the integration of multiple flows traversing that =
>>output
>>interface gets close to the maximum bandwidth of the interface, and the
>>system is close to a stable situation, some probability distribution
>>function must exist that can describe the queue length. Without any
>>mathematical proof, I dare to say that the average queue length in this
>>condition should be of a few (less than 10?) packets. Some fluctuations =
>>can
>>occur due to slight changes in traffic load, and since that does not =
>>mean
>>=93congestion=94, there must be enough buffer to keep these few packets =
>>in the
>>game. But when the number of packets waiting to be transmitted rises =
>>above a
>>certain limit (20? 40?) packets, this is seen by the router as sign =
>>that
>>there are more flows trying to cross that output interface than it can
>>accommodate. So =85 time to start dropping some packets, and make a few
>>transmitting TCP guys to slow down. The buffer must have the proper =
>>size
>>to drop packets when there is a probable congestion, and do not drop =
>>packets
>>under normal fluctuations. Where does delay considerations get here? =
>>They
>>don=92t.
>>
>>=20
>>
>>n Alexandre.
>>
>>=20
>>
>>=20
>>
>>=20
>>
>>=20
>>
>>De: end2end-interest-bounces at postel.org
>>[mailto:end2end-interest-bounces at postel.org] Em nome de Paddy Ganti
>>Enviada em: sexta-feira, 19 de junho de 2009 16:20
>>Para: end2end-interest at postel.org
>>Assunto: [e2e] Why Buffering?
>>
>>=20
>>
>>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=20
>>buffering in routers (and any other stochastically multiplexing =
>>devices).=20
>>
>>The real reason for having buffers is the fact that information about=20
>>congestions takes some time to propagate. (In TCP/IP congestion are=20
>>detected by seeing lost packets).=20
>>
>>If buffers are not sufficient to hold packets until TCP speakers see=20
>>congestion and slow down, the system becomes unstable. Buffers are,=20
>>essentially, inertial elements in the delayed negative-feedback control=20
>>loop. Insufficient inertia causes oscillations in such systems, which is =
>>
>>sometimes useful, but in case of networks leads to decreased =
>>througoutput=20
>>because the wire is utilized fully only at upswings and underutilized on =
>>
>>downswings (collapsed TCP windows aggravate the effect futher).=20
>>
>>Consequently, the holding capacity of buffers should be sufficient to=20
>>bring the inertia of the system up to the reaction time of the negative=20
>>feedback (this is a simplification, of course). This reaction time is=20
>>about one round-trip time for end-to-end packets.=20
>>
>>In real networks, the RTTs differ for different paths, so some=20
>>"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=20
>>interface). This rule can be somewhat relaxed if congestion control loop =
>>
>>is engaged proactively before congestion occured (by using Random Early=20
>>Detection), but not much.=20
>>
>>Even with properly sized buffers, sessions with longer RTTs suffer from=20
>>congestions disproportionately because TCPs on the ends never get enough =
>>
>>time to recover fully (i.e. to bring windows to large enough size to=20
>>maintain steady stream of packets), while small-RTT sessions recover=20
>>quickly, and, therefore, get bigger share of bandwidth. But I'm=20
>>digressing :)=20
>>
>>--vadim
>>-------------------------------------------------------------------------=
>>---
>>----------------------------------------------------=20
>>
>>=20
>>
>>My question to the group is : what other reasons not mentioned here can =
>>be
>>reasons to buffer in a router?
>>
>>=20
>>
>>-Paddy=20
>>
>>
>>------=_NextPart_000_0050_01C9F392.7FF50A70
>>Content-Type: text/html;
>> charset="iso-8859-1"
>>Content-Transfer-Encoding: quoted-printable
>>
>><html xmlns:v=3D"urn:schemas-microsoft-com:vml" =
>>xmlns:o=3D"urn:schemas-microsoft-com:office:office" =
>>xmlns:w=3D"urn:schemas-microsoft-com:office:word" =
>>xmlns:x=3D"urn:schemas-microsoft-com:office:excel" =
>>xmlns:m=3D"http://schemas.microsoft.com/office/2004/12/omml" =
>>xmlns=3D"http://www.w3.org/TR/REC-html40">
>>
>><head>
>><meta http-equiv=3DContent-Type content=3D"text/html; =
>>charset=3Diso-8859-1">
>><meta name=3DGenerator content=3D"Microsoft Word 12 (filtered medium)">
>><style>
>><!--
>> /* Font Definitions */
>> @font-face
>> {font-family:Wingdings;
>> panose-1:5 0 0 0 0 0 0 0 0 0;}
>>@font-face
>> {font-family:"Cambria Math";
>> panose-1:2 4 5 3 5 4 6 3 2 4;}
>>@font-face
>> {font-family:Calibri;
>> panose-1:2 15 5 2 2 2 4 3 2 4;}
>>@font-face
>> {font-family:Tahoma;
>> panose-1:2 11 6 4 3 5 4 4 2 4;}
>> /* Style Definitions */
>> p.MsoNormal, li.MsoNormal, div.MsoNormal
>> {margin:0cm;
>> margin-bottom:.0001pt;
>> font-size:12.0pt;
>> font-family:"Times New Roman","serif";}
>>a:link, span.MsoHyperlink
>> {mso-style-priority:99;
>> color:blue;
>> text-decoration:underline;}
>>a:visited, span.MsoHyperlinkFollowed
>> {mso-style-priority:99;
>> color:purple;
>> text-decoration:underline;}
>>p
>> {mso-style-priority:99;
>> mso-margin-top-alt:auto;
>> margin-right:0cm;
>> mso-margin-bottom-alt:auto;
>> margin-left:0cm;
>> font-size:12.0pt;
>> font-family:"Times New Roman","serif";}
>>p.MsoAcetate, li.MsoAcetate, div.MsoAcetate
>> {mso-style-priority:99;
>> mso-style-link:"Texto de bal=E3o Char";
>> margin:0cm;
>> margin-bottom:.0001pt;
>> font-size:8.0pt;
>> font-family:"Tahoma","sans-serif";}
>>p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
>> {mso-style-priority:34;
>> margin-top:0cm;
>> margin-right:0cm;
>> margin-bottom:0cm;
>> margin-left:36.0pt;
>> margin-bottom:.0001pt;
>> font-size:12.0pt;
>> font-family:"Times New Roman","serif";}
>>span.EstiloDeEmail17
>> {mso-style-type:personal-reply;
>> font-family:"Calibri","sans-serif";
>> color:#1F497D;}
>>span.TextodebaloChar
>> {mso-style-name:"Texto de bal=E3o Char";
>> mso-style-priority:99;
>> mso-style-link:"Texto de bal=E3o";
>> font-family:"Tahoma","sans-serif";}
>>.MsoChpDefault
>> {mso-style-type:export-only;}
>>@page Section1
>> {size:612.0pt 792.0pt;
>> margin:70.85pt 3.0cm 70.85pt 3.0cm;}
>>div.Section1
>> {page:Section1;}
>> /* List Definitions */
>> @list l0
>> {mso-list-id:56704280;
>> mso-list-type:hybrid;
>> mso-list-template-ids:-1148278648 -1346070502 68550659 68550661 =
>>68550657 68550659 68550661 68550657 68550659 68550661;}
>>@list l0:level1
>> {mso-level-start-at:0;
>> mso-level-number-format:bullet;
>> mso-level-text:\F06E;
>> mso-level-tab-stop:none;
>> mso-level-number-position:left;
>> text-indent:-18.0pt;
>> font-family:Wingdings;
>> mso-fareast-font-family:"Times New Roman";
>> mso-bidi-font-family:"Times New Roman";}
>>ol
>> {margin-bottom:0cm;}
>>ul
>> {margin-bottom:0cm;}
>>-->
>></style>
>><!--[if gte mso 9]><xml>
>> <o:shapedefaults v:ext=3D"edit" spidmax=3D"1026" />
>></xml><![endif]--><!--[if gte mso 9]><xml>
>> <o:shapelayout v:ext=3D"edit">
>> <o:idmap v:ext=3D"edit" data=3D"1" />
>> </o:shapelayout></xml><![endif]-->
>></head>
>>
>><body lang=3DPT-BR link=3Dblue vlink=3Dpurple>
>>
>><div class=3DSection1>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>Paddy,<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>I’m sorry, but I am afraid I have to strongly =
>>disagree
>>with Antonov=B4s view on buffer length needs, and perhaps with most =
>>people=B4s
>>opinion on this list.<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>About buffer sizes on routers, I suggest you look for =
>>Nick
>>McKeown’s presentation “<b>Buffers:</b> How we fell in love =
>>with
>>them, and why we need a divorce”. It makes sense to =
>>me.<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>IMHO, most of you seem to make confusion between buffers =
>>needed
>>at the *ends* of a TCP connection, and buffers needed middle way.=A0 At =
>>the ends,
>>where congestion is detected, and TCP anti-congestion mechanisms act, =
>>large
>>buffers are necessary when you want to obtain a high bit rate over a =
>>long round
>>trip delay path.<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>This has nothing to do with buffers <b>within</b> =
>>routers. A lot
>>of flows flow through a backbone router. Some of them have large BW, =
>>same have
>>very little BW. Some of them have very very far endpoints, some of them =
>>come
>>from the host in the other side of the town. The router has no clue on =
>>the
>>BW.delay product of each flow, and cannot buffer accordingly – =
>>supposing
>>this could help someway.<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>In his text, Antonov says that buffers add
>>“inertia”. This does not seem true. In physical systems, =
>>inertia is
>>added by mass. Buffers are more like springs. If you think of a car =
>>suspension,
>>a buffer too long is like a suspension too soft. Maybe good to isolate =
>>from
>>road irregularities, but quite unstable.<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>As buffers grow large, the information about congestion =
>>takes
>>longer time to come back to a TCP sender, what makes the system less =
>>stable
>>(not more stable), and more prone to oscillatory =
>>behavior.<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>My vision of what a router does: what a router sees are =
>>output
>>interfaces, with a=A0 given bandwidth and some characteristics. Under =
>>light
>>traffic, the output queue will be almost always empty, at most with a =
>>sending
>>packet and another waiting. If the integration of multiple flows =
>>traversing
>>that output interface gets close to the maximum bandwidth of the =
>>interface, and
>>the system is=A0 close to a stable situation, some probability =
>>distribution
>>function must exist that can describe the queue length. Without any
>>mathematical proof, I dare to say that the average queue length in this
>>condition should be of a few (less than 10?) packets. Some fluctuations =
>>can
>>occur due to slight changes in traffic load, and since that does not =
>>mean
>>“congestion”, there must be enough buffer to keep these few =
>>packets
>>in the game. But when the number of packets waiting to be transmitted =
>>rises
>>above a certain limit (20? 40?) packets, this is seen=A0 by the router =
>>as sign
>>that there are more flows trying to cross that output interface than it =
>>can
>>accommodate. So … time to start dropping some packets, and make a =
>>few
>>transmitting TCP guys to slow down. The buffer must=A0 have the =
>>proper=A0 size to drop
>>packets when there is a probable congestion, and do not drop packets =
>>under
>>normal fluctuations. Where does delay considerations get here? They
>>don’t.<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoListParagraph style=3D'text-indent:-18.0pt;mso-list:l0 =
>>level1 lfo1'><![if !supportLists]><span
>>lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:Wingdings;color:#1F497D'><span
>>style=3D'mso-list:Ignore'>n<span style=3D'font:7.0pt "Times New =
>>Roman"'> </span></span></span><![endif]><span
>>lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>Alexandre.<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'>=A0<o:p></o:p></span></p>
>>
>><p class=3DMsoNormal><span lang=3DEN-US =
>>style=3D'font-size:11.0pt;font-family:"Calibri","sans-serif";
>>color:#1F497D'><o:p> </o:p></span></p>
>>
>><div style=3D'border:none;border-left:solid blue 1.5pt;padding:0cm 0cm =
>>0cm 4.0pt'>
>>
>><div>
>>
>><div style=3D'border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt =
>>0cm 0cm 0cm'>
>>
>><p class=3DMsoNormal><b><span =
>>style=3D'font-size:10.0pt;font-family:"Tahoma","sans-serif"'>De:</span></=
>>b><span
>>style=3D'font-size:10.0pt;font-family:"Tahoma","sans-serif"'> =
>>end2end-interest-bounces at postel.org
>>[mailto:end2end-interest-bounces at postel.org] <b>Em nome de </b>Paddy =
>>Ganti<br>
>><b>Enviada em:</b> sexta-feira, 19 de junho de 2009 16:20<br>
>><b>Para:</b> end2end-interest at postel.org<br>
>><b>Assunto:</b> [e2e] Why Buffering?<o:p></o:p></span></p>
>>
>></div>
>>
>></div>
>>
>><p class=3DMsoNormal><o:p> </o:p></p>
>>
>><div>
>>
>><p class=3DMsoNormal>For the question of "why do routers =
>>buffer", Vadim
>>Antonov provided the following rationale (<a
>>href=3D"http://www.irbs.net/internet/nanog/0204/0298.html">http://www.irb=
>>s.net/internet/nanog/0204/0298.html</a>)<o:p></o:p></p>
>>
>></div>
>>
>><div>
>>
>><p =
>>class=3DMsoNormal>-------------------------------------------------------=
>>-------------------------------------------------------------------------=
>>-------------------------<o:p></o:p></p>
>>
>></div>
>>
>><div>
>>
>><p class=3DMsoNormal>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 about =
>><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 system 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 =
>><br>
>>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>
>>Consequently, the holding capacity of buffers should be sufficient to =
>><br>
>>bring 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>
>>about one round-trip time for end-to-end packets. <br>
>><br>
>>In real networks, the RTTs differ for different paths, so some <br>
>>"characteristic" 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 loop =
>><br>
>>is engaged proactively before congestion occured (by using Random Early =
>><br>
>>Detection), but not much. <br>
>><br>
>>Even with properly sized buffers, sessions with longer RTTs suffer from =
>><br>
>>congestions disproportionately because TCPs on the ends never get enough =
>><br>
>>time to recover fully (i.e. to bring windows to large enough size to =
>><br>
>>maintain steady stream of packets), while small-RTT sessions recover =
>><br>
>>quickly, and, therefore, get bigger share of bandwidth. But I'm <br>
>>digressing :) <br>
>><br>
>>--vadim<br>
>>-------------------------------------------------------------------------=
>>------------------------------------------------------- <o:p></o:p><=
>>/p>
>>
>></div>
>>
>><div>
>>
>><p class=3DMsoNormal><o:p> </o:p></p>
>>
>></div>
>>
>><div>
>>
>><p class=3DMsoNormal>My question to the group is : what other reasons =
>>not
>>mentioned here can be reasons to buffer in a router?<o:p></o:p></p>
>>
>></div>
>>
>><div>
>>
>><p class=3DMsoNormal><o:p> </o:p></p>
>>
>></div>
>>
>><div>
>>
>><p class=3DMsoNormal>-Paddy <o:p></o:p></p>
>>
>></div>
>>
>></div>
>>
>></div>
>>
>></body>
>>
>></html>
>>
>>------=_NextPart_000_0050_01C9F392.7FF50A70--
>>
>>
cheers
jon
More information about the end2end-interest
mailing list