Rapid alternate paths for network destinations
AssigneeAvici Systems, Inc.
InventorsAlia Atlas, Raveendra Torvi
Life of this patent
Estimating the term…
Abstract
Network traffic is sent via alternate paths in cases of network link or node failure. An alternate node responds to U-Turn traffic from a primary neighbor to select a further alternate. An algorithm for determining the alternate paths is provided to select loop-free neighbors.
Claims49
A method of forwarding data packets comprising, at a network node:
- storing links to primary neighbor nodes to which the data packet is primarily forwarded;
- storing links to alternate neighbor nodes, and
- upon receiving a U-turn data packet at the network node from a primary neighbor node, forwarding the data packet to an associated alternate neighbor node.
A method of forwarding a unicast data packet to a globally defined destination comprising:
- at a network node, for the destination, storing a function mapping inputs of the network node to outputs of the network node, some of which are used as alternates to reach the destination;
- and
- forwarding the data packet arriving to the network node from the inputs to the outputs according to the mapping function.
A router comprising:
- stored primary neighbor node data indicating next-hops to which data packets are primarily forwarded toward destinations;
- and
- stored alternate neighbor node data indicating next-hops to which the router forwards U-turn data packets.
A router comprising:
- means for storing next-hops to an alternate neighbor node at a network node;
- and
- means for forwarding a U-turn data packet to one of the alternate neighbor nodes associated with the primary neighbor from which that U-turn data packet was received by the network node.
A router comprising:
- means for storing a function mapping unicast inputs of the network node to unicast outputs of the network node for a globally defined destination, some of which are used as alternates to reach the destination;
- and
- means for forwarding the data packet arriving to the network node from the inputs from the outputs according to the mapping function
A method of forwarding data packets comprising:
- at a network node storing links to primary neighbor nodes and forwarding data packets to primary paths through primary neighbor nodes;
- upon failure of a primary path, forwarding data packets destined from the network node to the primary path to an alternate link to an alternate neighbor node;
- and
- upon receipt of a data packet through an alternate link at the alternate node, forwarding the data packet to an alternate link of the alternate neighbor node.
A router comprising:
- stored primary neighbor node data indicating next-hops to which data packets are primarily forwarded toward destinations;
- and
- stored alternate neighbor node data indicating next-hops to which the router forwards data packets upon failure of a primary next-hop data path;
- and
- alternate neighbor node data indicating next-hops to which the router forwards certain data packets received at the router as an alternate neighbor node.
A method of minimizing path values associated with paths in a network comprising:
- storing a data structure defining a network of nodes and links where the links have at least one weight between nodes;
- storing plural data sets, each data set corresponding to the paths that yield the solutions of a minimization function, and each element of the data set containing a path value that corresponds to the solution for a particular node of the network for that minimization function;
- and
- for the plural data sets, maintaining a common set of candidate nodes having path values to be inherited by other nodes;
- and
- successively selecting nodes from the set of candidate nodes and computing path values of nodes neighboring the selected nodes from path values of the selected nodes and weight values from functions of the traversed links;
- and
- updating any path value which has been further reduced for a node neighboring the selected node and then adding that node to the common set of candidate nodes if that node is not already in that set.
Dependencies are inferred from the claim text.