[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04

TSVWG Working Group
INTERNET-DRAFT                                              L. Westberg
                                                          Z. R. Turanyi
                                                             D. Partain
                                                               A. Bader
                                                               Ericsson

                                                   Georgios Karagiannis
                                        University of Twente / Ericsson

                                                       December 1, 2005




                   Load Control of Real-Time Traffic
                     draft-westberg-loadcntr-04.txt




Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   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".

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on June 1, 2006.







Westberg, et. al.                                               [Page 1]


Internet Draft                                              Load Control


Abstract

   There is an increased interest of simple and scalable resource
   provisioning solution for Diffserv networks. This is an updated
   version of the old draft (previous version was submitted in
   April 2000) describing a concept called Load Control.

   Load Control addresses the following issues:

     1. Admission control for real time data flows in stateless domains

     2. Dropping of flows in case of exceptional events, such as
        severe congestion after re-routing

   Admission control in a stateless domain can be a measurement-based
   access control, whereby a probe packet is sent along the forwarding
   path in a network to determine whether a flow can be admitted based
   upon the current congestion state of the network. If measurement-
   based method is not sufficient a lightweight reservation of a certain
   amount of network resources can be performed.

   Load Control uses two-bit markers in packet headers to carry load
   information from core routers to edge devices. The scheme provides
   the capability of controlling the traffic load in the network
   without requiring signaling or any per-flow processing in the
   core routers. The complexity of Load Control is kept to a minimum
   to make implementation simple.


   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED",  "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].


Westberg, et. al.                                               [Page 2]


Internet Draft                                              Load Control


Table of Contents

1 Background and Motivation .......................................    4
2 Overview ........................................................    5
3 Operation of Load Control .......................................    5
3.1 Simple Marking ................................................    6
3.2 Unit-based Reservations .......................................    7
3.3 Multiple Unit reservation .....................................    8
3.4 Codepoints for Flow Types .....................................    9
4 Objects for Standardization .....................................    9
4.1 Packet Types ..................................................    9
4.2 Coding of Packet Types ........................................   10
4.3 Behavior Description ..........................................   10
4.3.1 Behavior of the Core Routers ................................   10
4.3.2 Behavior of the Edge Devices ................................   11
5 Interworking with RSVP/Intserv ..................................   11
6 Security Considerations .........................................   12
7 Identification of Edge Nodes ....................................   12
8 IANA Considerations.............................................    12
9 Informative References..........................................    13
 Appendix A. Admission Precision of Simple Marking ................   14
 Appendix B. Effect of Delays on Admission ........................   14
 Appendix C. A Simple Algorithm for Core Routers ..................   15
 Appendix D. Simulation Results ...................................   16
 D.1 Simple Marking ...............................................   17
 D.1.1 Constant Bit-Rate Sources ..................................   17
 D.1.2 On/Off Sources .............................................   17
 D.1.3 The Router Algorithm .......................................   18
 D.2 Unit-Based Reservations ......................................   18
 Appendix E: Marking using ECN bits ...............................   19

Westberg, et. al.                                               [Page 3]


Internet Draft                                              Load Control

1.  Background and Motivation

   The amount of traffic carried on the Internet is now greater than the
   traffic on the world's telephony network. Still, Internet-based
   communication services generate less income than plain old telephony
   services. Enabling value-added services over the Internet is
   therefore crucial for service providers. One significant class of
   such value-added services requires real-time packet transportation.
   It can be expected that these real-time services will be popular as
   they replicate or are natural extensions of existing communication
   services like telephony.  Exact and reliable resource management
   (e.g., admission control) is essential for achieving high utilization
   in networks with real-time transportation capabilities. The problem
   is difficult mainly due to scalability issues.

   With the introduction of differentiated services (DS) [RFC2475], it
   is now possible to provide large scale, real-time services. The basic
   idea of DiffServ is that, rather than classifying packets at each
   router, packets are only classified at the edge devices.  The result
   - the required packet treatment - is stored and carried in the packet
   headers, and core routers can carry out appropriate scheduling.

   The current definition of DiffServ, however, does not contain any
   simple, scalable solution to the problem of resource provisioning and
   control. A number of approaches to solving the problem already exist
   [Berson97, Guerin97, Stoica99, Bernet99].  The scheme presented in
   this document does not require any state aggregation and aims at
   extreme simplicity and low cost of implementation along with good
   scaling properties. Load control operates edge-to-edge in a DS
   domain, or between two RSVP or NSIS capable routers, where only the
   edge devices keep flow state and do per-flow processing.  The main
   purpose of Load Control is to provide a simple and scalable solution
   to the resource provisioning problem.

   Note that the last version of this draft was submitted in April 2000.
   The original Load Control concept has been developed further to a
   signaling concept named Resource Management in Diffserv.  RMD was
   incorporated by NSIS working group, where the protocol details were
   worked out for using NSIS as external protocol [RMD]. Recently new
   drafts have been submitted aiming to standardize new Diffserv PHB
   and define an architecture providing controlled load services in
   Diffserv domains [CL-Diffs, CL-PHB]. These proposals are very similar
   to the two-bit marking scheme of Load Control. The major differences
   are that in the admission control is based on the marking of the data
   packets, i.e. without sending probe packets, and it proposes marking
   of the ECN field.  This document aims to develop a common framework
   that could be used both with RSVP and NSIS external protocols.

Westberg, et. al.                                               [Page 4]


Internet Draft                                              Load Control

2.  Overview

   Load control is achieved by two actions: admission control of
   incoming requests and the dropping of admitted flows in case of
   exceptional events such as link failures.  Load Control uses
   two-bit markers in the probe packet headers to gather information
   about the load level along various paths through the network.  In
   addition, the core routers are able to mark passing packets to signal
   the exhaustion of resources to the edge devices.

   For admission control, the resource state of core routers is gathered
   by sending a specially marked packet, denoted a "probe" packet, from
   the ingress to the egress edge device.  The probe result is then used
   by the ingress to decide flow acceptance or rejection and to set up
   traffic conditioning/policy.  If rigid admission control is required,
   soft-state based reservations are also supported. In this case the
   probe packet does both the probing and allocation of resources along
   the path. The latter method is comparable to signaling based schemes
   but does not require processing of signaling messages in the core
   routers.

   Under normal circumstances, admission control is enough to control
   the load in the network. Nevertheless, when exceptional events (such
   as link failures) cause too much traffic to be re-routed over a link,
   the resulting severe congestion may degrade the quality of all of the
   flows on the link. In that case, the best solution might be to keep
   existing flows and suffer the loss of quality. However, for some
   services, it may be desirable to drop some of the previously admitted
   flows to protect the quality of the remaining flows. Thus, when
   severe congestion occurs, the core routers mark the headers of all
   (not only probe) packets to notify the edge devices of the congestion
   condition.

   In the following sections, we assume a DS (DiffServ) domain where
   connection requests arrive at the edges of the domain via RSVP, NSIS
   QoS NSLP at the request of a Bandwidth Broker, or by other means.
   The requests may be generated directly at the edge by a gateway,
   which provides connection to other types of networks, or in hosts
   that are connected directly to the domain.


3.  Operation of Load Control

   The Load Control scheme has two modes of operation:

      a) 'Simple marking':  This refers to a measurement-based admission
      scheme where routers measure the traffic volume and base the
      marking on these results.

Westberg, et. al.                                               [Page 5]


Internet Draft                                              Load Control

      b) 'Unit-based reservations':  A "unit" represents a share of
      bandwidth in the network that could be reserved by the edge
      devices.  This mode makes it possible to perform resource
      reservations, independently of the amount of traffic that is
      actually transmitted.

   Both modes can perform admission control of incoming requests and
   indicate exceptional events.

   In the appendices, we present some analysis of Load Control
   properties, but a more detailed investigation can be found in
   [Tur99].


3.1.  Simple Marking

   The idea of simple marking is that core routers measure the traffic,
   and, if they encounter near exhaustion of resources, they mark
   passing probe packets and thereby notify the edge devices of the lack
   of resources.

   The scheme has the following steps of operation:

      1) Resource Probing: Before establishing the flow, the initiating
      edge device sends a probe packet into the network.  The probe
      packet passes through the same routers as the actual traffic will
      pass through (in any case, with a high degree of probability) and
      is exposed to the marking function in each router. The marking
      performs an OR-operation of its own status and the incoming probe
      packet status (a packet once marked must not be changed).  When
      the packet reaches the egress edge device, its header will reflect
      the aggregated resource status along that path.

      2) Send resource status to ingress: When the egress edge device
      receives the probe packet, it copies the marker from the header to
      the header/payload of a reverse packet and sends it back to the
      initiating party (the ingress edge device). The probe packet may
      be discarded, converted to an ordinary data packet, or
      encapsulated (as mentioned above) and sent to the ingress edge
      device. The packet containing the probing result can also serve as
      a probe packet for the reverse path. This allows the initiating
      party to check for bi-directional resources.

      3) Acceptance/Rejection: The report packet is returned to the
      initiating ingress edge device, which uses the result of the probe
      to admit or block the request by setting up appropriate packet
      filtering, measuring, and marking rules.

Westberg, et. al.                                               [Page 6]


Internet Draft                                              Load Control

      4) Reaction to exceptional events: If a core router detects severe
      congestion on an interface, it starts marking the data packets on
      that interface. If the egress edge device receives a marked packet
      which is not a probe packet, this can be interpreted as a sign of
      severe congestion along the path.  The fact that the incoming
      marked packet was not sent as a probe packet can be determined
      from the packet content, by multi-field classification or by
      checking the admittance state at the egress edge device.  If
      severe congestion occurs, a signaling message can be sent to the
      ingress edge device, which can then take the appropriate action,
      e.g. preempting active flows between the corresponding ingress and
      egress edge.

      The marking process of interior routers should be a standard
      method. The simplest solution all packets are marked. If
      the number of marked packets are proportional to the overload or
      proportional to the number of lost packets egress edge will
      receive information about the overload and can terminate a number
      of flows that is necessary to restore normal operation.

   To make the scheme more robust against packet loss, the initiating
   edge device MAY maintain a timer associated with each probe packet.
   If a probe packet is lost, the device simply re-transmits on time-
   out.  How often and how many times the probe packet should be
   retransmitted before failure is declared is an implementation issue,
   but these parameters SHOULD be configurable (e.g., via an SNMP MIB).
   Furthermore, whether probes are retransmitted at all SHOULD be
   configurable.


3.2.  Unit-based Reservations

   While measurement-based admission control has important advantages
   over non-measurement based algorithms, it has disadvantages as well.
   Unit-based reservations allow the sources to keep their reservations
   irrespective of the volume of the traffic they transmit.  Although
   the admission scheme is very similar to the simple marking case, the
   presence of actual reservations is a fundamental difference.

   Each flow can occupy any number of units of resources, and even
   fractions of units by allowing a number of flows to share a common
   resource unit.  The unit is not necessarily a simple bandwidth value:
   it may be defined in terms of any resource unit (e.g., effective
   bandwidth) to support statistical multiplexing at packet level (use
   of silence period). The definition of the unit may vary from network
   to network and is outside the scope of this document.  The basic idea
   of unit-based reservation is to allow the edge devices periodically
   to mark some of the data packets to refresh resource reservation.
   Each refresh packet reserves one unit of resources for one refresh
   period. Reservations are timed out after a refresh period and have to
   be refreshed in a soft state manner.  The length of the refresh
   period must be the same throughout the DS domain and SHOULD be
   configurable.

Westberg, et. al.                                               [Page 7]


Internet Draft                                              Load Control


   Core routers estimate the number of reservations by counting the
   number of refresh packets during a refresh interval. If the router
   runs out of units, it goes into blocking state, starts to mark probe
   packets indicating congestion and thereby rejects new flows.  The
   probe packets that pass the router unmarked and the refresh packets
   reserve one unit of resources for the following refresh period.
   (Editor note:  It is clear that we need to have the capability of
   reserving more than one unit, but it is not yet clear how that will
   be encoded in the packet header.  See below.) Thus, after the probe
   packet has passed along the path unmarked, the ingress edge device is
   required to send the first reservation refresh packet during the next
   refresh period.

   If a flow occupies more than one unit, more than one probe packet may
   be sent to allocate the required number of resources (an alternative
   using only one packet should be defined).  Similarly, more than one
   refresh packet must be sent for such a flow. By proper definition of
   the unit, a wide range of flows can be described and handled using
   this simple mechanism.

   If a probe packet was forwarded unmarked by a core router, but was
   marked later downstream, that core router will not be notified and
   will incorrectly maintain the reservation. However, as the flow is
   rejected, no refresh packets will arrive, and the reservation will
   time out at the end of the refresh period and will be released.

   Severe congestion is handled in the same way as in 'Simple marking'
   (see below).

   If a refresh packet is lost, the downstream routers will
   underestimate the number of reserved units. Refresh and probe packets
   should therefore be protected from losses in the manner described
   above.

   Core routers estimate the number of allocated units by counting the
   number of refresh packets during a refresh period.  The accuracy of
   the estimate can be increased by generating refresh packets evenly
   spread in time over the refresh period. This minimizes errors
   resulting from time alignment differences between routers and edge
   devices.


3.3.  Multiple Unit reservation

   In some cases it might feasible to add functionality for reservation
   of several units in one single reservation request.  A similar
   semantic (as the two-bit reservation scheme) could be used to provide
   such functionality but it will of course require addition of a
   integer value denoting the number of units.

   The coding of such proposal is still under discussion and needs to
   studied further.

Westberg, et. al.                                               [Page 8]


Internet Draft                                              Load Control

3.4.  Codepoints for Flow Types

   In both variants of Load Control, routers making marking decisions
   have very little information about the resource or QoS requirement of
   the flow in question. The DS field of the probe packet can be used to
   indicate the DiffServ class the flow will arrive on and thus the QoS
   requirements.  The marking function of core routers can take the
   required PHB into account when deciding on the marking.

   Information on the resource requirements for incoming flows can also
   be expressed using the DS field by dividing real-time traffic into
   classes based on resource requirements and using different codepoints
   for different classes. If the DSCPs denote not only the PHB that the
   flow is to receive, but implicitly also the bandwidth requirements
   for the flow, core routers will be able to mark packets more
   intelligently, resulting in less resource waste and greater
   flexibility.

   In the unit-based case, the major benefit is that the size of the
   unit can be different in different classes, making it possible to
   allocate resources with finer granularity.


4.  Objects for Standardization

   A forthcoming standard might only include the encoding of the Load
   Control information into the IP header and some design
   recommendations.


4.1.  Packet Types

   We need four types of packets in the algorithm:

      - Ordinary Packet (OP)
      - Probe Packet (PP)
      - Marked Packet (MP)
      - Refresh Packet (RP)

   During transport through the network, a probe packet can be changed
   to a marked packet. This indicates that at least one router does not
   accept the reservation associated by the probe packet.

   ------       Rejection       ------
   | PP |---------------------->| MP |
   ------                       ------

   An ordinary packet can also be changed to a marked packet, meaning
   that some exceptional event caused severe congestion on one link of
   the path the packet took.

Westberg, et. al.                                               [Page 9]


Internet Draft                                              Load Control

   ------  Severe Congestion   ------
   | OP |---------------------->| MP |
   ------                       ------

   In the simple marking scheme, only three packet types are used.
   Refresh packets are treated as ordinary packets, except
   that these packets cannot be changed to marked (MP) packets.


4.2.  Coding of Packet Types

   We have two alternative solutions for storing Load Control related
   information in the packet headers: using new DS codepoints or using
   the two currently unused bits (intended for ECN) in the DS byte.  The
   latter case is only considered in Appendix E.

   In the first alternative (where PHBs are intended to be used together
   for Load Control), two or three new codepoints would have to be
   defined for probe, marked and (optionally) refresh packets. For
   example, in the case of the EF PHB, in addition to the codepoint used
   for the EF packets, EF-probe, EF-marked and EF-refresh packets can
   also be sent. The new codepoints can be drawn from the LU/EXP space.


4.3.  Behavior Description

   The behavior of the edge devices depends greatly on the application
   or signaling protocol that uses the load control scheme. Below we
   only describe the few aspects of the edge device behavior that are
   necessary for inter-working with the core routers.


4.3.1.  Behavior of the Core Routers

   All core routers continuously maintain a state of accepting or
   rejecting more flows.  If the state is accepting, the router passes
   all packets unchanged. If the state is congestion, then the router
   changes the marking of incoming packets from probe (PP) to
   marked (MP).

   If the router is capable of detecting severe congestion, and this
   occurs, then the router forwards both ordinary (OP) and probe packets
   (PP) as (MP) marked.  The router MUST NOT change the marking of
   refresh packets (RP).

   Addition for Unit-based Reservations:

      The router uses the refresh and probe markers in packets to
      maintain its estimation of reserved resources. A refresh packet
      signals previously admitted resource usage, while a probe packet
      signals a new request. When passed unmarked, both types of packets
      reserve one unit for one refresh period.

Westberg, et. al.                                              [Page 10]


Internet Draft                                              Load Control


4.3.2.  Behavior of the Edge Devices

   When a new reservation is needed, the ingress edge device should send
   the appropriate number of packets marked as probe.
   If the egress edge device receives a probe packet that is marked,
   this means that the network has insufficient capacity along the path
   between the two edge devices. The egress edge device should take care
   of blocking the flow by notifying the ingress device.  If the egress
   device receives marked (MP) packets that are not initially sent as
   probe packets, it shall use a policy function in the egress node to
   calculate the number of admitted flows that have to be terminated.
   This information shall be sent towards the ingress device to reject
   these admitted flows. This can be determined from the packet content,
   multi-field classification of the IP header, or by checking the
   admittance state at the egress edge device.

    Addition for Unit-based Reservations:

      For the unit-based reservation scheme, the ingress edge device
      should generate the required number of refresh packets per refresh
      period and per flow. If there are not enough data packets to mark
      as refresh packets, the ingress device must generate dummy packets
      and mark those as refresh packets.  The generated refresh packets
      should be as uniformly distributed through the refresh interval as
      possible to minimize the effect of refresh interval timing between
      routers.


5.  Interworking with RSVP/NSIS Intserv

   Load control can also be used in DiffServ regions (backbones) that
   connect RSVP/Intserv regions. This inter-operation is described in
   detail in [Bernet99]. For load control, border routers of the
   DiffServ region must be RSVP-aware in order to detect the arrival of
   new connections.

   RSVP PATH messages can be used as probe packets to gather congestion
   information along the path between the two border routers. When a new
   RSVP path state is installed at the egress border router, the
   collective admission state of the path (collected in the packet of
   the PATH message) is also stored. If a RESV message for the installed
   state arrives within a time period during which the congestion state
   can be considered valid, then the egress border router can perform
   the admission control for the DiffServ network as well. If the first
   RESV message arrives too late, then the egress border router MUST
   solicit a new (dummy) probe packet from the ingress router to
   determine the current congestion state.

Westberg, et. al.                                              [Page 11]


Internet Draft                                              Load Control

   When the egress receives a marked packet that is not a PATH message
   nor a dummy probe packet, this signals a severe congestion state
   along the path. The identity of the ingress router can easily be
   determined from the path state, but in this case the egress router
   can itself decide to drop certain reservations. The ingress router
   can be notified via ResvTear messages while the receiver end systems
   get ResvErr messages.

   RSVP routers can also be placed inside the domain. In this case,
   probing is performed between RSVP routers instead of edge devices.
   Thus adding a simple and cheap extension to non-RSVP capable routers,
   correct admission control is possible on non-RSVP capable parts of an
   end-to-end path.

   Unit-based reservations can also be used to provide resources in a DS

   domain that is used to provide VPN tunnels between customer sites.
   Using a load control scheme, it is fast and easy to modify the size
   of these tunnels. Thus, tunnel size selection can be a very dynamic
   process. Note that tunnels are not necessarily real-time tunnels.
   Packets of any DSCP can travel on them after receiving the
   appropriate PHB. Even best-effort tunnels can be reserved this way.
   Provisioning can be done on a per-DSCP basis or in aggregates as the
   service provider wishes.

   The inter-working with NSIS is discussed in RMD draft in detailed
   [RMD]. Since QoS-NSLP can be used for sender initiated reservation
   the Reserve message can be used as probe packets.


6.  Security Considerations

   We propose using two-bit markers in packet headers (DS field) to
   reserve resources within a DiffServ domain. This poses similar
   security problems to the use of the DS field to differentiate packets
   in general [RFC2475].

   If the interior of the DS domain fully contains a tunnel, then by
   copying the outer marking into the inner header at de-encapsulation,
   load control can be exercised over the links of the tunnel as well.
   The procedure is similar to the one described in [RFC2481]. As IPSec
   [RFC2402, 2406] does not allow the copying of the DS field from the
   outer to the inner header at de-encapsulation, load control cannot be
   exercised over regions where IPSec tunnels are used.


7.  Identification of Edge Nodes

   In the absense of RSVP, an alternative method for identification of
   edge nodes will be required.  This section needs to be written.


8.  IANA Considerations

Westberg, et. al.                                              [Page 12]


Internet Draft                                              Load Control

To be included in later versions


9.  Informative References

[RFC2406] Kent, S. and R. Atkinson, "IP Encapsulating Security Payload
   (ESP)", RFC 2406, November 1998.

[Bernet99] Bernett, Y., Yavatkar, R., Ford, P., Baker, F., Zhang, L.,
   Speer, M., Braden, R., "Interoperation of RSVP/Intserv and Diffserv
   Networks", Work in Progress, March 1999

[Stoica99] Stoica, I., et al "Per Hop Behaviors Based on Dynamic Packet
   States", Work in Progress, February 1999

[Berson97] Berson, S. and Vincent, R., "Aggregation of Internet
   Integrated Services State", Work in Progress, December 1997.

[Guerin97] Guerin, R., Blake, S. and Herzog, S.,"Aggregating RSVP based
   QoS Requests", Work in Progress, November 1997.

[Gross99] Grossglauser, M., Tse, D. N. C., "A Time-Scale Decomposition
   Approach to Measurement-Based Admission Control", Infocom '99

[Tur99] Z. R. Turanyi, L. Westberg "Load Control: Lightweight
   Provisioning of Internet Resources" submitted to Networking 2000,
   Paris, May 2000, http: //www.ericsson.co.hu/ethzrt/

[IAB-QoS] G. Huston (Internet Architecture Board), "Next Steps for the
   IP QoS Architecture", Work in Progress, March 2000.

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
   Requirement Levels", BCP 14, RFC2119, March 1997.

[RFC3168] Ramakrishnan, K., Floyd, S., Black, S., "The Addition of
   Explicit Congestion Notification (ECN) to IP", RFC3168, Sept. 2001.

[RMD] Bader, A., et al., "RMD-QOSM: An NSIS QoS Signaling
   Policy Model for Networks, Work in Progress, Oct. 2005

[QoS-NSLP] Manner, J., et al., "NSLP for Quality-of-Service
   Signaling," Work in progress, Oct. 2005

[CL-Diffs]  Briscoe, B. et al. "A Framework for Admission Control over
   DiffServ using Pre-Congestion Notification", draft-briscoe-tsvwg-cl-
   architecture-01.txt, Work in progress, Oct 2005,;

[CL-PHB]  Briscoe, B. et al. "The Controlled Load per hop behaviour"
   draft-briscoe-tsvwg-cl-phb-00.txt, Work in progress, July 2005

[Floyd05] Floyd, S., "Specifying Alternate Semantics for the Explicit
   Congestion Notification (ECN) Field", Internet-draft
   draft-floyd-ecn-alternates-02.txt, work in progress, August 2005.

Westberg, et. al.                                              [Page 13]


Internet Draft                                              Load Control

Appendix A. Admission Precision of MBAC Simple Marking

   Simple marking is basically a measurement-based admission control
   scheme, where flows do not say anything about their traffic
   characteristics. In addition, flow departure is not signaled
   explicitly.

   When the network carries more types of flows with different bandwidth
   requirements, the core routers do not know the bandwidth requirements
   of the incoming flows. They simply declare whether they will accept
   more flows or not irrespective of the bandwidth demands of the new
   flow. Thus the marking algorithm in the routers should conservatively
   always expect the largest type of flow that the network carries and
   start rejecting flows when there is not enough bandwidth left for one
   such flow.  On the positive side, this will result in fair rejection
   among different flow types, but on the negative side, some bandwidth
   will be wasted.  However, if the links of our domain can carry at
   least several hundred requests even from the most bandwidth-demanding
   types of flow, then this is not a significant waste.


Appendix B. Effect of Delays on Admission

   When a probe packet is passed unmarked without correcting the
   estimate of the free resources, we in fact admit a flow without
   immediately reserving resources for it.  The reservation will be
   implicitly done later by the arriving traffic or refresh packets of
   the flow. During the time between admission and the arrival of the
   traffic of the flow, new requests can be admitted without taking the
   previously admitted flow into account.  To illustrate the effects of
   this delay, we took an old and simple Markovian example. Flows are
   identical with an average flow-holding time of 180 seconds and flow
   arrivals and departures follow a Poisson process. Let the link be
   able to carry N calls and let the delay be T. The link starts
   refusing flows when the measured traffic exceeds N-H calls. We can
   say that a space of size H is put aside to cater for the errors
   caused by the delay.

   If the link is properly dimensioned, then the usual blocking ratio
   should not exceed 1%. However, in a mass call situation (such as
   occurs at New Year's Eve for example) it can be considerably higher.
   In this example, 50% blocking was chosen to demonstrate the extreme
   load case. Thus, the offered traffic is roughly twice the link
   capacity.

   QoS violation occurs if during time T the difference between the
   number of arriving and departing flows is larger than H. Under the
   above assumptions, the chance of QoS violation can be calculated.
   Naturally the larger H is, the less the chance is that QoS will be
   violated. The required value of H can be determined for a low value
   of QoS violation probability (e.g.  10e-5).

Westberg, et. al.                                              [Page 14]


Internet Draft                                              Load Control

   The following table presents the value of H as a function of link
   size (N), delay length (T) and load (causing 1% or 50% blocking).

         |    1ms    |   10ms    |   100ms   |   500ms   |     1s    |
         | 1%  | 50% | 1%  | 50% | 1%  | 50% | 1%  | 50% | 1%  | 50% |
   ------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
      50 |  2  |  2  |  2  |  3  |   3 |   4 |   4 |   5 |   5 |   7 |
     100 |  2  |  2  |  3  |  3  |   4 |   4 |   4 |   7 |   6 |   9 |
     500 |  2  |  3  |  3  |  4  |   4 |   7 |   9 |  13 |  12 |  18 |
    1000 |  3  |  3  |  4  |  4  |   5 |   9 |  12 |  18 |  16 |  25 |
    5000 |  3  |  4  |  5  |  7  |  12 |  18 |  24 |  44 |  33 |  69 |
   10000 |  4  |  4  |  7  |  9  |  16 |  25 |  33 |  69 |  47 | 113 |

   The amount of required safety margin is highest for small links,
   since less statistical multiplexing is possible there.


Appendix C. A Simple Algorithm for Core Routers

   In this appendix, we present an algorithm for core routers that use
   unit-based reservations. The algorithm is simple, so it can be easily
   implemented in hardware by simple counters. Its inputs are the
   refresh interval and the number of flows allowed on the link. The
   latter is denoted by <threshold>. (We assume flows with similar
   characteristics (e.g., voice) and that one flow sends one refresh
   packet per refresh interval.) If the network uses more DSCPs for
   real-time traffic, then a separate copy of the algorithm may be run
   for each DSCP, resulting in per-DSCP admission.

   The algorithm counts the number of refresh and admitted probe packets
   in refresh intervals (<count>). The result of the counting is an
   upper limit on the number of units reserved on the link, as some
   reservations may have gone by the end of the refresh interval. The
   value of this counter is used in the next interval to decide on
   admission (<last>). When a new reservation is admitted, this value is
   increased to take the new reservation into account. If this value is
   high above the admission limit, then we start sending severe
   congestion notifications by marking regular packets as well.

Westberg, et. al.                                              [Page 15]


Internet Draft                                              Load Control

      On initialization:
         last = 0
         count = 0

      On arrival of a refresh packet
         count++

      On arrival of a probe packet
         if last < threshold then
            last ++
            count ++
         elseif
            Mark Packet
         endif

      On arrival of a regular packet
         if last < threshold*1.1 then
            Mark Packet
         endif


      At the end of the refresh interval
         last = count
         count = 0


Appendix D. Simulation Results

   The purpose of the simulations described in this appendix is to give
   some insight into the performance of load control. The simulation
   cases are by no means representative, and the scheme may work
   differently in other situations. In section C.1, the simple marking
   case is demonstrated with a purely measurement-based admission
   algorithm by using a single link with both constant bit-rate and
   on/off sources. In appendix C.2, the unit-based reservation method is
   shown, using the algorithm in appendix B.

   Severe congestion signaling is not used in any of the examples; only
   admission control is used.

   We simulated a very simple network of one link. This can be viewed as
   the single bottleneck in the domain. The link had a 2 Mbit/s
   throughput, 50% of which was designated to carry real-time traffic.
   The round trip propagation delay was set to 100ms. The real time
   flows arrived according to a Poisson process, holding time was
   exponential with a 90 second mean. The arrival rate of flows was set
   to produce approximately 50% blocking. Only real-time traffic was
   simulated, so scheduling was simple FIFO.

Westberg, et. al.                                              [Page 16]


Internet Draft                                              Load Control

D.1 Simple Marking based on Measurement Based Admission Control

D.1.1 Constant Bit-Rate Sources

   In the first case, flows emitted 40 byte long packets every 20 ms,
   producing a constant 16 kbit/s load. The 1 Mbit/s capacity assigned
   to this traffic can thus carry 62.5 flows. From the table in appendix
   A, we can see that 4 calls should be reserved in addition to the
   62.5. After an initial transient of 5 minutes, we simulated 2.5
   hours.

   During the 2.5 hour simulation time, utilization was measured over
   5-minute intervals. Utilization was also measured in 20ms slots and
   the percentage of slots in which it was above 1.064 Mbit/s (66.5
   calls) was counted.

      min/avg/max of the utilization was: 881 / 899 / 914 kbit/s
      min/avg/max of the violation ratio was: 98.96% / 99.78% / 100%


D.1.2 On/Off Sources

   In the second simulation case, on/off sources were used. During an
   "off" period, no packets were generated, while in the "on" state the
   behavior is the same as in the previous case: 40 byte long packets 20
   ms apart. The distributions of the on and off periods were both drawn
   from a pareto distribution with the shape parameter of 1.1 and mean
   of 5 seconds. The average bit-rate of the sources is thus 8 kbit/s.
   The flow arrival rate has been doubled to produce50% blocking,
   since the link is capable of carrying nearly twice the number of
   flows. The same set of measurements was carried out as in the
   previous case.

      min/avg/max of the utilization was: 808 / 819 / 837 kbit/s
      min/avg/max of the violation ratio was: 98.98% / 99.40% / 99.70%

   It can be seen that although the measurement-based approach was not
   able to prevent the over-use of the real-time resources in this high
   load case, it is a viable alternative. In no case did the 20 ms
   measurements exceed 1.15 Mbit/s, so the over-use just means a
   temporary steal from the resources provisioned to the lower priority
   traffic.

Westberg, et. al.                                              [Page 17]


Internet Draft                                              Load Control

D.1.3 The Router Algorithm

   The mbac algorithm used by the router is presented here only for the
   completeness of the simulation description. The marking strategy was
   the same for both types of traffic. The router counts the number of
   bytes transmitted in every 20 ms interval and calculates the average
   bit rate in these 20 ms slots. Then it smoothes these values in time
   through an exponentially weighted moving average (ewma) filter. The
   window size of the ewma was set to 9 seconds, i.e., running a unit
   step function through it, the output will be 0.63 after 9 seconds.
   The algorithm also calculated the histogram of the difference between
   the original slot values and the filtered values. The histogram has
   been counted in 1000 bins between the range of -1 and +1 Mbit/s. The
   99% quantile of the histogram was calculated every 100 seconds. The
   router marks all passing packets if the sum of the output of the ewma
   filter and the calculated quantile is greater than 1 Mbit/s. The
   router makes no correction to its measurements when a new flow is a

   Thus, the target violation probability was set to 1%, which was in
   fact fulfilled in the long run.

   On arrival of a new packet, only counters are incremented. Every 20
   ms a new value for the ewma must be calculated, a marking decision
   must be made for the next 20 ms and the value of one bin in the
   histogram must be increased. Every 100 seconds, the 99% quantile
   value must be looked up in the histogram and the histogram must be
   initialized.

   The interested reader can read more about the design rationale of the
   above algorithm in [Gross99].


D.2 Unit-Based Reservations

   In this section we demonstrate the unit-based reservation scheme. The
   routers use the simple algorithm in Appendix B, except that it never
   marks regular packets. The simulation setup is otherwise the same as
   in the previous section. The traffic inside the flows does not affect
   the admission algorithm, so during simulation, sources send only
   probe and refresh packets. The definition of the unit is a peak bit-
   rate of 16 kbit/s. The flow number threshold was set to 62 flows
   resulting in close to the same target utilization of 1Mbits/s as in
   appendix C.1. The length of the refresh period was changed between
   100 ms and 10 seconds. The actual number of flows on the link never
   exceeded 62 (no violation), so only the utilization values are shown
   in kbit/s.

Westberg, et. al.                                              [Page 18]


Internet Draft                                              Load Control

                      | interval | min | avg | max |
                      +----------+-----+-----+-----+
                      |    --    | 968 | 972 | 976 |
                      | 100 ms   | 952 | 954 | 959 |
                      |  1 sec.  | 941 | 946 | 949 |
                      |  2 sec.  | 927 | 933 | 936 |
                      |  4 sec.  | 908 | 913 | 920 |
                      |  7 sec.  | 861 | 870 | 879 |
                      | 10 sec.  | 827 | 837 | 852 |

   The first line shows the utilization value for the case when the
   Source limits itself to 62 flows, i.e., blocking is not done by the
   network, but by the source. This emulates the case when the refresh
   period is infinitely short or when a state approach is used, as in
   RSVP. The utilization is not 100% due to the burstiness of the
   arrivals.

   It can be seen that as the refresh packets becomes less frequent,
   more resources are wasted, as the resources allocated to departing
   flows remain allocated until the end of the next refresh period. The
   result is not only lower average utilization, but lower maximal
   utilization as well. When the refresh period is 10 seconds long, the
   highest utilization experienced was 952 kbit/sec, which is 3 units
   below the limit.

   This motivates the use of as short a refresh period as possible.
   However, too short a refresh period will increase the effects of
   clock differences between edge and core devices (which was not taken
   into account during simulation). It also decreases the chance of
   finding a packet to mark as refresh if the flow is currently
   transmitting below its reserved rate.


Appendix E: Marking using ECN bits

   If the ECN bits were to be used for load control marking, the values
   are encoded in the two unused bits as described below, and the DS
   field contains the PHB.

               DS byte    Load Control
               01234567   codepoint (in ECN)
               -----------------------------
               xxxxxx00   Ordinary
               xxxxxx01   Probe
               xxxxxx10   Marked
               xxxxxx11   Refresh


Westberg, et. al.                                              [Page 19]


Internet Draft                                              Load Control

   The interpretation of the two ECN bits remains unspecified for other
   PHB that do not support Load Control. This is done so as not to
   Interfere with possible ECN deployment [RFC2481], [RFC3168].
   Furthermore, the ECN bits SHOULD be used for load control only
   if the requirements on using alternate semantics on ECN specified in
   [Floyd05] are satisfied. In particular, it SHOULD be ensured that the
   load control (edge-to-edge) ECN semantics do not conflict with a flow
   (connection) that is using other ECN semantics end-to-end.


Authors' Addresses

   Lars Westberg
   Ericsson Research
   Kistagangen 26
   SE-164 80 Stockholm
   Sweden
   EMail: Lars.Westberg@.ericsson.com

   Zoltan R. Turanyi
   Ericsson Research
   Ericsson Hungary Ltd.
   Laborc 1, Budapest, H-1037Hungary
   EMail: Zoltan.Turanyi@ericsson.com

   David Partain
   Ericsson Radio Systems AB
   P.O. Box 1248
   SE-581 12  Linkoping
   Sweden
   EMail: David.Partain@ericsson.com

   Attila Bader
   Ericsson Research
   Ericsson Hungary Ltd.
   Laborc 1, Budapest, H-1037
   Hungary
   EMail: Attila.Bader@ericsson.com

   Georgios Karagiannis
   University of Twente
   P.O.  BOX 217
   7500 AE Enschede, The Netherlands
   EMail: g.karagiannis@ewi.utwente.nl


Westberg, et. al.                                              [Page 20]

Internet Draft                                              Load Control

Copyright (C) The Internet Society (2005).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided
   on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
   REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES,
   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT
   THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR
   ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
   PARTICULAR PURPOSE.

   Disclaimer of validity:

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed
   to pertain to the implementation or use of the technology
   described in this document or the extent to which any license
   under such rights might or might not be available; nor does it
   represent that it has made any independent effort to identify any
   such rights.  Information on the procedures with respect to rights
   in RFC documents can be found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use
   of such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository
   at http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention
   any copyrights, patents or patent applications, or other
   proprietary rights that may cover technology that may be required
   to implement this standard.  Please address the information to the
   IETF at ietf-ipr@ietf.org.


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/