Internet Draft Load Control April 2000
Load Control of Real-Time Traffic
draft-westberg-loadcntr-03.txt
Document Revision: 1.3
2000/04/19 12:43:19
A Two-bit Resource Allocation Scheme
April 2000
L. Westberg
Z. R. Turanyi
D. Partain
Ericsson
Various Authors Expires October 2000 [Page 1]
Internet Draft Load Control April 2000
Status of this Memo
This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026.
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.
1. Abstract
The purpose of this memo is to present a new resource allocation
scheme for DiffServ (DS) networks, called Load Control. The main
purpose of Load Control is to provide a simple and scalable solution
to the resource provisioning problem.
Load Control addresses two particular issues:
1. 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
2. A lightweight reservation of a certain amount of network
resources.
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
Various Authors Expires October 2000 [Page 2]
Internet Draft Load Control April 2000
document are to be interpreted as described in [RFC2119].
2. 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-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.
3. Overview
Load control is achieved by two actions: measurement-based 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 packet headers to gather information about the
load level along various paths through the network. The core routers
Various Authors Expires October 2000 [Page 3]
Internet Draft Load Control April 2000
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, 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.
4. 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.
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
Various Authors Expires October 2000 [Page 4]
Internet Draft Load Control April 2000
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].
4.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.
Various Authors Expires October 2000 [Page 5]
Internet Draft Load Control April 2000
4) Reaction to exceptional events: If a core router detects severe
congestion on an interface, it starts marking all 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.
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.
4.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
Various Authors Expires October 2000 [Page 6]
Internet Draft Load Control April 2000
configurable.
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.
Various Authors Expires October 2000 [Page 7]
Internet Draft Load Control April 2000
4.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.
4.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.
5. Objects for Standardization
A forthcoming standard might only include the encoding of the Load
Control information into the IP header and some design
recommendations.
Various Authors Expires October 2000 [Page 8]
Internet Draft Load Control April 2000
5.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.
------ 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 packets.
5.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.
Various Authors Expires October 2000 [Page 9]
Internet Draft Load Control April 2000
5.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 interworking with the core routers.
5.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 to marked.
If the router is capable of detecting severe congestion, and this
occurs, then the router forwards both ordinary and probe packets as
marked. The router MUST NOT change the marking of refresh packets.
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.
5.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 a marked packet that is not initially sent as probe
packet, it shall inform the ingress device to reject 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:
Various Authors Expires October 2000 [Page 10]
Internet Draft Load Control April 2000
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.
6. Interworking with RSVP/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.
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
Various Authors Expires October 2000 [Page 11]
Internet Draft Load Control April 2000
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.
7. 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.
8. Identification of Edge Nodes
In the absense of RSVP, an alternative method for identificatiof of
edge nodes will be required. This section needs to be written.
9. Multicast-related Issues
[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
Various Authors Expires October 2000 [Page 12]
Internet Draft Load Control April 2000
[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.
Appendix A. Admission Precision of 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.
Various Authors Expires October 2000 [Page 13]
Internet Draft Load Control April 2000
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).
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,
Various Authors Expires October 2000 [Page 14]
Internet Draft Load Control April 2000
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.
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
Various Authors Expires October 2000 [Page 15]
Internet Draft Load Control April 2000
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.
D.1 Simple Marking
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
Various Authors Expires October 2000 [Page 16]
Internet Draft Load Control April 2000
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.
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
Various Authors Expires October 2000 [Page 17]
Internet Draft Load Control April 2000
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.
| 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
Various Authors Expires October 2000 [Page 18]
Internet Draft Load Control April 2000
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
The interpretation of the two unused bits remains
unspecified for other PHBs that do not support Load
Control. This is done so as not to interfere with
possible ECN deployment [RFC2481].
Table of Contents
1 Abstract ........................................................ 2
2 Background and Motivation ....................................... 3
3 Overview ........................................................ 3
Various Authors Expires October 2000 [Page 19]
Internet Draft Load Control April 2000
4 Operation of Load Control ....................................... 4
4.1 Simple Marking ................................................ 5
4.2 Unit-based Reservations ....................................... 6
4.3 Multiple Unit reservation ..................................... 8
4.4 Codepoints for Flow Types ..................................... 8
5 Objects for Standardization ..................................... 8
5.1 Packet Types .................................................. 9
5.2 Coding of Packet Types ........................................ 9
5.3 Behavior Description .......................................... 10
5.3.1 Behavior of the Core Routers ................................ 10
5.3.2 Behavior of the Edge Devices ................................ 10
6 Interworking with RSVP/Intserv .................................. 11
7 Security Considerations ......................................... 12
8 Identification of Edge Nodes .................................... 12
9 Multicast-related Issues ........................................ 12
Appendix A. Admission Precision of Simple Marking ................ 13
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 ............................................... 16
D.1.1 Constant Bit-Rate Sources .................................. 16
D.1.2 On/Off Sources ............................................. 17
D.1.3 The Router Algorithm ....................................... 17
D.2 Unit-Based Reservations ...................................... 18
Appendix E: Marking using ECN bits ............................... 19
Authors' Addresses
Lars Westberg
Ericsson Research
Kistagangen 26
SE-164 80 Stockholm
Sweden
EMail: Lars.Westberg@era-t.ericsson.se
Zoltan R. Turanyi
Ericcson Telecommunications
Budapest, Laborc u. 1
H-1037
Hungary
Various Authors Expires October 2000 [Page 20]
Internet Draft Load Control April 2000
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
Various Authors Expires October 2000 [Page 21]