Routing and rate control in a universal transfer mode network

• US 6,580,721 B1
• Filed: 08/11/1998
• Issued: 06/17/2003
• Est. Priority Date: 08/11/1998
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Beshai, Maged E.
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): NGUYEN, TOAN D
• Application Number:
  US09/132,464
• Time in Patent Office: 1,771 Days
• Field of Search: 370/230, 370/391, 370/395.21, 370/395.41, 370/412, 370/413, 370/428, 370/429, 370/468
• 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 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 occupandy 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 stream is positive, neutral or negative; and

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

2. A method of transfer rate allocation as claimed in claim 1 wherein three zones are defined, a first zone in which a traffic stream is determined to be if the current occupancy is less than the lower bound, a second zone in which the traffic stream is determined to be if the current 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 current occupancy is greater than the upper bound.

3. A method of transfer rate allocation as claimed in claim 2 wherein a transfer rate allocation 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.

4. A method of transfer rate allocation as claimed in claim 2 wherein a transfer rate allocation 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.

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

6. A method of transfer rate allocation as claimed in claim 2 wherein a requested change in transfer rate allocation 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 allocation.

7. A method of transfer rate allocation as claimed in claim 2 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.

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

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

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

11. A method of transfer rate allocation as claimed in claim 3 wherein the transfer rate allocation 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.

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

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

14. A method of transfer rate allocation as claimed in claim 4 wherein the transfer rate allocation 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⁻

1, where j is an integer, 0≦

j<

16.

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

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

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

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

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

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

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

22. An apparatus for regulating a transfer rate allocation 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 buffer;

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 allocation increment, and a transfer rate allocation decrement; and

a circuit for determining a transfer rate allocation 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.

23. The apparatus as claimed in claim 22 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.

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

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

1 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 allocation increment and transfer rate allocation decrement for a traffic stream.

26. The apparatus as claimed in claim 22 wherein the transfer rate allocation increments and transfer rate allocation 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.

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

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

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

30. The apparatus as claimed in claim 22 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 allocation(s) to the unregulated traffic streams.