IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
APPLICATION FOR LETTERS PATENT
42 St. Johns Avenue
TRAFFIC FLOW MANAGEMENT IN A COMMUNICATIONS NETWORK
TRAFFIC FLOW MANAGEMENT IN A COMMUNICATIONS NETWORK
FIELD OF THE INVENTION
This invention relates to methods and apparatus for controlling traffic flow In a
communications network so as to reduce congestion.
BACKGROUND OF THE INVENTION
Increasing volumes of communications traffic are now being cam'ed on packet
networks, and in particular on Internet Protocol (IP) networks. Such networks
comprise on any nodes or routers interconnected by links so as to define a mesh.
A recent introduction has been the concept of network havinjj an optical core in
which traffic is carried on switched optical fibre paths between routers. The core is
accessed by an edge network Typically in the design of high Ccipacity IP networks,
routers are classified as either core routers or edge routers. Edge routers carry out
all the network ingress and egress functions in parBcular controlling the incoming
traffic streams across the network. Core routers act as transit nauters fonivarding
network traffic from one network node to another.
In such a network, the user data is assembled into packets and each provided w/ith
a header identifying the destination of the packet and optional ,y, including routing
infomnation. The header may further contain Information relating to the router of
the packet contents and identiiying a priority dass for the packet For example,
packets containing high quality of service real time traffic, a nd is voice, will be
accorded the highest priority, while packets containing 'best efforts' data may be
accorded a low priori^.
A particular problem that has been experienced with certain types of traffic,
particularly data traffic and real-time video traffic. In its inhenjntly bursty nature.
Further, «iis burstlness occurs on a timescale that is shorter than feasible network
control loop timescales, and thus can lead to congestion when traffic is heavy.
When congestion occurs, ordinary data traffic which is not critcally time sensitive
can be briefly buffered In the routers which are experiencing congestion. Urgent
data traffic and real time interactive services such as voice and video cannot be
In order to maximise the overall networic utilisation. It Is d«slrable to perform
statistical multiplexing of traffic traversing the network whilo providing a prior
allocation of resources and protection particularly for the delay sensitive traffic .
Existing control and feedback mechanisms Such as described in patents... are
however inadequate to respond to this bursty traffic at a sufficiently rapid rateto
provide this resource allocation and protection. In the conventional approach to ttiis
problem, the high speed statistical variations in traffic flow are simply allowed for by
setting large margins in the setting of control levels for determining feedback price.
Proposals for 'pricing" ingress flows at the edge of the networit for admission
control purposes have Involved for instance measuring the 'effi3Ctive bandwidth' of
the flow. (Ref) Effective bandwidth is a measure of the bandwi(ith that needs to be
reserved to give a desired packet loss ofr delay rate on a stati.-stically varying flow.
Unfortunately effective bandwidths do not add lineariy on .aggregation so are
difficult to use in a congestion price feedback control scheme.
SUMMARY OF THE INVENTION
An object of the invention is to minimize or to overcome these <Jisadvantages.
Accorcling to a first aspect of the invention there is provided a method of controlling
traffic flow in a communications packet networic, the method comprising
detemiining for flows within the networit a mean utStisatlon requirement and a
measure of a variance from that mean, and determining from said mean and
variance and bandwidth pricing so as to control the admission of said flows to Une
Advantageously, control limits are set by the network operator for mean and
variance, and the pricing is increased as one or both of these Imlts is approached
so as to provide feedback control of admission to the networic.
The control method may be embodied as software in machine readable form on a
According to another aspect of the invention, there is provided a method of
controlling admission of traffic flows to a communications network, the method
comprising sampling the fcraffic flows each at an ingress, and sampling an
aggregate flow of said flows at some or all of the resources us€d by the aggregate
5 flow, determining from said sampling a mean bandvwdth requirement for each traffic
flow and a measure of the variance from that mean, detemnining from said mean
and variance measurements first and second prices for the mean and variance
components of the corrtrolled traffic flows that are admitted to the network, and
determining from said first and second prices an admission cost for each said flow
10 so as to regulate the admission of that flow.
According to a further aspect of the invention, there is provided an admission
control arrangement for a communications network, the arrangement comprising
sampling means for sampling a traffic flow, means for debirmining from said
1 5 sampling means a measure of mean bandwidth requirement and of a variance firom
that mean, and price computation means for determining from said mean and
variance a cost or price for bandwidth case so as to provide ingress price control
for admission of the traffic flow to the networi^.
The admission control arrangement may be incorporated in a networi? manager,
e.g. in software form.
In our arrangement and method, overall resource utilisation Is optimised by the use
of congestion price based feedback that separates out the components of price
that affect the mean traffic flow from the standard deviation of the flow, it is well
known that on aggregation, standard deviations add accordin<3 to a square route
law and means add lineariy. In a mixed traffic flow type network, a networi^ flow
optimisation process that separates these components can provide improved
overall resource utilisation. A further advantage of this arrangement and method is
that that it enables a fairer allocation of 'network —price' to any given ingress flow.
Rather than simply allocating the networit charges on the bas is of mean ingress
flow, the charges are based on a measure of mean and standard deviation. This
discourages users from abusing the network by sending excessiveiy bursty traffic,
unless it is genuinely important to tlie user. It should be noted tnatthetemis prices
and charges as employed herein refer to an internal networt: cun-ency used for
admission control purposes and is generally separate from any real billing.
BRIEF DESCRIPTION OF THE DRAWINGS
Embodiments of the invention will now be described witfi reference to the
accompanying drawings in which:-
Figure 1 1s a selective design of an exemplary network;
Figure 2 illustrates the aggregation of traffic flows at a nodo in the network of
5 Figure 1;
Figure 2a shows the construction of an ingress controller;
Figure 3a and 3b illustrate Idealised and practical l)andwidth demands for a traffic
10 Figure 4 illustrates the variance of tfie traffic flow of Figure 3;
Figure 5a illustrates the measured mean and standard deviation of a traffic
Figure 5b illustrates the primary flow control level and its di^nsion into separate
allocations for variance and mean..
DESCRIPTION OF PREFERRED EMBODIMENTS
Referring first to Figure 1, this shows an exemplary network in schematic form. As
shown in Figure 1 , the network comprises a number of nodes 1 1 j[nterconnected by
links 12. As shown in Figure 1, the network comprises a core region 13 accessed
20 via an edge region 14. The links 12 are usually optical fibre, particularly In the core
region. Advantageously the network of Figure 1 is an Internet Protocol (IP) or
MPLS (muiti protocol label switched) network in which traflic is transported in
packet form. An objective of the resource control system is tc control the ingress
of IP and MPLS traffic in such a way that different traffic classes are treated
25 optimally. In particular, delay sensitive classes of traffic must see minimal
congestion inside any router or on entering any of the psicket buffers at he
entrance to each optical link.
Referring now to Figure 2, this shows in schematic form a an «dge node 11 and a
core network node 11a. At the edge node 11. a number of input traffic flows are
aggregated on to a traffic path on link 12. At the core node l ia two transit traffic
flows are shown merging. Prior to entering the packet buffer 17 at the entrance to
5 transmission link 12, the traffic is sampled by the aggregate sampling circuit 21. At
the entrance to the next link on the traffic path 12a a similar measurement
anangement exists 17a,21 a. The traffic flows are sampled by sampling cin:uits 21
and 22 to determine both the mean bandwidth usage and the; standard deviation
Oi from that mean for each aggregated flow across the network. TTie mean ar^
10 standanJ deviation measurement are pnDcessed by a network admission controller
to determine a pair of pfices for using that partlcuiaf resoarce. This price psfir
defines separate prices for the mean component of traffic flow sind the deviation (or
variance) component, A separate ingress controller 23 (Figure 2a) in the edge
router samples 24 and measures the mean and deviation oi' individual edge to
1 5 edge flows entering the networic. The ingress controller also continuously monitors
the sum of the resource price pairs for the edge to edge path it is using, (note there
is one ingress controller per edge to edge path, the explicit edge to edge path
being defined for instance by MPLS labels attached to each packet. The user (or a
software object using pre-agreed ingress control rules) can them either accept this
20 price or modify this mean band\Afldth or standard deviation bandwidth requirements
to obtain his optimum quality of service vs price. To modify thti ingress traffic flow
the ingress controller could use the traffic shaper 2S or for example signal back to
the original traffic source (not shown). The traffic shaper controls scheduler 26.
This price feedback mechanism provides a setf-regula«ng mechanism on the
25 bandwidth demands imposed on the networi<.
The ingress control 23 controls traffic on every end to end path through the
network. The paths may be MPLS paths.
Refening now to Figures 3a and 3b, these illustrate re^eciively idealised and
practical bandwidth requirements for a traffic flow. Figure 3a shows a slowiy
30 varying mean bandwidth demand, while figure 3b shows a typical rapid short term
variation superimposed on the mean.
The short term variations, which represent the deviations of the traffic flow from the
mean, are illustrated in Figure 4. These can be statistically analysed in real time to
give a measure of mean and standard deviation. This analysis atso gives the
variance vvhich is the standard deviation squared. A variety of algorithms could be
used for this purpose. The exponentially weighted time averaged mean is one of
the simplest, v/Msi the sampled data can and the mean together can be used to
give the time averaged variance. The rest of this description makes the assumption
that the sampling periods and rate and time averaging parametars used forlngress
control purposes are sufficiently similar to those used by the agijregate flow meters
that insignificant errors are caused. Typically the time averaging time constant is
greater than the feedback time constants of the DRC contrcil system. Typically
100ms to 10 seconds. The variance sampling period is typically sufficiently short
that the shortest bursts you are interested in controlling are caatured. This implies -
a sampling time period does not need to be much shorter than Uie specified worst
case permitted delay variation for the traffic being controlled, 1-1 oms might be
appropriate for typical delay sensitive traffic. (Longer sampling periods could be
tolerated if margins were increased. A measure of the significance of these rapid
short term variations is given by the standard deviation (a) or by the corresponding
In the arrangement of Figure 2a in which a number flows are aggregated on a
common path. Assuming that traffic deviations are uncorr<jlated in time, the
standard deviation cta of the aggregate flow Is given by the expression
The aggregated mean traffic of course adds lineariy so the agcjregated mean flow
is given by the expression
Refening now to Figure 5a, this illustrates a bandwidth plan from which pricing
infonnation is detennined to provide feedback control for admission to the networit.
In figure 5a, the network operator sets a peak bandwidth maximum or control level
Xc which, in the ordinary cause of events should not bs exceeded, even
momentarily by the peak bursts of the aggregated traffic. A typical flow has a
mean bandwidth xa well below this maximum level. Further, to minimise the risk of
congestion, this mean )^ should be at least one and prefsrably 'k' standard
deviations below this control level xc- To ensure that the probability of momentary
congestion is sufficiently small for all practical purposes k should typically lie in tiie
range 3 to 6.
5 In a prefen-ed embodiment, separate price calculations are performed from the
mean XAand standard deviation oa demands on the network as; follows
The network operator subdivides the control level bandwdth into two sub
allocations, Xcm the allocation for the mean flow, and Xcothe nominal allocation for
the components of flow that deviate from the mean. These .wo allocations are
'10 related to the controrievel by^he equation xc^ Xo^i + xcd ,as~illustiiteci in Figure
5b. . We determine the mean pricing as a function of the Tiean demand and
the control level for mean traffic. This price v^'tl typically be quoted by the resource
in terms of a price per unit bandwidth.
i.e. Px = P (Xcm , Xa)
15 In a discrete system, in which price is updated at regular interva s , At, an example
function might be.
P«(t+1) = iP>c(t>+pAt(XcM-XA)k
This equation indicates that the new price at the end of the current time interval
equals the cunrent price plus a gain factor times the time interval and the difference
20 between the control level for mean traffic and the current mean flow. The outer
brackets with subscript + sign signifies that the solution is constrained to be
positive. The parameter pis the feedback gain. This is an example of an
integrating control feedback system, as the error signal is intec rated over time to
produce change in price. Other variants include differential and proportional
Similariy, we define the variance pricing Pv in terms of the the measured standard
deviation cta and the control level Xcd. This price will typically havi? units of price per
unit time per unit bandwidth variance, i.e..
Pv = F (Xcd , oa)
In a discrete system an example function might be
Pv (t+1) - |Pv (t) +aA t (x^cn -kV*)!*
This equation indicates that the new variance price at the end of the current time
interval equals tiie current price plus a gain factor times the time interval and the
difference between the square of control level for deviation aid the square of k
5 times the measured aggregate variance. The outer brackets with subscript + sign
signifies that the solution is constrained to be positive. The parameter a is the
feedback gain. This is an example of an integrating control feedback system, as
the en"or signal is integrated over time to produce change in p ice. Other variants
. include differential and proportional feedback.
In both these examples the price increases rapidly as the argument of the inner
bracket (the error signal) goes positive.
A more sophisticated pricing may be obtained by intnoducing a second order term
which takes into account the first and/or second differentials of the traffic flow
1 5 means and deviations. . In that case the pricing functions become
Pm = F((XcM.x,^), -r-, -Trf )and Pv = F ((x«, .£T^ r^. -^r")
at a t at iw
The price that is fed back to the user is in the form of the two separate prices Pm
and Pv. These prices can be quoted In terms of a price per urit bandwidth and a
price per unit variance. The total 'price' charged to the user is ihen detemnined by
20 measurements on the trafflc leaving the user of the mean and variance of his
traffic. These are multiplied by the prices per unit and added together to give the
total price to the user T. This enables the networic (and optionsiliy) the user to see
a much fairer estimate of the network 'cosf to transport that p>ar1icular flow. This
infonnation can then be used for admission control purposes, for instance for
25 smoothing the flow to reduce the variance component of the low or reducing or
even shutting off the mean flow if the total price T is becoming excessive. It can
also be used for admission control of inelastic traffic flows where a user would ask
for admission of a guaranteed flow with certain quoted mean and variance
characteristics. Once admitted, the ingress controller of such inelastic traffic flows
is committed to allow the ingress of traffic within the pre agreed limits, Irrespective
of how high the internal congestion price subsequently goes.
The technique enables finely differentiated services to be provided by control of
ingress flows at the network edge. Some users may, for instance want a class of
seMce which highly values the transmission of bursty traffic without delay. These
users would have a service level agreement that assigned a high WtP (willingness
to pay) to the variance component of the traffic. Thus even in high congestion the
bursts from such users would be allowed into the network whilst other users vwth a
low WtP for variance would have their traffic bursts smoothed and hence
A modification of the schemes described above is a system in which the sub-
ailocatjons of bandwidth for mean and standard deviation contrtil levels and Xcw
are not defined by management fiat, but are estimated dyramicaliy from- the
measurements of mean and deviation parameters of the incoming aggregate flows.
The management system still defines the bandwidth peak maximum control level
xc- The simplest way to detemnine the standard deviation allocation is simply to
-define _ „
That is to say the allocation for standard deviation is simply taken to be the
difference between the current mean traffic level and the peak maximum control
level. This has the advantage that as the mean level rises towards the peak
bandwidth control level, the variance price rises in an inversfj square manner,
drastically curtailing new traffic bursts. When the network has only low mean
traffic, the variance price is extremely low and bursty traffic is hardly discouraged at
In this case it would be natural to define the control level for the nean flow as
XcM = Xc-k.CTA
That IS to say the mean control level Is defined as the peak bandiwdth control level
minus K times the currently measured standard deviation. In practice caution may
suggest that other constraints such as a minimum bandwidth m;irgin between the
peak confrol level and the mean control level are added.
For optimum resource usage in a future system in which the ingress controllers
actively adjusted the shaping of the mean and deviation components of their traffic
in response to mean and deviation prices and the class of traffic; being transmitted,
then maximum user utility would be obtained when proportional fairness is applied
5 to the allocation split between mean and deviation traffic. ITie nasource would thus
adjust the ratio of Xcm to Xcd to be the same as the current nsvenue from mean
traffic and the current revenue the variance component of the traffic. These
adjustments would have to be carried out slowly in comperison to the DRC
feedback control time constant or instability could result
The price for traffic traversing a series of resources along a patt» is optimally found
by adding the prices at each resource Irneariy. Thus, the prices per unit bandwidth
for the mean flows for traffic flowing along a particular path are found by adding the
prices per unit bandwidth of the means in each resource th^t ths path utilizes. We
15 have found that, for optimum results, the price per unit Vciriance should be
detennined by adding the price per unit variance of each resource that the path
utilizes, rather than adding the price per unit-standard deviation.
In a further modification, partlculariy bursty traffic can Incur a further price penalty
20 by the user of an exponential weighting on the standard deviation measurement.
This exponential weighting function can be used to weight large positive deviations
of traffic flow from the mean more strongly than small deviations. This would tje
used as a second order correction to discourage users from transmitting large
bursts of traffic unexpectedly at very high rates. Note that th.3 use of variance
25 rather than simple deviation from a mean already penalizes large sudden
deviations with a square law dependency.
It wilt be understood that the above description of a preferred embodiment is given
by way of example only and that various modifications may be made by those
30 skilled in the art without departing from the spirit and scope of th« invention.