Inverse multiplexing of managed traffic flows over a multi-star network

• US 7,289,525 B2
• Filed: 02/21/2002
• Issued: 10/30/2007
• Est. Priority Date: 02/21/2002
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Lebizay, Gerald, Gish, David W, Mitchel, Henry M
• Primary Examiner(s): Orgad; Edan
• Assistant Examiner(s): Haliyur; Venkatesh
• Application Number:
  US10/080,329
• Publication Number:
  US 20030156535A1
• Time in Patent Office: 2,077 Days
• Field of Search: 370/230, 370/235, 370/394, 370/395.3, 370/412, 370/425
• US Class Current: 370/425
• CPC Class Codes: H04L 12/44 Star or tree networks
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/358 Infiniband Switches

Abstract

A method for inverse multiplexing of managed traffic flows over a multi-star switch network includes a source node classifier. The source node classifier, using a traffic-engineering algorithm, classifies incoming traffic based on flow parameters, embeds the flow parameters in a routing table in a node for a flow, places packets from classified flows into Switch-Specific Managed-Traffic Queues (SSMT) and a source node unmanaged traffic queue. A source node switch input scheduler process for a switch selects all managed packets from the SSMT destined for the switch, then selects a single unmanaged packet from the source node unmanaged traffic queue. The source node transmits the packets as classified flows through a switch fabric to the destination node. At the destination node packets transmitted through the switch fabric are sorted by a Switch Output Process and sent to intended output queues.

Claims

1. A method of inverse multiplexing managed traffic flows over a multi-star switch network, comprising:

classifying incoming traffic based on flow parameters to form classified flows, and embedding the flow parameters in a routing table in a source node for a flow;

placing packets from the classified flows into a plurality of Switch-Specific Managed-Traffic Queue Sets (SSMTs) and an unmanaged traffic queue set;

selecting such that a Switch Input Scheduler Process for a switch selects all managed packets available from one of the SSMTs, then selects a single unmanaged packet from the unmanaged traffic queue set to form selected packets; and

transmitting selected packets from the classified flows from the source node through a multi-star switch fabric to a destination node, wherein the multi-star switch fabric includes a switch that is connected to every node therein, but is not connected to any other switch.

2. The method according to claim 1, wherein the flow parameters define the source node, a path, a backup path, a selected switch, a backup switch, the destination node, and whether the flow is managed or unmanaged.

3. The method according to claim 2, wherein a source node classifier, using a traffic engineering algorithm, classifies the incoming traffic based on the flow parameters, embeds the flow parameters in the routing table in the source node for the flow, and places packets from the classified flows into the SSMTs and the unmanaged traffic queue set.

4. The method according to claim 3, wherein the traffic engineering algorithm classifies based on bandwidth that the flow requires.

7. The method according to claim 2, wherein the selecting includes moving, by the Switch Input Scheduler Process, selected packets from the classified flows from the SSMT and the unmanaged traffic queue set, to the selected switch.

8. The method according to claim 1, wherein the selecting, by the Switch Input Scheduler Process, includes a randomization function.

9. The method according to claim 1, wherein the source node has the Switch Input Scheduler Process for the switch.

28. The method according to claim 1, further comprising receiving of the classified flows by the destination node, wherein a switch output process sorts the classified flows received from a fabric output, and sends the classified flows to an intended output queue.

5. A method of inverse multiplexing managed traffic flows over a multi-star switch network, comprising:

classifying, using a traffic engineering algorithm, incoming traffic based on flow parameters to form classified flows, and embedding the flow parameters in a routing table in a source node for a flow, wherein the traffic engineering algorithm classifies based on bandwidth that the flow requires;

placing packets from the classified flows into a plurality of Switch-Specific Managed-Traffic Queue Sets (SSMTs) and an unmanaged traffic queue set;

selecting such that a Switch Input Scheduler Process for a switch selects all managed packets available from one of the SSMTs, then selects a single unmanaged packet from the unmanaged traffic queue set to form selected packets;

transmitting selected packets from the classified flows from the source node through a multi-star switch fabric to a destination node,

wherein the multi-star switch fabric includes a switch that is connected to every node therein, but is not connected to any other switch and wherein a Bandwidth Negotiated Managed Traffic (BNMT) flow has a known bandwidth requirement.

29. The method according to claim 5, further comprising receiving of the classified flows by the destination node, wherein a switch output process sorts the classified flows received from a fabric output, and sends the classified flows to an intended output queue.

6. A method of inverse multiplexing managed traffic flows over a multi-star switch network, comprising:

classifying, using a traffic engineering algorithm, incoming traffic based on flow parameters to form classified flows, and embedding the flow parameters in a routing table in a source node for a flow, wherein the traffic engineering algorithm classifies based on bandwidth that the flow requires;

placing packets from the classified flows into a plurality of Switch-Specific Managed-Traffic Queue Sets (SSMTs) and an unmanaged traffic queue set;

selecting such that a Switch Input Scheduler Process for a switch selects all managed packets available from one of the SSMTs, then selects a single unmanaged packet from the unmanaged traffic queue set to form selected packets;

transmitting selected packets from the classified flows from the source node through a multi-star switch fabric to a destination node,

wherein the multi-star switch fabric includes a switch that is connected to every node therein, but is not connected to any other switch and wherein an Un-negotiated Managed Traffic (UMT) flow having a unknown bandwidth requirement, is considered part of an aggregate for which the bandwidth is known or is placed initially in a queue for a selected switch, the UMT bandwidth is measured, and the measured bandwidth is used to correct the initial placement.

30. The method according to claim 6, further comprising receiving of the classified flows by the destination node, wherein a switch output process sorts the classified flows received from a fabric output, and sends the classified flows to an intended output queue.

10. A program code storage device, comprising:

a computer-readable storage medium; and

computer-readable program code, stored on the computer-readable storage medium, which when executed causes a computer to classify incoming traffic based on flow parameters to form classified flows, embed flow parameters in a routing table in a source node for a flow, place packets from the classified flows into a plurality of Switch-Specific Managed-Traffic Queue sets (SSMTs) and an unmanaged traffic queue set,

select such that a Switch Input Scheduler Process for a switch selects all managed packets available from one of the SSMTs first, then selects a single unmanaged packet from the unmanaged traffic queue set to form selected packets, and

transmit the selected packets from the classified flows from the source node through a multi-star switch fabric to a destination node wherein the multi-star switch fabric includes a switch that is connected to every node therein, but is not connected to any other switch.

11. The program code storage device according to claim 10, wherein the flow parameters define the source node, a path, a backup path, a selected switch, a backup switch, the destination node, and whether the flow is managed or unmanaged.

12. The program code storage device according to claim 10, wherein a source node classifier, using a traffic engineering algorithm, classifies the incoming traffic based on the flow parameters, embeds the flow parameters in the routing table in the source node for the flow, and places packets from the classified flows into the SSMTs and the unmanaged traffic queue set.

13. The program code storage device according to claim 12, wherein the traffic-engineering algorithm classifies based on bandwidth that the flow requires.

16. The program code storage device according to claim 11, wherein the Switch Input Scheduler Process moves packets from the SSMTs and the unmanaged traffic queue set, to the selected switch.

17. The program code storage device according to claim 10, wherein the Switch Input Scheduler Process includes a randomization function.

18. The program code storage device according to claim 10, wherein the source node has a Switch Input Scheduler Process for the switch.

31. The program code storage device according to claim 10, wherein the machine readable program code includes instruction to receive the classified flows in the destination node, wherein a switch output process sorts the classified flows received from a fabric output, and sends classified flows to an intended output queue.

14. A program code storage device, comprising:

a computer-readable storage medium; and

computer-readable program code, stored on the computer-readable storage medium, which when executed causes a computer to

classify, using a traffic engineering algorithm, incoming traffic based on flow parameters to form classified flows, wherein the traffic engineering algorithm classifies based on bandwidth that the flow requires,

embed flow parameters in a routing table in a source node for a flow,

place packets from the classified flows into a plurality of Switch-Specific Managed-Traffic Queues sets (SSMTs) and an unmanaged traffic queue set,

select such that a Switch Input Scheduler Process for a switch selects all managed packets available from one of the S SMTs first, then selects a single unmanaged packet from the unmanaged traffic queue set to form selected packets, and

transmit the selected packets from the classified flows from the source node through a multi-star switch fabric to a destination node,

wherein the multi-star switch fabric includes a switch that is connected to every node therein, but is not connected to any other switch and wherein a Bandwidth Negotiated Managed Traffic (BNMT) flow has a known bandwidth requirement.

32. The program code storage device according to claim 14, wherein the machine readable program code includes instruction to receive the classified flows in the destination node, wherein a switch output process sorts the classified flows received from a fabric output, and sends classified flows to an intended output queue.

15. A program code storage device, comprising:

a maehinecomputer-readable storage medium; and

computer-readable program code, stored on the computer-readable storage medium, which when executed causes a computer to

classify, using a traffic engineering algorithm, incoming traffic based on flow parameters to form classified flows, wherein the traffic engineering algorithm classifies based on bandwidth that the flow requires,

embed flow parameters in a routing table in a source node for a flow,

place packets from the classified flows into a plurality of Switch-Specific Managed-Traffic Queues sets (SSMTs) and an unmanaged traffic queue set,

select such that a Switch Input Scheduler Process for a switch selects all managed packets available from one of the SSMTs first, then selects a single unmanaged packet from the unmanaged traffic queue set to form selected packets, and

transmit the selected packets from the classified flows from the source node through a multi-star switch fabric to a destination node,

wherein the multi-star switch fabric includes a switch that is connected to every node, therein, but is not connected to any other switch and wherein a Un-negotiated Managed Traffic (UMT) flow having a unknown bandwidth requirement, is considered part of an aggregate for which the bandwidth is known or is placed initially in a queue for a selected switch, the UMT bandwidth is measured, and the measured bandwidth is used to correct the initial placement.

33. The program code storage device according to claim 15, wherein the machine readable program code includes instruction to receive the classified flows in the destination node, wherein a switch output process sorts the classified flows received from a fabric output, and sends classified flows to an intended output queue.

19. A multi-star switch network, comprising:

a multi-star switch fabric including a switch that is connected to every node therein, but is not connected to any other switch;

an input device, connected to the switched fabric, having a routing table, a plurality of Switch-Specific Managed-Traffic Queues Sets (SSMTs), an unmanaged traffic queue set, and a Switch Input Scheduler, wherein the input device classifies incoming traffic based on flow parameters to form classified flows, embeds the flow parameters in the routing table for a flow, places packets from the classified flows into the SSMTs and the unmanaged traffic queue set, selects such that the Switch Input Scheduler for a switch selects all managed packets available from one of the SSMTs, then selects a single unmanaged packet from the unmanaged traffic queue set to form selected packets, transmits the selected packets for the classified flows from the input device through the switch fabric to an output device; and

the output device, connected to the switched fabric, contains a switch output process that sorts the classified flows received from a fabric output, and sends the classified flows to an intended output queue.

20. The multi-star switch network according to claim 19, wherein the flow parameters include the input device, a path, a backup path, a selected switch, a backup switch, the output device, and whether the flow is managed or unmanaged.

21. The multi-star switch network according to claim 20, wherein the input device classifies, using a traffic engineering algorithm, the incoming traffic based on the flow parameters, embeds the flow parameters in the routing table for the flow, and places the packets from the classified flows into the SSMTs and the unmanaged traffic queue set.

22. The multi-star switch network according to claim 21, wherein the traffic-engineering algorithm classifies based on bandwidth that the flow requires.

25. The multi-star switch network according to claim 20, wherein the Switch Input Scheduler moves packets from the SSMTs and the unmanaged traffic queue set to the selected switch.

26. The multi-star switch network according to claim 19, wherein the Switch Input Scheduler includes a randomization function.

27. The multi-star switch network according to claim 19, wherein the input device has the Switch Input Scheduler for the switch.

23. A multi-star switch network, comprising:

a multi-star switch fabric including a switch that is connected to every node therein, but is not connected to any other switch;

an input device, connected to the switched fabric, having a routing table, a plurality of Switch-Specific Managed-Traffic Queues Sets (SSMTs), an unmanaged traffic queue set, and a Switch Input Scheduler, wherein the input device classifies incoming traffic based on flow parameters to form classified flows, embeds the flow parameters in the routing table for a flow, places packets from the classified flows into the SSMTs and the unmanaged traffic queue set, selects such that the Switch Input Scheduler for a switch selects all managed packets available from one of the SSMTs, then selects a single unmanaged packet from the unmanaged traffic queue set to form selected packets, transmits the selected packets for the classified flows from the input device through the switch fabric to an output device; and

the output device, connected to the switched fabric, containing a switch output process that sorts the classified flows received from a fabric output, and sends the classified flows to an intended output queue,

wherein a Bandwidth Negotiated Managed Traffic (BNMT) flow has a known bandwidth requirement.

24. A multi-star switch network, comprising:

a multi-star switch fabric including a switch that is connected to every node therein, but is not connected to any other switch;

an input device, connected to the switched fabric, having a routing table, a plurality of Switch-Specific Managed-Traffic Queues Sets (SSMTs), an unmanaged traffic queue set, and a Switch Input Scheduler, wherein the input device classifies incoming traffic based on flow parameters to form classified flows, embeds the flow parameters in the routing table for a flow, places packets from the classified flows into the SSMTs and the unmanaged traffic queue set, selects such that the Switch Input Scheduler for a switch selects all managed packets available from one of the SSMTs, then selects a single unmanaged packet from the unmanaged traffic queue set to form selected packets, transmits the selected packets for the classified flows from the input device through the switch fabric to an output device; and

the output device, connected to the switched fabric, containing a switch output process that sorts the classified flows received from a fabric output, and sends the classified flows to an intended output queue,

wherein a Un-negotiated Managed Traffic (UMT) flow having a unknown bandwidth requirement, is considered part of an aggregate for which the bandwidth is known or is placed initially in a queue for a selected switch, the UMT bandwidth is measured, and the measured bandwidth is used to correct the initial placement.