Skip to main content

Full text of "USPTO Patents Application 09750903"

See other formats


IN THE UNITED STATES PATENT AND TRADEMARK OFFICE 


APPLICATION FOR LETTERS PATENT 


BY 


Paul Kirkby 

42 St. Johns Avenue 
Harlow 
Essex 
UNITED KINGDOM 


FOR 


TRAFFIC FLOW MANAGEMENT IN A COMMUNICATIONS NETWORK 


12599ID Kirkby 


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 earned on packet 
networks, and in particular on Internet Protocol (IP) networks. Such networks 
comprise on any nodes or routers interconnected by links so a s to define a mesh. 
A recent introduction has been the concept of network havlnjj 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 ccipadty IP networks, 
routers are classified as either core routers or edge routers. Ed ge routers carry out 
all the network ingress and egress functions in particular contrDlling ttie incoming 
traffic streams across the network. Core routers act as transit routers forwarding 
netvyork trafnc from one network node to another. 

In such a network, the user data is assembled into packets and each provided vMth 
a header identifying the destination of the packet and optional y, including routing 
infomiation. The header may further contain information relaling to the router of 
the packet contents and identifying a priority class for the pat^et For example, 
packets containing high quality of service real time traffic, aid is voice, will be 
accorded the highest priority, while packets containing 'best efforts' data may be 
accorded a low priority. 

A parttojlar problem that has been experienced with certain types of traffic, 
particulariy data traffic and reahUme video traffic. In its inhensntly bursty nature. 
Further, this burstiness occurs on a timescale that is shorter th an feasible network 
control loop timescales, and thus can lead to congestion when traffic is heavy. 



-2- 

When congestion occurs, ordinary data traffic which is not crit cally 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 
delayed. 

In order to maximise the overall network utilisation, It is desirable to perform 
statistical multiplexing of traffic traversing the network whihi providing a prior 
allocation of resources and protection particulariy 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 this 
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 net/vorit for admission 
confrol purposes have Involved for instance measuring the 'effi^ctive bandwidth' of 
the flow. (Ref) Effective bandwidth Is a measure of the bandwi<lth that needs to be 
reserved to give a desired packet loss ofr delay rate on a statii^cally varying flow. 
Unfortunately effective bandwldths do not add iinearty 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- 

According to a first aspect of the invention there is provided a method of controlling 
traffic flow in a communications packet network, the method comprising 
determining for flows within the networi^ a mean utilisation requirement and a 
measure of a variance from that mean, and determining fram said mean and 
variance and bandwidth pricing so as to control the admission of said flows to the 
network. 

Advantageously, control limits are set by the networtc operator for mean and 
variance, and the pricing is increased as one or both of these imits is approached 
so as to provide feedlMiCk control of admission to the networt^. 


The control method may be embodied as software in machine readable form on a 
storage medium. 

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 traffic 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 
flow, detemiining from said sampling a mean bandwidth requirement for each traffic 
flow and a measure of the variance from that mean, detemiining from said mean 
and variance measurements first and second prices for the mean and variance 
components of the controlled traffic flows that are admitted to the network, and 
detenmining from said first and second prices an admission cost for each said flow 
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 
sampling means a measure of mean bandwidth requirement and of a variance from 
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 networt^. 

The admission control arrangement may be Incorporated in a network 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 accordintj to a square route 
law and means add lineariy. In a mixed traffic flow type network, a network 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 networi^ charges on the batis of mean ingress 
flow, the charges are based on a measure of mean and standard deviation. This 


-4- 

d!scx)urages users from abusing the network by sending excessively bursty trafTic, 
unless it is genuinely important to the user. It should be noted tiat the terms prices 
and charges as employed herein refer to an internal network: currency 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 descril^ed witl'i reference to the 

accompanying drawings in which:- 

Figure 1 is a selective design of an exemplary network; 

Figure 2 illustrates the aggregation of traffic flows at a nodi3 in the network of 
5 Figure 1 ; 

Figure 2a shows the construction of an ingress controller; 

Rgure 3a and 3b illustrate idealised and practical bandwidth demands for a traffic 
flow. 

10 Figure 4 illustrates the variance of the traffic flow of Figure 3; 

Figure 5a illustrates tiie measured mean and standard dc^viation of a traffic 
aggregate; and 

Figure 5b illustrates the primary flow control level and Its dl>/islon Into separate 
allocations for variance and mean.. 

15 

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 interconnected by 
links 12. As shown in Figure 1, the network comprises a core region 13 access^ 

20 via an edge region 14. The links 12 are usually optical fibre, partloulariy in the core 
region. Advantageously the network of Figure 1 is an Intenet Protocol (IP) or 
MPLS (multi protocol label switched) networic 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 'Masses are treated 

25 optimally. In particular, delay sensitive dasses of traffic must see minimal 
congestion inside any router or on entering any of the pstcket buffers at he 
entrance to each optical link. 


Referring now to Figure 2. this shows in schematic form a an «sdge node 11 and 
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 1 la two transit traffic 
flows are shown merging. Prior to entering the packet buffer 17 at the entrance to 
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 
an^ngement exists 17a,21a. The traffic flows are sampled by sampling circuits ^1 
and 22 to determine both the mean bandwidth usage Xi and thc^ standard deviation 
tji from that mean for each aggregated flow across the netwc»rk. The mean an^d 
standard deviation measurement are processed by a network admission controller 
to^determihe ~a^ pair of "prices ~f6f~us(ng^ thMisraftlOtJlaT resoarcev Thispnce^ pa^r 
defines separate prices for the mean component of traffic flow « ind the deviation (or 
variance) component A separate ingress controller 23 (Figure 2a) in the edgje 
router samples 24 and measures the mean and deviation oi' individual edge to 
edge flows entering the networi^. The ingress controller also continuously monitors 
the sum of the resource price pairs for the edge to edge path it is using, (note tiiere 
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 Ihexx either accept this 
price or modify this mean bandwidth or standard deviation bandwidth requirements 
to obtain his optimum quality of service vs price. To modify thu ingress traffic flow 
the ingress controller could use the traffic shaper 25 or for example signal back to 
the original traffic source (not shown). The traffic shaper controls scheduler 26. 
This price feedback mechanism provides a self-regulating mechanism on the 
bandwidth demands Imposed on the networic. 

The ingress control 23 controls traffic on every end to end path through the 
network. The paths may be MPLS paths. 

Referring now to Figures 3a and 3b, these illustrate respecjvely idealised and 
practical bandwidth requirements for a traffic flow. Figure 3a shows a slowly 
varying mean bandwidth demand, while figure 3b shows a typical rapid short term 
variation superimposed on the mean. 

The short temn 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 


m 


-6- 


give a measure of mean and standard deviation. This analysts also gives the 
variance which is the standard deviation squared. A variety of algorithms could be 
used for this purpose. The exponentially weighted time averaned mean is one bf 
the simplest, Nn^ilst 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 for Ingress 
control purposes are sufficiently similar to those used by the agigregate flow meters 
that insignificant errors are caused. Typically tiie time averaging time constant is 
greater than the feedback time constants of the DRC contixil 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 the specified worst 
case permitted delay variation for the traffic being controlled, 1-I0ms might be 
appropriate for typical delay sensitive traffic. (Longer sampling periods could be 
tolerated if margins were increased. A measure of the significsince of these rapid 
short term variations is given by the standard deviation (o) or by tiie con-esponding 
variance o^. 

In the arrangement of Figure 2a in which a number flows are aggregated on a 
common path. Assuming that traffic deviations are uncompleted in time, the 
standard deviation of the aggregate flow is given by the expression 


The aggregated mean traffic of course adds lineariy so the aggregated mean flow 
Is given by the expression 


Referring now to Figure 5a. this illustrates a bandwidth plan from which pricing 
information is determined to provide feedback control for admission to the network. 
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 



-7- 

congestion, tiiis mean Xa should be at least one and preferably 'k* standarxl 
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 the 
range 3 to 6. 

In a preferred embodiment, separate price calculations are perfontied from the 
mean xa and 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 Xojthe nominal allocation for 
the components of flow that deviate from the mean. These wo allocations aro 
Telatedto the control Tev¥rbythe~equat^^ Xcm + xcd ^s^jliuSratedTin Rgu^ 
5b. . We determine the mean pricing as a function of the nean demand and 
the control level for mean traffic. This price will typically be quoted by the resource 
in terms of a price per unit bandwidth. 

i.e. Px = F (Xcm , Xft) 

In a discrete system, in which price is updated at regular Interva s , At, an example 
function might be. 

Px (t+1) = IP. (t) +pA t (Xcm - XOk 

This equation indicates that the new price at the end of the current time interval 
equals the current price plus a gain factor times the time interval and the difference 
between the control level for mean traffic and the cun^t mejm flow. The outer 
brackets wrtth 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 enxir signal is integrated over time to 
produce change in price. Other variants include differential and proportional 
feedback. 

Similariy, we define tiie variance pricing Pv in ternis of the the measured standartl 
deviation cta and the control level Xcd. This price will typically hav*? units of price per 
unit time per unit bandwidth variance, i.e.. 

Pv = F (Xcd . cia) 

In a discrete system an example function might be 



-8- 

Pv (t+1) =^ |Pv (t) +aA t (x^cD -k^o*A)|+ 

This equation indicates that the new variance price at the end of the current time 
interval equals the current price plus a gain factor times the time Interval and the 
difference between the square of control level for deviation and the square of k 
S times the measured aggregate variance. The outer brackets with subscript + sigiii 
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 error 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 introducing a second order term 
vy/hich takes into account the first and/or second differentials of the traffic flow 
15 means and deviations. . In that case the pricing functions become 

Pni = F((XcM.XA), ^)andPv = F({xcg.cT^,^, 

di a t at at 

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 detemiined by 

20 measurements on the traffic 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 option^tlly) the user to see 
a much fairer estimate of the networic 'cost* to transport that particular flow. This 
infomiation 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 



-9- 

i$ committed to allow the ingress of traffic within the pre agreed limits, irrespecbVe 
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 
5 service which highly values the transmission of bursty traffic without delay. These 
users would have a service level agreement that assigned a hlg h WtP (willingness . 
to pay) to the variance component of the traffic. Thus even in high congestion the 
bursts from such users vrautd be allowed into the network whilst other users with a 
low WtP for variance would have their traffic bursts smoothed and hence 
1 0 momentarily delayed. 

A modification of the schemes described above is a system in which the sub- 
allocations of bandwidth for mean and standard deviation control levels Xm and Xcm 
are not defined by management fiat, but are estimated dyramically from the 
measurements of mean and deviation parameters of the incoming aggregate flows.' 
15 The management system still defines the bandwidth peak maximum control level 
xc- The simplest way to determine the standard deviation allocation is simply to 
-define - _ _ _ ... _ _ „ . . _ _ _ ; 

Xcd = Xc-Xa 

That is to say the allocation for standard deviation is simply taken to be the 
20 difference between the cument 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 inversn 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 
25 all. 

In this case it would be natural to define the control level for the nean flow as 

XcM = Xc-k.aA 

That is to say the mean control level is defined as the peak bandividth control level 
minus K times the currently measured standard deviation. In practice caution may 
30 suggest that other constraints such as a minimum bandwMth miirgin between the ' 
peak control level and the mean control level are added. 


-10^ 

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 proportionai fairness is applied 
6 to the allocation split between mean and deviation traffic. The nasouroe would thus 
adjust the ratio of xc^i to Xcd to be the same as the current nivenu© from mean 
traffic and the current revenue the variance component of the traffic. These 
adjustments would have to be carried out slowly in comparison to the DRC 
feedback control time constant or instability could result 

10 

The price for traffic traversing a series of resources along a p&Q\ Is optimally found 
by adding the prices at each resource linearly. 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 that th 2 path utilizes. We 
15 have found that, for optimum results, ttie price per unit vsiriance should be 
determined 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, particularly 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 be 
used as a second order correction to discourage users from transmitting targe 
bursts of traffic unexpectedly at very high rates. Note that this use of variance 
25 rather than simple deviation from a mean already penalizes large sudden 
deviations with a square law dependency. 

It will be understood that the above description of a preferred embodiment is given 
by vt^y 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,