Route finding in communication networks

• US 6,122,282 A
• Filed: 02/05/1998
• Issued: 09/19/2000
• Est. Priority Date: 08/07/1995
• Status: Expired due to Fees

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications (BT Group Plc) (BT Group PLC)
• Inventors: Chng, Raymond Soo Khiaw
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Pham, Brenda H.
• Application Number:
  US09/011,003
• Time in Patent Office: 957 Days
• Field of Search: 370/406, 370/410, 370/351, 370/216, 370/222, 370/227, 709/238, 714/4
• US Class Current: 370/406
• 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: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

PURPOSE: To obtain a processing method capable of executing processing by a small memory and restricting the memory in accordance with the number of searching routes.

CONSTITUTION: Retrieving processing is started (10, 11) by using start point node as a start node, and in each end of processing, a node existing in a queue table 3 is used as a start node and the retrieving processing is repeated (12, 13). In retrieving processing (14, 15), the 1st processing is repeated by successively using the start node as a master node until there i no start node. The 1st processing (16) retrieves all slave nodes connected to the master node and the 2nd processing of the slave nodes is executed. If an item corresponding to a node in a data table 2 is in an idle state when the slave node is not an end point node in the 2nd processing (17 to 24), link information to the master node is recorded and the slave node is used as a start node, and when an idle state exists in the queue table in the recorded state of the link information, the identification (ID) information of the master node is recorded, and at the end point node, a route searching result is obtained from the link information stored in the data table 2.

Claims

1. A method of determining an additional route in a fully or partly meshed communications network of nodes, the method comprising the steps of:

determining, in response to a first predetermined circumstance and in accordance with a respective predetermined master/slave relationship, at each of a pair of the nodes between which there is an existing route, the one node of said pair which is to act as master end node with respect to said existing route and the other node which is to act as slave end node;

sending from said one node to its neighbouring nodes a forward route-finder signature for said existing route and including a first field containing identification data for said existing route;

receiving at a node a said forward route-finder signature, determining from the contents of said first field whether such receiving node is the slave end node for said existing route and, in the event that it is not, forwarding such received forward route-finder signature to its neighbouring nodes;

determining at said another node in response to a second predetermined circumstance a potential additional route and sending from said other node on said potential additional route a route confirmation signature identifying said potential additional route; and

storing details of said potential restoration route at said one node upon receipt thereat of the route confirmation signature;

and the method being characterised by the steps of ;

detecting at a node that a common circumstance has occurred in respect of a plurality of existing routes associated with said detecting node; and

generating at said detecting node a common signature corresponding to said common circumstance, said common signature comprising respective first fields containing respective identification data for said plurality of existing routes, and a second field containing the number of said first fields.

2. A method as claimed in claim 1, wherein said detecting node is a tandem node for each of said plurality of existing routes, and said common circumstance is the unavailability of respective bypass routes for said plurality of existing routes between said detecting node and an associated neighbouring node or nodes whereby said common signature is a common help signature for breaking down connections in the respective nodes of said plurality of existing routes and for initiating a restoration process at the respective end nodes of said plurality of existing routes, and wherein said common signature is sent from said detecting node to each neighbouring node which is associated with one or more of said plurality of existing routes and with whom said detecting node has operational links.

3. A method as claimed in claim 1, wherein said detecting node is constituted by said one node, said common circumstance is said one node is, in addition to acting as master end node for said existing route, also acting as master end node with respect to one or more other existing routes whereby the common signature is a route-finder signature.

4. A method as claimed in claim 3, wherein the common signature is sent to all the neighbouring nodes of said one node.

5. A node for use in a fully or partly meshed communications network of nodes, the node being arranged:

to respond, in use, to a first predetermined circumstance with respect to an existing route for which it is an end route to determine whether it will act as master end node or slave end node;

to send, in use, to its neighbouring nodes, in response to a determination that it will act as master end node, a forward route-finder signature;

to receive, in use, a route-finder signature and to determine whether or not it is an end node for the existing route identified by the route-finder signature, and, in response to a determination that it is not such an end node, to forward such received route-finder signature to its neighbouring nodes, or, in response to a determination that it is such an end node and subsequent to a preceding determination that the node is the slave end node for the existing route, to determine, in response to a second predetermined circumstance, a potential additional route, and to send on said potential additional route a route confirmation identifying the existing route; and

to store, in use, details of a said potential additional route upon receipt thereat of a route confirmation signature for an existing route for which it is acting as master end node;

and characterised in that it is arranged;

to detect, in use, the occurrence of a common circumstance in respect of a plurality of existing routes associated therewith; and

to generate a common signature corresponding to said common circumstance, said common signature comprising respective first fields containing respective identification data for said plurality of existing routes, and a second field containing the number of said first fields.

6. A node as claimed in claim 5, and arranged to detect, in use and when it is a tandem node for each of said plurality of existing routes, the unavailability of respective bypass routes for said plurality of existing routes between itself and an associated neighbouring node or nodes, said unavailability constituting said common circumstance;

to generate said common signature as a help signature for breaking down connections in the respective nodes of said plurality of existing routes and for initiating a restoration process at respective end nodes of said plurality of existing routes; and

to send said common signature to each neighbouring node which is associated with one or more of said plurality of existing routes and with whom the node has operational links.

7. A node as claimed in claim 5, and arranged such that, upon a determination that, in addition to acting as master end node for said existing route, it is also to act as master end node with respect to one or more other existing routes, it generates the common signature as a route-finder signature, said determination constituting said common circumstance.

8. A node as claimed in claim 7, and arranged to send, in use, the common signature to all its neighbouring nodes.

9. A fully or partly meshed communications network of nodes, comprising nodes as claimed in claim 5, wherein the nodes are substantially identical.