Hierarchical flow-characterizing multiplexor

• US 7,621,162 B2
• Filed: 12/30/2003
• Issued: 11/24/2009
• Est. Priority Date: 12/30/2003
• Status: Expired due to Fees

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Bartky, Alan Keith
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): NGUYEN, PHUONGCHAU BA
• Application Number:
  US10/750,120
• Publication Number:
  US 20050141427A1
• Time in Patent Office: 2,156 Days
• Field of Search: 370235-236, 370/256, 370/388, 370/395.42, 370412-418, 370/428
• US Class Current: 70/388
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching
• CPC Class Codes: Y10T 70/7763 Key ejecting

Abstract

A method of multiplexing a plurality of data flows into a single output using hierarchical gating operations instead of queues is disclosed. In the preferred embodiment, the hierarchical multiplexing method comprises sequentially processing a packet at each of a plurality of hierarchical levels by characterizing the flow at each hierarchical level and either passing or discarding the packet. The decision whether to pass or discard a packet is generally made for each packet at one or more hierarchical levels based on traffic parameters and the state of the system such as congestion. In the preferred embodiment, a Three Color Marker algorithm is used to characterize the flow and mark packets subjecting to the discard decision. The invention may be used by a router or multi-layer switch to process multiple data flows in a hierarchical fashion without hierarchical queues, thereby reducing processing and memory requirements.

Claims

1. A hierarchical multiplexing method comprising the steps of:

receiving a protocol data unit (PDU) associated with one of a plurality of flows;

sequentially processing the PDU at each of a plurality of hierarchical levels, said processing at each of the plurality of hierarchical levels consisting of;

characterizing the flow at a current hierarchical level;

gating the PDU wherein the PDU is either passed or dropped based upon the character of the flow at the current level, wherein the gating includes applying a color to the PDUs of the flows based upon traffic parameters specific to those flows at a second hierarchical level characterizing the flow at the current hierarchical level;

additionally gating the PDU based upon the character of the flow at the second hierarchical level, wherein the additional gating includes employing a plurality of measure/mark modules to measure how much data is flowing per given time period; and

outputting the gated PDU and the additionally gated PDU in a single stream via a hierarchical multiplexor if the PDU is passed at each of the plurality of hierarchical levels.

2. The hierarchical multiplexing method of claim 1, wherein the plurality of hierarchical levels comprises a last hierarchical level, wherein the step of sequentially processing the PDU at the last hierarchical level comprises the step of queuing the PDU.

3. The hierarchical multiplexing method of claim 2, wherein the step of queuing the PDU comprises the step of buffering the PDU at an egress queue associated with an egress port of a network switching device.

4. The hierarchical multiplexing method of claim 2, wherein the step of queuing the PDU comprises the step of buffering the PDU preceding transmission to a switch fabric.

5. The hierarchical multiplexing method of claim 1, wherein the step of sequentially processing the PDU at one or more hierarchical levels comprises performing one or more forwarding operations.

6. The hierarchical multiplexing method of claim 5, wherein the one or more forwarding operations comprise appending an address to the PDU.

7. The hierarchical multiplexing method of claim 6, wherein the appending of an address to the PDU comprises the steps of:

appending a virtual circuit identifier at a first hierarchical level; and

appending a virtual path identifier at a second hierarchical level.

8. The hierarchical multiplexing method of claim 5, wherein the one or more forwarding operations comprises appending one or more virtual local area network (VLAN) tags at one or more hierarchical levels.

9. The hierarchical multiplexing method of claim 1, wherein:

characterizing comprises the step of measuring a flow rate for the flow associated with the PDU based on a current hierarchical level; and

gating comprises the step of discarding the PDU if it exceeds a maximum bandwidth parameter.

10. The hierarchical multiplexing method of claim 1, wherein the gating comprises the steps of:

associating with the PDU a color marker using a three color marker algorithm; and

applying discard control logic to selectively discard the PDU based upon the color marker.

11. A hierarchical multiplexing method comprising the steps of:

receiving a protocol data unit (PDU) associated with one of a plurality of flows;

sequentially processing the PDU at each of three or more hierarchical levels, said processing at each of the hierarchical levels comprising the step of gating the PDU characterizing the flow at a current hierarchical level;

additionally gating the PDU based upon the character of the flow at the second hierarchical level, wherein the additional gating includes employing a plurality of measure/mark modules to measure how much data is flowing per given time period;

mapping the a plurality of flows between each of the hierarchical levels;

applying a color to the PDUs of the flows based upon traffic parameters specific to those flows at a second hierarchical level; and

outputting the gated PDU and the additionally gated PDU in a single stream via the hierarchical multiplexor if the PDU is passed at each of the plurality of hierarchical levels.

12. A packet processing method comprising the steps of:

receiving a protocol data unit (PDU) associated with one of a plurality of flows;

sequentially processing the PDU at each of a plurality of hierarchical levels, said processing at each of the plurality of hierarchical levels consisting of;

characterizing the flow at a current hierarchical level;

gating the PDU based upon the character of the flow at the current hierarchical level, wherein the gating includes applying a color to the PDUs of the flows based upon traffic parameters specific to those flows at a second hierarchical level;

additionally gating the PDU based upon the character of the flow at the second hierarchical level, wherein the additional gating includes employing a plurality of measure/mark modules to measure how much data is flowing per given time period; and

outputting the gated PDU and the additionally gated PDU in a single stream via a hierarchical multiplexor if the PDU is passed at each of the plurality of hierarchical levels.

13. A hierarchical multiplexor comprising:

an input channel for receiving a protocol data unit (PDU) associated with one of a plurality of flows;

a plurality of hierarchical levels, each hierarchical level consisting of;

means for characterizing the flow at the hierarchical level;

means for gating the PDU based upon the character of the flow at the hierarchical level, wherein the gating includes applying a color to the PDUs of the flows based upon traffic parameters specific to those flows at a second hierarchical level;

means for additionally gating the PDU based upon the character of the flow at the second hierarchical level, wherein the additional gating includes employing a plurality of measure/mark modules to measure how much data is flowing per given time period; and

means for mapping the PDU to a flow at the next hierarchical level; and

an output channel for transmitting the gated PDU and the additionally gated PDU in a single stream via the hierarchical multiplexor if the PDU is passed at each of the plurality of hierarchical levels.

14. The hierarchical multiplexor of claim 13, wherein one or more of the plurality of hierarchical levels further consists of means for performing forwarding operations associated with the PDU.

15. The hierarchical multiplexor of claim 14, wherein the hierarchical multiplexor further comprises a last hierarchical level comprising:

means for characterizing the flow at the last hierarchical level; and

means for gating the PDU based upon the character of the flow at the last hierarchical level.

16. The hierarchical multiplexor of claim 15, wherein the last hierarchical level further comprises a queue for buffering the PDU at the output channel.

17. The hierarchical multiplexor of claim 14, wherein the means for characterizing the flow comprises a meter for measuring the flow rate of the flow associated with the PDU.

18. The hierarchical multiplexor of claim 17, wherein the means for gating the PDU comprises means for discarding the PDU depending on the flow rate.

19. The hierarchical multiplexor of claim 17, wherein the means for characterizing the flow further comprises a marker module for marking the PDU in accordance with a Three-Color Marker (TCM) algorithm.

20. The hierarchical multiplexor of claim 19, wherein the means for gating the PDU comprises means for discarding the PDU in accordance with the TCM algorithm.

21. A hierarchical multiplexor for processing a protocol data unit (PDU) associated with one of a plurality of flows, the hierarchical multiplexor comprising:

a plurality of hierarchical levels for performing gating operations, each hierarchical level consisting of;

a meter for measuring the flow rate at the hierarchical level;

a gate for discarding the PDU based upon the flow rate at the hierarchical level wherein the gate applies a color to the PDUs of the flows based upon traffic parameters specific to those flows at a second hierarchical level;

an additional gate for discarding the PDU based upon the flow rate at the hierarchical level, wherein the additional gate includes a plurality of measure/mark modules to measure how much data is flowing per given time period; and

a last hierarchical level comprising a queue for buffering the gated PDU and the additionally gated PDU in a single stream via a hierarchical multiplexor prior to transmission.