All-to-All Broadcast in optical WDM ring with 2-length extension and
3-length extension
K. MANOHARAN1, M. SABRIGIRIRAJ2
1Department of ECE, SNS College of Technology, Coimbatore, 641 035, Tamilnadu, INDIA
2 Department of ECE, SVS College of Engineering, Coimbatore, 642 109, Tamilnadu, INDIA
Abstract: - All-to-all broadcast communication is to transmit a distinctive data from each node to every other
node available in the network. This is a fundamental prerequisite in high performance computing and
telecommunication networks including enterprises operating datacenters which may spread across thousands of
nodes by means of WDM optical networks. Wavelengths are scarce resources in WDM optical networks.
Reducing the wavelengths usage is essential to decrease the price and complication of the network. In this
article, a ring network is extended by additionally connecting alternate nodes in order to provide alternate paths
so as to reduce the effective number of hops between the communicating nodes and also to reduce the
wavelength requirements and this network is referred as a ring network with 2-length extension. Similarly, a
ring network is extended by directly linking all nodes which are separated by two intermediate nodes with
additional fibers and this network is referred as a ring network with 3-length extension. For the ring network
with 2-length extension the optimum wavelength number necessary to establish all-to-all broadcast under
unidirectional routing is derived by grouping nonoverlapping connections on a common wavelength. The
wavelength number necessary atmost to establish all-to-all broadcast in a unidirectional ring with 3-length
extension is derived using longest link first routing algorithm.
Key-Words: - All-to-All Broadcast, WDM Optical Network, Linear Array, Wavelength Assignment, RWA,
Modified Linear Array
Received: August 21, 2021. Revised: March 25, 2022. Accepted: April 24, 2022. Published: May 20, 2022.
1 Introduction
A WDM optical network has the potential of
interconnecting thousands of users covering local to
wide area networks. The WDM optical network
employs numerous optical nodes and nodes are
interconnected using optical fibers in some fashion.
WDM technology permits the passage for multiple
wavelength optical signals through the same fiber
and thus provides abundant bandwidth. Each optical
node employs required optical sources (Ex: laser
diodes) at the transmitter section to modulate the
input electrical signals with light signal as carrier
and required optical detectors (Ex: photo diodes) at
the receiver section to demodulate the received
signal and extract the input signal that was fed at the
transmitter. Though the same fiber can be used for
signal transmission in both forward and reverse
directions, it is normally assumed that each optical
link is a set of two fibers, with one fiber dedicated to
forward transmission and another one for reverse
transmission. An optical connection (lightpath) (m,
n) corresponds to the establishment of an optical
path for transfer information from source m to
destination n on a distinctive wavelength. In the
absence of wavelength converters at the
intermediate optical nodes, each lightpath needs to
be on the same wavelength from source to
destination. All-to-all broadcast communication,
distributing messages from each node to every other
node, is a opaque communication pattern and finds
abundant applications from network control plane to
datacenters[1-3]. In general, all-to-all broadcast is
employed for numerous applications in advanced
distributed computing and communication systems
which employ WDM optical networks comprising
hundreds of optical nodes at the backbone and
involving huge number of operating wavelengths [4-
18]. Wavelength need to be assigned for various
lightpaths in such a way that no two lightpaths are
established using the same wavelength, if they share
any common link along entire route. Wavelengths
being a scarce and costly resource, hence their
utilization must be limited to reduce the complexity
and cost of the network. WDM optical all-to-all
broadcast was extensively analysed by many
researchers but still it contains so many research
challenges. All-to-all broadcast was studied for
numerous optical networks like ring, linear-array,
torus, mesh and tree under all optical routing
models. Preceding research works [19-22] propose
interconnecting the alternate nodes of primary ring
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
135
Volume 21, 2022
network with additional link, and called as modified
/ extended ring topology to establish enormous
traffic requirement with high speed, enlarged call
connection probability and improved survivability.
The link and node failure analysis are studied for the
modified/ extended ring networks topology [23-24].
Also, the wide-sense nonblocking multicast
communication for modified/ extended ring is
studied [25]. In this workr, we examine WDM all
optical all-to-all broadcast in a ring with 3-length
extension network, as it guarantees lower
wavelength necessities and emerge attractive for
optical control plane.
In this article, a study on all-to-all broadcast
communication in a ring with 2-length extension
and ring with 3-length extension network was
performed under all optical routing model. The
wavelength assignment for all-to-all broadcast is
studied for the unidirectional ring with 2-length
extension and unidirectional ring with 3-length
extension network using longest link first routing
algorithm. The wavelength number necessary for
all-to-all broadcast is derived. Section 2 gives the
preliminaries necessary to study the unidirectional
ring with 2 length extension and 3 length extension.
Section 3 provides the wavelength number
necessary to establish all-to-all broadcast in ring
with 2 length extension and 3-length extension
under uni directional communication. Section 4
discusses the results obtained the in the work.
Section 5 concludes the article highlighting future
research avenues.
2 Preliminaries
2.1 Unidirectional Ring with 2-length
Extension
Fig. 1 shows an eight node (0 to 7) ring with 2-
length extension [19-22]. Every node of the ring
network is additionally interconnected to an
alternate node using additional link.
Fig. 1: An eight node Ring with 2 length extension
At each node, data can move from node to node
and node where denotes modulo
addition. This offers alternate paths and it
decrease the number of hops and also to decrease
the wavelength necessities for all-to-all broadcast.
Example 1: Wavelength assignment for all
connections of all-to-all broadcast in an eight-node
unidirectional ring network using longest link first
routing algorithm.
Consider the eight-node ring with 2-length
extension shown in Fig. 1. All-to-all broadcast
connections are listed as shown below,
(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7)
(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,0)
(2,3),(2,4),(2,5),(2,6),(2,7),(2,0),(2,1)
(3,4),(3,5),(3,6),(3,7),(3,0),(3,1),(3,2)
(4,5),(4,6),(4,7),(4,0),(4,1),(4,2),(4,3)
(5,6),(5,7),(5,0),(5,1),(5,2),(5,3),(5,4)
(6,7),(6,0),(6,1),(6,2),(6,3),(6,4),(6,5)
(7,0),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6)
The non-overlapping connections are grouped in the
above set of connections and prevalent wavelength
is allocated as shown below:
Thus, 14 wavelength numbers are necessary atmost
for an eight-node unidirectional ring with 2-length
extension to establish all-to-all broadcast.
2.2 Unidirectional Ring with 3-length
Extension
Fig. 2 shows a 12-node (indexed from 0 to 11) ring
with 3-length extension. A ring network is extended
by additionally connecting two nodes which are
separated by two intermediate nodes with additional
fibers. This network is referred as ring with 3-length
extension. That is, each node is straightly
connected to node and node
where denotes addition modulo. This provides
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
136
Volume 21, 2022
alternate paths so as to aid reduce the effective
number of hops for communicating nodes and also
to reduce the wavelength number necessary for all-
to-all broadcast.
Fig. 2: A 12-node ring with 3-length extension
Example 2: Wavelength allotment for all-to-all
broadcast in a 12-node unidirectional ring with 3-
length extension using longest link first routing
algorithm.
Consider the 12-node ring with 3-length extension
shown in Fig. 2 All-to-all broadcast connections can
be listed as shown below:
The non-overlapping connections are grouped in the
above set of connections and prevalent wavelength
is allocated as shown below:
{(0,1),(1,0),(4,5),(5,4),(8,9),(9,8)} -λ1
{(1,2),(2,1),(5,6),(6,5),(9,10),(10,9)} -λ2
{(2,3),(3,2),(6,7),(7,6),(10,11),(11,10)} -λ3
{(3,4),(4,5),(7,8),(8,7),(11,0),(0,11)} -λ4
{(0,2),(2,0),(4,6),(6,4),(8,10),(10,8)} -λ5
{(1,3),(3,1),(5,7),(7,5),(9,11),(11,9)} -λ6
{(2,4),(4,2),(6,8),(8,6),(10,0),(0,10)} -λ7
{(3,5),(5,3),(7,9),(9,7),(11,1),(1,11)} -λ8
{(0,3),(3,0),(4,7),(7,4),(8,11),(11,8)} -λ9
{(1,4),(4,1),(5,8),(8,5),(9,0),(0,9)} -λ10
{(2,5),(5,2),(6,9),(9,6),(10,1),(1,10)} -λ11
{(3,6),(6,3),(7,10),(10,7),(11,2),(2,11)} -λ12
{(0,4),(4,0),(4,8),(8,4),(8,0),(0,8)} -λ13
{(1,5),(5,1),(5,9),(9,5),(9,1),(1,9)} -λ14
{(2,6),(6,2),(6,10),(10,6),(10,2),(2,10)} -λ15
{(3,7),(7,3),(7,11),(11,7),(11,3),(3,11)} -λ16
{(0,5),(5,0),(4,9),(9,4),(8,1),(1,8)} -λ17
{(1,6),(6,1),(5,10),(10,5),(9,2),(2,9)} -λ18
{(2,7),(7,2),(6,11),(11,6),(10,3),(3,10)} -λ19
{(3,8),(8,3),(7,0),(0,7),(11,4),(4,11)} -λ20
{(0,6),(6,0),(1,7),(7,1),(2,8),(8,2)} -λ21
{(3,9),(9,3),(4,10),(10,4),(5,11),(11,5)} -λ22
Thus, 22 wavelength numbers are necessary atmost
for a 12-node unidirectional ring with 3-length
extension to establish all-to-all broadcast.
The following definitions are necessary to
understand the analysis done in this chapter.
Definition 1: “A link that joins the nodes and
( is said to be shorter link. A link that
directly joins the nodes and and nodes
and ( is said to be longer link” [22].
Definition 2: “A connection is the set of all links
that joins source node and destination node
following a prescribed routing method” [22].
Definition 3: “A connection that selects longer link
over a shorter link at the source node and at various
intermediate nodes to reach the destination node is
said to follow ‘longest link first routing’. For
example, in Figure 1, under longest link first
routing, a connection from source node 2 to
destination node 5 selects first the longer link inter
connecting the node 2 with 4 and then the shorter
link joining node 4 with 5” [22].
Definition 4: “If the number of intermediate nodes
between the source node and destination node in the
primary ring isthen the connection is called a
lengthconnection. For example, in Figure 4.1, if
the source node is indexed 2 and the destination
node is indexed 5, then the length of the connection
is 3” [22].
Lemma 1: Under the longest link first routing
algorithm, for
a length connections
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
137
Volume 21, 2022
initiating from a source node with even index do not
interfere with another same length connection
initiating from a source node with odd index.
Proof: It can be observe that all connections of
length , whereis positive integer use only
longer links inter connecting two even numbered
nodes, if the index of source node is an even number
whereas all connections of same length , use
onlylonger links inter connecting two odd numbered
nodes, if the index of source node is an odd number.
Also, all connections of length , use first
only longer links inter connecting two even
numbered nodes and finally end with a shorter link
inter connecting even numbered node with an odd
numbered node, if the index of source node is an
even number. Whereas, all connections of same
length use first only longer links inter connecting
two odd numbered nodes and finally end with a
shorter link inter connecting odd numbered node
with an even numbered node, if the index of source
node is an odd number. Hence, all the length
connections initiating from source node with even
index do not interfere with all the same length
connections initiating from source node with odd
index because they never share any common link.
Lemma 2: Based on longest link first routing
algorithm, for
and ,
three connections of length and initiating (source)
from any 3 consecutive nodes never interfere with
each other.
Proof: Let be the index of the three
consecutive nodes where A connection of
lengthinitiating from node index first use the
longer links inter connecting the nodes and ,
then nodes with and so on. Similarly,
length connections initiating from node index
first use the longer links inter connecting the
nodes and , then nodes with
, and so on. Also, length connections initiating
from node index, first use the longer links
inter connecting the nodes and , then
nodes with , and so on. Hence, these 3
sets of connections never share any common link
and hence they do not interfere with each other.
Lemma 3: Under longest link first routing
algorithm, for
and
three connections of length and initiating
(source) from any 3 consecutive nodes never
interfere with each other.
Proof: Let be the index of the three
consecutive nodes where A connection of
length initiating from node index a, first use the
longer links inter connecting the nodes and ,
then nodes with and so on and finally
end with one shorter link. Similarly, length
connectionsinitiating from node index first
use the longer links inter connecting the nodes
and , then nodes with , and so
on and finally end with one shorter link. Also,
length connections initiating from node index
first use the longer links inter connecting the
nodes and , then nodes with
, and so on and finally end with one shorter
link. As the longer links involved in the 3 sets of
connections are completely different, the shorter
link immediately following the last longer link in
the 3 sets of connections will also be different (as
the source node of shorter links are not same).
Hence, these 3 sets of connections never share any
common link and hence they do not interfere with
each other.
Lemma 4: Let be a positive integer. Then, two
wavelengths are sufficient to establish all
connections of length in a node ring with 3-
length extension using longest link first routing
algorithm.
Proof: Let be the index of the two nodes
(where ) which are separated by exactly one
intermediate node indexed . A connection of
length , initiating from node index , involve
two consecutive shorter links, first the link inter
connecting the nodes and , then the link
inter connecting the nodes and .
Similarly, connections of length initiating
from node index , involve two consecutive
shorter links, first the link inter connecting the
nodes and , then the link inter
connecting the nodes and Hence,
these 2 sets of connections never share any common
link and hence they do not interfere with each other.
Hence, two wavelengths are sufficient to route all
length 2connections.
Lemma 5: Under longest link first routing
algorithm, for
and ,
connections of same length, and initiating (source)
from any 3 nodes which are separated by exactly
one intermediate node they never interfere with each
other.
Proof: Let be the indices of the three
nodes (where ) which are separated by one
intermediate nodes. A connection of length
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
138
Volume 21, 2022
initiating from node index first use the longer links
inter connecting the nodes and , then nodes
with , and so on and finally end with
two consecutive shorter links. Similarly, length
connections initiating from node index, first
use the longer links inter connecting the nodes
and, then nodes with, and so
on and finally end with two consecutive shorter
links. Similarly, length connections initiating from
node index, first use the longer links inter
connecting the nodes and, then nodes
with, and so on and finally end with
two consecutive shorter links. As the longer links
involved in the 3 sets of connections are different,
the two consecutive shorter links immediately
following the longer links in the 3 sets of
connections would also be different (as the indices
of the source node of the first shorter link in the 3
set of connections differ exactly by 2). Hence, these
3 sets of connections do not share any common link
and hence they do not interfere with each other.
3 Main Results
In this section, first we derive the wavelength
number necessary to establish all connections of all-
to-all broadcast and then the link load of the ring
network with 2-length extension and ring network
with 2-length extension. The connections are routed
based on the longest link first routing technique.
The results of Theorems proved below are based on
the principle on grouping non overlapping
connections on a common wavelength.
3.1 Unidirectional Ring with 2-length
Extension
Theorem 1: Let be an odd integer and .
Then, the wavelength number necessary for
establishing all-to-all broadcast in a node
unidirectional ring with 2-length extension is at
most
using longest link first routing algorithm.
Proof: Define a group as
for every integer i and j such that
and
.
It can be observe that connections in do not
overlap. Hence, we assign a distinctive wavelength
to all connections in a single. By this way, the
wavelength number necessary to assign for all
connections is equal to the number of groups
which is equal to
(1)
The remaining connections can be grouped as
for
It can be observe that connections in do not
overlap. Hence, we assign a distinctive wavelength
to all connections in a single. Hence, the total
wavelength number necessary to assign for all
connections is equal to the number of groups,
which is equal to
. (2)
Since the groups and defined above
contains all the connections, by adding (1) & (2) we
get
wavelength number necessary to establish
all-to-all broadcast communication.
Theorem 2: Let where is a positive
integer and . Then, the wavelength number
necessary to establish all-to-all broadcast in a
unidirectional node ring with 2-length extension
is at most
using longest link first routing
algorithm.
Proof: Define a group as
for every integer i and j such that
and
.
It can be observe that connections in do not
overlap. Hence, we assign a distinctive wavelength
to all connections in a single. By this way, the
wavelength number necessary to assign for all
connections is equal to the number of group
which is equal to
. (3)
The remaining connections can be grouped as
for
It can be observe that connections in do not
overlap. Hence, we assign a distinctive wavelength
to all connections in a single. Hence, the total
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
139
Volume 21, 2022
wavelength number necessary to assign for all
connections is equal to the number of groups,
which is equal to
. (4)
Since the groups and defined above
contains all the connections, by adding (3) & (4) we
get
wavelength number necessary to
establish all-to-all broadcast communication.
Theorem 3: Let where is a positive
integer and . Then, the wavelength number
necessary to establish all-to-all broadcast in a
unidirectional node ring with 2-length extension
is at most
using longest link first routing
algorithm.
Proof: Define a group as
for every integer i and j such that
and
.
It can be observe that connections in do not
overlap. Hence, we assign a distinctive wavelength
to all connections in a single. By this way, the
wavelength number necessary to assign for all
connections is equal to the number of groups
which is equal to
(5)
The remaining connections can be grouped as
for
and
for
It can be observe that connections in do not
overlap. Hence, we assign a distinctive wavelength
to all connections in a single. Hence, the total
wavelength number necessary to assign for all
connections is equal to the number of groups,
which is equal to
. (6)
Since the groups and defined above
contains all the connections, by adding (5) & (6) we
get
wavelength number necessary to
establish all-to-all broadcast communication.
Now, let us derive the link load of the network of a
network with N even. Consider a random longer
link inter connecting the nodes and. It can
be observe that for
nodes at a distance
of length, before node share the above
link to transmit the message to number of
nodes immediately after node . Then the total
number of connections that share the above link is
which is equal to
Consider anarbitrary shorter link inter
connecting the nodes and. It can be observe
that for
nodes at a distance of
length, before node share the above link to
transmit the message to Hence, the number
of connections that share the above link is
Next, we derive the link load of the network with N
odd. Consider a random longer link inter connecting
the nodes andIt can be observe that for
nodes at a distance of length, before
node share the above link to transmit the
message to number of nodes immediately
after node. Then the total number of connections
that share the above link is
=
which is equal to
. Consider
anarbitrary shorter link inter connecting the nodes
and. It can be observe that for
nodes at a distance of length, before node
share the above link to transmit the message to
Hence, the number of connections that share the
above link is
It can be noted that for a every N
value, the link load of all longer links are same.
Similarly, the link load of all shorter links are also
same. Hence, the wavelength number derived in
Theorems 1 through 3 is the optimum wavelength
number using longest link first routing algorithm.
3.2 Unidirectional Ring with 3- length
Extension
Theorem 1: Let , where is a positive
integer. Then, the wavelength number necessary
atmost to establish all-to-all broadcast in a node
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
140
Volume 21, 2022
unidirectional ring with 3-length extension is
using longest link first routing algorithm.
Proof: Let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections
in,and do not overlap. Hence,
a distinctive wavelength is allotted to all
connections in a single, and
. By this way, the wavelength number
necessary atmost to assign for all connections is
equal to the number of groups of
and which is equal to
The remaining connections can be grouped as
for
It can be observe that connections in do not
overlap. Hence, a distinctive wavelength is allotted
for all connections in a single. Hence, the total
wavelength number necessary to assign for all
connections is equal to the number of groups,
which is equal to
Since the groups,,,
and defined above contains all the connections.
Adding (7) & (8), the wavelength number necessary
atmost to establish all-to-all broadcast is obtained
as
.
Theorem 2: Let , where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing algorithm.
Proof: Let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted for all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
groups and which is
equal to
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
141
Volume 21, 2022
The remaining connections can be grouped as
for
It can be observe that connections in do not
overlap. Hence, a distinctive wavelength is allotted
for all connections in a singleHence, the
wavelength number necessary to assign for all
connections is equal to the number of groups,
which is equal to
Since the groups,,,
and defined above contains all the
connections. Adding (9) & (10), the wavelength
number necessary atmost to establish all-to-all
broadcast is obtained as
.
Theorem 3: Let , where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing algorithm.
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
groups and which is
equal to
The remaining connections can be grouped as
for
for
It can be observe that connections in do not
overlap. Hence, a distinctive wavelength is allotted
to all connections in a single. Hence, the total
wavelength number necessary to assign for all
connections is equal to the number of groups,
which is equal to
Since the groups ,,,
and defined above contains all the
connections. Adding (11) & (12), the wavelength
number necessary atmost to establish all-to-all
broadcast is obtained as
.
Theorem 4: Let , where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
142
Volume 21, 2022
is
using longest link first routing
algorithm.
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
groups and which is
equal to
Since the groups,, and
defined above contains all the connections. From
(13), the wavelength number necessary atmost to
establish all-to-all broadcast is obtained as
.
Theorem 5: Let , where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing algorithm.
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
groups and which is
equal to
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
143
Volume 21, 2022
The remaining connections can be grouped as
for
for
It can be observe that connections in do not
overlap and connections in also do not
overlap. Hence, a distinctive wavelength is allotted
for all connections in a single
and.Hence, the total wavelength number
necessary to assign for all connections is equal to
the number of groups and, which is
equal to
Since the groups,,,
and defined above contains all
the connections. Adding (14) & (15), the
wavelength number necessary atmost to establish
all-to-all broadcast is obtained as
.
Theorem 6: Let where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing
algorithm.
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
groups and which
is equal to
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
144
Volume 21, 2022
Since the groups, , and
defined above contains all the connections. From
(16), the wavelength number necessary atmost to
establish all-to-all broadcast is obtained as
.
Theorem 7: Let , where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing
algorithm.
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
groups and which is
equal to
The remaining connections can be grouped as
for
It can be observe that connections in do not
overlap. Hence, a distinctive wavelength is allotted
to all connections in a single. Hence, the total
wavelength number necessary to assign for all
connections is equal to the number of groups,
which is equal to
Since the groups,,,
and defined above contains all the connections.
Adding (17) & (18), the wavelength number
necessary atmost to establish all-to-all broadcast is
obtained as
.
Theorem 8: Let where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing
algorithm.
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
145
Volume 21, 2022
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single,and . By this
way, the wavelength number necessary to assign for
all connections is equal to the number of
groups and which is
equal to
Since the groups, , and
defined above contains all the connections. From
(19), the wavelength number necessary atmost to
establish all-to-all broadcast is obtained as
.
Theorem 9: Let , where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing algorithm.
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
146
Volume 21, 2022
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
groups and which is
equal to
The remaining connections can be grouped as
for
for
It can be observe that connections in do not
overlap. Hence, a distinctive wavelength is allotted
to all connections in a single. Hence, the total
wavelength number necessary to assign for all
connections is equal to the number of groups,
which is equal to
Since the groups,, ,
and defined above contains all the connections.
Adding (20) & (21), the wavelength number
necessary atmost to establish all-to-all broadcast is
obtained as
.
Theorem 10: Let , where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing
algorithm.
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
groups and which is
equal to
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
147
Volume 21, 2022
Since the groups, , and
defined above contains all the connections. From
(22), the wavelength number necessary atmost to
establish all-to-all broadcast is obtained as
.
Theorem 11: Let where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing algorithm.
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
groups and which is
equal to
The remaining connections can be grouped as
for
for
for
It can be observe that connections in do not
overlap and connections in also do not
overlap. Hence, a distinctive wavelength is allotted
to all connections in a single and.
Hence, the wavelength number necessary to assign
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
148
Volume 21, 2022
for all connections is equal to the number of
groups and, which is equal to
Since the
groups,,,and
defined above contains all the connections.
Adding (23) & (24), the wavelength number
necessary atmost to establish all-to-all broadcast is
obtained as
.
Theorem 12: Let , where is a
positive integer. Then, the wavelength number
necessary atmost to establish all-to-all broadcast in
a node unidirectional ring with 3-length extension
is
using longest link first routing algorithm.
Proof: Let
for every integer and such that
and
Also, let
for every integer and such that
and
It can be observe that connections in do not
overlap. Similarly, the connections in ,
and do not overlap. Hence, a
distinctive wavelength is allotted to all connections
in a single, and . By
this way, the wavelength number necessary to
assign for all connections is equal to the number of
and which is equal
to
)
Since the groups, and
defined above contains all the connections. From
(25), the wavelength number necessary atmost to
establish all-to-all broadcast is obtained as
.
Link Load
Now, the link load of the ring with 3-length
extension for all-to-all broadcast is derived. Let
denote link load of ring with -length extension,
which is the maximum number of paths that share a
common link.
Case i)
Consider a random longer link inter connecting the
nodes and. It can be observe that for
nodes at a distance of length, before
node share the above link to transmit the
message to number of nodes immediately
after node. Then the total number of connections
that share the above link is
Consider a random shorter link inter connecting the
nodes and. It can be observe that for
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
149
Volume 21, 2022
nodes which are present at a distance of
length share the above link to
transmit the message to and node.
Similarly, nodes which are present at a distance of
length share the above
link to transmit the message to node. Hence,
the number of connections that share the above link
is 2*
The link load of longer link is higher than that of
shorter link, so the link load of a longer link is the
link load of the network. From the equitation (26) &
(27), the link load of the network
.
Case ii)
Consider a random longer link inter connecting the
nodes and. It can be observe that for
nodes at a distance of length, before
node share the above link to transmit the
message to number of nodes immediately
after node. Then the total number of connections
that share the above link is
Consider a random shorter link inter connecting the
nodes and. It can be observe that for
nodes which are present at a distance of
length share the above link to
transmit the message to and node.
Similarly, nodes which are present at a distance of
length share the above
link to transmit the message to node. Hence,
the number of connections that share the above link
is 2*
The link load of longer link is higher than that of
shorter link, so the link load of a longer link is the
link load of the network. From the equitation (28) &
(29), the link load of the network
.
Case iii)
Consider a random longer link inter connecting the
nodes and. It can be observe that for
nodes at a distance of length, before
node share the above link to transmit the
message to number of nodes immediately
after node. Then the total number of connections
that share the above link is
Consider a random shorter link inter connecting the
nodes and. It can be observe that for
nodes which are present at a distance of
length share the above link to
transmit the message to and node.
Also, node share the
above link to transmit the message to
Similarly nodes which are present at a distance of
length share the above
link to transmit the message to node.
Hence, the number of connections that share the
above link is
The link load of longer link is higher than that of
shorter link, so the link load of a longer link is the
link load of the network. From the equitation (30) &
(31), the link load of the network
. It is
to be observed that for a particular value of N, the
link load of all longer links is same. Similarly, the
link load of all shorter links is also same.
4 Results and Discussion
4.1 Unidirectional Ring with 2-length
Extension
Table 1 compares the results obtained in the
previous section with that of a unidirectional
primary ring. It can be easily observed that the
wavelength number necessary atmost to establish
all-to-all broadcast in a ring with 2-length extension
is reduced by a minimum of 46% and a maximum of
50% than that necessary for a primary ring. Table 2
shows the values of wavelength number necessary
atmost to establish all-to-all broadcast along with
link load for certain values of node number. It can
be observed that the difference between the
wavelength number necessary and link load is very
small, which indicates that the derived results are
either equal or nearer to the minimum wavelength
number.
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
150
Volume 21, 2022
Table 1. Wavelength number necessary atmost to
establish all-to-all broadcast in a unidirectional ring
and unidirectional ring with 2-length extension.
Network Topology
with N node
Wavelength number
required atmost to establish
all-to-all broadcast
Unidirectional ring
[5]
Unidirectional ring
with 2-length
extension
Table 2. Wavelength number required atmost to
establish all-to-all broadcast along with link load for
certain values of node numberin a unidirectional
ring with 2-length extension.
Table 3. Comparison of wavelength number
required atmost to establish all-to-all broadcast for
certain values of node number in a unidirectional
ring, unidirectional ring with 2-length extension.
Node number
N
Wavelength number required atmost to
establish all-to-all broadcast
Unidirectional
ring (Sabrigiriraj
et al. 2009)
Unidirectional
ring with 2-length
extension
12
66
33
13
78
42
14
91
46
15
105
56
16
120
60
17
136
72
18
153
77
19
171
90
20
190
95
21
210
110
22
231
116
23
253
132
24
276
138
27
351
182
30
435
218
33
528
272
36
630
315
39
741
380
42
861
431
45
990
506
48
1128
564
51
1275
650
60
1770
885
70
2415
1208
80
3160
1580
90
4005
2003
100
4950
2475
125
7750
3906
150
11175
5588
175
15225
7656
200
19900
9950
300
44850
22425
500
124750
62375
700
244650
122325
1000
499500
249750
From Table 3, it can be observed that the
wavelength number necessary atmost to establish
all-to-all broadcast in a unidirectional ring with 2-
length extension is reduced by a minimum of 46%
and a maximum of 50% than that necessary for a
unidirectional primary ring network.
4.2 Unidirectional Ring with 3-length
Extension
Table 4 compares wavelength number necessary
atmost to establish all-to-all broadcast in a
unidirectional ring with 3-length extension,
unidirectional ring with 2 length extension and
unidirectional primary ring.
Table 4 Wavelength number required atmost to
establish all-to-all broadcast in a unidirectional ring,
Node
number
N
Wavelen
gth
number
required
Link
load
Difference
between
wavelength
number and
link load
25
156
144
12
30
218
210
8
40
390
380
10
55
756
729
27
70
1208
1190
18
85
1806
1764
42
90
2003
1980
23
100
2475
2450
25
120
3570
3540
30
150
5588
5550
38
175
7656
7569
87
225
12656
12544
112
350
30538
30450
88
500
62375
62250
125
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
151
Volume 21, 2022
unidirectional ring with 2-length extension and
unidirectional ring with 3-length extension.
Network
Topology with
N node
Wavelength number required
atmost to establish all-to-all
broadcast
Unidirectional
ring [5]
Unidirectional
ring with 2-
length
extension
Unidirectional
ring with 3-
length
extension
Unidirectional
ring with 3-
length
extension
Table 5. Wavelength number required atmost to
establish all-to-all broadcast along with link load for
certain values of node numberin a unidirectional
ring with 3-length extension.
Node
number N
Wavelen
gth
number
required
Link
load
Difference
between
wavelength
number required
and link load
25
108
92
16
30
173
135
38
40
274
247
27
55
540
477
63
70
828
782
46
85
1218
1162
56
90
1423
1305
118
100
1684
1617
67
120
2380
2340
40
150
3873
3675
198
175
5220
5017
203
225
8512
8325
187
350
20591
20242
349
500
41916
41417
499
Table 5 shows the values of wavelength number
necessary atmost to establish all-to-all broadcast
along with link load for certain values of. It can
be observed that the difference between the
wavelength number necessary and link load and is
little, which indicates that the derived results are
either equal or nearer to the minimum wavelength
number.
Table 6. Comparison of wavelength number
required atmost to establish all-to-all broadcast for
certain value of node number N in a unidirectional
ring, unidirectional ring with 2-length extension and
unidirectional ring with 3-length extension.
Node
number
N
Comparison of wavelength number required
atmost to establish all-to-all broadcast
Unidirectio
nal ring [5]
Unidirectiona
l ring with 2-
length
extension
Unidirectional
ring with 3-
length
extension
12
66
33
22
13
78
42
30
14
91
46
39
15
105
56
42
16
120
60
46
17
136
72
56
18
153
77
67
19
171
90
72
20
190
95
76
21
210
110
80
22
231
116
84
23
253
132
88
24
276
138
92
27
351
182
130
30
435
218
173
33
528
272
192
36
630
315
210
39
741
380
266
42
861
431
327
45
990
506
352
48
1128
564
376
51
1275
650
450
60
1770
885
590
70
2415
1208
828
80
3160
1580
1106
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
152
Volume 21, 2022
Node
number
N
Comparison of wavelength number required
atmost to establish all-to-all broadcast
Unidirectio
nal ring [5]
Unidirectiona
l ring with 2-
length
extension
Unidirectional
ring with 3-
length
extension
90
4005
2003
1423
100
4950
2475
1684
125
7750
3906
2666
150
11175
5588
3873
175
15225
7656
5220
200
19900
9950
6766
300
44850
22425
14950
500
124750
62375
41916
700
244650
122325
81784
1000
499500
249750
166834
From Table 6, it can be easily observed that the
wavelength number necessary atmost to establish
all-to-all broadcast in a ring with 3-length extension
is reduced by a minimum of 56% and a maximum of
66% when compared to primary ring. Similarly, the
wavelength number necessary atmost to establish
all-to-all broadcast in a unidirectional ring with 3-
length extension is reduced by a minimum of 13%
and a maximum of 33% when compared to
unidirectional ring with 2-length extension.
5 Conclusion and Future Work
In this article, all-to-all broadcast is studied for
unidirectional ring with 2 length extension and
unidirectional ring with 3 length extension. The
wavelength number necessary atmost to establish
all-to-all broadcast in a unidirectional ring with 2-
length extension and 3-length extension is derived.
The proof of various Theorems clearly displays the
method of wavelength allotment. The result
obtained shows that the wavelength number
necessary atmost to establish all-to-all broadcast in a
unidirectional ring with 2-length extension is
reduced by a minimum of 46% and a maximum of
50% than that necessary for a unidirectional primary
ring network. Also, the result obtained shows that
the wavelength number necessary atmost to
establish all-to-all broadcast in a unidirectional ring
with 3-length extension is reduced by a minimum of
56% and a maximum of 66% when compared to
primary ring. Similarly, the wavelength number
necessary atmost to establish all-to-all broadcast in a
unidirectional ring with 3-length extension is
reduced by a minimum of 13% and a maximum of
33% when compared to unidirectional ring with 2-
length extension.
Wavelength number requirement needs to be
investigated with still higher order extensions, to
judge the rate of reduction in wavelength number
requirements with increasing extension and is a
challenging issue. Also, deriving a generalized
expression for wavelength number requirement in a
linear array/ring network with k-length extension (k
is any positive integer and k < N where N is the total
number of nodes in the network) is another
interesting and challenging future work. Examining
the effects of physical layer impairments and
network survivability on routing and wavelength
assignment are other research issues with these
extended networks.
References:
[1] Y. Cheng, R.Lin, M. De Andrade, L.
Wosinska, and J. Chen, “Disaggregated Data
Centers: Challenges and Tradeoffs”, IEEE
Communications Magazine, 2019.
[2] T. Alexoudi, C. Mitsolidou, S. Pitris, J.H. Han,
A.F. Beldachi, N. Manihatty-Bojan, Y. Ou, E.
Hugues-Salas, R. Broeke, R. Nejabati, and D.
Simeonidou, “WDM routing for edge data
centers and disaggregated computing”,
In Photonic Networks and Devices, Optical
Society of America, 2018.
[3] K. Kontodimas, K. Christodoulopoulos, E.
Zahavi, and E., Varvarigos, “Resource
allocation in slotted optical data center
networks”, International Conference on Optical
Network Design and Modeling, pp. 248-253,
2018.
[4] M. Sabrigiriraj, M. Meenakshi and R.
Roopkumar, “Wavelength assignment in WDM
linear array”, IET Electronics letters, Vol. 43,
No.20, pp.1111-1113, 2007.
[5] M.Sabrigiriraj, M.Meenakshi and
R.Roopkumar, “Wavelength assignment for all-
to-all broadcast in wavelength division
multiplexing optical ring”, IETE Journal of
Research, Vol. 55, No.5, pp.236-241, 2009.
[6] M. Sabrigiriraj, M. Meenakshiand R.
Roopkumar, “An efficient wavelength
assignment for all-to-all broadcast in optical
WDM hypercube network”, Journal of Optics,
Vol. 35, No. 4, pp. 188-196, 2006.
[7] R. Abbas, N. Al-Aboody, andH. Al-
Raweshidy, “Required in m-arity tree
networks”, Electronics Letters, Vol. 50, No. 24,
pp. 1855-1857, 2014.
[8] M. Sabrigiriraj, and K. Manoharan,
“Wavelength allotment for all-to-all broadcast
in WDM optical modified linear array for
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
153
Volume 21, 2022
reliable communication”, Journal of Mobile
Networks and Applications, pp. 1-7, 2017.
[9] M. Sabrigiriraj, & K. Manoharan,
“Wavelength allocation for all-to-all broadcast
in bidirectional optical WDM modified ring”,
Journal of Optik, Vol. 179, pp.545-556, 2019
[10] M. Sabrigiriraj, M. Meenakshi, and R.
Roopkumar, “Wavelength assignment for all-
to-all broadcast in WDM optical linear array
with limited drops”, Computer
Communications, Vol. 33, No. 15, pp. 1804-
1808, 2010.
[11] M.Sabrigiriraj and M.Meenakshi, “All-to-all
broadcast in optical WDM networks under
light-tree model”, Computer Communications,
Vol.31, No. 10, pp.2562-2565, 2008.
[12] M. Sabrigiriraj, M. Meenakshi and R.
Roopkumar, “Wavelength assignment for all-
to-all broadcast in WDM optical ring with
limited drops”, Journal of Optics, Vol.38,
pp.103-123, 2009.
[13] M. Sabrigiriraj and M. Balaji “Wavelength
assignment for all-to-all broadcast in bi-
directional WDM optical Ring with limited
drops”, Optik, Vol.125, No. 23, pp. 6930-6941,
2014.
[14] M.Sabrigiriraj “Wavelength assignment for all-
to-all broadcast in WRMD WDM Linear array
and Ring”, Optik, Vol.125, pp.2213–2216,
2014.
[15] S. Pascu, “Optical control plane: Theory and
Algorithms”, Louisiana State University and
Agricultural and Mechanical college, Doctor of
Philosophy Thesis, 2006.
[16] Z.Wang, K.Liu, L. Li,W.Chen, M.Chen and
L.Zhang, “A novel approach for all-to-all
routing in all-optical hypersquare torus
network”, Proceedings of CF’16 (ACM), Italy,
2016.
[17] W. Liang, andX. Shen, “A general approach for
all-to-all routing in multihop WDM optical
networks”, IEEE/ACM Transactions on
Networking (TON), Vol. 14, No 4, pp.914-923,
2006.
[18] V.S.Shekhawat, D.K.Tyagi and V.K.Chaubey,
“Design and characterization of a modified
WDM ring network – An analytical approach”,
Optik, Vol.123, pp.1103-1107, 2012.
[19] S.Sen, R.Vikas, V.K.Chaubey, “Designing and
simulation of a modified WDM ring network
with improved grade of service”, Optical Fiber
Technology, Vol. 11, pp. 266-277, 2005.
[20] A. Meulenberg, and T. C. Wan, ‘LEO-Ring-
Based Communications Network’, Physics
Procedia, Vol. 20, pp.232-241, 2011.
[21] A.S. Arora, S. Subramaniam, and H.A. Choi,
‘Logical topology design for linear and ring
optical networks’, IEEE Journal on Selected
Areas in Communications, Vol. 20(1), pp.62-
74, 2002.
[22] M. Sabrigiriraj, and R. Karthik, "Wide-sense
nonblocking multicast in optical WDM
networks", Cluster Computing,pp.1-6, 2017.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
WSEAS TRANSACTIONS on COMMUNICATIONS
DOI: 10.37394/23204.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2864
154
Volume 21, 2022
