Collective network routing

Abstract

Disclosed are a unified method and apparatus to classify, route, and process injected data packets into a network so as to belong to a plurality of logical networks, each implementing a specific flow of data on top of a common physical network. The method allows to locally identify collectives of packets for local processing, such as the computation of the sum, difference, maximum, minimum, or other logical operations among the identified packet collective. Packets are injected together with a class-attribute and an opcode attribute. Network routers, employing the described method, use the packet attributes to look-up the class-specific route information from a local route table, which contains the local incoming and outgoing directions as part of the specifically implemented global data flow of the particular virtual network.

1 . A method of routing data packets in a computer network having a multitude of nodes and a multitude of links connecting the nodes together, each data packet including a class identifier, the method comprising: 
 each node, for each of a defined set of data packets,    looking at the data packet to identify the class of the data packet; and    routing the data packet from the node based on the identified class of the data packet.    
   
   
       2 . A method according to  claim 1 , wherein each node includes a route descriptor table including one or more route descriptors, each route descriptor (i) specifying a route from the node, and (ii) being associated with one of a plurality of packet classes, and wherein the routing step includes the steps of, 
 each node, for each of the defined set of data packets,    identifying the route descriptor, in the route descriptor table of the node, associated with the class of the data packet; and    routing the data packet on the route specified by the identified route descriptor.    
   
   
       3 . A method according to  claim 2 , wherein each node includes one or more channels, and each route descriptor table includes an array of registers comprising at least two bits for each channel of the node in which the descriptor table is located.  
   
   
       4 . A method according to  claim 1 , wherein at each node, the defined set of data packets includes data packets received at the node and data packets originated at the node.  
   
   
       5 . A method as specified in  claim 1 , wherein an opcode associated with each packet or packet class indicates that the plurality of selected, specified input directions defines a local collective of packets which is subject to the said collective packet operation.  
   
   
       6 . A method as specified in  claim 5 , wherein the identified collective of packets is subject to arithmetical/logical data processing operations to combine the members of the packet collective thereby reducing the number of packets to be routed through the network.  
   
   
       7 . A method as specified in  claim 5 , wherein the identified collective of packets is subject to arithmetical/logical data processing operations to compute a number of resulting packets based on the data of the identified packet collective without reducing the number of packets to be routed through the network.  
   
   
       8 . An apparatus for routing data packets in a computer network having a multitude of nodes and a multitude of links connecting the nodes together, each data packet including a class identifier, the apparatus comprising: 
 a plurality of checking means, each of the checking means being located at a respective one of the nodes for checking each of a defined set of data packets, to identify the class of the data packet; and    a plurality of routing means, each of the routing means being located at a respective one of the nodes to route data packets from the node based on the class of the data packets.    
   
   
       9 . Apparatus according to  claim 8 , further comprising a plurality of route descriptor tables, each of the route descriptor tables being located at a respective one of the nodes, each route descriptor table including one or more route descriptors, each route descriptor (i) specifying a route in the network and (ii) being associated with one of a plurality of packet classes, and wherein each routing means includes: 
 means for identifying the route descriptor, in the route descriptor table at the node at which the routing means is located, associated with the identified class of the data packet; and    means for directing the data packet onto the route specified by the identified route descriptor.    
   
   
       10 . Apparatus according to  claim 9 , wherein each node includes one or more channels, and each route descriptor table includes an array of registers comprising at least two bits for each channel of the node in which the descriptor table is located.  
   
   
       11 . Apparatus according to  claim 8 , wherein, at each node, the defined set of data packets includes data packets received at the node and data packets originated at the node.  
   
   
       12 . A method as specified in  claim 8 , wherein an opcode associated with each packet or packet class indicates that the plurality of selected, specified input directions defines a local collective of packets which is subject to the said collective packet operation.  
   
   
       13 . A method as specified in  claim 8 , wherein in addition to packet routes also specifies a plurality of nodes on the network which participate in a particular collective operation, comprising two additional bits per local route descriptor; one bit corresponding to the local contribution of the actual node to the said collective operation and another bit correlating to the local reception of the results of the said operation.  
   
   
       14 . The method specified in  claim 13 , wherein the packet class and opcode information is also subject to a collective operation such as but not limited to substituting the class or opcode with certain predefined values or increment/decrement operations.  
   
   
       15 . The method specified in  claim 14 , wherein the packet class and/or opcode information is being utilized to apply pre-processing steps, such as reverting the word order, to the data locally injected and/or to apply post-processing steps to the said data.  
   
   
       16 . A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for routing data packets in a computer network having a multitude of nodes and a multitude of links connecting the nodes together, each data packet including a class identifier, said method steps comprising: 
 each node, for each of a defined set of data packets,    looking at the data packet to identify the class of the data packet; and    routing the data packet from the node based on the identified class of the data packet.    
   
   
       17 . A program storage device according to  claim 16 , wherein each node includes a route descriptor table including one or more route descriptors, each route descriptor (i) specifying a route from the node, and (ii) being associated with one of a plurality of packet classes, and wherein the routing step includes the steps of, 
 each node, for each of the defined set of data packets,    identifying the route descriptor, in the route descriptor table of the node, associated with the class of the data packet; and    routing the data packet on the route specified by the identified route descriptor.    
   
   
       18 . A program storage device according to  claim 17 , wherein each node includes one or more channels, and each route descriptor table includes an array of registers comprising at least two bits for each channel of the node in which the descriptor table is located.  
   
   
       19 . A program storage device according to  claim 16 , wherein at each node, the defined set of data packets includes data packets received at the node and data packets originated at the node.  
   
   
       20 . A program storage device according to  claim 16 , wherein an opcode associated with each packet or packet class indicates that the plurality of selected, specified input directions defines a local collective of packets which is subject to the said collective packet operation.  
   
   
       21 . A program storage device according to  claim 20 , wherein the identified collective of packets is subject to arithmetical/logical data processing operations to combine the members of the packet collective thereby reducing the number of packets to be routed through the network.  
   
   
       22 . A method of identifying a collective of data packets on a computer system, the computer system including a multitude of interconnected processing nodes, and wherein a multitude of data packets are routed in the computer system, the method comprising the steps of: 
 allocating a class identifier to identify a given class of data packets;    providing each data packet in said given class with said class identifier;    providing each of the nodes with a set of channels for receiving and holding data packets; and    each of at least some of the nodes, 
 i) identifying a subset of the set of channels of the node,  
 ii) evaluating the data packets at the node to identify the class of the data packet, and  
 iii) identifying said collective as complete when all of the channels of said subset have a data packet of the given class.  
   
   
   
       23 . A method according to  claim 22 , wherein each of said at least some of the nodes includes a route descriptor table identifying routes for data packets from said node, and further comprising the step of using the route descriptor table to identify a route for the collective of data packets from the node.  
   
   
       24 . A method according to  claim 22 , further comprising the step of initializing the plurality of local route descriptors to reflect the local flow of data for the desired global operation associated with that class by selectively enabling the desired input and output directions.  
   
   
       25 . A method according to  claim 24 , further comprising the steps of: 
 using the class identifier of the incoming packets to select one of the local route descriptors; and    using the selected route descriptor to determine the plurality of valid input and output directions.    
   
   
       26 . A method according to  claim 25 , further comprising the step of comparing the incoming direction of the packet with the specified incoming directions of the packet class to determine whether the packet is to be routed to the specified output directions or to the specified input directions.  
   
   
       27 . A method as specified in  claim 26 , wherein an opcode associated with each packet or packet class indicates that the plurality of selected, specified input directions defines a local collective of packets which is subject to the said collective packet operation.  
   
   
       28 . A method a specified in  claim 27 , wherein the identified collective of packets is subject to arithmetical/logical data processing operations to combine the members of the packet collective thereby reducing the number of packets to be routed through the network.