Methods and apparatus for distributed control of a multi-class network

• US 6,404,735 B1
• Filed: 05/01/1998
• Issued: 06/11/2002
• Est. Priority Date: 04/30/1998
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Beshai, Maged E., Vickers, Richard
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US09/071,344
• Time in Patent Office: 1,502 Days
• Field of Search: 330/229-235, 330/252, 330/389, 330/395, 330/400, 330/401, 330/412, 330/428, 330/429, 330/431, 330/437, 330/468, 330/465
• US Class Current: 370/230
• 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/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/741 Holding a request until resources become available
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/806 Broadcast or multicast traffic
• CPC Class Codes: H04L 47/821 Prioritising resource allocation or reservation requests
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04Q 2213/13107 Control equipment for a part of the connection, distributed control, co-processing
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13164 Traffic (registration, measurement,...)
• CPC Class Codes: H04Q 2213/13166 Fault prevention
• CPC Class Codes: H04Q 2213/13167 Redundant apparatus
• CPC Class Codes: H04Q 2213/1325 Priority service
• CPC Class Codes: H04Q 2213/13251 Restricted service, class of service
• CPC Class Codes: H04Q 2213/1329 Asynchronous transfer mode, ATM
• CPC Class Codes: H04Q 2213/13293 TASI, irregular time division, burst switching
• CPC Class Codes: H04Q 2213/13296 Packet switching, X.25, frame relay
• CPC Class Codes: H04Q 2213/13332 Broadband, CATV, dynamic bandwidth allocation
• CPC Class Codes: H04Q 2213/13352 : Self-routing networks, real-time routing
• CPC Class Codes: H04Q 2213/13353 : Routing table, map memory
• CPC Class Codes: H04Q 2213/1338 : Inter-exchange connection
• CPC Class Codes: H04Q 2213/13389 : LAN, internet
• CPC Class Codes: H04Q 2213/13392 : Channels assigned according to rules
• CPC Class Codes: H04Q 3/66 : Traffic distributors

Abstract

Methods and apparatus for control of a multi-class digital network are described. The network supports a plurality of digital services using dynamically-configured service bands to support various transport modes and qualities of service. Flexible controls with two degrees of freedom are used at the node level to dynamically configure the transport bands. The first degree of freedom is realized using adaptive alternate routing to balance the traffic intensity across the network and, hence, increase the efficiency of the band. The second degree of freedom is achieved through adaptive network partitioning to provide elasticity to the band structure. This permits band capacity to be adaptively reconfigured as connections are added and dropped. The switching nodes use rate controllers to divide the capacity of each link among the connection classes according to rules which ensure consistent service attributes for each band across the network. The rate controllers are adapted to support different transport modes and different packet sizes so that the deconstruction and reconstruction of packets at network edge devices is eliminated. The advantage is a flexible multi-class network which dynamically reconfigures to service traffic loads as service demands fluctuate.

Claims

1. A method of controlling traffic admission and routing in a multi-class digital network serving variable-size packets, comprising steps of:

computing an equivalent bit rate for each traffic admission request as received at a node in the network;

determining whether a connection for the traffic admission request can be established through the network;

in an instance when the connection can be established, adding the equivalent bit rate for the traffic admission request to the current service rate allocation of a class of traffic being served by an egress link through which the connection is established, to permit a service rate controller to control transmission of each class on the egress link;

wherein determining whether the connection for the traffic admission request can be established through the network includes steps of;

(a) determining a class of service to which the traffic admission request belongs;

(b) selecting a direct path to a destination for the traffic admission request if a direct path exists for the class to which the traffic seeking admission belongs, and the path has adequate bandwidth available to accommodate the traffic;

else

(c) selecting a routing method associated with the class;

(d) examining, in a predetermined order, route sets associated with the destination to determine if the egress link exists with the adequate available bandwidth to accommodate the traffic; and

(e) if the egress link is found, attempting to establish a connection for the traffic on the link;

else

(f) rejecting the traffic admission request;

and wherein the routing methods which may be associated with a class of service comprise;

(a) shortest path hop-by-hop routing;

(b) selective routing using a conservative scheme; and

(c) selective routing using true-state information;

and wherein the shortest path hop-by-hop routing comprises the steps of;

(a) comparing in the predetermined order an occupancy state of links in a set of routes associated with the destination, and selecting the most vacant link in the set of routes where at least one link has adequate available bandwidth for the traffic admission requests;

(b) determining a number of hops in a shortest path to the destination for the traffic admission request given the selected link;

(c) assigning a number of route selection credits to the traffic admission request, the number of route selection credits equaling the number of hops in the shortest available path, plus two;

(d) forwarding a traffic admission request message to a node associated with an opposite end of the selected link;

(c) subtracting one from the credits at the node associated with the opposite end of the selected link; and

(f) repeating steps (a), (d) and (e) without returning to an immediately preceding node until a connection is established to the destination, or the route selection credits are exhausted in which case the traffic admission request is rejected.

2. A method of controlling traffic admission and routing in a multi-class digital network serving variable-size packets, comprising steps of:

computing an equivalent bit rate for each traffic admission request as received at a node in the network;

determining whether a connection for the traffic admission request can be established through the network;

in an instance when the connection can be established, adding the equivalent bit rate for the traffic admission request to the current service rate allocation of a class of traffic being served by an egress link through which the connection is established, to permit a service rate controller to control transmission of each class on the egress link;

wherein determining whether the connection for the traffic admission request can be established through the network includes steps of;

(a) determining a class of service to which the traffic admission request belongs;

(b) selecting a direct path to a destination for the traffic admission request if a direct path exists for the class to which the traffic seeking admission

(c) selecting a routing method associated with the class;

(d) examining, in a predetermined order, route sets associated with the destination to determine if the egress link exists with the adequate available bandwidth to accommodate the traffic; and

(e) if the egress link is found, attempting to establish a connection for the traffic on the link;

else

(f) rejecting the traffic admission request;

and wherein the routing methods which may be associated with a class of service comprise;

(a) shortest path hop-by-hop routing;

(b) selective routing using a conservative scheme; and

(c) selective routing using true-state information;

and wherein the selective routing using a conservative scheme comprises the steps of;

(a) selecting at most two links with adequate bandwidth to accommodate the admission request;

(b) debiting an available capacity of the at most two links selected by the equivalent bit rate computed for the traffic admission request;

(c) forwarding a traffic admission request message to a node associated with an opposite end of the at most two links;

(d) repeating steps (a) to (c) until a connection for the traffic admission request is established or the traffic admission request is rejected; and

(e) crediting an available capacity of any link debited which did not become a link in the connection after the connection is established or the traffic admission request is rejected.

3. A method of controlling traffic admission and routing in a multi-class digital network serving variable-size packets, comprising steps of:

computing an equivalent bit rate for each traffic admission request as received at a node in the network;

determining whether a connection for the traffic admission request can be established through the network;

in an instance when the connection can be established, adding the equivalent bit rate for the traffic admission request to the current service rate allocation of a class of traffic being served by an egress link through which the connection is established, to permit a service rate controller to control transmission of each class on the egress link;

wherein determining whether the connection for the traffic admission request can be established through the network includes steps of;

(a) determining a class of service to which the traffic admission request belongs;

(b) selecting a direct path to a destination for the traffic admission request if a direct path exists for the class to which the traffic seeking admission belongs, and the path has adequate bandwidth available to accommodate the traffic;

else

(c) selecting a routing method associated with the class;

(d) examining, in a predetermined order, route sets associated with the destination to determine if the egress link exists with the adequate available bandwidth to accommodate the traffic; and

(e) if the egress link is found, attempting to establish a connection for the traffic on the link;

else

(f) rejecting the traffic admission request;

and wherein the routing methods which may be associated with a class of service comprise;

(a) shortest path hop-by-hop routing;

(b) selective routing using a conservative scheme; and

(c) selective routing using true-state information;

and wherein the selective routing using a true-state scheme comprises;

(a) selecting at most two links with adequate bandwidth at an originating node to accommodate the traffic admission request;

(b) declaring at the at most two links unavailable to another route selection process of a same class of service until a connection to a destination is established or rejected;

(c) forwarding a traffic admission request message to a node associated with an opposite end of the at most two links;

(d) determining if a next link in a route associated with each of the at most two links has adequate bandwidth to accommodate the traffic admission request and repeating steps (b) and (c) until a connection for the traffic admission request is established or the traffic admission request is rejected; and

(e) if the connection is established, instructing from a controlling node all other nodes to debit an available capacity of links in the connection;

else

(f) declaring the at most two links available to other route selection processes.

4. A method of controlling traffic admission and routing in a multi-class digital network serving variable-size packets, comprising steps of:

computing an equivalent bit rate for each traffic admission request as received at a node in the network;

determining whether a connection for the traffic admission request can be established through the network;

in an instance when the connection can be established, adding the equivalent bit rate for the traffic admission request to the current service rate allocation of a class of traffic being served by an egress link through which the connection is established, to permit a service rate controller to control transmission of each class on the egress link;

wherein the combined service rate allocations for all classes of traffic being served by the egress link satisfies the condition;

$0<<br><br>f_j=\frac{F_j}{R}<<br><br>1,j=0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},K-1,\mathrm{with}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{j=0}{\overset{K-1}{\sum <br><br>}}<br><br>f_j<<br><br>1$

10 wherein;

K is the number of classes;

R is the link rate in bits per second;

F_j is the required service allocation for class j in bits per second; and

f_j is the normalized service rate for class j.

5. A link controller for a transport link in a multi-class digital network serving variable-length packets, comprising:

a service rate controller adapted to control an egress of variable-sized packets on the link, the service rate controller comprising;

a) a sampling frequency memory for storing a class service allocation computed by a node control element in response to a traffic load for the class at a specific point in time;

b) an adder adapted to add a value of the class service allocation to an adder memory after counting a predetermined number of clock signals;

c) a comparator adapted to compare a value in the adder memory to a normalized packet size;

d) a selector for visiting each comparator and writing a class number to a ready queue when the comparator determines that the value in the adder memory is greater than or equal to the normalized packet size; and

e) a buffer for each class, the buffers storing packets to be transferred onto the link when the class number reaches a head of the ready queue.

6. A link controller for a transport link in a multi-class digital network as claimed in claim 5 wherein a clock that produces the clock signals is a clock that is local to the link controller.

7. A link controller for a transport link in a multi-class digital network as claimed in claim 6 wherein the clock produces clock signals at a rate which is equal to a time required to transfer a smallest packet accommodated by the link.

8. A link controller for a transport link in a multi-class digital network as claimed in claim 5 wherein the service rate controller is adapted to control an egress of variable-sized packets using different transport modes, each transport mode consisting of at least one transport protocol and traffic using different transport modes are assigned to different classes.

9. A method of computing an equivalent bit rate (EBR) for a traffic admission request to a multi-class network, comprising the steps of:

(a) computing at a node control element where a traffic admission request is received, an EBR and parameters which may be used in subsequent nodes to compute an approximated EBR, the approximated EBR being used to determine in subsequent nodes whether link capacity exists to accept the traffic admission request;

(b) passing the parameters to an adjacent node control element;

(c) computing at the adjacent node an approximated EBR using the parameters in a simplified interpolation formula; and

(d) repeating steps (b) and (c) until a connection is established or the admission request is rejected;

wherein the simplified interpolation formula is a hyperbolic approximation having the form;

$\mathrm{\Omega <br><br>}={\mathrm{\Omega <br><br>}}_{\mathrm{\infty <br><br>}}+\frac{a}{R+b}$

 

wherein

Ω

is the approximated EBR;

R is the link capacity of a link selected in response to the traffic admission request; and

Ω

_∞

, a and b are the computed parameters.

10. A method of computing an equivalent bit rate (EBR) as claimed in claim 9 wherein Ω

_∞

is computed using formula;

11. A method of computing an equivalent bit rate (EBR) as claimed in claim 9 wherein the traffic admission request is for traffic to be multicast.