Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2000-04-07
2004-08-03
Harvey, Jack B. (Department: 2142)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C370S469000, C370S395500, C370S395520, C713S163000
Reexamination Certificate
active
06772222
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a multicast forwarding processor and, more particularly, to a processor which minimizes the software resource needed to process multicast protocol and broadcast protocol for bridges and routers in a network processor based environment.
2. Background Description
The problem of the design of computer networks is partitioned into smaller subtasks, by dividing the problem into layers. The OSI (Open Systems Interconnection) reference model defines seven layers. This invention is primarily concerned with the protocols of Layer 2, the data link layer, Layer 3, the network layer, and Layer 4, the transport layer. Each layer communicates with its peer layer in another node in the network through the use of a protocol. A multicast address is intended to be destined to a group of nodes, as opposed to a unicast address which is destined for a single node in the network.
While the Multicast Identifier (MID) is a well-known field regarding multicast flows, the definition of this term and how is used still needs to be properly introduced. An MID is simply a number that can be used to identify a grouping of logical or physical ports, or nodes, that need to receive a frame. This typically is done using a port vector mask in many multi-layer switches but, due to the large number of ports supported by large systems, the use of a port vector mask is impractical. For example, in some system chassis over 200 ports can exist. This would require a vector greater than 200 bits to be sent along with each frame as it traversed the switch internally. Also, multicast flows are broken down into ingress and egress processing in a network processor. During the ingress processing, the Network Processor (NP) needs to know “what target blades or Network Processor do I need to send this frame to?” On the egress side processing, the NP needs to know “what target ports do I need to send this frame to and how should I modify it?” Because of this the concept, a globally defined Multicast Identifier (MID) was introduced. Each MID is associated with a structure within the system that identifies a collection of blades, ports, and other attributes that affect the frame's forwarding.
On the ingress NP, the MID identifies a list of target NPs needed by the ingress NP to identify which of the NPs should receive a copy of this frame. Some products use hardware that replicates the frame by sending it out multiple switching fabric interfaces. Other products make use of the switching fabric subsystem for frame replication to each of the NPs. In either case, the frame replication performed by the hardware is transparent to the ingress NP.
On the egress NP, the MID directly or indirectly identifies the list of target ports needed by the egress side to forward the frame. On each egress NP the multicast list is simply turned into a series of unicast enqueues or dispatches to each of the ports. While the multicast is turned into a series of unicast enqueues an additional parameter is passed during the enqueue to assist the hardware in knowing when to release the buffer used for storing the frame. The hardware keeps a count of each of the enqueues and releases the memory used to store the frame during processing once all of the target ports have finished transmitting the frame.
In a Layer 2/3 switch, when a multicast frame is received on a given port, it may need to be both routed and bridged by the switch. All other ports within the source port's Virtual Local Area Network (VLAN) will need to receive an identical copy of the frame. However, if the frame is IPv4 (Internet Protocol version 4) for example, and also routed to another VLAN, the frame must be modified. Therefore, each NP needs to know the original VLAN the frame was received on as well as the source NP so it can determine how to process the frame. The MID by itself does not contain enough information. For this reason frames that are both bridged and routed must be identified by a unique frame header (FH).
It is worth noting that frame modification for multicast flows should not be done on the ingress and then removed on egress. While the operations performed for a protocol like IP are trivial the encapsulation of the frame itself may need to change for each VLAN. This would complicate the egress processing significantly.
Examples of users of multicast services for a multi-layer switch include:
Layer 2 Bridging, multicast frames need to be forwarded to all ports in a VLAN. Unicast frames whose destination address (DA) has not been learned need to be forwarded to all ports in a VLAN.
VLANs may construct multicast trees for different protocol based VLANs.
Layer 3 IPv4 multicast routing can be used for IPv4 to route frames to multiple VLANs.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a multicast processor which minimizes the software resource needed to process multicast protocol and broadcast protocol for bridges and routers in a network processor based environment.
According to the invention, there is provided a multicast forwarding processor which receives multicast and broadcast Layer 2/Layer 3/Layer 4 (L2/L3/L4) frames from a network processor. During reception, a frame layer flag, a unicast/multicast flag, and a frame position flag are set. A multitask forwarding table is accessed, and the frame, unicast/multicast, and frame position flags are stored and updated. The frame, unicast/multicast, and frame position flags are then sent to a frame forwarding processor. The L2/L3/L4 frames are routed to an L2 learning processor. The L2/L3/L4 frames are received from the frame forwarding processor, and the L2/L3/L4 frames are sent to an L3/L4 processor for frame header modification. The modified L2/L3/L4 frames are received from said L3/L4 processor, and the modified L2/L3/L4 frames are sent to an L2 filter processor.
REFERENCES:
patent: 5909686 (1999-06-01), Muller et al.
patent: 5938736 (1999-08-01), Muller et al.
patent: 6356951 (2002-03-01), Gentry, Jr.
Fast and scalable layer four switching, Srinivasan, V.; Varghese, G.; Suri, S.; Waldvogel, M., ACM SIGCOMM '98, ISSN: 0146-4833, pp. 191-202.*
Distributed core multicast (DCM): a multicast routing protocol for many groups with few receivers, Blazevi, L.; Le Boudec, J., ACM SIGCOMM, vol. 29, Oct. 1999, ISSN: 0146-4833, pp. 6-21.*
An architecture for wide-area multicast routing, Deering, et. al., Conference on Comm. architectures, protocols and application, London, 1994, ISBN: 0-89791-682-4, pp. 126-135.
Gallo Anthony Matteo
Rovner Sonia Kiang
Vaidhyanathan Natarajan
Woodland Gail Irene
Cockburn J.
Harvey Jack B.
McGuirewoods LLP
Prieto Beatriz
LandOfFree
Multicast forwarding table processor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multicast forwarding table processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicast forwarding table processor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3269297