Patent ID: 7203191

Claim:
A method for loop-free multipath routing of data in a network, comprising: (a) maintaining at each node i in a network, (i) a main distance table (MDT) containing D j i and p j i , where D j i is the distance of node i to destination j and p j i is the predecessor to destination j on the shortest path from i to j, (ii) said MDT further containing, for each destination j, successor set S j i , feasible distance FD j i , reported distance RD j i , and flags designated as changed and report-it, (iii) a main link table (MLT) T i which is the node's view of the network and contains links represented by (m, n, d) where (m, n) is a link with cost d, (iv) a neighbor distance table (NDT) for neighbor k containing D jk i and p jk i where D jk i is the distance of neighbor k to j as communicated by k and p jk i is the predecessor to j on the shortest path from k to j as notified by k, (v) a neighbor link table (NLT)T k i which is the view that neighbor k has of the network as known to i and contains link information derived from the distance and predecessor information in the NDT, and (vi) an adjacent link table (ALT) containing the cost l k i of an adjacent link to each neighbor k, wherein said cost is infinity if a link is down; (b) in response to receipt of an update message M from a neighbor k, detection of a change in cost of an adjacent link to k, or detection of a change in status of an adjacent link to k, (i) updating the NDT and NLT for neighbor k with links (m, n, d) where d=D nk i −D mk i and m=p nk i , and (ii) constructing an MLT for neighbor k by merging topologies T k i and adjacent links l k i ; and (c) routing data through a loop-free path in the network; wherein at least one said loop-free path is determined using information in each of said tables at each node i.