Subject: Traffic Policing and domino effect

From: Philippe OECHSLIN <[email-masked]>
Date: Wed, 11 Jun 1997 11:42:49 +0100

I see a problem with routers doing policing and serving non-conformant
traffic with best effort service.

Imagine a source sending traffic which is close to its maximum
envelope. At some point the source sends a burst which is non
conformant.

A router with policing function will discover the non-conformant
burst and put it into the best effort queue. This means that the
burst may be delayed more than the rest of the flow and thus be
reinserted in the flow at a later point. 

Now the next router doing policing will discover non-conformant
traffic around the new location of the burst. However it may well be
that it is not exactly the packets of the burst that are found to be
non-conformant but the packets just following it. These packets are
again delayed by serving them with best effort service. They will thus
be reinserted into the flow at later point. The flow will be
non-conformant at that later point for the next router.

The result is that one non-conformant burst generates a tail of
repeating non-conformant bursts in the traffic flow. Each router only
sees one non-conforming burst at a time, but the flow ends up having a
repeating pattern of resequenced or possibly dropped packets.

My conclusion is that a router which modifies the structure of a flow
must always reshape the flow to avoid any further degradation of the
flow by a later policing function. Alternatively one could prohibit
policing anywhere else than at the ingress to a network.

Note that routers which don't do policing may still modify the structure
of a flow depending on the scheduling strategy they use. Thus in the
above example, the source might have been sending conforming traffic
and the burst might have appeared at the output of a router doing
priority scheduling.

  Philippe

--
[email-masked]

---

From: Craig Partridge <[email-masked]>
Date: Wed, 11 Jun 97 09:20:31 -0700

Right, and under the current specifications, once the source does this
all guarantees or promises are invalid.

Which is fine.

Yes -- the specifications are clear that this will happen.

This is not a problem but a well-described result of violating the traffic
rules.

Craig

---

From: Roch Guerin <[email-masked]>
Date: Wed, 11 Jun 97 18:11:56 -0400

A quick remark concerning the issue of handling non-conformant traffic
in the case of CL.  We had a related discussion with John on this a
while back, that was motivated by the fact that interferences in the
network will turn an initially conformant traffic stream into a
non-conformant one.  As a result and as with GS, it is highly undesirable
to do policing within the network.  Instead, *some amount* of tolerance 
needs to be put in, e.g., through reshaping, and I believe that this
is expressed in the following paragraphs from the CL specs:

   When resources are available, network elements at points within the
   interior of the network SHOULD be prepared to accommodate packet
   bursts somewhat larger than the actual TSpec. This requirement
   derives from the traffic distortion effect described in Section 4. As
   described there, it may be met either through explicit means or
   statistical multiplexing of shared buffering resources.

   When handling such traffic, it is permissible to allow some delaying
   of a packet if that delay would allow it to pass the policing
   function.  (In other words, to reshape the traffic). 

The main difference between GS and CL is that GS gives you a precise
test to detect non-conformance (through the buffer test, although this
gives you only a necessary condition, i.e., if you don't pass it you are
non-conformant but you need not be conformant if you pass it, but that's
ok since GS is focused on the worst case anyway), while with CL there
is more of an *engineering* decision needed.

Roch

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Wed, 18 Jun 1997 21:58:44 -0400 (EDT)

> is expressed in the following paragraphs from the CL specs:

Roch,

Reshaping is of course a solution, although an expensive one if it
is required for every flow at every node. 

However, if a router is unaware of the buffer sizes of up-stream nodes, 
and no re-shaping has been done upstream, I can not see how the 
*amount* of tolerance can be specified and engineered. Interference
in up-stream nodes can be arbitrarly large when large aggregations
have been made, or proprietary scheduling mechanisms have been
used.

Don't we need some estimate of the effective bandwidth of the flow 
as seen by donwstream nodes and after several hops ?

Dimitrios

---

From: Roch Guerin <[email-masked]>
Date: Fri, 20 Jun 97 19:17:37 -0400

>as seen by donwstream nodes and after several hops ?

Dimitrios,

You certainly cannot give hard guarantees such as those of GS, but
you still can do a lot to ensure adequate performance.  For example,
with a WFQ like scheduler I can give the flow a rate guarantee and
also allocate some (dedicated) buffering plus access to a shared
buffer pool with some limitations on how much each flow can grab 
from the shared pool.  This wont avoid real bad cases, where you
have schedulers that do a lot of lumping, but you can still go a
long way.

In any case, the main point I was trying to make is that you should
not do hard policing within the network.  Instead, you need to have
mechanisms to ensure that excess traffic from one flow does not 
degrade overall performance, but without assuming that anything
that does not conform to the TSpec is excess.

Roch

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Sat, 21 Jun 1997 09:18:36 -0400 (EDT)

Roch,

> have schedulers that do a lot of lumping, but you can still go a

Hard guarantees is definately not the goal of a Controller Load 
service type. My feeling, however, is that the known analytical
results are inadequate to make an efficient use of the Controlled
Load traffic class. 

1. If we assume a per-flow scheduler how can one specify the
   necessary bandwidth to assure adequate sharing?
   If things like the TSpec leaky bucket rate are used, then no
   overbooking can be made, and the statistical multiplexing 
   gain will be low. From the network node resources point of view this 
   is the same as GS. If measurements are used, it is not clear yet
   how one can capture variance of traffic with long tails
   (if such tails exist ?) And what if measurements are wrong ?
   What if we understimated or overestimated the effective bandwidth
   and result in weights that are not accurate? The whole WFQ model
   is based on the assumption that weights are accurate. And,
   anyway how can static weights capture the variability of traffic
   over time ?
2. Even if we assume that 1 can be done, there is still no theory
   available for estimating effective bandwidth for anything else
   than a FIFO scheduler. The state-dependency of most per-flow
   schedulers make this a very difficult problem.
3. For me it is still an open question, whether the information
   captured in TSpec (average,peak, mx burst)  is saficient
   to allow network nodes to make effective admission control decisions
   that will ensure good support of Controlled Load and efficient
   use of resources. But I guess, we have to survive with that .. :)
> that does not conform to the TSpec is excess.

I have to totally agree with that. It is my feeling however, that 
we have a long way to go before we can *efficiently* use a Controlled
Load traffic class.

Dimitrios

---

From: Roch Guerin <[email-masked]>
Date: Fri, 20 Jun 97 19:17:37 -0400

Dimitrios,

Roch

> This goes along with the concepts about adaptive
> compression presented in Huitema's books, "Routing In
> The Internet" and "IPv6 - The New Internet Protocol".
> 
> The only difference to _NOT_ reserving bandwidth at
> all would be that the application would KNOW how much
> bandwidth is currently availabe; the router could simply
> cancel the reservation so that the app would have to
> try again.
> 
> The benefits ? The app could ASK the user if he'd like
> to continue with less bandwidth and then make a well
> defined transision to less octaves and voices in our
> musical example, still keeping guaranteed latency.
> 
> Now some of you might say this would probably lead to
> streams that would be interrupted or just refused all
> the time. Well, first, I'd rather live with _VERY_ little
> reserved bandwidth (AND latency !) than with none at
> all. When the first synthesizers came out, nobody
> worried about the fact they were monophonic. It was
> still better than having nothing at all.
> 
> Second, due to its adaptive nature, as the overall
> net bandwidth increases, so does the allowed reservation !!!!
> 
> I'm serious, why not give it a try ?
> 
> greetings,
> Michael

--
Andrew T. Campbell  
http://comet.ctr.columbia.edu/~campbell
Wireless Media Systems Project 
http://comet.ct
.columbia.edu/wireless

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Sat, 21 Jun 1997 09:18:36 -0400 (EDT)

Roch,

Dimitrios

---

From: Roch Guerin <[email-masked]>
Date: Fri, 20 Jun 97 19:17:37 -0400

Dimitrios,

Roch

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Sat, 21 Jun 1997 09:18:36 -0400 (EDT)

Roch,

Dimitrios

---

From: Roch Guerin <[email-masked]>
Date: Fri, 20 Jun 97 19:17:37 -0400

Dimitrios,

Roch