Routing and rate control in a universal transfer mode network

• US 20030189947A1
• Filed: 04/16/2003
• Published: 10/09/2003
• Est. Priority Date: 08/11/1998
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Beshai, Maged E.
• Granted Patent: US 7,310,349 B2
• Time in Patent Office: Days
• US Class Current: 370/428
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• 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/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/627 policing
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/805 QOS or priority aware
• 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: H04L 47/829 Topology based
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/505 Corrective measures

Abstract

A method and a network for a universal transfer mode (UTM) of transferring data packets at a regulated bit rate are disclosed. The method defines a protocol that uses an adaptive packet header to simplify packet routing and increase transfer speed. The protocol supports a plurality of data formats, such as PCM voice data, IP packets, ATM cells, frame relay and the like. The network preferably includes a plurality of modules that provide interfaces to various data sources. The modules are interconnected by an optic core with adequate inter-module links with preferably no more than two hops being required between any origination/destination pair of modules. The adaptive packet header is used for both signaling and payload transfer. The header is parsed using an algorithm to determine its function. Rate regulation is accomplished using each module control element and egress port controllers to regulate packet transfer. The protocol enables the modules to behave as a single distributed switch capable of multi-terabit transfer rates. The advantage is a high speed distributed switch capable of serving as a transfer backbone for substantially any telecommunications service.

Claims

1. A transfer rate regulation mechanism for a data packet switch switching variable sized packets, comprising:

a) a plurality of queues or buffers containing data packets sorted into traffic streams, the data packets in each traffic stream being associated with one or more logically related communication sessions;

d) a memory for storing a transfer rate allocation of normalized data units for each data stream, the transfer rate allocation being an accumulation of transfer rate allocations assigned to communications sessions in the respective data streams on setup of the communications sessions through a network that includes the data packet switch; and

e) a multi-stage circuit of parallel arithmetic processors, which compute an eligibility for transfer of the data packets in the respective traffic streams, based on the respective transfer rate allocations.

2. A transfer rate regulation mechanism as claimed in claim 1 wherein the plurality of queues or buffers are distributed among the stages of the multi-stage circuit, the number of queues or buffers in each stage being fewer than the number of queues or buffers in a previous stage.

3. A transfer rate regulation mechanism as claimed in claim 2 wherein a selector moves packets from a queue or buffer of a given stage to a queue or buffer in a subsequent stage based on the accumulation of transfer credits for all connections associated with the queue or buffer of the given stage.

4. A transfer rate regulation mechanism as claimed in claim 3 wherein the selectors in at least two stages of the multi-stage circuit use parallel arithmetic processors to compute an eligibility of the packets for transfer.

5. A transfer rate regulation mechanism as claimed in claim 4 wherein the multi-stage circuit is a four-stage circuit, the respective stages comprising:

1) a first plurality of queues or buffers which store an identity of data packets waiting for transfer, the data packets being sorted into logically related traffic streams;

2) a first plurality of selectors for selecting data packets eligible for transfer from the first plurality of queues or buffers using the accumulated transfer credits, the first plurality of selectors respectively visiting a predetermined subset of the first plurality of queues or buffers in a cyclical selection process;

3) a second plurality of queues or buffers for respectively receiving data packets selected for transfer by one of the first plurality of selectors;

4) a second plurality of selectors for selecting data packets eligible for transfer from the second plurality of queues or buffers using the accumulated transfer credits, the second plurality of selectors respectively visiting a predetermined subset of the second plurality of queues or buffers in a cyclical selection process and transferring packets eligible for transfer to a third plurality of queues or buffers;

5) a third selector for cyclically visiting the third plurality of queues or buffers to transfer the packets to a ready queue from which the packets are transferred to a communications link in a first-in-first-out basis.

6. A transfer rate regulation mechanism as claimed in claim 5 wherein the data packets identified in each of the first plurality of queues or buffers are logically related by respectively having a same destination and a same class of service.

7. A transfer rate regulation mechanism as claimed in claim 5 wherein the first plurality of queues or buffers are divided into a plurality of subsets, the queues of buffers in each subset containing identities of packets having a same destination.

8. A transfer rate regulation mechanism as claimed in claim 6 wherein the data packets identified in each of the second plurality of queues or buffers are logically related by respectively having the same destination.

9. A transfer rate regulation mechanism as claimed in claim 5 wherein the second selector comprises a plurality of parallel adders and a plurality of parallel egress selector circuits, the parallel adders computing the cumulative packet sizes of packets waiting in the respective queues or buffers to be transferred and the parallel egress selector circuits comparing the cumulative size of the packets waiting in the second plurality of queues of buffers with the accumulated transfer credits to determine whether the packets waiting to be transferred are eligible for transfer.

10. A transfer rate regulation mechanism as claimed in claim 9 wherein the four-stage circuit further includes a fast transfer unit to determine the number of data packets eligible for transfer when the egress selector circuit determines that the cumulative size of the packets waiting in a one of the queues or buffers is larger than the accumulated transfer credits, the fast transfer unit comprising:

a) a plurality of parallel memories for storing a size in data units of each of the packets waiting for transfer;

b) an adder for each of the plurality of parallel memories to compute a cumulative size of the data units stored in each parallel memory;

c) an adder for computing a cumulative total using the cumulative sizes; and

d) a comparator for comparing the cumulative total with the accumulated transfer credits to determine the number of packets eligible for transfer.

11. A transfer rate regulation mechanism as claimed in claim 10 wherein the comparator compares the cumulative total with the accumulated transfer credits each time the adder for computing the cumulative total adds a cumulative size to the cumulative total.

12. A transfer rate regulation mechanism as claimed in claim 5 wherein the the number of second selectors is equal to a square root of the number of queues or buffers in the first plurality of queues or buffers, rounded to the nearest integer.

13. A transfer rate regulation mechanism for a data packet switch, comprising:

a) a first plurality of buffers for storing an identity of data packets sorted into traffic streams of data packets associated with one or more communications sessions, the communications sessions being logically related;

b) a transfer rate allocation of normalized data units for each traffic stream which is stored in a rate allocation memory, the rate allocation being an accumulation of rate allocations assigned to communications sessions in the respective traffic streams on admission of the communications session to a network that includes the data packet switch;

f) a transfer credit stored in a transfer credit memory, the transfer credit being an accumulation of the normalized data units plus any normalized data units carried forward from a last transfer of packets from the respective traffic streams;

g) a rate regulator for transferring the data packets from the first plurality of buffers to a second plurality of buffers as the data packets are eligible using parallel arithemetic calculations to compute an eligibility for transfer based on the transfer credits, whereby a data packet is eligible for transfer to a one of the second plurality of buffers when a transfer credit accumulated is equal to or greater than a number of data units in the data packet; and

h) an egress selector for selecting packets from the second plurality of buffers in accordance with a respective transfer credit using parallel arithmetic calculations to determine a number of packets to be eligible for transfer based on accumulated transfer credits.

14. A transfer rate regulation mechanism as claimed in claim 13 wherein the rate regulation mechanism further comprises a ready queue for storing an identity of packets eligible for transfer to an egress link of the data packet switch.

15. A transfer rate regulation mechanism as claimed in claim 14 wherein packets are selected from the ready queue in a first-in-first-out order.

16. A transfer rate regulation mechanism as claimed in claim 13 wherein the first plurality of buffers is divided into a plurality of first subsets, the traffic streams in each subset being logically related.

17. A transfer rate regulation mechanism as claimed in claim 16 wherein the first subsets are logically related in that the traffic streams have a common destination switching module in the data network.

18. A transfer rate regulation mechanism as claimed in claim 16 wherein the second plurality of queues or buffers are divided into a plurality of second subsets.

19. A transfer rate regulation mechanism as claimed in claim 18 wherein a process of comparing the transfer credits and the data units in data packets waiting in a one of the first or second subsets is performed by a dedicated circuit for each subset.

20. A transfer rate regulation mechanism as claimed in claim 19 wherein the dedicated circuit includes a plurality of parallel adders and at least one comparator.

21. A routing and grade-of-service control mechanism for a switch module of a universal transfer mode (UTM) network, comprising:

a memory for storing a sorted list of routes from the switch module to each other switch module in the UTM network,

a routing request queue at each ingress port of the switch module,

at least one routing progress queue at each egress port of the switch module,

a routing request processor at each ingress port of the switch module,

a routing progress processor at each egress port of the switch module, and

a switch module routing processor adapted to communicate with each of the routing request processors and the routing progress processors.

22. A routing and grade-of-service control mechanism as claimed in claim 21 wherein the lists of routes are sorted according to cost.

23. A routing and grade-of-service control mechanism as claimed in claim 21 wherein where lists of sorted routes are downloaded from a central controller associated with the distributed switch.

24. A routing and grade-of-service control mechanism as claimed in claim 21 wherein routing requests in the routing progress queues are sorted according to a grade-of-service designation.

25. A routing and grade-of-service control mechanism as claimed in claim 21 wherein each egress port in a switch module has a subset of routing progress queues dedicated to requests that do not originate from the switch module.

26. A routing and grade-of-service control mechanism as claimed in claim 21 wherein each egress port has an associated state indicator which contains a value of zero or one.

27. A routing and grade-of-service control mechanism as claimed in claim 26 wherein the state indicator is set to 1 by the routing progress processor when a routing request is sent on a link associated with the egress port.

28. A method of routing a path or an independent connection between an originating switch module and a destination switch module in a highly-connected network, comprising the steps of:

a) enabling a network controller to store an identification and a cost of each available route from each switch module in the network to each other switch module in the network, to identify each two-hop route between each pair of switch modules in the network and to distribute to each switch module a list of the two-hop routes from the switch module to each other switch module in the network;

b) enabling each switch module to store and update information respecting an uncommitted capacity of each link from the switch module to each of its neighboring switch modules; and

c) enabling each switch module to find a route for a connection admission request received from a local source by sending at least one routing request to at least one other switch module to determine the uncommitted capacity of a link involved in the route from the other module to a destination switch module in the network; and

d) selecting a route for the connection admission request based on a parameter determined by a function using a least of the uncommitted capacities of two links involved in a route and a cost factor associated with the each of the two routes.

29. A method of routing as claimed in claim 28 wherein upon receipt of a connection admission request the originating switch module performs the steps of:

a) determining a number K of candidate routes;

b) selecting a candidate route set comprising the first K members of a sorted list of routes to the destination node;

c) reading K intermediate switch modules, including null intermediate switch modules, from the list of sorted routes;

d) determining a number L, less than or equal to K, of candidate routes having a sufficient uncommitted capacity in an adjacent link to accommodate the routing request;

e) rejecting the request if the number L is less than 1;

f) formulating and sending routing request messages to obtain information respecting an uncommitted capacity of links between the intermediate switch modules and a destination switch module, the request messages freezing those links to further routing request processing;

g) determining an uncommitted capacity of the L routes by examining replies to the routing request messages;

h) eliminating routes with insufficient uncommitted capacity to find an number M of eligible routes;

i) rejecting the connection admission request if M is zero;

j) sending a message to release any candidate link with insufficient capacity;

k) selecting a best route; and

l) sending a message to release each link frozen by the route selection process.

30. The method as claimed in claim 29 wherein the route selection criterion is a cost per unit of uncommitted capacity determined as a ratio of the route cost and the uncommitted capacity of the route.

31. The method as claimed in claim 30 wherein the inverse of the cost is expressed a digital number.

32. The method as claimed in claim 31 wherein the route selection criterion is the product of the inverse cost and the uncommitted capacity of the route.

33. The method as claimed in claim 29 wherein the value of K is dependent on the grade-of-service associated with the connection admission request.

34. The method as claimed in claim 33 wherein K=1 and the least cost route based on adjacent link occupancy is attempted.

35. The method as claimed in claim 29 wherein routing request queues are processed according to a predefined order related to a grade of service associated with a connection admission request for which a routing request was sent.

36. A method of fast route setup for a connection admission request between an originating switch module and a destination switch module in a packet network, comprising the steps of:

a) for each respective connection request, computing at a central control element of the originating switch module a cost-weighted uncommitted capacity of a set of designated routes selected from a table which stores a normalized cost of each route and an uncommitted capacity of each route to the destination switch module, and selecting a route from the designated routes according to a predefined rule;

b) reducing the uncommitted capacity of an adjacent link in the route according to a bit-rate specified in the connection admission request;

c) communicating with an intermediate switch module of the selected route, if the route includes an intermediate switch module, to reduce the uncommitted capacity of a link to the destination switch module; and

d) communicating with the destination switch module of the selected route to reduce the uncommitted capacity of a link to a sink for the connection request, whereby each the connection requests are routed in a sequential order.

37. A method of fast route setup as claimed in claim 36 wherein the source switch module selects another designated route not included in the designated set of routes based on cost-weighted uncommitted capacity, if the uncommitted capacity of the link between the intermediate switch module and the destination switch module is inadequate to accommodate the bit-rate for the call.

38. A method of fast route setup as claimed in claim 36 wherein the source switch module rejects the connection admission request when the uncommitted capacity of a link between the destination switch module and the sink is inadequate to accommodate the bit-rate for the call.

39. A method of fast route setup as claimed in claim 36 wherein each switch module stores a table of identities of neighboring switch modules to which the switch module periodically reports the uncommitted capacity of a selected subset of its adjacent links.

40. A method of fast route setup as claimed in claim 39 wherein the switch module reports the uncommitted capacity of the selected subset of its adjacent links to the list of neighboring switch modules at regular predetermined intervals.

41. A method of fast route setup as claimed in claim 39 wherein the switch module reports the uncommitted capacity of the selected subset of its adjacent links to the list of neighboring switch modules each time the uncommitted capacity of a one of its adjacent links changes by a predetermined amount.

42. A method of transfer rate allocation for traffic streams in a shared path through a switched data network, the shared path being used to transfer a plurality of traffic streams, and identity of data packets of each traffic stream being stored in a traffic stream buffer, each traffic stream having an assigned quality-of-service index, but none of the traffic streams having a predefined transfer rate allocation, comprising, at a predefined interval, the steps of:

a) monitoring an occupancy of a traffic stream buffer which represents a count of data units in each traffic stream,

b) storing a current occupancy of each traffic stream buffer in a first memory;

c) storing a previous occupancy of each traffic stream buffer in a second memory;

d) comparing the current occupancy with a predefined lower bound and a predefined upper bound to determine a current zone for each traffic stream selected from a set of predefined zones;

e) comparing the current occupancy and the previous occupancy to determine whether a change in buffer occupancy for each traffic is positive, neutral or negative; and

f) requesting a change in the transfer rate for a traffic stream if the zone and the change in buffer occupancy in combination meet a predetermined criteria.

43. A method of transfer rate allocation as claimed in claim 42 wherein three zones are defined, a first zone in which a traffic stream is determined to be if the occupancy is less than the lower bound, a second zone in which the traffic stream is determined to be if the occupancy is between the lower bound and the upper bound, and a third zone in which the traffic stream is determined to be if the occupancy is greater than the upper bound.

44. A method of transfer rate allocation as claimed in claim 43 wherein a transfer rate increment in a size of the path is requested if the traffic stream is determined to be in the third zone and the buffer occupancy change for the traffic stream is positive.

45. A method of transfer rate allocation as claimed in claim 43 wherein a transfer rate decrement in a size of the path is requested if the traffic stream is determined to be in the first zone and the buffer occupancy change for the traffic stream is negative.

46. A method of transfer rate allocation as claimed in claim 43 wherein no action is taken to alter a size of the path if the traffic stream is determined to be in the second zone.

47. A method of transfer rate allocation as claimed in claim 43 wherein a requested change in transfer rate is communicated to a control element of a switch module in the data network, and the control element requests other switch modules in the path to effect a path size change in accordance with the requested change in transfer rate.

48. A method of transfer rate allocation as claimed in claim 43 wherein the lower bound and the upper bound are defined for each quality-of-service index to discriminate a quality-of-service index of a traffic stream from a different quality-of-service index of another traffic stream.

49. A method of transfer rate allocation as claimed in claim 43 wherein an upper bound selected for delay sensitive traffic streams is substantially smaller than an upper bound selected for delay tolerant traffic streams.

50. A method of transfer rate allocation as claimed in claim 43 wherein the transfer rate increment and the transfer rate decrement are traffic-stream dependent values correlated with a quality-of-service index, or determined by a network administrator.

51. A method of transfer rate allocation as claimed in claim 44 wherein the transfer rate increment is added to a current capacity of the path.

52. A method of transfer rate allocation as claimed in claim 44 wherein the transfer rate increment is a multiplier and the increment in a current capacity of the path is computed by performing a binary right shift on a binary number representative of a current capacity of the path, whereby the binary right shift is represented by the exponent j of 2⁻

j, where j is an integer, 0≦

j<

16.

53. A method of transfer rate allocation as claimed in claim 52 wherein j is a traffic-stream dependent value that is set by a network administrator.

54. A method of transfer rate allocation as claimed in claim 45 wherein the magnitude of a transfer rate decrement is subtracted from a current capacity of the path.

55. A method of transfer rate allocation as claimed in claim 45 wherein the transfer rate decrement is a multiplier and the decrement in a current capacity of the path is computed by performing a binary right shift on a binary number representative of a current capacity of the path, whereby the binary right shift is represented by the exponent j of 2⁻

j, where j is an integer, 0≦

j<

16.

56. A method of transfer rate allocation as claimed in claim 55 wherein j is a traffic-stream dependent value that is set by a network administrator.

57. A method of transfer rate allocation as claimed in claim 43 wherein the shared path is served by a direct link between two switching nodes.

58. A method of transfer rate allocation as claimed in claim 43 wherein the shared path traverses one or more intermediate switch modules, and each of the intermediate switch modules have knowledge only of a current transfer allocation for the path.

59. A method of transfer rate allocation as claimed in claim 58 wherein data packets in the traffic streams are transferred in accordance with a strict priority discipline dictated by their quality of service indices.

60. A method of transfer rate allocation as claimed in claim 43 wherein the traffic streams are transferred according to a weighted-priority discipline.

61. A method of transfer rate allocation as claimed in claim 43 wherein the traffic streams share the path with other traffic streams having predefined transfer rate allocations.

62. A method of transfer rate allocation as claimed in claim 43 wherein data packets are transferred from the traffic streams in a cyclic order.

63. An apparatus for regulating a transfer rate of traffic streams in a shared path serving a plurality of traffic streams, each traffic stream having an assigned quality-of-service index, but none of the traffic streams having a transfer rate allocation, the apparatus comprising:

a monitor for periodically monitoring an occupancy of each traffic stream;

a first memory for storing the occupancy of each traffic stream buffer when the occupancy is monitored;

a second memory for storing a previous occupancy of each traffic stream buffer from a last time that the traffic stream was monitored;

registers for storing a lower occupancy bound, an upper occupancy bound, a transfer rate increment, and a transfer rate decrement; and

a circuit for determining a transfer rate change for each traffic stream using a difference between the occupancy stored in the first and second memories and a relationship of the current occupancy to the upper and lower bounds.

64. The apparatus as claimed in claim 63 wherein a lower bound and an upper bound are associated with each quality-of-service index and a memory stores a lower bound and an upper bound for each quality-of-service index.

65. The apparatus as claimed in claim 63 wherein a transfer rate increment coefficient and a transfer rate decrement coefficient are associated with each quality-of-service index and a memory stores a transfer rate increment coefficient and a transfer rate decrement coefficient for each quality-of-service index.

66. The apparatus as claimed in claim 65 wherein the transfer rate increment coefficients and transfer rate decrement coefficients are of the form 2⁻

j where j is an integer with a binary representation of four bits and the value of j for each quality-of-service index is stored and used directly to determine the transfer rate increment and transfer rate decrement for a traffic stream.

67. The apparatus as claimed in claim 63 wherein the transfer rate increments and transfer rate decrements for traffic streams originating from a source module and destined to a common sink module are aggregated, and the aggregate result is presented to the connection admission controller, unless the aggregate result is zero or negative.

68. The apparatus as claimed in claim 67 wherein if the aggregate rate change is positive, the admission controller may modify the requested aggregate rate change but must reply with a permissible aggregate rate change, which may be equal to, smaller than, or greater than the requested aggregate rate change.

69. The apparatus as claimed in claim 68 wherein the permissible aggregate rate change is divided proportionately among the unregulated traffic streams which require a transfer rate increment, the proportional division of the permissible aggregate rate being dependent on the requested transfer rate increments of individual traffic streams.

70. The apparatus as claimed in claim 69 wherein the transfer rate increments and transfer rate decrements for all traffic streams are presented to a first-stage transfer rate regulator.

71. The apparatus as claimed in claim 63 wherein the unregulated traffic streams are stored in logical buffers associated with logical buffers that store traffic streams having predefined transfer rate allocations, and all of the buffers are transfer rate regulated by a common transfer rate regulator after the apparatus has determined and assigned a provisional transfer rate(s) to the unregulated traffic streams.