AUTOMATED DETERMINATION OF TREE ATTRIBUTES AND ASSIGNMENT OF RECEIVER IDENTIFIERS BY DISTRIBUTED ELECTION IN MULTICAST ARCHITECTURES RELYING ON PACKETS IDENTIFYING INTENDED RECEIVERS

• US 20160087890A1
• Filed: 12/22/2014
• Published: 03/24/2016
• Est. Priority Date: 09/19/2014
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Tantsura, Evgeny, Przygienda, Antoni
• Granted Patent: US 9,749,220 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 45/741 Routing in networks with a plurality of addressing schemes, e.g. with both IPv4 and IPv6

Abstract

Exemplary methods include a first network device participating in an election process to determine a designated bit forwarding router (D-BFR). The methods include in response to determining the first network device is elected to be the D-BFR, performing D-BFR operations comprising determining an elected bitmask (BM) length of a BM based on maximum local BM lengths advertised by other BFRs in the network, wherein each bit of the BM will correspond to a bit forwarding egress router (BFER), and advertising the determined elected BM length to other BFRs. The methods may further include one or more of determining an elected tree type based on supported tree types advertised by other BFRs in the network, assigning one or more BM positions (BMPs) to one or more BFERs, and advertising the elected determined tree type and/or the assigned one or more BMPs.

Claims

1. A method in a first network device (101) that is communicatively coupled to a plurality of other network devices (102-107) in a network, wherein each of the network devices is a bit forwarding router (BFR), the method comprising:

participating in an election process to determine a designated BFR (D-BFR); and

in response to determining the first network device is elected to be the D-BFR (101), performing D-BFR operations comprising;

determining an elected bitmask (BM) length (635, 640) of a BM based on maximum local BM lengths advertised by other BFRs (102-107) in the network, wherein each bit of the BM will correspond to a bit forwarding egress router(BFER) (105-107), and

advertising (645) the determined elected BM length to the other BFRs.

2. The method of claim 1, wherein performing D-BFR operations further comprises:

determining an elected tree type (720, 725, 730) based on supported tree types advertised by other BFRs in the network; and

advertising (735) the determined elected tree type to the other BFRs.

3. The method of claim 1, wherein performing D-BFR operations further comprises:

assigning (810) one or more BM positions (BMPs), each of the one or more BMPs assigned to a different BFER; and

advertising (820) the assigned one or more BMPs to the other BFRs.

4. The method of claim 1, wherein determining the elected BM length comprises:

receiving (605) a message from one or more of the other BFRs, each message including a maximum BM length supported by a BFR that sent the message;

determining (620) a minimum BM length of all the maximum BM lengths included in a received message; and

in response to determining the minimum BM length is not shorter than a previously elected BM length, setting (635) the elected BM length to be equal to the determined minimum BM length.

5. The method of claim 1, wherein determining the elected BM length comprises:

receiving (605) a message from one or more of the other BFRs, each message including a maximum BM length supported by a BFR that sent the message;

determining (620) a minimum BM length of all the maximum BM lengths included in a received message; and

in response to determining the minimum BM length is shorter than a previously elected BM length, setting (640) the elected BM length to be equal to the previously elected BM length.

6. The method of claim 2, wherein determining the elected tree type comprises:

receiving (705) a message from one or more of the other BFRs, each message including an indication of one or more tree types supported by a BFR that sent the message;

determining a tree type that is indicated as supported by one or more BFRs that sent a message; and

setting (720, 725, 730) the elected tree type to be the determined tree type that is indicated as supported by one or more BFRs that sent a message.

7. The method of claim 3, wherein assigning one or more BMPs comprises:

receiving (505) a message from a BFER, the message indicating a request for a BMP to be assigned to the BFER;

assigning (810) a BMP to the BFER; and

updating (815) BMP information to indicate the BMP has been assigned so that the BMP will not be assigned to another BFER.

8. The method of claim 7, wherein the message from the BFER further indicates a particular BMP that the BFER prefers.

9. The method of claim 8, wherein the message from the BFER further indicates that the BFER is willing to accept a BMP other than the particular BMP that the BFER prefers.

10. A first network device (101) that is communicatively coupled to a plurality of other network devices (102-107) in a network, wherein each of the network devices is a bit forwarding router (BFR), the first network device comprising:

a set of one or more processors; and

a non-transitory machine-readable storage medium containing code, which when executed by the set of one or more processors, cause the first network device to;

participate in an election process to determine a designated BFR (D-BFR), and

in response to determining the first network device is elected to be the D-BFR, perform D-BFR operations comprising;

determine an elected bitmask (BM) length (635, 640) of a BM based on maximum local BM lengths advertised by other BFRs (102-107) in the network, wherein each bit of the BM will correspond to a bit forwarding egress router (BFER) (105-107), and

advertise (645) the determined elected BM length to the other BFRs.

11. The first network device of claim 10, wherein performing D-BFR operations further comprises the first network device to:

determine an elected tree type (720, 725, 730) based on supported tree types advertised by other BFRs in the network; and

advertise (735) the determined elected tree type to the other BFRs.

12. The first network device of claim 10, wherein performing D-BFR operations further comprises the first network device to:

assign (810) one or more BM positions (BMPs), each of the one or more BMPs assigned to a different BFER; and

advertise (820) the assigned one or more BMPs to the other BFRs.

13. The first network device of claim 10, wherein determining the elected BM length comprises the first network device to:

receive (605) a message from one or more of the other BFRs, each message including a maximum BM length supported by a BFR that sent the message;

determine (620) a minimum BM length of all the maximum BM lengths included in a received message; and

in response to determining the minimum BM length is not shorter than a previously elected BM length, set (635) the elected BM length to be equal to the determined minimum BM length.

14. The first network device of claim 10, wherein determining the elected BM length comprises the first network device to:

receive (605) a message from one or more of the other BFRs, each message including a maximum BM length supported by a BFR that sent the message;

determine (620) a minimum BM length of all the maximum BM lengths included in a received message; and

in response to determining the minimum BM length is shorter than a previously elected BM length, set (640) the elected BM length to be equal to the previously elected BM length.

15. The first network device of claim 11, wherein determining the elected tree type comprises the first network device to:

receive (705) a message from one or more of the other BFRs, each message including an indication of one or more tree types supported by a BFR that sent the message;

determine a tree type that is indicated as supported by one or more BFRs that sent a message; and

set (720, 725, 730) the elected tree type to be the determined tree type that is indicated as supported by one or more BFRs that sent a message.

16. The first network device of claim 12, wherein assigning one or more BMPs comprises the first network device to:

receive (505) a message from a BFER, the message indicating a request for a BMP to be assigned to the BFER;

assign (810) a BMP to the BFER; and

update (815) BMP information to indicate the BMP has been assigned so that the BMP will not be assigned to another BFER.

17. The first network device of claim 16, wherein the message from the BFER further indicates a particular BMP that the BFER prefers.

18. The first network device of claim 17, wherein the message from the BFER further indicates that the BFER is willing to accept a BMP other than the BMP that the BFER prefers.

19. A non-transitory computer-readable storage medium having computer code stored therein, which when executed by a processor of a first network device that is communicatively coupled to a plurality of other network devices (102-107) in a network, wherein each of the network devices is a bit forwarding router (BFR), cause the first network device to perform operations comprising:

participating in an election process to determine a designated BFR (D-BFR); and

in response to determining the first network device is elected to be the D-BFR (101), performing D-BFR operations comprising;

determining an elected bitmask (BM) length (635, 640) of a BM based on maximum local BM lengths advertised by other BFRs (102-107) in the network, wherein each bit of the BM will correspond to a bit forwarding egress router (BFER) (105-107), and

advertising (645) the determined elected BM length to the other BFRs.

20. The non-transitory computer-readable storage medium of claim 19, wherein performing D-BFR operations further comprises:

determining an elected tree type (720, 725, 730) based on supported tree types advertised by other BFRs in the network; and

advertising (735) the determined elected tree type to the other BFRs.

21. The non-transitory computer-readable storage medium of claim 19, wherein performing D-BFR operations further comprises:

assigning (810) one or more BM positions (BMPs), each of the one or more BMPs assigned to a different BFER; and

advertising (820) the assigned one or more BMPs to the other BFRs.

22. The non-transitory computer-readable storage medium of claim 19, wherein determining the elected BM length comprises:

receiving (605) a message from one or more of the other BFRs, each message including a maximum BM length supported by a BFR that sent the message;

determining (620) a minimum BM length of all the maximum BM lengths included in a received message; and

in response to determining the minimum BM length is not shorter than a previously elected BM length, setting (635) the elected BM length to be equal to the determined minimum BM length.

23. The non-transitory computer-readable storage medium of claim 19, wherein determining the elected BM length comprises:

receiving (605) a message from one or more of the other BFRs, each message including a maximum BM length supported by a BFR that sent the message;

determining (620) a minimum BM length of all the maximum BM lengths included in a received message; and

in response to determining the minimum BM length is shorter than a previously elected BM length, setting (640) the elected BM length to be equal to the previously elected BM length.

24. The non-transitory computer-readable storage medium of claim 20, wherein determining the elected tree type comprises:

receiving (705) a message from one or more of the other BFRs, each message including an indication of one or more tree types supported by a BFR that sent the message;

determining a tree type that is indicated as supported by one or more BFRs that sent a message; and

setting (720, 725, 730) the elected tree type to be the determined tree type that is indicated as supported by one or more BFRs that sent a message.

25. The non-transitory computer-readable storage medium of claim 21, wherein assigning one or more BMPs comprises:

receiving (505) a message from a BFER, the message indicating a request for a BMP to be assigned to the BFER;

assigning (810) a BMP to the BFER; and

updating (815) BMP information to indicate the BMP has been assigned so that the BMP will not be assigned to another BFER.

26. The non-transitory computer-readable storage medium of claim 25, wherein the message from the BFER further indicates a particular BMP that the BFER prefers.

27. The non-transitory computer-readable storage medium of claim 26, wherein the message from the BFER further indicates that the BFER is willing to accept a BMP other than the particular BMP that the BFER prefers.