Subject: protected best effort service

From: Juha Heinanen <[email-masked]>
Date: Thu, 15 Feb 1996 17:23:18 +0200

hello,

someone may remember that in the dallas meeting i verbally proposed a
simple intergated service service that is based on best effort flows.
below is the first draft of a such service specification.  currently i
call the service "protected best effort", but better name proposals are
wellcome.

i would like to get a slot to discuss this proposal in the upcoming ietf
meeting and of course receive comments on the mailing list or privately
before the meeting.

-- juha

ps.  i just sent a message to be added to the int-serv mailing list.
since i may take some time to get on it, please include my email address
to your response.
-------------------------------

Internet Engineering Task Force                   Integrated Services WG
INTERNET-DRAFT                                             Juha Heinanen
draft-heinanen-pbe-svc-00.txt                       Telecom Finland Inc.
                                                       February 15, 1996

   Specification of the Protected Best Effort Network Element Service

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 draft has been submitted to 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.

Abstract

   This document specifies the Protected Best Effort (PBE) service that
   provides to the application an isolated best effort flow with a
   possible minimum bandwidth.

Introduction

   This document defines the requirements for network elements that
   support the Protected Best Effort (PBE) service.  The end-to-end
   behavior provided to an application by a series of network elements
   conforming to this specification is

   - fair share of the bandwidth available for PBE traffic along the
     path of the application's data flow or at least a minimum bandwidth
     whichever is larger,

Heinanen                 Expires July 15, 1996                  [Page 1]

INTERNET-DRAFT                PBE Service                   Feb 15, 1996

   - fair transit delay among the applications whose PBE data flows
     share the same network elements, and

   - ordered delivery of packets as long as the network path of the
     application's PBE data flow doesn't change.

   To ensure that the above behaviour can be met, an application
   requesting PBE service provides the network elements with a Minimum
   Requested Bandwidth (MRB).  A network element that correctly
   implements the PBE service, doesn't need to support MRB values > 0.

   The application may not assume succesful delivery of packets sent at
   a rate which is higher than the MRB, since there may not be more
   bandwidth available on the path for PBE traffic.  Further, the
   application may not assume any given upper bound for transit delay or
   jitter, since the number of PBE data flows that share the same
   network path can change dynamically.

Motivation

   The PBE service is intented to support any non-realtime applications
   that are developed for use in today's internets.  In particular, the
   PBE service is suitable for applications that don't require a given
   maximum delay or delay variation and that can't characterize their
   traffic requirements in terms of average data rates and maximum burst
   lengths.  The PBE service differs from the conventional
   (=unprotected) best effort service in that it guarantees bandwidth
   and delay fairness by isolating the PBE data flows from each other.
   If all the network elements along the path of the application's data
   flow support a greater than zero MRB, then the PBE service can also
   be used to provide an upper bound for the time it takes to transfer
   the information across the network.

Network Element Data Handling Requirements

   Each network element accepting a request for a PBE service must
   ensure that adequate network element and link resources are available
   to handle the requested level of traffic as given by the MRB in the
   requestor's TSpec.  This must be accomplished through active
   admission control.  A network element may employ statistical methods
   to decide whether adequate resources are available to accept the
   service request.

   Links are not permitted to fragment packets which receive the
   controlled-load service. Packets larger than the MTU of the link must
   be treated as nonconformant to the TSpec. This implies that they will
   be policed according to the rules described in the Policing section
   below.

Heinanen                 Expires July 15, 1996                  [Page 2]

INTERNET-DRAFT                PBE Service                   Feb 15, 1996

   The PBE service is invoked by specifying the data flow's requested
   traffic parameters (TSpec) to the network element. Requests placed
   for a new flow will be accepted if the network element has the
   capacity to forward the flow's packets as described above. Requests
   to change the TSpec for an existing flow should be treated as a new
   invocation in the sense that admission control must be reapplied to
   the flow. Requests that reduce the TSpec for an existing flow (in the
   sense that the new TSpec is strictly smaller than the old TSpec
   according to the ordering rules given below) should never be denied
   service.

   The TSpec consists of a rate (MRB), a minimum policed unit (m), and a
   maximum packet size (M).  MRB is measured in bytes of IP datagrams
   per second. Values of this parameter may range from 1 byte per second
   to 40 terabytes per second. Network elements must return an error for
   requests containing values outside this range. Network elements must
   return an error for any request containing a value within this range
   which cannot be supported by the element. In practice, only the first
   few digits of the MRB parameter are significant, so the use of
   floating point representations, accurate to at least 0.1% is
   encouraged.

   The range of values allowed for these parameters is intentionally
   large to allow for future network technologies. Any given network
   element is not expected to support the full range of values.

   The minimum policed unit, m, is an integer measured in bytes.  All IP
   datagrams less than size m will be counted against MRB as being of
   size m. The maximum packet size, M, is the biggest packet that will
   conform to the traffic specification; it is also measured in bytes.
   Network elements must reject a service request if the requested
   maximum packet size is larger than the MTU of the link.  Both m and M
   must be positive, and m must be less then or equal to M.

   The preferred concrete representation for the TSpec is one floating
   point number in single-precision IEEE floating point format followed
   by two 32-bit integers in network byte order.  The first value is the
   rate (MRB), the second value is the minimum policed unit (m), and the
   third is the maximum packet size (M).

Exported Information

   The PBE service is assigned service_name X.

   The PBE service has no required characterization parameters. Specific
   implementations may export appropriate measurement and monitoring
   information.

Heinanen                 Expires July 15, 1996                  [Page 3]

INTERNET-DRAFT                PBE Service                   Feb 15, 1996

Policing

   PBE traffic must be policed for conformance at every network element.

   All PBE traffic that exceeds either the flow's fair share of the
   network element's best effort resources or MRB*T over all time
   periods T (whichever is larger) is considered nonconformant and must
   be discarded.  For the purposes of this accounting, network elements
   must count packets that are smaller than the minimal policing unit to
   be of size m.

   The fair share of the flow is determined according to the max-min
   criteria [1-2].  In determining the number of best effort flows
   competing on the network element's resources, all unprotected best
   effort traffic must be counted as one flow.  The MRB of this flow is
   network element specific, i.e., the manager of the network element
   may choose to allocate some amount of bandwidth for unprotected best
   effort traffic.

   At all network elements, packets bigger than the outgoing link MTU
   must be considered nonconformant and thus discarded.

   (I would like to add to the TSpec Peak Rate parameter that tells the
   maximum bandwidth ever possibly available for PBE traffic on the
   current path and then police all PBE traffic also according to this
   parameter.  It doesn't namely make sense to allow traffic to the
   network that possibly can't get through at later network elements.
   The value of the Peak Rate parameter is determined using the path
   message.)

Ordering and Merging

   The PBE service TSpec is ordered according to the following rule:
   TSpec A is a substitute for ("as good or better than") TSpec B if and
   only if

   (1) MRB for TSpec A is greater than or equal to those of TSpec B,

   (2) the minimum policed unit m is at least as small for TSpec A as it
       is for TSpec B, and

   (3) the maximum packet size M is at least as large for TSpec A as it
       is for TSpec B.

   A merged TSpec may be calculated over a set of TSpecs by taking the
   largest MRB, smallest minimal policed unit, and largest maximum
   packet size across all members of the set.  This use of the word
   "merging" is similar to that in the RSVP protocol; a merged TSpec is

Heinanen                 Expires July 15, 1996                  [Page 4]

INTERNET-DRAFT                PBE Service                   Feb 15, 1996

   one that is adequate to describe the traffic from any one of a number
   of flows.

   The sum of n PBE service TSpecs is used when computing the TSpec for
   a shared reservation of n flows. It is computed by taking:

   - The minimum across all TSpecs of the minimum policed unit parameter
     m.

   - The maximum across all TSpecs of the maximum packet size parameter
     M.

   - The sum across all TSpecs of the parameter MRB.

   The perfect minimum of two TSpecs is defined as a TSpec which would
   view as compliant any traffic flow that complied with both of the
   original TSpecs, but would reject any flow that was non-compliant
   with at least one of the original TSpecs. This perfect minimum can be
   computed only when the two original TSpecs are ordered, in the sense
   described above.

   A definition for computing the minimum of two unordered TSpecs is:

   - The minimum of the minimum policed units m.

   - The maximum of the maximum packet sizes M.

   - The minimum of the rates MRB.

Guidelines for Implementors

   Network elements providing the PBE service are permitted to
   oversubscribe the available resources to some extent, in the sense
   that the MRB requirements indicated by summing the TSpec MRB values
   of all PBE flows may exceed the maximum capabilities of the network
   element. However, this oversubscription may only be done in cases
   where the element is quite sure that actual utilization is far less
   than the sum of the MRBs would suggest. The most conservative
   approach, rejection of new flows whenever the addition of their
   traffic would cause the sum of the MRBs to exceed the capacity of the
   network element, may be appropriate in other circumstances.

Evaluation Criteria

   The quality of a PBE implementation can be evaluated by measuring the
   degree of bandwidth and delay fairness it provides to PBE flows
   sharing the same network path.  In addition, it should be measured
   that the bandwidth available to a PBE flow is always at least MRB and

Heinanen                 Expires July 15, 1996                  [Page 5]

INTERNET-DRAFT                PBE Service                   Feb 15, 1996

   that unprotected best effort traffic can't get more resources than a
   single PBE flow can get.

   A bandwidth fairness is commonly measured using the so-called parking
   lot configuration.  The service is bandwidth fair if each flow
   receives an equal amount of bandwidth no matter how many network
   elements it has traversed.

   Delay fairness can be evaluated by measuring that the delay of a
   packets only depends on the number of the simultaneously active flows
   on the path.  The delay should increase linearly when new flows
   become active, but should not depend on the bandwidth of each flow.

   (A more detailed description of the evaluation criteria can be
   provided later.)

Examples of Implementation

   One possible implementation of the PBE service uses a fair queuing
   mechanism where each PBE flow and all unprotected best efforts flows
   together have their own queues that are serviced in a round robin
   fashion or at least so often that the flow can be guaranteed its MRB.

Security Considerations

   Security considerations are not discussed in this memo.

Acknowledgements

   This specification was created using the Controlled-Load Network
   Element Service specification [3] as the template.

References

   [1] Bertsekas, D., and R. Galager, Data Networks, Prentice Hall,
       1987.

   [2] Jaffe, J., Bottleneck Flow Control, IEEE Trans. Communications,
       July 1981.

   [3] Wroclawski, J., Specification of the Controlled-Load Network
       Element Service.  Internet draft, November, 1995.

Authors' Addresses

   Juha Heinanen
   Telecom Finland Inc.
   PO Box 228

Heinanen                 Expires July 15, 1996                  [Page 6]

INTERNET-DRAFT                PBE Service                   Feb 15, 1996

   FI-33101 Tampere
   Finland

   Phone: +358 400 500 958
   Email: [email-masked]

Heinanen                 Expires July 15, 1996                  [Page 7]

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 15 Feb 1996 16:45:53 -0500

> since i may take some time to get on it, please include my email address

Juha,

I'm hoping that Scott will just allow setting b==0 in the controlled
load draft.  Controlled load would then be a superset of what I think
you want in protected best effort (see below) and we wouldn't need
PBE.

As you define PBE is is exactly equal to controlled load with an
arbitrarily small value of "b" and requiring that non-conforming
traffic is dropped.  If what you are trying to do is tunnelling other
protocols like SNA and IPX (as you've stated in private) you would not
get very good service this way since the application would have to do
very good rate shaping to avoid policing.  Controlled load is actually
better since you get some queueing allowing for changes in the rate
shaping due to queueing along the way.  If you do WFQ with weights
based on the bandwidth spec and queue the nonconformant traffic as you
would normally queue elastic traffic (the suggestions I made wrt b==0
in controlled load) you would get much better service for tunnelled
protocols (a minimum bandwidth plus the ability to significantly
exceed that bandwidth if there is excess capacity).

If this is not what you intended, then I suggest that PBE as written
is already a subset of controlled load and need not be considered.

Curtis

---

From: Juha Heinanen <[email-masked]>
Date: Fri, 16 Feb 1996 11:31:16 +0200

curtis,

i see very little similarities between pbe and controlled load (that is
why i wrote the pbe draft).  if you read the en-to-end behavior section
of controled load, pbe doesn't match with either of its two key points:

- pbe doesn't promise that a very high percentage of transmitted packets
will be delivered (how much will be delivered depends on how much
capacity is available for pbe and what is the fair share of it)

- pbe doesn't promise that the delay experienced by a very high
percentage of the packets will not greatly exceed the minimum transit
delay (how much it is exceeded depends on the other traffic and the
number of simultaneously active pbe flows)

   traffic is dropped.  

looks like i have made a mistake in requiring that a non-conforming
traffic must be dropped. i did the thing too fast and thought that once
you have got your fair share (or minimum), the rest of the traffic must
be dropped, since they is no bandwidth left anymore.  this is, of
course, only the case when all sources are persistent.  

i'll try to rewrite that portion of the text after which your further
concerns below shouldn't apply.  thanks for pointing out an obvious
error.

-- juha

   If what you are trying to do is tunnelling other

   Curtis

---

From: "Steve Blake" <[email-masked]>
Date: Fri, 16 Feb 1996 10:22:09 +22299804

> call the service "protected best effort", but better name proposals are

  How about "Guaranteed Bandwidth"?

>    must count packets that are smaller than the minimal policing unit to

  Juha, I'm confused about what you are trying to propose.  Are you saying
that the policing function is:

  cumulative_bits(t)  <=  MRB * t  ?

If so, then what you are asking is for the node to police your traffic
with a token bucket with rate = MRB and size = infinity which starts out
empty.  This would give very little control over the transient behavior
of the traffic.  Alternatively, are you proposing that the source be policed
with a sliding window?  If that is the case, then you must specify a
minimum window interval, otherwise, a conformant implementation can
strictly police your instantaneous rate to MRB.

  The scheduling implementation of this service looks identical to
guaranteed delay, where the receiver reserves MRB (although I suppose GD
doesn't promise fair sharing of excess link capacity).  In addition to
MRB, why don't you include a buffer space request (BR) in the Tspec and Rspec?
The implementation could discard packets that fell off the end of a BR-sized
buffer under congestion, and the source could emulate this and pace itself
with an (MBR, BR) token bucket if it was sensitive to packet loss.  Of
course, in that case you would have a service essentially identical to
guaranteed delay...

/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
| Steven L. Blake              [email-masked] |
| Access Technology Architecture      (919)254-2030 |
| IBM Networking Hardware Division                  |
| "You like the 'Net?  You ain't seen nothin' yet!" |
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/

---

From: Juha Heinanen <[email-masked]>
Date: Fri, 16 Feb 1996 19:40:16 +0200

might be ok, but since MRB > 0 need not to be supported, the name may
sound misleading.

i tried to say that the policing is based on a sliding window. i guess
that the window interval T can't be arbitralily small, but i'm not an
expert on this.  i guess it would be always ok to blast one max size
packet at line rate.  i'm clad to receive suggestion on how to correctly
express this.

as i told earlier, i had a mistake in the policing section.
nonconforming packets should not be discarded if there is still buffer
resources available for new packets belonging to conforming flows.
below is a new try of that section.

-- juha
---------------
PBE traffic must be policed for conformance at each network element. All
PBE traffic that exceeds either the flow's fair share of the network
element's best effort resources or MRB*T over all time periods T
(whichever is larger) is considered nonconformant.  For the purposes of
this accounting, network elements must count packets that are smaller
than the minimal policing unit to be of size m.

The fair share of the flow is determined according to the max-min
criteria [1-2].  In determining the number of best effort flows
competing on the network element's resource, all unprotected best effort
traffic using that resource must be counted as one single flow.  The MRB
of this flow is network element specific, i.e., the manager of the
network element may choose to allocate some amount of bandwidth for
unprotected best effort traffic.

A network element may discard any nonconforming PBE packets, but should
not do so as long as it has enough buffering resources available to
protect conforming PBE flows, i.e., flows that are currently using less
than their fair share of the network element's resources.  Conversely,
the network element must discard nonconforming packets if buffering
resources would not otherwise be adequate to accommodate new packets
belonging to conforming PBE flows.