WO1998013967A1

WO1998013967A1 - Method and arrangement for message based synchronisation

Info

Publication number: WO1998013967A1
Application number: PCT/SE1997/001468
Authority: WO
Inventors: Tobias Adelgren
Original assignee: Telefonaktiebolaget Lm Ericsson (Publ)
Priority date: 1996-09-24
Filing date: 1997-09-03
Publication date: 1998-04-02
Also published as: AU4140897A; SE506175C2; SE9603479L; SE9603479D0

Abstract

The invention relates to a device in nodes in a network and a process for establishing or re-establishing a synchronisation network in the said network. The invention is characterised in that means of reading in are adapted to read in synchronisation strings from adjacent nodes and that the synchronisation strings read in comprise a sequence of node names representing the nodes which the synchronisation string has passed previously, including the synchronisation source. The invention is further characterised in that means of selecting link to the synchronisation source are adapted to select either one of the synchronisation strings read in or none at all, according to a predetermined pattern, in that means of operation are adapted to form a new synchronisation string and that the means of writing are adapted to write the new synchronisation string to the adjacent nodes.

Description

METHOD AND ARRANGEMENT FOR MESSAGE BASED SYNCHRONISATION

TECHNICAL SPHERE

The present invention relates to a device in nodes in a network of interconnected, named nodes in which each node is associated with a value indicating with what priority it is to be used as synchronisation source for other nodes. The nodes are adapted to each read the synchronisation messages which are written from adjacent nodes and from these synchronisation messages to determine which node is to act as synchronisation source.

The invention also relates to a telecommunications system which uses message-based synchronisation.

The invention furthermore relates to a process for establishing or re-establishing a synchronisation network in a network of interconnected named nodes.

PRIOR ART

In networks of nodes which are connected together by transmission lines synchronisation of the nodes is often achieved in that one of the nodes acts as master and other nodes are synchronised with the said master node. This is achieved by designating a node with highest priority. Should the master node be disconnected from the network for any reason, for example due to interruptions in one or more of the transmission lines, another node should act as master for other nodes. Ranking a plurality of nodes or all nodes in a network according to the priority in which they are to be used as master node for other nodes is therefore already known. The nodes then exchange the synchronisation messages with adjacent nodes, the synchronisation messages stating which node is master. From the synchronisation messages of adjacent nodes, the nodes are suitably adapted to select one message indicating a master node with highest priority.

However, this dynamic establishment of a synchronisation network carries a risk that "false" information may begin to circulate in the network. This false information occurs in that the synchronisation messages originating from a disconnected master node remain in the network, despite the fact that the said master node is consequently no longer supplying the network with synchronisation messages. This is due to the fact that each message has a certain transmission time, which is always greater than zero. The nodes in the network have no indication that the master node has been disconnected, but receive and relay old messages from the said disconnected master node, as a result of which loops may be formed in which these erroneous synchronisation messages circulate. These loops may disrupt all other traffic on the network.

A method and a device intended to solve this problem of circulating false information are already known from WO 95/24 772. Having the synchronisation messages contain both information on which node is synchronisation source (master) and a parameter indicating the distance to the synchronisation source is known from this publication. This parameter is thus increased by one increment each time the synchronisation message passes a node The said parameter is then monitored by each of the nodes and if the parameter increases a predetermined number of times in succession whilst the synchronisation source is the same, this is assumed to be a result of false signals circulating in the network

A disadvantage with this known solution is that the nodes may first accept false information as the correct synchronisation signals and relay these a number of times before they are made to accept that the synchronisation messages are in reality false information originating from a synchronisation source no longer accessible. Another disadvantage is that the said parameters cannot be used for an application more sophisticated than the representation of a distance.

DESCRIPTION OF THE INVENTION

The present invention is intended to effectively prevent false information in the guise of correct synchronisation messages circulating in a network of interconnected nodes

This is achieved by a device in nodes in a network of named nodes interconnected by way of lines, in which the nodes are associated with a value indicating with what priority they are to be used as synchronisation source for other nodes The device in each of the nodes comprises means of reading in information in the form of synchronisation strings from adjacent nodes, the synchronisation strings comprising a sequence of node names representing the nodes which the synchronisation string has previously passed, including the synchronisation source. The device in each of the nodes is adapted to select link to the synchronisation source by selecting either one of the synchronisation strings read in or none of them in a predetermined manner.

Should the device in a node select one of the synchronisation strings read in, this is adapted to form a new synchronisation string by adding its own node name to the sequence of node names in the selected synchronisation string Should none of the synchronisation strings be selected, the device is on the other hand adapted to form the new synchronisation string from its own node name. Finally the device in each of the nodes comprises means of writing in order to write information in the form of the new synchronisation string to adjacent nodes.

This is also achieved in that the said device is arranged in each node in a telecommunications system using message-based synchronisation.

This is also achieved by a process by means of which a synchronisation network is established or re-established in a network of named nodes interconnected by way of lines. The process assumes that the nodes are each associated with a value indicating in what priority they are to be used as synchronisation source for other nodes. The nodes in the network are made to read in the synchronisation message in the form of synchronisation strings from adjacent nodes, the synchronisation strings comprising a sequence of node names, representing the nodes which the synchronisation message has passed previously, including the synchronisation source. Each of the nodes is made to select a link to the synchronisation source. This is done in that either one of the synchronisation strings read in is selected or none at all, according to a predetermined pattern. Thereafter each of the nodes is made to form a new synchronisation string. Where one of the synchronisation strings read in was selected, this is done by adding its own node name to the sequence of node names in the selected synchronisation string. Where no synchronisation was selected this is done by forming the new synchronisation string from its own node name. Finally each of the nodes is made to write the new synchronisation string to adjacent nodes.

The advantage with the device according to the invention and the process according to the invention is that the entire sequence of nodes which the synchronisation string passes is included in the synchronisation strings which are exchanged between the nodes. If each of the nodes selects links by selecting one of those synchronisation strings present in which the sequence of node names does not include its own node name and in which the synchronisation source has a higher priority than the node itself, the false synchronisation messages are effectively prevented from circulating in the network.

DESCRIPTION OF FIGURES

Fig. 1 shows an example of a network in which the present invention is adapted to function Fig. 2 shows a flow chart of the process in each node in the network in order to establish and re-establish a synchronisation network.

PREFERRED EMBODIMENTS The invention will be explained below with reference to the figures. Fig. 1 shows a network comprising nodes (circles) and transmission lines (solid lines), the transmission lines (links) constituting connections between the nodes. The network is preferably a telecommunications network. Each of the nodes is named. A priority is associated with each node name, either intrinsic to the node name or received by way of a data base in the node. The priority is common to the entire network. For implementation reasons it is a good idea to name the nodes in such a way that it is easy to determine from the node names the priority with which each node is to be used as synchronisation source for other nodes. Thus in the network shown in fig. 1 node A has the highest priority, node B the next highest priority etc. It may be advisable to rank ail nodes right down to those with the lowest priority, even though these nodes are rarely if ever used as synchronisation source for other nodes.

The flow chart in fig. 2 illustrates the various stages in the establishment according to the invention of a synchronisation network through which the equipment in the nodes learns by way of a decision taken locally which node is the synchronisation source (master) in the network. In stage 1 in fig. 2 all nodes are in an initiation condition in which they assume that they are their own synchronisation source. Each of the nodes, by way of accessible transmission lines, informs its adjacent nodes of the priority of its synchronisation source. This is done in that each of the nodes sends messages regarding synchronisation, the messages comprising a string containing its own node name, from which the priority of the node can be determined, and an initiation value of a weighting factor w; in one embodiment w_start=0. Let us call the message regarding synchronisation which a node with the node name n writes to adjacent nodes for a synchronisation string S(n), where in the initialisation condition S(n)={ n,w_start}={ n,0} . In the case shown fig. 1, the node name n corresponds to the node names A, B, C, ... and G. The nodes A, B, C ... G respectively thus write their synchronisation strings S(A), S(B), S(C), ... S(G) respectively to their adjacent nodes, that is node A writes S(A) to node E and node F, node B writes S(B) to the nodes D and G, node C writes S(C) to the nodes D, E and F etc.

In stage 2 in fig. 2 each of the nodes reads the synchronisation strings which were written by their adjacent nodes, with which contact is achieved by way of the transmission lines. The nodes store information on their own node name and further information I(n), which will be used on stages 3 and 4, and for that reason this information I(n) will be described in more detail in connection with these. In one embodiment the nodes store the synchronisation strings read in, together with a string called the reference string, comprising its own node name and the information I(n). We will call the reference string for R(n), where R(n)=(n,I(n)}. In the case in fig. 1 therefore node A stores the strings S(E), S(F) and R(A); node B stores S(D), S(G) and R(B) etc.

In stage 3 each node n selects link to the synchronisation source by selecting any of the stored strings, either one of the synchronisation strings read in, or the reference string R(n), according to a predetermined pattern.

In stage 4 a new synchronisation string is created. This process varies according to whether the node n selected one of the synchronisation strings read in or the reference string. If one of the synchronisation strings read in was selected (denoted by S(selected) in fig. 2), the new synchronisation string is formed by adding its own node name from the reference string to the sequence of node names in the selected synchronisation string and adding a predetermined number x to the weighting factor w in the selected synchronisation string. The number x is obtained by using the stored information I(n) according to which synchronisation string was selected. This will be described in more detail later. The synchronisation string consequently comprises a "list" containing the names of all nodes which the synchronisation message has passed previously. If, on the other hand, the node n selected the reference string R(n), signifying that the node selected itself as its synchronisation source, the new synchronisation string is formed by the node name from the reference string and an initial value for the weighting factor, in one embodiment w_slart=0; consequently the new synchronisation string becomes {n,0}. In both cases the new synchronisation string forms a new message S_new(n).

In stage 5 the new message S_ne (n) is written to the adjacent nodes. The entire procedure is then repeated starting from stage 2. The synchronisation network is established when the node situated furthest from the synchronisation source (the master) learns which node is the synchronisation source. Since the nodes nearest the synchronisation source are first to learn which node is synchronisation source and this is then disseminated to one more node each time the procedure is repeated, the node furthest from the synchronisation source is informed when a number of cycles has elapsed which corresponds to the distance between the said node and the synchronisation source. Note that an established synchronisation network need not necessarily use all transmission lines, accessible in the network.

After some cycles have elapsed the synchronisation strings which are exchanged between the nodes will contain a long sequence of node names, representing nodes which have been passed previously. First in the sequence of node names in a synchronisation string received by a node is the synchronisation source (i.e. the master), followed thereafter by a number of nodes which the message has passed, and last in the sequence of node names is the node which sent the synchronisation string to the said node. In the light of this, a preferred embodiment of the invention will be described below, in which the selection of link according to the above-mentioned predetermined pattern (stage 3) makes effective use of the information which is exchanged between the nodes.

In the preferred embodiments of the invention the synchronisation strings which include the nodes own node name are first sorted out. This effectively prevents

"false" information being disseminated in the network and forming loops, since the equipment in one node never selects a string which has previously passed the said node. Once these synchronisation strings have been sorted out, strings (the reference string and/or synchronisation strings) in which the synchronisation source (the master) does not have highest priority are also sorted out. Either the reference string or one or more of the synchronisation strings now remain. Where it is the reference string that remains, this is selected, and where it is one of the synchronisation strings that remain, this is selected. Should more than one synchronisation string remain, the weighting factor decides which string is to be selected. If it is still not possible to select a synchronisation string, the string which is written by the neighbouring node having the highest priority may be selected, for example; in other words the priority of the last node name in the list of node names is what decides.

By means of the weighting factor w the synchronisation network can be optimised in various ways. In one embodiment the network is optimised in respect of the number of nodes which the synchronisation string passes, the so-called "hop length". The weighting factor may, however, be used in order to optimise the synchronisation network in many other ways. In another embodiment of the invention the synchronisation network is optimised in respect of the length of the transmission lines (geographical distance) and in a further embodiment in respect of the probability of faults (in most instances referred to as accessibility). In a further embodiment the synchronisation network is optimised in respect of a combination of the above-mentioned. With reference to fig. 1 we shall now describe these embodiments in more detail with regard to the process in the equipment belonging to node C. From this node transmission lines, or links, extend to the equipment in nodes D, E and F. We shall define the following functions, accessible for the equipment in node C, through the information 1(C) in the reference string R(C) as x D, X E, X _F and x c, where x _D,

X^C _E, and x^C|< contain information on the transmission lines between the node C and the nodes D, E and F and where x^Cc contains information on its own node C. Where account must be taken of the weighting factor in the selection of link to the synchronisation source (stage 3 in fig. 2), the synchronisation string is selected so that the weighting factor + a predetermined number is minimised. For each synchronisation string which was not selected earlier in stage 3 in fig. 2 a provisional weighting factor Wj+x, is therefore calculated, where x,=α x^Cj+β x c and where i is the node from which the synchronisation string arrives, i.e. in this case either D, E or F and where and β are two numbers which can be set as follows. The synchronisation string with the lowest associated provisional weighting factor is thus selected as a link to the synchronisation source and in stage 4 in fig. 2 the predetermined number

where i is the node from which the selected synchronisation string arrives, is added to the weighting factor for the selected synchronisation string.

If x _D=χ _E=χ _F=0 and β is an arbitrary number or if β=0 and x _D. x E and x F are arbitrary numbers at the same time that a>0 and x c c>0, preferably with α= 1 and x^Cc=l , where x=l , the synchronisation network is optimised in respect of "hop length", that is the number of equipments between an equipment (in this case the equipment in node C) and the synchronisation source.

If, on the other hand x p, λ u, and x _F respectively are equal to the distance between node C and nodes D, E and F respectively (that is to say the distance associated with the links I_D, 1_E and I_F respectively) and ooO, preferably with oc=l, at the same time that β=0 and/or x^Cc=0 the synchronisation network is optimised in respect of geographical distance. In a combined case, where ooO, β>0 and X^C _D, X^C _E and x^c _F respectively are equal to the distance between node C and node D, E and F respectively and x°c=l the synchronisation network is optimised in respect of the both "hop length" and geographical distance. The ratio between α and β determines how the optimisation must be done.

If, on the other hand, we assume that each link has an accessibility of po, pε and P_F where 0<p,<l and p,=0 means that the accessibility is 0, that is to say there is always a fault on the link and p,= l stands for constant accessibility, that is to say there is never a fault on the link, then x^c _D=l/p_D, x^c _F=l/p_E and x^c ₍ = l/p_F With ooO, and preferably ot=l, at the same time that β=0 and/or x^c _c=0 the synchronisation network is then optimised in respect of the accessibility In a combined case where α>0, β>0 and x

the synchronisation network is optimised in respect of both "hop length" and accessibility The ratio between a and b determines how the optimisation must be done

The solution described in fig 2 functions not only in the establishing of a synchronisation network but also when a synchronisation network is to be reestablished, for example after interruptions on one or more transmission lines or after the equipment at one or more nodes has broken down Since stages 2 to 5 in the loop in fig 2 are performed continuously, in the event of an interruption or failure other ways are sought in order to obtain a stable synchronisation network again If, for example, there should be an interruption on the transmission line AE in fig. I , the device according to the invention represented in the diagram in fig 2 seeks ways (via node F) of obtaining a stable synchronisation network again with node A as the synchronisation source Even if the synchronisation source should be entirely disconnected from the network, for example as a result of the transmission line AF also being affected by an interruption, a synchronisation network will be reestablished in which node B acts as synchronisation source

Claims

1. Device in nodes in a network of named nodes (A, ...G) interconnected by way of lines, the nodes being associated with a value indicating with what priority they are to be used as synchronisation source for other nodes, and the device in each of the nodes comprising means of reading in information from adjacent nodes, means of writing information to adjacent nodes, means of selecting links to the synchronisation source and means of operation, characterised in that,

- the means of reading in are adapted to read in synchronisation strings from adjacent nodes,

- the synchronisation strings read in comprise a sequence of node names, representing the nodes which the synchronisation string has passed previously, including the synchronisation source,

- the means of selecting link to the synchronisation source are adapted, in a predetermined way, to select either one of the synchronisation strings read in or none at all, - the means of operation are adapted, where one of the synchronisation strings read in is selected, to form a new synchronisation string by adding their own node name to the sequence of node names in the selected synchronisation string, and where none of the synchronisation strings is selected to form the new synchronisation string from their own node name and - the means of writing are adapted to write the new synchronisation string to the adjacent nodes.

2. Device according to claim 1 , characterised in that, the means of selecting link are adapted, should the synchronisation strings read in include synchronisation strings in which the sequence of node names does not include the node itself and in which the synchronisation source has a higher priority than the node itself, to select one of these synchronisation strings.

3. Device according to claim 2, characterised in that, - the means of operation are adapted, where none of the synchronisation strings is selected, to include an initial value of a weighting factor when forming the new synchronisation string, and where one of the synchronisation strings read in is selected to add a predetermined number to the weighting factor, -the means of selecting link are also adapted to take account of the magnitude of the weighting factor when selecting the synchronisation string.

4. Telecommunications system which utilises message-based synchronisation and which comprises a plurality of named nodes interconnected by way of lines, each of the said nodes being associated with a value indicating with what priority they are to be used as synchronisation source for other nodes, in which the nodes each have means of reading-in information from adjacent nodes, means of writing information to adjacent nodes, means of selecting links to the synchronisation source and means of operation, characterised in that,

- the means of reading in are adapted to read in synchronisation strings from adjacent nodes, - the synchronisation strings read in comprise a sequence of node names, representing the nodes which the synchronisation string has passed previously, including the synchronisation source,

- the means of selecting links to the synchronisation source are adapted, in a predetermined way, to select either one of the synchronisation strings read in or none at all,

- the means of operation are adapted, where one of the synchronisation strings read in is selected, to form a new synchronisation string, by adding their own node name to the sequence of node names in the selected synchronisation string, and where none of the synchronisation strings is selected to form the new synchronisation string from their own node name and

- the means of writing are adapted to write the new synchronisation string to the adjacent nodes.

5. Telecommunications system according to claim 4, characterised in that, the means of selecting link are adapted, should the synchronisation strings read in include synchronisation strings in which the sequence of node names does not include the node itself and in which the synchronisation source has a higher priority than the node itself, to select one of these synchronisation strings.

6. Telecommunications system according to claim 5, characterised in that,

- the means of operation are adapted, where none of the synchronisation strings is selected, to include an initial value of a weighting factor when forming the new synchronisation string, and where one of the synchronisation strings read in is selected to add a predetermined number to the weighting factor, - the means of selecting link are also adapted to take account of the magnitude of the weighting factor when selecting the synchronisation string. 7 Process for establishing or re-establishing a synchronisation network in a network of named nodes interconnected by way of lines, the nodes each being associated with a value indicating with what priority they are to be used as synchronisation source for other nodes, characterised in that, the nodes in the network are made to:

- read in synchronisation strings from adjacent nodes, the synchronisation strings comprising a sequence of node names, representing the nodes which the synchronisation string has passed previously, including the synchronisation source, - select link to the synchronisation source by selecting either one of the synchronisation strings read in or none at all according to a predetermined pattern,

- form a new synchronisation string, where one of the synchronisation strings read in is selected by adding their own node name to the sequence of node names in the selected synchronisation string, and where none of the synchronisation strings is selected to form the new synchronisation string from their own node name,

- write the new synchronisation string to adjacent nodes.

8 Process according to claim 7, characterised in that, should the synchronisation strings read in include synchronisation strings in which the sequence of node names does not include the node itself and in which the synchronisation source has a higher priority than the node itself, the selection of link according to the predetermined pattern consists of making the nodes select one of these synchronisation strings.

9 Process according to claim 8, characterised in that,

- where none of the synchronisation strings read in is selected, each node is made to include an initial value of a weighting factor when forming the new synchronisation string,

- where one of the synchronisation strings is selected, each node is made to add a predetermined number to the weighting factor when forming the new synchronisation string,

- the selection of link according to the predetermined pattern consists of making each node take account of the magnitude of the weighting factor when selecting the synchronisation string.

10 Process in a network of named nodes interconnected by way of lines which comprises the following stages - the nodes, which are each associated with a value indicating with what priority they are to be used as synchronisation source, read in synchronisation strings from adjacent nodes, the synchronisation strings comprising a sequence of node names, representing the nodes which the synchronisation message has passed previously, including the synchronisation source; - each of the nodes stores the synchronisation strings read in and a reference string including the nodes own node name;

-each of the nodes selects a link to the synchronisation source by selecting either one of the input synchronisation strings read in or the reference string according to a predetermined pattern; -each of the nodes forms a new synchronisation string in that, where one of the synchronisation strings read in is selected, it adds the node name from the reference string to the sequence of node names in the selected synchronisation string, and where the reference string is selected it forms the new synchronisation string of the node name from the reference string; -each of the nodes writes he new synchronisation string to adjacent nodes.