Subject: heterogeneity

From: Scott Shenker <[email-masked]>
Date: Wed, 4 Jan 1995 17:24:30 PST

Recently I sent a note to this WG about the template document.  From
the lack of discussion, and the apparent degree of consensus at the
IETF meeting, I assume we are ready to move on to considering proposals
for individual services.  The definition and standardization of these
services is perhaps the central task of this WG.  I hope we make some
progress on this before the next WG meeting.

However, there are aspects of our job that are not adequately addressed
by just defining individual services.  Heterogeneity is one such
issue.  The note attached below is an initial attempt to grapple with
heterogeneity.  Comments are welcome!

--Scott

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

		Strategies for Dealing with Heterogeneity

CONTEXT

In the current version of the service model paradigm, we assume that at
any point in time there is a single IP service model.  The service
model is a collection of several constituent services (e.g., Guaranteed
service, Predictive service, ASAP service, etc.); the service model is
extensible in that we can easily add to this list of services, but it
will be difficult to delete services once they have become part of the
service model.  Routers need not support all of these constituent
services; in order to be compliant, routers merely need to abide by the
standards for those services they do claim to support.  This raises the
problem of heterogeneity.  The set of constituent services available
along a particular path will depend on the path and will change over
time as routers are upgraded.   Moreover, routers along a given path
may not all support the same services.  For example, along a path where
all other routers support Guaranteed and delay-bounded Predictive and
level-of-effort Predictive service, there may be an ethernet which only
supports ASAP service.  Also, along a given path it might be the case
that some routers support Guaranteed service but others do not.  How
can we deal with this heterogeneity in the available services?  How can
we know what services are available along a given path, and how can we
utilize those services without always resorting to the lowest common
denominator?

In this short note I describe several possible approaches to dealing
with heterogeneity.  I focus on the what network functionality we
should provide for dealing with heterogeneity. I do not address what
host modules are needed to use this functionality; i.e., I am not
addressing the function or structure of the "quality of service
manager" (QM) but am only discussing what functions are available from
the network that the QM can use.  Thus, I will refer to "host" actions
rather than "application" actions because the functionality on the host
may be divided in various ways between the application and the QM.

In designing these mechanisms, it is important to state explicitly the
degree of heterogeneity we expect to see.  I think the Integrated
Services WG should accept as a basic premise that we will adopt a
rather small and compact set of services.  In my opinion, we need to
make this assumption if we want the problem of heterogeneity to be
manageable.  If we were to adopt, instead, the principle that we
approve every reasonable looking service (e.g., ending up with ten
varieties of Predictive service) I think the resulting heterogeneity
would pose a severe problem with little compensating benefit.

Most of the approaches I discuss in this note have been mentioned, in
one form or another, in previous WG discussions.  For convenience, the
presentation here will assume the use of RSVP as a set-up protocol, but
the proposals are not meant to be RSVP-specific.  I hope this note
stimulates some more detailed examination and discussion of these
proposals.  Feedback is welcome!  In writing this note I have been
greatly aided by the comments of Lee Breslau, but he is not responsible
for any of the numerous errors in judgement that undoubtedly remain.

We start with a description of our general approach to the problem, and
then we turn to a more detailed discussion.  We interrupt our detailed
discussion at two points to propose two design options, one with
significantly more complexity (and functionality) than the other.

GENERAL APPROACH

In the current design, a host requests a particular service by
specifying an RSpec, TSpec pair.  See the earlier note on service
templates for a description of RSpec's and TSpec's, but in short the
TSpec is a description of the traffic (e.g., token bucket filter
parameters) and RSpec is a description of the QoS request (e.g.
Level-of-Effort Predictive class 1, etc.).  If all routers supported
all the services in the service model, there would be no problem; the
resulting service would be installed at each router along the path.
Advertising (via the one-pass-with-advertising approach, called OPWA)
would enable the host to know what end-to-end QoS would result from its
particular service request.

However, if not all routers along the path support the service then our
current design results in an admission control reject at the first
router which does not offer the requested service.  This means that a
host can only request the "lowest common denominator" service along a
path.  This is certain to inhibit the development, deployment, and
utilization of new services, and should be avoided if at all possible.

The approach described here is based the principle of replacements; if
the service requested by host is not available at a router then another
service can be substituted.  The various approaches differ mainly in
who (the host or the router) decides which service is substituted.  The
approaches all share the property that the service expected by a host
should be modeled on the ideal of end-to-end connectivity of the
requested service (i.e., what would be provided if all routers offered
the requested service), and the network is responsible for informing
the host the extent to which this is a realistic approximation.

Thus, our first approach is to have the router substitute a
"replacement" service if the requested service is not supported by that
router.  That is, if I request Guaranteed service, but the router does
not offer Guaranteed service, then it can substitute its best
replacement.  These replacements will vary a great deal in their
reliability; e.g., Delay-Bounded Predictive is a reliable replacement
for Guaranteed service, whereas ASAP is typically not.  Moreover, by
having routers advertise their service offerings, and the availability
of reliable replacements, OPWA would allow hosts to know the end-to-end
availability of a service.

This first design option has routers reject service if admission
control fails, but to substitute replacements if the requested service
is not offered.  However, some hosts might want replacements
substituted even in the case of an admission control rejection.  To
accomplish this we must allow the host to control the replacement
decisions.  This can be done through the use of reservation scripts,
which are part of the service request and which allow a host to specify
the desired router actions when a service is rejected.  However, such
scripts need to be merged (when two reservations merge), and this is a
serious problem (which we do not deal with extensively in this note).
Some hosts might want an even more detailed control over the
reservations along a path.  This extra control can be provided by
allowing the service request to specify the service at each individual
link.  Again, this involves merging problems.

Let's now turn to a more detailed discussion of these issues.  We first
describe replacements and reliable replacement, and then describe the
way advertising can be used in this context.  We then present design
option 1 and briefly discuss its merits.  After that we present the
notions of reservation scripts and explicit per-link control.  We
conclude with a brief discussion of design option 2 and its relative
merits.

DETAILED DISCUSSION

*Reliable Replacements and Replacements

If a requested service is not available, a router (if the service
request allows it; see below) can substitute a "reliable replacement".
An example of this would be that the ASAP service of an underutilized
ethernet might be a reliable replacement for Level-of-Effort Predictive
service (or even Delay-Bounded Predictive service).  Also,
Delay-Bounded Predictive service could be a reliable replacement for
Guaranteed service.  The degree of reliability of the replacement is
not specified, just as we don't specify the rarity of delay violations
in Predictive service.  This may sound unacceptably vague, but we
assume that there will be operational guidelines and informal standards
of acceptable practice that make this measure meaningful.  For the
time being, we should think of a reliable replacement as one that
meets the service specifications of the original service well over 95%
of the time.

A weaker form of this is an unreliable replacement.  If the best a
router can offer a Guaranteed service request is ASAP service, then if
the service request allows the use of such unreliable replacements
(again, see below), the router can use it in its stead.  Such
unreliable replacements carry no quality assurance; the router is doing
its best, but the resulting level of service can be arbitrarily bad.

Note that the use of replacements (reliable and otherwise) leaves it up
to the router to decide which services best fit the original request,
and if these substitutes are reliable.  This allows overprovisioning of
less stringent services to serve as replacements for more demanding
ones.  A network built around overprovisioned ASAP service cannot claim
to support Guaranteed or Predictive service, but could claim to provide
reliable replacements.  In some cases users will care about the
difference in perceived quality between Guaranteed or Predictive
service and its reliable replacement, and won't use reliable
replacements, but my guess is that for the vast majority of cases the
difference in perceived quality will not matter.

There is a subtle distinction between the notion of reliability in
Predictive service and the reliability of a "reliable replacement." For
a router to offer Predictive service, it must be able to meet the
service requirements independent of where it is deployed and the
ambient load.  A router would, presumably, have to undergo what we
refer to as the "Bradner tests" where it is subject to a wide variety
of loads and its ability to deliver the advertised service is
measured.  In contrast, the reliability of a reliable replacement need
only apply to the particular context where assumptions can be made
about the nature of the load.  Thus, an overprovisioned router with
FIFO scheduling and no admission control does not support Predictive
service, but can offer a reliable replacement for Predictive service.

Recall that in the template document we discussed the fact that service
requests are typically comprised of two distinct pieces: the traffic
specification TSpec (e.g., token bucket filter parameters) and the
quality of service request RSpec (e.g., Predictive class 1).  The use
of replacements and reliable replacements is much easier if the traffic
specifications are the same in the various services used to replace
each other (i.e., if all services use token bucket parameters as their
traffic specification).  Then, using a replacement is merely equivalent
to substituting a different RSpec.  If the TSpec's are not the same,
then the router needs to map the original TSpec into a new TSpec
appropriate for the replacement service.

*Advertisement of Service Availability

It is mandatory that each router advertise the degree of availability
of all services in the service model.  For each service, the router
must advertise one of the following responses:  offered, reliable
replacement available, no reliable replacement available, not known.
Not known means that the router not only does not offer that service,
but does not even know what it is (e.g., a newly adopted service will
not be known to most deployed routers).  For such unknown services, the
router obviously cannot make sensible decisions about replacements
(except to perhaps default to the ubiquitously available ASAP
service).  For each service the advertisements keep a count of how many
routers fall into each category (offered, reliable replacement
available, etc.).  Thus, a set-up protocol like RSVP can use
advertising (a la OPWA) to transmit to the host the degree of
availability of a service end-to-end.  Another piece of functionality,
which is not the subject of this note but which perhaps is relevant
context, is quality-of-service routing that may enable receivers to
request routes that provide end-to-end support of their requested
service.

When a replacement service (reliable or otherwise) is offered (i.e., if
the service is known), the router indicates this in the service
availability advertisement and fills in the normal advertisements
associated with the original service request.  For instance, if a
router with an overprovisioned ethernet offers ASAP service as a
reliable replacement for delay-bounded Predictive, it advertises a
delay bound for that service.  When the replacements are unreliable,
the router still attempts to fill in the advertisement field with
something meaningful even though it cannot ensure adherence to
that service specification.

These two components, replacements and advertising, are enough to
provide some limited ability to cope with heterogeneity.  This
combination will be the foundation of design option #1.
  
**Design Option 1:  Every router advertises the availability of all
known services (offered, reliable replacement, no reliable replacement)
and, for each service, provides the appropriate parameters describing
that service (e.g., delay bounds, instantaneous delays, etc.).  All
service requests are processed with the understanding that if the
requested service is not offered, the best replacement (in terms of
offered services) will be substituted in its place (a router must use,
as its substitute, a service that can meet the advertised
characteristics).  If a service request is denied by admission control,
then the flow is rejected and no substitute is offered. Note that if
Guaranteed is requested by the host but not offered by a router (which
instead offers Delay-Bounded Predictive service as a reliable
replacement), that router will process the request as if it were a
Delay-Bounded Predictive service; if the Delay-Bounded Predictive
request is denied by admission control (because of the current load
conditions), then a reject occurs (the router does not try to
substitute for admission control failures of its own substitutes).  The
reason we assume a failure upon admission control reject, rather than
substituting a replacement service, is that advertising has no way of
telling us what admission control will do and RSVP has no confirmation
message that tells us what admission control did (except to inform us
of a reject).  A host that wants Guaranteed service and does not want a
replacement would have no way of knowing if replacements were made
because of admission control failures.

This design, along with OPWA, allows a host to know what end-to-end
service is available (is it offered end-to-end, or a reliable
replacement end-to-end, or just a replacement end-to-end, or is there a
router which does not even know about the service).  It does not allow
a host to ask for replacements in the case of admission control
failures.  This design makes advertising rather central to dealing with
heterogeneity, and requires hosts to act intelligently upon the
information contained in advertisements.  [This design also does not
deal well with the case where services are not known at a router; we
deal with that below, but if we adopt design option 1 then we need to
consider this issue further.  Perhaps we should adopt the approach we
discuss later for design option 2 where the service request comes with
a list of substitute RSpec's, and the router uses the first one it
knows.  For now, assume that if the service is not known then the
router substitutes ASAP service.]

For the reasons listed above, one might not find design option 1 to be
sufficient.  We can address some of the problems by introducing
the notion of reservation scripts, which we now describe.

*Reservation Script

When a service request (in the form of an RSpec, TSpec pair) arrives at
a router, there are four conditions under which this service can be denied.

	Not known:  the requested service is not available
		at this router, and the router does not know about the
		service.
		
	Not offered but known:  the requested service is not available
		at this router, but the router does know about the
		service.

	Not mergeable: the requested service is available at this router, but
		there is presently an existing reservation for an overlapping
		flow and the service request cannot merge with the existing
		service.  If we decide that there is no ordering relationship 
		between Guaranteed and Predictive service, this would occur if 
		a Predictive service request were to arrive at a router with an 
		existing Guaranteed reservation.  This also would occur with a 
		Wildcard Filter reservation and a Fixed Filter reservation.

	Not admissable: the requested service is available, and there are no
		merging problems.  However, admission control indicates that
		this flow cannot at present be admitted.[This may later be
		sharpened to indicate either that the request can never be
		admitted (e.g., requesting 10 mbps on a 1.5 mbps link) or
		that the current load conditions prevent admission.]

We can use reservation scripts to indicate what should happen in each
one of these cases.  These scripts are included in the service
request.  Logically, they could take the form

	If <Not known> then <RSpec list>
	If <Not offered but known> then <router action 1>
	If <Not mergeable> then <router action 2>
	If <Not admissable> then <router action 3>

The generic set of allowed router actions are:

		fail 

		use reliable replacement (if one is not available
			then fail)

		use replacement (reliable if available but any 
				replacement if not)		

The RSpec list is a list of alternate RSpec's.  The router should
substitute the first known of these for the requested RSpec and then
process the rest of the script.  The reservation scripts should be
interpreted as having each router action produce a new RSpec, which is
then fed back into the script all over again; the router cannot let any
RSpec occur twice in this process, so no looping is allowed (i.e., if
services A and B are reliable replacements for each other, we don't
keep substituting one for the other).  

The big problem with such scripts (and it becomes an even bigger
problem if we allow more complicated scripts) is that we have to merge
them; if two receivers each offer a script, how do we merge the two
scripts?  We have made some, but not much, progress on this issue, but
I won't go into the details now.  For this merging to produce the right
results, we need enlarge the functionality of RSVP's teardown messages
(they not only tear down state in response to a failure, but they also
carry information about substitutions being made, so downstream nodes
can then teardown flows which didn't want such substitutions).  One can
also avoid the merging problem by making the assumption that all
receivers of a given flow use the same script (e.g., the script could
be part of what is contained in sd); then we don't allow any merging
among nonidentical scripts and we need no additional capability from
RSVP teardown messages.  Note also that if substitutions are made in
the case of admission control failures (not mergeable or not
admissable) then the advertisements of the resulting end-to-end service
are not dependable; the end-to-end delays that are advertised (via
OPWA) do not reflect the substitutions made for admission control
reasons (they do reflect the substitutions made when a service is not
offered).  These advertisements are also not dependable when
substitutions are made for services that are not known (because the
router does not know enough to fill in the advertisement fields in a
meaningful manner).

*Explicit Control

I hope that the above features will enable hosts to cope with most
situations.  However, there might be a need for a fall back option
that allows the host to exert a finer degree of control.  For instance,
users of an oft travelled path may want to hand-tune the service.
Thus, the service module interface should allow a service request of
the form:

<node1>: RSpec1
<node2>: RSpec2
<node3>: RSpec3
<node4>: RSpec4
......

For instance, one might request delay bounded Predictive service only
at the bottleneck link and ASAP service everywhere else.  Clearly, for
a host to use this intelligently, it must have probed the path in
detail to know what services are available where.  That would require
better tools (perhaps in RSVP) for probing the path.  Again, merging of
these detailed instructions is a problem, but perhaps it can be done
hop-by-hop.  Doing this for multi-source flows is also a problem.

The addition of reservation scripts and explicit control leads us to
design option #2.

**Design Option 2:  Incorporate the reservation scripts and the
explicit controls in addition to design option 1.  This allows much
finer control of the reservation process.  The use of scripts means
that advertising is not such a central mechanism; one can use scripts
instead of having to look at the detailed information from the
advertising messages (this means that a centrally supplied script could
relieve individual hosts from having to figure out what action they
wanted).  However, design option 2 leads us either into severe merging
problems or serious requirements of homogeneity (with all hosts asking
for the same script).  Design option 2 also means that hosts do not
always know the characteristics of the resulting end-to-end service
(e.g. delays) since advertising cannot reflect substitutions for
admission control reasons.

**Summary

I have identified two design options to deal with heterogeneity.  In
design option 1, routers can offer replacement services and the
availability of services is advertised.  In design option 2, hosts can
use reservation scripts to advise routers of their desires, and hosts
can finally, if all else fails, resort to an explicit and detailed
control of the per-hop service.

The question is I would like to pose for this WG is: do design options
1 and 2 allow us to adequately deal with the heterogeneity that is
likely to exist in the network?  Are there other features that should
be added?  Are there aspects of these proposals that should be
eliminated?  Which option seems more attractive?  Obviously many
details remain to be settled, and now is not the time to quibble over
them.  I am more interested in whether the general approaches seem to
be appropriate.

My current opinion is that design option 2 is a swamp that is best
avoided at least for now.  Design option 1 (with more attention paid to
the case where services are not known) is the right starting point.
Comments?  Will this be enough?

---

From: Jon Crowcroft <[email-masked]>
Date: Thu, 05 Jan 95 10:12:32 +0000

>heterogeneity.  Comments are welcome!
 
Scott

well, this is putting more and more complexity on the end system
(which may be no bad thing, but...) which may not know....

there are two facets here
1/ can you simply rank service classes (with overlaps), and then for 
an instance of a class, under a particular load pattern, at a particular node
impleenmting it with a particular scheduling algirthm, decide that the
lower class can provide the higher service? if so, surely the
admission control algorithm can just say 'Yes' and problem is solved,
albeit for lower utilisation
2/ for intangible reasons, a user may want a level of assurance
(mission/life/safety critical, for instance), or
the network may want to operate at a level of utilisatrion, which
makes the class hierarchy less overlapped. Then the admission control
is simply less flexible

all you need is 1 bit in the RSVP request which says whether the user
is flexible, and 1 bit per network path that says whether the network
operators' policy is to let the net run underutilsied in favour of
admitting flows more flexibly, don't you?

cheers

jon 
[happy new year to all & sundry]