Method and apparatus for controlling data flow within a switching device

• US 5,732,080 A
• Filed: 07/12/1995
• Issued: 03/24/1998
• Est. Priority Date: 07/12/1995
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Bay Networks, Inc. (Nortel Networks Corporation)
• Inventors: Ferguson, H. Earl, Prince, Jeffrey, Noll, Mike K., Ryals, Randy, Pitcher, Derek H.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Carman, Melissa Kay
• Application Number:
  US08/501,483
• Time in Patent Office: 986 Days
• Field of Search: 370/395, 370/389, 370/473, 370/357, 370/386, 370/392, 370/419, 370/359, 370/235, 370/355, 370/257, 370/397, 370/352
• US Class Current: 370/392
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 49/104 Asynchronous transfer mode [ATM] switching fabrics
• CPC Class Codes: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and apparatus for controlling data flow within a switching device are provided. The switching device includes a cell-switched backplane. Both packet switched and cell switched network interface cards may be coupled to the cell-switched backplane. A destination tag is created for each unique destination port and for each unique set of destination ports. The destination tags are used to index a master destination tag table. The entry of the master destination tag table that corresponds to a given destination tag includes a destination mask that indicates which ports are destination ports the given destination tag. Local tables are built and maintained within each network interface card based on the information contained in the master destination tag table. When a network interface receives data from an external device, the network interface determines the destination tag associated with the data. Once the destination tag is determined, it is used as an index to the locally stored tables to determine whether the data should be forwarded to any local ports, and whether the data should be sent over the cell-switched backplane to other network interfaces within the switching device. When a network interface receives data over the backplane, the network interface uses the destination tag as an index to a locally stored table to determine to which local ports the data should be sent. Tables also establish correlations between destination tags and control information for converting data between packets and cells.

Claims

1. A method for forwarding data between ports on a plurality of network interfaces located in a switching device, the method comprising the steps of:

receiving data at a first port on a first network interface in said switching device;

determining a destination tag for said data based on destination information contained with said data;

using said destination tag as an index to a first table to determine whether any ports on said first network interface other than said first port are associated with said destination tag;

if one or more ports on said first network interface other than said first port are associated with said destination tag, then forwarding said data to said one or more ports;

using said destination tag as an index to a second table to determine whether any of said plurality of network interfaces other than said first network interface include ports that are associated with said destination tag;

if one or more network interfaces other than said first network interface include ports that are associated with said destination tag, then forwarding said data to said one or more network interfaces over a common backplane.

2. The method of claim 1 further comprising causing each of said one or more network interfaces to perform the following steps:

reading said data from said common backplane;

using said destination tag as an index to a third table to determine whether any ports on said network interface is associated with said destination tag; and

if one or more ports on said network interface is associated with said destination tag, then forwarding said data to said one or more ports.

3. The method of claim 1 wherein:

said first network interface is a LAN interface and said common backplane is a cell switched backplane,

said step of receiving data at said first port comprises receiving a packet at said first port;

said step of forwarding said data to said one or more network interfaces over a common backplane comprises placing one or more cells containing information from said packet onto said backplane;

the method further comprising the step of converting said packet into said one or more cells.

4. The method of claim 3 wherein the step of converting said packet into one or more cells includes using said destination tag as an index to a table to determine which information to strip from and add to said packet to create said one or more cells.

5. The method of claim 1 wherein said first table and said second table are stored on said first network interface.

6. The method of claim 5 wherein said first table is a different table than said second table.

7. The method of claim 1 further comprising the step of constructing said first table and said second table based on information contained in a master destination tag table.

8. The method of claim 7 wherein:

said master destination tag table includes a plurality of entries, each entry corresponding to a destination tag;

each entry of said master destination tag table includes a destination mask, said destination mask indicating which of all the ports on all of said plurality of network interfaces are destination ports for said corresponding destination tag.

9. The method of claim 1 wherein said step of forwarding said data to said one or more network interfaces over a common backplane includes:

encapsulating said data into cells;

adding said destination tag into a header on each of said cells; and

applying said cells to said common backplane.

10. A switching device comprising:

a backplane; and

a plurality of network interfaces coupled to said backplane;

each of said plurality of network interfaces comprising

one or more ports;

a first set of correlation data that establish a correlation between destination information and destination tags;

a second set of correlation data that establish a correlation between destination tags and said one or more ports on said network interface;

a third set of correlation data that establish a correlation between destination tags and the other of said plurality of network interfaces; and

a forwarding mechanism configured to forward data between and among said one or more ports and said backplane based on said first, second and third sets of correlation data.

11. The switching device of claim 10 wherein said forwarding mechanism is configured to forward data received at one of said one or more ports by:

reading destination information from said data;

inspecting said first set of correlation data to determine a destination tag for said data based on said destination information from said data;

inspecting said second set of correlation data to determine whether any of said one or more ports are associated with said destination tag;

forwarding said data to each of said one or more ports that are associated with said destination tag;

inspecting said third set of correlation data to determine whether any of said other network interfaces are associated with said destination tag; and

placing said data on said backplane if any of said other network interfaces are associated with said destination tag.

12. The switching device of claim 10 wherein said forwarding mechanism is configured to forward data received over said backplane from another of said network interfaces by:

determining a destination tag for said data;

inspecting said second set of correlation data to determine whether any of said one or more ports are associated with said destination tag; and

forwarding said data to each of said one or more ports that are associated with said destination tag.

13. The switching device of claim 11 wherein said forwarding mechanism is configured to add an indication of said destination tag to said data prior to placing said data on said backplane.

14. The switching device of claim 12 wherein said forwarding mechanism determines said destination tag for said data by extracting an indication of said destination tag from said data.

15. The switching device of claim 10 wherein said backplane is a cell switched backplane and at least one of said plurality of network interfaces is a packet switched interface for a packet switched network, said forwarding mechanism on said packet switched interface including a segmentation and reassembly unit for converting packets into cells prior to placing the cells on the backplane and for reassembling cells received from said backplane into packets.

16. The switching device of claim 15 wherein said packet switched interface includes a fourth set of correlation data that establish a correlation between destination tags and conversion information, said forwarding mechanism on said packet switched interface inspecting said fourth set of correlation data to determine how to convert a packet associated with a destination tag to cells, said forwarding mechanism on said packet switched interface inspecting said fourth set of correlation data to determine how to convert cells associated with a destination tag to a packet.

17. The switching device of claim 10 further comprising a master control process configured to maintain a master destination tag table, said master destination tag table establishing a correlation between destination tags and sets of ports, each set of said sets of ports including one or more ports located on one or more of said plurality of network interfaces.

18. The switching device of claim 17 wherein said master control process transmits messages containing information derived from said master destination tag table to each of said plurality of network interfaces, each of said plurality of network interfaces constructing said first, second and third sets of correlation data based on the information derived from said master destination tag table contained in said messages.

19. The switching device of claim 18 wherein the messages sent to any given network interface include a mapping between destination tags and one or more ports on said given network interface, and a mapping between destination tags and each of the other network interfaces present in the switching device.

20. The switching device of claim 10 configured to implement a virtual token ring that includes a particular set of ports by establishing a unique destination tag for said virtual token ring, wherein, for each of said plurality of network interfaces:

said second set of correlation data establishes a correlation between said unique destination tag and the ports on said network interface that belong to said particular set of ports; and

said third set of correlation data establishes a correlation between said unique destination tag and the network interfaces, of said other of said plurality of network interfaces, that include at least one port of said particular set of ports.

21. The switching device of claim 10 configured to allow data that is sent out any port of a set of one or more ports to be monitored on a particular port of a particular network interface, wherein:

for each of said network interfaces other than said particular network interface, every entry in said third set of correlation data that corresponds to a destination tag of a particular set of destination tags establishes a correlation between said destination tag and said particular network interface;

for said particular network interface, every entry in said second set of correlation data that corresponds to a destination tag of said particular set of destination tags establishes a correlation between said destination tag and said particular port;

said particular set of destination tags including all destination tags that are correlated in second set of correlation data on any of said plurality of network interfaces with any port of said set of one or more ports to be monitored.

22. A method for forwarding data between ports on a plurality of network interfaces located in a switching device, the method comprising the steps of:

when data arrives at any port of any of said plurality of network interfaces performing the steps of

determining a destination tag for said data based on destination information contained with said data by

using the destination information as an index into a first table to retrieve a corresponding destination tag if the destination information represents a first type of destination designation scheme, and

using the destination information as an index into a second table to retrieve a corresponding destination tag if the destination information represents a second type of destination designation scheme;

using said destination tag as an index to correlation data to determine a set of destination ports associated with said destination tag; and

forwarding said data to each destination port in said set of destination ports.

23. The method of claim 22 wherein:

the data arrives at a first port, said first port residing on a first network interface;

the step of using said destination tag as an index to correlation data to determine said set of destination ports includes the steps of

using said destination tag as an index to said correlation data to determine whether any ports on said first network interface other than said first port are associated with said destination tag; and

using said destination tag as an index to said correlation data to determine whether any of said plurality of network interfaces other than said first network interface are associated with said destination tag.

24. The method of claim 23 wherein the step of forwarding said data to each destination port in said set of destination ports includes the steps of:

if one or more ports on said first network interface other than said first port are associated with said destination tag, then forwarding said data to said one or more ports;

if one or more network interfaces other than said first network interface are associated with said destination tag, then forwarding said data to said one or more network interfaces over a common backplane.

25. The method of claim 23 wherein said correlation data is stored locally on said first network interface and said steps of determining whether any ports on said first network interface other than said first port are associated with said destination tag and determining whether any of said plurality of network interfaces other than said first network interface are associated with said destination tag are performed by a forwarding mechanism located on said first network interface.

26. The method of claim 22 further comprising the step of establishing a virtual token ring that includes a first set of ports by performing the steps of:

creating a destination tag for said virtual token ring;

updating said correlation data to establish a correlation between said destination tag and each port in said first set of ports.

27. The method of claim 22 further comprising the step of monitoring at a given port data that flows through a first set of ports, said step of monitoring including the steps of:

inspecting said correlation data to determine a set of destination tags, said set of destination tags including all of the destination tags that are associated with any port in said first set of ports;

updating said correlation data to cause each destination tag in said set of destination tags to also be associated with said given port.

28. A switching device comprising:

a backplane; and

a plurality of network interfaces coupled to said backplan;

each of said plurality of network interfaces comprising

one or more ports,

a first set of correlation data that maps destination addresses to destination tags,

a second set of correlation data that maps destination tags from said first set of correlation data to said one or more ports on said network interface, and

a forwarding mechanism configured to forward data among said one or more ports based on said first set of correlation data and said second set of correlation data.

29. The switching device of claim 28, further comprising a third set of correlation data that maps destination tags from said first set of correlation data to other of said plurality of network interfaces, and wherein the forwarding mechanism is configured to forward data between and among said one or more ports and said backplane with reference to said third set of correlation data.

30. The switching device of claim 28 wherein said forwarding mechanism is configured to forward data received over said backplane from another of said network interfaces by:

determining a destination tag for said data based upon said first set of correlation data;

accessing said second set of correlation data with said destination tag to determine whether any of said one or more ports are associated with said destination tag; and

forwarding said data to each of said one or more ports that are determined to be associated with said destination tag.

31. A method for forwarding data between ports on a plurality of network interfaces located in a switching device, the method comprising the steps of:

when data arrives at a first port, said first port residing on a first network interface performing the steps of

determining a destination tag for said data based on destination information contained with said data;

using said destination tag as an index to correlation data to determine a set of

destination ports associated with said destination tag by

determining whether any ports on said first network interface other than said first port are associated with said destination tag, and

determining whether any of said plurality of network interfaces other than said first network interface are associated with said destination tag; and

forwarding said data to each destination port in said set of destination ports.

32. The method of claim 31 wherein the step of forwarding said data to each destination port in said set of destination ports includes the steps of:

if one or more ports on said first network interface other than said first port are associated with said destination tag, then forwarding said data to said one more ports;

if one or more network interfaces other than said first network interface are associated with said destination tag, then forwarding said data to said one or more network interfaces over a common backplane.

33. The method of claim 31 wherein said correlation data is stored locally on said first network interface and said steps of determining whether any ports on said first network interface other than said first port are associated with said destination tag and determining whether any of said plurality of network interfaces other than said first network interface are associated with said destination tag are performed by a forwarding mechanism located on said first network interface.