Systems and methods for multipath load balancing

Patent metadata

Field	Value
Publication number	US-9654401-B2
Application number	US-201414229958-A
Country	US
Kind code	B2
Filing date	Mar 30, 2014
Priority date	Mar 30, 2014
Publication date	May 16, 2017
Grant date	May 16, 2017

Abstract

A computer-implemented method for multipath load balancing may include (1) identifying a plurality of paths from a source switch to a destination switch, (2) determining, for each of the plurality of paths, a limiting bandwidth of the path based at least in part on the lowest link bandwidth of one or more data links in the path, and (3) balancing network traffic that is transmitted from the source switch to the destination switch across the plurality of paths based at least in part on the limiting bandwidth of each of the plurality of paths. Various other methods, systems, and computer-readable media are also disclosed.

First claim

What is claimed is:

1. A computer-implemented method comprising:
identifying an intermediate switch that connects a source switch to a destination switch, wherein:
a plurality of shortest paths connect the source switch to the intermediate switch;
each of the plurality of shortest paths comprises one or more data links;
a data link connects the intermediate switch directly to the destination switch; and
each of the one or more data links and the data link has a maximum available link bandwidth;

assigning, for each shortest path in the plurality of shortest paths, a limiting bandwidth to the shortest path based at least in part on the maximum available link bandwidth of the one or more data links of the shortest path;
assigning a limiting bandwidth to a shortest path from the source switch to the destination switch through the intermediate switch that is equal to the lowest of the maximum available link bandwidth of the data link and a sum of the limiting bandwidths of the plurality of shortest paths;
identifying an additional intermediate switch that connects the source switch to the destination switch, wherein:
an additional plurality of shortest paths connect the source switch to the additional intermediate switch;
each of the additional plurality of shortest paths comprises one or more additional data links;
an additional data link connects the additional intermediate switch directly to the destination switch; and
each of the one or more additional data links and the additional data link has a maximum available link bandwidth;

assigning, for each shortest path in the additional plurality of shortest paths, a limiting bandwidth to the shortest path based at least in part on the maximum available link bandwidth of the one or more additional data links of the shortest path;
assigning a limiting bandwidth to an additional shortest path from the source switch to the destination switch through the additional intermediate switch that is equal to the lowest of the maximum available link bandwidth of the additional data link and a sum of the limiting bandwidths of the additional plurality of shortest paths; and
balancing network traffic that is transmitted from the source switch to the destination switch across the shortest path and the additional shortest path based at least in part on the limiting bandwidth of the shortest path and the limiting bandwidth of the additional shortest path.

2. The method of claim 1 , wherein the source switch, the intermediate switch, and the destination switch comprise at least a portion of a virtual-chassis fabric that behaves as a single logical switch.

3. The method of claim 1 , wherein balancing the network traffic across the shortest path comprises, for each of a plurality of shortest paths from the source switch to the destination switch:
assigning a path weight to the path based at least in part on a ratio of the limiting bandwidth of the path to a sum of the limiting bandwidths of all paths in the plurality of shortest paths from the source switch to the destination switch; and
using the path weight assigned to the path to transmit a portion of the network traffic via the path.

4. The method of claim 3 , wherein using the path weight assigned to the path to transmit the portion of the network traffic via the path comprises:
identifying a plurality of interfaces of the source switch that connect to the path;
for each interface in the plurality of interfaces:
determining a bandwidth of the interface; and
assigning an interface weight to the interface based at least in part on a ratio of the bandwidth of the interface to a sum of the bandwidths of all interfaces in the plurality of interfaces; and

using the interface weight assigned to each interface to balance the portion of the network traffic that is transmitted via the path across the plurality of interfaces.

5. The method of claim 1 , wherein balancing the network traffic across the shortest path comprises balancing the network traffic across a plurality of interfaces of the source switch that connect to the plurality of shortest paths.

6. The method of claim 5 , wherein balancing the network traffic across the plurality of interfaces of the source switch that connect to the plurality of shortest paths comprises, for each of the plurality of interfaces:
assigning an interface weight to the interface based at least in part on:
a ratio of the bandwidth of the interface to a sum of the bandwidths of all interfaces in the plurality of interfaces that connect to at least one path in the plurality of shortest paths to which the interface connects; and
a ratio of the limiting bandwidth of the at least one path in the plurality of shortest paths to which the interface connects to a sum of the limiting bandwidths of all paths in the plurality of shortest paths; and

using the interface weight assigned to the interface to transmit a portion of the network traffic via the interface.

7. The method of claim 1 , wherein the plurality of shortest paths comprise at least every shortest path from the source switch to the intermediate switch.

8. A system comprising:
an identifying module, stored in memory, that:
identifies an intermediate switch that connects a source switch to a destination switch, wherein:
a plurality of shortest paths connect the source switch to the intermediate switch;
each of the plurality of shortest paths comprises one or more data links;
a data link connects the intermediate switch directly to the destination switch; and
each of the one or more data links and the data link has a maximum available link bandwidth; and

identifies an additional intermediate switch that connects the source switch to the destination switch, wherein:
an additional plurality of shortest paths connect the source switch to the additional intermediate switch;
each of the additional plurality of shortest paths comprises one or more additional data links;
an additional data link connects the additional intermediate switch directly to the destination switch; and
each of the one or more additional data links and the additional data link has a maximum available link bandwidth;

a determining module, stored in memory, that:
assigns, for each shortest path in the plurality of shortest paths, a limiting bandwidth to the shortest path based at least in part on the maximum available link bandwidth of the one or more data links of the shortest path;
assigns a limiting bandwidth to a shortest path from the source switch to the destination switch through the intermediate switch that is equal to the lowest of the maximum available link bandwidth of the data link and a sum of the limiting bandwidths of the plurality of shortest paths;
assigns, for each shortest path in the additional plurality of shortest paths, a limiting bandwidth to the shortest path based at least in part on the maximum available link bandwidth of the one or more additional data links of the shortest path; and
assigns a limiting bandwidth to an additional shortest path from the source switch to the destination switch through the additional intermediate switch that is equal to the lowest of the maximum available link bandwidth of the additional data link and a sum of the limiting bandwidths of the additional plurality of shortest paths;

a balancing module, stored in memory, that balances network traffic that is transmitted from the source switch to the destination switch across the shortest path and the additional shortest path based at least in part on the limiting bandwidth of the shortest path and the limiting bandwidth of the additional shortest path; and
at least one physical processor that executes the identifying module, the determining module, and the balancing modul

Assignees

• Juniper Networks Inc

Inventors

• Wu Qiang

Classifications

• H04L47/125 Primary

  by balancing the load, e.g. traffic engineering · CPC title

• H04L45/125

  based on throughput or bandwidth · CPC title

• H04L45/24

  Multipath · CPC title