Subject: Re: [Diffserv] EF RFC and loss

From: Constantinos <[email-masked]>
Date: Thu, 4 Nov 1999 21:39:23 -0600 (CST)

Ion,

A (late) comment about your last note. 

I think that your analysis for the EF buffer requirements in
a router leads to very conservative results. One reason is that
you assume that we can have more than one EF flow in each
interface (perhaps you think about microflows?).
The second reason is that you don't take into account that
that the EF traffic should be regulated at each hop.
Let me first, though, describe how the EF traffic should be
aggregated in a router, at least in my understanding.

Each input or output interface carries at most one EF aggregate.
In the case of an edge router, the EF aggregate at an input
interface can be EF microflows, of course.

Now, in the context of a VLL-type of service, the (explicit or
sometimes implicit) assumption is that the routes of the EF
flows are known and fixed. This means that for a certain router,
the network manager knows how much of the EF traffic from each
input interface will go to each output interface.

To simplify slightly, say that a specific output interface receives
N aggregates of EF traffic, from N input interfaces respectively,
each having an EF capacity R. In this case, the EF capacity that
should be reserved in that output interface is N*R (statistical multiplexing
games with EF traffic are a "no-no"). Additionally, the EF traffic
that is forwarded to that output interface should be regulated by a
leaky-bucket shaper with the following parameters:
	service rate: N*R packets per second
	max burstiness: 1 packet
	# of buffers: N-1 packets 
                                                                                The regulation is necessary so that we avoid the clumping effect that
Stefano talks about. The queueing delay in the regulator, which can
be at most (N-1)/(N*R) with GPS, or N/C with strict-priority
(C is the link's capacity),  is within the queueing delay
bound of 1/R seconds that EF requires.

Going back to your example with the 32kbps EF microflows: I think that 
the only case in which we can need 15000 packet buffers or so is in a 
router with 15000 input ports.                 

Cheers,

Constantinos

> 
> Hi,
> 
> I just want to make a clarification with respect to the burstiness and
> buffer requirements at core routers for the premium service. In
> particular, the burstiness at an input/output port of a core router can
> be as high as the _number_ of EF flows that share that link.
> 
> Assume you have a router with N ports, and assume that EF traffic with
> a burst size of M packets arrives at each input port (i.e., there are
> M consecutive packets belonging to the EF traffic arriving at each
> input).  Then, if the EF traffic from all inputs is going to the same
> output, the burstiness of the EF traffic at that output will be M1 =
> N*M.
> 
> Thus, even if you start with perfectly regulated flows at each ingress
> (i.e., with burstiness 1), the burstiness at the output link of the
> s-th hop can be as high as N^s. 
> 
> On the other hand, the burst cannot exceed the total number of flows
> on the output link. Let m be the number of flows on the output
> link. Then the traffic burstiness at the s-th hop is
> 
>       min(m, N^s) (1)
> 
> Since at least theoretically we can arbitrarily increase s, let us
> consider that the burstiness is bounded by m.
> 
> Now, let us compute the buffer requirements. For this consider again
> the one router case in which EF traffic with burst size of M packets
> arrives at each input port, and the EF traffic from all inputs goes to
> the same output. Assume that the link speeds of the outputs and inputs
> are the same. This means that during the time it takes M consecutive
> packets to arrive at an input, the output will transmit at most M
> packets. Thus, at the end of the bursts the output will still have at
> least
> 
> 
>       (N-1)*M  = N*M - M = M1 - M1/N (2)
> 
> buffered packets waiting to be transmitted.
> 
> Since the burstiness on the output link M1 is bounded by m, i.e., the
> number of EF flows at the output port, from (2) it results that the
> buffer requirements at the output can be as high as
> 
>       m - m / N
> 
> EXAMPLE: Assume an OC-48 (2.4 Gbps) link and 32 Kbps EF flows. Further
> assume that the EF traffic is limited to 20 percents of the link
> bandwidth. Let C denote the link capacity and let r denote a flow
> rate. Then, the number of flows at the output port can be as high as
> 
>     m = 0.2 * C / r = 0.2 * 2.4Gbps / 32 Kbps = 15000
> 
> If we assume that the router has N=32 ports, then the buffer size should
> be at least 
> 
>     m - m / N = 14531 packets
> 
> Finally, I have two comments:
> 
> 1. If you regulate the aggregate EF traffic at each output, this will
> not help in the context of the above example. In particular, assume
> that you restrict the EF traffic to 30% of the link capacity. But then
> you can still have M packets arriving at each input at the rate
> 0.3*C. Since the output cannot send more than M packets during the
> same time interval it takes an input to receive M packets (as the EF
> traffic at the output is also rate limited to 0.3*C) the number of
> packets that needs to be buffered at the output at the end of the burst
> is still m*(1 - 1/N). Worse yet, regulating the EF traffic will increase
> the end-to-end delay.
> 
> 
> 2. The above "bound" is only for feed-forward networks; for general
> networks (in which the paths of several flows can result in cycles,
> e.g., flow f1 shares a common sub-path with f2, which shares a common
> sub-path with f3, which shares a common sub-path with f1) they can be
> much worse. For more details see
> 
>   R. Cruz, A Calculus for Network Delay, Part {II} : Network Analysis,
>   IEEE Transaction of Information Theory, 37, 1, 121-141, 1991.
> 
> 
> Ion
> 
> 
> Scott W Brim wrote:
> > 
> > At 14:34 10/28/1999 -0700, Kathleen Nichols wrote:
> > >Scott W Brim wrote:
> > > >
> > >...In a properly managed network very
> > > > little excess EF traffic will be admitted.  So if you're seeing a lot of
> > > > excess traffic, either your hardware is broken, your capacity management
> > > > is broken, or someone is sneaking packets in.
> > > >
> > >
> > >I would say "In a properly managed network NO excess EF traffic
> > >will be admitted." But perhaps you have a different definition
> > >of "excess" that I do.
> > >
> > >I think dealing with the excess traffic in a reasonable way is
> > >what the "better effort" or "class of service" services are
> > >all about. Traffic marked for the EF aggregate shouldn't have
> > >any of this excess.
> > >
> > >         Kathie
> > 
> > :nods
> > 
> > _______________________________________________
> > diffserv mailing list
> > [email-masked]
> > http://www.ietf.org/mailman/listinfo/diffserv
> > Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
> 
> _______________________________________________
> diffserv mailing list
> [email-masked]
> http://www.ietf.org/mailman/listinfo/diffserv
> Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
> 
> 

_______________________________________________
diffserv mailing list
[email-masked]
http://www.ietf.org/mailman/listinfo/diffserv
Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/

---

From: Stefano Salsano <[email-masked]>
Date: Fri, 05 Nov 1999 11:43:08 +0100

Dear Constantinos,

shaping is of no effect with respect to worst case analysis.
In general it make things even worse, because it increases
the average delay. 

Here is a simple example where you you cannot avoid worst case
clumping and you need more buffer than you assume. 

You have N input interfaces, each one having an aggregate EF rate of R.
From each interface, a VLL of rate R/N is directed to a
specific output port X, therefore you reserve the rate R on the
output port. 

If you assume shaping you have the following parameters on the 
output port 1X:
        service rate: R packets per second
        max burstiness: 1 packet
        # of buffers: N-1 packets 

Assume that at given time (T=0 s.) a packet appears on each input
interface, belonging to the VLL directed to the output port 1X.
The more unlucky VLL, say on input port 11, will have to wait (N-1)
packets. At time T=N/R s. a packet appears on port 1 directed 
to output port X, while no packets of the other VLL directed to
port 1X appear. Therefore you will have two consecutive packets
of a given VLL which appear at "istantaneous" rate R on the output 
line 1X. (Remember that the contractual rate of the VLL is R/N).

Assume that you combine N lines like the output line 1X as input
to a second level router, and assume that for each inpur port a VLL 
of contractual rate R/N is directed to output port 2X.
In a short interval 2/R s. you can receive 2N packets directed to
the output port 2X. In this interval you can output only 2 packets,
therefore you need to buffer (2N-2) packets.

I agree that this worst case is very conservative ... but if
you promise deterministic no loss you need the worst case.

Regards,
Stefano

-- 
*******************************************************************
Stefano Salsano
CoRiTeL - Consorzio di Ricerca sulle Telecomunicazioni
                  
E-mail  : [email-masked]      URL     : http://www.coritel.it
Tel.    : +39 06 20410029         Address : Via di Tor Vergata, 135     
Fax.    : +39 06 20410037                   00133 Roma - ITALY          
*******************************************************************

---

From: Ion Stoica <[email-masked]>
Date: Fri, 05 Nov 1999 14:59:55 -0500

Hi Constantinos,

Even if you ignore the "clumping" effect, an interior node still needs
to have a buffer whose size is proportional to the number of flows
that traverse that node. As it was mentioned before, per aggregate
regulation will not help. Even if you regulate the EF aggregates at
both the inputs and outputs, the buffer requirements still depend on
the number of flows. In particular, regulating the traffic from each
input to each output, as I believe you proposed, will just result in
having large buffers at the inputs, instead of outputs.

NOTE: To eliminate any confusion, in the followings I will use the
word "flow" to denote the aggregate traffic between an input of an
ingress and an output of an egress node, i.e., the traffic that
follows the same path through a diffserv domain.

For clarity, consider the following simple topology, where 1, 2, 3,
and 4, are ingress routers, and 5, 6, and 7, are interior routers. For
simplicity, assume that all packets have unit size, and that all the
input/output ports run at the same speed. Finally, assume that the
time is divided in slots, where a slot represents the time it takes to
send a packet.

Now, let "o" denote a time slot during which a packet that reaches the
first output of router 7 is sent, and let "." denote a time slot
during which no such packet is sent. The packets are moving from left
to right.

              --
 ........o --|  |
             |1 |                ---
 ........o --|  |-- .......oo --|   |
              --                |   |
                                | 5 |
              --                |   |
 ........o --|  |-- .......oo --|   |-- .....oooo -
             |2 |                ---               \
 ........o --|  |                                   \   --
              --                                     --|  |-- .oooooooo
                                                       |7 |
              --                                     --|  |
 ........o --|  |                                   /   --
             |3 |                ---               /
 ........o --|  |-- .......oo --|   |-- .....oooo -
              --                |   |
                                | 6 |
              --                |   |
 ........o --|  |-- .......oo --|   |
             |4 |                ---
 ........o --|  |
              --

Next, let us concentrate our attention on router 7.  Consider the
following cases:

- no regulation (the EF traffic has strict priority). Then, during the
first four time slots each of the inputs of router 7 receives exactly
four packets, while the output can send at most four packets (recall
that both inputs and outputs run at the same speed).  As a result, the
output needs a buffer of at least four packets.

In general, if you have a router with N inputs, then the output of the
s-th hop needs a buffer of at least (N - 1)*N^{s-1} packets. In our
example, we have N=2, s=3, which gives us a four packet buffer, as
mentioned above.

- each output is restricted to use a certain fraction of the link
capacity (e.g., 20%) for the EF traffic. This case reduces to the
previous one. The only difference is that it will take longer to send
one packet (assuming an idealized fluid flow system). As was mentioned
before this will not decrease the buffer requirements; it will only
increase the delay.

- each output is regulated at slightly more than the aggregated EF
traffic rate. This case can be reduces to the previous one, i.e., the
case in which we allocate the same rate to EF on each link. To achieve
this, just assume enough EF cross traffic (following different paths)
to drive the aggregate on each link to the same value.

- both the inputs and outputs are regulated at slightly more than the
aggregate rates. In particular, an input will regulate the traffic at
its aggregate reserved rate before sending it to the output. While
this will reduce the amount of buffers at the output to a level that
you are mentioning, i.e., the amount of buffer space is equal to the
number of inputs, it will increase the buffer requirements at the
input.

To see this, assume a router that receives at input i aggregate EF
traffic at a rate R, and assume that this consists of n flows of rate
r, i.e., R = n*r. Then assume that n/K of these flows go to the
output j. As a result the traffic from input i to output j will be
regulated to R/K. Now assume that all packets of these n/K flows are
received back-to-back, i.e., it will take

                    t = (n / K)/ R = n / (K*R)

to receive these packets. In contrast, since the rate between input i
and output j is limited to R/K, during the same time input i can
transfer to output j only

                     m = (R/K)*t = n/K^2

packets. Thus, at the end of this interval the input i has to store

                     n/K - m = n/K (1 - 1/K)

packets for output j. It is easy to see that this value is maximized
for K=2. Thus even if you regulate the traffic at the inputs you still
need a buffer of size proportional to the number of flows. And recall
that this is only for one output; the input has to eventually maintain
a buffer for each output port.

Finally, as Stefano noted, taking into account "clumping" will only
increase the buffer requirements.

To summarize, the main points of this discussion are: (a) if you are
concerned with the worst case, then buffer requirements can be
quit large, and (b) per aggregate regulation is of little help in
reducing these buffer requirements.

Please let me know if you have any other comment(s) or question(s).

Thanks,

Ion