Subject: [Diffserv] on the delay bound of VW

From: Anna Charny <[email-masked]>
Date: Wed, 26 Jul 2000 20:46:27 -0400

Hi,

If I understand it correctly, the VW draft claims that the delay of  any VW 
packet is bounded by S/R + hMTU/C where h is the number of hops the circuit 
traverses.
This claim is made under the assumption that

1)  the configured rate of EF aggregate on any  link does not exceed 50% of 
the link bandwidth
2)  the rate of any individual VW "circuit" does not exceed the 
1/(1+max(n_j))   where n_j is defined as the max number of other VW 
circuits that circuit j can meet as it traverses the domain;  (here S is 
the max packet size of the VW packets and R the VW circuit configured rate).

Here is an example when this bound  does not seem to hold:

VW circuits 1 and 2 traverse  2 separate node chains, each containing 
N  nodes in it.
these chains converge  at node that we will call nodeX
VW circuit 3 enters nodeX immediately upon leaving its source,  and merges 
with circuits 1 and 2 on the same outgoing link
all links are of the same speed C
each circuit has the rate R = C/6
all packets are the same size S=MTU, and they are ideally shaped to their 
rate at the entry top the router
there are no other VW circuits in the network
all routers implement PQ.

Note that all the rate constraints mentioned in the VW draft seem to be 
satisfied - no link is over 50% utilized, and since the total number of VW 
circuits is only 3, the constraint  on the individual circuit rate is also 
satisfied;  all flows are strictly shaped at the input to the network, and 
the routers implement the "priority queuing model of EF".  So it seems to 
me it  is a "properly configured network" (if it isn't, I hope someone 
would tell me what I am missing here).

Here is the picture:
                                                                                      cir3
cir1 
|
o----------->o-----------o--------...---------o------- |        |
cir2 
V     V
o----------->o-----------o--------...---------o------->nodeX---------->

So now assume that at time zero the first packet of cir 1 and cir 2 enters 
its own chain, and at each node in the chain it sees a non-EF packet, also 
of size S.  That means that in N hops the first packet of cir 1 and cir 2 
is delayed by NS/C.  If the other packets of cir 1 and cir2 do not see any 
non-EF packets,  N/6  back-to-back packets of cir1 and c2 will accumulate 
by the time the first packet reaches nodeX (assume it happens by time t). 
Assume at nodeX there is also a non-EF packet at time t.  That means that 
by time t1= t+NS/6C,  N/6 packets of each of cir 1and cir2 will arrive, and 
N/6 - 1 of those packets will depart (the non-EF packet and N/6 - 1 VW 
packets will leave), so there will be N/6+ 1 VW packets in the queue at 
time t1.  Suppose now a packet of cir3 (color it blue) arrives at nodeX at 
time  t1.  Its queuing delay will be equal to NS/6C + S/C

Choosing N=6K for some K will result in the blue packet being delayed by 
KS/R plus one MTU at link speed.  For any K>1 this seems to violate the 
delay bound for cir3: since cir3 only traverses a single hop its delay 
bound according to the VW draft should be S/R + S/C

What did I misunderstand?

I tried to understand the origin of the contradiction between this example 
and the argument in VW draft showing the tight bound.  Here are some 
thoughts that were helpful for me to sort it out - I am posting them here 
in the hope they may be also helpful to others.

First, I will try to re-state  the  argument that seems to be  used  to 
demonstrate the small jitter bounds in draft-ietf-diffserv-pdb-vw-00, as I 
understand it:
The argument appear to have 5 logical steps:

Statement 1:  In the absence of any non-EF traffic, in a VW-only network a 
VW packet can meet any other packet of any other VW "circuit" in the queue 
at most once as that packet traverses the domain, provided the following 
conditions on the rates of Ef aggregate and EF circuits hold:

                  1)  the configured rate of EF aggregate on any  link does 
not exceed 50% of the link bandwidth
                  2)  the rate of any individual VW "circuit" does not 
exceed the 1/(1+max(n_j))   where n_j is defined as the max number of other 
VW circuits that circuit j can meet as it traverses the domain.

Statement 2:  Statement 1 implies that in the absence of non-EF traffic any 
VW packet will be delayed in all  queues combined by at most S/R (one 
packet interval at the rate)
Statement 3:   Given PQ model of EF,  at most one non-EF packet can 
interfere with  the Ef aggregate at each hop

Statement 4.   The jitter of a given packet is the jitter it would 
experience in a network without non-EF traffic at all  plus the time it 
takes to transmit all the non-Ef packets it encounters.

Statement 5: Statement 4 implies that (assuming same speed links) the 
jitter bound is S/R + hMTU/C where h is the numer of hops.

I would like to note here that the logic indicated by the sequence of 
statements 1-5 above is NOT quite how the VW draft is actually 
presented.  However, the above appears to be the only way I could interpret 
the text so that it made sense to me (I am sending detailed comments and 
clarification questions on the details of the draft in a separate 
message).  So it is possible that my interpretation of the logic of the 
proof is not what the authors of the draft intended. I am sure they will 
correct me if that is so.

The high-level (intuitive :-)) reason this 5-step argument might be wrong 
is that interaction with non-EF packets causes some of the VW packets to 
"bunch up". This bunching up may end up resulting in multiple EF packets of 
the same "circuit" catching up with each other over a few hops.  If you 
then bring several of such "bunched-up" VW circuits together, then some 
packets  may see more than one packet of other circuits ahead of it in the 
queue.  That may cause delay queuing delay which is larger that S/R + hMTU/R.

The example I gave at the beginning of this message indicates that 
statements 4 and 5 are actually incorrect. In this example, the delay of 
the blue packet is affected by non-EF packets encountered by *other* VW 
packets.   The delay in the absence of Ef packets and the delay of a given 
packet due to the EF packets it encountered is NOT actually additive.  The 
"bunching up" of other packets should be accounted for and is not.

Note also that in the example above, the blue packet sees more that one 
packet of each other VW circuit.  This does appear to contradict the 
popular belief that it cannot happen in  a "properly configured EF network".

Regards,
Anna

---------------------------------------
Anna Charny
Cisco Systems, Inc
300 Apollo Drive
Chelmsford, MA  01824
Tel. (978)-244-8172
Fax (978)-244-8126

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