Consolidation encodings representing designated receivers in a bit string

Patent metadata

Field	Value
Publication number	US-9712458-B2
Application number	US-201514684415-A
Country	US
Kind code	B2
Filing date	Apr 12, 2015
Priority date	Apr 12, 2015
Publication date	Jul 18, 2017
Grant date	Jul 18, 2017

Abstract

In one embodiment, for each particular multicast flow of a plurality of multicast flows of packets a particular consolidation encoding of a plurality of consolidation encodings is selected based on the sparseness of bit positions within a bit string corresponding to designated receiving packet switching devices of the particular multicast flow. The packet switching device sends one or more packets corresponding to said particular packet, with each of these one or more packets including designated receiving packet switching devices of the particular multicast flow in the header of said particular packet according to the particular consolidation encoding. In one embodiment, different consolidation encodings of the plurality of consolidation encodings are used for at least two different multicast flows of the plurality of multicast flows of packets. In one embodiment, each of said receiving packet switching devices is Bit Index Explicit Replication (BIER) Bit-Forwarding Router (BFR).

First claim

What is claimed is:

1. A method, comprising:
performing operations by a packet switching device, with said operations comprising for each particular multicast flow of a plurality of multicast flows of packets:
selecting a particular consolidation encoding of a plurality of consolidation encodings based on the sparseness of bit positions within a bit string corresponding to designated receiving packet switching devices of the particular multicast flow; and
sending, from the packet switching device, one or more packets corresponding to said particular packet, with each of these one or more packets including designated receiving packet switching devices of the particular multicast flow in the header of said particular packet according to the particular consolidation encoding.

2. The method of claim 1 , wherein different consolidation encodings of the plurality of consolidation encodings are used for at least two different multicast flows of the plurality of multicast flows of packets.

3. The method of claim 2 , wherein each of said two different consolidation encodings is a uniform consolidation encoding using a same manner of encoding portions of the bit string.

4. The method of claim 2 , wherein at least one of said two different consolidation encodings is a varying consolidation encoding using at least two different manners of encoding portions of the bit string.

5. The method of claim 1 , wherein each of said receiving packet switching devices is Bit Index Explicit Replication (BIER) Bit-Forwarding Router (BFR).

6. The method of claim 5 , wherein the packet switching device is a BIER edge packet switching device.

7. A method, comprising:
performing operations by a particular packet switching device, with said operations including:
receiving a particular packet including a bitmap designating a plurality of receiving packet switching devices in the header of the particular packet;
determining that the plurality of receiving packet switching devices are to be reached by at least two different next hop packet switching devices from the particular packet switching device; and
for each particular next hop packet switching device of said at least two different next hop packet switching devices, selecting a particular consolidation encoding of a plurality of consolidation encodings based on the sparseness of bit positions within a bit string corresponding to designated receiving packet switching devices to be reached via said particular next hop packet switching device, and sending a particular packet to said particular next hop packet switching device with the particular packet including said designated receiving packet switching devices to be reached via said particular next hop packet switching device in the header of said particular packet according to the particular consolidation encoding.

8. The method of claim 7 , wherein for at least one next hop packet switching device which is not a Bit Index Explicit Replication (BIER) Bit-Forwarding Router (BFR) of said at least two different next hop packet switching devices the operation of sending the particular packet includes encapsulating said particular packet and sending said encapsulated particular packet through a tunnel to one of said designated receiving packet switching devices.

9. The method of claim 7 , wherein different consolidation encodings of the plurality of consolidation encodings are used for at least two different multicast flows of the plurality of multicast flows of packets.

10. The method of claim 9 , wherein each of said two different consolidation encodings is a uniform consolidation encoding using a same manner of encoding portions of the bit string.

11. The method of claim 9 , wherein at least one of said two different consolidation encodings is a varying consolidation encoding using at least two different manners of encoding portions of the bit string.

12. The method of claim 7 , wherein each of said receiving packet switching devices is Bit Index Explicit Replication (BIER) Bit-Forwarding Router (BFR).

13. The method of claim 12 , wherein the packet switching device is a BIER edge packet switching device.

14. The method of claim 7 , wherein for at least one next hop packet switching device of said at least two different next hop packet switching devices the operation of sending the particular packet includes encapsulating said particular packet and sending said encapsulated particular packet through a tunnel to one of said designated receiving packet switching devices.

15. A packet switching device, comprising:
a plurality of interfaces configured to send and receive packets; and
one or more packet switching mechanisms configured to packet switch packets among said interfaces;
wherein the packet switching device is configured to perform operations, with said operations including for each particular multicast flow of a plurality of multicast flows of packets:
selecting a particular consolidation encoding of a plurality of consolidation encodings based on the sparseness of bit positions within a bit string corresponding to designated receiving packet switching devices of the particular multicast flow, and
sending, from the packet switching device, one or more packets corresponding to said particular packet, with each of these one or more packets including designated receiving packet switching devices of the particular multicast flow in the header of said particular packet according to the particular consolidation encoding.

16. The packet switching device of claim 15 , wherein different consolidation encodings of the plurality of consolidation encodings are used for at least two different multicast flows of the plurality of multicast flows of packets.

17. The packet switching device of claim 16 , wherein each of said two different consolidation encodings is a uniform consolidation encoding using a same manner of encoding portions of the bit string.

18. The packet switching device of claim 16 , wherein at least one of said two different consolidation encodings is a varying consolidation encoding using at least two different manners of encoding portions of the bit string.

19. The packet switching device of claim 15 , wherein each of said receiving packet switching devices is Bit Index Explicit Replication (BIER) Bit-Forwarding Router (BFR).

20. The packet switching device of claim 19 , wherein the packet switching device is a BIER edge packet switching device.

Assignees

• Wijnands Ijsbrand
• Shepherd Gregory J
• Ranns Neale David Raymond
• Bryant Stewart Frederick
• Cisco Tech Inc

Inventors

• Wijnands Ijsbrand
• Shepherd Gregory J
• Ranns Neale David Raymond
• Bryant Stewart Frederick

Classifications

• H04L49/201 Primary

  Multicast operation; Broadcast operation · CPC title