Subject: Policing issues

From: [email-masked] (Bruce Davie)
Date: Thu, 11 May 1995 13:23:48 -0400

This started out as a nice, succint message but grew into something
long and rambling. The patience-challenged may jump to the summary at
the end.

Having read the minutes of the rsvp and int-serv meetings at Danvers
as well as some of the mailing list discussion, I wanted to raise a
few points about the issue of policing. Some of this will be a
restatement of things said before, but I wanted to get the relevant
details all in one place. Bob will be sure to tell me if this doesn't
belong on rsvp, but I think rsvp needs to be aware of the ways that
policing is likely to be enforced.

First, a definition.  John Krawczyk correctly observed that we need a
precise definition of policing, and defined it correctly (in my
opinion.) He narrowed it down from some of the earlier discussion, as
follows:

>From: [email-masked] (John Krawczyk)
>To: [email-masked] (Fred Baker)
>Cc: [email-masked], [email-masked]
>Subject: Re: question on traffic policing
>
[...]
>Perhaps we need a precise definition of policing.  I always thought it
>meant "monitoring the rate of arrival of packets on a flow to ensure
>that it does not exceed its Tspec (b,r).  Packets that exceed their
>Tspec are dealt with as defined in the service definition."
>

The next question is, what's the correct way to deal with packets that
exceed their Tspec, which we might describe as non-conforming
packets. Dropping them is certainly the most obvious solution. One
could argue that it would be better to mark them as non-conforming and
only drop them in the event that resources are scarce at some point on
the path they travel. After all, if resources aren't scare,
non-conforming packets do no harm. However, I'm not sure how the
implementation of such a scheme would work out in practice. A third
alternative is to delay non-conforming packets until the become
conforming, although this is only possible if the long term average
rate is not greater than that in the Tspec. We can call these three
options dropping, marking, and shaping; there may be other
options. More on shaping later.

The issue I'm really concerned about is where we enforce policing,
independent of whether we drop non-conforming packets or not. Several
documents have talked about enforcing policing at the entry to the
network and at all merge points. I will assert that policing at merge
points is the wrong thing to do (although I will slightly relax this
assertion later). As a sender, I can (and should) take responsibility
for putting my packets into the network in such a way that they
conform to my Tspec, but I have no control over how the routers along
the path will affect the characteristics of the traffic. Even with
FIFO queueing, it's easy to show that my nice, smooth, conformant
traffic can get burstier and thus non-conformant as it traverses the
network. My intuition is that this could be even worse if my packets
are encountering non-FIFO queues. (As an aside, the
non-work-conserving `stop-and-go' queue does ensure that my traffic
remains conformant, but it's the only scheme that I know of with that
property.)

I think I made the above point at the int-serv meeting in Danvers, and
the minutes record the following:

>- Traffic policing and merging. The service as currently defined calls
>for traffic policing (not shaping) at entrance to the network and at
>traffic flow merge points. The question of handling extra burstiness
>caused by merging was raised. The two options are to add a traffic
>shaping function at this point or to accept the increased burstiness,
>which includes ensuring that the function which calculates merged
>reservation traffic specifications takes it into account. This remains
>a matter for further research.

Interestingly, this text distinguishes policing and shaping. As I
suggested above, and in keeping with Krawczyk's definition, shaping
could in fact be a viable alternative way to perform policing. I would
even say that it is a function that, if performed at merge points,
might be acceptable, since it re-smooths (rather than dropping) the
traffic that was made un-smooth through no fault of mine. As long as I
still get the service that I asked for, I'll be happy.

Note that if we're using WFQ to provide guaranteed service, there is
no need to smooth or `take into account' the increased
burstiness. Parekh's result assures us that we'll get the right
performance as long as the traffic entering the network conforms to
the Tspec *when it enters*. There's no need for some additional
mechanism to preserve conformance at every point. (In fact, I wonder
if the presence of smoothing devices would invalidate Parekh's
result.) 

What about for other services? Here I have to hand wave a
bit. I did a little bit of simulation a few years back that showed a
tendency for traffic to get less bursty *on average* as it passes
through queues. This was far from conclusive, but it did help to back
up my intuition that this would happen. Unfortunately, I assumed FIFO
queues, so I'm not sure how far we could extend the results. However,
given the fact that token buckets are a lousy description of real
traffic anyway, I'm not at all convinced that we need to force traffic
to conform to some token bucket spec in the middle of the network to
make our predictive or controlled delay services work. I think we'll
be living by engineering approximations like `the last time I allowed
someone with this Tspec to join this class, it blew away the
performance, so I'm just going to say no this time.' We'll have such a
big statistical game going on that one more bit of uncertainty (caused
by allowing non-conformance in the middle of the network) won't be
noticeable. In case you haven't noticed, most of this paragraph is
total shooting-from-the-hip.

Summary:
- policing = treatment of packets that don't conform to the Tspec
- various treatments (drop, mark, shape) of non-conforming traffic are
  possible
- any form of policing at merge points, except maybe shaping, is
  unacceptable
- even shaping at merge points is of dubious value

Bruce Davie
Bellcore

---

From: John Wroclawski <[email-masked]>
Date: Thu, 11 May 1995 17:00:49 -0400

From: [email-masked] (Bruce Davie)

   Having read the minutes of the rsvp and int-serv meetings at Danvers
   as well as some of the mailing list discussion, I wanted to raise a
   few points about the issue of policing.

   the path they travel. 

This is a per-service decision. For example, a service intended for
use with rate-adaptive applications will likely use the marking
approach you describe. For controlled-delay, dropping is likely to be
the best choice.

   I will assert that policing at merge points is the wrong thing to
   do 

The issue is that the level of resources reserved above the merge point
may be less than the sum of the resources reserved below the merge
point. This is the essence of a shared reservation. Hence, you have to
police at the merge points.

The burst aggregation effect you describe leads to the requirement
that the policing filter at a merge point be larger than a simple
sum of the merged filters for best results. This point is made more
clearly in the next draft of the service specification template. The
precise definition of a policing function, like the precise choice of
a scheduling algorithm, is something we think best left to the
implementor.

Notice that there is an implication here that policing at -additional-
points (neither entry nor merge points) is a problem because of the
potentially growing burstiness, unless you adjust the policing
function at those points also. 

There're a bunch of open questions. Shaping adds delay.  There are
situations where you'd rather have 99% of the packets earlier than
99.5% of them later. On the other hand you can argue that the same
effect could be achieved purely by adjusting the playback point at the
end-node. More interestingly, there are claims that shaping allows
some forms of measurement-based admission control to work better (give
higher link loadings, etc). Personally I think this may be an
appropriate place for a vendor tradeoff, but I'm not sure I understand
the end-to-end effects of allowing a flexible specification clearly.

	-john

---

From: Steve Jackowski <[email-masked]>
Date: Thu, 11 May 1995 14:16:08 -0900 (PDT)

Bruce,

You bring up some interesting points.  I actually like the 
THOUGHT of the network doing no policing: doing shaping 
instead.  Unfortunately, as a host implementor, and one 
who's using my existing ST-2 policing mechanisms, I allow 
a stream to exceed its reservation during bursts  (the 
RFC 1190 flowspec has a burst parameter).  I police if a 
stream interferes with other streams or exceeds the total 
bandwidth allocated to reserved traffic or exceed its 
burst allocation.  

I don't think the router that has multiple streams can 
be guaranteed to handle multiple bursts and simply shape.  
Packets must be dropped if there is any chance that the 
guaranteed bandwidth is in jeopardy as far as the local 
router is concerned.

Steve

---

From: Jon Crowcroft <[email-masked]>
Date: Fri, 12 May 95 09:00:55 +0100

shaping and policing

Policing is the act of monitoring and marking for action flows
that exceed their requested resources. The action is separately
defined....for example, you can drop cells  in an input queue, or an
output queue, or just mark as lower priority so they may get dropped
in a downstream switch without the need for further policing....

the confusion with shaping only occurs when you define whether the
policing action is to drop, or to allow packets in a flow
to go out of spec w.r.t delay distribution 

if you have agreed to some particular lkeaky bucket parameters (or any
form of non CBR service), and you don't drop packets, you are
increasing the statistical chance that this, or some other flow, will
have a delay variation higher than speceified....

a provider does this because theu know something about their switches
(oops, sorry, routers) and links (like actually, they have excesss
capacity or something...)

you can of course choose to do somethign to OTHER peopels traffic
because this traffic is out of spec....this would be part of some
policy, and i would refer you to sally floyds forthcoming paper in ToN
on CBQ for ideas on this....

if you start getting into the art of shaping a set of flows because
of a priority treatment that gives less stringently policed traffic
the rights to disrupt other flows, you get into dangerously complex
territory in terms of tehory - for example all the work in Parekh's
GPS and PGPS ideas avoids this....

but you will probbly get higher utilisation if you do it....

intuitively, an flow that is bursting higher or longer than its RSpec
can borrow from other flows that have a higher delay variation
tolerance and are currently below mean rate, or even at mean rate so
long as the set of all the flows at a class with a higher delay
variation is below mean for your dimension of switch/link....

the aggregation _ought_ to mean you can get away with this, provided
that "self-similarity" in a subsequent burstr from all the below spec
class doesn't hit you.....which it might....so someone needs to
combine the ideas from CBQ and self-similairty to re-workout the 
equations people used to come up with for "Available Bandwidthj"
calculations that used to be used to decide if a call (oops sorry,
rsvp request) can be admitted.....

 jon

---

From: [email-masked] (Bruce Davie)
Date: Fri, 12 May 1995 10:53:59 -0400

John,
 It actually looks like we agree on most things:

   Date: Thu, 11 May 1995 17:00:49 -0400
   From: John Wroclawski <[email-masked]>
   CC: [email-masked], [email-masked]

Absolutely.

I agree with everything up to the `Hence'. It seems to me that if I
policed all the flows at the edges, then I don't necessarily need to
police them when they merge. Could you elaborate on the logic
underlying your last statement? I view policing as an action that I
take on a flow that has not stuck to its part of the bargain,
i.e. exceeded its Tspec. Since a source only controls what goes in at
the edge, it seems unfair to police elsewhere. My algorithms for
providing QOS had better be able to live with that.

   [...more stuff from John that I agree with...]

Yes, shaping does add delay, which is a reason why I'm still opposed
to doing in other than at the edge. However, if an implementor uses
shaping to make his algorithm work, and I still get the service I
contracted for, then all power to him. Given all the open questions, I
think that implementing something reasonable and playing with it is a
good way to go. 

Also, given our level of uncertainty, I think we can answer Bob
Braden's question that got me started on this:

   From: [email-masked]
   Date: Mon, 10 Apr 1995 15:43:19 -0700
   Posted-Date: Mon, 10 Apr 1995 15:43:19 -0700
   To: [email-masked]
   Subject: question on traffic policing
   
   Hi.  All the current draft service specs say about Traffic
   Specification and Policing:
   
      "Policing is done at the edge of the network and at all source merge
      points."
   
   Would you expect that any service that does policing will do it this
   way?  More specifically, RSVP currently defines a single flag to the
   kernel "policing is needed", and turns it on for either the edge of
   the network or a source merge point.  Is one flag enough, or should
   the two conditions be distinguished in the interface?

A single flag that says `policing is needed' is inadequate, because
there may be situations where we police at the edge only, or
situations where we police at edge and merge points.

Bruce

---

From: [email-masked] (Dilip Kandlur)
Date: Fri, 12 May 95 11:27:51 -0500

Does the controlled delay service attempt to control jitter in any
form?  If not, I don't see why dropping packets is the best choice.

-- Dilip.

---

From: [email-masked] (Bruce Davie)
Date: Fri, 12 May 1995 11:25:49 -0400

Date: Thu, 11 May 1995 14:16:08 -0900 (PDT)
   From: Steve Jackowski <[email-masked]>
   Cc: [email-masked], [email-masked]
  
   Bruce,

   RFC 1190 flowspec has a burst parameter). 

   Steve

Steve,
 The whole point of a token-bucket-style Tspec is that it includes a
specification of potential burstiness. So I should never exceed my
Tspec - I can exceed my average bandwidth, but not the burstiness
specified by the token bucket. If I do, I deserve to be punished
(i.e. policed). 

Bruce