Packet forwarding based on path encoding

Patent metadata

Field	Value
Publication number	US-9992108-B2
Application number	US-201414337815-A
Country	US
Kind code	B2
Filing date	Jul 22, 2014
Priority date	Jul 22, 2014
Publication date	Jun 5, 2018
Grant date	Jun 5, 2018

Abstract

In general, a capability for forwarding packets based on path encoding is presented. The capability for forwarding a packet based on path encoding may be configured to enable forwarding of a packet along a network path by determining a path encoding label for the network path, associating the path encoding label for the network path with the packet, and forwarding the packet along the network path based on the path encoding label associated with the packet. The network path for a packet may include an ordered sequence of node output interfaces of an ordered sequence of nodes. The path encoding label for the network path includes an ordered sequence of node interface labels corresponding to the ordered sequence of node output interfaces of the nodes of the network path. The nodes of the network path forward the packet along the network path based on the path encoding label.

First claim

What is claimed is:

1. An apparatus, comprising:
a processor and a memory communicatively connected to the processor, the processor configured to:
determine a network path through a network, the network path comprising an ordered sequence of nodes of the network, the ordered sequence of nodes of the network path comprising an ordered sequence of three or more nodes of the network;
determine, for each of the nodes in the ordered sequence of nodes of the network path, a respective node output interface of the respective node that is to support the network path at the respective node;
determine, for each of the node output interfaces of each of the nodes in the ordered sequence of nodes of the network path, a respective node interface label representing the respective node output interface of the respective node in the ordered sequence of nodes of the network path; and
determine, based on the node interface labels representing the respective node output interfaces of the respective nodes in the ordered sequence of nodes of the network path, a path encoding label for the network path, the path encoding label for the network path comprising an ordered sequence of the node interface labels representing the respective node output interfaces of the respective nodes in the ordered sequence of nodes of the network path.

2. The apparatus of claim 1 , wherein, to determine the path encoding label for the network path, the processor is configured to:
concatenate the node interface labels representing the respective node output interfaces of the respective nodes in the ordered sequence of nodes of the network path, based on the ordered sequence of the node interface labels representing the respective node output interfaces of the respective nodes in the ordered sequence of nodes of the network path, to form the path encoding label.

3. The apparatus of claim 2 , wherein, to determine the respective node interface label representing the respective node output interface of the respective node in the ordered sequence of nodes of the network path, the processor is configured to:
determine the respective node with which the respective node output interface is associated;
determine an interface identifier of the respective node output interface; and
determine the respective node interface label for the respective node output interface based on a mapping of the interface identifier of the respective node output interface of the respective node to the respective node interface label for the respective node output interface of the respective node.

4. The apparatus of claim 1 , wherein the path encoding label further comprises offset information configured for use by the respective nodes of the network path in identifying portions of the path encoding label associated with the respective nodes of the network path.

5. The apparatus of claim 1 , wherein the processor is configured to:
generate a mapping of the network path to the path encoding label for the network path; and
propagate, toward a first node in the ordered sequence of nodes of the network path, the mapping of the network path to the path encoding label for the network path.

6. The apparatus of claim 1 , wherein the nodes of the network path include at least a portion of a set of available nodes of the network, wherein each of the available nodes in the set of available nodes of the network comprises a respective set of node output interfaces, wherein the processor is configured to:
generate respective node interface labels for the respective node output interfaces of the respective available nodes in the set of available nodes of the network.

7. The apparatus of claim 6 , wherein, for each of the available nodes in the set of available nodes of the network, the respective node interface labels for the node output interfaces of the respective available node are configured to be prefix-free.

8. The apparatus of claim 6 , wherein, to generate the respective node interface labels for the respective node output interfaces of the nodes in the set of available nodes of the network, the processor is configured to:
assign, to each of the respective node output interfaces of each of the available nodes in the set of available nodes of the network, a respective length function li; and
create the respective node interface labels for the respective node output interfaces of the available nodes in the set of available nodes of the network such that the node interface labels satisfy the respective length functions li and a sum of 2(−li) over the node output interfaces of the available nodes in the set of available nodes of the network is equal to or less than one (1).

9. The apparatus of claim 8 , wherein, to assign the respective length functions 2(−li) to the respective node output interfaces of the available nodes in the set of available nodes of the network, the processor is configured to:
formulate the assignment problem as a convex optimization problem;
determine a solution for the convex optimization problem; and
round the solution to satisfy integer constraints.

10. The apparatus of claim 1 , wherein the processor is configured to:
receive a packet to be forwarded via the network path; and
associate the path encoding label of the network path with the packet.

11. A method, comprising:
determining, by a processor, a network path through a network, the network path comprising an ordered sequence of nodes of the network, the ordered sequence of nodes of the network path comprising an ordered sequence of three or more nodes of the network;
determining, by the processor for each of the nodes in the ordered sequence of nodes of the network path, a respective node output interface of the respective node that is to support the network path at the respective node;
determining, by the processor for each of the node output interfaces of each of the nodes in the ordered sequence of nodes of the network path, a respective node interface label representing the respective node output interface of the respective node in the ordered sequence of nodes of the network path; and
determining, by the processor based on the node interface labels representing the respective node output interfaces of the respective nodes in the ordered sequence of nodes of the network path, a path encoding label for the network path, the path encoding label for the network path comprising an ordered sequence of the node interface labels representing the respective node output interfaces of the respective nodes in the ordered sequence of nodes of the network path.

12. An apparatus, comprising:
a processor and a memory communicatively connected to the processor, the processor configured to:
receive a packet to be routed via a network path through a network, the network path comprising an ordered sequence of nodes of the network, the ordered sequence of nodes of the network path comprising an ordered sequence of three or more nodes of the network, the network path comprising, for each of the nodes in the ordered sequence of nodes of the network path, a respective node output interface of the respective node that is to support the network path at the respective node;
determine, based on the packet, a path encoding label for the network path, the path encoding label for the network path comprising an ordered sequence of node interface labels representing the respective node output interfaces of the respective nodes of the ordered sequence of nodes of the network path;
associate the path encoding label for the network path with the packet; and
send the packet for propagation via the network path based on the path encoding label for the network path.

Assignees

• Hari Adiseshu
• Niesen Urs
• Wilfong Gordon
• Alcatel Lucent Usa Inc

Inventors

• Hari Adiseshu
• Niesen Urs
• Wilfong Gordon

Classifications

• H04W36/30

  by measured or perceived connection quality data · CPC title

• H04L45/74 Primary

  Address processing for routing · CPC title

• H04L45/64

  using an overlay routing layer · CPC title

• H04L47/34

  ensuring sequence integrity, e.g. using sequence numbers · CPC title