US 6,147,966 AGranted

Route finding in communications networks

AssigneeBritish Telecommunications public limited company

InventorsDavid Johnson, Raymond Soo Khiaw Chng

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method of determining a restoration route as in a fully or partially meshed communications network of nodes, comprising setting, at a slave end node for an existing route, a timeout for receiving a number of forward route-finder signatures from which it will select the signature representing the potential restoration route having the shortest length and return a route confirmation signature; switching, to act as master end node for the existing route and send reverse route-finder signatures to its neighbouring nodes; switching, upon receipt of a reverse route-finder signature at a master end node for an existing route, to act as slave end node, and send a corresponding return signature. Where a slave end node receives a backtrack signature indicating that the potential restoration route no longer has sufficient capacity, the node will switch to act as master end node. Where a forward route-finder signature is received after a node has sent a reverse route-finder signature, a priority route confirmation signature is sent. Where a node has sent a forward route-finder signature, received a reverse route-finder signature, sent a confirmation signature, and subsequently receives a priority confirmation signature, then unless a backtrack signature is received two restoration routes will be established and the nodes will select the better one.

Claims11

Dependent claims

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 accordance with a respective predetermined master/slave relationship, at each of a pair of the nodes, between which pair 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, said determining step being initiated in response to receipt, at each of said pair of nodes, of a signal indicating that an additional route is required in respect of said existing route;
sending from said one node to its neighbouring nodes a forward route-finder signature for said existing route;
receiving at a node a said forward route-finder signature, determining 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 other node, upon the expiry of a predetermined timeout triggered by receipt of-said signal, 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 additional route at said one node upon receipt thereat of the route confirmation signature;
and the method being characterised by the steps of:
responding at said other node, in the event that at said timeout a potential additional route has not been determined, and in the event that said other node has sent a said route confirmation signature but has received a backtrack signature indicative of insufficient capacity for said potential additional route at an intermediate node on said potential additional route, by switching to act as master end node with respect to said existing route;
sending from said other node to its neighbouring nodes a reverse route-finder signature for said existing route;
and
responding at said one node to receipt thereat of said reverse route-finder signature to switch to act as slave end node with respect to said existing route, to determine a respective potential additional route, and to send a corresponding route confirmation signature.

8 more elements

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

to respond, in use, to receipt of a signal indicative of a requirement for an additional route in respect of 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 for said existing route;
to receive, in use, a route-finder signature and to determine whether or not it is an end node for an 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, and, 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 identified by the route-finder signature, to determine, upon expiry of a predetermined timeout triggered by receipt of said signal, a potential additional route for the existing route identified by the route-finder signature, and to send on said potential additional route a route confirmation signature for the existing route identified by the route-finder signature;
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 respond, when acting as slave end node, to expiry of said predetermined timeout in the absence of a determination of a said potential additional route, and to receipt of a backtrack signature indicative of insufficient capacity for said potential additional route at an intermediate node on said potential additional route, to switch to act as master end node with respect to the existing route identified by the route-finder signature and to send a reverse route-finder signature for that existing route to its neighbouring nodes;
and
to respond, when acting as master end node with respect to said existing route, to receipt thereat of a said reverse route-finder signature for that existing route to switch to act as slave end node with respect to that existing route, to determine a respective potential additional route, and to send a corresponding route confirmation signature on said respective potential additional route.

6 more elements

Dependencies are inferred from the claim text.