Methods and systems for network address lookup engines

Abstract

Internet routers are a key component in today's Internet. Each router forwards received packets toward their final destinations based upon a Longest Prefix Matching (LPM) algorithm select an entry from a routing table that determines the closest location to the final packet destination among several candidates. Prior art solutions to LPM lookup offer different tradeoffs and that it would be beneficial for a design methodology that provides for low power large scale IP lookup engines addressing the limitations within the prior art. According to embodiments of the invention a low-power large-scale IP lookup engine may be implemented exploiting clustered neural networks (CNNs). In addition to reduced power consumption embodiments of the invention provide reduced transistor count providing for reduced semiconductor die footprints and hence reduced die cost.

What is claimed is: 
     
         1 . A device comprising;
 a clustered neural network processing algorithms storing ternary data.   
     
     
         2 . The device according to  claim 1  wherein;
 the ternary data comprises data having values of either 0, 1, or don't care. 
 
     
     
         3 . The device according to  claim 1 ;
 wherein the device only stores data as binary weighted connections between clusters of the clustered neural network.   
     
     
         4 . The device according to  claim 1  wherein;
 input data to the device comprises a network address of a plurality of network addresses according to a predetermined standard, each network address relating to a destination of a packet of data received at a system comprising at least the device; and 
 output data from the device comprises a rule for routing the packet of data; wherein the plurality of addresses and their associated rules are stored as associations within the device without the requirement for an additional rule specific memory. 
 
     
     
         5 . A device comprising:
 a first plurality of input clusters forming a first predetermined portion of a clustered neural network, each input cluster comprising of a first predetermined number of input neurons; and   a second plurality of output clusters forming a second predetermined portion of the clustered neural network, each output cluster comprising a second predetermined number of output neurons; wherein,   the clustered neural network stores a plurality of network addresses and routing rules relating to the network addresses as associations.   
     
     
         6 . The device according to  claim 5  wherein,
 the clustered neural network operates using ternary data, the ternary data comprising data having values of either 0, 1, or don't care. 
 
     
     
         7 . The device according to  claim 5 ;
 wherein the device only stores data as binary weighted connections between clusters of the clustered neural network.   
     
     
         8 . A method comprising;
 providing an address lookup engine for a routing device employing a clustered neural network capable of processing ternary data;   teaching the address lookup engine about a plurality of addresses and their corresponding rules for routing data packets received by the routing device in dependence upon at least an address forming a predetermined portion of the data packet; and   routing data packets using the address lookup engine.   
     
     
         9 . The method according to  claim 8  wherein,
 providing the address lookup engine comprises:
 providing a first plurality of input clusters forming a first predetermined portion of the clustered neural network, each input cluster comprising of a first predetermined number of input neurons; and 
 providing a second plurality of output clusters forming a second predetermined portion of the clustered neural network, each output cluster comprising a second predetermined number of output neurons; wherein, 
 the clustered neural network stores a plurality of network addresses and routing rules relating to the network addresses as associations.