Patent ID: 7379424
Filing Date: 2008-05-27
Classification: H04L

Abstract:
1. In a multiprocessor computer system having a plurality of processing nodes and physical communication links interconnecting the processing nodes in a predefined topology, wherein each processing node includes a processor, a router and a local memory, wherein the physical communication links connect a router in one processing node to a router in another processing node, and wherein each router consults a routing table resident within its associated processing node when deciding where to route a message from one processing node to an adjacent processing node, a method of building a routing table, comprising: a) determining all single hops for each processing node; b) querying each adjacent node for its single hop routes; c) determining if all nodes can be reached; d) if all nodes cannot be reached, setting x=2; e) querying each adjacent node for its “x” hop routes; f) eliminating all routes to a particular node that are longer than existing routes from the node where the routing table will reside to that particular node; g) eliminating all routes that introduce a cyclic dependency; h) choosing a preferred route to the particular node among the routes that have not been eliminated by either f or g; i) determining if all nodes can now be reached; j) if all nodes cannot be reached, setting x=x+1 and repeating e through j; and k) if all nodes can be reached, building the routing table.