Arrangement for rendering forwarding decisions for packets transferred among network switches

• US 5,872,783 A
• Filed: 07/24/1996
• Issued: 02/16/1999
• Est. Priority Date: 07/24/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Chin, Hon Wah
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/686,106
• Time in Patent Office: 937 Days
• Field of Search: 370/236, 370/351, 370/352, 370/392, 370/395, 370/396, 370/397, 370/399, 370/255, 370/401, 370/402, 370/409
• US Class Current: 370/395.32
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

An arrangement facilitates rendering of a forwarding decision for a packet transferred between high-speed switches of a network using a path identifier (PTID) encapsulated within the packet. The PTID is a tag associated with a destination address of the packet and comprises a value that uniquely identifies a corresponding entry of a forwarding table of the switch. Rather than requiring a full compare of the destination address with the contents of the forwarding table, the PTID is used as a direct index address into the table that identifies the corresponding entry in a fast and efficient manner.

Claims

1. In a communications network, an arrangement comprising:

A) a first switch that includes a first-switch port from which the first switch forwards packets, each of a plurality of said packets including a path-identifier field and link-level destination- and source-address fields; and

B) a second switch comprising;

i) a plurality of second-switch ports, including second-switch output ports and a second-switch input port coupled to the first-switch port;

ii) a forwarding table into which the second switch places at each of a plurality of table locations therein a respective entry that associates a respective link-level address with a second-switch output port at which the second switch has received a packet that included a source-address field containing that link-level address, each table location being represented by a respective index address; and

iii) means for fetching the table entry at the table location represented by the contents of the path-identifier field of each of said plurality of packets forwarded from said first-switch port and received at the second-switch input port and, if that entry associates a given second-switch port with the contents of that packet'"'"'s destination-address field, forwarding that received packet from the given second-switch port.

2. The arrangement of claim 1 wherein the means for fetching the table entry and forwarding the received packet comprises a processing unit coupled to a switching fabric circuit.

3. The arrangement of claim 2 wherein the forwarding table is an inbound table and the second switch further comprises at least one outbound table comprising a plurality of outbound-table entries at respective table locations therein represented by respective index addresses, and wherein the switching fabric circuit comprises one of a shared memory fabric and a shared medium fabric.

4. The arrangement of claim 3 wherein the inbound table is associated with the second-switch input port and wherein the table entries are inbound-table entries included in the inbound table, each inbound-table entry containing (i) a destination-address field containing the link-level address with which that inbound-table entry associates a second-switch port, (ii) an outbound-port-information field and (iii) an internal-PTID field.

5. The arrangement of claim 4 wherein the contents of a given inbound-table entry'"'"'s outbound-port-information field specifies the second-switch output port that the given table entry associates with the contents of the destination-address field.

6. The arrangement of claim 4 wherein the second switch includes a plurality of said second-switch output ports associated with a respective said outbound tables and wherein the contents of the internal-PTID field are employed where the packet is destined for multiple output ports, the contents of the internal-PTID field being used as an index address into the outbound table associated with at least one of the second-switch output ports.

7. The arrangement of claim 6 wherein:

one said second-switch output port is coupled to a third switch; and

each outbound-table entry in the outbound table associated with said one second-switch output port contains at least one field for storing a new PTID assigned by the third switch.

8. The arrangement of claim 7 further comprising a memory element coupled between the processing unit and the second-switch input port for facilitating rendering of the forwarding decision at the second-switch input port for the packet when the destination address is known to the processing unit but unknown by the second-switch input port.

9. The arrangement of claim 8 wherein the memory element is a content addressable memory having a predetermined number of entries, each of which contains fields for storing information similar to that stored in the inbound table entries.

10. The arrangement of claim 8 further comprising an out-of-band data path for transferring predetermined information to the processing unit.

11. The arrangement of claim 10 wherein the out-of-band data path is one of a first-in, first-out buffer and a queue buffer, and wherein the processing unit either periodically polls the buffer or is interrupted by the buffer in response to the transferred predetermined information.

12. A method for facilitating rendering of a forwarding decision for a packet transferred from a first switch to a destination station via a second switch of a network, which second switch includes second-switch output ports and a second-switch input port coupled to the first switch, the method comprising the steps of:

configuring a forwarding table, associated with the second-switch input port, that includes at each of a plurality of table locations therein a respective table entry that associates a respective link-level address with a second-switch output port at which the second switch has received a packet that included a source-address field containing that link-level address, each table location being represented by a respective index address;

sending a message from the second switch to the first switch notifying the first switch of the index address that represents the location at which a table entry associates the destination station'"'"'s link-level address with one said second-switch output port;

encapsulating the packet with that index address at the first switch prior to forwarding the packet to the second switch; and

rendering the forwarding decision for the packet received at the second switch using that index address to locate the corresponding table entry.

13. The method of claim 12 wherein the first switch is a learning switch and the second switch is an interpreting switch, wherein the forwarding table is an inbound table, and wherein the step of configuring further includes configuring a plurality of outbound tables associated with respective ones of said second-switch output ports.

14. The method of claim 13 wherein the table entries in the inbound table are inbound-table entries and the step of configuring further comprises the steps of:

configuring each inbound-table entry with (i) a destination-address field containing the link-level address associated with that inbound-table entry, (ii) an outbound-port-information field whose contents specify the output ports of the switch selected to receive the packet and (iii) an internal-PTID field.

15. The method of claim 14 wherein one of said second-switch output ports is coupled to a third switch and the step of configuring further comprises the steps of:

configuring each outbound table to include a plurality of outbound-table entries, each having a plurality of fields; and

loading, in the internal-PTID field of an entry in the outbound table associated with said one second-switch output port, a new PTID tag assigned by the third switch.

16. The method of claim 15 wherein the step of configuring further comprises the step of decoupling indexing into a selected outbound table from addressing of the inbound table in the event that the new PTID tag assigned to a copy of the packet destined for said one of said second switch output ports by the third switch is different from the tag assigned to another copy of the packet by another interpreting switch.