Providing admission control and network quality of service with a distributed bandwidth broker

• US 6,487,170 B1
• Filed: 11/18/1998
• Issued: 11/26/2002
• Est. Priority Date: 11/18/1998
• Status: Expired due to Fees

• Current Assignee: Avaya Incorporated
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Figueira, Norival R., Chen, Shenze
• Primary Examiner(s): Yao, Kwang Bin
• Assistant Examiner(s): NGUYEN, HANH N
• Application Number:
  US09/195,348
• Time in Patent Office: 1,469 Days
• Field of Search: 370/468, 370/477, 370/230, 370/231, 370/235, 370/236, 370/400, 370/401, 370/410-413, 370/415, 370/419, 370/389, 370/390, 370/395.2, 370/396, 370/395.41, 370/395.51, 370/230.1, 370/232-234, 370/351, 709/227, 709/226, 709/229, 709/238, 709/225
• US Class Current: 370/231
• CPC Class Codes: H04L 12/1827 Network arrangements for conference optimisation or adaptation
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/806 Broadcast or multicast traffic
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data

Abstract

A method and apparatus are provided for making admission decisions in a packet switched network, such as a Differentiated Services (DiffServ) Packet Network. According to one aspect of the present invention, admission control decisions are based upon local information. An average premium service bandwidth utilized on an output link of a network device during a predetermined window of time is calculated. A determination regarding whether to accept or reject a request for a premium service flow involving the output link is made based upon the request, a total premium service bandwidth available on the output link, the average premium service bandwidth, and bandwidth request information associated with one or more flows that have been admitted within a predetermined holding time interval. According to another aspect of the present invention, multicast flows are supported. A measure of utilized premium service bandwidth is calculated for each of the output links of a multicast-capable network device. A request for premium service bandwidth for a multicast session is forwarded onto those of the output links specified by a multicast routing protocol which have sufficient premium service bandwidth available to accommodate the request based upon the total premium service bandwidth available on the output link, the measure of utilized premium service bandwidth on the output link, and the request. For each of the output links associated with the multicast session, a link state is maintained. The link state indicates the current state of a state machine that determines the behavior of the multicast-capable network device for the corresponding output link of the multicast session. Multicast packets that are subsequently received are forwarded according to the link states associated with the output links.

Claims

1. A method of making admission control decisions in a packet switched network, the method comprising:

calculating an average premium service bandwidth used during a predetermined window of time on an output link of a network device; and

determining whether to accept or reject a request for a premium service flow by evaluating the following expression;

2. The method of claim 1, wherein the network device is a multicast-capable network device and includes a plurality of output links, the method further comprising:

receiving a second request, the second request for premium service bandwidth for a multicast session;

forwarding the second request onto one or more of the plurality of output links that are associated with the multicast session as determined by a multicast routing protocol and which have sufficient premium service bandwidth available to accommodate the second request based upon a total premium service bandwidth available on the output link, a measure of utilized premium service bandwidth on the output link, and the second request;

maintaining a link state for each of the one or more output links that are associated with the multicast session, the link state indicating a current state of a state machine that determines the behavior of the multicast-capable network device for the corresponding output link of the multicast session; and

forwarding packets that are part of the multicast session according to the link states associated with the one or more output links.

3. The method of claim 2, further comprising:

forwarding data packets that are part of the multicast session as best-effort traffic over those of the one or more output links having link states associated with a first state of the state machine, the first state representing a state in which the corresponding output link is waiting for an admission decision for the second request from a branch of its downlink sub-tree; and

forwarding data packets that are part of the multicast session as premium service traffic over those of the one or more output links having link states associated with a second state of the state machine, the second state representing a state in which the corresponding output link has received an indication that a branch of its downlink sub-tree has accepted the second request.

4. A method of making admission control decisions in a packet switched network, the method comprising:

calculating an average premium service bandwidth used during a predetermined window of time on an output link of a network device; and

determining whether to accept or reject a request for a premium service flow involving the output link based upon the request, a total premium service bandwidth available on the output link, the average premium service bandwidth, and bandwidth request information associated with one or more flows that have been admitted within a predetermined holding time interval, the determining of whether to accept or reject the request comprises accepting the request when the following expression is true and rejecting the request when it is false;

5. A method of making admission control decisions in a Differentiated Services Packet Network, the method comprising:

determining a measure of utilized premium service bandwidth on an output link of a network device by

periodically calculating an average premium service bandwidth used during a predetermined window of time, and

adding to the average premium service bandwidth a bandwidth associated with a flow that has been admitted but that has not yet started to inject premium packets onto the output link; and

determining whether to accepting or reject a request for a premium service flow involving the output link based upon a total premium service bandwidth available on the output link, the measure of utilized premium service bandwidth on the output link and the request, the determining whether to accepting or reject the request comprises accepting the request when the following expression is true and rejecting the request when it is false;

6. A method of making admission control decisions regarding premium unicast flows in a packet switched network without maintaining permanent per-flow state information for accepted unicast flows, the method comprising:

temporarily storing bandwidth request information associated with admitted unicast flows that have been admitted within a predetermined holding time interval;

calculating an average premium service bandwidth used during a predetermined window of time on an output link of a network device;

determining whether to accept or reject a request for a premium service flow involving the output link based upon the request, a total premium service bandwidth available on the output link, the average premium service bandwidth, and the bandwidth request information based on an expression;

7. A method of making admission control decisions in a Differentiated Services Packet Network, the method comprising:

periodically determining a measure of utilized premium service bandwidth on an output link of a network device based upon an average premium service bandwidth used during a predetermined window of time and requested bandwidth associated with at least one flow that has been admitted but that has not yet started to inject premium packets onto the output link;

receiving a request for premium service bandwidth over the output link; and

determining whether to accepting or reject the request based upon a total premium service bandwidth available on the output link, the measure of utilized premium service bandwidth on the output link, and the request in accordance with an expression;

8. A method of managing multicast flows in a Differentiated Services Packet Network, the method comprising the steps of:

receiving a request for premium service bandwidth for a multicast flow;

identifying one or more output links of a multicast-capable network device that are part of the multicast flow;

forwarding the request onto those of the one or more output links that satisfy an admission criterion, the admission criterion comprises the following expression;

9. The method of claim 8, wherein the state machine has an initial state to which all new multicast flows are initialized, a flow pending state in which the associated output link has satisfied the admission criterion and is waiting for an admission decision for the request from a branch of its downlink sub-tree, a flow established state in which the associated output link has received an indication that a branch of its downlink sub-tree has accepted the request, and a flow refresh state in which the associated output link has forwarded a repeated request and is waiting for an admission decision for the repeated request from a branch of its downlink sub-tree, and wherein the method further comprises:

forwarding data packets as best-effort traffic over those of the one or more output links having a link state associated with the initial state or the flow pending state; and

forwarding data packets as premium service traffic over those of the one or more output links having a link state associated with the flow established state or the flow refresh state.

10. The method of claim 9, wherein the maintaining of the link state for each of the one or more output links comprises:

transitioning from the initial state to the flow pending state after determining that the output link satisfies the admission criterion;

transitioning from the flow pending state to the flow established state after receiving an admission decision on the output link;

transitioning from the flow established state to the flow refresh state after receiving a repeated request for the multicast flow.

11. The method of claim 10, wherein the maintaining of the link state for each of the one or more output links further comprises:

transitioning from the refresh state to the flow established state after receiving an admission decision on the output link;

transitioning from the refresh state to the flow pending state after receiving no admission derision on the output link for a first predetermined time interval;

transitioning from the flow pending state to the initial state after receiving no admission decision on the output link for a second predetermined time interval.

12. The method of claim 11, wherein the maintaining of the link state for each of the one or more output links further comprises:

remaining in the initial state after deter mining that the output link does not satisfy the admission criterion;

remaining in the flow pending state after receiving subsequent requests;

remaining in the flow established state after receiving subsequent admission decisions on the output link; and

remaining in the flow refresh state after receiving subsequent requests.

13. The method of claim 10, further comprising:

in the initial state, after determining that the output link satisfies the admission criterion, forwarding the request on the output link and transitioning to the flow pending state;

in the flow pending state, after receiving an admission decision on the output link, forwarding the admission decision upstream and transitioning to the flow established state;

in the flow established state, after receiving a repeated request for the multicast flow, forwarding the repeated request onto each of the one or more output links and transitioning to the flow refresh state.

14. The method of claim 13, further comprising:

in the refresh state, after receiving an admission decision on the output link, forwarding the admission decision upstream and transitioning to the flow established state;

in the refresh state, after receiving no admission decision on the output link for a first predetermined time interval, transitioning to the flow pending state;

in the flow pending state, after receiving no admission decision on the output link for a second predetermined time interval, transitioning to the initial state.

15. The method of claim 14, wherein the maintaining of the link state for each of the one or more output links further comprises:

in the initial state, after determining that the output link does not satisfy the admission criterion, remaining in the initial state;

in the flow pending state, after receiving subsequent requests, forwarding the subsequent requests on the output link and remaining in the flow pending state;

in the flow established state, after receiving subsequent admission decisions on the output link, dropping the subsequent admission decisions and remaining in the flow established state; and

in the flow refresh state, after receiving subsequent requests, forwarding the subsequent requests on the output link and remaining in the flow refresh state.

16. A network device comprising:

a storage device having stored therein one or more routines for implementing admission control policy based on local information;

a processor coupled to the storage device for executing the one or more routines to make an admission decision regarding a request for establishment of a flow, where;

an average premium service bandwidth utilized during a predetermined window of time is determined for an output link through which the flow will pass;

bandwidth request information associated with one or more flows that have been admitted within a predetermined time interval is temporarily stored; and

an admission criterion is evaluated based upon a following expression;