Skip to main content

Full text of "USPTO Patents Application 09750903"

See other formats


JAN. 2,3- 2006 1 2:43PM BARNES & THORNBURG 


NO. 777 P. 3/17 


BEST AVAILABLE COPY 

in the Specification: rumunwu. wwr i 


Please amend the specification as follows: 


Page 1 . line 7 to page 2» line 1 9. 


BACKGROUND OF THE INVENTION 


Increasing volumes of communications traffic are now being carried 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 a network having 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 capacity IP networks, 
routers are classified as either core routers or edge routers. Edge routers carry out 
all the network ingress and egress functions^ in particular controlling the incoming 
traffic streams across the network. Core routers act as transit routers forwarding 
network traffic from one network node to another. 


In such a network, the user data is assembled into packets and each packet is 
provided with a header identifying the destination of the packet and optionally, 
including routing information. The header may further contain information relating to 
the router &f chosen to route the packet contents and identifying a priority class for 
the packet. For example, packets containing high quality of service real time traffic, 
dftd-te such as voice, will be accorded the highest priority, while packets containing 
'best efforts' data may be accorded a low priority. 


A particular problem that has been experienced with certain types of traffic, 
particularly data traffic and real-time video traffic, m is its inherently bursty nature. 
Further, this burstiness occurs on a timescale that is shorter than feasible network 


2 


PAGE 3/17*RCVD AT 1/23/2006 1:44:34 PM [Eastern Standard Time] ' SVR:USPTMFXRF-6I31 * DM8:2738300 ' CSID:3127595646 * DURATION (mm*s):04-16 


JAN. 23. 2006 1 2:43PM BARNES & THORNBURG 


NO. 777 P. 4/17 


control loop timescales, and thus can lead to congestion when traffic is heavy. 
When congestion occurs, ordinary data traffic which is not critically 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 while providing a prior 
allocation of resources and protection particularly for the delay sensitive traffic . 
Existing control and feedback mechanisms Such as d e scr i bed in patents... are 
however inadequate to respond to this bursty traffic at a sufficiently rapid rate to 
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 network for admission control 
purposes have involved for instance measuring the 'effective bandwidth' of the flow. 
{Re*} Effective bandwidth is a measure of the bandwidth that needs to be reserved to 
give a desired packet loss efr for delay rate on a statistically varying flow, 
Unfortunately A effective bandwklths do not add linearly on aggregation and so are 
difficult to use in a congestion price feedback control scheme. 


Page 3. lines 3 to 12. 

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 e ach at an ingress, and sampling an aggregate 
flow of said flows at some or all of the resources used by the aggregate flow, 
determining from said sampling a mean bandwidth requirement for each traffic flow 
and a measure of the variance from that mean, determining from said mean and 
variance measurements first and second prices for the mean and variance 


3 


PAGE 4117 1 RCVD AT 1/2312006 1:44:34 PM [Eastern Standard Time] ' SVR:USPTO-EFXRF-6/31 * DN1S:2738300 ' CSID:3127595M6 1 DURATION {mm-ss):04-16 


JAN. 2,3. 2006 1 2:44PM BARNES & THORNBURG 


NO. 777 P. 5/17 


components of the controlled traffic flows that are admitted to the network, and 
determining from said first and second prices an admission cost for each said flow so 
as to regulate the admission of that flow. 

Page 4, line 20 to page 7< line 5. 

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 11 t 11a interconnected 
by links 12. As shown in Figure 1, the network comprises a core region 13 accessed 
via an edge region 14. The [inks 12 are usually optical fibre links , particularly in the 
core region. Advantageously the network of Figure 1 is an Internet Protocol (IP) or 
MPLS (multi protocol label switched) network in which traffic is transported in packet 
form. An objective of the resource control system is to control the ingress of IP and 
MPLS traffic in such a way that different traffic classes are treated optimally. In 
particular, delay sensitive classes of traffic must see minimal congestion inside any 
router or on entering any of the packet buffers at the entrance to each optical link. 

Referring now to Figure 2, this shows in schematic form a an edge node 1 1 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 11a 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 12a on the traffic path 12a a similar measurement 
arrangement of packet buffer 17a and aggregate sampling circuit 21a exists 
17a,21a . The traffic flows are sampled by sampling circuits 21 and 22 21a to 
determine both the mean bandwidth usage Xj and the standard deviation u\ from that 
the mean for each aggregated flow across the network. The mean and standard 


4 


PAGE 5/17 * RCVD AT 1/23/2005 1:44:34 Ml [Eastern Standard Time] 1 SVR:U$PTMFXM » DNIS:2738300 * CSID:3127595646 * DURATION (mm-ss):04-16 


JAN. 2,3. 2006 1 2:44PM BARNES & THORNBU RG 


NO. 777 P. 6/17 


deviation measurement are processed by a network admission controller to 
determine a pair of prices for using that particular resource. This price pair defines 
separate prices for the mean component of traffic flow and the deviation (or 
variance) component A separate ingress controller 23 (Figure 2a) in the edge router 
has a sampler 24 that samples OA and measures the mean and deviation of 
individual edge to edge flows entering the network. 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 then 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 the ingress 
traffic flow the ingress controller could use the a traffic shaper 25 (figure 2a) or for 
example send a signal back to the original traffic source (not shown). The traffic 
shaper controls a scheduler 26. This price feedback mechanism provides a self- 
regulating mechanism on the bandwidth demands imposed on the network. 

The ingress controller 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 respectively 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 term variations, which represent the deviations of the traffic ftow 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 also gives the 
variance which is the square of the standard deviation s quared , A variety of 
algorithms could be used for this purpose. The exponentially weighted time averaged 


5 


PAGE 6/17 * RCVD AT 1/23/2006 1 :44:34 PM [Eastern Standard Time) 1 SVR:USPT<KF XRF-6/31 1 0)08:2738300 1 CSiD:3127505646 • DURATION (mm-ss):04-16 


JAN. 23. 2006 12:44PM 


BARNES & THORNBURG 


NO. 777 


P. 7/17 


mean is one of the simplest, whilst the sampled data ean 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 parameters used 
for ingress control purposes are sufficiently similar to those used by the aggregate 
flow meters that insignificant errors are caused. Typically the time averaging time 
constant is greater than the feedback time constants of the DRC control system, 
Typically 100ms to 10 seconds. The variance sampling period is typically sufficiently 
short that the shortest bursts yeu -a r e one is interested in controlling are captured. 
This implies that 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-1 Oms 
(milliseconds) 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 variance a 2 . 


In the arrangement of Figure 2a in which a number flows are aggregated on a 
common patht-A x assuming that traffic deviations are uncorrected in time, the 
standard deviation <y A of the aggregate flow is given by the expression 


The aggregated mean traffic of course adds linearly so the aggregated mean flow 
and 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 f the network operator sets a peak bandwidth maximum or control level Xc 
which, in the ordinary cau se course of events should not be exceeded, even 
momentarily by the peak bursts of the aggregated traffic. A typical flow has a mean 


PAGE 7/17 • RCVD AT 1/23(2006 1:44:34 PM [Eastern Standard Time) • SVR:USPTO-EFXRF-6/31 * DN!S:2738300 * CSID:3127595M6 1 DURATION (mm-$s):W-16 



6 


JAN. 2.3. 2006 1 2:44PM BARNES & THORNBU R6 


NO. 777 P. 8/17 


bandwidth Xa well below this maximum level. Further, to minimise the risk of 
congestion, this mean Xa should be at least one and preferably 'k' standard 
deviations below this control level Xq. 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. 


Page 10. lines 1 to 9 

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 to 
the allocation split between mean and deviation traffic. The resource would thus 
adjust the ratio of x C m to Xcd to be the same as the current revenue from mean traffic 
and the current revenue from 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. 


7 


PAGE 8/17 • RCVD AT 1/23/2006 1:44:34 PM [Eastern Standard Time] * SVR:USPTO-EFXRF-6J31 * DNIS:2738300 » CSID:3127595M6 4 DURATION (mm-ss):04-16 


This Page is Inserted by IFW Indexing and Scanning 
Operations and is not part of the Official Record 

BEST AVAILABLE IMAGES 

Defective images within this document are accurate representations of the original 
documents submitted by the applicant. 

Defects in the images include but are not limited to the items checked: 

□ BLACK BORDERS 

□ IMAGE CUT OFF AT TOP, BOTTOM OR SIDES 

□ FADED TEXT OR DRAWING 

□ BLURRED OR ILLEGIBLE TEXT OR DRAWING 

□ SKEWED/SLANTED IMAGES 

□ COLOR OR BLACK AND WHITE PHOTOGRAPHS 

□ GRAY SCALE DOCUMENTS 

~/Q*LJNES OR MARKS ON ORIGINAL DOCUMENT 

□ REFERENCE(S) OR EXHIBIT(S) SUBMITTED ARE POOR QUALITY 

□ OTHER: 

IMAGES ARE BEST AVAILABLE COPY. 
As rescanning these documents will not correct the image 
problems checked, please do not report these problems to 
the IFW Image Problem Mailbox.