[e2e] Why Buffering?

Detlef Bosau detlef.bosau at web.de
Sun Jun 21 12:23:11 PDT 2009


Lachlan Andrew wrote:
> 2009/6/21 Detlef Bosau <detlef.bosau at web.de>:
>   
>> David P. Reed wrote:
>>     
>>> Dave - This is variously known as Little's Theorem or Little's Lemma.
>>>       
>> Little's Theorem can be easily applied in wired networks where a link's
>> capacity is easily expressed as "latency throghput product".
>>
>> The situation becomes a bit more complicated in wireless networks,
>> particularly WWAN, where the preconditions for Little's Theorem may not
>> hold, particularly the service time may not be stationary or stable.
>>     
>
> Little's law (N = T lambda) holds in basically all scenarios.  It
> doesn't rely on stationarity.  It refers to long-run averages, which
> wash out all of the fluctuations.  

I'm not quite sure here.

At least, to my knowledge the law relies on "rates".
http://en.wikipedia.org/wiki/Little%27s_law

So, the question is the meaning of the term "rate" here.

Now, let's have a look at the original paper.
http://www.doc.ic.ac.uk/~uh/for-paul/A%20PROOF%20FOR%20THE%20QUEUING%20FORMULA%20L=lW.%207689045.pdf


I may have a closer look to the paper in the next days, but in Little's 
paper it is said that the formula holds in
"steady state processes".



> If the service time were "not
> stable" in the sense of tending to infinity as time progresses, then
> it would not apply simply (we'd have infinite T, and either infinite N
> or zero lambda), but that is not the case in WWANs.
>
>   

Like on any lossy link, in WWAN we have to choices.

Either we guarantee error free delivery along a link with errors, 
achieved by data retransmission if necessary, - in that case the 
delivery time can grow beyond all limits.
Or we impose an upper limit on the delivery time, as we actually do in 
order to prevent unlimited head of line blocking, and have a residual 
possibility for the packet to see corruption.

In terms of queuing theory, the packet is not being served in that case. 
I'm a bit out of practice in queuing theory - but wouldn't this be 
modeled by an infinite service time for that packet with the inevitable 
consequence that an average vale for the service time, or an expectation 
for the service time and hence an average number of customers in the 
system wouldn't even exist?

> If your point is that Little's law doesn't tell us anything about
> short-term behaviour, then that is certainly true.  

Particularly in WWAN, one could hardly be interested in the long term 
behavior. (Argh.... my Thunderbird uses an American spell checker.... ;-))

Consider a user suffering from multipath fading who moves just a few 
centimeters from an interference maximum to an interference minimum. I 
don't think he is interested in the fact that the "over the day average" 
of his throughput is "high".

Actually, I've seen users who used mobiles for IP comunication more than 
I ever did, and sometimes performed some kind of "Aerobic" to achieve 
satisfactory throughput while reading or sending mails or the like.
> The only
> difference between WWANs and wired networks is what we can consider to
> be "short-term".
>
> (If your point is that having the knee depends on more than Little's
> law, then that is also true...)
>   

Now, the thought becomes important when we want to adapt a rate 
controlled source to actual network conditions,
e.g. in media streaming or in rate control TCP flavors. (Oh, that spell 
checker... ;-))

In addition, when a mobile runs into an interference minimum (some guy 
talked to me about "short time disconnection", which matches the policy 
of some NO who suspend channels with insufficient SNR from being 
serviced), there is absolutely no guarantee that this situation will 
ever change. So, what's an "average" then?

(O.k., after some time the mobile's battery will run low - and this will 
certainly stop the situation, which is of course some kind of "change" ;-))

The other point I wanted to address is the "latency bandwidth product" 
which is sometimes given or WWAN links and which frequently ignores that 
for a packet being in service not only the "original copy" is on the 
link (ignore RLP breakup of packets for simplicity) but the 
retransmissions require capacity as well.

So, either we regard retransmissions as packets being in service as 
well, or we have to reconsider the term "latency bandwidth product" for 
WWAN.


Detlef

-- 
Detlef Bosau		Galileistraße 30	70565 Stuttgart
phone: +49 711 5208031	mobile: +49 172 6819937	skype: detlef.bosau	
ICQ: 566129673		http://detlef.bosau@web.de			




More information about the end2end-interest mailing list