Subject: Forwarding misplaced message thread to int-serv

From: braden (Bob Braden)
Date: Mon, 23 May 1994 14:46:20 -0700

There has been a recent thread on the RSVP mailing list that really
belongs on this list.  My attempt to get it moved only resulted in
its being lost!  So, this time it should be MOVED.  In the process, I
made a pass with an editor trying to digest the thread a little; not
sure I did any good, but here it is.  There are a number of somewhat
distinct issues raised here, all of direct relevance to the int-serv
WG (I think).

Bob Braden

_____________________________________________________________________

Jon Crowcroft asked:

  *> 
  *> actually, i'm interested in what
  *> the int-serv & rsvp architecture says happens if you make an RSVP
  *> across multiple hops that implement multiple scheduling algorithms
  *> 
  *> (for isntance, JW's CSZ code and Van & our CBQ code)
  *> 
  *> what precisely is the notion of conformance to a flow spec?
  *> 
  *>  jon
  *> 

Amit Gupta replied, from the viewpoint of work done in the
Berkeley Tenet group:

  *> 
  *>  It should work without any problems; the information exchange (between
  *> different nodes) should be independent of the scheduling discipline; for
  *> example (considering only deterministic and statistically guaranteed
  *> services), the "downstream" information is the traffic spec, and the
  *> "remaining" performance spec i.e. delay & jitter bounds, along with the
  *> probability that each bound would be met, etc etc. 
  *> 
  *>  This is how things work in the new Tenet scheme; they should be the same
  *> with RSVP and "int-serv" (as per my admittedly limited understanding of 
  *> the ideas and the design philosophy).
  *> 
  *>  -amit
  *> 
  *>  ps: In principle, we can have multiple scheduling disciplines at a 
  *> single node!!
  *> 

and further, he wrote:

  *>  The information exchanged should be a function of the "establishment"/
  *> "call set-up" approach (and independent of the scheduling discipline);
  *> clearly, some scheduling disciplines may not be able to provide support
  *> for all the services, but wherever a service can be supported by multiple
  *> scheduling disciplines, it should be possible for us to handle multiple
  *> scheduling disciplines.
  *> 
  *>  In an inter-networking environment, we cannot (and should not) mandate that 
  *> everyone use our scheduling discipline; all that we can ask for is that the 
  *> admission control regime provide an interface that
  *> 
  *>  a) accepts the flow-spec (pref accept a variety of flow-specs)
  *>  b) accept/reject the new request, and
  *>  c) if it accepts the new request, provide information that the call set-up
  *> regime requires (e.g. bounds on delay/jitter, failure probabilities, error 
  *> rates etc for guaranteed performance determinstic and statistical service;
  *> "packet priority level" for predictive service etc)
  *> 
  *> The important obervation is that the information is independent of the
  *> scheduling discipline (FIFO, EDD, J-EDD, D-EDD, RCSP, HRR etc) and is a
  *> function of the QoS parameters that service provides; we have to avoid
  *> linking a service QoS type (deterministic vs. guaranteed stat vs predictive 
  *> vs best effort etc)  with a particular scheduling discipline (though the
  *> scheduling discipline does limit the QoS type offered).
  *> 
...
  *> 
  *>  In Tenet scheme, in general, we do jitter control on a hop-by-hop basis, 
  *> with components that do no jitter control simply saying that their 
  *> jitter control is zero. The end nodes finish up any unresolved jitter
  *> (that intermediate nodes could/would not do).
  *>  

and later...

  *> 
  *> The information exchange should be independent of the scheduling discipline,
  *> *as long as* the scheduling discipline supports the required service type.
  *> 
  *>  IMHO we cannot claim complete orthogonality between the scheduling 
  *> disciplines and the service type. All scheduling systems may not support
  *> all service types e.g., pure FIFO cannot support guaranteed services. 
  *> 
  *>  What we can do, however, is that if two (or more) scheduling disciplines
  *> provide support for the same service type, then we can do the call set-up
  *> (and refreshes, in case of RSVP) where different nodes have different 
  *> scheduling disciplines. I described, in a previous email, as to how this
  *> is done in the Tenet protocol suite. 

Don Hoffman of Sun got into it:

  *> 
  *> 
  *> The flow spec gives you a common language with which to talk to the
  *> admission control and scheduling code. Conformance to a flow spec implies
  *> the ability to map from the common language to the model offered by the local
  *> scheduling discipline.
  *> 
  *> We are currently trying to understand how we might map the flow spec in the
  *> RSVP spec to the CBQ model (Using some of the really excellent and high
  *> quality code provided to us by the CBQ folks:-)).  Its not been completely
  *> obvious to me (mostly due to my current poor understanding of CBQ).   What
  *> happens if we cannot come up with a perfect mapping.  Does this mean that the
  *> flow spec is not general enough and needs to be improved, or that our
  *> scheduling discipline is not sufficiently conformant (BTW, I am not yet
  *> claiming either is the case).  Basically, one of the measures of conformance
  *> is a claim that we are "close" within some bounds.
  *> 
  *> How close is close enough?  How do we measure "close".  
  *> 
  *> For "guaranteed" or statistical types of reservation (I think the types Amit
  *> speaks of), this may be conceptually straightforward (although in practice
  *> difficult -- e.g., have you ever tried to write a performance spec that has
  *> legal standing).
  *> 
  *> But what about predictive reservations (ala CSZ'92 etc.)?  The whole idea is
  *> that we do not make firm a priori commitments.  Do we refund the cost of the
  *> router for the periods where we are outside the tolerance of the conformance
  *> specification?  On the face this might sound a bit silly, but many think some
  *> sort of economic model is needed to keep the service provider (and service
  *> implementor) honest.  The models could be either explicit, in that I only pay
  *> for the times when I get conformant service, or implicit, where I pay less up
  *> front but agree to live with out-of-conformance service.    We then don't
  *> need to decide a priori if my service or implementation of the flow spec is
  *> conformant or not.  I (as an implementor) am motivated to get close so I can
  *> charge more money (or not if I want to sell at K-Mart prices).  The downside
  *> is that we don't get to write some unambiguous statement in an RFC or
  *> Internet Standard somewhere.  (BTW, I was a bit sloppy above in that
  *> predicive delivery of QoS is different from "predictive" conformance to a
  *> specification, but the parallels should be obvious).
  *> 
  *> Don
  *> 

Amit replied:

  *> 
  *>  I agree that these problems exist; all I was saying was that heterogeneity
  *> in scheduling disciplines on nodes along the route of a call is a non-issue;
  *> e.g. in a network with nodes A and B, if we can accept calls with a 
  *> particular flow-spec under the following two alternative conditions
  *> 
  *>  1. scheduling discipline X at node A and node B
  *>  2. scheduling discipline Y at node A and node B
  *> 
  *>  then we should be able to work with calls with the same flow-spec under the
  *> condition that scheduling disciplines at A and B are X and Y respectively. It
  *> is an entirely different issue whether a particular scheduling discipline (and 
  *> the related admission control regime) is compatible with a particular flow-spec.
  *> 
  *>  :For "guaranteed" or statistical types of reservation (I think the types Amit
  *>  :speaks of), this may be conceptually straightforward (although in practice
  *>  :difficult -- e.g., have you ever tried to write a performance spec that has
  *>  :legal standing).
  *> 
  *>  I agree; guaarnteed (deterministic as well as statistically guaranteed) 
  *> performance is conceptually simpler (and that is why I believe that the 
  *> fundamentals are easier to study in that framework).
  *> 
  *> I have never written a performance spec with legal standing but I do 
  *> understand that the phone companies do provide guarantees with some legal
  *> standing (e.g. downtime < 2hrs in 20 years with prob > 0.999 or stuff
  *> like that); there is considerable work in statistically determining, with
  *> a certain degree of confidence, whether statistical guarantees are met
  *> (Dinesh Verma's Ph.D. thesis provides a very good description).
  *> 
  *>  Writing guarantees (and disclaimers) is beyond the scope of our research, 
  *> IMHO, while designing techniques that can provide guarantees is within
  *> the scope of research in realtime communication in computer networks.
  *> 
  *>  -amit

Amit also wrote:

  *> 
  *> Don wrote:
  *>   
  *> 
  *>  * A question follows from this:  Do we have different flow specs for the
  *>  * different scheduling disciplines and then use the flow spec type to select
  *>  * the discipline against which to reserve?
  *> 
  *> I would say that (at the first cut) have a flow-spec for each service type,
  *> but use the same flow spec for all scheduling disciplines that support a
  *> particular service type. Then, define a single flow-spec that is flexible 
  *> enough (parameterized?) to be useful for a variety of service types. 
  *> 
  *>  Jon wrote:
  *>  
  *>  * i could be given a flow spec for delay, throughput, error,
  *>  * mean+variance, or mean+peak+burst or whatever the RSVP people devise

Jon, Jon, you should know better than that... the "RSVP people" are devising
RSVP, not flowspecs.  Maybe you mean "the ISPS people", or the "CSZ people"?

  *>  * i can turn that into several different things
  *>  * CSZ defines some of these, but not all (e.g. delay first, rather than
  *>  * throughput first...)
  *> 
  *>  The overall scheme (service type/establishment approach) determines
  *> the information that the admission control routines output (e.g. this
  *> could be a priority level for predictive service, mathematically provable
  *> bounds on delay, jitter etc for deterministic service, probability of
  *> not meeting these bounds for statistical service etc), but all packet
  *> schedulers, which support a particular service type, should output the 
  *> same information. 
  *> 
  *> Hope this helps
  *> 
  *> thanks
  *> 
  *>  -amit
  *> 

I tried to move the conversation to the int-serv mailing list, but
I only succeeded in getting it off the RSVP list... !

Noel Chiappa reviewed Amit's viewpoint, and raised new questions:

  *> 
  *> If I understand what you are saying here, you are saying that we need to
  *> define a common set of semantics for user requests to resource allocation
  *> devices; that semantics (along with some syntax) turns into a protocol (RSVP)
  *> used to talk to all the resource allocation devices.
  *> 
  *> Those devices would then map from those requests, to whatever local knobs they
  *> have to control the traffic, see if they can provide what's requested (and set
  *> it up, if so), and return an accept/reject to the requestor (logically, since
  *> the accept may actually happen by passing the request on to the next hop).
  *> 
  *> Is this right?
  *> 
  *> 
...

  *> 
  *>     In Tenet scheme, in general, we do jitter control on a hop-by-hop basis, 
  *>     with components that do no jitter control simply saying that their 
  *>     jitter control is zero. The end nodes finish up any unresolved jitter
  *>     (that intermediate nodes could/would not do).
  *>  
  *> This I didn't quite get; let me tell you what I think I understand (since I'm
  *> new to this resource stuff), and you tell me where I went wrong.
  *> 
  *> I think what you were saying here is that for delay variance, you can smooth
  *> it out at the last hop (provided you are within your overall delay budget) by
  *> buffering it up a bit. Is this right?
  *> 
  *> However, in more general terms of thigns that have to be done at setup time,
  *> if you have a budget for something like delay, I can see how you can check to
  *> see whether the cumulative budget has been used up, and do that in either a
  *> distributed or localized way. However, if you run out on a given path, don't
  *> you have to interact with the routing and try and find a path which doesn't
  *> use the budget? I don't see any easy way to do that in a distributed way.
  *> 
...

  *> 
  *>     It is an entirely different issue whether a particular scheduling
  *>     discipline (and the related admission control regime) is compatible with a
  *>     particular flow-spec.
  *> 
  *> This makes me think of something else; how deep is the linkage between the
  *> scheduling mechanism itself (in terms of what capabilities it has), and the
  *> semantics of the request language. I.e., can we really provide semantics for
  *> the request language which encompass all useful scheduling algorithms, or do
  *> we have to have knowledge of the idiosyncratic capabilities of the algorithm
  *> to define the request language?
  *> 
  *> The reason I ask is that in the policy/QoS routing field (my expertise), we
  *> decided that user requirements were so arcane that we couldn't define a
  *> semantics to cover them all. For the hard cases, we reverse the process, so
  *> that we give the user a map, with the attributes of the links (in some agreed
  *> upon notation) marked on it, and let them figure out the path that meets
  *> their bizarre, unstateable, requirements.
  *> 

Jon Crowcroft came back with a purported counter-example to Amit's
hypothesis:

  *>  
  *> here is a realy simple example to show what i am saying
  *> 
  *> i do a reservation for a flow with a spec
  *> delay bound = 1 sec, otherwise discard
  *> 
  *> the path is 10 hops
  *> 
  *> 1 scheduling algorithm setes a deadline in every hop to 100msecs
  *> 
  *> a different scheduling algorithm saves it up and sets a deadline of
  *> 1 sec in the 10th hop only.
  *> 
  *> youi cannot put a service together out of these two systems, as it
  *> would possibly lose 100% of packets one way round, and waste
  *> scheudlign effort in 9 hops the other way round...
  *> 
  *>  jon
  *> 

Zheng Wang (UCL) entered the conversation:

  *> 
  *> Some scheduling disciplines may not work if you mix them
  *> with other scheduling disciplines. For example, GPS or
  *> WFQ provides a delay bound only when the input traffic conforms
  *> to a leaky bucket, and all nodes on the path use the same
  *> algorithm. I think the reason for this is that a WFQ node
  *> can maintain the same arrival constraint for the following
  *> WFQ nodes.
  *> 
  *> Cheers
  *> Zheng

(At this point, I include recent messages in toto.)

----- Begin Included Message -----

>From [email-masked] Mon May 23 09:29:17 1994
To: Zheng Wang <[email-masked]>
Cc: Amit Gupta <[email-masked]>, [email-masked],
        [email-masked], [email-masked], [email-masked]
Subject: Re: Comments on RSVP, etc. (flow spec conformance) 
In-Reply-To: Your message of Thu, 19 May 94 12:08:55 +0100.
             <[email-masked]> 
From: Craig Partridge <[email-masked]>
Date: Mon, 23 May 94 09:08:04 -0700
Sender: [email-masked]
Content-Length: 1570
X-Lines: 37

     > What we can do, however, is that if two (or more) scheduling disciplines
     >provide support for the same service type, then we can do the call set-up
     >(and refreshes, in case of RSVP) where different nodes have different
     >scheduling disciplines. I described, in a previous email, as to how this
     >is done in the Tenet protocol suite.

    Some scheduling disciplines may not work if you mix them
    with other scheduling disciplines. For example, GPS or
    WFQ provides a delay bound only when the input traffic conforms
    to a leaky bucket, and all nodes on the path use the same
    algorithm. I think the reason for this is that a WFQ node
    can maintain the same arrival constraint for the following
    WFQ nodes.

Zheng:
    
    I wouldn't describe WFQ/GPS in such a limiting way.

    In brief, what Parekh's thesis says is if you feed the worst case
token bucket traffic into a WFQ configured to provide the minimum acceptable
bandwidth to each user your worst case queueing delay is X where X is
simply the summation of the WFQ per-hop delays plus the queueing "bulge"
that is caused by dumping all burst data in excess of the WFQ rate.

    It seems to me that one could do a similar analysis for just about
any admission process which can be characterized by a mean
bandwidth and a maximum amount sent in excess of the mean sent over an
arbitrary time T.  In essence, the first term of Parekh's thesis is
simply:

    (Max(T) - Mean(T))/Mean(T)

and that's the only term strongly affected by the admission process.

Craig

----- End Included Message -----

----- Begin Included Message -----

>From [email-masked] Mon May 23 09:26:32 1994
To: Amit Gupta <[email-masked]>
Cc: [email-masked], [email-masked], [email-masked]
Subject: Re: Comments on RSVP, etc. (flow spec conformance)
In-Reply-To: Your message of "Fri, 20 May 94 10:25:02 PDT." <[email-masked]>
Date: Mon, 23 May 94 17:16:41 +0100
From: Zheng Wang <[email-masked]>
Content-Length: 1070
X-Lines: 24

 >A) With the same scheduling discipline, we can have many different
 >admission control routines (which depend on the analysis and
 >policy issues). In particular, I know that admission control
 >routines for WFQ can be written where the analysis does not depend
 >on having WFQ at other nodes in the network.

I think admission control is also tied to the scheduling
discipline. For a given flow spec, some scheduling discipline
may require peak-rate reservation but some may require just
average-rate.

 >For WFQ, we can add an extra "jitter-controlling" component to ensure
 >that the traffic always obeys the leaky bucket (or any other specification
 >of traffic constraint); even without this "jitter-control", we can
 >obtain end-to-end bounds, though we may not accept as many connections.

I dont quite understand what you are suggesting here. It is possible
to have different scheduling disciplines in one network but the
performance is likely to be affected (i.e. we may have to reserve
peak-rate instead of average-rate just to make it work).

Cheers
Zheng

----- End Included Message -----

----- Begin Included Message -----

>From [email-masked] Mon May 23 10:28:26 1994
To: Zheng Wang <[email-masked]>
Cc: [email-masked], [email-masked], [email-masked]
Subject: Re: Comments on RSVP, etc. (flow spec conformance) 
In-Reply-To: Your message of "Mon, 23 May 1994 17:16:41 BST."
             <[email-masked]> 
Date: Mon, 23 May 1994 10:27:22 PDT
From: "Amit Gupta" <[email-masked]>
Content-Length: 2143
X-Lines: 49

 Hi Zheng 
 
 :I think admission control is also tied to the scheduling
 :discipline. For a given flow spec, some scheduling discipline
 :may require peak-rate reservation but some may require just
 :average-rate.

Peak-rate vs average rate depends on the admission control analysis,
and not on the scheduling discipline (in general). For example, look
at Hui Zhang's thesis for a peak-rate reservation based analysis and an
average-rate based analysis for RCSP (which is sorta like multiple 
priority FIFO, with rate control).

 There are some disciplines where average-rate based analysis may be 
"very difficult" and not easy to transform into usable admission
control tests, but that is, IMHO, a different issue. 

 Admission control analysis depends on the scheduling discipline 
*at that node*. We can perform the analysis so that it depends on
having the same scheduling disciplines on all nodes, but in the
analyses that I have seen, the dependency can be factored in as
an extra parameter (e.g. the "outgoing jitter", as below, and as 
Craig suggested in his email). 

 IMHO, it is undesirable that admission control at a node depend on the 
constraint that the same scheduling discipline be followed at other nodes
in the network.
 
 : >For WFQ, we can add an extra "jitter-controlling" component to ensure
 : >that the traffic always obeys the leaky bucket (or any other specification
 : >of traffic constraint); even without this "jitter-control", we can
 : >obtain end-to-end bounds, though we may not accept as many connections.
 
 :I dont quite understand what you are suggesting here. It is possible
 :to have different scheduling disciplines in one network but the
 :performance is likely to be affected (i.e. we may have to reserve
 :peak-rate instead of average-rate just to make it work).

 Please refer to the comment above (about avg rate vs peak rate). Among
the scheduling disciplines and admission control analyses that I am aware 
of, including FIFO, WFQ, EDD (and its variants), RCSP etc, there is no
"performance hit" in the analysis with heterogeneous scheduling disciplines
in the network.  

 thanks

 -amit

----- End Included Message -----