Simple admission control for IP based networks

• US 7,489,632 B2
• Filed: 03/22/2002
• Issued: 02/10/2009
• Est. Priority Date: 03/22/2002
• Status: Expired due to Fees

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Lakkakorpi, Jani
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): Jain, Raj K
• Application Number:
  US10/105,067
• Publication Number:
  US 20030179704A1
• Time in Patent Office: 2,517 Days
• Field of Search: None
• US Class Current: 370/231
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/808 User-type aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04L 47/826 Involving periods of time
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 48/06 based on traffic conditions
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 80/04 Network layer protocols, e.g. mobile IP [Internet Protocol]

Abstract

A simple admission control mechanism for IP based networks is provided. The decision on whether a new flow is accepted is based on the link load information on the paths from the source to destination. The new flow is accepted when the link load is less than a threshold. When at least one of the links on all of the available paths is larger than the acceptable threshold, access is denied to the flow. More than one threshold level may be used. Under the multiple threshold scenario, the traffic may be divided into different classes. The admission control mechanism helps to ensure a network that is not heavily congested.

Claims

1. A method comprising:

determining when a flow arrives;

for each of a plurality of links within a path for the flow, receiving a message indicating whether or not the link is congested;

determining from the plurality of received messages whether or not the path is congested; and

accepting the flow if the path is determined not to be congested, wherein accepting the flow comprises one of sending a packet over one of the plurality of links that was received on another of the plurality of links or sending a bandwidth broker message to each node through which one of the plurality of links passes, where the bandwidth broker message comprises one of link loads for the plurality of links or configuration rules for the flow.

2. The method of claim 1, wherein determining whether or not the path is congested further comprises receiving in each message a link load, and comparing each received link load to a predetermined threshold to determine whether or not the path is congested.

3. The method of claim 1, wherein the network comprises a radio access network.

4. The method of claim 1, wherein each of the messages indicating whether or not the link is congested is received:

upon at least one of the conditions;

a change to a congestion status of the link; and

expiration of a timer.

5. The method of claim 1, wherein each of the messages indicate congestion by a link load that is represented by an exponential averaging equation.

6. The method of claim 1, executed by a bandwidth broker.

7. The method of claim 5, wherein the exponential averaging equation is:

link load=(1−

w)*link load_i-1+w*(8*bytes per period_i/(p*link capacity)),

wherein link capacity is bits per second, w is a weighting parameter and p is a measurement period parameter over a time period for which the load is measured.

8. The method of claim 1, wherein determining from the received plurality of messages whether the at least one path is congested comprises reading from each received message a congestion bit indicating the link is congested or not congested.

9. The method of claim 1, wherein a new message is received for each link no more frequently than when that link changes between congested and not congested, and expiration of a timer kept by a node through which that link passes.

10. The method of claim 1, wherein determining when a flow arrives further comprises determining a service class of the flow;

and further wherein determining whether or not the path is congested is specific for the service class.

11. The method of claim 1, wherein there are a plurality of paths for the flow, wherein a message is received from each link within each of the plurality of paths indicating whether or not the link is congested and determining whether or not the path is congested is for each of the plurality of paths, and wherein accepting the flow comprises choosing a least congested path from among the plurality of paths.

12. A computer readable storage medium storing computer executable instructions when executed by a computer perform the following:

for each of a plurality of links within a path through a network, receiving a message from a node through which the link passes that indicates whether or not the link is congested;

determining from the plurality of messages whether or not the path is congested; and

accepting a new flow that is satisfied by the path if the at path is determined not to be congested, wherein accepting the new flow comprises one of sending over one of the plurality of links a packet that was received on another of the plurality of links or sending a bandwidth broker message to each of the nodes through which one of the plurality of links passes, where the bandwidth broker message comprises one of link loads for the plurality of links or configuration rules for the new flow.

13. The computer-readable storage medium of claim 12, wherein determining from the plurality of messages whether or not path is congested further comprises receiving in each message a link load, and comparing the link load to a predetermined threshold.

14. The computer-readable storage medium of claim 12, wherein determining from the plurality of messages whether or not the path is congested further comprises calculating a link load from each of the messages.

15. The computer-readable storage medium of claim 14, wherein the link load is computed as:

link load_i=(1−

w)*link load_i-1+w*(8*bytes per period_i/(p*link capacity)),

wherein link capacity is bits per second, w is a weighting parameter and p is a measurement period parameter over a time period for which the load is measured.

16. The computer-readable storage medium of claim 12, wherein the network comprises a radio access network.

17. The computer-readable storage medium of claim 12, wherein the computer readable storage medium and processor are disposed in a bandwidth broker.

18. The computer-readable storage medium of claim 12, wherein the instructions further comprise determining a service class of the new flow;

and further wherein determining whether or not the at least one path is congested is specific for the service class.

19. The computer-readable storage medium of claim 12, wherein the instructions operate for a plurality of paths through the network and each link is within at least one of the plurality of paths, and wherein accepting the flow comprises choosing a path from among the plurality of paths based on a parameter selected from the group:

least congested;

number of hops; and

shortest distance.

20. A system comprising:

nodes arranged along an available path through an internet protocol based network, each node comprising a network interface unit arranged to communicate across the network a message indicating whether or not a link through the node is congested or not congested; and

a bandwidth broker that is configured to process information relating to each of the messages received from the nodes, wherein the bandwidth broker comprises;

a network interface unit arranged to communicate with the nodes;

a processor; and

an admission control program embodied on a computer-readable storage medium executing under the control of an operating system and operative to perform actions, including;

receiving from each of the nodes the congested or the not-congested message; and

for a new flow between a source and destination coupled by the available path, accepting the new flow if the message from each node along the available path is a not-congested message,

wherein accepting the new flow comprises sending from the network interface unit a bandwidth broker message to each of the nodes, where the bandwidth broker message comprises one of link loads for the nodes or configuration rules for the new flow.

21. The system of claim 20, wherein the internet protocol-based network comprises a radio access network.

22. The system of claim 20, wherein each node further comprises a processor configured to calculate a link load, and wherein the message is based on a comparison of the link load to a threshold.

23. The system of claim 22, wherein the link load is calculated according to:

link load_i=(1−

w)*link load_i-1+w*(8*bytes per period_i/(p*link capacity)),

where w is a weighting parameter and p is a measurement period parameter over a time period for which the load is measured.

24. The system of claim 20, wherein the instructions further comprise:

calculating at the bandwidth broker a link load from each of the received messages.

25. An apparatus comprising:

means for determining when a flow arrives;

means for determining, from a plurality of messages, each message received from a node associated with a link within an available path for the flow, whether the available path is congested; and

means for accepting the flow when the available path is determined not to be congested, wherein accepting the flow comprises one of sending from a sending means over one of the links a packet that was received on another of the links or sending a bandwidth broker message to each of the nodes, where the bandwidth broker message comprises one of link loads for the links or configuration rules for the new flow.

26. The apparatus of claim 25, wherein:

the means for determining when a flow arrives comprises a processor coupled to a network interface unit;

the means for determining whether the available path is congested and the means for accepting the flow comprises the processor; and

the sending means comprises the network interface unit.

27. An apparatus comprising:

a processor and a network interface that are configured to determine when a flow arrives;

the processor configured to determine from a plurality of messages, each message received from a node associated with a link within an available path for the flow, whether the available path is congested; and

the network interface configured to accept the flow when the available path is determined not to be congested by one of sending over one of the links a packet that was received on another of the links or sending a bandwidth broker message to each of the nodes, where the bandwidth broker message comprises one of link loads for the links or configuration rules for the new flow.

28. The apparatus of claim 27 comprising a bandwidth broker.

29. The apparatus of claim 27, wherein each of the plurality of messages comprises a link load, and the processor is configured to determine whether the available path is congested by comparing the link load of each of the plurality of messages to a

30. The apparatus of claim 29, wherein the link load is represented by an exponential averaging equation.

31. The apparatus of claim 30, wherein the exponential averaging equation is:

link 1oad_i=(1−

w)*link load_1-1+w*(8*bytes per period_i/(p*link capacity)),

wherein link capacity is bits per second, w is a weighting parameter and p is a measurement period parameter over a time period for which the load is measured.