State information and routing table updates in large scale data networks

• US 6,944,131 B2
• Filed: 12/30/2003
• Issued: 09/13/2005
• 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:
  US10/747,077
• Publication Number:
  US 20040151130A1
• Time in Patent Office: 623 Days
• Field of Search: 370/216, 370/217, 370/219, 370/220, 370/221, 370/225, 370/227, 370/228, 370/237, 370/238, 370/238.1, 370/245, 370/248, 370/252, 370/328, 370/338, 370/384, 370/385, 370/386, 709/239, 709/241
• US Class Current: 370/238.1
• 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 the given node. Each node receives heartbeat signals from its neighbouring nodes. An unexpected delay between heartbeat signals may be perceived as a failure of a link. The perceived 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. A network comprising:

a plurality of nodes;

links interconnecting said nodes; and

a plurality of network controllers, each of said network controllers having an associated set of subtending nodes belonging to said plurality of nodes;

wherein;

each node of said plurality of nodes is operable to elect a primary network controller from said plurality of network controllers; and

each network controller of said plurality of network controllers is operable to determine, for each subtending node in said associated set of subtending nodes;

a route set to each other subtending node in said associated set of subtending nodes; and

a route set to at least one subtending node in said set of subtending nodes associated with each other network controller in said plurality of network controllers.

2. The network of claim 1 wherein at least one of said nodes functions as one of said network controllers.

3. The network of claim 1 wherein said each node is operable to elect the network controller having the least-cost path to said each node as said primary network controller.

4. The network of claim 3 wherein said each node is operable to use said primary network controller as a current network controller.

5. The network of claim 4 wherein said each node is operable to exchange regular control signals with said current network controller.

6. The network of claim 5 wherein said each node is operable to:

switch to a secondary network controller selected from among said plurality of network controllers if said regular control signals exchanged with said primary network controller are disrupted; and

use said secondary network controller as said current network controller.

7. The network of claim 6 wherein said each node is operable to communicate a link-state-information message to said current network controller, said message comprising:

an identifier of said each node;

a message number;

where link-state changes have occurred, an indication of a quantity of said link-state changes; and

for each link-state change of said link-state changes;

a link identifier;

a link-state sequence number; and

an indication of a type for said each link-state change.

8. The network of claim 6 wherein said current network controller is operable to communicate a link-state-information message to at least one regular nodes in said associated set of subtending nodes, said message comprising:

an identifier of said current network controller;

a message number,

an indication of an integer number of link state changes; and

for each link-state change of said link-state changes;

a link identifier;

a link state sequence number; and

an indication of said each link-state change.