Dynamic bandwidth estimation and adaptation in high speed packet switching networks

• US 5,815,492 A
• Filed: 02/27/1997
• Issued: 09/29/1998
• 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: Galand, Claude, Berthaud, Jean-Marc, Nicolas, Laurent, Foriel, Pierre-Andre, Lengelle, Stephane
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): BAKER, WILBUR TODD
• Application Number:
  US08/807,499
• Time in Patent Office: 579 Days
• Field of Search: 370/234, 370/230, 370/232, 370/253
• US Class Current: 370/234
• 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/5684 Characteristics of traffic flows
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/32 Specific management aspects for broadband networks
• CPC Class Codes: H04L 43/028 by filtering
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 49/105 ATM switching elements
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/503 Policing

Abstract

Method and system for adapting access to a packet switching network including a dynamic bandwidth adjustment mechanism which continuously monitors the mean bit rate of the signal source and the loss probability of the connection. These values are filtered to remove noise and then used to test whether the values fall within a pre-defined acceptable adaptation region in the mean bit rate, loss probability plane. Values falling outside of this region trigger bandwidth adaptation procedures which, in turn, result in acquiring a new connection bandwidth, and determining new parameters for the adaptation mechanism. Furthermore, the mechanism controls the number of connections that can be adapted by a single processor, given its processing capability. It ensures fairness between the connections in the sense that it prevents a single connection from using, on the average, a greater portion of the processor capacity than it should.

Claims

1. A method for dynamically controlling access by data sources to a packet data communication network interconnecting source and destination nodes, each source node having at least one management system for controlling access to the network by a data source connected to the source node, including for each said data source the steps of:

measuring the mean bit rate of the traffic emanating from the data source;

controlling the flow of data packets from the data source into the network;

measuring the loss probability of data packets introduced into the network;

performing a low pass filter operation on the loss probability measurements;

defining adaption regions based on the simultaneous mean bit rate and loss probability measurements;

in response to pairs of said mean bit rate and loss probability measurements falling outside the adaption regions, requesting modification of the bandwidth allocated to the transmission of data packets;

measuring the average number of bandwidth modification requests; and

modifying the characteristics of the low pass filtering step as a function of the average number of bandwidth modification requests.

2. The method according to claim 1 wherein said step of measuring an average number of bandwidth modification requests comprises the further step of:

filtering said average number of bandwidth modification request measurements.

3. The method according to claim 1 wherein:

the more the average number of bandwidth modifications requested for the same processor increases, the more the bandwidth of the low pass filter (109) decreases.

4. The method according to claim 1 wherein

the more often a connection requires modification of its allocated bandwidth, the less the management system gives priority to said requests, and

the less often a connection requires modification of its allocated bandwidth, the more the link processor gives priority to said requests.

5. In a packet data communication network for interconnecting source and destination nodes, at least one management system, each for controlling access to the network by a data source connected to the source node comprising:

means for measuring the mean bit rate of the traffic emanating from the data source;

a leaky bucket circuit for controlling the flow of data packets from the data source into the network;

means for measuring the loss probability of data packets introduced into the network;

a low pass filter for filtering the loss probability measurements;

means for defining adaption regions based on the simultaneous mean bit rate and loss probability measurements;

means responsive to pairs of said mean bit rate and loss probability measurements falling outside the adaption regions for requesting modification of the bandwidth allocated to the transmission of data packets;

means for measuring the average number of bandwidth modification requests; and

means for modifying the characteristics of the low pass filter as a function of the average number of bandwidth modification requests.

6. A communications network according to claim 5 further comprising means for filtering said average number of bandwidth modification request measurements.