Bridging of non-capable subnetworks in bit indexed explicit replication

1. A method, comprising:

receiving, from a next-hop upstream node configured for bit indexed forwarding, an incoming tree descriptor message comprising a tree identifier and a descriptor bit array, wherein

each of a plurality of network destination nodes is represented by a relative bit position within the descriptor bit array,

bit values in the descriptor bit array identify intended destination nodes, from among a plurality of network destination nodes, to be reached via a network tree identified by the tree identifier, and

the network tree connects the next-hop upstream node to one or more downstream nodes configured for bit-indexed forwarding;

replicating and modifying the incoming tree descriptor message to generate an outgoing tree descriptor message for a next-hop downstream node within the network tree, wherein the outgoing tree descriptor message comprises the tree identifier and describes a portion of the network tree rooted at the next-hop downstream node;

sending the outgoing tree descriptor message to the next-hop downstream node; and

sending to the next-hop upstream node a local label allocated to the tree identifier.

2. The method of claim 1 , further comprising:

receiving from the next-hop downstream node a remote label associated by the next-hop downstream node with the tree identifier; and

storing the remote label in a forwarding table for use in label-switched forwarding, to the next-hop downstream node, of an incoming data message carrying the local label.

3. The method of claim 1 , wherein

the outgoing tree descriptor message further comprises an outgoing descriptor bit array in place of the descriptor bit array;

bit values in the outgoing descriptor bit array identify a subset of the intended destination nodes; and

the subset of the intended destination nodes comprises the intended destination nodes reachable via and allocated to the portion of the network tree rooted at the next-hop downstream node.

4. The method of claim 3 , further comprising:

accessing the descriptor bit array; and

using a stored bit indexed routing table to determine the subset of the intended destination nodes.

5. The method of claim 1 , wherein

the incoming tree descriptor message further comprises an incoming explicit route object and a payload object;

the tree identifier is associated with a point-to-multipoint label-switched path;

the incoming explicit route object encodes a path, within the label-switched path, including the next-hop downstream node; and

the descriptor bit array is within the payload object.

6. The method of claim 5 , wherein

the outgoing tree descriptor message comprises an outgoing explicit route object; and

the outgoing explicit route object encodes a portion, of the path encoded by the incoming explicit route object, that is rooted at the next-hop downstream node.

7. The method of claim 1 , wherein receiving the incoming tree descriptor message comprises receiving the incoming tree descriptor message at a node not configured for bit indexed forwarding.

8. A network device, comprising:

a network interface; and

a processor operably coupled to the network interface and adapted to

receive, from a next-hop upstream node configured for bit indexed forwarding, an incoming tree descriptor message comprising a tree identifier and a descriptor bit array, wherein

each of a plurality of network destination nodes is represented by a relative bit position within the descriptor bit array,

bit values in the descriptor bit array identify intended destination nodes, from among a plurality of network destination nodes, to be reached via a network tree identified by the tree identifier, and

the network tree connects the next-hop upstream node to one or more downstream nodes configured for bit-indexed forwarding,

replicate and modify the incoming tree descriptor message to generate an outgoing tree descriptor message for a next-hop downstream node within the network tree, wherein the outgoing tree descriptor message comprises the tree identifier and describes a portion of the network tree rooted at the next-hop downstream node,

send the outgoing tree descriptor message to the next-hop downstream node, and

send to the next-hop upstream node a local label allocated to the tree identifier.

9. The network device of claim 8 , wherein the processor is further adapted to

receive from the next-hop downstream node a remote label associated by the next-hop downstream node with the tree identifier; and

store the remote label in a forwarding table for use in label-switched forwarding, to the next-hop downstream node, of an incoming data message carrying the local label.

10. The network device of claim 8 , wherein

the outgoing tree descriptor message further comprises an outgoing descriptor bit array in place of the descriptor bit array;

bit values in the outgoing descriptor bit array identify a subset of the intended destination nodes; and

the subset of the intended destination nodes comprises the intended destination nodes reachable via and allocated to the portion of the network tree rooted at the next-hop downstream node.

11. The network device of claim 10 , wherein the processor is further adapted to

access the descriptor bit array; and

use a stored bit indexed routing table to determine the subset of the intended destination nodes.

12. The network device of claim 8 , wherein

the incoming tree descriptor message further comprises an incoming explicit route object and a payload object;

the tree identifier is associated with a point-to-multipoint label-switched path;

the incoming explicit route object encodes a path, within the label-switched path, including the next-hop downstream node; and

the descriptor bit array is within the payload object.

13. The network device of claim 12 , wherein

the outgoing tree descriptor message comprises an outgoing explicit route object; and

the outgoing explicit route object encodes a portion, of the path encoded by the incoming explicit route object, that is rooted at the next-hop downstream node.

14. The network device of claim 8 , wherein the network device implements a network node not configured for bit indexed forwarding.

15. A non-transitory computer readable medium comprising computer readable instructions executable to:

receive, from a next-hop upstream node configured for bit indexed forwarding, an incoming tree descriptor message comprising a tree identifier and a descriptor bit array, wherein

each of a plurality of network destination nodes is represented by a relative bit position within the descriptor bit array,

bit values in the descriptor bit array identify intended destination nodes, from among a plurality of network destination nodes, to be reached via a network tree identified by the tree identifier, and

the network tree connects the next-hop upstream node to one or more downstream nodes configured for bit-indexed forwarding;

replicate and modify the incoming tree descriptor message to generate an outgoing tree descriptor message for a next-hop downstream node within the network tree, wherein the outgoing tree descriptor message comprises the tree identifier and describes a portion of the network tree rooted at the next-hop downstream node;

send the outgoing tree descriptor message to the next-hop downstream node; and

send to the next-hop upstream node a local label allocated to the tree identifier.

16. The non-transitory computer readable medium of claim 15 ,

wherein the instructions are further executable to:

receive from the next-hop downstream node a remote label associated by the next-hop downstream node with the tree identifier; and

store the remote label in a forwarding table for use in label-switched forwarding, to the next-hop downstream node, of an incoming data message carrying the local label.

17. The non-transitory computer readable medium of claim 15 ,

wherein

the outgoing tree descriptor message further comprises an outgoing descriptor bit array in place of the descriptor bit array;

bit values in the outgoing descriptor bit array identify a subset of the intended destination nodes; and

the subset of the intended destination nodes comprises the intended destination nodes reachable via and allocated to the portion of the network tree rooted at the next-hop downstream node.

18. The non-transitory computer readable medium of claim 17 ,

wherein the instructions are further executable to:

access the descriptor bit array; and

use a stored bit indexed routing table to determine the subset of the intended destination nodes.

19. The non-transitory computer readable medium of claim 15 ,

wherein

the incoming tree descriptor message further comprises an incoming explicit route object and a payload object;

the tree identifier is associated with a point-to-multipoint label-switched path;

the incoming explicit route object encodes a path, within the label-switched path, including the next-hop downstream node; and

the descriptor bit array is within the payload object.

20. The non-transitory computer readable medium of claim 19 ,

wherein

the outgoing tree descriptor message comprises an outgoing explicit route object; and

the outgoing explicit route object encodes a portion, of the path encoded by the incoming explicit route object, that is rooted at the next-hop downstream node.