초록 ▼

A system for maintaining routing tables at each router in a computer network. The system is based on (a) a feasibility condition that provides multiple loop-free paths through a computer network and that minimizes the amount of synchronization among routers necessary for the correct operation of a r

A system for maintaining routing tables at each router in a computer network. The system is based on (a) a feasibility condition that provides multiple loop-free paths through a computer network and that minimizes the amount of synchronization among routers necessary for the correct operation of a routing algorithm, and (b) a method that manages the set of successors during the time it synchronizes its routing-table update activity with other routers, in order to efficiently compute multiple loop-free paths, including the shortest path, through a computer network.

대표청구항 ▼

[ We claim:] [1.] A method of maintaining multiple loop-free paths between a source node and a destination node in a computer network, the source node being a router, a computer, or a special-purpose device; the destination node being a computer, a router, a device, or a network connected to the sou

[ We claim:] [1.] A method of maintaining multiple loop-free paths between a source node and a destination node in a computer network, the source node being a router, a computer, or a special-purpose device; the destination node being a computer, a router, a device, or a network connected to the source node either directly or through one or more intermediate nodes; each intermediate node being a computer, a router, or a special-purpose device; and the method comprising the following steps:(a) generating a list of neighbor nodes, each neighbor node being adjacent to and directly connected to the source node;(b) generating a list of neighbor-node lengths, each neighbor-node length being measured on a link or an attached network from the source node to a corresponding one of the neighbor nodes;(c) generating a list of the neighbor-to-destination lengths, each neighbor-to-destination length being measured from one of the neighbor nodes to the destination node;(d) generating a list of the smallest value of the neighbor-to-destination length being measured from each of the neighbor nodes to the destination node;(e) generating the shortest loop-free path length, the shortest loop-free path length representing the length of a shortest loop-free path from the source node to the destination node;(f) generating the feasible length, the feasible length representing the smallest value of the shortest loop-free path length;(g) selecting a successor set comprised of successor nodes, each successor node being the next node along a loop-free path from the source to the destination node;(h) determining whether a condition has been met that may cause the source to change its set of successor nodes or its shortest loop-free path length;(i) performing the following steps, in the event the condition has been met:(j) selecting those neighbor nodes for whom the smallest values of their adjacent-to-destination lengths are smaller than the feasible length;(k) storing each selected neighbor node as a successor node in the successor set, each successor node being the next node along a loop-free path from the source node to the destination node;(l) for each neighbor node in the successor set, adding the neighbor-to-destination length to its corresponding neighbor node length, each sum forming a distance from the source node to the destination node through one of the selected neighbor nodes;(m) storing each corresponding distance as a loop-free path length from the source node to the destination node through the given neighbor node;(n) determining the smallest loop-free path length;(o) storing the smallest loop-free path length as the shortest loop-free path length;(p) selecting the neighbor nodes for whom the sum of the neighbor-to-destination length and the corresponding neighbor-node length equal the shortest path length;(q) storing each selected neighbor in the shortest-path set.