Subject: template doc

From: Scott Shenker <[email-masked]>
Date: Thu, 15 Dec 1994 16:03:41 PST

This note is a follow-up to our WG meeting in San Jose.  It contains a
slightly revised version of the services template I described in the
Wednesday meeting.  For each constituent service that we adopt as part
of the service model, we must describe what a router (more generally, a
network element) must do in order to support this service.  The purpose
of this template is to provide a common format and context for these
descriptions.  Following the description of the template, I have
appended three example templates.  Their purpose is to illustrate the
use of this template, rather than advocate specific services.

I invite your feedback on this template.  I hope the WG can quickly
come to closure on the templates and soon start actually debating the
merits of individual service proposals.

This note assumes some context which, if you were not at the WG
meetings in San Jose, you may not have.  For those of you fortunate
enough to have had better things to do, I apologize in advance if the
note is rather cryptic and inaccessible.  Some of the WG presentation
slides might help, though they are somewhat out of date since I have
revised the content in response to feedback I received at the meeting.
The slides I presented to the RSVP WG on one-pass-with-advertising, and
the slides I presented to the int-serv WG, can be found on:

parcftp.xerox.com:/pub/net-research/opwa.ps

parcftp.xerox.com:/pub/net-research/rrdoc.ps

--Scott

----------------------------------------------------------------------
Scott Shenker				Office: 415-812-4840
Xerox Palo Alto Research Center		FAX: (415) 812-4471
3333 Coyote Hill Road			Email: [email-masked]
Palo Alto, CA 94304-1314

----------------------------------------------------------------------

Network Element Service Specification Template

Each service incorporated into the service model must be described.
These service descriptions define what is required of a router (or,
more generally, a network element) to support a particular service.  I
propose the following multipart template for these service
descriptions.

0)  Motivation

This describes the intended usage of the service, for informational
purposes only.  

1)  Per-hop service

This is a description of how the packets are handled.  These are
requirements on, for example, maximal packet delays or bandwidth shares
given to a flow.  This also includes issues of feedback (as in explicit
congestion feedback, where bits in the header must be set or control
messages sent).  This portion of the service description is the most
central aspect (at least for most services) and will require the most
care in describing.

2)  Traffic specification and policing

For many kinds of network service, flows must provide a specification
of their traffic to the network before receiving service.  This portion
of the service description must both describe the nature of the traffic
specification (e.g., a token bucket filter) and the nature of policing
(e.g., policing could either drop or delay nonconforming packets) used
to enforce adherence to that traffic specification.  The description of
policing must also describe where that policing is done, which might
for example be at the edge of the network only, at every hop, or at all
merge points (considering the edge a merge point).  The abstractions
available to the service module from the set-up protocol about the
topology must include these notions of edge and merge points.

3)  Invocation

This describes the set of parameters handed to the service module to
invoke the service, and the mapping between those parameter values and
the resulting service.  For example, one might hand the router a delay
target and have the flow mapped into the bounded delay class with the
bound closest to that target.  This portion of the service description
will eventually describe the detailed layout of the bits in the service
invocation (but not in this draft).

The invocation for all the services listed so far can be broken into
two parts, the traffic descriptor (which we will call the TSpec) and
the service request descriptor (which we will call the RSpec).  For
instance, the TSpec might be token bucket filter parameters and the
RSpec the level of Predictive service desired.

4)  Ordering relations

The service module must be able to answer questions about the ordering
between different service requests.  This is used when merging service
requests from different receivers.  One service request is greater than
or equal to another if and only if both its TSpec and its RSpec are
greater than or equal.

This portion of the service description should also note any ordering
relationships with other services.  Of course, this portion of the
service description must be updated as new services are added to ensure
that the entries are complete and consistent.

5)  Advertisement

This is a description of how the services at the router are
characterized.  Note that this is not tied directly to the
one-pass-with-advertising proposal (OPWA) made to the RSVP WG (although
OPWA does use it); any service which wants its behavior characterized
must make these quantities available.  These characterizations are not
necessarily the same parameters that were used to invoke the service.
These advertisements are provided in response from a request (most
likely from either the set-up protocol or the routing protocol).  These
quantities can either be mandatory (any router offering this service
must be able to provide this characterization) or optional.  It is
assumed that these characterizations are composed along the path, and
part of the specification of an advertisement is the composition rule.
These composition rules should result in characterizations that are
independent of the order in which the routers are composed;
commutativity and associativity are sufficient but not necessary
conditions for this.

The issue of exactly how advertisements are used in a specific protocol
(e.g., RSVP) is another issue that is best described in the context
of that specific protocol.  However, the interface to the service module
should be flexible enough to allow the request of any and all advertised
numbers.

There are a number of optional generic advertisements that are
independent of the individual services.  These include (with the
composition rule described in parenthesis):

Latency: (composition rule: additive)

Hop number: (composition rule: add 1)

Bandwidth of link: (composition rule: MIN)

6)  The resulting end-to-end service

This is a description of the service that results if all routers along
the path offer the same service.  This is for informational purposes
only.  Its inclusion does not imply that the common case is that all
routers offer the same service end-to-end.  Rather, there are some
services, Guaranteed being the most notable example, where the resulting
delay bound is a highly nontrivial result of the concatenation of per-hop
services; the purpose of this entry in the template is so that such
nontrivial results are not left unrevealed to the reader of this document.

Appendix:  Examples

Some examples of of how templates are used may be useful.  I have
appended three service descriptions: level-of-effort predictive,
bounded delay predictive, and guaranteed service.  The point here is
not to advocate these services in particular, but to merely illustrate
the use of the template.  Once we agree on the template for services we
can move on to consideration of the particular services themselves.  I
should note that this template can also be used to describe
link-sharing and ASAP (best effort) service; in both cases the
description of the required per-hop service is a little daunting (for
best effort, the difficulty comes in specifying fairness) so I didn't
start with them.  However, in no way does the template assume, or
favor, services that require admission control or delay bounds; the
example services listed below are just the services for which the
template is the easiest to write right now.

Example 1:  Level-of-Effort Predictive Service:

0)  Motivation:  This service is designed for service adaptive and delay
adaptive applications; i.e., applications that are prepared to adapt to
changing delays and to change their service request if the current service
level is not adequate.  This service does not provide any quantified level
of assurance.  Instead, it merely promises to avoid overloads by turning
excess flows away; the criterion for determining overloads is unspecified.
Thus, while this service controls delay, it does not make any specific
assurances about delay.

1)  Per-hop Service:  The router must assure that the packet delays are
controlled.  No quantitative specification of the level of delay are
given, but the router is expected to use admission control to avoid
overload situations.  There are 5 (pick a number) different logical
levels of service, with different levels of delay control.

2)  Traffic specification and policing:  Traffic is described by a
token bucket filter (tbf).  Policing is done at the edge of the network
and at all source merge points.  Nonconforming packets are dropped.

3)  Invocation:  

TSpec: (token bucket depth, token bucket rate) 

RSpec: (target-delay) or (service-level)

The service module can map the target-delay into a service level with
any monotonic mapping.

4)  Ordering:  The TSpec's are ordered according to the usual tbf
ordering; both the token bucket depth and rate must be greater than or
equal in order for the TSpec to be greater than or equal.  The RSpec's
are ordered in the obvious fashion.

5)  Advertisements:  

	Instantaneous Delay [optional]:  (composition rule: additive)

		The router provides some measurement of the instantaneous
		delays.  Since the maximal delays are more important than
		the average delays, this measure will likely focus more
		on those, but no standard procedure is given for computing
		this number.

*Resulting end-to-end service:  several levels of controlled delay
service are offered.  There are no assurances about the absolute levels
of delay or jitter.

Example 2:  Bounded Delay Predictive Service:

0)  Motivation:  This service is designed for playback applications which
are tolerant of occasional missed playback points.  The presence of
delay bounds serves two functions.  First, they provide some
characterization of the service so that a non-service-adaptive
application (that is, an application that does not want to continually
change its service request in response to current conditions) can know
beforehand the worst delays its packets will experience in a given
service class.  This will allow such applications to choose an
appropriate service class.  Second, such delay bounds can help
applications which are not interested in adapting to current delays to
set their playback point.

1)  Per-hop Service:  There are several levels of service.  Each level is
associated with a delay bound, and the router must ensure that
violations of this delay bound are rare.  There are 5 different
logical levels of service, with different levels of delay
control.

2)  Traffic specification and policing:  Traffic is described by a
token bucket filter (tbf).  Policing is done at the edge of the network
and at all source merge points.  Nonconforming packets are dropped.

3)  Invocation:  

TSpec: (token bucket depth, token bucket rate) 

RSpec: (target-delay) or (service-level)

The service module maps the target-delay into the service class with the
largest delay bound which is still less than the target delay.

4)  Ordering:  The TSpec's are ordered according to the usual tbf
ordering; both the token bucket depth and rate must be greater than or
equal in order for the TSpec to be greater than or equal.  The RSpec's
are ordered in the obvious fashion.

5)  Advertisements:  

	Instantaneous Delay [optional]:  (composition rule: additive)

		The router provides some measurement of the instantaneous
		delays.  Since the maximal delays are more important than
		the average delays, this measure will likely focus more
		on those, but no standard procedure is given for computing
		this number.

	Delay Bound [mandatory]:  (composition rule: additive)

		The router provides the delay bound targets for the
		various levels of predictive service.

6)  Resulting end-to-end service:  several levels of delay bounded
service are offered.  Each level of service must obey a delay bound,
but may also be characterized by other quantities (e.g., instantaneous
delays).

Example 3:  Guaranteed Service:

0)  Motivation:  This service is designed for playback applications which
are intolerant of any missed playback points, and other applications
with hard real-time requirements.

1)  Per-hop Service:  The level of service is characterized by a rate
r.  The router must assure that the service matches the "fluid model"
of service at that same rate to withing some error bound.  The error
bound is of the form A/r+B.  The WFQ bounds have A=Pmax and B=0.  [Some
math remains to be done here to decide and make precise what we mean by
error term.  Also, the current description of the per-hop service is
obviously overly terse as stands, but hopefully gives an adequate idea
of what is required.]

2)  Traffic specification and policing:  Traffic is described by a
token bucket filter (tbf).  Policing is done at the edge of the network
and at all source merge points.  Nonconforming packets are dropped.

3)  Invocation:  

TSpec: (token bucket depth, token bucket rate) 

RSpec: (rate)

The variable (rate) is the rate in the fluid model.

4)  Ordering:  The TSpec's are ordered according to the usual tbf
ordering; both the token bucket depth and rate must be greater than or
equal in order for the TSpec to be greater than or equal.  The RSpec's
are ordered in the obvious fashion.

5)  Advertisements:  

	Latency [mandatory]:  (composition rule: additive)

	Error Terms A and B [mandatory]:  (composition rule: additive)

		The router provides the delay bound targets for the
		various levels of predictive service.

6)  Resulting end-to-end service: an assured bandwidth service which, when
used by a policed flow, produces a delay bounded service.  In fact, the
service conforms to the fluid model to within the specified error bounds.

---

From: [email-masked]
Date: Wed, 28 Dec 1994 09:05:41 -0800

Scott,

I am still struggling to understand what is going on here.
Since there have been no other comments, I assume everyone else
understands... well, be patient with me.

  *> 
  *> There are a number of optional generic advertisements that are
  *> independent of the individual services.  These include (with the
  *> composition rule described in parenthesis):
  *> 
  *> Latency: (composition rule: additive)
  *> 
  *> Hop number: (composition rule: add 1)
  *> 
  *> Bandwidth of link: (composition rule: MIN)
  *> 

Optional means some routers do, some don't?  That seems likely to lead
to a random hodge-podge that won't provide anything useful to anybody...

  *> 
  *> Example 1:  Level-of-Effort Predictive Service:
  *> 
  *> 0)  Motivation:  This service is designed for service adaptive and delay
  *> adaptive applications; i.e., applications that are prepared to adapt to
  *> changing delays and to change their service request if the current service
  *> level is not adequate.  This service does not provide any quantified level
  *> of assurance.  Instead, it merely promises to avoid overloads by turning
  *> excess flows away; the criterion for determining overloads is unspecified.
  *> Thus, while this service controls delay, it does not make any specific
  *> assurances about delay.
  *> 
  *> 1)  Per-hop Service:  The router must assure that the packet delays are
  *> controlled.  No quantitative specification of the level of delay are

What does "controlled" mean, exactly?

  *> given, but the router is expected to use admission control to avoid
  *> overload situations.  There are 5 (pick a number) different logical
  *> levels of service, with different levels of delay control.
  *> 
  *> 2)  Traffic specification and policing:  Traffic is described by a
  *> token bucket filter (tbf).  Policing is done at the edge of the network
  *> and at all source merge points.  Nonconforming packets are dropped.
  *> 
  *> 3)  Invocation:  
  *> 
  *> TSpec: (token bucket depth, token bucket rate) 
  *> 
  *> RSpec: (target-delay) or (service-level)
  *> 

Is "terget-delay" per-hop?

  *> The service module can map the target-delay into a service level with
  *> any monotonic mapping.
  *> 

Is this mapping router-specific?  Should it be configurable?

  *> 4)  Ordering:  The TSpec's are ordered according to the usual tbf
  *> ordering; both the token bucket depth and rate must be greater than or
  *> equal in order for the TSpec to be greater than or equal.  The RSpec's
  *> are ordered in the obvious fashion.
  *> 

Obvious, once you map target-delay into service level, and order service
levels (but words like "obvious" don't belong in specs).

  *> 5)  Advertisements:  
  *> 
  *> 	Instantaneous Delay [optional]:  (composition rule: additive)
  *> 
  *> 		The router provides some measurement of the instantaneous
  *> 		delays.  Since the maximal delays are more important than
  *> 		the average delays, this measure will likely focus more
  *> 		on those, but no standard procedure is given for computing
  *> 		this number.
  *> 
  *> *Resulting end-to-end service:  several levels of controlled delay
  *> service are offered.  There are no assurances about the absolute levels
  *> of delay or jitter.
  *> 
  *> 
  *> 
  *> Example 2:  Bounded Delay Predictive Service:
  *> 
  *> 0)  Motivation:  This service is designed for playback applications which
  *> are tolerant of occasional missed playback points.  The presence of
  *> delay bounds serves two functions.  First, they provide some
  *> characterization of the service so that a non-service-adaptive
  *> application (that is, an application that does not want to continually
  *> change its service request in response to current conditions) can know
  *> beforehand the worst delays its packets will experience in a given
  *> service class.  This will allow such applications to choose an
  *> appropriate service class.  Second, such delay bounds can help
  *> applications which are not interested in adapting to current delays to
  *> set their playback point.
  *> 
  *> 1)  Per-hop Service:  There are several levels of service.  Each level is
  *> associated with a delay bound, and the router must ensure that
  *> violations of this delay bound are rare.  There are 5 different
  *> logical levels of service, with different levels of delay
  *> control.
  *> 

Again, are the delay bounds a local configuration item?

  *> 2)  Traffic specification and policing:  Traffic is described by a
  *> token bucket filter (tbf).  Policing is done at the edge of the network
  *> and at all source merge points.  Nonconforming packets are dropped.
  *> 
  *> 3)  Invocation:  
  *> 
  *> TSpec: (token bucket depth, token bucket rate) 
  *> 
  *> RSpec: (target-delay) or (service-level)
  *> 

Ooops, you and I been here before, and I still don't get it.  How does it
make sense fpr an end system to specify a service-level, when the meanings of
the levels are locally determined?

  *> The service module maps the target-delay into the service class with the
  *> largest delay bound which is still less than the target delay.
  *> 
  *> 4)  Ordering:  The TSpec's are ordered according to the usual tbf
  *> ordering; both the token bucket depth and rate must be greater than or
  *> equal in order for the TSpec to be greater than or equal.  The RSpec's
  *> are ordered in the obvious fashion.
  *> 
  *> 

To summarize the three examples, they apparently all use the
Tspec:

	Tspec_TBF{ b, r}

and there are 5 different Rspecs:

	Rspec_Bdelay_Pred_TD{ d }

	Rspec_Bdelay_Pred_SL{ e }

	Rspec_LoE_Pred_TD{ d }

	Rspec_LoE_Pred_SL{ e }

	Rspec_Guar{ d }

where b, r, and d are as in the CSZ flowspec, and e is the level of effort.

Five different Rspecs but only 3 different services?  That seems confusing.

Bob

---

From: Scott Shenker <[email-masked]>
Date: Thu, 29 Dec 1994 08:14:29 PST

Bob,

Thanks for your comments!

My note was originally intended to advocate the use of the template to
describe services, and the particular examples were meant to merely
illustrate the use of the template.  Most of your comments dealt with
the technical content of the examples, where I was being overly sloppy
(or noncommittal).  Can I take this as an implicit endorsement of the
template?

[stuff deleted]
> to a random hodge-podge that won't provide anything useful to anybody...

Yes.  I think one of the hardest design decision the int-serv group
will have to make is which advertisements are mandatory and which are
optional.  The tradeoff is between achieving homogeneity versus
imposing a burden on all routers offering that service.  I think the
examples above could easily be made them mandatory, but advertisements
which involve measuring per-packet delay involve substantial overhead
and perhaps we don't want to impose that requirement universally.

> What does "controlled" mean, exactly?

I don't know what it means exactly.  If I were writing the spec for
this service I would say that the router must exercise admission
control, and that the notion of controlled delay applied no matter what
the load pattern (i.e., you cannot say that an overprovisioned ethernet
provides "controlled delay").  However, the basic notion of
level-of-effort is that the actual delays are not characterized
precisely, and so I don't know if we can say more than this.  I assume
that "controlled delay" will be an issue where router vendors vie for
competitive advantage by finding better algorithms for controlling
delay and we don't need a more precise statement of what that means.

Others might disagree, and we need to have that debate.  Since I didn't
want the issue of the template to go down in flames over this issue I
remained extremely vague.  Since it appears that there are no serious
objections to the template, we should start moving ahead to debate the
individual services, and this would require someone to prepare a more
detailed description of the various services where perhaps "controlled
delay" will be more fully elucidated.

> Is "terget-delay" per-hop?

Yes, target delay means the target delay at that particular hop.

> Is this mapping router-specific?  Should it be configurable?

Yes, and yes.  The mapping between target-delay and the service level
for this level-of-effort Predictive service need not be uniform across
all routers.

> levels (but words like "obvious" don't belong in specs).

Once again, you are right.  I was just being lazy.

> Again, are the delay bounds a local configuration item?

Yes (at least in my opinion).  There are no global delay bounds
mandated; each router gets to choose their own (although there may be
informal guidelines which determine the choice of these bounds).

> the levels are locally determined?

Yes, we have been here before.  I remain confused and so I included
both.  I tried to write some words to explain my confusion, but perhaps
this is best left for a separate discussion.  [The basic issue is if you don't
have global service levels, what do you advertise?]
  
> Five different Rspecs but only 3 different services?  That seems confusing.

Well, this all gets back to the service-level versus target-delay
debate.  I was being noncommittal and included both.  If we end up
deciding to use only with target delays then this solves your problem.
But it doesn't seem like that big a problem to start with.

--Scott

---

From: Scott Shenker <[email-masked]>
Date: Thu, 29 Dec 1994 08:14:29 PST

Bob,

[stuff deleted]

  

--Scott

---

From: [email-masked]
Date: Thu, 29 Dec 1994 08:56:35 -0800

*> From [email-masked] Thu Dec 29 08:34:56 1994
  *> From: Scott Shenker <[email-masked]>
  *> To: [email-masked], [email-masked]
  *> Subject: Re: template doc
  *> Cc: [email-masked]
  *> Date: Thu, 29 Dec 1994 08:14:29 PST
  *> Content-Length: 9033
  *> X-Lines: 224
  *> 
  *> Bob,
  *> 
  *> Thanks for your comments!
  *> 
  *> My note was originally intended to advocate the use of the template to
  *> describe services, and the particular examples were meant to merely
  *> illustrate the use of the template.  Most of your comments dealt with
  *> the technical content of the examples, where I was being overly sloppy
  *> (or noncommittal).  Can I take this as an implicit endorsement of the
  *> template?
  *>   
  *> 

Scott,

Sure.  But a template is just pure syntax, or should I say pure
taxonomy; in a sense, any template will do, what matters is the
contents.  I think your template is fine in principle; my primary
question is whether it will be possible to fill it out in a way that
neither under-determines nor over-determines the services.

  *> >   *> 
  *> >   *> 1)  Per-hop Service:  The router must assure that the packet delays are
  *> >   *> controlled.  No quantitative specification of the level of delay are
  *> > 
  *> > What does "controlled" mean, exactly?
  *> 
  *> I don't know what it means exactly.  If I were writing the spec for
  *> this service I would say that the router must exercise admission
  *> control, and that the notion of controlled delay applied no matter what
  *> the load pattern (i.e., you cannot say that an overprovisioned ethernet
  *> provides "controlled delay").  However, the basic notion of
  *> level-of-effort is that the actual delays are not characterized
  *> precisely, and so I don't know if we can say more than this.  I assume
  *> that "controlled delay" will be an issue where router vendors vie for
  *> competitive advantage by finding better algorithms for controlling
  *> delay and we don't need a more precise statement of what that means.
  *> 

This only make sense if there is some defined notion of "better" for
controlled delays.  That sounds offhand like a non-trivial intellectual
question, but I think it has to be answered if your "competitive
advantage" strategy is to succeed.

  *> Others might disagree, and we need to have that debate.  Since I didn't
  *> want the issue of the template to go down in flames over this issue I
  *> remained extremely vague.  Since it appears that there are no serious
  *> objections to the template, we should start moving ahead to debate the
  *> individual services, and this would require someone to prepare a more
  *> detailed description of the various services where perhaps "controlled
  *> delay" will be more fully elucidated.
  *> 

Yes.

  *> > 
  *> > To summarize the three examples, they apparently all use the
  *> > Tspec:
  *> > 
  *> > 	Tspec_TBF{ b, r}
  *> > 
  *> > and there are 5 different Rspecs:
  *> > 
  *> > 	Rspec_Bdelay_Pred_TD{ d }
  *> > 
  *> > 	Rspec_Bdelay_Pred_SL{ e }
  *> > 
  *> > 	Rspec_LoE_Pred_TD{ d }
  *> > 
  *> > 	Rspec_LoE_Pred_SL{ e }
  *> > 
  *> > 	Rspec_Guar{ d }
  *> > 
  *> > where b, r, and d are as in the CSZ flowspec, and e is the level of effort.
  *> > 
  *> > Five different Rspecs but only 3 different services?  That seems confusing.
  *> > 
  *> 
  *> Well, this all gets back to the service-level versus target-delay
  *> debate.  I was being noncommittal and included both.  If we end up
  *> deciding to use only with target delays then this solves your problem.
  *> But it doesn't seem like that big a problem to start with.
  *> 
  *> 

Well, I was thinking about concrete representations.  Is a flowspec
(Tspec or Rspec) of the form: (service, parm1, parm2, ...), or is
it (service, sub-service, parm1, parm2, ...) or ??  I agreee it
is not a big problem.

Bob

  *> 
  *> --Scott
  *> 
  *>