Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2000-07-25
2002-11-19
Rinehart, Mark H. (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C370S292000
Reexamination Certificate
active
06484209
ABSTRACT:
COPYRIGHT NOTICE
Contained herein is material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent disclosure by any person as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights to the copyright whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to the field of computer networking devices. More particularly, the invention relates to a method and apparatus for efficiently forwarding data, such as multicast data, from a source port to one or more destination ports of a networking device.
2. Description of the Related Art
Point-to-multipoint transmission is becoming increasingly important as the number of Internet and Local Area Network (LAN) applications that rely on multicast transmission continues to rise. As used herein “multicast” refers to the transmission of information to a group of recipients (e.g., a multicast group) via a single transmission by the source. Without multicast services, applications dependent upon such services would be forced to send information to groups of users with unicast packets. This means that a server, for instance, would have to send an individual copy of each data packet to all the users in an interest group (e.g., a Virtual LAN (VLAN), or other multicast group, such as an Internet Protocol (IP) multicast group). Unicasting to dispersed groups of users is inefficient for both the data source and the network, thus, network-based multicast services allow servers and other data sources to send out a single packet that is automatically copied and distributed by network devices, such as backbone routers or switches, to every endstation in the target group of users. Network devices that are configured to process multicast traffic typically maintain an internal mapping of multicast groups to member ports. In this manner, the network device can avoid unnecessary flooding of the data by forwarding multicast traffic only on those interfaces known to reach a member of the specified multicast group.
A prior approach for internally mapping multicast groups to interfaces having members is illustrated with reference to
FIG. 1. A
network device
100
includes a plurality of ports
105
-
108
, switching logic
115
, and a shared memory
110
. The switching logic
115
maintains one or more output queues
111
-
113
in the shared memory
110
for each of the plurality of ports
105
-
108
. The switching logic
115
determines with which output queues to associate received multicast data with reference to a multicast table
120
. The multicast table
120
maps multicast group identifiers to corresponding per port bit vectors that identify members of the multicast groups. A processor (not shown) within the network device
100
may execute one or more well known multicast protocols, such as a group membership protocol (e.g., Internet Group Management Protocol (IGMP)) and a multicast routing protocol (e.g., Multicast Open Shortest Path First (MOSPF), Distance Vector Multicast Routing Protocol (DVMRP), Protocol Independent Multicasting (PIM)), to facilitate initialization and maintenance of the multicast table
120
.
Because the switching logic
115
operates at a port level, a disadvantage of this prior approach is that the switching logic
115
must keep track of a substantial number of output queues in the shared memory
110
. Additionally, the switching logic
115
interfaces with each of the ports
105
-
108
. As a result, the switching logic
115
is complex and inefficient. Therefore, a more efficient mechanism for forwarding data through a networking device is needed.
BRIEF SUMMARY OF THE INVENTION
A method and apparatus for efficiently switching data through a switch fabric are described. According to one aspect of the present invention, logic for forwarding and filtering multicast data is distributed among various layers of a network device. Data is received at a first port of an input/output (I/O) card. A multicast group identifier corresponding to the data is determined. The data and the multicast group identifier are then transferred to a switching card which indexes into a fast set of correlation data with the multicast group identifier to identify a set of egress forwarding paths that lead to I/O cards having members of a multicast group corresponding to the multicast group identifier. The switching card forwards the data to the I/O cards via the set of egress forwarding paths identified. For their part, the I/O cards identify a set of ports associated with the multicast group by indexing into a second set of correlation data and forwarding the data to each of the ports identified. Advantageously, rather than tracking information for each port, the switching logic requires only general knowledge regarding which I/O cards have ports that are members of a multicast group, thereby offloading the switching logic and reducing the complexity of the switching logic.
According to another aspect of the present invention, a network device comprises a backplane, multiple I/O cards, and a switch core. Correlation data is distributed between the I/O cards and the switch core. The I/O cards each include multiple ports, a first set of correlation data, and a forwarding and filtering mechanism. The first set of correlation data maps multicast group identifiers to ports that are members of the corresponding multicast groups. The forwarding and filtering mechanism is configured to forward multicast data based upon the first set of correlation data. The switch core includes a second set of correlation data and a forwarding and filtering mechanism. The second set of correlation data maps multicast group identifiers to I/O cards that include one or more member ports. The switch core's forwarding and filtering mechanism is configured to forward multicast data to member I/O cards based upon the second set of correlation data.
Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.
REFERENCES:
patent: 5394402 (1995-02-01), Ross
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5742604 (1998-04-01), Edsall et al.
patent: 5796732 (1998-08-01), Mazzola et al.
patent: 5818838 (1998-10-01), Backes et al.
patent: 5822523 (1998-10-01), Rothschild et al.
patent: 5864535 (1999-01-01), Basilico
patent: 5898686 (1999-04-01), Virgile
patent: 5898687 (1999-04-01), Harriman et al.
patent: 5909438 (1999-06-01), Melden et al.
patent: 5917819 (1999-06-01), Yang et al.
patent: 5930259 (1999-07-01), Katsube et al.
patent: 5933425 (1999-08-01), Iwata
patent: 5951651 (1999-09-01), Lakshman et al.
patent: 5959989 (1999-09-01), Gleeson et al.
patent: 5991295 (1999-11-01), Tout et al.
patent: 5991297 (1999-11-01), Palnati et al.
patent: 5991298 (1999-11-01), Hunt et al.
patent: 5991302 (1999-11-01), Berl et al.
patent: 5999531 (1999-12-01), Ferolito et al.
patent: 6078595 (2000-06-01), Jones et al.
Blakely , Sokoloff, Taylor & Zafman LLP
Jaroenchonwanit Bunjob
Rinehart Mark H.
LandOfFree
Efficient path based forwarding and multicast forwarding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient path based forwarding and multicast forwarding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient path based forwarding and multicast forwarding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2948197