Method for routing information over a network employing centralized control

• US 9,030,962 B2
• Filed: 11/30/2011
• Issued: 05/12/2015
• Est. Priority Date: 12/30/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Saleh, Ali N., Zadikian, H. Michael, Baghdasarian, Zareh, Parsi, Vahid
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): ANDREWS, LEON T
• Application Number:
  US13/307,995
• Publication Number:
  US 20120076492A1
• Time in Patent Office: 1,259 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 41/0803 Configuration setting
• CPC Class Codes: H04L 41/0866 Checking the configuration
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]

Abstract

A method and apparatus for centralized control of a network is described. The network includes a number of nodes. The method includes creating a database and storing the database on a master node of the network. The database contains topology information regarding a topology of the network. Each of the nodes is coupled to at least one other of the nodes, with the master node being one of the nodes.

Claims

1. A method implemented by a network device comprising:

maintaining a plurality of topology databases, wherein

each of the topology databases comprise information regarding a topology of a network,

the network comprises

a plurality of nodes, and

a plurality of optical links,

each of the nodes is communicatively coupled to another of the nodes by at least one of the optical links, such that the network is a mesh network, and

the maintaining comprises

sending a message, wherein

the message is sent from a master node to a backup node, and

the master node provides centralized routing control of the network,

receiving a reply in response to the message, wherein

the reply is received, at the master node, from the backup node,

the reply comprises

 

backup topology information,

the backup topology information identifies a backup topology database maintained at the backup node, and

the backup topology database is one of the topology databases,

comparing the backup topology information and authoritative topology information, wherein

the comparing is performed at the master node,

the authoritative topology information identifies an authoritative topology database maintained at the master node,

the authoritative topology database is another of the topology databases, and

the master node maintains the authoritative topology database, at least in part, by determining the topology of the network, and

if the comparing indicates that the backup topology database is not up-to-date,

transferring a copy of at least a portion of the authoritative topology database from the master node to the backup node, and

replacing the backup topology database with the copy of the at least the portion of the authoritative topology database.

2. The method of claim 1, further comprising:

if the comparing indicates that the backup topology database should be synchronized, synchronizing the authoritative topology database and the backup topology database, wherein the synchronizing comprises

making the copy of the at least the portion of the authoritative topology database, and

sending the copy of the at least the portion of the authoritative topology database from the master node to the backup node, wherein

a process of the master node maintaining the authoritative topology database and a process of the backup node maintaining the backup topology database execute independently of one another, and

the backup node is configured to provide centralized routing control of the network, wherein if the master node is not functioning properly, the backup node is used for centralized routing control of the network.

3. The method of claim 2, further comprising:

receiving the copy of the at least the portion of the authoritative topology database at the backup node; and

merging the backup topology information in the backup topology database with the copy of the at least the portion of the authoritative topology database into the backup topology database.

4. The method of claim 2, further comprising:

upon the receiving the copy of the at least the portion of the authoritative topology database at the backup node, forwarding the copy of the at least the portion of the authoritative topology database from the backup node to a standby node.

5. The method of claim 1, further comprising:

sending a copy of at least a portion of a dynamic topology database from the master node to the backup node.

6. The method of claim 5, further comprising:

forwarding the copy of the at least the portion of the dynamic topology database from the backup node to a standby node.

7. The method of claim 1, further comprising:

forwarding the copy of the at least the portion of the authoritative topology database from the backup node to a standby node; and

storing the copy of the at least the portion of the authoritative topology database as a standby topology database.

8. The method of claim 7, wherein the maintaining further comprises:

maintaining synchronization between

the authoritative topology database,

the backup topology database, and

the standby topology database.

9. The method of claim 1, wherein the maintaining further comprises:

creating the authoritative topology database at the master node, wherein

the creating the authoritative topology database comprises receiving a positive reply at the master node,

the positive reply at the master node is from a neighbor node of the master node of a plurality of neighbor nodes of the master node,

the positive reply at the master node is with regard to a first neighbor node,

the first neighbor node is a neighbor node of the neighbor node of the master node, and

the first neighbor node is not among the plurality of neighbor nodes of the master node.

10. The method of claim 9, wherein the maintaining further comprises:

creating the backup topology database at the backup node, wherein

the creating the backup topology database comprises receiving a positive reply at the backup node,

the positive reply at the backup node is from a neighbor node of the backup node of a plurality of neighbor nodes of the backup node,

the positive reply at the backup node is with regard to a second neighbor node,

the second neighbor node is a neighbor node of the neighbor node of the backup node, and

the second neighbor node is not among the plurality of neighbor nodes of the backup node.

11. A network device comprising:

a processor;

a non-transitory computer-readable storage medium, coupled to the processor; and

a plurality of instructions, encoded in the non-transitory computer-readable storage medium and configured to cause the processor to

maintain a plurality of topology databases, wherein

each of the topology databases comprise information regarding a topology of a network,

the network comprises

a plurality of nodes, and

a plurality of optical links,

each of the nodes is communicatively coupled to another of the nodes by at least one of the optical links, such that the network is a mesh network, and

the instructions configured to cause the processor to maintain the topology databases comprise instructions configured to cause the processor to;

cause master node to send a message to a backup node, wherein

the network device is the master node,

the master node is configured to provide centralized routing control of the network,

receive a reply in response to the message, wherein

the reply is received, at the master node,

from the backup node,

the reply comprises

backup topology information,

the backup topology information identifies a backup topology database maintained at the backup node,

the backup topology database is one of the topology databases, and

compare the backup topology information and authoritative topology information, wherein

the instructions configured to cause the processor to compare are executed by the master node,

the authoritative topology information identifies an authoritative topology database maintained at the master node,

the authoritative topology database is another of the topology databases, and

the master node maintains the authoritative topology database, at least in part, by determining the topology of the network, and

if the instructions configured to cause the processor to compare indicate that the backup topology database is not up-to-date,

transfer a copy of at least a portion of the authoritative topology database from the master node to the backup node, and

replace the backup topology database with the copy of the at least the portion of the authoritative topology database.

12. The network device of claim 11, wherein the instructions further comprise instructions configured to cause the processor to:

if the comparing indicates that the backup topology database should be synchronized, synchronize the authoritative topology database and the backup topology database, wherein the instructions configured to cause the processor to synchronize comprise instructions configured to cause the processor to make the copy of the at least the portion of the authoritative topology database, and

send the copy of the at least the portion of the authoritative topology database from the master node to the backup node, wherein

a process of the master node maintaining the authoritative topology database and a process of the backup node maintaining the backup topology database are executed independently of one another.

13. The network device of claim 12, wherein the instructions further comprise instructions configured to cause the processor to:

receive the copy of the at least the portion of the authoritative topology database at the backup node; and

merge the backup topology information in the backup topology database with the copy of the at least the portion of the authoritative topology database into the backup topology database.

14. The network device of claim 12, wherein the instructions further comprise instructions configured to cause the processor to:

upon receipt of the copy of the at least the portion of the authoritative topology database at the backup node, forward the copy of the at least the portion of authoritative topology database from the backup node to a standby node.

15. The network device of claim 11, wherein the instructions further comprise instructions configured to cause the processor to:

send a copy of at least a portion of a dynamic topology database from the master node to the backup node.

16. The network device of claim 15, wherein the instructions further comprise instructions configured to cause the processor to:

forward the copy of the at least the portion of the dynamic topology database from the backup node to a standby node.

17. The network device of claim 11, wherein the instructions further comprise instructions configured to cause the processor to:

forward the copy of the at least the portion of the authoritative topology database from the backup node to a standby node; and

store the copy of the at least the portion of the authoritative topology database as a standby topology database.

18. The network device of claim 17, wherein the instructions configured to cause the processor to maintain the plurality of topology databases are further configured to cause the processor to:

maintain synchronization between

the authoritative topology database,

the backup topology database, and

the standby topology database.

19. A computer program product comprising:

a plurality of instructions, comprising

a first set of instructions, executable on a network device, configured to maintain a plurality of topology databases, wherein

each of the topology databases comprise information regarding a topology of a network,

the network comprises

a plurality of nodes, and

a plurality of optical links,

each of the nodes is communicatively coupled to another of the nodes by at least one of the optical links, such that the network is a mesh network, and

the first set of instructions comprises

a second set of instructions, executable on the network device, configured to cause a master node to send a message to a backup node, wherein

the network device is the master node,

the master node is configured to provide centralized routing control of the network,

a third set of instructions, executable on the network device, configured to receive a reply in response to the message, wherein

the reply is received at the master node,

from the backup node,

the reply comprises

backup topology information,

the backup topology information identifies a backup topology database maintained at the backup node,

the backup topology database is one of the topology databases, and

a fourth set of instructions, executable on the network device, configured to compare the backup topology information and authoritative topology information, wherein

the fourth set of instructions are executed by the master node,

the authoritative topology information identifies an authoritative topology database maintained at the master node,

the authoritative topology database is another of the topology databases, and

the master node maintains the authoritative topology database, at least in part, by determining the topology of the network, and

a fifth set of instructions, executable on the network device, configured to, if the fourth set of instructions indicate that the backup topology database is not up-to-date,

transfer a copy of at least a portion of the authoritative topology database from the master node to the backup node, and

replace the backup topology database with the copy of the at least the portion of the authoritative topology database; and

a non-transitory computer-readable storage medium, wherein the instructions are encoded in the non-transitory computer-readable storage medium.

20. The computer program product of claim 19, wherein the first set of instructions further comprises:

a sixth set of instructions, executable on the network device, configured to, if the comparing indicates that the backup topology database should be synchronized, synchronize the authoritative topology database and the backup topology database, wherein the fifth set of instructions comprises

a first subset of instructions, executable on the network device, configured to make the copy of the at least the portion of the authoritative topology database, and

a second subset of instructions, executable on the network device, configured to send the copy of the at least the portion of the authoritative topology database from the master node to the backup node, wherein

a process of the master node maintaining the authoritative topology database and a process of the backup node maintaining the backup topology database are executed independently of one another.

21. The computer program product of claim 20, wherein the first set of instructions further comprises:

a seventh set of instructions, executable on the network device, configured to receive the copy of the at least the portion of the authoritative topology database at the backup node; and

a eighth set of instructions, executable on the network device, configured to merge the backup topology information in the backup topology database with the copy of the at least the portion of the authoritative topology database into the backup topology database.

22. The computer program product of claim 20, wherein the first set of instructions further comprises:

a seventh set of instructions, executable on the network device, configured to send a copy of at least a portion of a dynamic topology database from the master node to the backup node; and

a eighth set of instructions, executable on the network device, configured to forward the copy of the at least the portion of the dynamic topology database from the backup node to a standby node.