SPLITTING A NETWORK TRAFFIC FLOW

• US 20130117466A1
• Filed: 08/22/2012
• Published: 05/09/2013
• Est. Priority Date: 11/08/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hartman, Tzvika, Segalov, Michal, Raz, Dan, Hassidim, Avinatan
• Granted Patent: US 9,015,340 B2
• Time in Patent Office: Days
• US Class Current: 709/235
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols

Abstract

Systems and methods for splitting a network traffic flow in a data network are described. A flow of traffic between a source node and a destination node in the data network is split into a set of data paths. A data path includes one or more data links between nodes in the data network. A submap of the data network that excludes at least one data link is used to determine the set of flow paths.

Claims

1. A method for splitting a flow of data in a data network into a set of flow paths comprising:

retrieving, from a memory, map data comprising a plurality of network nodes and a plurality of data links between the network nodes, wherein each data link has an associated flow value;

receiving, at a processing circuit, a selection of a source node and a selection of a destination node from the plurality of network nodes;

sorting the data links based in part on the associated flow values;

determining, by the processing circuit, a submap of the map data using the sorted data links, wherein the submap has a maximum flow between the selected source node and the selected destination node that is greater than a predefined percentage of a maximum flow between the selected source node and the selected destination node in the map data;

adjusting flow capacities of data links in the submap based on a smallest flow capacity of a data link in the submap; and

determining, by the processing circuit, a set of flow paths from the source node to the destination node using the adjusted flow capacities.

2. The method of claim 1, wherein flow is conserved for each network node between the source node and the destination node.

3. The method of claim 1, wherein the set of flow values and data links for the submap are determined based in part on bandwidth of the data links in the submap.

4. The method of claim 1, wherein the set of flow values and data links for the submap are determined based in part on latency of the data links in the submap.

5. The method of claim 1, further comprising providing the set of flow paths to another processing circuit.

6. The method of claim 1, wherein a flow capacity corresponds to a maximum bandwidth allocated to a priority class in the data network.

7. The method of claim 1, wherein the network nodes correspond to nodes in an MPLS network.

8. A system for splitting a flow of data in a data network into a set of flow paths comprising a processing circuit configured to:

retrieve map data comprising a plurality of network nodes and a plurality of data links between the network nodes, wherein each data link has an associated flow value;

receive a selection of a source node and a selection of a destination node from the plurality of network nodes;

sort the data links based in part on the associated flow values;

determine a submap of the map data using the sorted data links, wherein the submap has a maximum flow between the selected source node and the selected destination node that is greater than a predefined percentage of a maximum flow between the selected source node and the selected destination node in the map data;

adjust flow capacities of data links in the submap based on a smallest flow capacity of a data link in the submap; and

determine a set of flow paths from the source node to the destination node using the adjusted flow capacities.

9. The system of claim 8, wherein flow is conserved for each network node between the source node and the destination node.

10. The system of claim 8, wherein the set of flow values and data links for the submap are determined based in part on bandwidth of the data links in the submap.

11. The system of claim 8, wherein the set of flow values and data links for the submap are determined based in part on latency of the data links in the submap.

12. The system of claim 8, further comprising providing the set of flow paths to another processing circuit.

13. The system of claim 8, wherein a flow capacity corresponds to a maximum bandwidth allocated to a priority class in the data network.

14. The system of claim 8, wherein the network nodes correspond to nodes in an MPLS network.

15. Computer-readable media having instructions stored therein, the instructions being executable by one or more processors to cause the one or more processors to perform operations comprising:

retrieving, from a memory, map data comprising a plurality of network nodes and a plurality of data links between the network nodes, wherein each data link has an associated flow value;

receiving a selection of a source node and a selection of a destination node from the plurality of network nodes;

sorting the data links based in part on the associated flow values;

determining a submap of the map data using the sorted data links, wherein the submap has a maximum flow between the selected source node and the selected destination node that is greater than a predefined percentage of a maximum flow between the selected source node and the selected destination node in the map data;

adjusting flow capacities of data links in the submap based on a smallest flow capacity of a data link in the submap; and

determining a set of flow paths from the source node to the destination node using the adjusted flow capacities.

16. The computer-readable media of claim 15, wherein flow is conserved for each network node between the source node and the destination node.

17. The computer-readable media of claim 15, wherein the set of flow values and data links for the submap are determined based in part on bandwidth of the data links in the submap.

18. The computer-readable media of claim 15, wherein the set of flow values and data links for the submap are determined based in part on latency of the data links in the submap.

19. The computer-readable media of claim 15, wherein the operations further comprise providing the set of flow paths to a network router.

20. The computer-readable media of claim 19, wherein the network router is a router in an MPLS network.