VC sharing for multicast in a computer network

• US 7,065,079 B1
• Filed: 05/04/2000
• Issued: 06/20/2006
• Est. Priority Date: 05/04/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Patra, Abhijit, Xu, Milton, Marimuthu, Peram, Wang, Jeffrey
• Primary Examiner(s): Pezzlo, John
• Application Number:
  US09/564,604
• Time in Patent Office: 2,238 Days
• Field of Search: 709/217, 709238-244, 709/236, 370/352, 370/355, 370/390, 370/432, 370/270, 370/256, 370/395.1, 370/395.2, 370/395.3, 370/395.31, 370/395.5, 370/389, 370/238, 370/238.1, 379/88.17
• US Class Current: 370/390
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM

Abstract

Only one point to multipoint virtual circuit (p2mp VC) is used within a router to handle all of the sources for a particular multicast group when other particulars of the multicast group are identical within that router. The router receiving a multicast packet for a particular multicast group identifies the source and the group number by reading fields of the incoming packet, identifies the input port of the router, and identifies the output port list. The input port of the router, the group number G, and the output port list are used by the router in establishing and identifying a point to multipoint VC within the router. The invention identifies all packets arriving at that particular input port, having the same multicast group number G, and having the same output port list, and transfers them to the identified VC. The VC is associated in the routing table with the output list of ports from which copies of the multicast packet are transmitted. Accordingly, only one VC is needed to transfer packets arising from any source of the multicast group so long as the multicast packets arrive on the same port of the router and have the same output port list.

Claims

1. A method for routing a multicast packet by a router, comprising:

receiving a multicast packet by a router at an input port;

reading a source end station address from the layer 3 field of said packet;

reading a multicast group number from the layer 3 address of said packet;

identifying an output port list in response to said source end station address and said multicast group number; and

selecting a point to multipoint virtual circuit that is internal to said router in response to said input port, said multicast group, and said output port list.

2. The method as in claim 1 further comprising:

receiving a second multicast packet with a different source end station address, said multicast group, and said output port list; and

selecting said point to multipoint virtual circuit.

3. The method of claim 1 further comprising:

transferring an identification of said point to multipoint virtual circuit to a line card to facilitate routing of said multicast packet.

4. A router for routing multicast packets, comprising:

means for receiving a multicast packet by a router at an input port;

means for reading a source end station address from the layer 3 field of said packet;

means for reading a multicast group number from the layer 3 address of said packet;

means for identifying an output port list in response to said source end station address and said multicast group number; and

means for selecting a point to multipoint virtual circuit that is internal to said router in response to said input port, said multicast group, and said output port list.

5. The router as in claim 4 further comprising:

means for reading said multicast group number from a layer 3 destination address field of said packet; and

means for reading said source end station address from a layer 3 source address field of said packet.

6. The router as in claim 4 further comprising:

means for transferring an identification of said point to multipoint virtual circuit to a line card to facilitate routing of said multicast packet.

7. A router for routing a multicast packet comprising:

a line card to receive said packet and to read a field indicating that said packet is a multicast packet, and in response to a determination that said packet is a multicast packet, to read a layer 3 source address as a multicast source station, and to read a layer 3 destination address as a multicast group number;

a first circuit to select an output port list in response to said source station and said multicast group;

a second circuit to select a point to multipoint virtual circuit that is internal to said router for routing said packet in response to said output port list and said multicast group; and

a replication mechanism to replicate said packet and to transmit said packet through ports listed in said output port list.

8. The router as in claim 7 wherein said first circuit, said second circuit, and said replication mechanism further comprise a central processor unit (CPU).

9. A computer readable media comprising:

said computer readable media having written thereon instructions for execution on a processor for practicing a method for routing a multicast packet by a router, the method having the steps of, receiving a multicast packet by a router at an input port;

reading a source end station address from the layer 3 field of said packet;

reading a multicast group number from the layer 3 address of said packet;

identifying an output port list in response to said source end station address and said multicast group number; and

selecting a point to multipoint virtual circuit that is internal to said router in response to said input port, said multicast group, and said output port list.

10. A method for routing a multicast packet by a router, comprising:

receiving said multicast packet by a router;

reading a source end station address from said packet;

reading a multicast group number from said packet;

identifying an output port list in response to said source end station address and said multicast group number; and

selecting a point to multipoint virtual circuit that is internal to said router in response to an input port, said multicast group, and said output port list, said point to multipoint virtual circuit routing the multicast packets from an input port to at least one output port.

11. The method as in claim 10, further comprising:

receiving a second multicast packet with a different source end station address, said multicast group, and said output port list; and

selecting said point to multipoint virtual circuit.

12. The method of claim 10, further comprising:

transferring an identification of said point to multipoint virtual circuit to a line card to facilitate routing of said multicast packet.

13. A computer readable media comprising:

said computer readable media having written thereon instructions for execution on a processor for practicing a method for routing a multicast packet by a router, the method having the steps of, receiving a multicast packet by a router at an input port;

receiving a multicast packet by a router;

reading a source end station address from said packet;

reading a multicast group number from said packet;

identifying an output port list in response to said source end station address and said multicast group number; and

selecting a point to multipoint virtual circuit that is internal to said router in response to an input port, said multicast group, and said output port list, said point to multipoint virtual circuit routing the multicast packets from an input port to at least one output port.

14. A router, comprising:

means for receiving a multicast packet by said router;

means for reading a source end station address from said packet;

means for reading a multicast group number from said packet;

means for identifying an output port list in response to said source end station address and said multicast group number; and

means for selecting a point to multipoint virtual circuit that is internal to said router in response to an input port, said multicast group, and said output port list, said point to multi-point virtual circuit routing the multicast packets from an input port to at least one output port.

15. The router as in claim 14, further comprising:

means for receiving a second multicast packet with a different source end station address, said multicast group, and said output port list; and

means for selecting said point to multipoint virtual circuit.

16. The router of claim 14, further comprising:

means for transferring an identification of said point to multipoint virtual circuit to a line card to facilitate routing of said multicast packet.

17. A router, comprising:

an I/O card to receive a multicast packet by said router;

a processor to read a source end station address from said packet, and to read a multi-cast group number from said packet; and

a CPU to identify an output port list in response to said source end station address and said multicast group number, and to select a point to multipoint virtual circuit that is internal to said router in response to an input port, said multicast group, and said output port list, said point to multipoint virtual circuit routing the multicast packets from an input port to at least one output port.

18. The router as in claim 17, further comprising:

said I/O card to receive a second multicast packet with a different source end station address, said multicast group, and said output port list; and

said CPU to select said point to multipoint virtual circuit.

19. The router of claim 17, further comprising:

said CPU to transfer an identification of said point to multipoint virtual circuit to a line card to facilitate routing of said multicast packet.

20. A method for routing a multicast packet by a router, comprising the steps of

receiving the multicast packet at an input port of a line card of the router, the packet having a source end station address;

determining an output port list for the multicast packet, the output port list including a plurality of output ports of the router on which the packet is to be forwarded;

if there is an existing point to multipoint virtual circuit beginning at the input port of the line card and terminating at the plurality of output ports, associating the multicast packet with the existing point to multipoint virtual circuit, regardless of the multicast packet'"'"'s source end station address; and

if there is not an existing point to multipoint virtual circuit beginning at the input port of the line card and terminating at the plurality of output ports, creating a new point to multi-point virtual circuit and associating the multicast packet with the new point to multipoint virtual circuit.

21. The method of claim 20 further comprising the step of:

incrementing a usage counter for the existing point to multipoint virtual circuit in response to associating the multicast packet with the existing point to multipoint virtual circuit.

22. The method of claim 20 further comprising the step of:

transferring an identification of the existing point to multipoint virtual circuit to the line card to facilitate routing of said multicast packet.

23. A router for routing a multicast packet comprising

a line card to receive a multicast packet having a source end station address;

a first circuit configured to determine an output port list for the multicast packet, the output port list including a plurality of output ports of the router on which the packet is to be forwarded; and

a second circuit configured to,

if there is an existing point to multipoint virtual circuit beginning at the input port of the line card and terminating at the plurality of output ports, associate the multicast packet with the existing point to multipoint virtual circuit, regardless of the multicast packet'"'"'s source end station address; and

if there is not an existing point to multipoint virtual circuit beginning at the input port of the line card and terminating at the plurality of output ports, create a new point to multipoint virtual circuit and associate the multi-cast packet with the new point to multipoint virtual circuit.

24. The router of claim 23 further comprising:

a usage counter for counting a number of multicast packets associated with the existing point to multipoint virtual circuit.

25. The router of claim 23 wherein said first circuit and said second circuit are a central processor unit (CPU).

26. A computer readable medium containing executable program instructions for routing a multicast packet, the executable program instructions comprising program instructions for:

receiving the multicast packet at an input port of a line card of the router, the packet having a source end station address;

determining an output port list for the multicast packet, the output port list including a plurality of output ports of the router on which the packet is to be forwarded;

if there is an existing point to multipoint virtual circuit beginning at the input port of the line card and terminating at the plurality of output ports, associating the multicast packet with the existing point to multipoint virtual circuit, regardless of the multicast packet'"'"'s 11 source end station address; and

if there is not an existing point to multipoint virtual circuit beginning at the input port of the line card and terminating at the plurality of output ports, creating a new point to multi-point virtual circuit and associating the multicast packet with the new point to multipoint virtual circuit.