FIELD OF THE INVENTION
The present invention relates to a communication network and a method for
managing the communication network.
BACKGROUND OF THE INVENTION
In distributed systems, knowledge of the entities which form the system is
essential for the system. For instance in a cluster of workstations employing a
distributed load balancing algorithm to serve client requests, each workstation
needs to be aware of all other workstations in the cluster and the load on each
one of them. If a workstation becomes unavailable in the event of a failure, the
remaining workstations need to quickly identify the failure and inform their
respective load balancing algorithms of the unavailability of the workstation,
ensuring optimal load distribution. In highly dynamic environments where entities
join and leave the group frequency and the communication network fails
sporadically, maintaining group information becomes a non-trivial issue.
To maintain this group membership information, protocols use different graph
topologies like rings, stars and trees to represent the group. A group member is
represented as a vertex or node in the graph and the logical communication link
between members as an edge between nodes.
One solution is periodic broadcast or multicast by every node to all other nodes
in the network. The amount of messages that gets generated with the size of the
cluster is multi-fold (O(N2) - were N is the size of network). This ensures fast
convergence time in case of state changes in the network but is very un-reliable
with large number of interconnected systems. The higher the number of
messages generated in the network, the more is the chance of a message loss.

This will raise false alarms among few nodes and the group membership protocol
will work inappropriately.
In another method, each node sends messages to a central node and the central
node will inform to all other nodes using some broadcast mechanism. This will
make the single node to be a bottleneck and may have many delays while
processing large number of messages from all the nodes in the network.
There is another method in which few nodes act as membership servers, and
when any of the other nodes in the system needs membership information, they
send a request to one of these servers. To maintain the state information across
membership servers becomes a tedious task and may tend to perform
inefficiently when the network size grows.
OBJECT OF THE INVENTION
It is therefore an object of the present invention to propose a communication
network and method for managing a communication network.
SUMMARY OF THE INVENTION
This object is achieved by a communication network,
- comprising an arrangement of nodes, each of the nodes being a leader
node or a child node of one of the leader nodes,
- each of the leader nodes having unidirectional links to a number of other
leader nodes, the number of other leader nodes being a function of n1, n1
being a total number of leader nodes.

This object is achieved by a method for managing a communication network,
comprising:
- arranging nodes of the network, each of the nodes being a leader node or
a child node of one of the leader nodes, depending on a total number of
nodes;
- each of the leader nodes having unidirectional links to a number of other
leader nodes, the number of other leader nodes being a function of n1, n1
being a total number of leader nodes.
The underlying idea of the present invention is to provide a network having the
nodes arranged as leader nodes and child nodes of the leader nodes. A leader
node is linked to only a number of other leader nodes in the network which is
derived from the total number of leader nodes. For peer detection, child nodes
periodically send messages to their leader node, which transmit these messages
to other leaders nodes linked to it. The leader nodes transmit the received
message to their child nodes. This results in a uniform view of the entire network.
In a preferred embodiment, a maximum number of child nodes of each leader
node equals n1-1. The present network arranges the node in a balanced state,
such that the number of child nodes along with their leader node equals total
number of leader nodes in the network. Hence if gCb is the number of leader
nodes, and nCb is the number of child nodes of each leader node along with the
leader node, then total number of nodes in the network (N) would be gcb* ncb. In
a completely balanced state, gCb = nCb- Therefore gCb = nCb= VN.
In a further preferred embodiment, the leader nodes maintain skip lists for the

unidirectional links to the other leader nodes in the network. Skip lists are based
on the concept of linked lists. In addition to pointers provided in linked lists to the
next node, skip lists have pointers to further nodes also. Such number of further
nodes can be calculated based on the total number of nodes
In another embodiment, a new node is added to the network as one of, a child
node of one of the leader nodes, depending on n1, a respective number of child
nodes of the leader node, and a maximum size of the network; or a new leader
node in the network when each leader node in the network has a number of child
nodes equal to n1-1. In a completely balanced state, as described above, gcb =
ncb. Hence a new node is made a separate leader node. In case the network is
not in a completely balanced state, the new mode is assigned as a child node to
one of the leader nodes in the network depending on the number of child nodes
of each leader node, the number of leader nodes and the total number of nodes
in the network.
BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS
The present invention is further described hereinafter with reference to illustrated
embodiments shown in the accompanying drawings, in which:
Figure 1 shows a general structure of the topology of an embodiment of the
present invention,
Figure 2 to Figure 7 illustrate by an example how a network grows, using an
embodiment of the present invention,
Figure 8 shows a flowchart relating to a method of managing a topology,

Figure 9 shows a flowchart relating to a method of message transmission in a
network,
Figure 10 shows a graph comparing message complexity of various known
topologies with the topology according to an embodiment of the present
invention,
Figure 11 shows a graph comparing efficiency of various known topologies with
the topology according to an embodiment of the present invention, and
Figure 12 shows a graph comparing robustness of various known topologies with
the topology according to an embodiment of the present invention.
DETAIL DESCRIPTION OF THE INVENTION
All nodes in the present network are assigned a unique node ID (NID) and a
group ID (GID). The GID is usually the same for all child nodes attached to the
same leader node and is the same as the leader node's NID. All nodes having
the same GID are henceforth referred to as a group.
In a preferred embodiment, the leader nodes are connected via a data structure
which provides link to a number of other leader nodes in the network, depending
on the data structure. In one embodiment the leader nodes are connected via
skip lists. A skip list is a probabilistic data structure, based on linked lists having
additional forward pointers. Each leader node, in the present network, maintains
logc (ni) links, where there are ni leader nodes and c is configurable.
Figure 1 shows the structure of the network as per an embodiment of the present

invention. Figure 1 shows the nodes arranged in groups. Each group has a
leader node 11-15. The leader node of a group is directly connected to a number
of leader nodes, which are in turn directly connected to other leader nodes via a
data structure 16-25. The leader nodes are also connected to their child nodes
130. Thus there is a connection between all the nodes. This increases efficiency
and robustness of the topology.
As per a preferred embodiment of the present invention, the present network is
said to be in a completely balanced state when the total number of nodes, N, in
the network, is exactly the square of a positive integer greater than 1. The node
joining immediately after the network attains a completely balanced state is
assigned a leader node status. In a completely balanced state, the number of
groups in the network (gct>) equals the next positive integer of (square root of size
of the network, N) i.e. p/N] each leader node of the groups having V(N-1) child
nodes attached to it. And in a completely balanced state, the number of nodes in
each group, nCb, equals number of groups in the network, gcb.
As an example, for a balanced network, the number of skip-lists a leader node
maintains is log2 (VN), where the number of leader nodes in the network is VN.
So, if i = log2 (VN), a node with NID x will be directly linked to nodes with NID
X+2°...X+2'-1.
GID of nodes is derived as I * p/S"|, where {i = 1, 2, 3 ... rVSi, "S" being a
maximum size the network can grow.
The GID of a group to which a new node joining the network is assigned, is
based on the conditions provided in following Table 1 where S is the maximum
size the network is expected to grow.


The NIDs are retrieved from a Failure Node Index (FNI) if available, for assigning
to new nodes. When a node fails, its NID is put in a Failure Node Index which
allows re-use of the NID. If there is none available in the FNI, the "higher
numbered NID within the group to which the node is assigned + 1" is assigned to
the new node. In case of a new group, NID of the first child node of the group is
GID+1.
The above network is now explained with the help of an example shown in Figure
2 - Figure 7.
In this example S is given a value of 1000000 i.e. the maximum size the network
is expected to grow is 1000000. Figure 2 shows one node 20 in the network i e.
N=1.
According to table 1, when N<=3, GID=N*VS, so the GID of the first node 20 is
V1000000 = 1000 as shown in Figure 2.
On addition of a second node 21, N=2, so GID is 2*1000=2000 as shown in
Figure 3.
For the third node 23 N<=3 is still satisfied, so GID is 3*1000=3000, as in Figure
4.

In Figure 5 N=4. So gCb=2, hence (gCb + 1) *nCb gives 6. Since N>3 and <= 6 so,
GID of the new node 24 will be 2000.
(calculated from {^(N-l)-1 +1} *VS) hence the new node 24 will be assigned to
leader node 2000 and will have NID 2001.
Similarly Figure 6 and Figure 7, where N=5 and N=6 and nodes 25 and 26 are
added.
Figure 8 relates to a flowchart for a method 50 for managing the present network,
as per a preferred embodiment
In step 51, the method comprises arranging the nodes in groups, each group
having leader nodes and child nodes of the leader nodes The number of groups
and nodes in each group depends on the total number of nodes in the network.
The group formed in step 51 are linked using a data structure in step 52. In a
preferred embodiment, skip list are used to link the groups. Skip lists provides a
forward pointer in addition to a pointer to the next adjacent node. Each group is
coupled to a predetermined number of groups, depending on total groups in the
network.
Figure 9 relates to a flowchart for a method 60, describing the message
transmission in the network of the present invention, as per a preferred
embodiment.
To manage the network, child nodes in a group send messages to their
respective leader nodes in step 61. The leader nodes consolidate these
messages to determine the child nodes present in the group and exchange
between themselves information, contained in the messages, about child nodes

using skip-lists in step 62. The use of skip-lists reduces the VCT and increases
the robustness of the topology with minimal increase in the messaging
complexity. Only updates are sent to reduce communication bandwidth usage.
The leader nodes get complete information about all other nodes in the network.
They consolidate information received from other leader nodes and propagate
this information to child nodes attached to it resulting in a uniform view of the
entire network, in step 63. Finally the status of the network gets updated at each
node.
In a preferred embodiment, failures in the network are also taken care of.
Failures can occur at two different places, at the child node or at the leader node.
When a child node fails, the leader node of the group will not receive any
message from the failed child node. After one or more cycles of the leader node
not receiving messages from the child node, the leader node declares the child
node to be failed and propagates this information to other leader nodes and the
child nodes attached to it.
When a leader node fails, the child nodes attached to a leader node detect the
failure of the leader node when it fails to provide update messages. The child
nodes confirm the failure of the leader node and select a new leader node from
the child nodes attached to the failed leader node. For instance the child node
with the least NID can become the leader node for the group. The newly elected
leader node then propagates this information to the other leader nodes.
When a node fails, its NID is put in a Failure Node Index or FNI which allows re-
use of NID's. The re-organization of the network is not done on each and every
node failure. The re-organization happens when all the nodes of a particular
group / groups fail.

In an embodiment, a leader node sends a re-organization request to all other
leader nodes in the network. A request is sent to peer leader nodes for identifying
the potential candidate node for leader node of the failed group. If at least one
suggestion is received from the existing peer leaders, one among the suggested
nodes is selected as the leader of the failed group.
The identified new leader node gives his acceptance for becoming a leader. This
information of the new leader is propagated to all the peer leaders in the network.
This information is further propagated down to all the children.
Figure 10, Figure 11 and Figure 12 evaluate various conventional topologies and
compare them with the topology of the network according to an embodiment of
the present invention.
For the purpose of the present document,
- efficiency is a measure of the view convergence time (VCT) or the time
required for all members of the group to have a consistent view of the
entire group. VCT is measured as the maximum number of hops required
for updates to reach between two nodes in the group. It is inversely
proportional to the average path length of a network, hence the lower the
distance or hop count, the higher is the efficiency;
- robustness is a measure of the reachability of the nodes, if the removal of
a node results in the network to split. A combination of functional and
structural robustness is considered here. The robustness of a graph with
respect to a vertex is the ratio of accessibility of the graph obtained after
removing the vertex. Average robustness is the average of robustness
over all the nodes. Worst case robustness is the minimum of robustness
over all the nodes.

- the notion of cost is a measure of messaging complexity. In a network, an
edge represents a communication link between two vertices along which
messages are transmitted. The messaging complexity is proportional to
the number of edges in the network.
Figure 10 is a graph indicating messaging complexity involved in different
topologies.
The x-axis 100 represents the number of nodes and the y-axis 200 is the number
of messages. Line 101 in the graph is for all-to-all topology, line 102 is for tree,
ring and star topologies and line 103 is the topology as per an embodiment of the
present invention.
An all-to-all broadcast has a messaging complexity of the order of 0(n2) and the
tree, ring, star and the embodiment according to the present invention all have a
complexity of the order O(n).
The VCT of different topologies can be seen in Figure 11.
The x-axis 100 in Figure 11 represents the number of nodes and the y-axis 200
is the VCT. Line 110 in the graph is for all-to-all topology, line 111 is fro three,
line 112 is for star topology and line 113 is for the topology as per an
embodiment of the present invention.
All-to-all braodcast has a VCT of 1 and the star topology has a VCT of 2. A tree
topology has a VCT of the order of O(log(n). The graph clearly indicates that the
topology as per the shown embodiment of the present invention outperforms the
tree with respect to the view convergence time.

Figure 12 shows the worst case normalized robustness characteristics of the
various topologies.
The x-axis 100 represents the number of nodes and the y-axis 200 is the
normalized worst case robustness. Line 120 in the graph is for all-to-all topology,
line 121 is tree, line 122 is star topology, and line 123 is the topology as per an
embodiment of the present invention.
The star topology has a robustness of zero. The ring and all-to-all broadcast
topologies have the best worst case robustness characteristics with a value of
one. With the increasing number of nodes, the robustness characteristics of the
present topology approach almost one, while the robustness of the tree fails off
towards zero. Accordingly the shown embodiment of the present invention clearly
has a more robust topology compared to that of the tree.
In light of the above, the present topology provides a significant, improvement in
comparison to hierarchical trees, with respect to view convergence time and
robustness without compromising on messaging complexity.
Although the invention has been described with reference to specific
embodiments, this description is not meant to be construed in a limiting sense.
Various modifications of the disclosed embodiments, as well as alternate
embodiments of the invention, will become apparent to persons skilled in the art
upon reference to the description of the invention. It is therefore contemplated
that such modifications can be made without departing from the spirit or scope of
the present invention as defined.

WE CLAIM
1. A communication network, comprising:
- an arrangement of a plurality of nodes, each of the nodes operating
as one of a leader node (11-15) and a child node (130) of one of
the leader nodes (11-15),
- each of the leader nodes (11-15) having unidirectional links (16-25)
with a number of other leader nodes (11-15), the number of other
leader nodes (11-15) being a function of n1, n1) being a total
number of leader nodes (11-15),
wherein the child nodes (130) and the leader nodes (11-15) in the network
are configured to perform:
• message transmission from the child nodes (130) to their
respective leader node (11-15) in the network are configured to
perform:
• circulation of the messages received by the leader node (11-15), to
the other linked leader nodes (11-15) of the network; and
• message transmission from the other linked leader nodes (11-15)
to their respective child nodes (130),
the messages comprising an updated status of the network.
2. The communication network as claimed in claim 1, wherein a maximum
number of child nodes (130) of each leader node (11-15) equals n1-1.

3. The communication network as claimed in any of the preceding claims,
wherein the leader nodes (11-15) maintain skip lists for the unidirectional
links to the other leader nodes (11-15)
4. The communication network as claimed in any of the preceding claims,
wherein a new node is added to the network as one of,

• a child node (130) of one of the leader nodes (11-15), depending
on n1, a respective number of child nodes (130) of the leader node
(11-15), and a maximum size of the network,
• a new leader node (11-15) in the network when each leader node
(11-15) in the network has a number of child nodes (130) equal to
n1-1
5. A method for operating a communication network, comprising:
- arrangement a plurality of nodes on the network, each of the nodes
acting as one of a leader node (11-15) and a child node (103) of
one of the leader nodes (11-15), depending on total number of the
nodes;
- each of the leader nodes (11-15) having unidirectional links with a
number of other leader nodes (11-15), the number of other leader
nodes (11-15), the number of other leader nodes (11-15) being a
function of n1, n1 being a total number of leader nodes (11-15),
wherein, the method further comprising:

• transmitting messages from the child nodes (130) to their
respective leader node (11-15),
• circulating the messages received from the child nodes (130), by
the leader node (11-15), to the other linked leader nodes (11-15) of
the network; and
• transmitting the messages from the other linked leader nodes (11-
15) to their respective child nodes (130),
the message comprising an updated status of the network.
6 The method as claimed in claim 5, comprising arranging the nodes in the
network such that a maximum number of child nodes (130) of each leader
node (11-15) equals n1-1.
7. The method as claimed in claim 5 or 6, wherein the leader nodes (11-15)
maintain skip lists for the unidirectional links to the other leader nodes (11-
15) in the network
8. The method as claimed in any of claims 5 to 7, wherein adding a new
node to the network comprises one of,

• assigning the new node as a child node (130) of one of the leader
nodes (11-15) in the network depending on n1, a respective number
of child nodes (130) of the leader node (11-15), and a maximum
size of the network, and
• adding the new node as a new leader node (11-15) in the network

when each leader node (11-15) in the network has a number of
child nodes (130) equal to n1-1.

ABSTRACT

TITLE: "COMMUNICATION NETWORK AND METHOD FOR MANAGING A
COMMUNICATION NETWORK"
A communication network, comprising an arrangement of a plurality of nodes,
each of the nodes operating as one of a leader node (11-15) and a child node
(130) of one of the leader nodes (11-15), each of the leader nodes (11-15)
having unidirectional links (16-25) with a number of other leader nodes (11-15),
the number of other leader nodes (11-15) being a function of n1, n1) being a total
number of leader nodes (11-15), wherein the child nodes (130) and the leader
nodes (11-15) in the network are configured to perform: message transmission
from the child nodes (130) to their respective leader node (11-15) in the network
are configured to perform: circulation of the messages received by the leader
node (11-15), to the other linked leader nodes (11-15) of the network; and
message transmission from the other linked leader nodes (11-15) to their
respective child nodes (130), the messages comprising an updated status of the
network.