Subject: proposal for heterogeneity

From: Craig Partridge <[email-masked]>
Date: Wed, 15 Nov 95 13:32:56 -0800

Hi folks:

Here's a proposal (new ID) for how we might handle heterogeneity of
services.  This is just a starting document (No one but the authors has
seriously worked through the document).  The notes below are from
Scott Shenker:

    Not all network elements will offer the same set of services; for
    instance, some elements might offer only controlled delay service, and
    others might offer only guaranteed service.  There is a new document
    describing one proposal for dealing with this heterogeneity in services
    offered by network elements.  While there is not yet consensus on this
    or any other particular proposal for dealing with the inevitable
    heterogeneity, we are distributing this document now to spur
    discussions on this important topic.

We expect to devote some time to this issue at the Dallas meeting.

Craig

Internet Engineering Task Force                   Integrated Services WG
INTERNET-DRAFT                                     L. Breslau/S. Shenker
draft-ietf-intserv-hetero-01.txt                                   Xerox
                                                        15 November 1995
                                                         Expires: ?/?/96

               A Proposal for Accommodating Heterogeneity

Status of this Memo

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   To learn the current status of any Internet-Draft, please check the
   "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast).

   This document is a product of the Integrated Services working group
   of the Internet Engineering Task Force.  Comments are solicited and
   should be addressed to the working group's mailing list at int-
   [email-masked] and/or the author(s).

Abstract

      Routers need not provide all services defined by the intserv WG.
      This will inevitably lead to heterogeneity in the set of services
      offered by network elements.  How can we enable applications to
      obtain the end-to-end service they desire in the face of this
      heterogeneity?  This document describes an approach involving
      replacement services and characterizations that builds end-to-end
      service out of heterogeneous per-link service offerings.  This
      proposal was first described in [1], from whence much of the text
      was lifted.

Breslau/Shenker              Expires ?/?/95                     [Page 1]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

Introduction

   The Integrated Services WG is currently operating under the
   assumption that while the IETF will define and standardize a set of
   services such as those described in [2-5], it cannot -- and indeed
   should not -- mandate the universal deployment of these services.
   Within this context, a router can be considered compliant with the
   integrated services architecture if it can respond to requests for
   enhanced qualities of service, even though it may not implement all
   (or any) of the specified real-time services.  We refer to such a
   router as "integrated services-aware".  Whether or not a service is
   deployed remains under the control of individual network service
   providers and router vendors. Different vendors may choose to support
   different subsets of defined services in their products, and
   different service providers may choose to deploy a different subset
   of defined services in their networks. Thus, different services will
   be available at different routers (or, more generally, network
   elements in the sense of [2]) in the Internet, and some routers may
   not support any service other than best-effort.  While private IP
   networks may achieve a high degree of homogeneity, heterogeneity in
   the set of services offered by various routers is inevitable in the
   Internet as a whole, and we must incorporate its presence in our
   overall architecture.

   In this document we discuss one approach to dealing with such
   heterogeneity gracefully.  We consider the situation where there are
   several defined services that require admission control, along with
   the traditional best effort service.  Absent the mechanisms we
   describe in this document, the normal semantics of a service request
   for these admission controlled service are assumed to be that if the
   service requested is not available, either because the current load
   is too high or because the router does not offer the service, then
   the service request is denied.  For specificity we will refer to the
   Guaranteed, Predictive, and Controlled Delay services defined in [3-
   5], but nothing in this proposal limits us to those particular
   services.  All routers support best effort service, but routers need
   not support any of the other services.  We confine this discussion to
   the problem of heterogeneity in the set of services offered by
   integrated services-aware routers.  We specifically do not address
   the problem of non-integrated services-aware routers, which offer
   only best effort service and cannot respond to requests for other
   services.

   Without mechanisms to cope with heterogeneity in the set of offered
   services, routers not supporting a service requested by an
   application must deny the service request.  This enables applications

Breslau/Shenker              Expires ?/?/95                     [Page 2]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   to use only those services offered by all routers along a path
   between source and destination.  This restriction to the "best common
   service" significantly limits the services available to applications.
   For example, applications running on any host attached to an ethernet
   supporting only best effort service would be unable to secure
   anything other than best-effort service at all routers along a path.
   Such a design would severely limit the use of partially deployed
   services, thereby inhibiting the incremental deployment of new
   services.  This default "best common service" behavior would
   therefore greatly slow, and perhaps even prevent, the evolution of
   the Internet towards an integrated services architecture.  Thus,
   mechanisms that address the problem of heterogeneity are a necessary
   component of an integrated services architecture.

   Some cases of heterogeneity can be handled trivially.  When presented
   with a service request, routers are always free to substitute a
   "better" service, in the sense of the ordering used for merging (see
   [2]).  For instance, a router can always use a better level of
   predictive service than the one requested, and in fact merging
   depends on such substitutions.  Less trivially, if predictive is
   always considered better than controlled delay in the ordering
   relationship, then a router can always substitute predictive service
   for controlled delay service.  In such "ordered" cases, the network
   element actually can be considered to offer the lesser service as
   well as the better service.  Thus, when we say a network element does
   not offer a service, we mean that it does not offer it or any other
   strictly better service.  However, as part of offering the lesser
   service, the element must export the appropriate characterization
   values.

Replacement Services

   The approach we take is based on the principle of "replacement"
   services.  When a service is requested, it can be replaced by an
   alternate service (under conditions described below) at those routers
   not offering it.  That is, the service request's RSpec specifies one
   service, but the router not offering that service invokes another
   service.  The fundamental principles underlying this approach are
   that (1) the service expected by an application should be modeled on
   the ideal of end-to-end connectivity of the requested service (i.e.,
   the service that would be provided if all routers along the path
   offered the requested service), and (2) the network is responsible

Breslau/Shenker              Expires ?/?/95                     [Page 3]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   for informing the application the extent to which this is a realistic
   approximation.  This insulates applications from having to
   understand, or even know about, the detailed nature of heterogeneity
   or how the different services along the path compose.  This
   insulation is critical, we feel, for enabling applications to
   function relatively undisturbed while the network infrastructure
   evolves.

   Before continuing, it is important to note that we are not addressing
   the issue of allowing substitutions for admission control failures.
   That is, we are not proposing using replacements if the requested
   service is offered at a router but admission control has denied the
   request because the load is too high, or the request is not mergeable
   with a previously existing reservation (if two services do not have a
   common "upper bound" that is better than both of them then there is
   no way to merge them).  We do think this is an important issue,
   especially when admission control failures are a result of merging
   problems and so are likely to deny service for a long period of time
   (i.e., if there is no ordering between predictive and guaranteed
   service, then a predictive request and a guaranteed request will not
   be able to merge and the later arriving request will continue to be
   denied until the earlier reservation terminates).  However, it does
   not seem on the critical path to early deployment of services.  In
   contrast, the heterogeneity problem, particularly where there are
   many network elements that offer no services besides best effort,
   will seriously hinder deployment if not addressed immediately.

   The use of replacement services can be viable for two reasons.
   First, local conditions and service definitions may enable a router
   to substitute one service for another without a perceptible
   difference in the quality of service delivered to the application.
   For example, a lightly loaded ethernet that offers only best-effort
   service may have low enough delays that it provides service as good
   as is required by predictive service.  Second, applications vary in
   the degree of assurance they require about the service they receive.
   An adaptive application that is tolerant of packet loss, may be
   satisfied with best-effort service at those routers where real-time
   service is not available.

   We characterize replacement services as "reliable" or "unreliable".
   A reliable replacement is one that meets the service specifications
   of the service it is replacing a large majority of the time.  We do
   not express the degree of compliance precisely, but for purposes of
   the present discussion we assume reliable replacements achieve this
   conformance well over 95% of the time.

   There is a distinction between the notion of the reliability of
   replacement services and the reliability of service implementations.

Breslau/Shenker              Expires ?/?/95                     [Page 4]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   The reliability of a reliable replacement need only apply to the
   particular environment in which it is deployed, 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.  In contrast, a compliant implementation of an
   actual service, such as predictive or controlled delay, must be able
   to meet the service requirements independent of both where it is
   deployed and the ambient load.

   While the lack of specification of the degree of reliability may seem
   vague, we assume that over time operational guidelines and informal
   standards of acceptable practice will emerge.  The key point behind
   the notion of reliable replacements is an implicit statement that use
   of the replacement will result in service that is usually not
   perceptibly different from the requested service.  Examples of
   reliable replacements could be the use of predictive service for
   guaranteed service, or the use of best effort service on an
   underutilized ethernet as a replacement for controlled delay service.
   However, these specific examples of replacement services, and their
   classification as reliable or unreliable, should not be taken as a
   definitive statement about the suitability of these services to act
   as replacements.  This ultimately depends on the specific services
   defined and on decisions taken by routers, which can be impacted by
   local conditions.

   Unreliable replacements are a weaker form of replacement services,
   carrying no assurance about the quality of the resulting service.
   That is, service offered as an unreliable replacement can be
   arbitrarily bad.  For example, controlled delay service or best-
   effort service on an often congested network could be considered
   unreliable replacements for guaranteed service.  Some applications
   may be willing to use unreliable replacements when no alternative
   exists, since poor service will in some cases be better than no
   service at all.  Unreliable replacements are always offered, as best
   effort service constitutes an unreliable replacement for all
   services.

   The choice of which service to use as a replacement for a service
   request, and whether the replacement is characterized as reliable or
   unreliable, is left to the router.  This allows overprovisioning of
   less stringent services to serve as replacements for more demanding
   ones.  A network built around overprovisioned best-effort service
   cannot claim to support guaranteed or predictive service, but it
   could claim to provide reliable replacements for them.  In some cases
   users will care about the difference in perceived quality between
   guaranteed or predictive service and its reliable replacement and
   will not use reliable replacements, but for the majority of cases the

Breslau/Shenker              Expires ?/?/95                     [Page 5]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   difference in perceived quality may not matter.

Router Substitutions

   In this section, we describe how routers substitute replacements for
   services that are not offered.  We defer until later the issue of
   when the use of replacements are allowed and how much control
   applications maintain over this process.  For now we assume that
   whenever a router receives a request for a service that is not
   offered, it attempts to use a replacement service.

   Requests for services not offered by a router can be divided into two
   categories: services known but not offered by the router and services
   that are neither offered nor known.  In the former case the router
   substitutes its best replacement service for the original request.
   This means a reliable replacement is substituted if one is offered,
   and an unreliable replacement is substituted if no reliable
   replacement is offered.  The service request is then processed as if
   it were a request for the replacement service. If the replacement
   service requires admission control, the router uses the admission
   control algorithm to determine the admissibility of the new request.
   The service request is rejected if the admission control test fails;
   substitutions of additional replacement services are not permitted.
   (The reason for this restriction will become evident later.  In
   short, it enables routers using replacement services to export useful
   characterization parameters describing their replacement services.)
   If the admission control test passes, or if the replacement service
   does not require admission control, the service request is accepted.
   If a setup protocol like RSVP is used to deliver the service request
   to the router, the original service request is propagated along the
   data path by the setup protocol.

   When a router receives a service request for an unknown service, it
   cannot even judge the suitability of services as replacements.  The
   best it can do is to substitute the ubiquitously available best-
   effort service.

   We show in some simple examples how characterization and service
   replacements can be used to deal with heterogeneity.  We expect the
   two scenarios we describe here to be representative of situations
   likely to be encountered in the future Internet.  Consider first a
   situation in which a single real-time service (e.g.  controlled
   delay) is offered at some routers along a path, and other routers
   offer only best-effort service. These routers will substitute best-
   effort service for the request for controlled delay service.  Thus,
   the use of service replacements allows an application to obtain the

Breslau/Shenker              Expires ?/?/95                     [Page 6]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   real-time service where it is offered.  Applications are not confined
   to using a common service offered end-to-end.  Instead, the end-to-
   end service is built out of heterogeneous services offered at the
   routers.

   Next, we consider the case in which all routers offer real-time
   service, but they do not all offer the same real-time service.  For
   example, some routers may offer guaranteed service, while others
   offer predictive (but neither service is offered at all routers).
   Without a mechanism to allow for the composition of end-to-end
   service out of different services, applications would only be able to
   use best-effort service (which is offered everywhere).  In this
   example, if routers use the real-time service they offer as a
   replacement for the service they do not offer, applications can
   acquire a real-time service at each router.  For example, an
   application may request guaranteed service, and routers that offer
   only predictive can substitute predictive.  Using these replacements,
   applications receive better service than if they were confined to
   using a single service.

   The previous example depends on routers using the real-time services
   they offer as replacements for ones they do not offer.  While the
   intelligent use of replacements at routers cannot be mandated, we
   believe that service providers will have strong incentives to use the
   best replacement strategies they can.  Offering replacement services
   will make their services more usable and will therefore increase the
   utilization of their networks.

Characterizing Service Availability

   In this section we describe the implications of our proposal for
   coping with heterogeneity on the characterization parameters that
   routers must export.  These parameters fall into two categories.
   First, we describe characterization parameters that provide
   information about the availability of services.  Second, we discuss
   how routers handle the service specific characterization parameters
   when they offer a replacement for a particular service.

   While routers may or may not offer particular services, they must
   characterize the availability (or lack thereof) of every service.
   For each service, the router characterizes the availability of the
   service as one of the following four conditions:

           Offered

           Reliable replacement available

Breslau/Shenker              Expires ?/?/95                     [Page 7]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

           No reliable replacement available

           Not known

   The first condition indicates the router offers the service as
   defined in the service specification.  The second indicates the
   router does not offer the service, but instead offers a reliable
   replacement for it.  The third indicates that the router offers
   neither the actual service nor a reliable replacement.  Every router
   implicitly offers an unreliable replacement, as best-effort service
   constitutes an unreliable replacement for all services.  Finally,
   "not known" means that in addition to not offering the specified
   service, the router does not even know what the service is.  For
   instance, a newly defined service will not be known to most deployed
   routers.

   For each service, there is a characterization parameter that keeps a
   count of how many routers fall into each category (offered, reliable
   replacement available, etc.).  The composition rule is to add one to
   the characterization parameter associated with the router's status.
   Thus, a setup protocol like RSVP can use these characterization
   parameters to transmit to the application the degree of service
   availability end-to-end.

   In addition to the characterization parameters describing service
   availability, a router must attempt to update the service-specific
   characterization parameter fields, such as the delay bounds in
   predictive service, with meaningful values.  When a replacement
   service is offered (reliable or otherwise), the router updates the
   characterization parameters in the normal manner.  For a reliable
   replacement, the characterization parameter values should accurately
   reflect the service provided by the replacement service.  A router
   can also attempt to fill in a characterization parameter value for an
   unreliable replacement since it understands something about the
   service.  For example, a router that uses an unreliable replacement
   and is consequently unable to guarantee packet delivery might still
   be able to provide an estimated delay bound based on delays
   experienced at the router.  However, the characterization parameters
   for unreliable services will often be of little value.  If there is
   no meaningful number that can be inserted, the router can set the
   validity bit of the associated characterization parameter.  This
   signals that the content of the composed characterization parameter
   is no longer valid.

   Finally, routers cannot provide any meaningful characterization
   parameters for services that are not known because they have no idea
   what the various characterization parameters represent.  For example,
   a router cannot know whether the characterization value for an

Breslau/Shenker              Expires ?/?/95                     [Page 8]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   unknown service reflects the delay experienced or the loss rate or
   some other value.  In this case, routers should set the validity bit
   on all the characterization values associated with services they do
   not know about.  Applications receiving characterizations will know
   how much confidence to place in the values based on the availability
   of the services end-to-end and on the status of the validity bit.

   If the characterizations of service availability are made available
   to the endpoints, e.g. through the use of "advertising" in RSVP, then
   applications know the extent to which replacements would be made for
   a specific service request.  This would enable an application that
   did not want such replacements to know beforehand to not submit the
   service request.

Use of Replacement Services

   While the use of replacement services permits the composition of
   heterogeneous services end-to-end, applications may have different
   levels of tolerance for the use of replacement services.  Some
   tolerant applications may always be willing to accept replacement
   services (reliable or unreliable), while others may prefer their
   service request to be denied when the requested service is not
   offered.  We discuss mechanisms to accommodate diverse application
   requirements below.  Not surprisingly, providing additional
   functionality and flexibility to applications entails added
   complexity in the associated mechanisms.

   The simplest design removes all choice from the applications and
   mandates a uniform use of replacement services.  That is, a router
   will always attempt to use its best replacement service when the
   requested service is not offered.  While this design is easy to
   implement in the sense that it requires no added complexity in
   service requests or in merging behavior, it does not accommodate
   applications that do not want replacements to be used.  As we noted
   above, however, in environments where end-to-end characterization of
   service availability is provided to applications, they  will know
   before making a request whether a service replacement will be made.
   In such an environment, an application that does not want service
   replacements has the option not to request a service that is not
   offered end-to-end.  If end-to-end characterizations were always
   available to endpoints (as was implicitly assumed in [1]) then this
   design choice is an appealing option.  However, our design must
   accommodate the situation where such characterizations are not
   available.

   An extension to the simple design enables applications to control the

Breslau/Shenker              Expires ?/?/95                     [Page 9]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   extent to which replacement services are used.  In this design, a
   replacement handling bit is associated with every service request.
   If the bit is set in a service request, replacement services are
   allowed.  If the bit is not set, a router that does not offer the
   requested service must reject the service request and return an
   error.  This enables applications to express their preferences about
   the use of replacement services.  In environments where end-to-end
   characterization of service availability is not known, setting the
   bit indicates that the application is willing to accept whatever
   service replacements are made along the path.  In environments where
   end-to-end service characterization is available, applications should
   always set the bit since applications that do not want replacements
   used will know about their use beforehand and therefore have the
   option to not request service.

   Including this extra bit in service requests, and allowing
   applications to control how this bit is set introduces the problem of
   merging requests that have the bit set differently.  What should be
   done when two requests must be merged, one of which has the
   replacement handling bit set and the other of which does not?

   We have identified two options to handle this merging problem.  The
   first mandates a particular merging behavior.  Namely, when merging
   two requests that have the bit set differently, the merged request
   does not have the bit set.  This approach takes the conservative
   approach that it is better to deny the "flexible" application the use
   of a replacement service than it is to provide the "inflexible"
   application with service inferior to what it requested.  If the
   applications are well-behaved, the inflexible application should
   cease or change its service request, which will give the other
   application the opportunity to use replacement services (although
   their service may be disrupted).  Hence, this middle ground allows
   applications to express their desires, but it avoids complicated
   merging behavior.  In this case, setting the bit to allow use of
   replacements can be thought of as advisory only.  The network will
   honor this desire unless it conflicts with the desires of other
   applications.  Applications that do not set the bit and are not
   well-behaved can deny service to those applications willing to use
   replacement services.  This option results in the desired behavior
   when end-to-end characterizations are made available to endpoints,
   since all applications will set their bits and there is no
   complicated merging behavior.  When end-to-end characterizations are
   not available, some flexible applications may have their service
   disrupted due to requests from inflexible applications.

   Treating the replacement handling bit as more than advisory requires
   maintaining additional information when service requests are merged.
   Specifically, merging service requests that have the replacement

Breslau/Shenker              Expires ?/?/95                    [Page 10]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   handling bit set differently requires maintaining two RSpecs in the
   merged request.  One RSpec indicates the best service requested by an
   application that is willing to use replacements and the other
   represents the best service requested by an application that is not
   willing to use replacements.

   Processing these merged requests is also more complicated.  The
   router must determine the appropriate level of service to install,
   when to return an error, and when and how to modify the service
   requests (we omit the details here).  However, the advantage of this
   design is that it makes available to applications a wider range of
   functionality.

Examples of Service Replacement

   In this section, we give examples of how services can be used as
   replacements.  We consider the 3 real-time services (Guaranteed,
   Predictive and Controlled Delay) currently being considered by the
   Integrated Services Working Group.  However, we reiterate that our
   proposal for coping with the problem of heterogeneity in the set of
   offered services could be used with other real-time services. These
   examples are intended to demonstrate that service replacement is
   possible.  Other ways to accomplish these replacements may be
   possible; we do not intend to preclude their use.

   Replacing Guaranteed Service with Predictive

      A network element that offers predictive service as a replacement
      for guaranteed should first select a single level of predictive
      service that it will use to serve guaranteed flows.  This level,
      i, can be any of the 3 levels of predictive service.  The network
      element assigns the guaranteed service characterization parameter
      C the value 0, and it assigns the characterization parameter D the
      value DB_i, where DB_i is the delay bound of predictive service
      level i.

      When the network element receives a request for guaranteed
      service, it treats the request as if it were a request for
      predictive level i, with the TSpec as specified in the original
      request.

      If the network element typically meets the service requirements of
      predictive service with no or very few delay bound violations,
      then this replacement can be characterized as reliable.

   Replacing Guaranteed Service with Controlled Delay

Breslau/Shenker              Expires ?/?/95                    [Page 11]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

      A network element that offers controlled delay service as a
      replacement for guaranteed should first select a single level of
      controlled delay that it will use to serve guaranteed flows.  This
      level, i, can be any of the 3 levels of controlled delay service.
      The network element assigns the guaranteed service
      characterization parameter C the value 0.  The characterization
      parameter D can be assigned the value of the maximal packet delay
      seen in the last 3600 seconds for level i of controlled delay
      (this is one of the required characterization parameters for
      controlled delay service).  Alternatively, if the network element
      maintains maximal delays seen over longer intervals, or if it
      maintains internally a delay target that it attempts to meet for
      level i of controlled delay service, it can use either of those
      values for the characterization parameter D.  If there is no
      available value for the characterization parameter that is likely
      to be an upper bound on the packet delays experienced, the network
      element should set the validity bit associated with the
      characterization parameter (indicating that the characterization
      is not valid) and not compose the associated characterization
      value.

      When the network element receives a request for guaranteed
      service, it treats the request as if it were a request for
      controlled delay level i, with the TSpec as specified in the
      original request.

      The network element can characterize this replacement as either
      reliable or unreliable, depending on the likelihood that
      guaranteed packets will experience delays less than the value it
      exported for the characterization parameter D.

   Replacing Guaranteed Service with Best Effort.

      The network element assigns the guaranteed service
      characterization parameter C the value 0.  If the network element
      maintains values of delay experienced by best effort traffic, it
      can use a value of maximal delays seen over a fairly long interval
      for the characterization parameter D.  Alternatively, if the
      network element does not measure packet delays, it can estimate a
      suitable value for D based on such factors as the amount of buffer
      space available at the network element.  If there is no available
      value for the characterization parameter that is likely to be an
      upper bound on the packet delays experienced, the network element
      should set the validity bit associated with the characterization
      parameter and not compose the associated characterization value.

      Since best effort is not an admission controlled service, all
      requests for guaranteed service are accepted.

Breslau/Shenker              Expires ?/?/95                    [Page 12]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

      Such a replacement can be characterized as reliable if the network
      element is typically underutilized so that packet loss is
      infrequent, and if the network element has confidence that packet
      delays will be less than the value it exports for the
      characterization parameter D.  Otherwise, the replacement should
      be characterized as unreliable.

   Replacing Predictive Service with Guaranteed

      A network element replacing predictive service with guaranteed
      chooses a delay bound, DB_i, for each level i of predictive
      service.  The only constraint on these values is that they be
      larger than the characterization parameter D exported for the
      guaranteed service.

      The network element uses these delay bounds as the
      characterization parameters that describe the delay bounds for
      each level of predictive service.  Network elements providing
      guaranteed service are not required to maintain measures of packet
      delays.  Furthermore, because implementations of guaranteed
      service are likely to isolate flows from each other, delays
      experienced by existing guaranteed flows are not necessarily
      indicative of delays that new flows may experience.  Unless the
      network element maintains measures of packet delay that are
      indicative of delays that will be experienced by new flows, it
      should not attempt to compose the characterization parameters
      associated with actual delays experienced by predictive traffic,
      and it should set the validity bit associated with these
      parameters.

      When the network element receives a request for predictive
      service, it must compute an appropriate RSpec for guaranteed
      service.  It can compute the reserved rate, R, using the following
      formula:

      R = (b + C)/(DB_i - D)

      where b is the token bucket depth specified in the TSpec, C and D
      are the characterization parameters for the guaranteed service,
      and DB_i is the delay bound for the requested level of predictive
      service.

      The network element treats this as a request for guaranteed
      service with the TSpec as specified in the original request and
      the RSpec having the rate R as computed above.

      This replacement can be characterized as reliable.

Breslau/Shenker              Expires ?/?/95                    [Page 13]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   Replacing Predictive Service with Controlled Delay

      The network element uses the characterization parameters
      describing measured delays for controlled delay service as the
      corresponding characterization parameters for predictive service.
      For each level of service, the network element can use as a
      characterization parameter describing the delay bound either the
      maximal delay seen over the last 3600 seconds, the maximal delay
      seen over some longer interval, or any internal delay target it
      maintains in its controlled delay implementation.

      A request for predictive service is treated as if it were a
      request for the same level of controlled delay service.

      This replacement can be characterized as either reliable or
      unreliable, depending on the confidence the network element has
      that the delays experienced by predictive flows will be less than
      the delay bound characterization parameters it exports for
      predictive service.

   Replacing Predictive Service with Best Effort

      The network element exports the same characterization parameters
      for each level of predictive service.  The network element can use
      as characterization parameters describing the delay bounds some
      long term measure of maximal packet delay or some estimate of
      maximum possible delay based on such factors as the amount of
      buffer space available at the network element.  If the network
      element maintains measured values of maximal packet delays, these
      can be used as the characterization parameters describing maximal
      delays experienced.  Alternatively, configured values based on
      average load or buffer space at the network element can be used.
      If these values are not likely to accurately reflect the service
      delivered by the network element, the network element should set
      the validity bit associated with the characterization parameters
      and not compose the characterization value.

      Since best effort does not use admission control, all requests for
      predictive service can be accepted.

      Such a replacement can be characterized as reliable if packet loss
      is infrequent at the network element and if the network element
      has confidence in its ability to meet the delay bounds it exports
      for predictive service.

   Replacing Controlled Delay with Guaranteed

      This replacement is similar to the replacement of predictive

Breslau/Shenker              Expires ?/?/95                    [Page 14]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

      service with guaranteed described above, with the only difference
      being that the network element does not export characterization
      parameters describing delay bounds.  However, even though
      controlled delay service does not have a per service level delay
      bound, the network element must maintain such bounds so that the
      it can compute an appropriate service rate R.

      This replacement can be characterized as reliable.

   Replacing Controlled Delay with Predictive

      This replacement is trivial, as a conformant implementation of
      predictive service satisfies all requirements for controlled delay
      service and the two services use the same invocation parameters.
      In fact, rather than characterizing this as a replacement service,
      a network element offering predictive service can also claim to
      offer controlled delay service.

   Replacing Controlled Delay with Best Effort

      This replacement is similar to the replacement of predictive
      service with best effort.  The only difference is that
      characterization parameters describing delay bounds need not be
      exported.

      Such a replacement can be characterized as reliable if packet loss
      is infrequent at the network element.

Other Approaches

   Our solution is built on the notion of routers selecting appropriate
   replacements for the services they do not offer.  Also, we presented
   ways to provide applications with a limited amount of control over
   the actual use of these replacements.  Specifically, applications can
   allow the use of replacements, or have their requests rejected when a
   requested service is not offered.

   To put this solution in context, it is worth mentioning alternative
   approaches which we considered.  The option described above which
   provided applications control over whether or not replacement
   services are used is a constrained example of what we refer to as
   "reservation scripts".  Fully general reservation scripts allow the
   entity requesting service to specify a set of router actions to be
   taken when the requested service is not offered.  Thus, a reservation
   script could expand the set of router behavior to include use any
   replacement, use only reliable replacements, or use only the

Breslau/Shenker              Expires ?/?/95                    [Page 15]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   requested service (with no replacements).  While more general scripts
   would expand functionality by presenting applications with additional
   options, they also increase complexity.  This increased complexity is
   primarily manifested in the problem of merging scripts of users who
   desire different router actions.  We feel this additional complexity
   is not worth the functionality it provides.

   One can extend the idea of reservation scripts to have individual
   applications indicate which specific services should be used as
   replacements.  For example, an application could indicate that
   predictive service should be substituted if guaranteed is not
   offered.  This idea exacerbates the merging problems described above.
   In addition, and perhaps more importantly, we believe it places the
   responsibility for selecting replacements in the wrong hands.  Since
   the quality of service provided by best-effort and controlled delay
   services will likely depend a great deal on the ambient load
   conditions, the local router is much better equipped to make the
   decision about whether or not a given service can function as a
   reasonable replacement (if the router knows about the service).
   There may be a few exceptional cases where a particular application
   requirement would suggest a different substitution, but we are not
   convinced that such occurrences outweigh the considerable additional
   complexity such specific reservation scripts would introduce.

   A more limited but similar alternative we considered is to include an
   explicit list of services in the reservation request.  Upon receiving
   a reservation request, a router would scan the list of requested
   services until finding the first one that it knows about.  It would
   then process the request as a request for this service.  If this
   service is known, but not offered, the router would substitute a
   replacement;  it does not continue to scan the list of services for
   one it offers.  Thus, receiver specified replacement services are
   used only when the router does not know about the receiver's first
   choice service;  in all other cases, the decision about replacement
   services is left to the router.  Since it is specifically in
   situations where services are not known that routers lack sufficient
   information to make intelligent decisions about replacement services,
   this limited control exerted by the receiver might be useful.

   The options discussed above vary in the amount of functionality and
   flexibility they allow and in what entity, either the router or
   application, exerts control over the use of replacement services.
   Another approach would be for the working group to mandate router
   behavior when requested services are not offered.  For example, the
   working group could define specific services as replacements for
   others and mandate that routers always use these defined substitutes
   when services are not offered.  We view this as inferior to our
   proposal as it places the control over replacements in the wrong

Breslau/Shenker              Expires ?/?/95                    [Page 16]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   hands.  As mentioned previously, the suitability of one service to
   act as a replacement for another depends in some cases on the
   environment in which it is deployed.  Lacking information about where
   a service is deployed, the working group cannot make appropriate
   decisions.  For example, best effort service may in many
   circumstances be an adequate replacement for other services.
   However, given that it can also be arbitrarily bad, the working group
   could not define it as an acceptable replacement for any real time
   service.  As an alternative to specifying replacement services, the
   working group could mandate a uniform router behavior when services
   are not offered.  For example, the working group could require a
   default action of providing best effort service when a service is not
   offered.  While inviting because of its simplicity, we rejected this
   approach because it does not give enough control to applications.
   Specifically, it does not satisfy those applications that desire a
   strong assurance that an actual service, or a close facsimile of it,
   will be used.

Discussion

   In this section, we touch on three issues in the integrated services
   architecture that are relevant to this proposal.

   We stated earlier that this proposal only attempts to solve the
   problem of what to do when a requested service is not offered.  We
   did not address the question of what to do when a requested service
   is offered, but not available.  The latter problem is the subject of
   discussion within the RSVP working group.  Various issues and
   solutions discussed in that context are similar to those we
   considered.  For instance, upon an admission control failure, some
   applications may want an error message returned to them, while others
   may prefer to receive best effort service at the node in question
   while their original request is propagated to other nodes.  This is
   similar to the choice of returning an error message or using the best
   replacement service when a requested service is not offered.  The
   mechanisms needed to provide this functionality in the two contexts
   are similar.  We confined the current discussion to the problem of
   heterogeneity.  However, since the two problems are related, their
   eventual solutions ought to fit into a unifying framework.

   Within the Internet community, there is still a vigorous debate about
   whether the overprovisioning of best-effort links is a reasonable
   real-time architecture.  Our proposal to accommodate heterogeneity in
   the set of offered services would allow such overprovisioned best-
   effort networks to compete with networks supporting real-time

Breslau/Shenker              Expires ?/?/95                    [Page 17]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   services. That is, an over-provisioned network providing only best
   effort service could characterize this best effort service as a
   reliable replacement for real-time services.  Different service
   providers can thus experiment with different ways of meeting
   application needs without changing the service model. We think this
   is crucial in allowing us to learn while the Internet evolves.

   Finally, we note that even among those supporting the standardization
   and deployment of real-time services, debate over the nature and
   number of these services continues. We believe that heterogeneity
   will be an issue, regardless of what service model is defined for
   real-time services.  Even if only a single type of real-time service
   were to be specified, this service will not be universally deployed.
   Some routers will offer it and others will not.  However, we expect
   that the requirements of real-time applications differ enough to
   warrant multiple types of real-time service, each geared towards
   supporting different classes of applications.  Multiple classes of
   service, none of which will be offered everywhere, only serves to
   compound the problem of heterogeneity.

Specific Recommendations

   We recommend the following approach be adopted.

   For each service for which the element offers a strictly better
   replacement, the element must also support the lesser service (by
   providing characterization values for it, and making ordered
   substitutions of the service requests).

   For each service it knows about but does not offer, a router should
   select a suitable replacement service.  The router should
   characterize the replacement as reliable or unreliable.

   For each known service, a router should export information about
   whether it offers the service, whether it offers a reliable
   replacement, or whether it offers no reliable replacement.

   A router should attempt to export useful characterization parameters
   for each service it replaces.  These parameters should reflect, as
   much as possible, the service the router provides.  When the router
   is unable to export a meaningful value for a characterization
   parameter, it sets the validity bit associated with that
   characterization parameter.

   Setup protocols, or other mechanisms, may be used to collect
   characterization information about end-to-end service availability
   and about the characteristics of the resulting service.

Breslau/Shenker              Expires ?/?/95                    [Page 18]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

   Service requests should be augmented to include a single service
   replacement handling bit.  Service replacements are allowed when the
   bit is set. They are not allowed when the bit is not set.

   Applications should set the bit according to their requirements.
   Applications that receive end-to-end characterizations about service
   availability should always set the bit on indicating that
   replacements are allowed.  If they are not satisfied with the
   replacements that would be made, they should not issue a service
   request.

   When merging two service requests with different values for the
   replacement handling bit, the router should turn the bit off,
   indicating that replacements are not allowed.

   When a router receives a request for a service it does not offer, it
   rejects the request if the replacement handling bit is off.  If the
   bit is on, the router should treat the request as a request for its
   best replacement for the requested service.  If the replacement
   service uses admission control, the router should apply an admission
   control decision.  If the admission control test fails, the request
   is rejected.  The router's replacement does not affect the original
   request if it is propagated to other routers by a setup protocol.

   When a router receives a request for a service it does not know
   about, it should use best effort as a replacement service, if the
   replacement handling bit is on.  Otherwise it should reject the
   request.

   This proposal has some deficiencies when end-to-end characterizations
   are not available.  However, providing better behavior in this case
   requires substantial additional complexity, so we deem it advisable
   to first observe the extent to which end-to-end characterizations
   become part of the integrated services architecture.  If these
   characterizations become ubiquitously available, then this handling
   bit will become a vestigial relic and we will have avoided the
   additional complexity.  If end-to-end characterizations are rarely
   provided, then we will have to see how serious an impediment the
   error handling deficiencies are.

Security Considerations

   Security considerations are not discussed in this memo.

Breslau/Shenker              Expires ?/?/95                    [Page 19]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

References

   [1] S. Shenker and L. Breslau. "Two Aspects of Reservation
   Establishment", Proceedings of Sigcomm '95.

   [2] S. Shenker and J. Wroclawski. "Network Element Service
   Specification Template", Internet Draft, June 1995, <draft-ietf-
   intserv-svc-template-01.txt>

   [3] S. Shenker, C. Partridge, and J. Wroclawski. "Specification of
   Controlled Delay Quality of Service", Internet Draft, ?? 1995,
   <draft-ietf-intserv-control-del-svc-02.txt>

   [4] S. Shenker and C. Partridge. Specification of Guaranteed Quality
   of Service", Internet Draft, ?? 1995, <draft-ietf-intserv-
   guaranteed-svc-03.txt>

   [5] S. Shenker, C. Partridge, B. Davie, and L. Breslau.
   "Specification of Predictive Quality of Service", Internet Draft, ??
   1995, <draft-ietf-intserv-predictive-svc-01.txt>

Author's Address:

   Lee Breslau
   Xerox PARC
   3333 Coyote Hill Road
   Palo Alto, CA  94304-1314
   [email-masked]
   415-812-4402
   415-812-4471 (FAX)

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

Breslau/Shenker              Expires ?/?/95                    [Page 20]

INTERNET-DRAFT      draft-ietf-intserv-hetero-01.txt             ?, 1995

Breslau/Shenker              Expires ?/?/95                    [Page 21]