Multicast routing cache

• US 6,795,433 B1
• Filed: 10/21/1999
• Issued: 09/21/2004
• Est. Priority Date: 10/21/1999
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Li, Yunzhou
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): SHAH, CHIRAG G
• Application Number:
  US09/422,702
• Time in Patent Office: 1,797 Days
• Field of Search: 370/389, 370/390, 370/392, 370/431, 370/432, 370/464, 370/465, 370/471, 370/393
• US Class Current: 370/389
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast

Abstract

A method of processing a multicast packet that includes determining whether a first forwarding cache that stores forwarding information for ranges of addresses includes a cache entry covering the source address, and, if the first forwarding cache includes the such an entry, adding an entry to a second forwarding cache for the specific source address and group of the packet using the forwarding information associated with the first cache entry.

Claims

1. A method or processing a multicast packer being sent from a

multicast source address to members of a multicast group, the method comprising:

forwarding the multicast packet to an interface indicated in a forwarding cache entry associated with the multicast source address of the packet, the interface being pre-calculated according to a routing protocol;

responsive to a determination that the forwarding cache does not include an entry associated with the multicast source address, determining whether a protocol cache that stores interface information for ranges of addresses includes an entry for a range of addresses that includes the multicast source address;

if the protocol cache includes the entry, adding the interface information indicated in the entry to forwarding cache for the specific multicast source address and multicast group of the multicast packet.

2. The method of claim 1, further comprising adding an interface entry in the protocol cache for the range of addresses that includes the multicast source address of the packet upon a determination that the protocol cache does not include the entry.

3. The method of claim 2, wherein the step of adding comprises using a multicast protocol routing algorithm to determine the interface entry for the range of address.

4. The method of claim 3, wherein the multicast protocol comprises one of the following:

MOSPF (Multicast Open Short Path First), DVMRP (Distance Vector Multicast Routing Protocol), and PIM-DM (Protocol Independent Multicasting—

Dense Mode).

5. The method of claim 2, wherein the step of adding an interface entry in the protocol cache comprises determining a range of source addresses in a table of multicast source addresses that include the multicast source address of the packet.

6. The method of claim 5, wherein the range of source addresses comprises a most specific range of source addresses including the multicast source address of the packet.

7. The method of claim 1, wherein the multicast source address comprises an Internet Protocol (IP) address.

8. The method of claim 1, wherein the address ranges of the protocol cache comprise nested address ranges.

9. A method of updating a first entry in a forwarding cache that stores forwarding information for multicast source address, multicast group pairs, in response to receipt of a multicast packet having a multicast source address, multicast group address pair with no corresponding entry in the forwarding cache, the method comprising:

selecting a second entry in a protocol cache that stores forwarding information for ranges of multicast source addresses, the range of addresses of the selected second entry including the multicast source address; and

replacing the forwarding information for the first entry in the forwarding cache with forwarding information associated with the selected second entry in the protocol cache.

10. The method of claim 9, wherein the forwarding information comprises identification of one or more outgoing interfaces and one or more incoming interfaces.

11. The method of claim 9, further comprising determining forwarding information for the entries in the protocol cache using a multicast protocol routing algorithm.

12. A router having a memory that stores one or more data structures for use in routing multicast network packets from a multicast source to a multicast group, comprising:

a forwarding cache that stores forwarding information for particular ranges of multicast source addresses associated with different groups;

a protocol forwarding cache that stores forwarding information for nested ranges of multicast source addresses; and

means for accessing the protocol cache to retrieve forwarding information for a multicast source addresses associated with a group, when forwarding information for a range of multicast source addresses associated with the group is not stored in the forwarding cache.

13. The memory of claim 12 wherein the forwarding information comprises at least one incoming interface and at least one outgoing interface associated with a range of addresses.

14. A computer program product, disposed on a computer readable medium, for processing a multicast packet being sent from a multicast source address to members of a multicast group, the program comprising instructions for causing a processor to:

determine whether a protocol cache that stores forwarding information for ranges of multicast source addresses includes a first entry for a range of multicast source addresses that includes the multicast source address; and

if the protocol cache includes the first entry, add an entry to a forwarding cache for the specific multicast source address and group of the packet using the forwarding information associated with the first forwarding cache entry.

15. The computer program of claim 14, further including instructions that cause a processor to add an entry in the protocol cache for a range of multicast source addresses that includes the multicast source address of the packet.

16. The computer program of claim 15, wherein the instructions that cause the processor to add an entry in the protocol cache comprise instructions that cause the processor to use a multicast protocol routing algorithm to determine forwarding information for the range of multicast source address.

17. The computer program of claim 15, wherein the instructions that cause a processor to add an entry in the protocol cache comprise instruction that cause a processor to determine a range of multicast source addresses in a table of multicast source addresses that include the multicast source address of the packet.

18. The computer program of claim 14, wherein the address ranges of the protocol comprise nested address ranges.

19. A computer program product, disposed on a computer readable medium, for updating an entry in a forwarding cache that stores forwarding information for multicast source address, multicast group pairs, in repsonse to receipt of a mulitcast packet having a multicast source address, mulitcast group address pair with no corresponding entry in the forwarding cache, the program comprising instructions for causing a processor to:

select an interface entry in a protocol cache that stores forwarding information for ranges of multicast source addresses, the range of multicast source addresses of the selected interface entry including the multicast source address; and

replace the forwarding information for the entry in the forwarding cache with forwarding information associated with the interface entry in the protocol cache.

20. A system for processing a multicast packet being sent from a multicast source address to members of a multicast group, the system comprising:

means for determining whether a protocol cache that stores interface information for ranges of multicast source addresses includes an interface entry for a range of multicast source addresses that includes the multicast source address; and

means for updating a forwarding cache by adding an entry for the specific multicast source address and multicast group of the packet using the interface information from the protocol cache if the protocol cache includes the interface entry, and otherwise calculating an interface for the multicast source address, and updating the protocol and forwarding cache with the calculated interface.