Patent ID: 7152113

Claim:
A method for adding routing information for a new node to a routing table with a plurality of entries that reflect an existing deadlock-free set of paths through a network of nodes, wherein the routing table has a row for each source node in the network and a column for each destination node in the network and wherein a table entry located at an entry row and an entry column identifies a link that can be used to send data from the source node in the entry row to the destination node in the entry column, the method comprising: forming an ordered set of deadlock-free sub-topologies of said network, each sub-topology comprising links that are not used in any other sub-topology; generating said routing table as a function of said ordered set of deadlock-free sub-topologies; adding to the routing table, a row including a plurality of entries, each entry identifying a link that directly connects the new node to a neighbor node that can be connected, via existing deadlock-free paths described by the table, to a destination node associated with the entry column; and adding to the routing table a column including a plurality of entries, each entry identifying a link that can be used to connect a source node associated with the entry row, via existing deadlock-free paths described by the table, to a neighbor node that can be directly connected to the new node, wherein the paths defined in the routing table continue to define deadlock-free paths in the network after addition of the row and column for the new node.