# US 2019/0058651 A1 · Routing packets using distance classes

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

- Number: US 2019/0058651 A1
- Document ID: US20190058651A1
- Status: Published application
- Kind: A1
- Application number: 15/677,504
- Filed: 2017-08-15
- Published: 2019-02-21
- Earliest claimed: 2017-08-15
- Assignees: Hewlett Packard Enterprise Development LP
- Applicants: Hewlett Packard Enterprise Development LP
- Inventors: Nicholas George McDonald
- Web page: https://patentgrep.com/patent/US20190058651A1

## CPC

- H04L 45/243: using M+N parallel active paths
- H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops
- H04L 45/44: Distributed routing
- H04L 45/3065: {for real time traffic}
- H04L 45/586: of virtual routers
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Examples relate to routing packets using distance classes in multidimensional networks. A packet is received at a network device in a fully connected multidimensional network and all possible candidate output ports for the packet to be routed to the destination network device are determined. The candidate output ports correspond to candidate minimal paths and candidate non-minimal paths between the network device and the destination network device along all remaining unaligned dimensions of the multidimensional network. An optimal output port among all the candidate output ports is selected and the packet is routed to a next hop in the network though the optimal output port and using a next distance class.

## Claims

### Claim 1

A method, comprising:
receiving a packet at a network device of a plurality of network devices in a fully connected multidimensional network, wherein the packet is to be routed to a destination network device;
determining, by a routing engine of the network device, all possible candidate output ports for the packet to be routed to the destination network device, the candidate output ports corresponding to candidate minimal paths and candidate non-minimal paths between the network device and the destination network device along all remaining unaligned dimensions of the fully connected multidimensional network;
selecting, by the routing engine, an optimal output port among all the candidate output ports; and
routing, by the routing engine, the packet to a next hop in the network though the optimal output port and using a next distance class.

### Claim 2 (depends on 1)

The method of claim 1, wherein the next distance class is selected among an order increased distance class, an order decreased distance class and a randomly permutated distance class, wherein the permutation is fixed.

### Claim 3 (depends on 1)

The method of claim 1, wherein the next distance class is selected from a group including virtual channels (VCs) and packet buffers.

### Claim 4 (depends on 1)

The method of claim 1, wherein selecting the optimal output port among the candidate output ports comprises:
calculating a weight for each candidate path, the weight being based on a combination of a number of hops of the candidate path and a congestion along the candidate path; and
associating the weight to the corresponding candidate output port.

### Claim 5 (depends on 4)

The method of claim 4, comprising selecting, by the routing engine, the optimal output port as the candidate output port corresponding to the candidate path having a lowest estimated latency.

### Claim 6 (depends on 1)

The method of claim 1, wherein selecting the optimal output port among the candidate output ports comprises:
detecting congestion of the candidate paths;
determining whether the congestion in a particular minimal path exceeds a threshold; and
selecting, when the particular minimal path does not exceed the threshold, the corresponding candidate output port as the optimal output port; or
selecting, when all the candidate minimal paths exceed the threshold, a particular candidate output port corresponding to one of the non-minimal paths as the optimal output port.

### Claim 7 (depends on 1)

The method of claim 1, comprising:
providing a fully connected N-dimensional network, N being a integer greater than 0;
provisioning the fully connected N-dimensional network with 2*N distance classes; and
enabling de-routing the packet to hops corresponding to non-minimal paths wherein the hops link the network device to an intermediate network device in a dimension of the N-dimensional network and wherein the packet de-routes at most once per dimension.

### Claim 8 (depends on 1)

The method of claim 1, comprising:
providing a fully connected N-dimensional network, N being a integer greater than 0;
provisioning the fully connected N-dimensional network with N+M distance classes, M being an integer greater than 0; and
enabling de-routing the packet to hops corresponding to non-minimal paths wherein the hops link the network device to an intermediate network device in a dimension of the N-dimensional network and wherein the packet de-routes a maximum of M times until reaching the destination network device.

### Claim 9 (depends on 8)

The method of claim 8, comprising disabling, by the routing engine, the ability to perform two deroutes in a row on the same dimension.

### Claim 10 (depends on 8)

The method of claim 8, comprising:
checking, by the routing engine, a number of remaining hops for the packet to reach the destination network device through the candidate minimal paths and a number of remaining distance classes available for the route;
calculating a difference between the number of remaining distance classes and the number of remaining hops required by the candidate minimal paths;
selecting, by the routing engine, an optimal output port corresponding to a minimal path or non-minimal path as the optimal output port when the difference is greater than zero; and
selecting, by the routing engine, an optimal output port corresponding to a minimal path as the optimal output port when the difference is equal to zero.

### Claim 11

A non-transitory machine readable storage medium comprising instructions executable by a routing engine of a network device of a plurality of network devices in a fully connected multidimensional network to:
in response to reception of a packet in the network device, determine all possible candidate output ports for the packet to be routed to the destination network device, the candidate output ports corresponding to minimal paths and non-minimal paths between the network device and the destination network device along all remaining unaligned dimensions of the fully connected multidimensional network;
select an optimal output port among all the candidate output ports; and
route the packet to a next hop in the network through the optimal output port and using a next distance class selected from a group comprising virtual channels (VC) and packet buffers.

### Claim 12 (depends on 11)

The non-transitory machine readable storage medium of claim 11, comprising instructions to use a VC for routing the packet that is different from the VCs used by other network devices to route the packet to the destination device.

### Claim 13 (depends on 11)

The non-transitory machine readable storage medium of claim 11, wherein the instructions to select the optimal output port among the candidate output ports comprise instructions to:
calculate a weight for each candidate path, the weight being based on a combination of a number of hops of the candidate path and a congestion along the candidate path; and
associate the weight to the corresponding candidate output port.

### Claim 14 (depends on 13)

The non-transitory machine readable storage medium of claim 13, wherein the instructions to select the optimal output port among the candidate output ports further comprise instructions to select the optimal output port as the candidate output port corresponding to the candidate path having a lowest estimated latency.

### Claim 15 (depends on 11)

The non-transitory machine readable storage medium of claim 11, wherein the instructions to select the optimal output port comprise instructions to:
detect congestion of the candidate paths;
determine whether the congestion in a particular minimal path exceeds a threshold; and
select, when the particular minimal path does not exceed the threshold, the corresponding candidate output port as the optimal output port; or
select, when all the candidate minimal paths exceed the threshold, a particular candidate output port corresponding to one of the non-minimal paths as the optimal output port.

### Claim 16 (depends on 11)

The non-transitory machine readable storage medium of claim 11, comprising instructions to:
provide a fully connected N-dimensional network, N being a integer greater than 0;
provision the fully connected N-dimensional network with 2*N distance classes; and
enable de-routing the packet to hops corresponding to non-minimal paths wherein the hops link the network device to an intermediate network device in a dimension of the N-dimensional network and wherein the packet de-routes once per dimension.

### Claim 17 (depends on 11)

The non-transitory machine readable storage medium of claim 11, comprising instructions to:
provide a fully connected N-dimensional network, N being a integer greater than 0;
provision the fully connected N-dimensional network with N+M distance classes, M being an integer greater than 0; and
enable de-routing the packet to hops corresponding to non-minimal paths wherein the hops link the network device to an intermediate network device in a dimension of the N-dimensional network and wherein the packet de-routes a maximum of M times until reaching the destination network device.

### Claim 18 (depends on 17)

The non-transitory machine readable storage medium of claim 17, comprising instructions to:
check a number of remaining hops for the packet to reach the destination network device through the candidate path and a number of de-routes previously performed by the packet;
calculate a difference between M and the number of de-routes previously performed by the packet;
select an optimal output port corresponding to a minimal path or non-minimal path as the optimal output port when the difference is greater than zero; and
select, by the routing engine, an optimal output port corresponding to a minimal path as the optimal output port when the difference is equal to zero.

### Claim 19

A system comprising:
a network device having at least one routing engine and at least one output port, wherein the routing engine is to:
receive a packet that is to be routed to a destination network device through a plurality of network devices in a fully connected multidimensional network;
determine, all possible candidate output ports for the packet to be routed to the destination network device, the candidate output ports corresponding to candidate minimal paths and candidate non-minimal paths between the network device and the destination network device along all remaining unaligned dimensions of the fully connected multidimensional network;
select an optimal output port among all the candidate output ports; and
route the packet to a next hop in the network though the optimal output port and using a next distance class.

### Claim 20 (depends on 19)

The system of claim 19, wherein the fully connected multidimensional network is a network selected among a HyperX network and a flattened butterfly network.
