Abstract:
A high quality network is provided that eliminates the sorting time for sorting through registering look-up conditions, such as source and destination MAC addresses, in a content addressable memory, by generating a routing or flow control look-up key, and then selectively activating some of the physical banks in the content addressable memory with the look-up key during look-up for the look-up conditions. The look-up key is generated by extracting a part or all of the data contained in a packet header.

Description:
CLAIM OF PRIORITY 
   The present application claims priority from Japanese application JP 2004-349265 filed on Dec. 2, 2004, the content of which is hereby incorporated by reference into this application. 
   FIELD OF THE INVENTION 
   The present invention relates to a data transfer device which performs routing and packet flow control, and more specifically, reduces power consumption during content addressable memory access. 
   BACKGROUND OF THE INVENTION 
   Data transfer devices which form a communication network, such as a layer 2 switch, IP router or layer 3 switch, transfer a received Ethernet (Ethernet: proprietary product name) frame, IP packet or MPLS packet transmitted by the MPLS method, to an output circuit corresponding to the address data of this packet. To reduce power consumption in the data transfer device accompanying the increase in traffic, various power consumption reduction methods are being examined. 
   As a way of reducing power consumption during content addressable memory access, there is a method wherein look-up conditions are first arranged in a desired registration order in a content addressable memory, and rearranged in order of increasing (or decreasing) value (e.g., Patent document 1). At this time, the value of the look-up condition situated at the boundary of each physical bank in the content addressable memory is stored in a register. In this example, a data look-up device of low power consumption is provided by limiting the physical banks to be looked up by the value of the look-up key generated from the inputted data, when looking up the look-up condition using the content addressable memory by comparing with the value of this register, and activating only the limited physical banks. 
   In addition, there is a method wherein, to reduce power consumption in a content addressable memory for routing of received IP packets, a physical bank to be activated is decided by a hash function (e.g., Non-patent document 1). 
   [Patent document 1] JP-A No. 185792/2004 
   [Non-patent document 1] [Hidell et al], “Router Architectures” Tutorial at Networking 2004, http://www.imit.kth.se/˜mahidell/pubs/networking04_tutorial_final.pdf, pp. 41 
   SUMMARY OF THE INVENTION 
   In a method which arranges look-up conditions in a desired registration order, although they are arranged in a desired registration order at the beginning in the content addressable memory, whatever the look-up method may be, e.g., full match look-up or longest match look-up, the data in the content addressable memory always have to be rearranged. Therefore, a sorting time is always required for rearrangement when the network configuration changes or during initial registration. 
   Next, in the method which decides the physical bank to be activated by a hash function, only the look-up condition for routing the received IP packet is looked up, and the details of how to reduce power consumption method are not considered. 
   It is therefore an object of the invention, when performing a full match look-up of a content addressable memory, to provide a high quality network which does not incur a sorting time when registering look-up conditions, and to provide a data transfer device of low power consumption by limiting the physical banks to be activated when the look-up conditions are looked up. 
   In order to attain this object, the data transfer device of the invention comprises multiple physical banks in which a forwarding table and a flow identification table have identical look-up bit width, and a forwarding table management unit and a flow identification table management unit decide the physical bank to be looked up from a look-up key and commands look-up of this physical bank. 
   According to the present invention, a low power consumption type data transfer device which can limit the physical banks of a content addressable memory to be activated for a content addressable memory which requires full match look-up in the case of routing and flow control of received packets, can be provided. Moreover, when the network configuration is modified or during initial registration, since all the look-up conditions arranged in the content addressable memory do not have to be rearranged as in the prior art, registration of look-up condition data can be rapidly completed, and a high quality network can be provided which is easily maintained. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a block diagram showing one embodiment of a data transfer device  10  according to the invention; 
       FIG. 2  is a diagram showing one example of the format of a variable-length Ethernet frame inputted into the data transfer device  10 ; 
       FIG. 3  is a block diagram showing one embodiment of a routing unit  20 ; 
       FIG. 4  is a block diagram showing one embodiment of a flow control unit  30 ; 
       FIG. 5  is a diagram showing one embodiment of a forwarding table management unit  201 , and a diagram showing the relation between a forwarding table management unit  201  and a content addressable memory  200  for routing; 
       FIG. 6  is a diagram showing one embodiment of a flow identification table management unit  301 , and a diagram showing the relation between a flow identification table management unit  301  and content addressable memory  300  for flow control; 
       FIG. 7A  is a diagram showing the format of a routing information  700  stored in the entries of a routing table  204 . 
       FIG. 7B  is a diagram showing the format of a flow control information  800  stored in the entries of a flow control table  304  during an Ethernet frame transfer; 
       FIG. 8  is a diagram showing the format of a variable-length IP packet inputted into the data transfer device  10 ; 
       FIG. 9  is a block diagram showing one embodiment of a routing bank decision unit  212 ; 
       FIG. 10  is a block diagram showing one embodiment of a flow control bank decision unit  312 ; 
       FIG. 11  is a diagram showing a content addressable memory array  220  for routing; and 
       FIG. 12  is a diagram showing a content addressable memory array  320  for flow identification. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   First Embodiment 
   Hereafter, one embodiment of the invention will be described referring to the drawings. In order to easily make comparisons with the prior art, the case where the invention is applied to a data transfer device  10  of  FIG. 1  will be described. In addition, in the first embodiment, transfer of an Ethernet frame which requires a full match look-up in packet routing and flow control using a content addressable memory, is described. However, provided that the effect of the invention is obtained, the kind of the device to which the invention is applied and the type of packet are not limited thereto. 
     FIG. 1  is a block diagram of the data transfer device  10  according to the invention. 
   The data transfer device  10  comprises multiple interface modules  11 - i  (i=1 to N) connected to input circuits IN-i and output circuits OUT-i, respectively, a selector  12  and data relay unit  16  connected to these interface modules, a buffer memory  13 , a header sampling unit  14  and buffer control unit  15  connected to the selector  12 , and a routing unit  20  and flow control unit  30  connected to the data relay unit  16 .  60  represents a management terminal situated outside the data transfer device  10 , wherein a signal line L 10  is connected to the routing unit  20  and a signal line L 11  is connected to the flow control unit, which is operated by the administrator of the data transfer device  10 . 
     FIG. 2  shows one example of the format of a variable-length Ethernet frame received from the input circuits IN-i. A variable-length Ethernet frame  100  comprises a L 2  header  110  and L 2  payload  120  of a second layer (data link layer) in an OSI reference model. 
   The format of the L 2  header  110  changes according to the type of input circuit, for example when the input circuit IN-i is Ethernet, a destination MAC address  111 , source MAC address  112 , frame type  114  and other data are contained in the L 2  header  110 . In  FIG. 2 , a tag  113  is stored in the L 2  header  110  as the other data. 
   Here, the tag  113  comprises the Ethernet frame transfer priority in the data transfer device  10  and a network identifier which identifies the network to which the Ethernet frame belongs. 
   In  FIG. 1 , each interface module  11 - i  outputs the Ethernet frame received from the input circuit IN-i to a signal line L 1 - i . The selector  12  selectively outputs the Ethernet frames inputted from the signal line L 1 - i  to a signal line L 2  according to a control signal supplied via a signal line L 15  from the buffer control unit  15 . The header sampling unit  14  analyzes the L 2  header  110  of the Ethernet frame  100  outputted to the signal line L 2 , outputs the frame length shown in the frame type  114  to a signal line L 12 , outputs the destination MAC address  111  and source MAC address  112  to a signal line L 3 , and outputs the L 2  header  110  to a signal line L 4 . 
   The buffer control unit  15  performs write of the Ethernet frame  100  outputted to the signal line L 2  to the buffer memory  13  and read of the Ethernet frame  100  to the signal line L 6  from the buffer memory  13 . The buffer control unit  15 , based on the frame length which the header sampling unit  14  outputs to the signal line L 12 , controls write of the Ethernet frame to the buffer memory  13 , and together with read of the Ethernet frame from the buffer memory  13 , outputs a switching control signal of the selector  12  to the signal line L 15  and writes the following Ethernet frame to the buffer memory  13 . 
   The routing unit  20  looks up the matching look-up condition from the forwarding table  202  stored in the routing content addressable memory  200  based on the destination MAC address  111  outputted by the header sampling unit  14  to the signal line L 3 , as shown in  FIG. 3 . As a result of looking up the look-up conditions, when there is a match, routing information  700  is looked up from the routing table  204 . The routing information  700  contains data on the output interface module of the Ethernet frame, as shown in  FIG. 7A . The routing unit  20  outputs the routing information  700  to a signal line L 7 . 
   Simultaneously with the routing of the Ethernet frame, the routing unit  20  looks up the matching look-up condition from the forwarding table  202  stored in the routing content addressable memory  200  based on the source MAC address  112  which the header sampling unit  14  outputs to the signal line L 3 . If, as a result of this look-up, a matching look-up condition does not exist, the forwarding table management unit  201  transmits the L 2  header  110  of the Ethernet frame to a routing table administration unit  205  via a signal line L 22 . The routing table administration unit  205  outputs data required for updating the forwarding table  202  to the signal line L 22  based on the L 2  header  110 . 
   When performing dynamic routing, the routing table administration unit  205  outputs routing data according to a routing protocol to the signal line L 22  or L 23  connected to the forwarding table management unit  201  or the routing table management unit  203 . When performing static routing, it outputs routing data according to a setup inputted from the management terminal  60  connected via the signal line L 10 . 
   When an error is contained in the data outputted from the forwarding table  202  and routing table  204  which are accessed at the time of routing, the routing table error administration unit  206  notifies a routing table error from the forwarding table management unit  201  or routing table management unit  203  to the buffer control unit  15  via a signal line L 13 . If a routing table error is inputted from the signal line L 13  at this time, the buffer control unit  15  will interpret the routing as invalid, and will discard the Ethernet frames stored in the buffer memory  13 . 
   The flow control unit  30  looks up the matching look-up condition from the flow identification table  302  stored in the flow control content addressable memory  300  based on the L 2  header  110  which the header sampling unit  14  outputs to the signal line L 4 , as shown in  FIG. 4 . As a result of looking up the look-up conditions, when there is a match, flow control information  800  are looked up from the flow control table  304 . The flow control information  800  contains for example communication quality information  802  which shows a transmitting priority, and transfer propriety identifier  801 , as shown in  FIG. 7B . The flow control unit  30  outputs the transfer propriety identifier  801  to a signal line L 5 , and outputs the communication quality information  802  to a signal line L 8 . 
   More specifically, the flow control unit  30 , at a predetermined timing, requests the buffer control unit  15  to perform control of the received Ethernet frame  100  via the signal line L 5 . The buffer control unit  15  controls the Ethernet frame  100  according to the inputted transfer propriety identifier  801 . When transfer is performed, the buffer control unit  15  outputs the Ethernet frame to the signal line L 6  from the memory buffer  13 . When transfer is not performed, the Ethernet frame stored in the memory buffer  13  is discarded. 
   The flow control table administration unit  305  is connected to the management terminal  60  via a signal line L 11 . According to the flow control setup from the management terminal  60 , flow control information is outputted to a signal line L 32  or L 33  connected to the flow identification table management unit  301  or flow control table management unit  303 . When an error is contained in the data outputted from the flow identification table  302  and flow control table  304  which are accessed during flow control, the flow control table error administration unit  306 , notifies a flow control table error from the flow identification table management unit  301  or flow control table management unit  303  to the buffer control unit  15  via a signal line L 14 . 
   If a flow control table error is inputted from the signal line L 14  at this time, the buffer control unit  15  will interpret the flow control as invalid, and will discard the Ethernet frames stored in the memory buffer  13 . 
   The data relay unit  16 , when an Ethernet frame  100  is inputted from the signal line L 6 , outputs this to an interface module  11 - k  corresponding to an output port number k shown by the routing information  700  from the signal line L 7  according to the priority shown in the communication quality data  802  inputted from the signal line L 8 . 
     FIG. 5  shows the types of connection to the forwarding table management unit  201  and routing content addressable memory  200  applied to the routing unit  20  of the invention. For simplification, it will be assumed that the routing content addressable memory  200  comprises a routing content addressable memory array  220  and a routing priority encoder  210 , as shown in  FIG. 5 . The routing content addressable memory array  220  comprises multiple routing physical banks  2021 - i  (i=1 to N) containing one or more entries which store routing look-up data used as look-up conditions. 
   As shown in  FIG. 11 , look-up conditions such as, for example, the source address and destination address, are stored in the entries. A routing look-up key and source MAC address look-up key are inputted into the content addressable memory  200  for routing, and if there is a match with multiple entries of the forwarding table  202 , the routing priority encoder  210  outputs the minimum (or maximum) address of the matching entries to a signal line L 2108 . 
   According to the invention, in the routing of Ethernet frames and the registration of the routing information for the forwarding table  302 , the physical banks to be activated are limited by a routing bank decision unit  212 . 
   The forwarding table management unit  201  will now be described referring to  FIG. 5 . Based on the destination MAC address  111  and source MAC address  112  of the Ethernet frame  100 , a routing look-up key generation unit  211  generates the routing look-up key and source MAC address look-up key corresponding to each, and outputs them to a signal line L 2101 . A routing command generation unit  213  is then requested to look up the look-up condition matching the routing or source MAC address of the Ethernet frame via a signal line L 2102 . 
   When a look-up condition to be registered in the forwarding table  202  from the signal line L 22  is inputted, a routing look-up data generation unit  214  generates routing look-up data to be used as the look-up condition of the routing look-up key and source MAC address look-up key, and outputs the routing look-up data to a signal line L 2106 . It also requests write of the routing look-up data to the forwarding table  202  by outputting the routing look-up data to a signal line L 2107 . 
   The routing bank decision unit  212  takes the routing look-up data and source MAC address look-up key inputted from the signal line L 2101 , or the routing look-up key inputted from the signal line L 2106  as input, and outputs the activation power to the physical banks to be made active and the routing lookup key or routing look-up data to the routing content addressable memory  200 . The routing bank decision unit  212  comprises a routing hash function unit  2121  which calculates the numbers of the physical banks to be made active relative to the input by a hash function, a routing register  2122  connected to a signal line L 26 , and a routing hash value translation unit  2123  which converts the hash values calculated by the routing hash function unit  2121  to the values shown in the routing register  2122 , and decides the physical banks to be made active, as shown in  FIG. 9 . 
   The routing hash function unit  2121  calculates a surplus by dividing the routing look-up key and source MAC address look-up key by a number (m) of routing physical banks  2021 - i  having an identical look-up bit width used for routing. Let this surplus value be the hash value. The input routing look-up key and source MAC address look-up key, or routing look-up data and hash value, are then outputted to the routing hash value translation unit  2123 . At this time, the range of hash values is 0 to (m−1). 
   A discrepancy may arise in the hash values outputted depending on the routing look-up data inputted into the routing hash function unit  2121 . Hence, to eliminate hash value discrepancies as much as possible, as shown in  FIG. 9 , hash values are set in the routing register  2122  which shows the physical bank numbers to be made active corresponding to each hash value. 
   The operator of the data transfer device  10  performs setup of the routing register  2122  from the management terminal  60 . Here, the operator of the data transfer device  10  specifies the physical bank corresponding to the hash value. 
   When the routing look-up key and source MAC address look-up key or routing look-up data and hash value are inputted the routing hash value translation unit  2123  refers to the routing register  2122  and outputs the activation power for the physical bank corresponding to the hash value to a signal line L 2104 . At this time, the routing look-up key and source MAC address look-up key, or routing look-up data, are outputted to a signal line L 2103 . Standby power is supplied to the other physical banks. 
   When the routing look-up key and source MAC address look-up key are inputted from the signal line L 2102 , the routing command generation unit  213  generates a look-up command, and outputs it to a signal line L 2105 . Also, when the routing look-up data for the forwarding table  202  is inputted from the signal line L 2107 , a write command is generated and output to the signal line L 2105 . It may be noted that signal lines, such as a clock bus for the routing content addressable memory  200 , are connected to the routing command generation unit  213 , but are not shown in  FIG. 5 . 
   A routing result analysis unit  215 , in the routing content addressable memory  200  which stores the forwarding table  202 , analyzes whether the address of the entry which matches the routing look-up key outputted from the routing content addressable memory  200  as the look-up result of the forwarding table  202 , is valid or invalid. If it is invalid, this is notified to the routing table error administration unit  206  via a signal line L 24 . 
     FIG. 6  shows how the flow identification table management unit  301  applied to the flow control unit  30  of the invention is connected to the flow control content addressable memory  300 . For simplification, as shown in  FIG. 6 , the flow control content addressable memory  300  comprises a flow identification content addressable memory array  320 , and a flow control priority encoder  310 . The flow identification content addressable memory array  320  comprises multiple flow control physical banks  3021 - i  (i=1 to N) containing one or more entries which store flow control look-up data used as look-up conditions of the flow control look-up key. 
   As shown in  FIG. 12 , look-up conditions such as a source address, destination address, source port number and destination port number are stored in the entries. 
   The flow control look-up key is inputted into the flow control content addressable memory  300 , and if there are matches with multiple entries of the flow identification table  202 , the flow control priority encoder  310  outputs the minimum (or maximum) address of the matching entries to a signal line L 3108 . 
   According to the invention, in the flow control of Ethernet frames and the registration of flow control information for the flow control table  302 , the physical banks to be activated are limited by a flow control bank decision unit  312 . 
   The flow identification table management unit  301  will now be described referring to  FIG. 6 . Based on a combination of the destination MAC address  111  of the L 2  header  110  and network identifier contained in the tag  113 , a flow control look-up key generation unit  311  generates the flow control look-up key and outputs it to a signal line L 3101 . A flow control command generation unit  313  is then requested for a flow identification to which the input Ethernet frame belongs via the signal line L 3102 . 
   When the operator of the data transfer device  10  inputs the data elements of the look-up conditions from the management terminal  60 , the flow control look-up data generation unit  314  generates flow control look-up data to be used as look-up conditions of the flow control look-up key, and outputs the flow control look-up data to the signal line L 3106 . Also, it requests write of the flow control look-up data to the flow identification table  302  via the signal line L 3107 . 
   The flow control bank decision unit  312  uses the flow control look-up key inputted from signal line L 3101  or the flow control look-up data inputted from the signal line L 3106  as input, and outputs the activation power to the physical banks to be made active and the flow control look-up key or flow control look-up data to the flow control content addressable memory  300 . The flow control bank decision unit  312  comprises a flow control hash function unit  3121  which calculates the numbers of the physical banks to be made active relative to the input by a hash function, a flow control register  3122  connected to a signal line L 36 , and a flow control hash value translation unit  3123  which converts the hash values calculated by the flow control hash function unit  3121  to the values shown in the flow control register  3122 , and decides the physical banks to be made active, as shown in  FIG. 10 . 
   The hash function unit  3121  for flow control calculates a surplus by dividing the flow control look-up key or flow control look-up data by a number (m) of flow control physical banks  3021 - i  having an identical look-up bit width used for flow control. Let this surplus value be the hash value. The input flow control look-up key or flow control look-up data and the hash value, are then outputted to the flow control hash value translation unit  3123 . At this time, the range of hash values is 0 to (m−1). 
   A discrepancy may arise in the hash values outputted depending on the flow control look-up data inputted into the flow control hash function unit  3121 . Hence, to eliminate discrepancies of hash values as much as possible, as shown in  FIG. 10 , hash values are set in the flow control register  3122  which shows the physical bank numbers to be made active corresponding to each hash value. 
   The operator of the data transfer device  10  performs setup of the flow control register  3122  from the management terminal  60 . Here, the operator of the data transfer device  10  specifies the physical bank corresponding to the hash value. 
   When the flow control look-up key or flow control look-up data and hash value are inputted, the flow control hash value translation unit  3123  refers to the flow control register  3122  and outputs the activation power for the physical bank  3021 - i  corresponding to the hash value to a signal line L 3104 . At this time, the flow control look-up key or flow control look-up data are outputted to a signal line L 3103 . Standby power is supplied to the other physical banks. 
   When the flow control look-up key is inputted from the signal line L 3102 , the flow control command generation unit  313  generates a look-up command, and outputs it to a signal line L 3105 . Also, when the flow control look-up data for the flow identification table  302  is inputted from the signal line L 3107 , a write command is generated and output to the signal line L 3105 . It may be noted that signal lines such as a clock bus for the flow control content addressable memory  300  are connected to the flow control command generation unit  313 , but are not shown in  FIG. 6 . 
   The flow control result analysis unit  315 , in the flow control content addressable memory  300  which stores the flow identification table  302 , analyzes whether the address of the entry which matches the flow control look-up key outputted from the flow control content addressable memory  300  as the look-up result of the flow identification table  302 , is valid or invalid. If it is invalid, this is notified to the flow control table error administration unit  306  via a signal line L 34 . 
   The routing hash function unit  2121  and flow control hash function unit  3121  always use the same calculation method for registration of routing look-up data and look-up of the forwarding table  202  by the routing look-up key, or registration of flow control look-up data and look-up of the flow identification table  302  by the flow control look-up key, respectively. Therefore, it is possible to match the routing look-up data and routing look-up key, and to match the flow control look-up data and flow control look-up key, when an Ethernet frame is received. 
   Although it was not mentioned in this aspect, the packet is not limited to an Ethernet frame, and may be a MPLS packet transmitted by the MPLS method. Thus, in the forwarding table  202  which the routing look-up key and routing look-up data access, and the flow identification table  302  which the flow control look-up key and flow control look-up data access, the routing bank decision unit  212  and flow control bank decision unit  312  not only reduce power consumption of the content addressable memory by limiting the physical banks to be activated, but when there is a change of network configuration and during initial registration, rearrangement of look-up conditions registered in the entries of the content addressable memory as in the prior art is not required, so registration of look-up conditions can be completed in a short period of time. 
   Second Embodiment 
   In the second embodiment, the case will be described where, in an IP router and layer  3  switch, flow control of IP packets transferred between networks which designate a specific source and destination, is performed. 
   First, one example of the format of a variable-length IP packet  400  is shown in  FIG. 8 . As shown in  FIG. 8 , the IP packet  400  comprises a IP payload  401  and IP header  402 , the IP header  402  containing a packet control data  403 , source IP address  404  and destination IP address  405 . The packet control data  403  means IP header data other than the IP address, e.g., the service type such as protocol classification, packet size and packet priority. 
   The flow control look-up key generation unit  311  generates flow control look-up data which are flow control look-up conditions from a combination of the protocol classification which is contained in the packet control data  403 , source IP address  404  and destination IP address  405 . 
   The flow control bank decision unit  312  then uses the flow control look-up data as input to decide the flow control physical bank  3021 - i  which registers the flow control look-up data. 
   Next, the flow control of received IP packets will be described. The data transfer device  10  functions as in the first embodiment also during transfer of the IP packets. 
   The difference from the first embodiment is that, when the flow control look-up key generation unit  311  generates the flow control look-up key, it uses a combination of the protocol classification contained in the packet control data  403 , source IP address  404  and destination IP address  405  of the inputted IP packets. Also, the header sampling unit  14  outputs a IP header  402 . 
   In an IP packet transfer, the same data as in the first embodiment is stored in the flow control table  304 . At this time, the flow control unit  30  performs the same operations as in the first embodiment. Further, the flow control hash function unit  3121  always uses the same calculation method for registration of flow control look-up data and look-up of the flow identification table  302  by the flow control look-up key. 
   Therefore, when a specific IP packet is received, the flow control look-up data and flow control look-up key can be matched. 
   According to the invention, in data transfer devices such as a layer 2 switch, IP router and layer 3 switch, power consumption in a content addressable memory can be reduced during packet routing and flow control, and regarding the registration of look-up conditions, a communication service which can rapidly respond to network configuration changes can be provided. 
   The invention can be applied to a data transfer device which uses a content addressable memory for packet routing and flow control.