Apparatus and method for detecting and eliminating call looping in a node-by-node routing network

• US 5,014,262 A
• Filed: 01/02/1990
• Issued: 05/07/1991
• Est. Priority Date: 01/02/1990
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Harshavardhana, Paramasiv
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Hsu, Alpus H.
• Application Number:
  US07/459,924
• Time in Patent Office: 490 Days
• Field of Search: 370/16, 370/16.1, 370/94.1, 370/94.3, 370/60, 370/14, 370/54, 340/825.03, 340/826, 340/827, 379/219, 379/220, 379/221, 379/271, 379/272, 379/273, 379/253, 379/284
• US Class Current: 370/237
• 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/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04Q 3/66 Traffic distributors
• CPC Class Codes: Y10S 379/901 Virtual networks or virtual private networks

Abstract

An apparatus and method for effectively managing a switched virtual circuit network by detecting and resolving call routing problems occurring in the routing pattern of the network is provided. Detecting the call routing problems is advantageously achieved by a first process contained in a network management center which has access to all nodes in the network and performs routing table verification for each node whenever there are changes in the routing tables caused by changes in the network, such as an addition of nodes, links and the like. Otherwise, call looping may occur during call set-up as a result of any undiscovered or uncorrected errors in one or more routing tables in the network. Detection of call loops is achieved by the first process through use of a plurality of processing modules that recognizes and excludes in their analysis of the network certain network components that can not be involved in call looping. Identified routing problems are resolved by a second process which provides alternative recommendations as to how best to modify the routing tables in the nodes of the network. A selected one of the alternative recommendations is coupled from the network management center to the nodes in the network for changing the routing tables located at the respective nodes.

Claims

1. Apparatus for detecting call looping in a node-by-node data routing network including a plurality of nodes for routing data calls, each node having routing information for directing data calls over multiple paths to multiple destinations, said apparatus comprising:

means for identifying those nodes in the network that are involved in call looping for data calls directed to specific destinations; and

means for modifying the routing information in at least one node involved in the call looping, the modifying means altering a routing path for a data call to a specific destination in a manner that prevents the data call from looping among the identified nodes.

2. The apparatus for detecting call looping as in claim 1 wherein the identifying means further comprises means for identifying those nodes in the network that are configured in a manner such that they are potentially involved in call looping and identifying those nodes in the network that are configured in a manner such that they are not involved in call looping.

3. The apparatus for detecting call looping as in claim 2 wherein those nodes that are potentially involved in call looping comprise nodes configured as tandem nodes.

4. The apparatus for detecting call looping as in claim 2 wherein the identifying means further comprises means for determining a number of call loops in the routing network and the direction of travel between nodes for each loop.

5. The apparatus for detecting call looping as in claim 4 further comprising means for detecting circuitous routing, the circuitous routing detecting means providing an indication when the number of nodes provided in a routing pattern for a primary path to the specific destination exceeds a predetermined number.

6. The apparatus for detecting call looping as in claim 5 further comprising means for detecting dead-end routing, the dead-end routing detecting means providing a means for comparing information in routing tables in the nodes of the network with that in a network database and providing an indication if any information is detected as missing from the routing tables.

7. A method of detecting call looping in a node-by-node data routing network including a plurality of nodes for routing data calls, each node having routing information for directing data calls over multiple paths to multiple destinations, the method comprising the steps of:

identifying those nodes in the network that are involved in call looping for data calls directed to specific destinations; and

modifying the routing information in at least one node involved in the call looping, the modifying step altering a routing path for a data call to a specific destination in a manner that prevents the data call from looping among the identified nodes.

8. The method of detecting call looping in a node-by-node data routing network as in claim 7 wherein the identifying step further comprises the steps of identifying those nodes in the network that are configured in a manner such that they are potentially involved in call looping and identifying those nodes in the network that are configured in a manner such that they can not be involved in call looping.

9. The method of detecting call looping in a node-by-node data routing network as in claim 8 wherein those nodes that are potentially involved in call looping comprise nodes configured as tandem nodes.

10. The method of detecting call looping in a node-by-node data routing network as in claim 8 further comprising the step of determining a number of call loops in the network and the direction of travel between nodes for each loop.

11. The method of detecting call looping in a node-by-node data routing network as in claim 10 wherein the information modifying step further comprises the steps of:

determining the routing paths that are involved in the highest number of loops in a routing pattern for the data call to the specific destination, examining a series of alternative recommendations for breaking the loops in the routing pattern, and providing one of the series of alternative recommendations to the network for modifying the routing information.

12. The method of detecting call looping in a node-by-node data routing network as in claim 7 wherein the identifying step further comprises the step of generating a routing matrix for each destination from the routing information contained in each node, the routing matrix containing data reflective of a circuit connection between individual nodes and priority of a routing choice for routing calls to the specific destination over the circuit connection.

13. The method of detecting call looping in a node-by-node data routing network as in claim 12 wherein the identifying step further comprises the step of generating an adjacency matrix for each destination from the routing matrix, the adjacency matrix containing data reflective only of the circuit connection between individual nodes for routing calls to the specific destination.

14. The method of detecting call looping in a node-by-node data routing network as in claim 13 further comprising the steps of identifying those nodes in the network that are configured in a manner such that they are potentially involved in call looping and identifying those nodes in the network that are configured in a manner such that they are not involved in call looping, the adjacency matrix providing the routing information for determining these identifying steps.

15. The method of detecting call looping in a node-by-node data routing network as in claim 14 further comprising the step of determining a number of call loops and the direction of travel between nodes for each loop.

16. The method of detecting call looping in a node-by-node data routing network as in claim 15 wherein the information modifying step further comprises the step of generating a connectivity matrix for the network, the connectivity matrix containing data reflective only of a circuit connection between individual nodes in the routing network.

17. The method of detecting call looping in a node-by-node data routing network as in claim 16 wherein the information modifying step further includes the steps of:

determining the number of loops associated with each circuit connection, examining a series of alternative recommendations for breaking the loops in a routing pattern for the data call to the specific destination, and providing one of the series of alternative recommendations to the network for modifying the routing information.

18. The method of detecting call looping in a node-by-node data routing network as in claim 17 wherein a first alternative recommendation concerns breaking the circuit connection involved in the highest number of loops in the routing pattern, and a second alternative recommendation concerns breaking the circuit connection involved in the second highest number of loops in the routing pattern.

19. Apparatus for detecting call looping in a node-by-node data routing network including a plurality of nodes for routing data calls, each node having routing information for directing data calls over multiple paths to multiple destinations, said apparatus comprising:

means for identifying those nodes in the network that are potentially involved in call looping for data calls directed to specific destinations; and

means for modifying the routing information in at least one node involved in the call looping, the modifying means altering a routing path for a data call to a specific destination in a manner that prevents the data call from looping among the identified nodes.

20. The apparatus for detecting call looping as in claim 19 wherein the identifying means further comprises means for identifying those nodes in the network that are configured in a manner such that they are potentially involved in call looping and identifying those nodes in the network that are configured in a manner such that they are not involved in call looping.

21. The apparatus for detecting call looping as in claim 20 wherein those nodes that are potentially involved in call looping comprise nodes configured as tandem nodes.

22. The apparatus for detecting call looping as in claim 20 wherein the identifying means further comprises means for determining a number of call loops in the routing network and the direction of travel between nodes for each loop.