Packet forwarding based on path encoding

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.

13. The apparatus of claim 12 , wherein, to associate the path encoding label for the network path with the packet, the processor is configured to:

add to the packet a header including the path encoding label.

14. The apparatus of claim 12 , wherein, to associate the path encoding label for the network path with the packet, the processor is configured to:

insert the path encoding label within one or more header fields of the packet.

15. The apparatus of claim 14 , wherein the one or more header fields of the packet comprise one or more address fields of the packet.

16. The apparatus of claim 14 , wherein the one or more header fields of the packet comprise a source address field of the packet and a destination address field of the packet.

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

18. The apparatus of claim 12 , wherein the apparatus comprises a set of network interfaces, wherein, to send the packet for propagation via the network path based on the path encoding label for the network path, the processor is configured to:

identify a portion of the path encoding label associated with the apparatus; and

forward the packet via one of the network interfaces based on the portion of the path encoding label associated with the apparatus.

19. The apparatus of claim 18 , wherein, to identify the portion of the path encoding label associated with the apparatus, the processor is configured to:

identify a portion of the path encoding label comprising offset information; and

identify the portion of the path encoding label associated with the apparatus based on the offset information.

20. The apparatus of claim 19 , wherein, to identify the portion of the path encoding label associated with the apparatus based on the offset information, the processor is configured to:

process the offset information to identify a bit position of the path encoding label that is storing a first bit of the portion of the path encoding label associated with the apparatus; and

identify, beginning with the first bit of the portion of the path encoding label associated with the apparatus, a longest prefix-free set of bits of the path encoding label.

21. The apparatus of claim 20 , wherein the processor is configured to:

prior to forwarding the packet toward a next node of the network path:

update the offset information to point to a first bit position of the path encoding label that is storing a first bit of a portion of the path encoding label that is associated with the next node of the network path.

22. The apparatus of claim 18 , wherein, to identify the portion of the path encoding label associated with the apparatus, the processor is configured to:

select a leftmost portion of the path encoding label associated with the apparatus that is prefix-free.

23. The apparatus of claim 22 , wherein the processor is configured to:

prior to forwarding the packet:

remove, from the packet, the leftmost prefix-free portion of the path encoding label associated with the apparatus; and

shift a remaining portion of the path encoding label to the left.

24. A method, comprising:

receiving, by a processor, 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;

determining, by the processor 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;

associating, by the processor, the path encoding label for the network path with the packet; and

sending, by the processor, the packet for propagation via the network path based on the path encoding label for the network path.