Dynamic bandwidth estimation and adaptation in high speed packet switching networks

• US 6,011,776 A
• Filed: 01/22/1997
• Issued: 01/04/2000
• Est. Priority Date: 06/20/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Lengelle, Stephane, Galand, Claude, Berthaud, Jean-Marc, Nicolas, Laurent, Foriel, Pierre-Andre
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Nguyen, Kim T.
• Application Number:
  US08/786,916
• Time in Patent Office: 1,077 Days
• Field of Search: 370/230, 370/232, 370/233, 370/234, 370/235, 370/431, 370/437, 370/468
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A system adapts access to a packet switching network. A dynamic bandwidth adaptation continuously monitors the mean bit rate of a signal source and the loss probability of a connection in the network. A filtering means removes noise from the mean bit rate and loss probabilty. A test means determine whether the values fall within a pre-defined acceptable adaptation region in a mean bit rate, loss probability plane. Triggering means initiate bandwidth adaptation procedures when the values fall outside of the region which in turn, initiate means for acquiring a new connection bandwidth, and determining new parameters for the adaptation mechanism.

Claims

1. A method of dynamically adapting access to a packet switching communication network comprising a plurality of nodes interconnected with transmission links source nodes and destination nodes for the transmission of digital traffics from source nodes to destination nodes, said method comprising the steps of:

measuring the mean bit rate m_n of signals from said source node;

controlling the flow of said traffics from said source node into the network by means of a leaky bucket control circuit;

measuring the loss probability δ

_n of packets introduced into said network by said leaky bucket control circuit;

defining adaptation regions on the values of said simultaneous mean bit rate and loss probability measurements;

in response to a pair of said mean bit rate and loss probability measurements falling outside said adaptation regions, modifying the bandwidth allocated to a connection between said source node and said destination node;

wherein said step of defining adaptation regions comprises the step of;

determining boundaries on values of said mean bit rate m_n and said packet loss probability ξ

_n satisfying the relationships;

space="preserve" listing-type="equation">ξ

.sub.n =ξ

.sub.H,ξ

.sub.n =ξ

.sub.L,m.sub.n =γ

,

where;

ξ

_H, ξ

_L are constants having an order of magnitude range of values around said loss probability measurements,

ξ

_L <

ξ

_H

γ

is the amount of bandwidth allocated to the connection

and wherein said step of modifying the bandwidth allocated to the connection comprises the steps of;

increasing the amount of bandwidth γ

allocated when;

space="preserve" listing-type="equation">ξ

.sub.n >

ξ

.sub.H

decreasing the amount of bandwidth γ

allocated when;

space="preserve" listing-type="equation">ξ

.sub.n <

ξ

.sub.L and m.sub.n <

γ

.

2. The method according to claim 1 wherein

said step of measuring the mean bit rate comprises the further step of:

filtering a plurality of said mean bit rate measurements,

and said step of measuring the loss probability comprises the further step of;

filtering a plurality of said loss probability measurements.

3. The method according to claim 2, wherein said step of modifying the bandwidth allocated to the connection comprises the step of:

determining a new mean burst duration b for the signal on the connection, the bandwidth allocated to the connection being an increasing function of the burst duration.

4. The method according to claim 3, wherein said step of defining adaptation regions comprises the step of:

determining boundaries on filtered values of said mean bit rate m_n and said packet loss probability ξ

_n satisfying the relationship;

space="preserve" listing-type="equation">ξ

.sub.n =ξ

.sub.H,ξ

.sub.n =ξ

.sub.L,m.sub.n =γ

space="preserve" listing-type="equation">m.sub.n =β

.m,

where β

is a constant, and m is the value of the mean bit rate used for the current bandwidth allocation,

wherein said step of determining a new mean burst duration comprises the step of computing;

b=b_-- max, where b_-- max is a constant

when 602b;

ξ

_n >

ξ

_H and m_n ≧

γ

##EQU7## when 602a ξ

_n >

ξ

_H and m_n ≦

γ

b=b/c

where c is a constant >

1,

when 601a;

ξ

_n <

ξ

_L, m_n <

γ and

m_n ≦

β

.m. ##EQU8## when 601b;

ξ

_n <

ξ

_L, m_n <

γ and

m_n >

β

.m. where;

R;

maximum bit rate, in bits per second, of the signal at the source node;

m_n ;

filtered value of the mean bit rate;

ξ

_n ;

filtered value of the red marking probability;

γ

;

equivalent capacity allocated to a connection; and

M;

maximum size of the green token pool in the leaky bucket.

5. The method according to claim 4 wherein said step of determining a new burst duration comprises the further step of computing:

m=m_n ##EQU9## where;

X is the amount of buffer space (in bits) available on any link along the path of the connection in the network,

ρ

=m/R,

ε

is the target maximum packet loss probability, and ##EQU10##

6. The method according claim 5 wherein said step of decreasing the amount of bandwidth γ

allocated to the connection is triggered after a pre-determined period of time with;

ξ

_n =ξ

_L, m_n =γ

.

7. A system for adapting access to a packet switching network comprising:

a) a dynamic bandwidth adaptation mechanism which continuously monitors the mean bit rate of a signal source and the loss probability of a connection in the network;

b) means for filtering the mean bit rate and loss probablilty values to remove noise;

c) means for testing whether the values fall within a pre-defined acceptable adaptation region in a mean bit rate, loss probability plane;

d) means for triggering bandwidth adaptation procedures when values fall outside of the region; and

e) means for acquiring a new connection bandwidth, and determining new parameters for the adaptation mechanism when the values fall outside of the region.

8. A packet communication network comprising:

a) a plurality of nodes;

b) means for interconnecting source nodes and destination nodes for establishing a connection having an allocated bandwidth for the transmission of digital packets of information from a source node to a destination node in the network;

c) a dynamic access control mechanism;

d) a leaky bucket control circuit for controlling a flow of signals from a source node into the network;

e) first means for measuring a mean bit rate of the signals to the leaky bucket and providing a first input to the dynamic access control mechanism;

f) means for measuring first and second loss probabilities for packets launched by the leaky bucket control circuit into the network and providing a second input to the dynamic access control mechanism;

g) means for establishing limits on the values of simultaneous pairs of measurements from said first means and said second loss probability;

h) means responsive to a pair of mean bit rate and second loss probability measurements falling outside of said limits for modifying the bandwidth allocated to the connection; and

i) supervising means coupled to the dynamic access control mechanism for calculating a fairness variable used in controlling requests for bandwidth allocation modifications among a plurality of connections.

9. In a packet communication network including a plurality of interconnected source nodes and destination nodes for establishing a connection having an allocated bandwidth for the transmission of digital packets of information from a source node to a destination node in the network, a method for dynamically modifying bandwidth allocated to the connection to the network comprising the steps of:

a) controlling a flow of signals from a source node into the network through a leaky bucket control circuit;

b) measuring a mean bit rate of the signals to the leaky bucket and providing a first input to a dynamic access control mechanism;

c) measuring first and second loss probabilities for packets launched by the leaky bucket control circuit into the network and providing a second input to the dynamic access control mechanism;

d) establishing limits on the values of simultaneous pairs of measurements from the mean bit rate and said second loss probability;

e) modifying the bandwidth allocated to the connection using the dynamic access control mechanism according to a pair of mean bit rate and second loss probability measurements falling outside of said limits; and

f) supervising the modification of bandwidth allocations among a plurality of connections.