Overlay signaling for bit indexed explicit replication
Various systems and methods for performing bit indexed explicit replication (BIER). For example, one method involves receiving a membership message that was generated by an egress router, where the membership message comprises information identifying a multicast group, and information identifying a plurality of egress routers. The method identifies at least one bit position in the membership message that is associated with the first egress router, where at least one bit position of the plurality of bit positions is associated with the first egress router. The method also records membership of the first egress router in the multicast group, where the membership is recorded in a bit of a group membership table, and the bit corresponds to the bit position identified in the membership message.
1. A method comprising:
receiving a membership message, wherein
the membership message comprises
information identifying a multicast group, and
information identifying a plurality of egress routers,
the plurality of egress routers comprises a first egress router, and
the membership message was generated by the first egress router;
identifying at least one bit position in the membership message that is associated with the first egress router, wherein
identifying the at least one bit position comprises accessing the information identifying the plurality of egress routers,
the information identifying the plurality of egress routers comprises a bit string,
the bit string comprises a plurality of bits in a plurality of bit positions,
at least one bit position of the plurality of bit positions is associated with the first egress router; and
recording membership of the first egress router in the multicast group, wherein
the membership is recorded in a bit of a group membership table, and
the bit corresponds to the bit position identified in the membership message.
2. The method of claim 1 , wherein
the membership message identifies a multicast group, and
the multicast group comprises a plurality of transit nodes and the plurality of egress routers.
3. The method of claim 2 , further comprising:
parsing the membership message to identify the multicast group, wherein
the parsing comprises
identifying a multicast group address field, and
extracting a multicast group address from the multicast group address field.
4. The method of claim 2 , wherein
each bit position of the plurality of bit positions represents at least one of the plurality of egress routers without representing any of the plurality of transit nodes.
5. The method of claim 1 , wherein
the membership message was received by an overlay participant node.
6. The method of claim 5 , further comprising:
determining whether group membership information for the multicast group is already stored by the overlay participant node, wherein
the determining comprises querying the group membership table.
7. The method of claim 1 , wherein:
the bit string comprises a first subset of bits and a second subset of bits, wherein
the first subset of bits indicates a set to which the egress router belongs, and
the second subset of bits comprises the information identifying the plurality of egress routers.
8. The method of claim 1 , wherein:
at least one of the bit positions that represents the egress router was assigned based on an order in which the egress router joined the multicast group.
9. A network device comprising:
a memory storing instructions;
a network interface configured to receive a membership request from a host; and
a processor configured to execute the instructions to perform a method comprising:
receiving a membership message, wherein
the membership message comprises
information identifying a multicast group, and
information identifying a plurality of egress routers,
the plurality of egress routers comprises a first egress router, and
the membership message was generated by the first egress router;
identifying at least one bit position in the membership message that is associated with the first egress router, wherein
identifying at least one bit position comprises accessing the information identifying the plurality of egress routers,
the information identifying the plurality of egress routers comprises a bit string,
the bit string comprises a plurality of bits in a plurality of bit positions,
at least one bit position of the plurality of bit positions is associated with the first egress router; and
recording membership of the first egress router in the multicast group, wherein
the membership is recorded in a bit of a group membership table, and
the bit corresponds to the bit position identified in the membership message.
10. The network device of claim 9 , wherein
the membership message identifies a multicast group, and
the multicast group comprises a plurality of transit nodes and the plurality of egress routers.
11. The network device of claim 10 , wherein the method further comprises:
parsing the membership message to identify the multicast group, wherein
the parsing comprises
identifying a multicast group address field, and
extracting a multicast group address from the multicast group address field.
12. The network device of claim 10 , wherein
each bit position of the plurality of bit positions represents at least one of the plurality of egress routers without representing any of the plurality of transit nodes.
13. The network device of claim 9 , wherein
the membership message was received by an overlay participant node, and
at least one of the bit positions that represents the egress router was assigned based on an order in which the egress router joined the multicast group.
14. The network device of claim 13 , wherein the method further comprises:
determining whether group membership information for the multicast group is already stored by the overlay participant node, wherein
the determining comprises querying the group membership table.
15. The network device of claim 9 , wherein:
the bit string comprises a first subset of bits and a second subset of bits, wherein
the first subset of bits indicates a set to which the egress router belongs, and
the second subset of bits comprises the information identifying the plurality of egress routers.
16. A computer program product, comprising a plurality of instructions stored on a non-transient computer-readable storage medium, wherein the instructions are configured to execute a method comprising the steps of:
receiving a membership message, wherein
the membership message comprises
information identifying a multicast group, and
information identifying a plurality of egress routers,
the plurality of egress routers comprises a first egress router, and
the membership message was generated by the first egress router;
identifying at least one bit position in the membership message that is associated with the first egress router, wherein
identifying at least one bit position comprises accessing the information identifying the plurality of egress routers,
the information identifying the plurality of egress routers comprises a bit string,
the bit string comprises a plurality of bits in a plurality of bit positions,
at least one bit position of the plurality of bit positions is associated with the first egress router; and
recording membership of the first egress router in the multicast group, wherein
the membership is recorded in a bit of a group membership table, and
the bit corresponds to the bit position identified in the membership message.
17. The computer program product of claim 16 , wherein
the membership message identifies a multicast group,
the multicast group comprises a plurality of transit nodes and the plurality of egress routers, and
each bit position of the plurality of bit positions represents at least one of the plurality of egress routers without representing any of the plurality of transit nodes.
18. The computer program product of claim 17 , wherein the method further comprises:
parsing the membership message to identify the multicast group, wherein
the parsing comprises
identifying a multicast group address field, and
extracting a multicast group address from the multicast group address field.
19. The computer program product of claim 16 , wherein
the membership message was received by an overlay participant node,
at least one of the bit positions that represents the egress router was assigned based on an order in which the egress router joined the multicast group,
the bit string comprises a first subset of bits and a second subset of bits, wherein
the first subset of bits indicates a set to which the egress router belongs, and
the second subset of bits comprises the information identifying the plurality of egress routers.
20. The computer program product of claim 19 , wherein the method further comprises:
determining whether group membership information for the multicast group is already stored by the overlay participant node, wherein
the determining comprises querying the group membership table.