Efficient programming of multicast routes in forwarding hardware

Patent metadata

Field	Value
Publication number	US-12452096-B2
Application number	US-202318117868-A
Country	US
Kind code	B2
Filing date	Mar 6, 2023
Priority date	Mar 6, 2023
Publication date	Oct 21, 2025
Grant date	Oct 21, 2025

Abstract

A system for facilitating efficient multicast programming in a switch is provided. During operation, the system can parse a multicast data structure that can map an ingress interface, a source, and a multicast group to a set of egress interfaces. Based on the data structure, the system can generate a cache that can map an egress interface to an ingress interface indicated in the data structure. Upon receiving a join request via a first interface, the system can look up the first interface in the cache. If the first interface matches a cache entry, the system can identify an ingress interface from the cache entry. The system can then program, in the data structure, a route entry with the first interface as an egress interface and the ingress interface. Subsequently, if a multicast data packet matches the route entry, the system can forward the packet via the first interface.

First claim

What is claimed is:

1. A method, comprising:
parsing, by a switch, a local multicast routing data structure, wherein a respective entry of the multicast routing data structure maps a combination of an ingress interface, a source, and a multicast group to a set of egress interfaces;
generating a multicast cache based on the multicast routing data structure, wherein a respective entry of the multicast cache maps an egress interface to an ingress interface indicated in the multicast routing data structure;
in response to receiving a first join request for a first multicast group via a first interface, looking up the first interface in the multicast cache;
in response to the first interface matching a cache entry in the multicast cache, identifying an ingress interface corresponding to the first interface from the cache entry of the multicast cache;
programming, in the multicast routing data structure for the first multicast group, a first route entry with the first interface as an egress interface and the identified ingress interface; and
in response to a multicast data packet matching the first route entry, forwarding the multicast data packet via the first interface.

2. The method of claim 1 , wherein, in response to the first interface not matching an entry in the multicast cache, the method further comprises:
forwarding the first join request to a rendezvous point (RP) for the first multicast group; and
refraining from generating the cache entry.

3. The method of claim 1 , wherein the multicast routing data structure is maintained in forwarding hardware of the switch, and wherein the multicast cache is maintained in a piece of software of the switch.

4. The method of claim 1 , wherein, in response to the multicast data packet not matching the first route entry, the method further comprises promoting the multicast data packet to a multicast daemon of the switch.

5. The method of claim 4 , further comprising timing out the first entry from the multicast routing data structure.

6. The method of claim 1 , wherein a respective entry in the multicast cache includes a count value of a number of times the identified ingress interface is included in the multicast routing data structure in association with the first interface.

7. The method of claim 6 , wherein the first interface matching the cache entry in the multicast cache further comprises:
identifying, in the multicast cache, a plurality of entries associated with the first interface; and
selecting the cache entry from the plurality of entries based on respective count values.

8. The method of claim 6 , further comprising updating a count value of the cache entry.

9. The method of claim 1 , wherein, in response to identifying a source of a second multicast group, the method further comprises programming, in the multicast routing data structure for the second multicast group, a second route entry with a second interface associated with a shortest-path to the source prior to receiving a data packet from the source.

10. The method of claim 1 , further comprising sending a join request to a source of a multicast group prior to receiving a data packet from the source.

11. A non-transitory computer-readable storage medium storing instructions that when executed by a computing system cause the computing system to perform a method, the method comprising:
parsing, by the computing system, a local multicast routing data structure, wherein a respective entry of the multicast routing data structure maps a combination of an ingress interface, a source, and a multicast group to a set of egress interfaces;
generating a multicast cache based on the multicast routing data structure, wherein a respective entry of the multicast cache maps an egress interface to an ingress interface indicated in the multicast routing data structure;
in response to receiving a first join request for a first multicast group via a first interface, looking up the first interface in the multicast cache;
in response to the first interface matching a cache entry in the multicast cache, identifying an ingress interface corresponding to the first interface from the cache entry of the multicast cache;
programming, in the multicast routing data structure for the first multicast group, a first route entry with the first interface as an egress interface and the identified ingress interface; and
in response to a multicast data packet matching the first route entry, forwarding the multicast data packet via the first interface.

12. The non-transitory computer-readable storage medium of claim 11 , wherein, in response to the first interface not matching an entry in the multicast cache, the method further comprises:
forwarding the first join request to a rendezvous point (RP) for the first multicast group; and
refraining from generating the cache entry.

13. The non-transitory computer-readable storage medium of claim 11 , wherein the multicast routing data structure is maintained in forwarding hardware of the computing system, and wherein the multicast cache is maintained in a piece of software running on the computing system.

14. The non-transitory computer-readable storage medium of claim 11 , wherein, in response to the multicast data packet not matching the first route entry, the method further comprises promoting the multicast data packet to a multicast daemon of the switch.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the method further comprises timing out the first entry from the multicast routing data structure.

16. The non-transitory computer-readable storage medium of claim 11 , wherein a respective entry in the multicast cache includes a count value of a number of times the identified ingress interface is included in the multicast routing data structure in association with the first interface.

17. The non-transitory computer-readable storage medium of claim 16 , wherein the first interface matching the cache entry in the multicast cache further comprises:
identifying, in the multicast cache, a plurality of entries associated with the first interface; and
selecting the cache entry from the plurality of entries based on respective count values.

18. The non-transitory computer-readable storage medium of claim 16 , wherein the method further comprises updating a count value of the cache entry.

19. The non-transitory computer-readable storage medium of claim 11 , wherein, in response to identifying a source of a second multicast group, the method further comprises programming, in the multicast routing data structure for the second multicast group, a second route entry with a second interface associated with a shortest-path to the source prior to receiving a data packet from the source.

20. A computer system, comprising:
processing circuitry;
forwarding hardware;
a caching logic block to:
parse a local multicast routing data structure, wherein a respective entry of the multicast routing data structure maps a combination of an ingress interface, a source, and a multicast group to a set of egress interfaces; and
generate a multicast cache based on the multicast routing data structure, wherein a respective entry of the multicast cache maps an egress interface to an ingress interface indicated in the multicast routing data structure;

a programming logic block:
in response to receiving a first join request for a first multicast group via a first interface, lookup the first interface in the multicast cache;
in response to the first interface matching a cache

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Nandy Tathagata
• Raj Anil
• Muthukumar Subramanian

Classifications

• H04L49/90 Primary

  Buffering arrangements · CPC title

• H04L45/16

  Multipoint routing · CPC title

• H04L12/185 Primary

  with management of multicast group membership · CPC title