Method and apparatus for processing and forwarding data packets

Abstract

The method and the apparatus for processing and forwarding data packets (pkt) in a computer network comprise at least one route table that contains entries each having an input index field (s-in), an operation code or a program (op) for the execution of an operation and an output selector field (s-out). The data packets (pkt) to be processed are each assigned a selector (sel) serving as indexing datum, the data packet (pkt) and the selector (sel) together constituting a token. The selector (sel) of a packet is matched with the input index field (s-in) of the entries of said at least one route table and the operation (op) contained in the matched route table entry or route table entries is/are executed on the matched token. This processing step can be repeated if the operation (op) results in one or more output token/tokens. Since according to the invention, programs to be executed on data packets (pkt) are stored in the route table, data packets (pkt) are directly processed in the fast data path, while at the same time the router can be dynamically reprogrammed.

1 . A method for processing and forwarding data packets comprising the steps of: 
 providing at least one route table comprising entries, at least one of which contains an input index field and at least one operation code for an action other than forwarding data packets or a program for the execution of a respective operation,    assigning a selector serving as indexing datum to each data packet, the data packet and its selector being parts of a token,    matching of the selector of a packet matched with the input index field of the entries of said at least one route table,    execution on the matched token of the at least one operation contained in the at least one matched route table entry.    
   
   
       2 . An apparatus for processing and forwarding data packets wherein the following items are provided: 
 at least one route table comprising entries, at least one of which contains an input index field and at least one operation code for an action other than forwarding data packets or a program for the execution of a respective operation,    means for assigning a selector serving as indexing datum to each data packet, the data packet and its selector being parts of a token,    means for matching the selector of a packet with the input index field of the entries of said at least one route table,    means for executing on the matched token the at least one operation contained in the at least one matched route table entry.    
   
   
       3 . The apparatus of  claim 2 , comprising at least one microprocessor the architecture of which implements at least one of said items.  
   
   
       4 . The method of  claim 1 , wherein tokens can be temporarily removed from said at least one multi-set and reinserted later on.  
   
   
       5 . The method of  claim 1 , wherein a control unit is provided which selects the tokens from the multi-set to be matched with entries of the route table.  
   
   
       6 . The method of  claim 1 , wherein the route table comprises at least one entry containing one of operation code and a program that can take care of at least one of entering parts of the contents of a data packet containing operation code into a route table entry and of removing or changing existing route table entries.  
   
   
       7 . The method of  claim 1 , wherein at least one of operation code and of a program contained in at least one route table entry comprises a reference to one of an externally installed subroutine and at least one of any other software and hardware based device serving as an extension.  
   
   
       8 . The method of  claim 7 , wherein the route table comprises at least one entry containing at least one of operation code and of a program that can take care of altering an extension or other modules based on information contained in a data packet.  
   
   
       9 . The method of  claim 6 , wherein at least one token containing operation code is assigned a program flow and that at least one of the operation code and its selector and of other data stored in this token is formed such that this program flow is executed based on information contained in the token and in the route table.  
   
   
       10 . The method of  claim 1 , wherein tokens for which no match with entries of the route table is possible, are deleted.  
   
   
       11 . The method of  claim 1 , wherein at least one default processing routine is provided and wherein tokens for which no match with an input index field of an entry of the at least one route table is possible are processed by one of said at least one default processing routines.  
   
   
       12 . The method of  claim 1 , wherein the at least one route table is implemented as an array or set of records having the structure of regular or consecutive memory zones, linked lists of memory zones, trees of memory zones or combinations thereof.  
   
   
       13 . The method of  claim 1 , wherein one or more auxiliary hash table or indirection pointer are provided to access the entries of said at least one route table.  
   
   
       14 . The method of  claim 1 , wherein at least one route table entry contains more than one operation.  
   
   
       15 . The method of  claim 1 , wherein the selection of route table entries that match a given token is non-deterministic.  
   
   
       16 . The method of  claim 1 , wherein a token's indexing datum is one of being embedded in and of being deductible from the token's data packet.  
   
   
       17 . The method of  claim 8 , wherein at least one token containing operation code is assigned a program flow and that at least one of the operation code and its selector and of other data stored in this token is formed such that this program flow is executed based on information contained in the token and in the route table.  
   
   
       18 . The method of  claim 12 , wherein one or more auxiliary hash table or indirection pointer are provided to access the entries of said at least one route table.