Bit indexed explicit replication

Patent metadata

Field	Value
Publication number	US-9853822-B2
Application number	US-201414488761-A
Country	US
Kind code	B2
Filing date	Sep 17, 2014
Priority date	Sep 17, 2013
Publication date	Dec 26, 2017
Grant date	Dec 26, 2017

Abstract

Various systems and methods for performing bit indexed explicit replication (BIER). For example, one method involves receiving a packet at a node. The packet includes a multicast forwarding entry. The multicast forwarding entry has a plurality of elements, and each element corresponds to a particular node. The method also involves comparing the multicast forwarding entry with forwarding information stored by the node. The method involves selecting a neighbor node based on the comparing, updating the multicast forwarding entry in the packet, and forwarding the packet to the neighbor node.

First claim

What is claimed is:

1. A method comprising:
receiving, at a first node in a network, an advertisement sent by an egress node of the network, wherein the advertisement identifies the egress node and a bit position, within a bit mask comprising bits in a plurality of bit positions, assigned to the egress node;
generating or updating a bit routing table at the first node, wherein
the generating or updating comprises using information from the advertisement, and
an entry of the bit routing table comprises an identifier of the egress node, an identifier of the 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 first node;

receiving, at the first node, a data packet for transmission to one or more egress nodes of the network, wherein
the data packet comprises a multicast forwarding entry,
the multicast forwarding entry comprises the bit mask, and
each bit position of the plurality of bit positions corresponds to a single respective egress node of the network;

comparing the multicast forwarding entry with forwarding information stored by the first node;
selecting at least one neighbor node based on the comparing;
updating the multicast forwarding entry; and
forwarding a copy of the data packet comprising the updated multicast forwarding entry to the at least one neighbor node.

2. The method of claim 1 , wherein
the multicast forwarding entry comprises a set identifier, and
a value of the set identifier corresponds to a respective set of egress nodes represented by the bit positions of the plurality of bit positions.

3. The method of claim 1 , wherein
the updating the multicast forwarding entry comprises clearing a bit within the bit mask.

4. The method of claim 1 , wherein
the comparing comprises performing a logical AND operation between the multicast forwarding entry and a portion of the forwarding information.

5. The method of claim 1 , further comprising:
deriving a bit position within the bit mask from a routable address associated with a node.

6. The method of claim 1 , further comprising:
generating or updating a bit forwarding table comprising the forwarding information, wherein the generating or updating the bit forwarding table comprises using the bit routing table.

7. The method of claim 1 , wherein one or more egress nodes of the network is associated with a respective host computer or receiver.

8. The method of claim 1 , wherein receiving an advertisement comprises receiving an interior gateway protocol advertisement.

9. The method of claim 2 , wherein at least one bit position within the plurality of bit positions corresponds to different egress nodes for respective different values of the set identifier.

10. The method of claim 2 , wherein comparing the multicast forwarding entry with forwarding information comprises selecting a portion of the forwarding information corresponding to the value of the set identifier in the multicast forwarding entry.

11. A system comprising:
a first node configured to
receive an advertisement sent by an egress node of a network comprising the first node, wherein the advertisement identifies the egress node and a bit position, within a bit mask comprising bits in a plurality of bit positions, assigned to the egress node;
generate or update a bit routing table for the first node, wherein
the first node is configured to generate or update the bit routing table using information from the advertisement, and
an entry of the bit routing table comprises an identifier of the egress node, an identifier of the 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 first node;

receive a data packet for transmission to one or more egress nodes of the network, wherein
the data packet comprises a multicast forwarding entry,
the multicast forwarding entry comprises the bit mask, and
each bit position of the plurality of bit positions corresponds to a single respective egress node of the network;

compare the multicast forwarding entry with forwarding information stored by the first node;
select at least one neighbor node based on the comparing;
update the multicast forwarding entry; and
forward a copy of the data packet comprising the updated multicast forwarding entry to the at least one neighbor node.

12. The system of claim 11 , wherein
the multicast forwarding entry comprises a set identifier, and
a value of the set identifier corresponds to a respective set of egress nodes represented by the bit positions of the plurality of bit positions.

13. The system of claim 11 , wherein
updating the multicast forwarding entry comprises clearing a bit within the bit mask.

14. The system of claim 11 , wherein
comparing the multicast forwarding entry with forwarding information stored by the first node comprises performing a logical AND operation between the multicast forwarding entry and a portion of the forwarding information.

15. The system of claim 11 , wherein the first node is further configured to:
use the bit routing table to generate a bit forwarding table comprising the forwarding information.

16. The system of claim 11 , wherein the first node comprises a port processor adapted to receive the advertisement, receive the packet, and forward the packet.

17. The system of claim 16 , wherein the first node further comprises a processor adapted to:
generate or update the bit routing table;
compare the multicast forwarding entry with the forwarding information;
select the neighbor node; and
update the multicast forwarding entry.

18. The system of claim 11 , wherein the first node comprises memory adapted to store the bit routing table.

19. A non-transitory computer readable storage medium comprising executable instructions, wherein a method is implemented in response to executing the instructions, the method comprising:
receiving, at a first node in a network, an advertisement sent by an egress node of the network, wherein the advertisement identifies the egress node and a bit position, within a bit mask comprising bits in a plurality of bit positions, assigned to the egress node;
generating or updating a bit routing table at the first node, wherein
the generating or updating comprises using information from the advertisement, and
an entry of the bit routing table comprises an identifier of the egress node, an identifier of the 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 first node;

receiving, at the first node, a data packet for transmission to one or more egress nodes of the network, wherein
the data packet comprises a multicast forwarding entry,
the multicast forwarding entry comprises the bit mask, and
each bit position of the plurality of bit positions corresponds to a single respective egress node of the network;

comparing the multicast forwarding entry with forwarding information stored by the first node;
selecting at least one neighbor node based on the comparing;
updating the multicast forwarding entry; and
forwarding a copy of the data packet comprising the updated multicast forwarding entry to the at least one neighbor node.

20. The non-transitory computer readable storage medium of claim 19 , wherein
the multicast forwarding entry comprises a set identifier, and
a value of the set identifier corresponds

Assignees

• Cisco Tech Inc

Inventors

• Wijnands Ijsbrand
• Shepherd Gregory J
• Martin Christian

Classifications

• H04L45/50

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04L12/1886

  with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains · CPC title

• H04L45/18

  Loop-free operations · CPC title

• H04L45/16

  Multipoint routing · CPC title

• H04L12/18 Primary

  for broadcast or conference {, e.g. multicast} · CPC title