Optimizing traffic in a data network
AssigneeGoogle Inc.
InventorsAlok Kumar, Michael Frumkin
Life of this patent
Estimating the term…
Abstract
Systems and methods for optimizing traffic in a data network are provided. Network traffic may be optimized by associating costs with data links that connect network nodes. The method includes determining a set of lowest cost paths between a source network node and a destination network node. Paths that contain loops may be excluded from the set of lowest cost paths. Exploration of certain paths may also be delayed or prevented entirely.
Claims20
A method comprising:
- retrieving, from a memory, map data identifying a plurality of network nodes and a plurality of data links between the network nodes, wherein each data link has an associated cost;
- receiving an identification of a source network node and a destination network node in the plurality of network nodes;
- determining, by a processing circuit, a set of respective single lowest cost paths between the destination network node and each other network node of the plurality based in part on the associated costs of the plurality of data links;
- determining, by the processing circuit, a set of paths to be explored based in part on the difference between the map data and the set of respective single lowest cost paths between the plurality of network nodes and the destination network node;
- and
- determining, by the processing circuit, a set of at least two lowest cost paths from the source network node to the destination network node by exploring one or more paths in the set of paths to be explored, wherein determining the set of at least two lowest cost paths from the source network node to the destination network node comprises excluding an explored path that contains a loop.
A processing circuit configured to retrieve, from a memory, map data identifying a plurality of network nodes and a plurality of data links between the network nodes, wherein each data link has an associated cost, wherein the processing circuit is further configured to:
- receive an indication of a source network node and a destination network node in the plurality of network nodes;
- determine a set of respective single lowest cost paths between the destination network node and each other network node of the plurality based in part on the associated costs of the plurality of data links;
- determine a set of paths to be explored based in part on the difference between the map data and the set of respective single lowest cost paths between the plurality of network nodes and the destination network node;
- and
- determine a set of at least two lowest cost paths from the source network node to the destination network node by exploring one or more paths in the set of paths to be explored, wherein determining the set of at least two lowest cost paths from the source network node to the destination network node comprises excluding an explored path that contains a loop.
One or more non-transitory 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 identifying a plurality of network nodes and a plurality of data links between the network nodes, wherein each data link has an associated cost;
- receiving an identification of a source network node and a destination network node in the plurality of network nodes;
- determining, by the one or more processors, a set of respective single lowest cost paths between the plurality of network nodes and the destination network node based in part on the associated costs of the plurality of data links;
- determining, by the one or more processors, a set of paths to be explored based in part on the difference between the map data and the set of respective single lowest cost paths between the plurality of network nodes and the destination network node;
- and
- determining, by the one or more processors, a set of at least two lowest cost paths from the source network node to the destination network node by exploring one or more paths in the set of paths to be explored, wherein determining the set of at least two lowest cost paths from the source network node to the destination network node comprises excluding an explored path that contains a loop.
Dependencies are inferred from the claim text.