Equal cost multi-path with bit indexed explicit replication

A node comprising:

• a memory for storing a plurality of sets of bit masks, wherein each set of the plurality can be used to forward a packet through a respective neighbor node towards one of a plurality of egress nodes, wherein each of the sets comprises M bit masks, wherein M is an integer greater than one, wherein each of the bit masks in each of the sets comprises N bits, wherein N is an integer greater than one, and wherein N and M are different;
• a network interface configured to receive a packet, wherein the packet comprises a bit string of N bits and a flow value, wherein each bit position of the bit string corresponds to a respective egress node;
• and
• a processor configured for:
• selecting a first set of bit masks from the plurality of sets of bit masks, wherein the selecting is based on the flow value;
• selecting a first bit mask from the first set;
• modifying the packet or a first copy of the packet to create a first modified packet, wherein modifying the packet or the first copy of the packet comprises modifying the bit string of the packet or the first copy of the packet based on the first bit mask;
• selecting a second bit mask from the first set;
• modifying the packet or a second copy of the packet to create a second modified packet, wherein modifying the packet or the second copy of the packet comprises modifying the bit string of the packet or the second copy of the packet based on the second bit mask;
• forwarding the first modified packet to a first neighbor node;
• forwarding the second modified packet to a second neighbor node;
• receiving an advertisement sent by an egress node, wherein the advertisement comprises an identifier of the egress node and a bit mask bit position assigned to the egress node;
• and
• generating or updating a bit routing table, wherein the generating or updating comprises using information from the advertisement to create an entry of the bit routing table, the entry comprising the identifier of the egress node, the bit mask bit position assigned to the egress node, and an identifier of an egress interface or neighbor node via which the egress node is reachable from the node.

A system comprising:

• a node comprising:
• storage means for storing a plurality of sets of masks, wherein each set of the plurality can be used to forward a packet through a respective neighbor node towards one of a plurality of egress nodes, wherein each of the sets comprises M bit masks, wherein M is an integer greater than one, wherein each of the bit masks in each of the sets comprises N bits, wherein N is an integer greater than one, and wherein M and N are different;
• network interface means for receiving a packet, wherein the packet comprises a bit string of N bits and a flow value, wherein each bit position of the bit string corresponds to a respective egress node;
• and
• processing means for:
• selecting a first set of bit masks from the plurality of sets of bit masks, wherein the selecting the first set of bit masks is based on the flow value;
• selecting a first bit mask from the first set;
• modifying the packet or a first copy of the packet to create a first modified packet, wherein modifying the packet or the first copy of the packet comprises modifying the bit string of the packet or the first copy of the packet based on the first bit mask;
• selecting a second bit mask from the first set;
• modifying the packet or a second copy of the packet to create a second modified packet, wherein modifying the packet or the second copy of the packet comprises modifying the bit string of the packet or the second copy of the packet based on the second bit mask;
• forwarding the first modified packet to a first neighbor node;
• forwarding the second modified packet to a second neighbor node;
• receiving an advertisement sent by an egress node of the network, wherein the advertisement comprises an identifier of the egress node and a bit mask bit position assigned to the egress node;
• and
• generating or updating a bit routing table at the node, wherein the generating or updating comprises using information from the advertisement to create an entry of the bit routing table, the entry comprising the identifier of the egress node, the bit mask bit position assigned to the egress node, and an identifier of an egress interface or neighbor node via which the egress node is reachable from the node.

A method comprising:

• a node determining first and second shortest paths of equal length between the node and a first egress node of a network, wherein the first egress node is one of a plurality of egress nodes in the network, wherein the network comprises the node;
• the node receiving a first packet, wherein the first packet comprises a first bit string of N bits and a first flow value, wherein bit positions of the first bit string correspond to the plurality of egress nodes, respectively;
• the node selecting a first set of bit masks from a plurality of sets of bit masks that are concurrently stored in memory of the node, wherein each set of the plurality can be used to forward a packet through a respective neighbor node towards the first egress node, wherein each of the sets comprises M bit masks, wherein M is an integer greater than one, wherein each of the bit masks in each of the sets comprises N bits, wherein the selecting is based on the first flow value;
• selecting a first bit mask from the first set;
• modifying the first packet or a copy of the first packet to create a modified first packet, wherein modifying the first packet or the copy of the first packet comprises modifying the first bit string of the first packet or the copy of the first packet based on the first bit mask;
• forwarding the modified first packet towards the first egress node via the first shortest path that comprises a first neighbor node;
• the node receiving a second packet, wherein the second packet comprises a second bit string of N bits and a second flow value, wherein bit positions of the second bit string correspond to the plurality of egress nodes, respectively;
• the node selecting a second set of bit masks from the plurality of sets of bit masks, based on the second flow value;
• selecting a second bit mask from the second set;
• modifying the second packet or a copy of the second packet to create a modified second packet, wherein modifying the second packet or the copy of the second packet comprises modifying the second bit string of the second packet or the copy of the second packet based on the second bit mask;
• forwarding the modified second packet towards the first egress node via the second shortest path that comprises a second neighbor node;
• receiving, at the node, an advertisement sent by an egress node of the network, wherein the advertisement comprises an identifier of the egress node and a bit mask bit position assigned to the egress node;
• and
• generating or updating a bit routing table at the node, wherein the generating or updating comprises using information from the advertisement to create an entry of the bit routing table, the entry comprising the identifier of the egress node, the bit mask bit position assigned to the egress node, and an identifier of an egress interface or neighbor node via which the egress node is reachable from the node.