Lucent Technologies Inc.

Paolo Narvaez-Guarnieri

Hong-Yi Tzeng

Kai-Yeung S Siu

This invention is an algorithm that restores routing in a link-state network after a link failure without flooding the entire routing area with new routing information. The algorithm operates only in the local neighborhood of the failed link and informs the minimum number of routers about the failure.

Fault-tolerant non-flooding routing

A novel data structure in a router helps to compute viable next hops for forwarding a data packet from a router to its destination along multiple alternate loop-free paths, which are not necessarily of shortest distance. Each viable next hop may also be specified with a degree of optimality, which enables a route to perform QoS routing and fault-tolerant routing efficiently. The data structure can be implemented as an add-on software to existing routing protocols and may be implemented in existing networks which use shortest path protocols, even where less than all of the routers use the data structure and multiple path scheme described herein.

Multiple path routing

Method for computing a shortest path tree structure for nodes in an interconnected network comprising the steps of maintaining a data structure T consisting of a set of edges e interconnecting the plurality of nodes in the network, each node having an associated parent node and distance value attributes; determining a weight change .DELTA. of an edge; obtaining a set of candidate nodes having associated parent and distance attributes that are affected by the weight change; selecting a node of the set of candidate nodes; identifying one or more descendents of the selected node and calculating a new distance attribute for each of the one or more descendents; searching for other nodes connected to the one or more identified descendent nodes and determining whether they should be included in the data structure T; and, repeating the selecting, identifying, calculating, searching and determining steps until all nodes of the set of candidate nodes are selected to update the data structure T.

Growing community of inventors

Middlesex, MA, United States of America

Paolo Narvaez-Guarnieri