Method for handling IP multicast packets in network switch

• US 7,720,055 B2
• Filed: 03/09/2004
• Issued: 05/18/2010
• Est. Priority Date: 03/17/1999
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Ambe, Shekhar, Kadambi, Shiri
• Primary Examiner(s): Nguyen; Steven H
• Assistant Examiner(s): HAILE, AWET A
• Application Number:
  US10/795,259
• Publication Number:
  US 20040170176A1
• Time in Patent Office: 2,261 Days
• Field of Search: 370/351, 370/389, 370/390, 370/432, 370/468, 370/245, 370/398, 370/414, 370/401, 370/469, 709/238
• US Class Current: 370/389
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 12/46 Interconnection of networks
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 12/4645 Details on frame tagging routing of packets H04L45/00; support for virtual LAN H04L49/354
• CPC Class Codes: H04L 12/467 Arrangements for supporting untagged frames, e.g. port-based VLANs
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/286 Time to live
• CPC Class Codes: H04L 47/43 : Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 47/50 : Queue scheduling
• CPC Class Codes: H04L 47/6215 : Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 : Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 47/623 : Weighted service order
• CPC Class Codes: H04L 49/102 : using shared medium, e.g. bus or ring
• CPC Class Codes: H04L 49/109 : Integrated on microchip, e.g. switch-on-chip
• CPC Class Codes: H04L 49/201 : Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/208 : Port mirroring
• CPC Class Codes: H04L 49/254 : Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3054 : Auto-negotiation, e.g. access control between switch gigabit interface connector [GBIC] and link
• CPC Class Codes: H04L 49/3081 : ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/351 : for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/352 : Gigabit ethernet switching [GBPS]
• CPC Class Codes: H04L 49/354 : for supporting virtual local area networks [VLAN]
• CPC Class Codes: H04L 49/45 : Arrangements for providing or supporting expansion
• CPC Class Codes: H04L 49/602 : Multilayer or multiprotocol switching, e.g. IP switching
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 49/901 : using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9047 : including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9057 : Arrangements for supporting packet reassembly or resequencing
• CPC Class Codes: H04L 49/9073 : Early interruption upon arrival of a fraction of a packet
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/14 : Multichannel or multilink protocols
• CPC Class Codes: H04L 69/16 : Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 : Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields

Abstract

A method of switching packets in a network switch includes the step of receiving a packet on a source port of a network switch. Thereafter, the method includes the step of determining whether the network switch has sufficient memory capacity to process the data packet; and if memory capacity is sufficient, then the method reads a selected portion of the packet to determine if the packet is to be sent to a mirrored port. If mirroring is determined, then the method sends the data packet to the mirrored port. The method also includes the step of determining whether the packet is to be sent to a remote CPU for further handling, and sending the data packet to the remote CPU if appropriate. The method additionally includes the step of determining whether the packet is a unicast packet, and if so, placing the packet on an internal communication channel within the network switch for appropriate storing and forwarding. If the packet is not a unicast packet, then the method determines if the packet is a multicast packet. If the packet is determined to be a multicast packet, then performing simultaneous lookups and switching using layer 2 lookup tables and addresses, and layer 3 lookup tables and addresses, thereby providing hybrid multicast handling of the packet.

Claims

1. A method of switching packets in a network switch, said method comprising:

receiving, by the network switch, at least a first packet and a second packet, the first packet including a first packet address and the second packet including a second packet address, on a source port of the network switch;

performing concurrent lookups of the first packet address and the second packet address, wherein;

the lookup of the first packet address is performed on an odd layer 2 and layer 3 lookup table, the odd layer 2 and layer 3 lookup table including odd addressed entries of source or destination addresses; and

the lookup of the second packet address is performed on an even layer 2 and layer 3 lookup table, the even layer 2 and layer 3 lookup table including even addressed entries of source or destination addresses; and

the concurrent lookups determine at least one egress port through which each of the first and second packets are to be sent; and

sending the first and second packets through the determined at least one egress port, the at least one egress port being based on the concurrent lookups.

2. A method as recited in claim 1, further comprising:

determining if the first packet and second packet are to be sent to a mirrored port; and

if mirroring is determined, sending the first packet and second packet to the mirrored port.

3. A method as recited in claim 1, wherein the concurrent lookups include each of:

searching an IP multicast table to determine if a destination address is contained in the IP multicast table;

forwarding the packets to a remote CPU if the destination address is not contained in the IP multicast table;

comparing a time-to-live (TTL) value to a predetermined TTL threshold if the destination address is known;

sending the packets to the remote CPU if the time-to-live value is below the predetermined TTL threshold;

obtaining a layer 3 port bitmap from the IP multicast table if the time-to-live value is not below the predetermined TTL threshold;

switching the packets to destination ports if the destination ports on the layer 3 port bitmap are considered active ports for the network switch;

concurrently with the searching of the IP multicast table, examining port filtering bits of the module header to determine whether a first predetermined port filtering value is present;

forwarding the packets to a selected group of ports on the switch if the first predetermined port filtering value is present;

searching a multicast table using a destination key if the first predetermined filtering value is not present;

obtaining a port bitmap from the multicast table if searching the multicast table results in a match, then forwarding the data packets to ports obtained from the port bitmap;

if there is not a match, examining the port filtering bits to see if a second predetermined port filtering value is present;

if the second predetermined port filtering value is present, dropping the packets; and

if the second predetermined port filtering value is not present, obtaining a destination port bitmap from a VLAN table, and forwarding the data packets to ports identified in the destination port bitmap.

4. A method as recited in claim 3, wherein said destination key is formed by combining a destination address and a destination VLAN identification value from a field in the packets.

9. A method as recited in claim 1, wherein the concurrent lookups are performed by a single L2/L3 search engine.

11. The method of claim 1, wherein:

the lookup of the first packet address continues until either the first packet address is found in the odd layer 2 and layer 3 lookup table or the first packet address is determined to not be included in the odd layer 2 and layer 3 lookup table, and if the first packet address is determined not to be included in the odd layer 2 and layer 3 lookup table, the lookup of the first packet address includes either finding the first packet address in the even layer 2 and layer 3 lookup table or determining that the lookup of the first packet address is a miss; and

the lookup of the second packet address continues until either the second packet address is found in the even layer 2 and layer 3 lookup table or the second packet address is determined to not be included in the even layer 2 and layer 3 lookup table, and if the second packet address is determined not to be included in the even layer 2 and layer 3 lookup table, the lookup of the second packet address includes either finding the second packet address in the odd layer 2 and layer 3 lookup table or determining that the lookup of the second packet address is a miss.

12. The method of claim 1, wherein:

the first packet includes a first packet source address and a first packet destination address, and the second packet includes a second packet source address and a second packet destination address; and

the concurrent searches include a first alternating search performed concurrently with a second alternating search, wherein;

the first alternating search alternates between searching for the first packet source address and the first packet destination address in the odd layer 2 and layer 3 lookup table; and

the second alternating search alternates between searching for the second packet source address and the second packet destination address in the even layer 2 and layer 3 lookup table.

5. A network switch for switching packets, comprising:

a source port configured to receive at least a first packet and a second packet, the first packet including a first packet address and the second packet including a second address;

a first search engine configured to perform, concurrently with an even lookup by a second search engine, an odd lookup of the first packet address on an odd layer 2 and layer 3 lookup table, the odd layer 2 and layer 3 lookup table including odd addressed entries of source or destination addresses; and

the second search engine configured to perform, concurrently with the odd lookup by the first search engine, the even lookup of the second packet address on an even layer 2 and layer 3 lookup table, the even layer 2 and layer 3 table including even addressed entries of source or destination addresses; and

a handler configured to send the first and second packets through at least one egress port, the egress port being based on the concurrent lookups.

6. A network switch as recited in claim 5, further comprising:

a determiner configured to determine whether the first and second packets are to be sent to a mirrored port; and

a sender configured to send the first and second packets to the mirrored port when mirroring is determined.

7. A network switch as recited in claim 5, wherein the search engines include each of:

a first searcher configured to search an IP multicast table to determine if a destination address is contained in either the odd layer 2 and layer 3 lookup table or the even layer 2 and layer 3 lookup table;

a first forwarder configured to forward the first and second packets to a remote CPU if the destination address is not contained in the IP multicast table;

a comparator configured to compare a time-to-live (TTL) value to a predetermined TTL threshold if the destination address is known;

a sender configured to send the packets to the CPU if the time-to-live value is below the predetermined TTL threshold;

a first obtainer configured to obtain a layer 3 port bitmap from the IP multicast table if the time-to-live value is not below the predetermined TTL threshold;

a switch configured to switch the packets to the destination ports if ports on the layer 3 port bitmap are considered active ports for the network switch;

a first examiner configured to examine port filtering bits of the module header to determine whether a first predetermined port filtering value is present, wherein the first examiner is configured to operate simultaneously with the first searcher;

a second forwarder configured to forward the first and second packets to a selected group of ports on the switch if the first predetermined port filtering value is present;

a second searcher configured to search a multicast table using a destination key if the first predetermined filtering value is not present;

a second obtainer configured to search a port bitmap from the multicast table if searching the multicast table results in a match;

a third forwarder configured to forward the data packet to ports obtained from the port bitmap, when the second obtainer obtains the port bitmap from the multicast table;

a second examiner configured to examine the port filtering bits to see if a second predetermined port filtering value is present if there is not a match through the searching of the multicast table;

a dropper configured to drop the packet when the second predetermined port filtering value is present;

a third obtainer configured to obtain from a VLAN table a destination port bitmap when the second predetermined port filtering value is not present; and

a fourth forwarder configured to forward the data packets to ports identified in the destination port bitmap.

8. A network switch as recited in claim 7, wherein said second searcher is configured to use the destination key formed by combining a destination address and a destination VLAN identification value from a field in at least one of the first and second packets.

10. A network switch as recited in claim 5, wherein the search engines each include a single L2/L3 search engine configured to perform the simultaneous lookups.

13. A network switch as recited in claim 5, wherein:

the first search engine is configured to continue the odd lookup of the first packet address until either the first packet address is found in the odd layer 2 and layer 3 lookup table or the first packet address is determined to not be included in the odd layer 2 and layer 3 lookup table, and if the first packet address is determined not to be included in the odd layer 2 and layer 3 lookup table, the odd lookup of the first packet address includes either finding the first packet address in the even layer 2 and layer 3 lookup table or determining that the odd lookup of the first packet address is a miss; and

the second search engine is configured to continue the even lookup of the second packet address until either the second packet address is found in the even layer 2 and layer 3 lookup table or the second packet address is determined to not be included in the even layer 2 and layer 3 lookup table, and if the second packet address is determined not to be included in the even layer 2 and layer 3 lookup table, the even lookup of the second packet address includes either finding the second packet address in the odd layer 2 and layer 3 lookup table or determining that the even lookup of the second packet address is a miss.

14. A network switch as recited in claim 5, wherein:

the first packet includes a first packet source address and a first packet destination address, and the second packet includes a second packet source address and a second packet destination address; and

the odd lookup alternates between searching for the first packet source address and the first packet destination address in the odd layer 2 and layer 3 lookup table; and

the even lookup alternates between searching for the second packet source address and the second packet destination address in the even layer 2 and layer 3 lookup table.

15. A network switch as recited in claim 5, wherein the search engines each include:

a first searcher configured to search an IP multicast table to determine if the respective packet address is contained in either the odd layer 2 and layer 3 lookup table or the even layer 2 and layer 3 lookup table; and

a first forwarder configured to forward the first and second packets to a remote CPU if the destination address is not contained in the IP multicast table.

16. A network switch as recited in claim 5, wherein the search engines each include:

a comparator configured to compare a time-to-live (TTL) value to a predetermined TTL threshold if the respective packet address is known;

a sender configured to send the respective packet to the CPU if the TTL value is below the predetermined TTL threshold; and

an obtainer configured to obtain a layer 3 port bitmap from an IP multicast table if the TTL value is not below the predetermined TTL threshold.

17. A network switch as recited in claim 5, wherein the search engines each include a switch configured to switch the respective packet to the destination ports if ports on the layer 3 port bitmap are considered active ports for the network switch.

18. A network switch as recited in claim 5, wherein the search engines each include:

an examiner configured to examine port filtering bits of the respective packet to determine whether a first predetermined port filtering value is present;

a forwarder configured to forward the respective packet to a selected port on the switch if the first predetermined port filtering value is present; and

a searcher configured to search a multicast table using a destination key if the first predetermined filtering value is not present.

19. A network switch as recited in claim 5, wherein the search engines each include:

a searcher configured to search an IP multicast table to determine if the respective packet address is contained in either the odd layer 2 and layer 3 lookup table or the even layer 2 and layer 3 lookup table;

an obtainer configured to search a port bitmap from the IP multicast table if searching the multicast table results in a match; and

a forwarder configured to forward the respective packet to ports obtained from the port bitmap, when the obtainer obtains the port bitmap from the multicast table.

20. A network switch as recited in claim 5, wherein the search engines each include:

a searcher configured to search an IP multicast table to determine if the respective packet address is contained in either the odd layer 2 and layer 3 lookup table or the even layer 2 and layer 3 lookup table;

a first examiner configured to examine port filtering bits of the respective packet to determine whether a first predetermined port filtering value is present;

a second examiner configured to examine the port filtering bits to see if a second predetermined port filtering value is present if there is not a match through the searching of the IP multicast table;

a dropper configured to drop the respective packet when the second predetermined port filtering value is present;

a obtainer configured to obtain from a VLAN table a destination port bitmap when the second predetermined port filtering value is not present; and

a forwarder configured to forward the data packets to ports identified in the destination port bitmap.