Ensuring fair access to upstream trunk bandwidth in ATM subtended configurations

• US 6,769,043 B1
• Filed: 04/11/2000
• Issued: 07/27/2004
• Est. Priority Date: 04/11/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Fedorkow, Guy C., Joyce, John A., Savla, Vijay J., Hoult, Kent H., Milano, Michael B., Swaminathan, Nagarajan
• Primary Examiner(s): Auve, Glenn A.
• Assistant Examiner(s): Lee, Christopher E.
• Application Number:
  US09/546,829
• Time in Patent Office: 1,568 Days
• Field of Search: 370/412, 370/314, 370/60, 370/395, 370/338, 370/375, 370/398, 370/395.4, 370/415, 370/429, 370/218, 370/235, 370/238, 370/419, 379/94, 395/800, 710/44, 710/310, 710/112, 710/29, 710/1, 709/223, 725/116
• US Class Current: 710/112
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5613 Bus (including DQDB)
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/50 Queue scheduling

Abstract

To ensure fair access to upstream trunk bandwidth among a plurality of interface units, a plurality of queues is provided in a first unit. One of the queues is associated with the first interface unit. Each of the remaining queues is associated with one of a plurality of second interface units. Local data is received by the first interface unit and forwarded to the associated queue. Data received from a second, subtended interface unit is forwarded to a queue which associated with the second interface unit. Data is then issued from the queues according to a fairness algorithm. A unique identifier is assigned to each interface unit. Associating a queue with an interface unit is done by associating the queue with the respective interface unit'"'"'s identifier. In each interface unit, local data is tagged with the instant interface unit'"'"'s identifier, and received data is forwarded to a queue according to the data'"'"'s tag. For ATM traffic, data can be tagged by inserting the receiving interface unit'"'"'s identifier into the generic flow control (GFC) field. Alternatively, a table of associations between virtual channel identifiers (VCIs) and interface unit identifiers may be maintained, and the received data is forwarded to a queue according to the interface unit identifier associated with the data'"'"'s VCI.

Claims

1. A method for ensuring fair access to upstream trunk bandwidth among a plurality of interface units, the plurality of interface units including a first interface unit and at least two interface units subtended by the first interface unit, comprising, in the first interface unit:

providing a plurality of queues, each subtended interface unit being associated with an individual queue;

receiving local data at a first input port, and forwarding the received local data to a queue associated with the first interface unit;

receiving at a second input port data originating from at least two subtended interface units and forwarding the received data to the corresponding individual queue associated with the respective subtended interface unit; and

issuing data from the queues according to a fairness algorithm.

2. The method of claim 1, further comprising:

assigning a unique queue identifier to each interface unit, a queue in the first interface unit being associated with a subtended interface unit by associating the queue with the respective subtended interface unit'"'"'s queue identifier;

in each interface unit, tagging local data with a tag comprising the respective interface unit'"'"'s queue identifier; and

in the first interface unit, forwarding received data to a queue responsive to the received data'"'"'s tag.

3. The method of claim 2, wherein data is formatted as asynchronous transfer mode (ATM) cells.

4. The method of claim 3, wherein an ATM cell comprises a generic flow control (GFC) field, wherein tagging local data in each interface unit comprises inserting the respective interface unit'"'"'s queue identifier into the GFC field.

5. The method of claim 3, wherein an ATM cell comprises a virtual channel identifier (VCI), the method further comprising:

maintaining a table of associations between VCIs and interface unit queue identifiers, wherein forwarding received data to a queue is responsive to an interface unit queue identifier associated with the data'"'"'s VCI.

6. The method of claim 1, wherein the fairness algorithm is a round robin algorithm.

7. The method of claim 1, further comprising:

interconnecting the plurality of interface units such that

a top-level interface unit connects to a network trunk, and

each non-top-level interface unit connects to an interface unit at a next higher level.

8. The method of claim 7, wherein the interface units are arranged in a tree configuration.

9. The method of claim 7, wherein the interface units are arranged in a daisy-chain configuration.

10. The method of claim 1, wherein each queue comprises plural sub-queues, each sub-queue associated with a different priority, and wherein issuing data from a queue comprises:

issuing data from the queue'"'"'s highest priority sub-queue that contains data.

11. A first interface unit, comprising:

a first input port for connecting to at least two subtended interface units, each subtended unit having the capability to connect with additional subtended interface units, the first interface unit receiving data originating with the subtended interface units;

a second input port for receiving local data;

an output port for connecting to one of;

a higher-level interface unit and a network trunk;

a plurality of queues, each subtended interface unit being associated with an individual queue, received data originating from any of the subtended interface units being forwarded to the queue associated with said subtended interface unit, and at least one of said queues for the received local data; and

an issuer that issues data to the output port from the queues according to a fairness algorithm.

12. The interface unit of claim 11, wherein a unique queue identifier is assigned to each interface unit, such that a queue is associated with an interface unit by associating the queue with the respective interface unit'"'"'s queue identifier, the interface unit further comprising:

a data tagger which tags local data with the interface unit'"'"'s queue identifier, non-local data received from a second interface unit having already been tagged; and

a sorter which forwards received data to a queue according to the data'"'"'s tag.

13. The interface unit of claim 12, wherein data is formatted as asynchronous transfer mode (ATM) cells.

14. The interface unit of claim 13, wherein an ATM cell comprises a generic flow control (GFC) field, wherein the tagger tags local data by inserting the respective interface unit'"'"'s queue identifier into the GFC field.

15. The interface unit of claim 14, an ATM cell comprising a virtual channel identifier (VCI), the interface unit further comprising:

a table of associations between VCIs and interface unit queue identifiers, the sorter forwarding received data to a queue responsive to an interface unit queue identifier associated with the data'"'"'s VCI.

16. The interface unit of claim 11, wherein the fairness algorithm is a round robin algorithm.

17. The interface unit of claim 11, wherein the interface unit is interconnected with a plurality of interface units such that

a top-level interface unit connects to a network trunk, and

each non-top-level interface unit connects to an interface unit at a next higher level.

18. The interface unit of claim 17, wherein the plurality of interface units are arranged in a tree configuration.

19. The interface unit of claim 17, wherein the plurality of interface units are arranged in a daisy-chain configuration.

20. The interface unit of claim 11, wherein each queue comprises plural sub-queues, each sub-queue associated with a different priority, and wherein issuing data from a queue comprises:

issuing data from the queue'"'"'s highest priority sub-queue that contains data.

21. A first interface unit, comprising:

means for receiving local data;

means for tagging the received local data with an interface unit queue identifier associated with the first interface unit;

means for receiving data from at least one interface unit subtended by the first interface unit, said data having been tagged with an interface unit queue identifier uniquely associated with a subtended interface unit in which said data originated;

means for queuing received data according to the interface unit queue identifier with which said data is tagged; and

means for issuing data from the queuing means according to a fairness algorithm.

22. The interface unit of claim 21, wherein data is formatted as asynchronous transfer mode (ATM) cells.

23. The interface unit of claim. 22, wherein an ATM cell comprises a generic flow control (GFC) field, wherein tagging local data in each interface unit comprises inserting the respective interface unit'"'"'s queue identifier into the GFC field.

24. The interface unit of claim 22, wherein an ATM cell comprises a virtual channel identifier (VCI), further comprising:

means for maintaining associations between VCIs and interface unit queue identifiers, wherein forwarding received data to a queue is responsive to an interface unit queue identifier associated with the data'"'"'s VCI.

25. The interface unit of claim 21, wherein the fairness algorithm is a round robin algorithm.

26. The interface unit of claim 21, wherein the interface units are interconnected such that

a top-level interface unit connects to a network trunk, and

each non-top-level interface unit connects to an interface unit at a next higher level.

27. The interface unit of claim 26, wherein the interface units are arranged in a tree configuration.

28. The interface unit of claim 26, wherein the interface units are arranged in a daisy-chain configuration.

29. The interface unit of claim 21, wherein the queuing means comprises plural sub-queue means, each sub-queue means associated with a different priority, and wherein said means for issuing data comprises:

means for issuing data from said queuing means highest priority sub-queue means that contains data.

30. A computer program product for ensuring fair access to upstream trunk bandwidth among a plurality of interface units, the computer program product comprising a computer usable medium having computer readable code thereon, including program code which, in a first interface unit:

tags received local data with an interface unit queue identifier uniquely associated with the first interface unit;

queues received local and non-local data according to tagged interface unit queue identifiers, received non-local data having been tagged, by an interface unit subtended by the first interface unit and in which said data originated, with a queue identifier corresponding uniquely to said subtended interface unit; and

issues data from queues according to a fairness algorithm.

31. The computer program product of claim 30, wherein data is formatted as asynchronous transfer mode (ATM) cells.

32. The computer program product of claim 31, wherein an ATM cell comprises a generic flow control (GFC) field, wherein tagging local data in each interface unit comprises inserting the respective interface unit'"'"'s queue identifier into the GFC field.

33. The computer program product of claim 31 wherein an ATM cell comprises a virtual channel identifier (VCI), further comprising program code which:

maintains a table of associations between VCIs and interface unit queue identifiers, wherein received data is forwarded to a queue responsive to an interface unit queue identifier associated with the data'"'"'s VCI.

34. The computer program product of claim 30, wherein the fairness algorithm is a round robin algorithm.

35. The computer program product of claim 30, wherein the interface units are interconnected such that

a top-level interface unit connects to a network trunk, and

each non-top-level interface unit connects to an interface unit at a next higher level.

36. The computer program product of claim 35, wherein the interface units are arranged in a tree configuration.

37. The computer program product of claim 35, wherein the interface units are arranged in a daisy-chain configuration.

38. The computer program product of claim 30, wherein each queue comprises plural sub-queues, each sub-queue associated with a different priority, and wherein said program code which issues data from a queue further comprises program code which:

issues data from said queue'"'"'s highest priority sub-queue that contains data.

39. A computer system comprising:

a processor located within a first interface unit;

a memory system connected to the processor; and

a computer program, in the memory, which;

tags received local data with an interface unit queue identifier uniquely associated with the first interface unit;

queues received local and non-local data according to tagged interface unit queue identifiers, received non-local data having been tagged, by an interface unit subtended by the first interface unit and in which said data originated, with an interface unit queue identifier corresponding uniquely to said subtended interface unit; and

issues data from queues according to a fairness algorithm.

40. The computer system of claim 39, wherein data is formatted as asynchronous transfer mode (ATM) cells.

41. The computer system of claim 40, wherein an ATM cell comprises a generic flow control (GFC) field, wherein tagging local data in each interface unit comprises inserting the respective interface unit'"'"'s queue identifier into the GFC field.

42. The computer system of claim 40, wherein an ATM cell comprises a virtual channel identifier (VCI), wherein the computer program further:

maintains a table of associations between VCIs and interface unit queue identifiers, wherein received data is forwarded to a queue responsive to an interface unit queues identifier associated with the data'"'"'s VCI.

43. The computer system of claim 39, wherein the fairness algorithm is a round robin algorithm.

44. The computer system of claim 39, wherein the interface units are interconnected such that

a top-level interface unit connects to a network trunk, and

each non-top-level interface unit connects to an interface unit at a next higher level.

45. The computer system of claim 44, wherein the interface units are arranged in a tree configuration.

46. The computer system of claim 44, wherein the interface units are arranged in a daisy-chain configuration.

47. The computer system of claim 39, wherein each queue comprises plural sub-queues, each sub-queue associated with a different priority, and wherein said computer program issues data from a queue by issuing data from said queue'"'"'s highest priority sub-queue that contains data.

48. A computer data signal embodied in a carrier wave for ensuring fair access to upstream trunk bandwidth among a plurality of interface units, the plurality of interface units including, a first interface unit and at least one interface unit subtended by the first interface unit, comprising:

program code for tagging, in the first interface unit, received local data with an interface unit queue identifier uniquely associated with the first interface unit;

program code for queuing, in the first interface unit, received local and non-local data according to tagged interface unit queue identifiers, received non-local data having been previously tagged, by an interface unit subtended by the first interface unit and in which said data originated, with an interface unit queue identifier uniquely associated with said subtended interface unit; and

program code for issuing, in the first interface unit, data from the queues according to a fairness algorithm.

49. The computer data signal of claim 48, wherein data is formatted as asynchronous transfer mode (ATM) cells.

50. The computer data signal of claim 49, wherein an ATM cell comprises a generic flow control (GFC) field, wherein tagging local data in each interface unit comprises inserting the respective interface unit'"'"'s queue identifier into the GFC field.

51. The computer data signal of claim 49, wherein an ATM cell comprises a virtual channel identifier (VCI), further comprising:

program code for maintaining associations between VCIs and interface unit queue identifiers, wherein received data is forwarded to a queue responsive to an interface unit queue identifier associated with the data'"'"'s VCI.

52. The computer data signal of claim 48, wherein the fairness algorithm is a round robin algorithm.

53. The computer data signal of claim 48, wherein the interface units are interconnected such that

a top-level interface unit connects to a network trunk, and

each non-top-level interface unit connects to an interface unit at a next higher level.

54. The computer data signal of claim 53, wherein the interface units are arranged in a tree configuration.

55. The computer data signal of claim 53, wherein the interface units are arranged in a daisy-chain configuration.

56. The computer data signal of claim 48, wherein each queue comprises plural sub-queues, each sub-queue associated with a different priority, and wherein said program code for issuing data from a queue issues data from said queue'"'"'s highest priority sub-queue that contains data.

57. A method for ensuring fair access to upstream trunk bandwidth among a plurality of interface units arranged hierarchically, a top-level interface unit connecting to a trunk port, comprising, in each interface unit:

associating each interface unit subtended by said unit with an individual queue;

receiving local data at a first input port, and forwarding the received local data to a queue associated with said interface unit;

receiving at a second input port data originating from at least two interface units

subtended by said unit;

forwarding the received data originating from interface units subtended by said unit to the individual queues according to the originating subtended interface units;

in each subtended interface unit, issuing data from the queues to said interface unit'"'"'s subtending interface unit according to a fairness algorithm; and

in the top-level interface unit, issuing data from the queues to the trunk port according to a fairness algorithm.