Multi-layer distributed network element

• US 6,115,378 A
• Filed: 06/30/1997
• Issued: 09/05/2000
• Est. Priority Date: 06/30/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Muller, Shimon, Hendel, Ariel
• Primary Examiner(s): Vu, Huy D.
• Application Number:
  US08/884,919
• Time in Patent Office: 1,163 Days
• Field of Search: 370/400, 370/401, 370/402, 370/403, 370/404, 370/405, 370/389, 370/392, 370/351, 370/410, 370/466, 370/467, 370/469, 370/409, 395/200.68, 395/200.72, 395/200.73, 395/200.74, 395/200.79, 395/200.8, 395/200.5
• US Class Current: 370/392
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

A distributed multi-layer network element delivering Layer 2 (data link layer) wire-speed performance within and across subnetworks, allowing queuing decisions to be based on Layer 3 (network layer) protocol and endstation information combined with Layer 2 topology information. The network element performs packet relay functions using multiple switching subsystems as building blocks coupled to each other to form a larger switch that acts as both a router and a bridge. Each switching subsystem includes a hardware forwarding search engine having a switching element coupled to a forwarding memory and an associated memory. The switching subsystems and their fully meshed interconnection allow the network element to scale easily without compromising packet forwarding speed and without significantly increasing the storage requirements of each forwarding memory.

Claims

1. In a network element for receiving and forwarding packets between nodes, the network element having separate first and second subsystem circuitry coupled by an internal link, the subsystems having first and second forwarding memories, respectively, a method for relaying packets comprising the steps of:

receiving a packet by the first subsystem circuitry the packet having a first header portion including a destination address;

searching the first forwarding memory for a first entry that matches the destination address in the first header portion;

sending the packet to the second subsystem circuitry through the internal link in response to the first entry matching the destination address in the first header portion and without changing the destination address of the packet;

and forwarding the packet to a destination specified in the first header portion in response to the first header portion including the destination address matching a second entry in the second forwarding memory.

2. A method as in claim 1 wherein the destination address is a Layer 2 destination address.

3. A method as in claim 1 wherein

the first entry comprises a Layer 2 address that was learned by the second subsystem and copied to the first forwarding memory prior to the packet being received by the first subsystem.

4. A method as in claim 1 wherein

the second entry comprises a Layer 2 address that was learned by the second subsystem prior to the packet being received by the first subsystem.

5. In a network element for receiving and forwarding packets between nodes, the network element having first and second subsystems coupled by an internal link, the subsystems having first and second forwarding memories, respectively, a method for relaying packets comprising the steps of:

receiving a packet by the first subsystem, the packet having a second header portion, the second header portion including a network layer destination address;

searching the first forward memory for a type 2 entry that matches the second header portion;

sending the packet and a control signal to the second subsystem through the internal link in response to the type 2 entry matching the first header portion, the control signal being associated with the type 2 entry and defining a queuing priority; and

forwarding the packet from the second subsystem, according to said queuing priority set by the control signal, to a destination specified in the second header portion.

6. A method as in claim 5 wherein the step of sending the packet and a control signal further includes sending a second control signal which identifies the packet as a member of a flow to the second subsystem, and further comprising the step of searching the second forwarding memory for a type 2 entry that matches the second header portion in response to receiving the second control signal.

20. A method as in claim 5 wherein the network element further comprises:

a central processing system (CPS) having a central memory (CM), the CPS coupled to each subsystem and configured with a copy of all source addressed learned by the first and second subsystems, and configured to cause a source address learned by the second subsystem to be stored in an entry of the first forwarding memory in response to a notification from the first subsystem that a destination address of a packet does not match any entry in the first forwarding memory but matches said source address.

21. A method as in claim 6 wherein a flow priority is associated with the type 2 entry in the second subsystem, and wherein the step of forwarding the packet from the second subsystem is in response to the type 2 entry matching the second header portion, the packet being forwarded from the second subsystem according to the flow priority rather than the queuing priority.

7. A network element for interconnecting nodes, comprising:

first subsystem circuitry having a first forwarding memory and configured to search the first forwarding memory for a first entry that matches a destination address in a first header portion of a packet;

second subsystem circuitry separate from the first subsystem circuitry and having a second forwarding memory; and

an internal link coupling the first and second subsystems for passing packets and control information from the first subsystem circuitry to the second subsystem circuitry, wherein

the first subsystem circuitry is configured to send the packet to the second subsystem circuitry through the internal link in response to the first entry matching the first header portion including the destination address, and without changing a Layer 2 destination address of the packet, and wherein

the second subsystem circuitry is configured to forward the packet to a destination specified in the first header portion in response to a second entry in the second forwarding memory matching the destination address in the first header portion of the packet.

8. A network element as in claim 7 wherein

the destination address is a Layer 2 destination address.

9. A network element as in claim 7 wherein

the first entry comprises a Layer 2 address that was learned by the second subsystem and copied to the first entry prior to the packet being received by the first subsystem.

10. A network element as in claim 9 wherein

the second entry comprises a Layer 2 address that was learned by the second subsystem prior to the packet being received by the first subsystem.

11. A network element as in claim 7 further comprising

a central processing system (CPS) having a central memory (CM), the CPS coupled to each subsystem and configured to cause a source address learned by the second subsystem to be stored in an entry of the first forwarding memory in response to finding a copy of the source address in the central memory.

12. A network element as in claim 7 wherein

the first subsystem further comprises

a first associated memory and an internal port coupling the internal link, the first associated memory for storing a port value identifying the internal port, the first subsystem configured to associate the port value with the first entry in the forwarding memory.

13. A network element as in claim 7 wherein

the first subsystem is further configured to flood the packet to a predefined subnet in response to no entry in the first forwarding memory matching the destination address in the first header portion.

14. A network element as in claim 7 wherein

the first subsystem is further configured to send the packet to the second subsystem in response to a second entry in the first forwarding memory matching a second header portion of the packet, the second header portion comprising a network layer destination address separate from the destination address in the first portion header, and wherein

the second subsystem is further configured to forward the packet to a destination specified in the second header portion.

15. A network element as in claim 14 wherein

the second subsystem is further configured to forward the packet to a destination specified in the second header portion in response to a fourth entry in the second forwarding memory matching the second header portion of the packet.

16. A network element as in claim 14 wherein

the third subsystem is further configured to perform a search of the second forwarding memory for an entry matching the second header portion of the packet in response to receiving the packet and a first control signal from the first subsystem.

17. A network element as in claim 14 wherein

the second subsystem is configured to forward the packet in accordance with quality of service (QOS) information received from the first subsystem, the QOS information being associated with the third entry in the first subsystem.

18. A network element as in claim 15 wherein the second subsystem is further configured to associate second QOS information with the fourth entry, the second QOS information overriding QOS information received from the first subsystem.

19. A network element as in claim 7 further comprising

a central processing system (CPS) having a central memory (CM), the CPS coupled to each subsystem and configured with a copy of all source addresses learned by the first and second subsystems, and configured to cause a source address learned by the second subsystem to be stored in an entry of the first forwarding memory in response to a notification from the first subsystem that a destination address of a packet does not match any entry in the first forwarding memory but matches said source address.

22. A network element as in claim 7 wherein each subsystem has a plurality of external ports and at least one internal port, the internal port connects to the internal link and the external ports connect to other nodes, and wherein the packet arriving through one of the external ports in the first subsystem and whose destination address in the first header portion does not match any entry in the first forwarding memory is flooded to all of the external ports, except the port of arrival, and the at least one internal port.

23. A network element as in claim 7 wherein each subsystem is implemented as part of a separate IC.

24. A network element for interconnecting nodes, comprising:

first subsystem having a first forwarding memory and configured to search the first forwarding memory for a first entry that matches a first header portion of a packet;

second subsystem having a second forwarding memory;

an internal link coupling the first and second subsystems for passing packets and control information from the first subsystem to the second subsystem; and

a central processing system (CPS) having a central memory (CM), the CPS coupled to each subsystem and configured to cause a source address learned by the second subsystem to be stored in an entry of the first forwarding memory in response to finding a copy of the source address in the central memory, and wherein

the first subsystem is configured to send the packet to the second subsystem through the internal link in response to the first entry matching the first header portion, and the second subsystem is configured to forward the packet to a destination specified in the first header portion.

25. A network element for interconnecting nodes, comprising:

first subsystem having a first forwarding memory and configured to search the first forwarding memory for at least one of a first entry that matches a first header portion of a packet and a third entry that matches a second header portion of the packet, the second header portion comprising a network layer destination address;

second subsystem having a second forwarding memory; and

an internal link coupling the first and second subsystems for passing packets and control information from the first subsystem to the second subsystem, wherein

the first subsystem is configured to send the packet to the second subsystem through the internal link in response to the first entry matching the first header portion, the second subsystem is configured to forward the packet to at least one of a destination specified in the first header portion, and a destination specified in the second header portion, and wherein

the second subsystem is further configured to perform a search of the second forwarding memory for an entry matching the second header portion of the packet in response to receiving the packet and a first control signal from the first subsystem.