Abstract:
The invention provides a method and system for rapid access to one or more M-tries for responding to header information. The M-tries are stored in a plurality of memory banks, which are accessed in parallel to provide relatively greater access throughput. Parts of the M-tries that are (or are expected to be) frequently referenced are stored in multiple banks of the memory, to provide concurrent simultaneous access for those parts of the M-tries for parallel lookup of multiple routes. Regions of the multiple banks of the memory can be dynamically reallocated to provide improved access through-put to those multiple banks. The invention can be applied to routing decisions in response to destination addresses, to combinations of destination and source addresses (either for unicast or multicast routing), to access control decisions, to quality of service decisions, to accounting, and to other administrative processing in response to header information.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to routing table lookup. 
     2. Related Art 
     In a computer network, routing devices receive messages at one of a set of input interfaces, and forward them on to one of a set of output interfaces. It is advantageous for such routing devices to operate as quickly as possible, to keep up with the rate of incoming messages. In a packet routing network, each packet includes a header, including information used for routing the packet to an output interface for forwarding to a destination device (or to another routing device for further forwarding). Header information used for routing can include a destination address, a source address, and other information such as a destination device port, a source device port, a protocol, packet length, and a priority for the packet. Header information used by routing devices for other administrative tasks can include information about access control, accounting, quality of service, and other purposes. 
     One problem in the known art is that there can be a relatively large number of possible destinations, and therefore a correspondingly large number of possible output interfaces (herein called “routes”), one of which is to be associated with the incoming packet. It is advantageous for the routing devices to match the associated output interface with the incoming packet as quickly as possible. Due to the nature of routing in computer networks, it is also advantageous for the routing devices to match the associated output interface with the longest possible sub-string of the header information (such as the destination address or a combination of the destination address and the source address). 
     One method in the known art is to use a branching tree, which differentiates among possible routes in response to each individual bit of the header information. A variant of this method is to generate an M-way branching tree (herein called an “M-trie,” which has up to M possible branches at each node). An M-trie differentiates among possible routes in response to groups of bits in the header information. 
     One problem in the known art is that using M-tries generates frequent references to memory to access the nodes of the M-trie. The access speed of the memory thus provides a limitation on the speed of the routing device. Moreover, some of the nodes of the M-trie near its root are relatively more frequently referenced than other nodes. The access speed of the memory for repeated references to the same location thus provides a second limitation on the speed of the routing device. 
     Accordingly, it would be desirable to provide a method and system for rapid access to one or more M-tries for responding to header information. This advantage is achieved in an embodiment of the invention in which the M-tries are stored in a plurality of memory banks, some of which duplicate parts of the M-tries that are frequently referenced. 
     SUMMARY OF THE INVENTION 
     The invention provides a method and system for rapid access to one or more M-tries for responding to header information. The M-tries are stored in a plurality of memory banks, which are accessed in parallel to provide relatively greater access throughput. Parts of the M-tries that are (or are expected to be) frequently referenced are stored in multiple banks of the memory, to provide concurrent simultaneous access to those parts of the M-tries for parallel lookup of multiple routes. 
     In a preferred embodiment, regions of the multiple banks of the memory can be dynamically reallocated to provide improved access throughput to those multiple banks. The invention can be applied to routing decisions in response to destination addresses, to combinations of destination and source addresses (either for unicast or multicast routing), to access control decisions, to quality of service decisions, to accounting, and to other administrative processing in response to header information. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows a block diagram of an improved system for routing table lookup. 
     FIG. 2 shows a memory data structure in an improved method for routing table lookup. 
     FIG. 3 shows a timing diagram for use of a receive or transmit memory. 
     FIG. 4 shows a flowchart for recording and using a routing table. 
     FIG. 5 shows possible contents of an M-trie. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     In the following description, a preferred embodiment of the invention is described with regard to preferred process steps and data structures. Those skilled in the art would recognize after perusal of this application that embodiments of the invention can be implemented using circuits adapted to particular process steps and data structures described herein, and that implementation of the process steps and data structures described herein would not require undue experimentation or further invention. 
     System Elements 
     FIG. 1 shows a block diagram of an improved system for routing table lookup. 
     A system  100  for routing table lookup includes one or more routers  110 . 
     The router  110  is coupled to a set of physical interfaces  111  for receiving and for transmitting packets  112  from non-router devices. The router  110  is also coupled to one or more fabric interfaces  113  for receiving and for transmitting packets  112  to the network fabric. 
     Each router  110  includes a set of device interface elements  120  PLIM, a receive element  130  Rx, a lookup table  140 , a set of memory controllers  150 , memory  160 , one or more fabric interface elements  170 , and a transmit element  180 . 
     The device interface elements  120  are coupled to the physical interfaces  111 , and are disposed for receiving and for transmitting packets  112 . 
     The receive element  130  Rx is coupled to the device interface elements  120  and to the lookup table  140 . The receive element  130  operates in conjunction with the lookup table  140  to perform receive operations on received packets  112 . These receive operations can include determining packet  112  integrity, isolating routing information from a set of packet headers  113  of the packets  112 , and other functions. 
     A receive memory controller  150  is coupled to the receive element  130  and to a receive memory  160 . The receive memory controller  150  operates in conjunction with the receive memory  160  to determine routing treatments for received packets  112 . These routing treatments can include one or more of the following: 
     selection of one or more output interfaces to which to forward received packets  112 ; 
     Selection can be responsive to the destination device, to the source and destination device, or to network flows as described in one or more of the following patent applications. 
     U.S. application Ser. No. 08/581,134, now U.S. Pat. No. 6,091,725, titled “Method For Traffic Management, Traffic Prioritization, Access Control, and Packet Forwarding in a Datagram Computer Network”, filed Dec. 29, 1995, in the name of inventors David R. Cheriton and Andreas V. Bechtolsheim, assigned to Cisco Technology, Inc.; 
     U.S. application Ser. No. 08/655,429, titled “Network Flow Switching and Flow Data Export”, filed May 28, 1996, in the name of inventors Darren Kerr and Barry Bruins, and assigned to Cisco Technology, Inc.; and 
     U.S. application Ser. No. 08/771,438, titled “Network Flow Switching and Flow Data Export”, filed Dec. 20, 1996, in the name of inventors Darren Kerr and Barry Bruins, assigned to Cisco Technology, Inc., 
     PCT International Application PCT/US 96/20205, titled “Method For Traffic Management, Traffic Prioritization, Access Control, and Packet Forwarding in a 
     Datagram Computer Network”, filed Dec. 18, 1996, in the name of inventors David R. Cheriton and Andreas V. Bechtolsheim, and assigned to Cisco Technology, Inc.; and 
     U.S. application Ser. No. 08/886,900, Express Mail Mailing No. EM053698725US, titled “Network Flow Switching and Flow Data Export”, filed Jul. 2, 1997, in the name of inventors Darren Kerr and Barry Bruins, assigned to Cisco Technology, Inc. 
     Each of these applications is hereby incorporated by reference as if fully set forth herein. These applications are collectively referred to herein as the “Netflow Routing Disclosures.” 
     Selection can also be responsive to unicast routing, multicast routing, or a combination thereof 
     determination of ACL (access control list) treatment for received packets  112 ; 
     determination of QoS (quality of service) treatment for received packets  112 ; 
     determination of one or more accounting records or treatments for received packets  112 ; and 
     determination of other administrative treatment for received packets  112 . 
     The receive memory  160  includes routing treatment information, disposed in a memory data structure responsive to information in packet  112  and it&#39;s packet header. The memory data structure is further described with regard to FIG.  2 . 
     The fabric interface elements  170  couple the router  100  to communication links to other routers  110  in the network fabric. 
     A transmit memory controller  150  is coupled to the fabric interface elements  170  and to a transmit memory  160 . The transmit memory controller  150  operates in conjunction with the transmit memory  160  to determine routing treatments for packets  112  for transmission. These routing treatments can be similar to the routing treatments for received packets  112  and can include one or more of the same treatments. 
     The transmit memory  160  includes routing treatment information, disposed in a memory data structure similar to that of the receive memory  160 . 
     The transmit memory controller  150  is coupled to the transmit element  180  Tx. The transmit element  180  operates to perform transmit operations on packets  112  for transmission. These transmit operations can include rewriting packet headers, altering routing information in the packet headers, and other functions. 
     Memory Data Structure 
     FIG. 2 shows a memory data structure in an improved method for routing table lookup. 
     In a preferred embodiment, the memory data structure is like that described for M-Tries in one or more of the Netflow Routing Disclosures. 
     The receive memory  160  includes at least one tree structure  200  (sometimes known as a “trie” structure), as described for M-Tries in one or more of the Netflow Routing Disclosures. Each tree structure  200  includes a set of nodes  210 , one of which is designated as a root node  210 , and a set of leaves  220 . The root node  210  and each other node  210  include a set of entries  211 , each of which points to either a sub-node  210  or to an associated leaf  220 . 
     Each leaf  220  includes a set of information for a routing treatment to be used for packets  112 . As noted herein, the routing treatment can include one or more of the following: 
     one or more output interfaces to which to forward packets  112 ; 
     ACL treatment for packets  112 ; 
     QoS treatment for packets  112 ; 
     accounting treatments for packets  112 ; and 
     other administrative treatment for packets  112 . 
     In a preferred embodiment in which each node  210  provides 16 bits of branching width, each node  210  includes sufficient entries  211  to use 64K bytes of the memory  160 . At least one region  220  of the memory  160  is about 64K bytes and is used for the root node  210 . In alternative embodiments, each node  210  may provide a different amount of branching width, such as 4 bits, 8 bits, 12 bits, or some variable responsive to the nature of the packet traffic. 
     Parallel Memory Operation 
     FIG. 3 shows a timing diagram for use of a receive or transmit memory. 
     The receive memory  160  includes an SDRAM (synchronous dynamic random access memory), having a plurality of memory banks  300 . As known in the art of computer memories, each memory bank  300  can be accessed separately and in parallel using a memory activate signal  310  and a memory read signal  320 . In response to the memory activate signal  310  and the memory read signal  320 , the memory  160  provides a data output signal  330 . 
     In a preferred embodiment, the receive memory  160  includes four memory banks  300  (bank  0 , bank  1 , bank  2 , and bank  3 ). The receive memory controller  150  provides a periodic sequence of four memory activate signals  310  (A 0 , A 1 , A 2 , and A 3 ) and four memory read signals  320  (R 0 , R 1 , R 2 , and R 3 ), and receives a periodic sequence of four data output signals  330  (D 0 , D 1 , D 2 , and D 3 ). Thus, the four memory banks  300  are effectively operated in parallel to provide quadruple the amount of throughput of a single memory bank  300 . 
     In a preferred embodiment, each memory bank  300  of the receive memory  160  operates at a cycle speed of about 80 nanoseconds. The memory activate signal  310  A 0  is presented to memory bank  300  bank 0  at an offset of about 0 nanoseconds into the cycle. The memory read signal  320  R 0  is presented to memory bank  300  bank 0  at an offset of about 30 nanoseconds into the cycle. The data output signal  330  D 0  is presented from the memory bank  300  bank 0  at an offset of about 60 nanoseconds into the cycle, and lasts about 20 nanoseconds to read out about 32 bits of data. CIS- 043   
     The memory activate signal  310 , memory read signal  320 , and data output signal  330  occur at offsets in the cycle that are similarly related. 
     Distributed Storage of the M-tries 
     The various nodes  210  of the tree structure  200  are recorded in the memory  160  in the various memory banks  300 . The receive memory controller  150  allocates the nodes  210  (and associated sub-trees depending from those nodes  220 ) of the tree structure  200  so that concurrent access in referencing those nodes  210  can be optimized. This optimization can include the following: 
     (1) the root node  210  is recorded in multiple banks  300 ; 
     (2) other frequently referenced nodes  210  are stored in multiple banks  300 ; and 
     (3) nodes  210  are dynamically reallocated to new regions of the multiple banks  300 . 
     In the first optimization, because the root node  210  is so frequently referenced, it is recorded in each memory bank  300 . 
     In the second optimization, those nodes  210  that are frequently referenced are copied to multiple memory banks  300 . The memory controller  150  can determine whether particular nodes  210  are sufficiently frequently referenced by maintaining a reference or frequency count at the node  210  or in a separate table. Those nodes  210  that are referenced often can be copied to two of the four memory banks  300 , while those nodes  210  that are referenced even more often can be copied to three or four of the four memory banks  300 . Similarly, those nodes  210  that have been copied to multiple memory banks  300  but are no longer frequently referenced, are deleted from one or more memory banks  300  to restrict them to fewer memory banks, down to a single memory bank  300 . 
     In the third optimization the receive memory controller  150  determines whether particular memory banks  300  have recorded nodes  210  that are collectively relatively infrequently or relatively frequently referenced. If a first memory bank  300  has a collection of nodes  210  that are much more frequently referenced than a second memory bank  300 , it can occur that concurrent use of the memory  160  is reduced by frequent attempts at multiple access to the same contested memory bank  300 . Accordingly, in these cases, the receive memory controller  150  reallocates at least some nodes  210  from the first to the second memory bank  300 . Similarly, if the frequency of references to sets of recorded nodes  210  changes, the receive memory controller  150  re-reallocates at least some nodes  210  from the first to the second memory bank  300  or vice versa. 
     Recording and Using Routing Table 
     FIG. 4 shows a flowchart for recording and using a routing table. Step S 401  shows recording an M-trie in memory banks. At least one node  210  is recorded in at least two memory banks. 
     Steps S 402  and/or S 403  can follow step S 401 . In step S 402 , at least two memory banks are accessed in parallel. One node recorded in plural memory banks can be accessed concurrently. In step S 403 , nodes are dynamically reallocated. Nodes can be reallocated, for example, responsive to access frequency, changes in access frequency, throughput, and other factors. 
     M-trie Contents 
     FIG. 5 shows possible contents of an M-trie. M-tie  400  can include access control information, accounting information, information for responding to packets, quality of service information, multicast information, routing decision information (responsive to source and/or destination addresses), and/or unicast information. Other information can be included. 
     Alternative Embodiments 
     Although preferred embodiments are disclosed herein, many variations are possible which remain within the concept, scope, and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application. 
     For example, as noted herein, the invention has wide applicability to a variety of operations possibly performed by routers.