State information and routing table updates in large scale data networks

• US 6,744,775 B1
• Filed: 09/27/1999
• Issued: 06/01/2004
• Est. Priority Date: 09/27/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Vickers, Richard, Beshai, Maged E.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): PHAM, BRENDA H
• Application Number:
  US09/405,003
• Time in Patent Office: 1,709 Days
• Field of Search: 370/237, 370/248, 370/395.31, 370/395.32, 370/395.2, 370/399, 370/393, 370/409
• US Class Current: 370/409
• CPC Class Codes: H04L 12/28 characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks] wireless communication networks H04W ; arrangements for dividing the transmission path H04W40/00
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

In a communication network comprising nodes and links between the nodes, a controller node disseminates link state information. A nodal routing table exists at each node comprising routes between pairs of nodes. The nodal routing table is either populated by the given node based on network information received from the controlling node or populated at the controlling node and received by given node. Each node receives heartbeat signals from its neighbouring nodes. An unexpected delay between hearbeat signals may be perceived as a failure of a link. The preceived failure of that link is reported by the perceiving node to the controlling node. Upon receiving link failure information from a node, the controlling node may determine a subset of nodes in the network influenced by the link failure and indicate the link failure to the determined subset of influenced nodes.

Claims

1. At a controller of a network, said network comprising nodes and links between said nodes, a method of disseminating link state information to said nodes, said method comprising:

populating an overall routing table for said network, where said overall rotating table comprises a plurality of nodal routing tables, where one of said nodal routing tables corresponds to a particular node and comprises a plurality of routes between said particular node and other said nodes in said network;

distributing each one of said nodal routing tables to each said node to which said each one of said nodal routing tables corresponds;

ascertaining link state change information;

determining a subset of nodes in said network influenced by said link state change information; and

indicating said link state change information to said subset of nodes.

2. The method of claim 1 wherein said populating said overall routing table comprises determining a route set for each node pair, wherein a node pair comprises a source node and a sink node and wherein a method of determining said route set comprises:

for each link emanating from said source node,

determining a metric-optimised route from a node at the end of said each link to said sink node; and

associating with said metric optimised route a sum of the metric of said each link and the cumulative metric of said metric optimised route; and

sorting said metric optimised routes in ascending order by said associated sum.

3. The method of claim 2 wherein said method of determining said route set further comprises limiting said route set to a first predetermined number of said metric optimised routes, wherein said predetermined number is an integer greater than zero and less than the number of links emanating from said source node.

4. The method of claim 2 further comprising predetermining a metric optimised matrix, said pre-determining comprising:

determining a metric optimised route from each node in said network to each other node in said network;

storing each said metric optimised route in said metric optimised matrix;

and wherein sad determining said metric optimised route from the node at the end of said each link to said sink node comprises consulting said metric optimised matrix.

5. The method of claim 4 further comprising, for each node in said network, identifying nodes along a route, wherein said metric is optimised, from said each node to said each other node in said network by employing Dijkstra'"'"'s Algorithm, with a graph of said network and said each node as input.

6. The method of claim 2 wherein said sorting further comprises:

(a) italicizing a ranked set with a route in said route set with the least associated sum;

(b) until all routes in said route set are in said ranked set;

(i) for each route not in said ranked set,

determining an intersection level value, where said intersection level value for a given route is equivalent to the number of links said given route has in common with routes in said ranked set;

determining, from said associated sum and said intersection level value, a composite index;

(ii) adding to said ranked set a route with the least composite index;

(c) sorting said routes in said ranked set in ascending order by said composite index.

7. The method of claim 2 wherein said subset determining comprises computing an inversion of said overall Touting table, wherein said inversion of said overall routing table relates a particular link to each node whose route set includes a route utilising said particular link.

8. The method of claim 1 further comprising indicating said link state change information to at least one other controller.