Automatic network topology identification by nodes in the network

• US 7,916,723 B2
• Filed: 07/01/2009
• Issued: 03/29/2011
• Est. Priority Date: 03/03/2000
• Status: Active Grant

• Current Assignee: ADTRAN Incorporated (ADTRAN Holdings, Inc.)
• Original Assignee: ADTRAN Incorporated (ADTRAN Holdings, Inc.)
• Inventors: Fan, Jason C., Bannai, Vinay K., Jogalekar, Prasad P.
• Primary Examiner(s): Kumar; Pankaj
• Assistant Examiner(s): Duong; Duc T
• Application Number:
  US12/496,147
• Publication Number:
  US 20100124176A1
• Time in Patent Office: 636 Days
• Field of Search: 370254-256, 370/400, 370/401, 370/389, 370/392, 709220-224, 709/245
• US Class Current: 370/389
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 2101/672 Short addresses
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 61/2596 Translation of addresses of the same type other than IP, e.g. translation from MAC to MAC addresses

Abstract

An automatic network topology identification technique is described herein. Each node in the network periodically or constantly transmits its unique address to its neighboring node. Once a node receives a different message from its neighbor, the node identifies a topology change in the network. In one embodiment, a current topology is associated with a session number. When a change in the topology is detected, the detecting node increments the session number and broadcasts the change in topology. The other nodes, detecting the changed session number, now know that there has been a change in the network. In response, the nodes in the network modify routing tables and other information stored at the node related to the topology. In one embodiment, the technique is used to reassign shortened addresses to each device on the network to support a dual-addressing mode of the network. The dual addressing mode substitutes reduced-length addresses (referred to as short addresses) for standard addresses (referred to as long addresses) for traffic whose source or destination is internal to a given virtual network topology. The required length of short addresses used for a given virtual topology is dependent on the number of devices reachable within the topology.

Claims

1. A method performed by a communications network, said network comprising interconnected nodes, said method comprising:

monitoring by a first one of said interconnected nodes a message from a neighboring node identifying attributes of said neighboring node, wherein each interconnected node is associated with a first address and a second address, wherein the second address has fewer bits than the first address, and wherein network data is transmitted within the interconnected nodes using the second addresses;

detecting a change in said message from a previous message so as to identify a change in attributes of said neighboring node, corresponding to a change in said network; and

communicating to other nodes in said network by said first node said change in said network, wherein said change in said network is communicated using the first addresses rather than using the second addresses.

2. The method of claim 1 further comprising remapping second addresses to said first addresses after said change in said network is communicated, wherein network data is transmitted within the interconnected nodes using the remapped second addresses.

3. The method of claim 1 wherein the communicating said change in said network includes broadcasting a neighbor status message to the neighboring nodes using said first addresses associated with the neighboring nodes.

4. The method of claim 1 wherein the change in the network is indicated by a change in link status for at least one network link connected to the neighboring node.

5. The method of claim 4 wherein the change in link status is detected based on counting errors on the at least one network link.

6. The method of claim 4 wherein the change in link status is determined based on detecting a loss of optical power on the at least one network link.

7. The method of claim 1 wherein the change in the network includes a change in the topology of the network including an addition or deletion of at least one node in the network.

8. The method of claim 7 further comprising updating a routing table within the interconnected nodes based on the change in the topology of the network.

9. The method of claim 2 further comprising:

constructing a network topology representation of the topology of the communications network using the first addresses associated with the interconnected nodes; and

validating said topology using said topology representation before the remapping of the second addresses.

10. The method of claim 9 wherein

the network topology representation is determined to be final upon determining a topology discovery timer has expired;

and

determining that a topology stability time has exceeded a threshold to determine that the topology is sufficiently stable for the validating of the topology.

11. A routing switch for use in a communications network, the network comprising routing switches interconnected by communication links, the routing switch comprising:

one or more transceivers connected to associated links to one or more other routing switches in neighboring nodes;

a switch fabric for routing information to and from the one or more transceivers; and

one or more processors, the one or more processors for controlling the routing switch to;

monitor a message from a neighboring node identifying attributes of the neighboring node, wherein each interconnected node is associated with a first address and a second address, wherein the second address has fewer bits than the first address, and wherein network data is transmitted within the interconnected nodes using the second addresses;

detect a change in the message from a previous message so as to identify a change in attributes of the neighboring node, corresponding to a change in the network; and

communicate to other nodes in the network by said first node the change in the network, wherein the change in the network is communicated using the first addresses rather than using the second addresses.

12. The routing switch of claim 11 wherein the one or more processors further control the routing switch to remap second addresses to said first addresses after the change in the network is communicated, wherein network data is transmitted within the interconnected nodes using the remapped second addresses.

13. The routing switch of claim 11 wherein the communicating of the change in the network includes broadcasting a neighbor status message to the neighboring nodes using the first addresses associated with the neighboring nodes.

14. The routing switch of claim 11 wherein the change in the network is indicated by a change in link status for at least one network link connected to the neighboring node, the change in link status being detected based on counting errors on the at least one network link or based on detecting a loss of optical power on the at least one network link.

15. The routing switch of claim 11 wherein the change in the network includes a change in the topology of the network including an addition or deletion of at least one node in the network.

16. The routing switch of claim 15 further comprising updating a routing table within the interconnected nodes based on the change in the topology of the network.

17. The routing switch of claim 12 wherein the change in the network includes a change in the topology of the network, and further comprising:

constructing a network topology representation of a topology of the communications network using the first addresses associated with the interconnected nodes; and

validating the topology using the topology representation before the remapping of the second addresses.

18. The routing switch of claim 17 wherein

the network topology representation is determined to be final upon determining a topology discovery timer has expired;

and

determining that a topology stability time has exceeded a threshold to determine that the topology is sufficiently stable for the validating of the topology.