Routing switch detecting change in session identifier before reconfiguring routing table

• US 20040213274A1
• Filed: 05/26/2004
• Published: 10/28/2004
• 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.
• Granted Patent: US 7,545,755 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• 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 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/2596 Translation of addresses of the same type other than IP, e.g. translation from MAC to MAC addresses
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function

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-3. -3. (canceled)

4. A method for validating a topology in an optical communications network, the topology including at least one node, comprising:

(a) detecting a topology change in the network;

(b) performing topology discovery;

(c) determining if a topology stability timer has exceeded a threshold; and

(d) performing topology validation for the topology change, if the topology stability timer has exceeded the threshold.

5. The method of claim 4, wherein the performing step (b) comprises:

(b1) resetting a topology discovery timer; and

(b2) performing the topology discovery.

6. The method of claim 5, wherein the determining step (c) comprises:

(c1) determining if the topology stability timer has exceeded a threshold, if the topology discovery timer has expired.

7. The method of claim 6, wherein the determining step (c) further comprises:

(c2) if the topology stability timer has not exceeded the threshold, then determine if the topology discovery timer has exceeded a maximum limit;

(c3) stopping the topology discovery and reporting an error, if the topology discovery timer has exceeded the maximum limit; and

(c4) resetting the topology discovery timer, if the topology discovery timer has not exceeded the maximum limit.

8. The method of claim 4, wherein the performing step (d) comprises:

(d1) determining if, for each ingress neighbor on each defined interface of the at least one node, a received neighbor status message is available from the ingress neighbor, wherein the topology is invalid if no received neighbor status message is available from each ingress neighbor;

(d2) updating a temporary topology data structure with the ingress neighbors, if the received neighbor status message is available from each ingress neighbor;

(d3) determining if each neighbor status message at the at least one node has been used, wherein the topology is invalid if at least one neighbor status message has not been used, wherein the topology is valid if all neighbor status messages have been used; and

(d4) updating a permanent topology data structure, if the topology is valid.

9. The method of claim 8, wherein the determining step (d1) comprises:

(d1i) checking that each pair of adjacent nodes in the topology report each other as neighbors.

10. The method of claim 8, wherein steps (d1) through (d4) are repeated for

11. The method of claim 8, wherein the determining step (d3) further comprises:

(d3i) determining if each node in the topology has at least one egress neighbor, wherein the topology is invalid if not each node in the topology has at least one egress neighbor, wherein the topology is valid if each node in the topology has at least one egress neighbor.

12. The method of claim 4, wherein the topology stability timer comprises a time period during which no neighbor status message are received from other nodes in the communications network corresponding to the change in the topology.

13. A computer readable medium with program instructions for validating a topology in an optical communications network, the topology including at least one node, comprising instructions for:

(a) detecting a topology change in the network;

(b) performing topology discovery;

(c) determining if a topology stability timer has exceeded a threshold; and

(d) performing topology validation for the topology change, if the topology stability timer has exceeded the threshold.

14. The medium of claim 13, wherein the performing instruction (b) comprises:

(b1) resetting a topology discovery timer; and

(b2) performing the topology discovery.

15. The medium of claim 14, wherein the determining instruction (c) comprises:

(c1) determining if the topology stability timer has exceeded a threshold, if the topology discovery timer has expired.

16. The medium of claim 15, wherein the determining instruction (c) further comprises:

(c2) if the topology stability timer has not exceeded the threshold, then determine if the topology discovery timer has exceeded a maximum limit;

(c3) stopping the topology discovery and reporting an error, if the topology discovery timer has exceeded the maximum limit; and

(c4) resetting the topology discovery timer, if the topology discovery timer has not exceeded the maximum limit.

17. The medium of claim 13, wherein the performing instruction (d) comprises:

(d1) determining if, for each ingress neighbor on each defined interface of the at least one node, a received neighbor status message is available from the ingress neighbor, wherein the topology is invalid if no received neighbor status message is available from each ingress neighbor;

(d2) updating a temporary topology data structure with the ingress neighbors, if the received neighbor status message is available from each ingress neighbor;

(d3) determining if each neighbor status message at the at least one node has been used, wherein the topology is invalid if at least one neighbor status message has not been used, wherein the topology is valid if all neighbor status messages have been used; and

(d4) updating a permanent topology data structure, if the topology is valid.

18. The medium of claim 17, wherein the determining instruction (d1) comprises:

(d1i) checking that each pair of adjacent nodes in the topology report each other as neighbors.

19. The medium of claim 17, wherein instructions (d1) through (d4) are repeated for each node in the topology.

20. The medium of claim 17, wherein the determining instruction (d3) further comprises:

(d3i) determining if each node in the topology has at least one egress neighbor, wherein the topology is invalid if not each node in the topology has at least one egress neighbor, wherein the topology is valid if each node in the topology has at least one egress neighbor.

21. The medium of claim 13, wherein the topology stability timer comprises a time period during which no neighbor status message are received from other nodes in the communications network corresponding to the change in the topology.

22. 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 for being 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 for controlling the routing switch, comprising a topology stability timer, wherein the processor;

detects a topology change in the network;

performs topology discovery;

determines if the topology stability timer has exceeded a threshold; and

performs topology validation for the topology change, if the topology stability timer has exceeded the threshold.

23. The system of claim 22, wherein the processor further comprises a topology discovery timer, wherein in performing the topology discovery, the processor further resets a topology discovery timer.

24. The system of claim 23, wherein the processor determines if the topology stability timer has exceeded the threshold, if the topology discovery timer has expired.

25. The system of claim 24, wherein in determining that the topology stability timer has exceeded the threshold, the processor further:

determines if the topology discovery timer has exceeded a maximum limit, if the topology stability timer has not exceeded the threshold;

stops the topology discovery and reporting an error, if the topology discovery timer has exceeded the maximum limit; and

resets the topology discovery timer, if the topology discovery timer has not exceeded the maximum limit.

26. The system of claim 22, wherein in performing the topology validation, the processor:

determines if, for each ingress neighbor on each defined interface of the at least one node, a received neighbor status message is available from the ingress neighbor, wherein the topology is invalid if no received neighbor status message is available from each ingress neighbor;

updates a temporary topology data structure with the ingress neighbors, if the received neighbor status message is available from each ingress neighbor;

determines if each neighbor status message at the at least one node has been used, wherein the topology is invalid if at least one neighbor status message has not been used, wherein the topology is valid if all neighbor status messages have been used; and

updates a permanent topology data structure, if the topology is valid.

27. The system of claim 26, wherein in performing the topology validation, the processor checks that each pair of adjacent nodes in the topology report each other as neighbors.

28. The system of claim 26, wherein the processor performs the topology validation for each node in the topology.

29. The system of claim 26, wherein in determining if each neighbor status message at the at least one node has been used, the processor:

determines if each node in the topology has at least one egress interface, wherein the topology is invalid if not each node in the topology has at least one egress interface, wherein the topology is valid if each node in the topology has at least one egress interface.

30. The system of claim 22, wherein the topology stability timer comprises a time period during which no neighbor status message are received from other nodes in the communications network corresponding to the change in the topology.