Subject: Re: Bandwidth reservations with WFQ (long -- 325 lines)

From: [email-masked] (Sven Tafvelin)
Date: Mon, 25 Mar 1996 14:37:33 +0100

I have been studying the mail from [email-masked] and would
like to add to it.

A major part of the bandwidth requirements needed in his calculations
is to empty the token bucket which he is estimating to 16K bytes. I cannot
find that very realistic in most cases. If my computer would take part in
an activity where I require strict delay limitations (taking part in a
videoconference for example) it would with a high probability not doing
something else. Therefore I could easily accept that the token bucket
was reduced. To see the influence of the token bucket I have added to
the earlier mail the corresoponding results if a token bucket size of
zero or 1K byte:
> 
> 
> ------- start of forwarded message (RFC 934) -------
> From: [email-masked]
> Sender: [email-masked]
> To: [email-masked], [email-masked]
> Subject: Bandwidth reservations with WFQ (long -- 325 lines)
> Date: Mon, 26 Feb 96 09:40 EST
> 
> A study of bandwidth requirements for guaranteed 
> service traffic with WFQ scheduling
> - -------------------------------------------------
> 
> S. Keshav
> 
> [email-masked]
> 
> 1. Introduction
> - ---------------
> 
> Guaranteed service in an Integrated services IP network is likely
> to use Weighted Fair Queueing (WFQ) or a variant that provides similar
> delay bounds. In this scheme, a user describes a burst size and data rate
> with a leaky-bucket-like descriptor, as well as an end-to-end delay bound.
> The delay bound is used by intermediate switches to compute a bandwidth
> reservation.
> 
> How much bandwidth must be reserved at a WFQ server to guarantee
> a particular end-to-end delay bound? The solution can be obtained by
> inverting Parekh and Gallager's well-known equation
> 
> worst-case-delay (d) = token-bucket-size (b)/allocated rate (g) +
> 			(# hops (N) -1) * my max. pkt size (P1max)/g +
> 			N * network's max pkt size (P2max) / link speed (r)
> 
> (assuming that links are homogeneous).
> 
> Inverting, this gives us
> 
> 	g = (b + (N-1)*P1max)/(d - (N*P2max/r))
> 
> Note the presence of P1max and P2max, which are packetization delays,
> and can considerably affect the fluid delay bound of b/g.
> To quantify this, I entered this equation into a spreadsheet to see 
> what sort of numbers came out for `reasonably conservative' values of 
> the parameters. While this produces very nice curves on my screen,
> I am only showing the tables here, for ease of dissemination. 
> 
> 2. Experiment 1  (Naive)
> - ------------------------
> 
> For the first experiment, 
> 
> o All links are homogeneous and have service rate (r) of 45 Mbps. 
> 	This models DS3-based backbones
> 
> o The token bucket size (b) of the reference connection is 16 Kbytes
> 	This is pretty small, and not far from what TCP uses in practice.
> 	For video applications, this would actually be much larger
> 
> 0 The largest packet size in the cross traffic (P2max) is 8 Kbytes.
> 	Again, this understates the largest allowed packet size (64 Kbytes).
> 	For the bound, we have to use the largest size, even if most
> 	packets are usually smaller than 1500 bytes because of Ethernet. 
> 	(The results are less than 20% off if we use P2max = 1500 instead of 
> 	P2max = 8192.)
> 
> I varied N (# hops), d (the required delay bound), and the connection's own max. 
> pkt. size P1max. Note that g is _independent_ of the actual bandwidth required by 
> a call. It is the _reservation_. Compare g to 45 Mbps to see the fraction of 
> the link that must be reserved by a single call.
> 
> Table 1 shows the sensitivity  of g to P1max and # hops, assuming d is 100ms.
> 
> * For one hop, the reference connection's max packet size doesn't matter. 
> 
> * When the reference connection's max. pkt. size is 4K (a `reasonable' value),
> note that on a 10 hop path, each hop has to reserve more than 10% of its capacity
> for the connection (_even_ if the connection only wanted 100 Kbps!).
> 
> * When P1max is 64 Kbytes, the delay bound cannot be met for a call longer 
> than 8 hops. 
> 
> * For 6 hops, a reasonable number of hops to expect, even with a 
> packet size limited to 4 Kbytes, a reservation of 3.2 Mbps is necessary, 
> 
> * In contrast, in an ATM network, where the connection's own 
> packet size is restricted to 53 bytes, and the largest cross traffic packet is 
> also restricted to 53 bytes, if the network implements WFQ at the cell level, 
> the bandwidth requirment hardly increases with number of hops.(Table 2). 
> 
> * If the max. packet size is restricted to 1500 bytes, there is about
> a 100% increase in bandwidth requirement for 10 hops, and a 45% increase
> for 6 hops, compared to an ATM network.
> 
> Packetization does matter.
> 
> - -------------------------------------------------------------------------------
Table 1a: Bandwidth required for a 100 ms end-to-end delay (P2max = 8K)
          and token bucket size of 0 bytes
          
# hops			reference connection's max. packet size (P1max)         
          
 	53	128	256	512	1024	4096	8192	32768	 65536 
 	        
 1       0        0       0       0        0       0       0        0        0  
 2    4367    10547   21094   42188    84377  337510  675021   270008  5400171  
 3    8867    21415   42831   85662   171325  685301 1370602  5482410 10964820  
 4   13506    32620   65240  130481   260962 1043848 2087697  8350788 16701577  
 5   18291    44176   88353  176707   353414 1413659 2827319 11309276 22618552  
 6   23229    56102  112204  224409   448818 1795273 3590546 14362187 28724374  
 7   28327    68414  136829  273658   547316 2189264 4378528 17514114 35028228  
 8   33593    81132  162265  324530   649061 2596244 5192488 20769954 41539908  
 9   39036    94277  188554  377108   754216 3016866 6033733 24134934   
10   44664   107869  215739  431478   862957 3451829 6903658 27614632   

Table 1b: Bandwidth required for a 100 ms end-to-end delay (P2max = 8K)
          and token bucket of 1024 bytes
          
# hops			reference connection's max. packet size (P1max)  
 
	53	128	256	512	1024	4096	8192	32768	 65536
	
 1   83130    83130   83130   83130    83130   83130   83130    83130    83130  
 2   88744    94924  105472  126566   168755  421888  759399  2784463  5484549  
 3   94530   107078  128493  171325   256987  770963 1456265  5568072 11050483  
 4  100494   119607  152227  217468   347949 1130836 2174684  8437776 16788564  
 5  106645   132530  176707  265061   441768 1502013 2915672 11397630 22706906  
 6  112993   145865  201968  314172   538582 1885037 3680310 14451950 28814138  
 7  119547   159633  228048  364877   638535 2280483 4469748 17605334 35119448  
 8  126316   173855  254988  417253   741784 2688967 5285211 20862678 41632632  
 9  133313   188554  282831  471385   848493 3111143 6128010 24229210   
10  140548   203753  311623  527362   958841 3547713 6999542 27710516   

and the the original table with token bucket size of 16K bytes

> Table 1: Bandwidth required for a 100ms end-to-end delay (P2max = 8192)
> 
> # hops			reference connection's max. packet size (P1max)
> 
> 	53	128	256	512	1024	4096	8192	32768	65536
> 
> 1	1330091	1330091	1330091	1330091	1330091	1330091 1330091	1330091	1330091
> 2	1354410	1360590	1371137	1392232	1434421	1687554	2025064	4050129	6750214
> 3	1379470	1392018	1413434	1456265	1541928	2055904	2741205	6853013	12335423
> 4	1405305	1424418	1457039	1522279	1652760	2435647	3479495	9742587	18093376
> 5	1431952	1457836	1502013	1590367	1767074	2827319	4240979	12722936 24032212
> 6	1459449	1492321	1548423	1660628	1885037	3231492	5026765	15798406 30160593
> 7	1487837	1527924	1596339	1733168	2006826 3648774	5838038	18973624 36487738
> 8	1517162	1564701	1645834	1808099	2132629 4079813	6676057	22253523 43023479
> 9	1547470	1602710	1696988	1885542	2262650 4525300	7542167	25643367	
> 10	1578811	1642016	1749886	1965625	2397103 4985975	8437804	29148779	  
> 
> - -------------------------------------------------------------------------------
Table 2a: Bandwith required for a call for 100ms end-to-end delay if reference 
	 connection and cross traffic packets are restricted and token bucket
	 size is 0. 
 
# hops	   P1max = P2max = 
	53	256	1500
	
 1       0        0        0  
 2    4240    20498   120643  
 3    8482    41016   241935  
 4   12724    61552   363881  
 5   16967    82106   486486  
 6   21211   102680   609756  
 7   25456   123272   733695  
 8   29702   143883   858310  
 9   33948   164513   983606  
10   38195   185162  1109589  

Table 2b: Bandwith required for a call for 100ms end-to-end delay if reference 
	 connection and cross traffic packets are restricted and token bucket
	 size is 1K bytes. 

# hops		P1max = P2max = 
	53	 256	  1500
	
 1   81927     81957     82139  
 2   86176    102493    203002  
 3   90425    123048    324516  
 4   94675    143621    446684  
 5   98926    164213    569513  
 6  103178    184824    693008  
 7  107430    205454    817173  
 8  111684    226103    942016  
 9  115938    246770   1067541  
10  120193    267457   1193753  

and the original table where token bucket size is 16 K bytes

> Table 2: Bandwith required for a call for 100ms end-to-end delay if reference 
> 	 connection and cross traffic packets are restricted. 
> 
> # hops		P1max = P2max = 
> 	53		256		1500
> 
> 1	1310844 	1311317		1314225
> 2	1315208 	1332413		1438391
> 3	1319573 	1353528		1563226
> 4	1323939 	1374662		1688733
> 5	1328306 	1395816		1814919
> 6	1332673 	1416989		1941789
> 7	1337042 	1438182		2069348
> 8	1341411 	1459393		2197602
> 9	1345781 	1480625		2326557
> 10	1350152 	1501875		2456219
> 
> - -------------------------------------------------------------------------------
> 

(table 3 and 4 deleted)

> -------------------------------------------------------------------------------
> 3. Experiment 2: Fragmentation and reassembly
> 
> In the previous experiment, the source was assumed to send packets of
> a given max size (P1max). In the second experiment, the source has
> a given _frame_ size F of 8Kbytes. It fragments the frame before transmission.
> The key point is that for a given fragment size, we need to wait for 
> a reassembly time at the endpoint for all the fragments to arrive.
> Thus, the delay bound when fragmenting must include the time for
> reassembly. Unfortunately, the reassembly time depends on the bandwidth
> reservation, which, in turn, depends on the delay bound. Therefore,
> for each fragment size, we need to solve the following equations:
> 
> g = (b + (N-1)P1max)/(d' - N*P2max/r)  	(Parekh-Gallager)
> d' = d - F/g				(reduce delay bound by reassembly time)
> 
> where F is the frame size (8K), and d' is the  delay bound taking 
> reassembly time into account.
> 
> Solving for g, we get
> 
> g = (b + (N-1)*P1max + F)/(d - N*P2max/r))
> 
> This equation allows us to compare the benefits of fragmentation,
> taking the reassembly time into account.
> 
> As before, d=0.1s, P2max = 8192. Also, F = 8192.
> 
> * Note that the effect of fragmentation is most pronounced for small
> fragment sizes. For a fragment size of 53 bytes, the bandwidth requirement
> is substantially higher than when the reassembly time is ignored.
> 
> * In general, the bandwidth requirements are larger than in Table 1.
> 
> * However, fragmentation is _still_ a win. Compare the 53 byte column
> with the 8192 byte column. This is because of the multiplexibility of
> smaller fragments.
> 
> - -------------------------------------------------------------------------------

 Table 5a: Bandwidth required for a 100ms end-to-end delay, including
	reassembly time, frame size = 8192 bytes and token bucket size 0.

		Fragment size =

# hops	53	128	256	512	1024	4096	 8192
 1  665045   665045  665045  665045   665045  665045   665045  
 2  679388   685568  696115  717210   759399 1012532  1350042  
 3  694168   706716  728132  770963   856626 1370602  2055903  
 4  709405   728519  761139  826380   956861 1739747  2783596  
 5  725121   751006  795183  883537  1060244 2120489  3534148  
 6  741339   774211  830313  942518  1166927 2513382  4308656  
 7  758082   798169  866583 1003412  1277070 2919019  5108283  
 8  775378   822916  904049 1066314  1390845 3338028  5934273  
 9  793253   848493  942770 1131325  1508433 3771083  6787950  
10  811737   874942  982812 1198551  1630030 4218902  7670731  

 Table 5b: Bandwidth required for a 100ms end-to-end delay, including
	reassembly time, frame size = 8192 bytes and token bucket size
	of 1K bytes.

		Fragment size =

# hops	53	128	256	512	1024	4096	 8192

 1  675436   675436  675436  675436   675436  675436   675436  
 2  689935   696115  706663  727757   769946 1023079  1360590  
 3  704876   717424  738840  781671   867334 1381310  2066611  
 4  720279   739392  772013  837253   967734 1750621  2794469  
 5  736165   762050  806227  894581  1071288 2131533  3545193  
 6  752559   785432  841534  953738  1178148 2524603  4319876  
 7  769485   809571  877986 1014815  1288473 2930421  5119685  
 8  786968   834507  915639 1077905  1402435 3349618  5945863  
 9  805037   860278  954555 1143109  1520218 3782868  6799734  
10  823723   886928  994797 1210537  1642015 4230887  7682716  

and the original table where token bucket size i 16 Kbytes

> Table 5: Bandwidth required for a 100ms end-to-end delay, including
> 	reassembly time, frame size = 8192 bytes.
> 
> 		Fragment size =
> 
> # hops	53	128	256	512	1024	4096	8192
> 
> 1	1995136	1995136	1995136	1995136	1995136	1995136	1995136
> 2	2029431	2035611	2046159	2067253	2109442	2362575	2700086
> 3	2064771	2077319	2098735	2141566	2227229	2741205	3426506
> 4	2101204	2120317	2152938	2218178	2348659	3131546	4175394
> 5	2138781	2164666	2208843	2297197	2473904	3534149	4947808
> 6	2177558	2210430	2266533	2378737	2603146	3949601	5744875
> 7	2217592	2257679	2326093	2462922	2736580	4378529	6567793
> 8	2258946	2306485	2387618	2549883	2874413	4821597	7417841
> 9	2301687	2356927	2451204	2639758	3016867	5279517	8296384
> 10	2345884	2409089	2516959	2732698	3164177	5753048	9204877
> - -------------------------------------------------------------------------------
> 
(Voice experiment deleted)
>
> 5. Conclusions
> 
> Parekh-Gallager bounds with WFQ are bad (even for reasonable traffic values)
> when either the reference connection or the cross traffic connections use large
> packets. This is because of the effect of packetization on the delay bound. 
> Some of the badness goes away with packet fragmentation.
> 
> This suggests that either (a) Guaranteed Service traffic must be restricted
> to small packet sizes, or (b) GS frames should be fragmented.
> 
> On a positive note, when the cross traffic packet size is restricted,
> the requirements for voice calls are not too bad. This bodes well for
> carrying CBR voice on int-serv. 
> 
> 6. Acknowledgment
> 
> I would like to thank K.K. Ramakrishnan for suggesting Experiment 2.
> ------- end -------

Later on Craig Partridge reacted on the discussion and some work
done by Robert Olsson:

------- start of forwarded message (RFC 934) -------
>Sender: [email-masked]
>To: [email-masked]
>Cc: [email-masked], [email-masked]
>Subject: Re: Bandwidth reservations with WFQ (long -- 325 lines) 
>Date: Fri, 01 Mar 96 09:49:52 -0800

>Hi Keshav:

>I did some more playing with the equations today (thanks in large part
>to Robert Olsson, who sent me some gnuplot equations he'd been playing with --
>Thanks Robert!).

>The interesting thing I found from Robert's plots was that at a certain
>point, changing the line bandwidth didn't matter.  One can also see this
>looking at the equation you sent:

>	g = (b + (N-1)*P1max)/(d - (N*P2max/r))

>The value of the guaranteed bandwidth (g) is minimized when the denominator
>is maximized.  So briefly, here's the denominator values for the tests
>you ran (plus higher bandwidths).  Always assume P2max is 8192 bytes and
>the desired d is 100 ms or 0.1s, so our goal is to have the denominator
>as close as possible to 0.1.

>    N values	 r=45Mbps	r=155Mbps	r=622Mbps
>    1		 0.0985		 0.0996		 0.0999
>    5		 0.0927		 0.0979		 0.0995
>    10		 0.0854		 0.0958		 0.0989
>    20		 0.0709		 0.0915		 0.0979

>Now my conclusion from these numbers is that, as rates increase, we can
>ignore the N*P2max/r term.  (Things are bad for 20 hops all at 45Mbps but
>rapidly stop being a problem with higher link speeds).

>If we ignore the N*P2max/r term, then the question of delay is entirely
>a matter of choosing P1max, *WHICH IS ENTIRELY AN APPLICATION DECISION.*
>Now choosing P1max, as you point out, is a big deal (end-to-end delays can
>be quite high).  But that's info to feed application authors.  It doesn't
>change the INT SERV specs.

>Craig
------- end -------

My findings from the discussion and my calculations are

1) The token bucket size must be small when we have delay sensitive communication.
A small factor (b) gives us much better situation regarding the possibilities to
fulfil the delay requirement. This is valuable information for those working
with operating systems and communication software.

2) The number of hops (N) is important. The things is easier if N can be
kept small. This is valuable input for those of us building networks.
NETWORKS SHOULD BE ORGANIZED IN SUCH A WAY THAT THE NUMBER OF HOPS IS
KEPT AS SMALL AS POSSIBLE! I have made some traceroutes indicating to me
that some net-builders have not understood this.

It may be the case that network service providers sometimes in the future
will compete offering few-hop networks. But I guess it will be
hopeless to hope for hop-less networking. (:-))

3) Even if we assume unlimited transport speed (Craig Partridge above) the
influence of the two factors above is still there and cannot be ignored.
On the other hand when the short term decision for a specific transport need
to be done the software deciding on (b) and the network topology (N) is already
there and fixed and the only thing we can change is P1max. I assume that this
is the situation which Craig assumed when he made the statements above.

Earlier Jon Crowcroft had responded in more general terms: 

>>A study of bandwidth requirements for guaranteed 
> >service traffic with WFQ scheduling
> >-------------------------------------------------
 
> keshav,

>this is a useful piece of work....

> >inverting Parekh and Gallager's well-known equation
 
> >worst-case-delay (d) = token-bucket-size (b)/allocated rate (g) +
> >			(# hops (N) -1) * my max. pkt size (P1max)/g +
> >			N * network's max pkt size (P2max) / link speed (r)

> >Packetization does matter.

>but only if you want 100% of packets inside the worst case delay....

>so a good reason for moving to a lossy model, and relaxing the
>constraint (and looking at average case delay, and variance, not worst
>case...) given the loss tolerant codings some people are now
>devising...

>cheers
>jon

I don't think that we have an either-or situation but a both-and one instead.
It is definitely a good thing to get applications which can stand loss/delayed
arrival of a packet now and then. This simplifies the situation for all parties.
But there will be cases where we need to know the maximum delay or the other
way around to be able to calculate the bandwidth needed to be able to promise
the maximum delay for sure.

I think it will be very difficult to build a correct, usable theory for the
WFQ system since the statistical behaviour of most of the input we need is
unknown. So good luck!

Regards
Sven Tafvelin