Calculating bandwidth information in multi-stage networks

Patent metadata

Field	Value
Publication number	US-9813356-B1
Application number	US-201615042077-A
Country	US
Kind code	B1
Filing date	Feb 11, 2016
Priority date	Feb 11, 2016
Publication date	Nov 7, 2017
Grant date	Nov 7, 2017

Abstract

Techniques and solutions are provided for calculating bandwidth matrices for multi-stage networks using matrix operations. For example, link status information can be obtained for network devices of the multi-stage network. Using the link status information, link state matrices can be determined representing bandwidth and connectivity between network devices of adjacent stages of the multi-stage network. Bandwidth matrices can then be calculated using the link state matrices. The bandwidth matrices represent how network traffic is distributed to destination devices.

First claim

What is claimed is:

1. A method, implemented by a controller device, for calculating bandwidth matrices for a Clos network comprising a plurality of tiers, the method comprising:
receiving, by the controller device, link status information indicating link bandwidth and link connectivity from network devices of the Clos network, wherein each tier, of the plurality of tiers, comprises a plurality of network devices, wherein each network device is a switch or a router, and wherein the Clos network is represented by an unfolded Clos network having a plurality of stages;
for each pair of adjacent stages of the plurality of stages:
determining, by the controller, a link state matrix between the pair of adjacent stages from the link status information, the link state matrix representing link bandwidth and link connectivity between the pair of adjacent stages;

calculating, by the controller using matrix multiplication operations, a set of bandwidth matrices for destination devices, wherein the set of bandwidth matrices comprise a separate bandwidth matrix for each of the plurality of stages representing how network traffic is distributed to the destination devices;
sending, by the controller device, ratios of values generated from the set of bandwidth matrices to the network devices of the Clos network; and
distributing network traffic for the destination devices using the network devices and according to the ratios of values.

2. The method of claim 1 wherein, for each pair of adjacent stages, the link state matrix contains a respective matrix entry for each combination of network devices from the adjacent stages, the matrix entry set to:
a value of zero when a network connection is down or not present between the combination of network devices; and
a value of one when the network connection is up between the combination of network devices, the value of one representing a network link bandwidth that is uniform among network links within the Clos network.

3. The method of claim 1 wherein the destination devices are defined by a unique connectivity pattern of network devices in an egress stage of the Clos network.

4. The method of claim 3 wherein additional sets of bandwidth matrices are calculated for additional groups of destination devices, wherein each additional group of destination devices has a unique connectivity pattern in the egress stage of the Clos network.

5. A computing device comprising:
a processing unit;
wherein the computing device is configured to use the processing unit to perform operations comprising:
obtaining link status information for network devices forming a multi-stage network, wherein the link status information indicates network bandwidth between the network devices;
determining a link state matrix representing network bandwidth between a pair of adjacent stages of the multi-stage network; and
calculating, using matrix multiplication operations, a bandwidth matrix for a stage of the multi-stage network, the bandwidth matrix representing how network traffic is distributed for a destination device located outside the multi-stage network;
wherein the network devices of the multi-stage network distribute network traffic for the destination device according to the bandwidth matrix.

6. The computing device of claim 5 wherein network traffic is distributed according to a ratio of values within the bandwidth matrix.

7. The computing device of claim 5 wherein the bandwidth matrix contains a respective value for each network device of the stage, the value indicating network bandwidth for the network device.

8. The computing device of claim 5 wherein the link state matrix contains a respective matrix entry for each combination of network devices from the pair of adjacent stages, the matrix entry set to:
a first value when a network connection is down or not present between the combination of network devices; and
a second value, different from the first value, when the network connection is up between the combination of network devices, the second value representing a network bandwidth.

9. The computing device of claim 5 wherein the link state matrix contains a respective matrix entry for each combination of network devices from the pair of adjacent stages, the matrix entry set to:
a first value when a network connection is down or not present between the combination of network devices; and
a plurality of other values representing a corresponding plurality of different network bandwidths when the network connection is up between the combination of network devices.

10. The computing device of claim 5 wherein the destination device is defined by a unique connectivity pattern of network devices in an egress stage of the multi-stage network.

11. The computing device of claim 5 , the operations further comprising:
calculating, using matrix multiplication operations, a bandwidth matrix for each remaining stage of the multi-stage network to generate a set of bandwidth matrices representing how network traffic is distributed to the destination device for all stages of the multi-stage network.

12. The computing device of claim 5 wherein the computing device further comprises a graphics processing unit (GPU), and wherein the matrix multiplication operations are performed, at least in part, by the GPU.

13. The computing device of claim 5 wherein each stage of the multi-stage network comprises a plurality of network devices, wherein each network device is a switch or a router.

14. The computing device of claim 5 wherein the bandwidth matrix is part of an extended bandwidth matrix that represents how network traffic is distributed for multiple unique connectivity patterns of destination devices in an egress stage of the multi-stage network.

15. A computer-readable storage medium storing computer-executable instructions for causing a computing device to perform operations, the operations comprising:
receiving, at a stage of a multi-stage network, network traffic for a destination device located outside the multi-stage network;
obtaining a ratio of values associated with network devices of a next-hop stage of the multi-stage network, wherein the ratio of values is from a bandwidth matrix calculated with matrix multiplication operations using a link state matrix, the bandwidth matrix representing how network traffic is distributed for the destination device; and
distributing the network traffic among the network devices of the next-hop stage according to the ratio of values.

16. The computer-readable storage medium of claim 15 wherein the ratio of values is received by network devices of the stage from a controller device, and wherein the ratio of values is determined by the controller device using the bandwidth matrix.

17. The computer-readable storage medium of claim 15 wherein the bandwidth matrix contains a respective value for each network device of the next-hop stage, the value indicating network bandwidth for network links of the network device capable of delivering network traffic to the destination device.

18. The computer-readable storage medium of claim 15 wherein the link state matrix contains a respective matrix entry for each combination of network devices from the stage and the next-hop stage, the matrix entry indicating a network bandwidth.

19. The computer-readable storage medium of claim 15 wherein the link state matrix contains a respective matrix entry for each combination of network devices from the stage and the next-hop stage, the matrix entry set to:
a value of zero when a network

Assignees

• Amazon Tech Inc

Inventors

• Kim Minsung
• Ramachandran Sudhakumari Ashi

Classifications

• H04L45/44

  Distributed routing · CPC title

• H04L49/1515 Primary

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