Unordered multi-path routing in a pcie express fabric environment

Patent metadata

Field	Value
Publication number	US-2016154756-A1
Application number	US-201414558404-A
Country	US
Kind code	A1
Filing date	Dec 2, 2014
Priority date	Mar 31, 2014
Publication date	Jun 2, 2016
Grant date	—

Abstract

A method of providing unordered packet routing in a multi-path PCIe switch fabric is provided. Fabric egress port congestion is measured and distributed to all ports within a switch and to neighboring switches. An unordered route choice vector is generated by table lookup. The local congestion mask vector identifies which of these choices has local congestion. A next hop masked choice vector generated by table lookup is gated with the next hop congestion mask vectors, received from neighboring switches, to identify the choices that have next hop congestion. Congested choices are excluded by masking. If multiple choices remain at the conclusion of the masking process, then a selection is made by round-robin among the surviving choices. If no choices remain, the selection is made by round robin among the original choices. The final selection is mapped to an egress port on the switch by table lookup.

First claim

What is claimed is:

1 . A method of providing unordered path routing in a multi-path PCIe switch fabric, the method comprising:
measuring port congestion on a local level receiving port congestion information of a next hop level, wherein the congestion information comprises low priority congestion information and medium priority congestion information; using a congestion feedback interconnect, such as a ring or bus, to communicate congestion within a chip, wherein only fabric ports send congestion information of the local level and an applicable next hop level to the congestion feedback ring; communicating local congestion information on said interconnect for both low priority congestion information and medium priority congestion information to a previous hop using a data link layer packet (DLLP) with a Reserved encoding; providing a masked choice vector that lists the number of paths available on the switch to route an unordered packet to a particular destination; saving the masked choice vector in a current hop destination look up table (CH-DLUT); providing a next hop masked choice vector that lists a number of choices available on the next hop per a local fabric port to route an unordered packet to a particular destination; saving the next hop masked choice vectors in a next hop destination look up table (NH-DLUT); and using the next hop masked choice vectors for a particular destination with a set of Port of Choice tables to construct a next hop masked port vector for that destination using the masked choice vector stored in the CH-DLUT and next hop masked port vector constructed from NH-DLUT and Ports of Choices tables respectively at locations corresponding to an unordered packets destination and their corresponding congestion information to determine a switching path for then unordered packet.

2 . A method as recited in claim 1 , wherein the masked choice vector lists a plurality of fabric ports of the switch.

3 . The method, as recited in claim 2 , further comprising communicating next hop congestion information using a data link layer packet (DLLP) with a Reserved or a Vendor Defined encoding.

4 . The method, as recited in claim 3 , wherein each local egress port maintains a counter, which counts the number of double words on an egress queue for the port, and wherein the number of double words is used to determine congestion for the port.

5 . The method, as recited in claim 4 , further comprising using programmable thresholds for the counters to determine congestion.

6 . A method of providing unordered path routing in a multi-path PCIe switch fabric, the method comprising:
measuring port congestion on a local level; receiving port congestion information of a next hop level; providing a masked choice vector that lists a number of paths available on the switch to route an unordered packet to a particular destination; saving the masked choice vector in a current hop destination look up table (CH-DLUT); providing a next hop masked choice vector that lists a number of paths available on the next hop per a local fabric port to route an unordered packet to a particular destination; saving the next hop masked choice vector in a next hop destination look up table (NH-DLUT); and using the masked choice and next hop masked choice vector stored in the CH-DLUT and NH-DLUT and their corresponding congestion information to determine a switching path for an unordered packet.

7 . A method as recited in claim 6 , wherein the masked choice vector lists a plurality) of fabric ports.

8 . The method, as recited in claim 7 , further comprising using a congestion feedback interconnect such as a ring or bus to communicate congestion within a chip.

9 . The method, as recited in claim 8 , wherein only fabric ports send congestion information of the local level and an applicable next hop level to the congestion feedback ring.

10 . The method, as recited in claim 9 , further comprising communicating next hop congestion information using a data link layer packet (DLLP) with a Reserved or Vendor Defined encoding.

11 . The method, as recited in claim 10 , wherein each fabric port provides to the congestion feedback ring the ports congestion information and next hop congestion information.

12 . The method, as recited in claim 11 , wherein the congestion information comprises low priority congestion information and medium priority congestion information.

13 . The method, as recited in claim 12 , wherein each port maintains a counter, which counts the number of double words stored in the egress queues for the port, and wherein the number of double words contained in the queues is used to determine congestion for the port.

14 . The method, as recited in claim 13 , further comprising using programmable thresholds for the counters to determine congestion.

15 . The method, as recited in claim 14 , further comprising periodically (with a configurable period) sending a reserved DLLP between switches from a center fabric port while a next hop port stays congested.

16 . A method as recited in claim 15 , further comprising:
masking off route choices in a destination look up table according to route congestion or route fault; broadcasting congestion feedback over a local switch ring; using an auto-XON feature; and

17 . A system comprising:
a switch fabric including at least two PCIe ExpressFabric™ switches and a management system, wherein the switch fabric comprises at least a plurality of switches, wherein each switch comprises:
a plurality of ports, wherein some of the plurality of ports are fabric ports; and
a feedback congestion ring which collects a congestion information only from fabric ports, wherein the congestion information provides port congestion on a local level and port congestion on an applicable next hop level;
an ingress scheduler, which collects congestion information from fabric ports on the same switch and congestion from the fabric ports on the next hop switch, wherein the uncongested paths derived form masked vector and the congestion information is used to select a single route for unordered packets, using a round robin process if multiple route choices or no route choices remain unmasked after local next hop congestion feedback masks have been applied.

18 . The system, as recited in claim 17 , wherein each port of the plurality of ports maintains a counter, whose value is proportional to the depth of the egress queue for the port, and wherein the value of the counter is used to determine congestion for the port.

19 . The system, as recited in claim 18 , further comprising programmable thresholds for the counters to determine congestion.

Assignees

• Avago Technologies General Ip

Inventors

• Dodson Jeffrey Michael
• Regula Jack
• Agrawal Natwar

Classifications

• G06F13/4282

  on a serial bus, e.g. I2C bus, SPI bus (on daisy chain buses G06F13/4247) · CPC title

• G06F13/4022 Primary

  using switching circuits, e.g. switching matrix, connection or expansion network (G06F13/4009 takes precedence) · CPC title