Switch routing algorithms

Patent metadata

Field	Value
Publication number	US-10237205-B2
Application number	US-201313922670-A
Country	US
Kind code	B2
Filing date	Jun 20, 2013
Priority date	Jun 20, 2013
Publication date	Mar 19, 2019
Grant date	Mar 19, 2019

Abstract

A method using a computer in conjunction with a non-transitory computer readable storage medium is provided comprising a computer receiving a message for forwarding at an ingress switch of a multi-stage circuit switching network. The method also comprises computer executing a first routing algorithm in transmitting the message, the algorithm comprising the computer determining at least one availability matrix for each middle switch, wherein a given middle switch comprises a switch between ingress and egress switches of the network. The method also comprises the computer assigning resources to a selected middle switch and updating the availability matrix and causing the ingress switch to transmit the message via the middle switch based on determining a first availability matrix for the middle switch using the algorithm wherein the algorithm is executed to forward messages on at least one of unicast, fan-in, and fan-out bases and minimize blocking and imbalance on middle switches.

First claim

What is claimed is:

1. A method implemented in a computer for routing messages through a multi-stage circuit switching network, the method comprising:
maintaining an availability matrix for each middle switch of the multi-stage circuit switching network comprising a plurality of middle switches between an ingress switch and an egress switch, wherein each availability matrix indicates therein available subchannels of a corresponding one of the plurality of middle switches for use to route messages;
receiving a message for forwarding at the ingress switch of the multi-stage circuit switching network;
determining, using the availability matrix for each middle switch, a selected middle switch of the plurality of middle switches of the multi-stage circuit switching network that has the most availability through which to route the message, wherein the availability of each middle switch in the plurality of middle switches is the minimum of available input subchannels and available output subchannels for each middle switch;
executing a heuristic tie-breaking method between a first middle switch and a second middle switch in determining the selected middle switch;
updating the availability matrix for the selected middle switch using an asymmetric resource availability matrix updating algorithm to indicate therein a reduction of the available subchannels of the selected middle switch; and
causing the ingress switch to transmit the message via the selected middle switch on at least one of a unicast basis, a fan-in basis, and a fan-out basis.

2. The method of claim 1 , wherein the multi-stage circuit switching network is a Clos network.

3. The method of claim 1 , wherein each availability matrix describes current availability and current usage of routing capacity of a middle switch in the plurality middle switches.

4. The method of claim 1 , further comprising executing fan-in forwarding at early stages of the multi-stage circuit switching network and executing fan-out forwarding at latter stages of the multi-stage circuit switching network.

5. The method of claim 1 , further comprising determining routing solutions for unicast transmissions based on a worst-fit bin packing algorithm.

6. A method implemented in a computer for routing messages through a multi-stage circuit switching network, the method comprising:
maintaining an availability matrix for each middle switch of the multi-stage circuit switching network comprising a plurality of middle switches between an ingress switch and an egress switch, wherein each availability matrix indicates therein available subchannels of a corresponding one of the plurality of middle switches for use to route messages in the multi-stage circuit switching network;
receiving a message to forward to the egress switch of the multi-stage circuit switching network;
determining, using the availability matrix for each middle switch, a selected middle switch of the plurality of middle switches in the multi-stage circuit switching network that has the most availability through which to route the message to the egress switch, wherein the availability of each middle switch in the plurality of middle switches is the minimum of available input subchannels and available output subchannels for each middle switch;
executing a heuristic tie-breaking method between a first middle switch and a second middle switch in determining the selected middle switch;
updating the availability matrix for the selected middle switch using an asymmetric resource availability matrix updating algorithm to indicate therein a reduction of the available subchannels of the selected middle switch; and
transmitting the message to the egress switch using the selected middle switch.

7. The method of claim 6 , wherein the message is a multicast message to be forwarded to one or more egress switches and wherein transmitting the multicast message includes dividing the multicast message into two or more unicast messages at the selected middle switch and forwarding the two or more unicast messages to the one or more egress switches.

8. The method of claim 6 , wherein the message is one of two or more unicast messages on different input subchannels of the ingress switch and further comprising combining the two or more unicast messages into one output subchannel at the ingress switch.

9. The method of claim 6 , wherein the availability matrix includes a table.

10. The method of claim 6 , wherein the message is transmitted through a max-min path.

11. The method of claim 6 , wherein the message is transmitted using a worst-fit bin packing algorithm.

12. An apparatus, comprising:
a multi-stage circuit switching network comprising a plurality of middle switches between an ingress switch and an egress switch; and
a computer configured to:
maintain an availability matrix for each middle switch of the multi-stage circuit switching network, wherein each availability matrix indicates therein available subchannels of a corresponding one of the plurality of middle switches for use to route messages in the multi-stage circuit switching network,
receive a message to forward to the egress switch of the multi-stage circuit switching network,
determine, using the availability matrix for each middle switch, a selected middle switch of the plurality of middle switches in the multi-stage circuit switching network that has the most availability through which to route the message to the egress switch, wherein the availability of each middle switch in the plurality of middle switches is the minimum of available input subchannels and available output subchannels for each middle switch,
execute a heuristic tie-breaking method between a first middle switch and a second middle switch in determining the selected middle switch,
update the availability matrix for the selected middle switch using an asymmetric resource availability matrix updating algorithm to indicate therein a reduction of the available subchannels of the selected middle switch, and
transmit the message to the egress switch using the selected middle switch.

13. The apparatus of claim 12 , wherein the computer is configured to cause the ingress switch to transmit the message via the selected middle switch on at least one of a unicast basis, a fan-in basis, and a fan-out basis.

14. The apparatus of claim 12 , wherein the multi-stage circuit switching network is a Clos network.

15. The apparatus of claim 12 , wherein the computer is configured to execute fan-in forwarding at early stages of the multi-stage circuit switching network and executing fan-out forwarding at latter stages of the multi-stage circuit switching network.

16. The apparatus of claim 12 , wherein the computer is configured to determine routing solutions for unicast transmissions based on a worst-fit bin packing algorithm.

Assignees

• Boeing Co

Inventors

• Miller Kristina A
• Le Tu Q
• Roh Tae J
• Liu Helen

Classifications

• H04L49/1515 Primary

  Non-blocking multistage, e.g. Clos · CPC title

• H04Q3/68

  Grouping or interlacing selector groups or stages · CPC title

• H04L49/25

  Routing or path finding in a switch fabric · CPC title