Systems and methods for forwarding data in a communications network

• US 7,668,083 B1
• Filed: 10/28/2003
• Issued: 02/23/2010
• Est. Priority Date: 10/28/2003
• Status: Active Grant

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: BBN Technologies (Rtx Corporation)
• Inventors: Elliott, Brig Barnum
• Primary Examiner(s): Tran; Phuc H
• Application Number:
  US10/694,968
• Time in Patent Office: 2,310 Days
• Field of Search: 370216-228, 370242-246
• US Class Current: 370/223
• CPC Class Codes: H04B 7/18521 Systems of inter linked satellites, i.e. inter satellite service for optical links between satellites H04B10/118
• CPC Class Codes: H04B 7/18584 Arrangements for data networking, i.e. for data packet routing, for congestion control data switching networks H04L12/00
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A communications network (100) includes at least one control station (160) and a group of network nodes (110, 120, 140). The at least one control station (160) generates batches of forwarding tables (300), where each batch of forwarding tables (300) includes a primary forwarding table (305) and a group of backup forwarding tables (310), and forwards the batches of forwarding tables (300). Each of the network nodes (110, 120, 140) is associated with one or more outbound and inbound links and is configured to receive a batch of forwarding tables (300) from the at least one control station (160) and install the primary forwarding table (305) from the batch (300) as a current forwarding table. Each network node (110, 120, 140) is further configured to detect that a quality of one of an outbound and inbound link has changed, generate a message (900) instructing other nodes of the group of network nodes (110, 120, 140) to switch to a backup forwarding table (310) in response to detecting the quality change, and transmit the message (900) to the other nodes.

Claims

1. A communications network comprising:

at least one control station configured to;

generate batches of forwarding tables, each batch of forwarding tables including a primary forwarding table and a plurality of backup forwarding tables, and

forward the batches of forwarding tables; and

a plurality of network nodes, each network node being associated with one or more outbound and inbound links and configured to;

receive a batch of forwarding tables from the at least one control station,

install the primary forwarding table from the batch as a current forwarding table,

detect that a quality of one of an associated outbound and inbound link has changed,

in response to detecting the quality change, generate a message instructing other nodes of the plurality of network nodes to switch to a backup forwarding table associated with the detected link, the backup forwarding table being selected from the plurality of backup forwarding tables received at each respective node, and

transmit the message to the other nodes.

2. The communications network of claim 1 wherein the message identifies the backup forwarding table.

3. The communications network of claim 1 wherein the message identifies the one outbound or inbound link, and

wherein the backup forwarding table corresponds to the one outbound or inbound link.

4. The communications network of claim 1 wherein each of the plurality of network nodes is further configured to:

transmit the message to the at least one control station.

5. The communications network of claim 1 wherein the plurality of network nodes includes at least one satellite.

6. The communications network of claim 5 wherein the at least one control station includes a terrestrial control station.

7. The communications network of claim 5 wherein the at least one control station includes a space-based control station.

8. A control station in a communications network comprising a plurality of nodes, the control station comprising:

a memory configured to store topology information for the communications network; and

a processor configured to;

generate a batch of forwarding tables for each of the plurality of nodes based on the topology information, each batch of forwarding tables including a primary forwarding table and a plurality of backup forwarding tables for a corresponding one of the plurality of nodes,

cause each batch of forwarding tables to be transmitted to the corresponding one of the plurality of nodes, and

receive a message from at least one of the plurality of the nodes that identifies a link, the message instructing other nodes in the network to switch to one of the plurality of backup forwarding tables associated with the link at each respective node.

9. The control station of claim 8 wherein the plurality of backup forwarding tables of each batch of forwarding tables allows the corresponding node to handle a subset of all single events that can occur in the communications network.

10. The control station of claim 8 wherein the plurality of backup forwarding tables of each batch of forwarding tables allows the corresponding node to handle any single event that can occur in the communications network.

11. The control station of claim 8 wherein the plurality of backup forwarding tables of each batch of forwarding tables allows the corresponding node to handle any combination of two or more events that can occur in the communications network.

12. The control station of claim 8 wherein the plurality of nodes includes at least one satellite.

13. The control station of claim 8 wherein the batch of forwarding tables includes forwarding tables for at least one of Internet Protocol, Asynchronous Transfer Mode, Multi-Protocol Label Switching, fast packet switching, and Ethernet.

14. In a communications network, a node that routes data in the communications network, comprising:

a memory configured to store a first primary forwarding table and a first plurality of backup forwarding tables; and

a processor configured to;

receive a batch of forwarding tables from a remote network device, the batch of forwarding tables including a second primary forwarding table and a second plurality of backup forwarding tables,

install the second primary forwarding table as a current primary forwarding table, and

replace the first plurality of backup forwarding tables with the second plurality of backup forwarding tables from the received batch.

15. The node of claim 14 wherein the node includes a satellite.

16. The node of claim 14 wherein the second plurality of backup forwarding tables allows the node to continue routing data in the communications network when any of a subset of possible events occurs in the communications network.

17. The node of claim 14 wherein the second plurality of backup forwarding tables allows the node to continue routing data in the communications network when a single event occurs in the communications network.

18. The node of claim 14 wherein the second plurality of backup forwarding tables allows the node to continue routing data in the communications network when a combination of two or more events occurs in the communications network.

19. The node of claim 14 wherein the node is associated with at least one outbound link and at least one inbound link, and

wherein the processor is further configured to:

detect a change in quality in one of the at least one outbound link and the at least one inbound link,

generate a message that identifies the detected one outbound link or inbound link, and

cause the message to be transmitted to one or more other nodes in the communications network, the message instructing the one or more other nodes to switch to a backup forwarding table associated with the identified one outbound link or inbound link, the backup forwarding table being selected from the first or the second plurality of backup forwarding tables.

20. The node of claim 14 wherein the processor is further configured to:

receive a message from another node in the communications network, the message instructing the node to switch to one of the plurality of second backup forwarding tables,

determine whether the second primary forwarding table is a current forwarding table in the node in response to receiving the message, and

cause the one second backup forwarding table to be the current forwarding table when the current forwarding table is the second primary forwarding table.

21. The node of claim 20 wherein the processor is further configured to:

cause the received message to be transmitted to at least one other node in the communications network.

22. The node of claim 20 wherein the processor is further configured to:

piggy-back the received message in a transmission to at least one other node in the communications network.

23. In a communications network, a node, associated with at least one outbound link and at least one inbound link, that transmits data in the communications network, the node comprising:

a memory configured to store a primary forwarding table and a plurality of backup forwarding tables; and

a processor configured to;

detect a change in quality in one of the at least one outbound link and the at least one inbound link,

generate a message that identifies the detected one outbound link or inbound link, and

cause the message to be transmitted to one or more other nodes in the communications network, the message instructing the one or more other nodes to switch to a backup forwarding table associated with the identified one outbound link or inbound link, the backup forwarding table being selected from the plurality of backup forwarding tables stored at each respective node.

24. The node of claim 23 wherein the plurality of backup forwarding tables allows the node to continue routing data in the communications network when any of a subset of possible events occurs in the communications network.

25. The node of claim 23 wherein the plurality of backup forwarding tables allows the node to continue routing data in the communications network when a single event occurs in the communications network.

26. The node of claim 23 wherein the plurality of backup forwarding tables allows the node to continue routing data in the communications network when a combination of two or more events occurs in the communications network.

27. The node of claim 23 wherein the processor is further configured to:

receive a second message from another node in the communications network, the second message instructing the node to switch to one of the plurality of backup forwarding tables,

determine whether the primary forwarding table is a current forwarding table in the node in response to receiving the second message, and

cause the one backup forwarding table to be the current forwarding table when the current forwarding table is the primary forwarding table.

28. The node of claim 27 wherein the processor is further configured to:

cause the received second message to be transmitted to at least one other node in the communications network.

29. The node of claim 27 wherein the processor is further configured to:

piggy-back the received second message in a transmission to at least one other node in the communications network.

30. A method for routing data in a communications network that comprises a plurality of nodes, comprising:

generating, for each of the plurality of nodes, a unique set of forwarding tables, the unique set of forwarding tables including a primary forwarding table and a plurality of backup forwarding tables;

forwarding the unique set of forwarding tables to each of the plurality of nodes, the plurality of backup forwarding tables allowing each of the plurality of nodes to continue routing data in the communications network after an occurrence of at least one event, and

receiving a message from at least one of the plurality of the nodes that identifies a link, the message instructing other nodes in the network to switch to one of the plurality of backup forwarding tables associated with the link at each respective node.

31. The method of claim 30 wherein the plurality of backup forwarding tables allows each of the plurality of nodes to continue routing data in the communications network when any of a subset of possible events occurs in the communications network.

32. The method of claim 30 wherein the plurality of backup forwarding tables allows each of the plurality of nodes to continue routing data in the communications network when a single event occurs in the communications network.

33. The method of claim 30 wherein the plurality of backup forwarding tables allows each of the plurality of nodes to continue routing data in the communications network when a combination of two or more events occurs in the communications network.

34. The method of claim 30 wherein at least one of the plurality of nodes includes a satellite.

35. A computer-readable medium containing a plurality of instructions that, when executed by at least one processor, causes the at least one processor to perform a method for routing data in a communications network, comprising:

generating, for each of a plurality of network nodes, a set of forwarding tables, the set of forwarding tables including a primary forwarding table and a plurality of backup forwarding tables;

forwarding the set of forwarding tables to each of the plurality of nodes, the plurality of backup forwarding tables allowing each of the plurality of nodes to continue routing data in the communications network following a failure of or degradation in a network node or link, and

receiving a message from at least one of the plurality of the nodes that identifies a link, the message instructing other nodes in the network to switch to one of the plurality of backup forwarding tables associated with the link at each respective node.

36. A method for routing data in a communications network, the method comprising:

receiving a group of forwarding tables, the forwarding tables including a primary forwarding table and a plurality of backup forwarding tables;

installing the primary forwarding table as a current forwarding table for routing data in the communications network;

storing the plurality of backup forwarding tables;

detecting a change in quality in an outbound or inbound link associated with a node in the network;

in response to detecting the quality change, generating a message that identifies the detected link; and

transmitting the message to one or more other nodes in the communications network, the message instructing the one or more other nodes to switch to a backup forwarding table associated with the detected link.

37. The method of claim 36 wherein the plurality of backup forwarding tables enables continued routing of data in the communications network when a failure or a degradation of a link occurs in the communications network.

38. The method of claim 36 wherein the plurality of backup forwarding tables enables continued routing data in the communications network when any of a subset of possible events occurs in the communications network.

39. The method of claim 36 wherein the plurality of backup forwarding tables enables continued routing data in the communications network when a combination of two or more events occurs in the communications network.

40. A computer-readable medium containing a plurality of instructions that, when executed by at least one processor, causes the at least one processor to perform a method for routing data in a communications network, comprising:

receiving a group of forwarding tables, the forwarding tables including a primary forwarding table and a plurality of backup forwarding tables;

installing the primary forwarding table as a current forwarding table for routing data in the communications network; and

storing the plurality of backup forwarding tables;

detecting a change in quality in an outbound or inbound link associated with a node in the network;

in response to detecting the quality change, generating a message that identifies the detected link; and

transmitting the message to one or more other nodes in the communications network, the message instructing the one or more other nodes to switch to a backup forwarding table associated with the detected link.

41. In a node comprising at least one outbound link and at least one inbound link, a method for routing data in a communications network, comprising:

receiving a group of forwarding tables, the forwarding tables including a primary forwarding table and a plurality of backup forwarding tables;

detecting a change in quality of one of the outbound link and the inbound link;

generating a message in response to the detecting, the message identifying the one outbound or inbound link; and

transmitting the message to at least one other node in the communications network, the message causing the at least one other node to switch to a backup forwarding table associated with the identified one outbound or inbound link.

42. The method of claim 41 wherein the message further identifies the node and the change in quality.

43. The method of claim 42 wherein the backup table is further associated with the node and the change in quality.

44. The method of claim 41 wherein the transmitting includes:

piggy-backing the message in a transmission to the at least one other node.

46. The computer-readable medium of claim 44 wherein the message further identifies the second quality.

45. A computer-readable medium containing a plurality of instructions that, when executed by at least one processor, causes the at least one processor to perform a method for routing data in a communications network, comprising:

receiving a group of forwarding tables, the forwarding tables including a primary forwarding table and a plurality of backup forwarding tables;

detecting a change from a first quality to a second quality of one of an outbound link and an inbound link;

generating a message in response to the detecting, the message identifying the one outbound or inbound link; and

sending the message to nodes in the communications network, the message causing the nodes to switch to a backup forwarding table associated with the identified one outbound or inbound link.

47. A system for routing data in a communications network, comprising:

means for receiving a group of forwarding tables, the forwarding tables including a primary forwarding table and a plurality of backup forwarding tables;

means for determining that a quality of one of an outbound link and an inbound link has changed;

means for generating a message in response to determining the quality change, the message identifying the one outbound or inbound link; and

means for sending the message to at least one other node in the communications network, the message instructing the at least one other node to switch to a backup forwarding table associated with the identified one outbound or inbound link.