Patent ID: 8364844

Claim:
A computer implemented method for constructing routes for data packets in a multi-dimensional computer network, said network comprising a plurality of interconnected compute nodes, said network overlayed by one or more subrectangles for performing collective operations, the method comprising: routing a data packet among nodes along one dimension towards a root node, each node having input and output communication links, said root node not having any outgoing uplinks; classifying the data packet into one of three classes, the three classes including: a first class associated with a reduction in a network traffic in the multi-dimensional computer network, a second class associated with security and reliability of each node in the multi-dimensional computer network while reducing the network traffic in the multi-dimensional computer network, a third class associated with a subset of nodes in the multi-dimensional computer network; determining, based on a class of the classified data packet, whether the classified data packet can be further routed along the one dimension in the multi-dimensional computer network and if so, further routing the classified data packet according to the class of the classified data packet toward an edge of a subrectangle for the one dimension; while routing the classified data packet according to the class of the classified data packet toward the edge of the subrectangle for the one dimension, determining at each node if the classified data packet has reached the edge of the subrectangle for the one dimension, and if the classified data packet has reached the edge of the subrectangle for the one dimension, determining if the classified data packet has reached the root node, and if the classified data packet has not reached the root node, routing the classified data packet among nodes along another dimension towards the root node.