Small group multicast in a computer network

• US 7,016,351 B1
• Filed: 02/29/2000
• Issued: 03/21/2006
• Est. Priority Date: 02/29/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Farinacci, Dino, Bion, Joel, Tweedly, Alex, Shand, Mike
• Primary Examiner(s): Nguyen, Brian
• Assistant Examiner(s): Phan, Tri H.
• Application Number:
  US09/515,295
• Time in Patent Office: 2,212 Days
• Field of Search: 370389-393, 370/396, 370399-401, 3703952-3953, 370/395.31, 370/312, 370/432
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

The invention solves the problem of overloading intermediate routers with state information as the number of multicast groups increases to millions of groups. The invention places multicast delivery tree information in the header of an encapsulated multicast packet, thereby relieving the routers from maintaining any state information about the multicast groups. The encapsulated packet is referred to as a small group multicast packet, or SGM packet. Routers which are neither branch points of the delivery tree nor destination routers will also need to do no additional forwarding processing other than that needed for standard unicast forwarding. A protocol designation field in the Layer 3 header informs the router that the packet is a SGM packet, and that the router is therefore instructed to parse the packet for route information. The router parses the SGM packet header and determines the next hop address of routers in the multicast delivery tree. The standard unicast forwarding tables are then consulted to determine the next packet destination addresses, and the router then rewrites the SGM packet and routes it to the next hop router. The routing tables also instruct the router as to which outbound port to route the packet.

Claims

1. A method of performing multicast transmission in a computer network, comprising:

receiving trace packets by a source router, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet;

receiving, by said source router, data packets transmitted by said multicast source end station;

transmitting by said source router small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets.

2. The method as in claim 1 wherein said receiving step further comprises:

detecting and receiving said data packets as multicast data packets transmitted by said multicast source end station.

3. The method as in claim 1 wherein said receiving step further comprises:

detecting and receiving said data packets as unicast data packets transmitted by said multicast source end station.

4. The method of claim 1 further comprising:

transmitting heartbeat packets by said source router along said multicast distribution tree in the event that no data packet is transmitted during a heartbeat timer time period, said heartbeat packet maintaining said multicast distribution tree active in the absence of data packets.

5. The method of claim 1 further comprising:

establishing heartbeat traffic between a destination router and said source router by said destination router unicasting an ICMP echo request packet to said multicast source end station, and receiving an ICMP echo response packet transmitted by said multicast source end station to said source router in response to said multicast source end station receiving said ICMP echo request packet from said destination router.

6. The method of claim 1 further comprising:

comparing, in a downstream router, a source address in a received SGM packet with a stored address of the correct source router;

transmitting a prune message to any source router whose address does not match said stored address of the correct source router.

7. The method of claim 1 further comprising:

inserting a pseudonode in a multicast distribution tree, in a layer 2 multicast capable LAN.

8. The method as in claim 1 further comprising:

inserting, in the event that said multicast source end station transmits multicast packets for a plurality of multicast groups, a list of groups in a trace packet in order to reduce the number of trace packets carried through the computer network.

9. The method as in claim 1 further comprising:

informing a destination router by a potential destination end station that said potential destination end station desires to receive a multicast group transmission from a particular source multicast end station by said destination end station using source filtering to inform said destination router of the destination end station address and multicast group number.

10. The method as in claim 1 further comprising:

informing a destination router by a potential destination end station that said potential destination end station desires to receive a multicast group transmission from a particular source multicast end station by said destination end station initiating a message received by said destination router.

11. The method as in claim 1 further comprising:

using multicast transmission by a source router for said source router to transfer heartbeat packets to destination routers.

12. A method of performing multicast transmission in a computer network, comprising:

receiving trace packets by a source router, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet;

receiving, by said source router, data packets transmitted by said multicast source end station;

transmitting by said source router small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets;

establishing said source router as separated from said multicast source end station by more than one router hop by a second router placing a data portion of a trace packet received by said second router into a data portion of an ICMP echo request packet having a destination address set to the group IP address, and a ICMP echo request identifier set to a protocol type assigned a SGM type;

receiving an ICMP echo response packet from said multicast source end station in response to receipt of said echo request packet by said multicast source end station; and

,

establishing, in response to receipt of said ICMP response packet by said second router, said second router as said source router.

13. The method as in claim 12 further comprising:

including in said echo request packet an identifier, and identifying said identifier in an echo response packet before establishing said second router as said source router.

14. A method of performing multicast transmission in a computer network, comprising:

receiving trace packets by a source router, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet;

receiving, by said source router, data packets transmitted by said multicast source end station;

transmitting by said source router small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets; and

setting a non-fragmentation bit in a trace packet so that a data portion of said SGM packet will not be separated from a SGM header portion of said trace packet by fragmentation.

15. A method of performing multicast transmission in a computer network, comprising:

receiving trace packets by a source router, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet;

receiving, by said source router, data packets transmitted by said multicast source end station;

transmitting by said source router small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets; and

transmitting a group membership notification (GMN) packet by a destination router containing a list of current group membership, said group membership including destination end stations receiving said multicast group transmissions, and placing only source information in trace packets and no group membership information in trace packets.

16. An apparatus to perform multicast transmission in a computer network, comprising:

means for receiving trace packets by a source router, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet;

means for receiving, by said source router, data packets transmitted by said multicast source end station;

means for transmitting by said source router small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets.

17. The apparatus of claim 16 wherein said means for receiving further comprise:

means for detecting and receiving said data packets as multicast data packets transmitted by said multicast source end station.

18. The apparatus of claim 16 wherein said means for receiving further comprise:

means for detecting and receiving said data packets as unicast data packets transmitted by said multicast source end station.

19. The apparatus of claim 16 further comprising:

means for transmitting heartbeat packets by said source router along said multicast distribution tree in the event that no data packet is transmitted during a heartbeat timer time period, said heartbeat packet maintaining said multicast distribution tree active in the absence of data packets.

20. The apparatus of claim 16 further comprising:

means for establishing heartbeat traffic between a destination router and said source router by said destination router unicasting an ICMP echo request packet to said multicast source end station, and receiving an ICMP echo response packet transmitted by said multicast source end station to said source router in response to said multicast source end station receiving said ICMP echo request packet from said destination router.

21. The apparatus of claim 16 further comprising:

means for establishing said source router as separated from said multicast source end station by more than one router hop by a second router placing a data portion of a trace packet received by said second router into a data portion of an ICMP echo request packet having a destination address set to a group IP address, and a ICMP echo request identifier set to a protocol type assigned a SGM type;

means for receiving an ICMP echo response packet from said multicast source end station in response to receipt of said echo request packet by said multicast source end station; and

,

means for establishing, in response to receipt of said ICMP response packet by said second router, said second router as said source router.

22. The apparatus of claim 21 further comprising:

means for including in said echo request packet an identifier, and identifying said identifier in an echo response packet before establishing said second router as said source router.

23. The apparatus of claim 16 further comprising:

means for comparing, in a downstream router, a source address in a received SGM packet with a stored address of the correct source router;

means for transmitting a prune message to any source router whose address does not match said stored address of the correct source router.

24. The apparatus of claim 16 further comprising:

means for inserting a pseudonode in the multicast distribution tree, in a layer 2 multicast capable LAN.

25. The apparatus of claim 16 further comprising:

means for inserting, in the event that said multicast source end station transmits multicast packets for a plurality of multicast groups, a list of groups in a trace packet in order to reduce the number of trace packets carried through the computer network.

26. The apparatus of claim 16 further comprising:

means for setting a non-fragmentation bit in a trace packet so that a data portion of said SGM packet will not be separated from a SGM header portion of said trace packet by fragmentation.

27. The apparatus of claim 16 further comprising:

means for placing only source information in trace packets and no group membership information in trace packets.

28. The apparatus of claim 16 further comprising:

means for informing a destination router by a potential destination end station that said potential destination end station desires to receive a multicast group transmission from a particular source multicast end station by said destination end station using source filtering to inform said destination router of the destination end station address and multicast group number.

29. The apparatus of claim 16 further comprising:

means for informing a destination router by a potential destination end station that said potential destination end station desires to receive a multicast group transmission from a particular source multicast end station by said destination end station initiating a message received by said destination router.

30. The apparatus of claim 16 further comprising:

means for using multicast transmission by said source router for said source router to transfer heartbeat packets to destination routers.

31. A router to perform multicast transmission in a computer network, comprising:

a receiver to receive trace packets, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet, and to receive data packets transmitted by said multicast source end station;

a transmitter to transmit small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets.

32. A computer readable media, comprising:

said computer readable media having instructions for execution on a processor written thereon for,

receiving trace packets by a source router, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet;

receiving, by said source router, data packets transmitted by said multicast source end station;

transmitting by said source router small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets.

33. A computer network having electromagnetic signals propagating thereon, said electromagnetic signals carrying instructions which when executed by a processor cause the processor to perform the steps comprising:

receiving trace packets by a source router, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet;

receiving, by said source router, data packets transmitted by said multicast source end station;

transmitting by said source router small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets.

34. A method of performing multicast transmission in a computer network, comprising:

receiving trace packets by a source router, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet;

receiving, by said source router, data packets transmitted by said multicast source end station;

transmitting by said source router small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets; and

transmitting a group membership notification (GMN) packet by a destination router containing a list of current group membership, said group membership including destination end stations receiving said multicast group transmissions.

35. The router of claim 34 further comprising:

said receiver for receiving trace packets with only source information in said trace packets and no group membership information in said trace packets.

36. An apparatus to perform multicast transmission in a computer network, comprising:

means for receiving trace packets by a source router, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet;

means for receiving, by said source router, data packets transmitted by said multicast source end station;

means for transmitting by said source router small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets; and

means for transmitting a group membership notification (GMN) packet by a destination router containing a list of current group membership, said group membership including destination end stations receiving said multicast group transmissions.

37. A router to perform multicast transmission in a computer network, comprising:

a receiver to receive trace packets, said trace packets transmitted in response to an end station requesting to join a multicast group having a multicast source end station, said trace packets containing an address list of intermediate routers which routed said trace packet, and to receive data packets transmitted by said multicast source end station;

said receiver also to receive group membership notification (GMN) packets from a destination router, said GMN packets containing a list of current group membership, said group membership including destination end stations receiving said multicast group transmissions; and

a transmitter to transmit small group multicast packets (SGM packets) having a multicast distribution tree written into a header of said SGM packets, said multicast distribution tree constructed by said source router in response to said address list contained in said trace packets, and said SGM packets containing in a data field, data read from said data packets.