System and method for a multi-layer network element

• US 6,081,522 A
• Filed: 06/30/1997
• Issued: 06/27/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: Murthy, Shree, Hendel, Ariel, Hejza, Leo A.
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US08/885,559
• Time in Patent Office: 1,093 Days
• Field of Search: 370/389, 370/392, 370/400, 370/401, 370/402, 370/432, 370/469, 370/412, 370/413-419, 370/428, 370/429, 340/825.52, 395/200.1, 395/200.2
• US Class Current: 370/389
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/3027 Output queuing
• 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 multi-layer network element for forwarding received packets from an input port to one or more output ports. The packet is examined to look for different types of forwarding information. An associative memory is searched once for each type of information. The results from the two searches are combined to forward the packet to the appropriate one or more output ports. The packet may be examined for other information as well to make the forwarding decisions. In one embodiment, the invention examines the packet for layer 2 information as the first type and layer 3, and perhaps some layer 4, information as the second type. The results are merged to determine the most appropriate combination of layer 2 or layer 3 forwarding decisions for the packet.

Claims

1. In a network element having at least one input port and at least one output port, a method of forwarding a packet entering on an input port comprising the steps of:

(a) receiving the packet from a network on the input port;

(b) determining a first search key from a first portion of header information associated with a first protocol layer;

(c) determining a second search key from a second portion of header information associated with a second protocol layer;

(d) simultaneously searching entries in a memory for an entry matching the first search key;

(e) using at least one entry, if any, located in step (d) to determine a first port result;

(f) simultaneously searching entries in the memory for entries associated with the second search key;

(g) selecting one entry from the entries associated with the second search key;

(h) using the result of step (g) to determine forwarding information;

(i) determining appropriate output ports, if any, based on the results of step (e) and step (h); and

(j) forwarding the packet to the appropriate output ports.

2. The method of claim 1, wherein step (g) includes selecting the entry in the memory based on layer 3 information based upon a predetermined importance criterion determined to be the most appropriate.

3. The method of claim 2, wherein, if no entries are matched in step (g), step (i) includes designating the appropriate output port as the first port result.

4. The method of claim 1, wherein step (i) includes the step of selecting the result of step (e) as the appropriate output port.

5. The method of claim 1, wherein step (j) includes the step of using portions of the result of step (h).

6. The network element of claim 1, wherein the memory comprises a first memory and a second memory, wherein at least one entry in the first memory is adapted to point to a corresponding entry in the second memory.

7. The network element of claim 6, wherein the first memory is a content-addressable memory.

8. The method of claim 1, wherein step (j) includes modifying the packet header according to the result of step (h).

25. The method of claim 1, wherein the first packet information includes VLAN information and step (e) includes using an entry matching only VLAN information.

9. A network element for forwarding packet on a network, the network element comprising:

(a) at least one input port for receiving a packet;

(b) processing logic for examining the packet and determining a first search key and a second search key associated with a first protocol layer and a second protocol layer, respectively;

(c) a memory adapted to have at least a portion of its contents searched simultaneously and output a result based on a search;

(d) first search circuitry configured to search the memory using the first search key and causing the memory to output a first search result;

(e) second search circuitry configured to search the memory using the second search key and causing the memory to output a second search result;

(f) at least one output port;

(g) merge circuitry coupled to the memory, the merge circuitry configured to forward the packet to appropriate output ports, if any, of the at least one output port based on the first search result and the second search result.

10. The network element of claim 9, wherein the memory comprises a first memory and a second memory, wherein at least one entry in the first memory points to a corresponding entry in the second memory, causing a search result to be output from the second memory.

11. The network element of claim 10, wherein the first memory is adapted to have at least a portion of its contents searched simultaneously.

12. The network element of claim 11, wherein the first memory is a content-addressable memory.

13. A network element for forwarding packets on a network, the network element comprising:

(a) at least one input port configured to receive a packet;

(b) header processing logic configured to examine packet header information for determining a first search key and a second search key associated with a first protocol layer and a second protocol layer, respectively;

(c) a memory;

(d) first search logic coupled to the memory, the first search logic configured to cause the memory to output a first search result based on the first search key;

(e) second search logic coupled to the memory, the second search logic configured to cause the memory to output a second search result based on the second search key;

(f) at least one output port;

(g) merge logic, coupled to the memory, configured to forward the packet to appropriate output ports, if any, of the at least one output port based on the first search result and the second search result.

14. The network element of claim 13, wherein the memory is adapted to have at least a portion of its contents searched simultaneously.

15. The network element of claim 14, wherein the memory is a content addressable memory.

16. The network element of claim 13, wherein the memory comprises a first memory and a second memory, wherein each entry in the first memory is adapted to point to a corresponding entry in the second memory, causing the results to be output from the second memory.

17. The network element of claim 15, wherein the first memory is adapted to have at least a portion of its contents searched simultaneously.

18. The network element of claim 17, wherein the first memory is a content-addressable memory.

19. A network element for forwarding packets on a network, the network element comprising:

(a) at least one input port configured to receive a packet;

(b) processing logic configured to determine first packet information and second packet information from packet header information associated with a first protocol layer and a second protocol layer, respectively;

(c) a memory;

(d) memory access logic coupled to the memory, the memory access logic configured to access the memory using a first address determined as a function of the first packet information to produce a first result and a second address determined as a function of the second packet information to produce a second result;

(e) at least one output port; and

(f) merge logic coupled to the memory, the merge logic configured to forward the packet to an appropriate output port of the at least one output port based on the first result and the second result.

20. The network element of claim 19, wherein the memory access logic is a content-addressable memory.

21. The network element of claim 19, wherein the memory access logic is based on a hashing function.

22. An apparatus for making a forwarding decision for a packet entering a network element having at least one input port and at least one output port, wherein the packet enters the network element on an input port and exits the network element on appropriate output ports, the apparatus comprising:

header logic configured to output, based on header information in the packet, a first search key associated with a first protocol layer, a second search key associated with a second protocol layer, and a default result;

a memory configured to output a first forwarding result in response to receiving the first search key from the header logic, and to output a second forwarding result in response to receiving the second search key;

merge logic configured to output information about appropriate output ports in response to the default result, the first forwarding result, and the second forwarding result; and

forwarding logic configured to direct the packet from the input port to the appropriate output ports based on the information about the appropriate output ports.

23. The apparatus of claim 22, further including:

a packet memory;

a packet memory manager configured to signal to the input port a location in the memory available to store a portion of the packet, to accept the packet from the input port and store the packet in the location, and to transmit the packet to the appropriate output port upon request from the output port; and

wherein the forwarding logic includes pointer passing logic configured to pass the location from the input port to the appropriate output port.

24. The apparatus of claim 22, wherein the input port and the output port are configured to modify the contents of the packet header.

26. A method of forwarding packets comprising the steps of:

receiving a packet from a network at an input port;

generating a first forwarding decision based upon information in a data link layer of the packet;

generating a second forwarding decision based upon information in a network layer of the packet;

determining a resulting forwarding decision based upon the first forwarding decision and the second forwarding decision; and

forwarding the packet to one or more output ports identified by the resulting forwarding decision.

27. The method of claim 26, wherein the packet includes header information, and wherein the step of generating a first forwarding decision based upon information in a data link layer of the packet comprises the steps of:

creating a first search key based upon a first portion of the header information;

simultaneously searching entries in a memory for a matching entry that matches the first search key; and

determining the first forwarding decision based upon the matching entry.

28. The method of claim 27, wherein the packet includes header information, and wherein the step of generating a second forwarding decision based upon information in a network layer of the packet comprises the steps of:

identifying a class of a plurality of classes with which the packet is associated based upon the header information;

creating a second search key based upon one or more fields in the header information, the one or more fields conditional upon the class;

simultaneously searching entries in the memory for entries associated with the second search key; and

determining the second forwarding decision based upon the class or an entry associated with the second search key.

29. The method of claim 28, wherein the step of determining a resulting forwarding decision based upon the first forwarding decision and the second forwarding decision comprises the step of merging the first forwarding decision and the second forwarding decision by selecting between the first forwarding decision and the second forwarding decision or combining aspects of both the first forwarding decision and the second forwarding decision.