Hierarchical address translation system for a network switch

• US 5,754,791 A
• Filed: 03/25/1996
• Issued: 05/19/1998
• Est. Priority Date: 03/25/1996
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: I-Cube, Inc.
• Inventors: Dahlgren, Kent Blair, Bedell, Daniel J.
• Primary Examiner(s): Treat, William M.
• Application Number:
  US08/622,764
• Time in Patent Office: 785 Days
• Field of Search: 370/400-402, 395/200.15, 395/200.68-200.74
• US Class Current: 709/242
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/1576 Crossbar or matrix
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags

Abstract

A network switch routes data transmissions between uniquely addressed network stations connected to input and output ports of the switch. The switch includes a hierarchical address translation system for relating network addresses of stations to receive incoming transmission to the switch ports to which they are connected. The translation system includes a central translation unit having a memory for storing a mapping entry for each network station, the entry mapping the station'"'"'s network address to its switch port. The system also includes a local translation unit in each input port. Each local translation unit contains a local cache memory for storing a smaller subset of the mapping entries stored by the central translation unit. When a data transmission arrives at an input port directed to a network address, the input port looks for an entry in its cache memory mapping that network address to an output port. Upon finding such an entry in its cache memory, the input port directs the incoming data transmission to that output port. When not finding such an entry in its cache memory, the input port obtains a copy of the appropriate mapping entry from the central translation unit, stores it as a new mapping entry in its cache memory and then directs the data transmission the output port identified by the new mapping entry.

Claims

1. A network switch for routine data transmissions between uniquely addressed network stations, each data transmission including an address of the station to which the transmission is being sent the network switch comprising:

a plurality of input ports, each receiving data transmissions from a separate one of said network stations, and for generating routing requests;

a plurality of output ports, each forwarding data transmissions to a corresponding one of said network stations;

routing means for selectively routing data transmissions from said input ports to said output ports in accordance with routing requests generated by said input ports; and

a central translation unit for storing a plurality of mapping entries, each mapping entry corresponding to a separate network station and mapping the address of the corresponding network station to an output port to which the station is connected;

wherein each input port includes a cache memory for storing copies of a portion of said mapping entries stored in said central address translation unlit,

wherein upon receiving a data transmission from a network station, any one of said input ports already storing in its cache memory an entry mapping an address conveyed in the data transmission to an output port transmits a routing request to said routing means causing said routing means to route the data transmission from the input port to the output part mapped by the cache memory entry.

wherein upon receiving a data transmission from a network station, any one of said input ports not already having in its cache memory an entry mapping an address conveyed in the data transmission to an output port obtains such mapping entry from said central translation unit, stores the obtained mapping entry in its cache memory, and transmits a routing request to said routing means causing said routing means to route the data transmission to the output port mapped the obtained mapping entry,

wherein each output port has associated therewith a unique port ID and each mapping entry includes a network address and a corresponding port ID.

wherein said cache memory comprises a plurality of cache units, each cache unit storing a separate mapping entry, each cache unit receiving an address included in each data transmission received by the input port and providing its stored port ID as a cache memory output when the received address matches the cache unit'"'"'s stored address and

wherein the input port generates the routing request transmitted to said routing means in accordance with the port ID output of the cache memory,

wherein each input port further comprises means for receiving input LOCK data from an external source, the LOCK data identifying at least one of said cache unit mapping entries as being locked, and

wherein the input port stores the obtained mapping entry into a one of the cache units not identified by said input lock data as being locked.

2. The network switch in accordance with claim 1 wherein the an input port stores an obtained mapping entry into a particular one of the cache units not identified as being locked which maps a network address least recently received by the cache units not identified as being locked.

3. A network switch for routing data transmissions between uniquely addressed network stations, each data transmission including an address of the station to which the transmission is being sent, the network switch comprising:

a plurality of input ports, each receiving data transmissions from a separate one of said network stations, and for generating routing requests;

a plurality of output ports each forwarding data transmissions to a corresponding one of said network stations;

routing means for selectively routing data transmissions from said input ports to said output ports in accordance with routing requests generated by said input ports; and

a central translation unit for storing a plurality of mapping entries, each mapping entry corresponding to a separate network station and mapping the address of the corresponding network station to an output port to which the station is connected;

wherein each input port includes a cache memory for storing copies of a portion of said mapping entries stored in said central address translation unit,

wherein upon receiving a data transmission from a network station, any one of said input ports already storing in its cache memory an entry mapping an address conveyed in the data transmission to an output port transmits a routing request to said routing means causing said routing means to route the data transmission from the input port to the output port mapped by the cache memory entry,

wherein upon receiving a data transmission from a network station, any one of said input ports not already having in its cache memory an entry mapping an address conveyed in the data transmission to an output port obtains such mapping entry from said central translation unit, stores the obtained mapping entry in its cache memory, and transmits a routing request to said routing means causing said routing means to route the data transmission to the output port mapped by the obtained mapping entry,

wherein each output port has associated therewith a unique port ID and each mapping entry includes a network address and a corresponding port ID,

wherein said cache memory comprises a plurality of cache units, each cache unit storing a separate mapping entry, each cache unit receiving an address included in each data transmission received by the input port and providing its stored port ID as a cache memory output when the received address matches the cache unit'"'"'s stored address,

wherein the input port generates the routing request transmitted to said routing means in accordance with the port ID output of the cache memory,

wherein when an input port stores an obtained mapping entry into a particular one of the cache units mapping a network address least recently received by the cache units,

wherein each cache unit maintains a miss count of a number of consecutive times it receives an address included in a data transmission which does not match its mapped address and resets its count when it receives an address matching its mapped address, and wherein said input port stores the obtained mapping entry in the cache unit having a highest miss count,

wherein each cache unit has a unique cache unit ID,

wherein each of said cache units are interconnected in series so that each cache unit other than a first cache unit of said series receives as input a miss count and a cache unit ID output from a preceding cache unit of said series,

wherein each cache unit provides as output its own miss count and cache unit ID when its own miss count is less than its received miss count and provides its received miss count and cache unit ID as output when its own miss count exceeds its received miss count, and

wherein said input port stores the obtained mapping entry in the cache unit identified by the cache unit ID output of a last cache unit of said series.

4. A network switch for routing data transmissions between uniquely addressed network stations, each data transmission including an address of the station to which the transmission is being sent, the network switch comprising:

a plurality of input ports each receiving data transmissions from a separate one of said network stations, and for generating routing requests;

a plurality of output sorts, each forwarding data transmissions to a corresponding one of said network stations;

routing means for selectively routing data transmissions from said input ports to said output ports in accordance with routing requests generated by said input ports; and

a central translation unit for storing a plurality of mapping entries, each mapping entry corresponding to a separate network station and mapping the address of the corresponding network station to an output port to which the station is connected;

wherein each input port includes a cache memory for storing copies of a portion of said mapping entries stored in said central address translation unit,

wherein upon receiving a data transmission from a network station, any one of said input ports already storing in its cache memory an entry mapping an address conveyed in the data transmission to an output port transmits a routing request to said routing means causing said routing means to route the data transmission from the input port to the output port mapped by the cache memory entry,

wherein upon receiving a data transmission from a network station, any one of said input ports not already having in its cache memory an entry mapping an address conveyed in the data transmission to an output port obtains such mapping entry from said central translation unit, stores the obtained mapping entry in its cache memory, and transmits a routing request to said routing means causing said routing means to route the data transmission to the output port mapped by the obtained mapping entry,

wherein each output port has associated therewith a unique port ID and each mapping entry includes a network address and a corresponding port ID,

wherein said cache memory comprises a plurality of cache units, each cache unit storing a separate mapping entry, each cache unit receiving an address included in each data transmission received by the input port and providing its stored port ID as a cache memory output when the received address matches the cache unit'"'"'s stored address,

wherein the input port generates the routing request transmitted to said routing means in accordance with the port ID output of the cache memory,

wherein when an input port stores an obtained mapping entry into a particular one of the cache units mapping a network address least recently received by the cache unit,

wherein each cache unit maintains a miss count of a number of consecutive times it receives an address included in a data transmission which does not match its mapped address and resets its count when it receives an address matching its mapped address, and wherein said input port stores the obtained mapping entry in the cache unit having a highest miss count,

wherein each cache unit includes an input for receiving an externally generated LOCK signal,

wherein each cache unit has a unique cache unit ID;

wherein each of said cache units are interconnected in series so that each cache unit other than a first cache unit of said series receives as input a miss count and a cache unit ID output from a preceding cache unit of said series,

wherein each cache unit provides as output its own miss count and cache unit ID when its own miss count is less than its received miss count and its input LOCK signal is not asserted, and provides its received miss count and cache unit ID as output when its own miss count exceeds its received miss count and when its LOCK signal is asserted, and

wherein said input port stores the obtained mapping entry in the cache unit identified by the cache unit ID output of a last cache unit of said series.

5. A hierarchical address translation system for a network switch having a plurality of ports, each port receiving incoming source addresses from a separate source, and each port having a unique identification number (ID), for mapping incoming source address to an ID of a port receiving the incoming source address, the system comprising:

a bus;

a central translation unit connected to said bus for receiving and storing a plurality of mapping entries, each mapping entry mapping a source address to a corresponding port ID; and

a plurality of local translation units, each corresponding to a separate one of said ports, each local translation unit comprising a cache memory for storing a subset of the mapping entries stored by said central translation unit and means for receiving incoming source addresses from a separate one of said sources, and upon receiving an incoming source address not already stored in a mapping entry of its cache memory transmitting the source address and an ID of the corresponding port as a mapping entry to the central translation unit via said bus for storage thereby.

6. A hierarchical translation system for receiving incoming input data values from a plurality of sources and producing an output data value corresponding to each input data value, the system comprising:

a bus for conveying data values;

a central translation unit connected to said bus for storing a plurality of mapping entries, each mapping entry mapping an input data value to a corresponding output data value, and for transmitting an output data value on said bus in response to an input data value received via said bus; and

a plurality of local translation units, each local translation unit comprising a cache memory for storing a subset of the mapping entries stored by said central translation unit and means for receiving incoming input data values from a separate one of said sources, and upon receiving an incoming input data value already stored in a mapping entry of its cache memory providing an output data value stored in that mapping entry as system output, and upon receiving an incoming input data value not already stored in a mapping entry of its cache memory transmitting the input data value to the central translation unit via said bus, receiving a corresponding data value from the central translation unit via said bus, storing the incoming input data value and received output data value as a new mapping entry in its cache memory, and providing the received output data value as system output,

wherein said cache memory comprises a plurality of cache units, each cache unit storing one of said mapping entries, each cache unit receiving the incoming input data value and providing its stored output data value as a system output when the incoming data value matches the cache unit'"'"'s stored input data value,

wherein when one of said local translation units stores a new mapping entry in its cache memory, it replaces an existing mapping entry stored in a particular one of the cache units replacing an existing mapping entry in one of the cache units containing an input data value having least recently matched an incoming input data value,

wherein each cache unit maintains a miss count of a number of consecutive times it receives an incoming input data value which does not match its stored input data value and resets its count when it receives an incoming input data value matching its stored input data value, and wherein each local translation unit stores the new mapping entry in one of its cache units having a highest miss count,

wherein each cache unit has a unique cache unit ID;

wherein the cache units of each local translation unit are interconnected in series whereby each cache unit other than a first cache unit of said series receives as input a miss count and a cache unit ID output from a preceding cache unit of said series,

wherein each cache unit provides as output its own miss count and cache unit ID when its own miss count is less than its received miss count and provides as output its received miss count and cache unit ID when its own miss count exceeds its received miss count, and

wherein each local translation unit stores the new mapping entry in the cache unit identified by the cache unit ID output of a last cache unit of said series.

7. A hierarchical translation system for receiving incoming input data values from a plurality of sources and producing an output data value corresponding to each input data value, the system comprising:

a bus for conveying data values;

a central translation unit connected to said bus for storing a plurality of mapping entries, each mapping entry mapping an input data value to a corresponding output data value, and for transmitting an output data value on said bus in response to an input data value received via said bus; and

a plurality of local translation units, each local translation unit comprising a cache memory for storing a subset of the mapping entries stored by said central translation unit and means for receiving incoming input data values from a separate one of said sources, and upon receiving an incoming input data value already stored in a mapping entry of its cache memory providing an output data value stored in that mapping entry as system output, and upon receiving an incoming input data value not already stored in a mapping entry of its cache memory transmitting the input data value to the central translation unit via said bus, receiving a corresponding data value from the central translation unit via said bus, storing the incoming input data value and received output data value as a new mapping entry in its cache memory, and providing the received output data value as system output,

wherein said cache memory comprises a plurality of cache units, each cache unit storing one of said mapping entries, each cache unit receiving the incoming input data value and providing its stored output data value as a system output when the incoming data value matches the cache unit'"'"'s stored input data value,

wherein when one of said local translation units stores a new mapping entry in its cache memory, it replaces an existing mapping entry stored in a particular one of the cache units replacing an existing mapping entry in one of the cache units containing an input data value having least recently matched an incoming input data value,

wherein each cache unit maintains a miss count of a number of consecutive times it receives an incoming input data value which does not match its stored input data value and resets its count when it receives an incoming input data value matching its stored input data value, and wherein each local translation unit stores the new mapping entry in one of its cache units having a highest miss count,

wherein each cache unit includes an input for receiving an externally generated LOCK signal,

wherein each cache unit of each local translation unit has a unique cache unit ID;

wherein the cache units of each local translation unit are interconnected in series so that each cache unit other than a first cache unit of said series receives as input a miss count and a cache unit ID output from a preceding cache unit of said series,

wherein each cache unit provides as output its own miss count and cache unit ID when its own miss count is less than its received miss count and its input LOCK signal is not asserted, and provides its received miss count and cache unit ID as output when its own miss count exceeds its received miss count and when its LOCK signal is asserted, and

wherein each local translation unit stores the new mapping entry in the cache unit identified by the cache unit ID output of a last cache unit of said series.