Patent ID: 8098593

Claim:
A method for generating a path for routing a packet in a multi-level interconnection network of devices, the method comprising: providing a packet to be sent from a source device to a destination device of the network; identifying a closest common ancestor cell of the source device and the destination device, the closest common ancestor cell being the lowest level cell that contains both the source device and the destination device; when the closest common ancestor cell is a basic cell, establishing the path as an inter-basic cell path between the source device and the destination device; and when the closest common ancestor cell is not a basic cell, identifying an inter-cell link between a source-side device of a child cell of the closest common ancestor cell that contains the source device and a destination-side device of the child cell of the closest common ancestor cell that contains the destination device; identifying a source-side path from the source device to the source-side device; identifying a destination-side path from the destination-side device to the destination device; and establishing the path as a concatenation of the source-side path, the inter-cell link, and the destination-side path.