Note: Descriptions are shown in the official language in which they were submitted.
2138~
METHOD OF TRANSMITTING COMMUNICATION SIGNALS VIA
THE SHORTEST ROUTE BETWEEN A PAIR OF NODES IN A
NETWORK
5 BACKGROUND OF THE INVENTION
This invention relates to a method of transmitting
communication signals via the shortest routes in a network. It is
particularly applicable to a network with time varying topology, such as is
encountered in telecommunication systems.
A typical telecommunications network has a number of
switching nodes interconnected by transmission trunks (bidirectional
links) which carry the communication signals. While the physical length
of each trunk will generally remain fixed, other operating parameters can
vary. For instance, traffic on the network will vary with time and can
readily affect operating costs, accessibility and delays times encountered in
any one link of the network. It is therefore desirable to be able to
dynamically select the shortest route (e.g. least cost, shortest time delay etc.)
between any two nodes in the network, to optimize network usage.
One known method utilizes the well known Dijkstra
algorithm as described in "Routing In Data Networks", Data Networks,
Bertsekas and Gallager, Chapter 5, pp.315-323, 1987. The general approach
which follows, is to find the shortest routes in order of increasing route
length.
In the network directory, each link (I,J) is characterized by a
(direction independent) length LEN(I,J) that can change with time with the
following kinds of information being maintained:
1. node labels S(I) indicating distance from the source node;
2. set P of nodes closest to source;
3. set Q of other nodes;
4. a shortest route tree (stored as a table) providing adjacency
of nodes in the set P.
To determine the shortest route between a source node and a
destination node using Dijkstra:
Step 1 (initialization):
3 5 S(source) = 0
S(I) = LEN(source,I) for nodes I adjacent to the source
21~8~92
S(I) = greater than the total length of any route connecting any two nodes
in the network, for all other nodes I
set P contains the source
set Q contains all other nodes.
Step 2 (one-step Dijkstra's algorithm):
Find the next closest node I and add it to the set P. Adjust the
shortest route tree.
Update label distances S(J) for all nodes J adjacent to node I:
S(J) = min[S(J), S(I)+LEN(I,J)].
Step 3 (stopping criteria):
If P contains all nodes then stop. The algorithm is complete.
Else, go to step 2.
This basic prior art algorithm has been shown to result in the
15 worse case computational complexity, with the complexity being
proportional to the power 2 of the number of nodes on the network.
Potentially much can be gained by stopping the calculations when a node I,
identified as the closest to the source, turns out to be the destination.
Properties of the Dijkstra algorithm assure that continued execution brings
20 nothing new to the shortest route already determined between the source
and destination.
An improved method, described in a paper by T.A.J.
Nicholson, entitled "Finding the shortest route between two points in a
network", Computer Journal, No, 9, 1966, pp.275-280, targets selection of a
25 shortest route between two nodes in a network. The procedure is to
examine all routes out of the source and into the destination as far as their
adjacent connected nodes, and then to extend further the route which has
so far covered the least distance. This process is iterative until a route out
from the source has a point on it which has already occurred on a route
30 into the destination. The length of this route is as small as the minimum
sum of the distances of routes out of the source and routes into the
destination, determined thus far.
However, this Nicholson method exhibits some inefficiencies.
One is a bias towards examining all the shortest routes in the
35 neighborhood of one node which could slow down route selection
conversion towards the shortest route between the two given nodes. For
- 2138092
instance, in a shortest route between two nodes, a part of that route which
is in the neighborhood of the destination node might turn out to be
significantly longer than a number of shortest routes considered in the
neighborhood of the source node, most of which could be leading away
from the destination node. Using Nicholson, no consideration is given to
the longer route incident to the destination node until all shorter routes
have been examined in the neighborhood of the source node.
An example in telecommunications would be when the
source node, a switching office, was located in a dense area of the network,
closely surrounded by numerous other switching offices, while the
destination node, also a switching office, was located in a remote area of
the network and was connected by a single very long link to the balance of
the network. The Nicholson procedure merely extends the shortest route
(i.e.: that closest to the source node) instead of aiming at getting the
shortest route as the outcome of the selection.
Also, the stopping condition involves searching for two
minima over subsets of nodes examined in the neighborhoods of both end
nodes. This is the outcome of the previous inefficiency. Hence, the
complexity of this stopping condition verification is proportional to the
number of separate shortest routes between both end nodes.
A totally different approach is described in United States
Patent 4,987,536 entitled "COMMUNICATION SYSTEM FOR SENDING
AN IDENTICAL ROUTING TREE TO ALL CONNECTED NODES TO
ESTABLISH A SHORTEST ROUTE AND TRANSMITTING MESSAGES
THEREAFTER" issued Jan. 22 1991 to Pierre A. Humblet. Here each
reference node receives a routing tree from each adjacent node. Upon
receipt the reference node produces a larger tree with itself as the root.
SUMMARY OF THE INVENTION
The inefficiencies of these prior art algorithms have been
improved upon in the present invention by a route selection method
which:
(1) operates alternately from both end nodes to provide better
computational efficiency. This is due to the fact that, on the average, the
adjacent subnetwork for each end node is much smaller than the whole
~138~2
network resulting in a much shorter time needed to select the next shortest
routes locally, one per end node;
(2) stops operating alternately from both end nodes as soon as
a node added to local set of closest nodes is found to have already been
included in the set of nodes closest to the other end node then the route
selection proceeds from this one end node while the condition for stopping
alternate selection remains true; and
(3) terminates as early as one end node is identified as the
closest node to the other node.
o Thus, in accordance with the present invention there is
provided in a communications network having a plurality of nodes, the
nodes in the network being interconnected via bidirectional links, a
method of transmitting communications signals via the shortest route
between a first end node and a second end node selected from a plurality of
15 nodes in a network, the method comprising the steps of: (a) maintaining a
directory of the nodes in the network, and the length of each of the
bidirectional links; (b) maintaining a record of a first set of nodes, which
includes the first end node; (c) maintaining a record of a second set of
nodes, which includes the second end node; (d) adding one of the nodes
20 from the directory to a selected one of the sets, the added node being an
adjacent one to a node of that one set, and being the next closest node to the
end node of that set, to identify the shortest route currently known;
(e) determining: (i) whether the just added node matches the end node of
the other set, or (ii) whether the just added node of that one set in the
25 shortest route currently known, match the node of the other set;
(f) selecting: (i) the alternate one of the sets if none of the conditions (e) is
true and repeating from step (d) until a match is determined in step (e (i));
and (ii) the same one of the sets if match is determined in step (e(ii)) and
repeating from step (d); thereby identifying the shortest route between the
30 end nodes via the matching nodes, over the bidirectional links having the
shortest route length; and (g) transmitting communications signals
between the end nodes via the shortest route length.
The method of the present invention, which particularly
centers around the unique termination criteria, and switching mode of
35 operation from alternate to one-ended, can provide a significant
improvement in efficiency over the Dijkstra method where all iterations
~138~92
originate from one end. For instance in a large network if it is assumed
that: the number of nodes is proportional to the area covered; and the
shortest route to each added node expands radially outward from the end
node; then the number of iterations required to find the shortest route
5 between two nodes applying the Dijkstra algorithm from one end only,
could be up to four times the number of iterations required when applying
the iterations alternately from both ends, and using the terminating
criteria of the present invention.
10 BRIEF DESCRIPTION OF THE DRAWINGS
An example embodiment of the invention will be described
with reference to the accompanying drawings in which:
Figure 1 is a schematic representation of a
telecommunications network;
Figures 2A to 2F illustrate the progressive selection of the
nodes in the network in Figure 1 to determine the shortest route between
two end nodes; and
Figure 3 is a flow chart of the algorithm used to determine the
shortest route.
DESCRIPTION OF THE PREFERRED EMBODIMENT
Referring to Figure 1, there is illustrated a
telecommunications network comprising a plurality of switching centers,
as represented by nodes 1 to 9 (enclosed in circles), each with its own
25 unique identity. The nodes 1 to 9 are interconnected by communication
trunks, represented by bidirectional links, each having a given length
(ranging from 1 to 11 in the example) which can vary over time with such
operating parameters as the initial and instantaneous operating costs, the
queue (time delay) of information packets awaiting transmission or any
30 combination of these and other parameters. When establishing a route
between two end nodes, it is desirable to utilize the least cost or shortest
route to optimize network utilization. In this example embodiment, the
source node 1 and the destination node 9 are the selected end nodes.
Initially, information on the current operating state (length of
35 the bidirectional links and operating state of the nodes) is conveyed over
conventional control channels from each of the nodes 1 to 9, to a control
21~8~92
center which typically is at the originating end of the communications link
(in the present case the source node 1). The control center at node 1 then
performs the following algorithm to determine the shortest route through
the network, which can then be used to establish the telecommunications
5 route from the source node 1 to the destination node 9 in a well known
manner .
Referring to Figure 3, the algorithm basically comprises the
steps of:
1) initializing: i) a directory to include updated information
10 on the length of the links; and ii) two sets of records each including one of the end nodes;
2) selecting one of the sets;
3) executing one step of the Dijkstra algorithm on the selected
set;
4) testing to determine whether the shortest route has been
found using an unique set of criteria;
5) if so, terminating the execution of the algorithm;
6) else selecting the other set and repeating steps 3), 4) and 5).
In the following mathematical description: i) each node is
20 unique and symbolized by capital letter "I"; ii) each link is identified by apair of adjacent nodes (I,J); and iii) each link is characterized by a (direction
independent) length LEN(I,J) that can change with time.
The following kinds of information are maintained:
1. node labels Ds(I) and Dd(I) indicating distance of node I
25 from source and from destination, respectively;
2. sets Ps and Pd of nodes closest to source or to destination,
respectively;
3. sets Qs and Qd of other nodes, not closest to source or to
destination, respectively;
4. shortest route trees TREEs and TREEd (stored as tables)
providing adjacency of nodes in the sets Ps and Pd, respectively. (They can
be organized as doubly linked lists to speed up search for adjacent nodes in
step 6.)
21~9~
Step 1 (initialization):
Ds(source) = O,
Dd(destination) = O
Ds(I) = LEN(source,I) for nodes I adjacent to the source
Ds(I) = greater than the total length of any route connecting any two nodes
in the network, for all other nodes I
Dd(I) = LEN(destination,I) for nodes I adjacent to the destination
Dd(I) = greater than the total length of any route connecting any two nodes
in the network, for all other nodes I
o set Ps contains the source
set Qs contains all other nodes
set Pd contains destination
set Qd contains all other nodes
Go to step 2.
Step 2 (pick a node):
Select an end node to start execution of the computing
apparatus. Since the source or destination can be selected equally likely, we
shall use a generic term `this end node' and denote it X. Consequently, we
shall use Dx to denote distance from X, Px for a set of nodes closest to X, and
Qx for a set of other nodes.
Go to step 3.
Step 3 (one-step Dijkstra's al~orithm):
Out of the nodes in the set Qx find the node I closest to this
end node X and add it to the set Px. Adjust the shortest route tree in table
2 5 TREEx:
- add a record of node I with distance Dx(I) and a reference (or
pointer) to its adjacent node K in a direction towards root node X;
- add a reference (a pointer) to node I, to the record of node K
via which node I is reachable.
Update label distances Dx(J) for all nodes J in set Qx adjacent to
node I:
Dx(J) = min[Dx(J), Dx(I)+LEN(I,J)].
Go to step 4.
21~8~92
Step 4 (stoppin~ criterion):
a) If node I is the other end node, then a shortest route has
been selected. Go to step 6.
b) Else, if node I is already included in the set P of nodes
closest to the other end then continue route selection out of this end. Go to
step 3.
Else, go to step 5.
Step 5 (pick the other end node):
Select the other end node to continue execution of the
o computing apparatus. If calculations before were done for the source, they
will be done now for the destination. If calculations before were done for
the destination, they will be done now for the source. Use a generic term
`this end node' for the selected end node and denote it X. Consequently,
use Dx to denote distance from X, Px for set of nodes closest to X, and Qx for
set of other nodes. Go to step 3.
Step 6 (a shortest route is selected):
For stopping criterion (a), the sequence of trunks between
node X and the other end node I can be established using node adjacency
data in table TREEx.
Repeated iterations of the Dijkstra algorithm using the
example embodiment illustrated in Figure 1 are shown in Figures 2A to 2F
in which the objective is to find the shortest route from the source node 1
to the destination node 9. In each of the Figures, the first number in
brackets identifies the node, and the second number the total length of the
bidirectional links from that node to the end node of that set (either source
node 1 or destination node 9).
After initialization of the directory and the sets of records as
illustrated in Figure 3, the first iteration of the Dijkstra algorithm is applied
to the first set containing the source node 1. Nodes 2, 3, 4 are identified as
being: i) not in the first set and ii) adjacent the source node. Of these, node
2 with a route length of 1 is closest to the source node as shown in Figure
2A and is therefore, added to the first set. A test determines that the
termination criterion is not met, with the result that the second set (other
set) is selected and the algorithm is repeated. This time the nodes, not in
3 5 the second set that are adjacent the end node, are nodes 6, 7, and 8. In thepresent example, node 6 is selected and added to the second set as shown in
21~8~
Figure 2B. Again neither of the termination criteria is met, so the
algorithm is again repeated with the first set. This time, node 3 is selected
and added to that set, as shown in Figure 2C.
Iterations of the algorithm are repeated as shown in Figures
5 2D, 2E, until the termination criterion is satisfied. This is illustrated in
Figure 2F, where it can be seen that node 1, just added to the second set is
the source node (the other end node). As a result the algorithm is
terminated and the shortest route, comprising nodes 1, 2, 3, 6, 9 with a
route length of 10 is selected.
Instead of executing the Dijkstra algorithm consecutively on
each of the sets, the algorithm can be executed concurrently on each set
using two processors to expedite the determination of the shortest route.
In any case the machine implemented method produces a description of
the shortest route between the two selected end nodes, to enable efficient
15 use of the network for the transmission of communications signals and the
like.
