# US 2018/0026878 A1 · Scalable deadlock-free deterministic minimal-path routing for dragonfly networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0026878 A1
- Document ID: US20180026878A1
- Status: Published application
- Kind: A1
- Application number: 15/218,028
- Filed: 2016-07-24
- Published: 2018-01-25
- Earliest claimed: 2016-07-24
- Assignees: Mellanox Technologies Tlv Ltd.; Universidad De Castilla La Mancha
- Applicants: Mellanox Technologies Tlv Ltd.; Universidad De Castilla-La Mancha
- Inventors: Eitan Zahavi; German Maglione-Mathey; Pedro Yebenes; Jesus Escudero-Sahuquillo; Pedro Javier Garcia; Francisco Jose Quiles
- Web page: https://patentgrep.com/patent/US20180026878A1

## CPC

- H04L 49/258: {Grouping}
- H04L 45/02: Topology update or discovery
- H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops
- H04L 45/38: {Flow based routing}
- H04L 45/586: of virtual routers
- H04L 45/64: using an overlay routing layer
- H04L 49/25: Routing or path finding in a switch fabric
- H04L 49/358: {Infiniband Switches}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A communication apparatus includes an interface and a processor. The interface is configured for connecting to a communication network, including multiple network switches divided into groups. The processor is configured to predefine a strictly monotonic order among the groups, to receive an indication of a flow of packets to be routed from a source endpoint served by a source network switch belonging to a source group to a destination endpoint served by a destination network switch belonging to a destination group, to assign a first Virtual Lane (VL) to the packets in the flow if the destination group succeeds the source group in the predefined order, to assign to the packets in the flow a second VL if the destination group does not succeed the source group in the predefined order, and to configure the network switches to route the packets of the flow in accordance with the assigned VL.

## Claims

### Claim 1

A communication apparatus, comprising:
an interface for connecting to a communication network, which comprises multiple network switches that are divided into groups; and
a processor, which is configured to predefine a strictly monotonic order among the groups, to receive an indication of a flow of packets to be routed from a source endpoint served by a source network switch belonging to a source group to a destination endpoint served by a destination network switch belonging to a destination group, to assign a first Virtual Lane (VL) to the packets in the flow if the destination group succeeds the source group in the predefined order, to assign to the packets in the flow a second VL, different from the first VL, if the destination group does not succeed the source group in the predefined order, and to configure the network switches to route the packets of the flow in accordance with the assigned VL.

### Claim 2 (depends on 1)

The apparatus according to claim 1, wherein any pair of the groups is connected by at least one direct inter-group link.

### Claim 3 (depends on 1)

The apparatus according to claim 1, wherein the processor is configured to prevent a deadlock in routing of the flow, while causing the network switches to apply minimal-path routing to the flow and to retain the assigned VL throughout routing of the flow from the source endpoint to the destination endpoint.

### Claim 4 (depends on 3)

The apparatus according to claim 3, wherein the processor is configured to assign to all flows across the communication network no more than the first and second VLs.

### Claim 5 (depends on 3)

The apparatus according to claim 3, wherein the processor is configured to improve routing performance by assigning a third VL, different from the first and second VLs, to another flow of packets.

### Claim 6

A method for communication, comprising:
in a communication network, which comprises multiple network switches that are divided into groups, predefining a strictly monotonic order among the groups;
receiving an indication of a flow of packets to be routed from a source endpoint served by a source network switch belonging to a source group, to a destination endpoint served by a destination network switch belonging to a destination group;
if the destination group succeeds the source group in the predefined order, assigning a first Virtual Lane (VL) to the packets in the flow;
if the destination group does not succeed the source group in the predefined order, assigning to the packets in the flow a second VL, different from the first VL; and
routing the packets of the flow via the communication network in accordance with the assigned VL.

### Claim 7 (depends on 6)

The method according to claim 6, wherein any pair of the groups is connected by at least one direct inter-group link.

### Claim 8 (depends on 6)

The method according to claim 6, wherein assigning the first or second VL comprises preventing a deadlock in routing of the flow, while causing the network switches to apply minimal-path routing to the flow and to retain the assigned VL throughout routing of the flow from the source endpoint to the destination endpoint.

### Claim 9 (depends on 8)

The method according to claim 8, and comprising assigning to all flows across the communication network no more than the first and second VLs.

### Claim 10 (depends on 8)

The method according to claim 8, and comprising improving routing performance by assigning a third VL, different from the first and second VLs, to another flow of packets.

### Claim 11

A communication system, comprising:
multiple network switches that are divided into groups; and
a processor, which is configured to predefine a strictly monotonic order among the groups, to receive an indication of a flow of packets to be routed from a source endpoint served by a source network switch belonging to a source group to a destination endpoint served by a destination network switch belonging to a destination group, to assign a first Virtual Lane (VL) to the packets in the flow if the destination group succeeds the source group in the predefined order, to assign to the packets in the flow a second VL, different from the first VL, if the destination group does not succeed the source group in the predefined order, and to configure the network switches to route the packets of the flow in accordance with the assigned VL.

### Claim 12 (depends on 11)

The communication network according to claim 11, wherein any pair of the groups are connected by at least one direct inter-group link.

### Claim 13 (depends on 11)

The communication network according to claim 11, wherein the processor is configured to prevent a deadlock in routing of the flow, while causing the network switches to apply minimal-path routing to the flow and to retain the assigned VL throughout routing of the flow from the source endpoint to the destination endpoint.

### Claim 14

A computer software product, the product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by one or more processors in a communication network, which comprises multiple network switches that are divided into groups, cause the processors to predefine a strictly monotonic order among the groups, to receive an indication of a flow of packets to be routed from a source endpoint served by a source network switch belonging to a source group to a destination endpoint served by a destination network switch belonging to a destination group, to assign a first Virtual Lane (VL) to the packets in the flow if the destination group succeeds the source group in the predefined order, to assign to the packets in the flow a second VL, different from the first VL, if the destination group does not succeed the source group in the predefined order, and to configure the network switches to route the packets of the flow in accordance with the assigned VL.
