# US 10,374,943 B2 · Routing packets in dimensional order in multidimensional networks > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,374,943 B2 - Document ID: US10374943B2 - Status: Granted - Kind: B2 - Application number: 15/678,550 - Filed: 2017-08-16 - Published: 2019-02-21 - Granted: 2019-08-06 - Earliest claimed: 2017-08-16 - Assignees: Hewlett Packard Enterprise Development LP - Applicants: Hewlett Packard Enterprise Development LP - Inventors: Nicholas George McDonald - Web page: https://patentgrep.com/patent/US10374943B2 ## CPC - H04L 45/121: by minimising delays - H04L 43/0882: Utilisation of link capacity - H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops - H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)} - H04L 45/124: {using a combination of metrics} - H04L 45/125: based on throughput or bandwidth - H04L 45/302: Route determination based on requested QoS - H04L 43/16: Threshold monitoring - H04L 45/22: {Alternate routing} - H04L 47/805: {QOS or priority aware} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Examples relate to routing packets in dimensional order 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 with a dimensional order 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. An optimal output port among all the candidate output ports is selected and the packet is routed to a next hop of the network though the optimal output port using a first resource class when the optimal output port corresponds to a candidate minimal path and a second resource class when the optimal output port corresponds to a candidate non-minimal path. ## 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 in a dimensional order, the candidate output ports corresponding to candidate minimal paths and candidate non-minimal paths between the network device and the destination network device; selecting, by the routing engine, an optimal output port among all the candidate output ports, by (1) 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 (2) associating the weight to the corresponding candidate output port; and routing, by the routing engine, the packet to a next hop of the network though the optimal output port using a first resource class when the optimal output port corresponds to a candidate minimal path and a second resource class when the optimal output port corresponds to a candidate non-minimal path. ### Claim 2 (depends on 1) The method of claim 1, wherein the first resource class is a first virtual channel (VC) and the second resource class is a second VC. ### Claim 3 (depends on 1) The method of claim 1, wherein the first resource class is a first packet buffer and the second resource class is a second packet buffer. ### Claim 4 (depends on 1) The method of claim 1, 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 5 (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; and 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 6 (depends on 5) The method of claim 5, wherein the congestion of the candidate paths comprises at least one selected from among a broken link, a link whose bandwidth usage has exceeded a bandwidth threshold and a blocked link. ### Claim 7 (depends on 1) The method of claim 1, wherein routing the packet to a next hop of the network through the optimal output port in the dimensional order comprises fully resolving a current dimension prior to routing the packet to a next dimension within the multidimensional network. ### Claim 8 (depends on 1) The method of claim 1, wherein routing the packet to a next hop of the network through the optimal output port in the dimensional order, wherein the next hop corresponds to a non-minimal path, comprises routing the packet to the same dimension the packet is currently being routed. ### Claim 9 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 in a dimensional order, the candidate output ports corresponding to candidate minimal paths and candidate non-minimal paths between the network device and the destination network device; assign a first resource class to the candidate output ports corresponding to candidate minimal paths and a second resource class to the candidate output ports corresponding to candidate non-minimal paths; select an optimal output port among all the candidate output ports, wherein the instructions to select the optimal path comprise instructions to (1) 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 (2) associate the weight to the corresponding candidate output port; and route the packet to a next hop of the network though the optimal output port and using the corresponding resource class. ### Claim 10 (depends on 9) The non-transitory machine readable storage medium of claim 9, wherein the first resource class is a first virtual channel (VC) and the second resource class is a second VC. ### Claim 11 (depends on 9) The non-transitory machine readable storage medium of claim 9, wherein the first resource class is a first packet buffer and the second resource class is a second packet buffer. ### Claim 12 (depends on 9) The non-transitory machine readable storage medium of claim 9, 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 13 (depends on 9) The non-transitory machine readable storage medium of claim 9, wherein the instructions to select the optimal output port among the candidate output ports comprise instructions to: detect congestion of the candidate paths; determine whether the congestion in a particular minimal path exceeds a threshold; select, when the particular minimal path does not exceed the threshold, the corresponding candidate output port as the optimal output port; and 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 14 (depends on 13) The non-transitory machine readable storage medium of claim 13, wherein the congestion of the candidate paths comprises at least one selected from among a broken link, a link whose bandwidth usage has exceeded a bandwidth threshold and a blocked link. ### Claim 15 (depends on 9) The non-transitory machine readable storage medium of claim 9, wherein the instructions to route the packet to a next hop of the network though the optimal output port in the dimensional order comprises instructions to fully resolve a current dimension prior to routing the packet in a next dimension within the multidimensional network. ### Claim 16 (depends on 9) The non-transitory machine readable storage medium of claim 9, wherein the instructions to route the packet to a next hop of the network though the optimal output port in the dimensional order, wherein the next hop corresponds to a non-minimal path, comprises instructions to route the packet in the same dimension the packet is currently being routed.