Method and apparatus for managing the flow of data within a switching device

Abstract

A method and apparatus for managing the flow of data within a switching device is provided. The switching device includes network interface cards connected to a common backplane. Each interface card is configured to support the maximum transfer rate of the backplane by maintaining a “pending” queue to track data that has been received but for which the appropriate routing destination has not yet been determined. The switching device includes a switch controller that maintains a central card/port-to-address table. When an interface card receives data with a destination address that is not known to the interface card, the interface card performs a direct memory access over a bus that is separate from the backplane to read routing data directly from the central table in the switch controller. Each interface card builds and maintains a routing information table in its own local memory that only includes routing information for the destination addresses that the interface card is most likely to receive.

1 - 14 . (canceled)  
   
   
       15 . A switching device comprising: 
 a master control process including a memory to store routing information; and    a plurality of devices coupled together over a first connection and in communication with the master control process, each of the plurality of devices comprising (i) a local memory including a plurality of entries that collectively contain a portion of the routing information stored in the memory of the master control process and (ii) a controller to update contents of at least one entry of the local memory from the memory of the master control process over a second connection separate from the first connection.    
   
   
       16 . The switching device of  claim 15 , wherein the plurality of devices comprises a first device including a plurality of ports.  
   
   
       17 . The switching device of  claim 16 , wherein controller of the first device updates the contents in response to an event being a condition in which contents of the entry have not been accessed for longer than a specified amount of time.  
   
   
       18 . The switching device of  claim 16 , wherein the controller of the first device updates the contents in response to an event being a condition in which a cell having a destination address is received and no routing information associated with the cell is currently stored in the local memory.  
   
   
       19 . The switching device of  claim 18 , wherein the device further comprising a control unit that controls the controller in performing a transfer of the portion of the routing information from the memory of the master control process into the local memory.  
   
   
       20 . The switching device of  claim 18 , wherein the cell is a packet including the destination address.  
   
   
       21 . The switching device of  claim 19 , wherein the control unit of the first device further comprising: 
 a buffer;    a plurality of queues including a pending queue; and    an arrival handling unit coupled to the pending queue, the arrival handling unit to place a pointer into the pending queue, the pointer being associated with a cell slot of the buffer into which the cell having the destination address is placed.    
   
   
       22 . The switching device of  claim 21 , wherein the control unit of the first device further comprising a route determination unit that sequentially removes pointers from the pending queue and determines where the cell having the destination address should be routed.  
   
   
       23 . The switching device of  claim 16 , wherein the first device is an interface card.  
   
   
       24 . The switching device of  claim 19 , wherein the controller and the control unit are implemented as separate circuitry.  
   
   
       25 . A switching device comprising: 
 a master control process including a memory to store routing information; and    a plurality of devices coupled together to exchange data over a first connection, each of the plurality of devices, being in communication with the master control process, comprises (i) a local memory adapted to contain a portion of the routing information stored in the memory of the master control process and (ii) a controller to receive the portion of the routing information from the memory of the master control process over a second connection separate of the first connection upon receiving data that includes a destination address about which no routing information is currently stored in the local memory.    
   
   
       26 . The switching device of  claim 25 , wherein the plurality of devices comprises 
 a first device that comprises (i) a first local memory including a first portion of the routing information stored in the memory of the master control process and (ii) a first controller to receive the first portion of the routing information from the memory of the master control process upon receiving data that includes a destination address about which no routing information is currently stored in the first local memory; and    a second device that comprises (i) a second local memory including a second portion of the routing information stored in the memory of the master control process and (ii) a second controller to receive the second portion of the routing information from the memory of the master control process upon receiving data that includes a destination address about which no routing information is currently stored in the second local memory.    
   
   
       27 . The switching device of  claim 26 , wherein the second portion of the routing information stored in the second local memory differs from the first portion of the routing information stored in the first local memory.  
   
   
       28 . The switching device of  claim 25 , wherein the portion of the routing information is a subset of the routing information stored in the memory of the master control process.  
   
   
       29 . The switching device of  claim 26 , wherein the master control process is coupled to each of the plurality of devices via the second connection being a multiple line bus that interconnects the first controller and the second controller.  
   
   
       30 . The switching device of  claim 25 , wherein at least a first device of the plurality of devices further comprises a control unit that controls the controller to perform a transfer of the portion of the routing information from the memory of the master control process into the local memory.  
   
   
       31 . The switching device of  claim 30 , wherein the control unit of the first device further comprising: 
 a buffer;    a plurality of queues; and    an arrival handling unit coupled to at least one of the plurality of queues, the arrival handling unit to place a pointer into an entry of the one of the plurality of queues, the pointer being associated with a location of the buffer into which the data having the destination address is placed.    
   
   
       32 . The switching device of  claim 31 , wherein the data is a cell.  
   
   
       33 . The switching device of  claim 32 , wherein the control unit of the first device further comprising a route determination unit that sequentially removes pointers from the one of the plurality of queues and determines where the cell having the destination address should be routed.  
   
   
       34 . The switching device of  claim 25 , wherein the master control process resides separately from the plurality of devices.  
   
   
       35 . The switching device of  claim 25 , wherein the memory of the master control process stores a card/port-to-address table to contain the routing information.  
   
   
       36 . The switching device of  claim 35 , wherein the routing information of the card/port-to-address table is indexed by performing a hash operation on at least a portion of the destination address.  
   
   
       37 . The switching device of  claim 35 , wherein an address space of the memory of the master control process is non-overlapping with address spaces of the local memories associated with the plurality of devices.  
   
   
       38 . The switching device of  claim 26 , wherein an address space of the memory of the master control process is non-overlapping with an address space of the first local memory associated with the first device and an address space of the second local memory associated with the second device.  
   
   
       39 . The switching device of  claim 38 , wherein the address spaces of the first local memory and the address space of the second local memory are non-overlapping.  
   
   
       40 . The switching device of  claim 39 , wherein the first controller is adapted to receive routing information contained in the second local memory of the second device.  
   
   
       41 . The switching device of  claim 25 , wherein the local memory contains the portion of the routing information by either (i) reading the portion of the routing information from the memory of the master control process or (ii) writing the portion of the routing information to the local memory.  
   
   
       42 . The switching device of  claim 35  wherein at least one of the plurality of devices is an interface card, the first connection being a bus and the second connection being a backplane.  
   
   
       43 . A switching device comprising: 
 a memory to store the routing information; and    a plurality of components in communication with the memory, each of the plurality of components including a local memory to store a table featuring a portion of the routing information and a memory controller to receive particular routing information from the memory upon receiving a cell that includes a destination address about which the particular routing information is currently not stored.    
   
   
       44 . The switching device of  claim 43 , wherein the plurality of components are a plurality of interface cards.  
   
   
       45 . The switching device of  claim 43 , wherein the portion of the routing information stored in a local memory of a first component of the plurality of components differs from the portion of the routing information stored in a local memory of a second component of the plurality of components.  
   
   
       46 . The switching device of  claim 43 , wherein the portion of the routing information is a subset of the routing information stored in the memory of a master control process.  
   
   
       47 . The switching device of  claim 43 , wherein the cell is a packet including the destination address.  
   
   
       48 . A switching device comprising: 
 a first connection;    a second connection;    a master control process coupled to the second connection, the master control process including a memory to store routing information; and    a first device coupled to the first connection and the second connection, the first device comprising a local memory and a memory controller to read the routing information from the memory of the master control process via the second connection upon receiving data that includes a destination address about which no routing information is currently stored in the local memory; and    a second device coupled to the first device via the first connection to transfer data to the first device and further coupled to the master control process via the second connection, the second device comprises a local memory and a memory controller to read the routing information from the memory of the master control process via the second connection upon receiving data that includes a destination address about which no routing information is currently stored in the local memory.    
   
   
       49 . The switching device of  claim 48 , wherein the second connection is a multiple line bus that interconnects the memory controller of the first device with the memory controller of the second device.  
   
   
       50 . The switching device of  claim 48 , wherein the memory controller of the first device with the memory controller of the second device exclusively using the second connection to read the routing information from the memory of the master control process.  
   
   
       51 . A method comprising: 
 exchanging data between a plurality of components coupled together by a first connection and collectively forming a switching device;    reading routing information;    inspecting a local table to determine if an entry associated with the routing information is stored within the local table;    using information from the entry for routing a cell if an entry of the local table associated with the routing information is stored within the local table;    accessing information from a central table over a second connection separate and independent from the first connection if no entry associated with the routing information is stored within the local table; and    receiving the information from the central table for use in routing the cell having the routing information.    
   
   
       52 . The method of  claim 51  further comprising: 
 storing the information from the central table into the local table for subsequent use upon receipt of the cell including the routing information.    
   
   
       53 . The method of  claim 51 , wherein the cell is a packet including a destination address.  
   
   
       54 . The method of  claim 53 , wherein the reading of the routing information from the cell includes reading the destination address of the packet.  
   
   
       55 . The method of  claim 53 , wherein the inspecting of the local table includes performing a hashing operation on the destination address of the cell to produce a result, the result being used as an index for the local table.  
   
   
       56 . The method of  claim 51 , wherein the accessing of the information from the central table is conducted by a direct memory access from one of the plurality of components to a master process control located remotely from the one of the plurality of components.  
   
   
       57 . A method comprising: 
 receiving a cell over a port coupled to a first memory of a first device of a switching device, the first device being coupled to a second device over a first connection to exchange data;    reading routing information from the cell;    inspecting a local table of the first memory to determine if an entry associated with the routing information is stored within the local table;    using information from the entry for routing the cell if an entry of the local table associated with the routing information is stored within the local table; and    populating the local table with information accessed from a secondary table stored in a second memory and retrieved over a second connection different than the first connection if no entry associated with the routing information is stored within the local table, the information being used for continued routing of the cell.    
   
   
       58 . The method of  claim 57 , wherein the cell is a packet including a destination address.  
   
   
       59 . The method of  claim 58 , wherein the inspecting of the local table includes performing a hashing operation on a destination address of the packet to produce a result, the result being used as an index for the local table.  
   
   
       60 . The method of  claim 59 , wherein the populating of the local table comprises exclusively using the second connection that is physically separate and independent from the first connection to route the information from the central table to the local table with the first connection being used to transfer information from the cell other than the routing information between the first and second devices of the switching device.  
   
   
       61 . The method of  claim 57 , wherein the populating of the local table includes accessing an entry of the secondary table of the second memory having an address space non-overlapping with an address space assigned to the first memory using a direct memory access operation.  
   
   
       62 . A method comprising: 
 storing data from a first connection into a location within a buffer;    snooping address information from the data detected on the first connection;    placing the address information and a pointer to the location into an entry of a queue;    determining a routing destination based on the address information; and    transmitting the data from the location within the buffer of the device based on the routing information.