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

From: [email-masked]
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 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 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 shows the bandwidth required for a call as a function of the
delay bound, assuming that the call takes 5 hops. 

* Note that with P1max set to 64 Kbytes, delay bounds of 50 ms or less are 
unachievable. With this value for P1max, when the delay bound is 150ms, 
a single call must reserve nearly 15.6 Mbps!

* The numbers are considerably better with the reference connection's
max packet size set to 8 Kbytes, but even so, with a 100 ms delay bound,
a connection needs a reservation of ~10% of the link capacity, so that the link
can accommodate only 10 such calls.

* When P1max is small, then the bandwidth required for smaller delay bounds
are more reasonable.

Table 4 shows the same results when both P1max and P2max
are restricted to 53, 256, and 1500 bytes.

* With restrictions on the GS packet size, even 5ms delay bounds can be supported.  
* The cost for 50ms bounds are not too bad, even for 1500 byte packets.

-------------------------------------------------------------------------------
Table 3: Bandwidth required for a 5 hop connection, P2max = 8192

		reference connection max. packet size (P1max)=
delay bound	53		8192		65536

0.005		-		-		-	
0.01		-		-		-	
0.05		3107995		9204877		-
0.075		1960595		5806650		32904349
0.1		1431952		4240979		24032212
0.15		930280.6	2755191		15612751
0.2		688922.9	2040368		11562083
0.25		547004.7	1620051		9180291
0.5		269460.3	798054.5	4522309
1		133741.9	396100.3	2244568

-------------------------------------------------------------------------------
Table 4: Bandwidth required for a 5 hop connection, both
	 P1max and P2max restricted

	 		P1max= P2max =

bound	53		256		1500

0.005	26806174 	29180853	_
0.01	13339645 	14250682	20662154
0.05	2657864 	2798014		3679562
0.075	1771353 	1862504		2430842
0.1	1328306 	1395816		1814919
0.15	885398.1 	929837.3	1204520
0.2	663996.4 	697113.2	901369.1
0.25	531172.1 	557563.5	720128.7
0.5	265561.0 	278654.8	359101.6
1.0	132774.3 	139295.7	179311.1

-------------------------------------------------------------------------------

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 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
-------------------------------------------------------------------------------

4. Experiment 3: Voice on Int-serv

In the second experiment, I look at the bandwidth that must be reserved 
for a voice call over an Int-serv Internet. I assume that 

o P1max = 64 bytes 
	This corresponds to 28 bytes of UDP/IP header and 36 bytes of voice

o token bucket for a voice call is 64 bytes
	1 packet in a burst
	
o an end-to-end delay bound of 50ms, so that the round-trip delay of 100ms 
	is within ergonomic bounds.  (I'm assuming 0 prop. delay)

Table 6 has the bandwidth requirements. DS0 equivalents are in Table 7. 

* Note that with P2max of 64 Kbytes, we cannot meet the delay bound
for a 5 hop call. 

* Things are better with a 16 Kbyte limit on cross traffic. 
But even there, with 10 hops, we need to reserve the equivalent of ~4 DS0s.

* As long as the cross traffic packet size is limited, things are not bad at all.
Therefore, it makes sense to _require_ all traffic in the guaranteed service
class to use small(er) packet sizes.

-------------------------------------------------------------------------------
Table 6: Bandwidth required for a voice call 50 ms end-to-end delay. P1max = b=
	64

# hops		  cross traffic max. packet size

	1500		8192		16384		65536

1	10294.91	10547.21	10873.42	13351.01
2	20700.81	21746.85	23180.75	38354.49
3	31219.51	33661.38	37225.65	102077
4	41852.86	46361.51	53404.04	602952
5	52602.74	59927.59	72242.01	
6	63471.07	74451.31	94454.1	
7	74459.83	90037.78	121036	
8	85571.03	106808.1	153417.9	
9	96806.72	124902.4	193730.7	
10	108169		144484		245294.3	

-------------------------------------------------------------------------------
Table 7: Bandwidth required for a voice call 50 ms end-to-end delay
         (in DS0 equivalents)

# hops		  cross traffic max. packet size

	1500		8192		16384		65536

1	0.157088	0.160938	0.165915	0.20372
2	0.315869	0.331831	0.35371		0.585243
3	0.476372	0.513632	0.568018	1.557571
4	0.638624	0.70742		0.814881	9.200317
5	0.802654	0.914422	1.102326	
6	0.968492	1.136037	1.441255	
7	1.136167	1.373868	1.846863	
8	1.30571		1.629762	2.340972	
9	1.477153	1.90586		2.956095	
10	1.650528	2.204651	3.742893
-------------------------------------------------------------------------------

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.

---

From: Jon Crowcroft <[email-masked]>
Date: Tue, 27 Feb 1996 15:05:19 +0000

>service traffic with WFQ scheduling
 
 keshav,

this is a useful piece of work....

 >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

---

From: Craig Partridge <[email-masked]>
Date: Wed, 28 Feb 96 08:55:32 -0800

Hi Keshav:
    
    Interesting numbers.  I'm not surprised that packetization effects
occur at 45 Mbps.  (Historically I've argued that packetization effects
recede into the noise as bandwidth goes up and 45 Mbps is too slow for
that to occur).

    Since you have the spreadsheet all set, can you rerun Experiment 1 with
the link bandwidth being 155 Mbps, 622 Mbps and 2.4 Gbps?

    What I'm interested in is the relative contributions of link speed and
requested guaranteed rate.

Thanks!

Craig

---

From: Craig Partridge <[email-masked]>
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:

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