Abstract—All-to-all broadcast communication, distributing messages from each node to every other node, is a dense
communication pattern and finds numerous applications in advanced computing and communication networks from the control
plane to datacenters. A ring network topology is one of the important regular network topologies due to its simple structure, high
speed, easy to extend and tolerant to link and node failures. Few researchers recommended connecting the alternate nodes of the
ring with additional fibers in the ring network, to support increased call connection probability, higher tolerable to multiple link
and node failures, enormous traffic handling capability and improved survivability. To reduce the complicatedness and cost of
the network, it is essential to reduce the wavelength-number required to establish all-to-all broadcast in wavelength-division
multiplexed ring network. In this paper, 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 ring with 3-length extension. The wavelength allotment
methods are proposed for realizing all-to-all broadcast over a WDM optical bi-directional ring with 3-length extension under
multiple unicast routing model using a two-stage heuristic algorithm. The heuristic algorithm is developed to identify non-
overlapping connections and an explicit wavelength allotment method based on the output of the heuristic technique is given.
The result obtained shows that wavelength-number required atmost to establish all-to-all broadcast in a bi-directional ring with
3-length extension is reduced by a minimum of 57% and a maximum of 66% when compared to bi-directional primary ring.
Similarly, the wavelength-number required atmost to establish all-to-all broadcast in a bi-directional ring with 3-length extension
is reduced by a minimum of 20% and a maximum of 33% when compared to a bi-directional ring with 2-length extension.
Keywords—All-to-All Broadcast, Modified Ring, Wavelength Assignment, WDM Optical Network.
Received: July 28, 2021. Revised: March 22, 2022. Accepted: April 17, 2022. Published: May 9, 2022.
1. Introduction
PTICAL Wavelength Division Multiplexing (WDM)
technologies have the potential to provide the tremendous
bandwidth demand for emerging high performance
computing applications. A WDM optical network employs
numerous optical nodes and these 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 of a packet from source m to
destination n on a unique 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, 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, its usage need to be restricted to reduce
the complexity and cost of the network. Optical WDM all-to-
all broadcast communication was extensively analysed by
many researchers but still it contains so many research
challenges. All-to-all broadcast was studied for numerous
topologies like ring, linear array, torus, mesh and tree under all
optical routing models. Preceding research works [19-22]
proposes interconnecting the alternate nodes of primary ring
with additional link, and termed as modified-ring / extended-
ring topology to support enormous bandwidth requirement,
enlarged call connection probability and improved stability.
The link and node failure analysis are studied for the
modified/ extended ring networks topology [23-24]. Also, the
wide-sense non-blocking multicast communication for
modified/ extended ring is studied [25]. In this work, we
Wavelength Allotment for All-to-All Broadcast in WDM Optical
bidirectional ring with 3-length extension
K. MANOHARAN1, M. SABRIGIRIRAJ2,
1Department of ECE, SNS College of Technology, Coimbatore, 641 035, Tamilnadu, INDIA
2Department of ECE, SVS College of Engineering, Coimbatore, 642 109, Tamilnadu, INDIA
O
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
139
Volume 21, 2022
examine all-to-all broadcast in a ring with 3-length extension
network, as it provides lower wavelength usage and eye-
catching for optical control plane.
Section 2 gives an overview of the basics required to
understand the investigation done in this paper. Wavelength-
number required atmost to establish all-to-all broadcast and its
associated link load is obtained in section 3 using proposed
heuristic algorithm. Finally, section 4 completes the paper
highlighting future research avenues.
2. Preliminaries
If Fig.1 illustrate a 12-node (node 0 to node11) ring with
3-length extension. A primary ring network topology is
extended by additionally linking two nodes which are
separated by two intermediate nodes with additional fibers.
This network is referred as ring with 3-length extension. In
this network each node is linked straight to node in
addition to node where stand for addition with
modulo. It offers additional paths so as to aid decrease the
effectual number of hops and also to decrease the wavelength-
number required to establish all-to-all broadcast
commendation.
The following definitions are necessary to prove the main
results.
Definition 1: A shorter link is one that links the nodes with
. A longer link is one that directly links the nodes
with (.
Definition 2: “A connection is the set of all links that joins
source node and destination node following a prescribed
routing method” [22].
Fig. 1. A 12-node ring with 3-length extension
Definition 3: “A connection that selects longest link over a
shortest link at the source node and at various intermediate
nodes to reach the destination node is said to follow ‘longest
link first routing” [22]. For example in Fig. 1, using longest
link first routing algorithm, a connection from node 2 to 6
selects first available longest link interconnecting the node 2
with node 5 and then the shortest link interconnecting node 5
with node 6.
Definition 4: “If the number of intermediate nodes between
the source node and destination node in the primary ring is
then the connection is called a length connection. For
example, in Fig. 1, if the source node is indexed 2 and the
destination node is indexed 5, then the length of the
connection is 3”[22].
Definition 5: “Two or more connections are said to be non-
overlapping with each other, if they do not share any link
along their path”[22].
Lemma 1: In longest link first routing, for
and
, three length connections starting (source)
from any 3 consecutive nodes do not interfere with each other.
Proof: Let be the index of the three
consecutive nodes whereA length connection starting
from node index first use the longer links joining the nodes
and , then nodes with and so on.
Similarly, length connections starting from node index
first use the longer links joining the nodes and ,
then nodes with and so on. Also, length
connections starting from node index, first use the
longer links joining the nodes and , then nodes
with , and so on. Hence, these 3 sets of
connections do not share any common link and hence they do
not interfere with each other.
Lemma 2: Under longest link first routing, for
and three length connections starting
(source) from any 3 consecutive nodes do not interfere with
each other.
Proof: Let be the index of the three
consecutive nodes where A length connection starting
from node index a, first use the longer links joining the nodes
and , then nodes with and so on and
finally end with one shorter link. Similarly, length
connections starting from node index first use the
longer links joining the nodes and , then nodes
with , and so on and finally end with one shorter
link. Also, length connections starting from node index
first use the longer links joining 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
do not share any common link and hence they do not interfere
with each other.
Lemma 3: Let be a positive integer. Then, two wavelengths
are sufficient to establish all connections of length in
anode ring with 3-length extension using longest link first
routing.
Proof: Let be the index of the two nodes (where
) which are separated by exactly one intermediate node
indexed . A length 2 connection starting from node
index, involve two consecutive shorter links, first the link
interconnecting the nodes and , then the link
interconnecting the nodes and . Similarly,
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
140
Volume 21, 2022
connections of length 2 originating from node index ,
involve two consecutive shorter links, first the link joining the
nodes and , then the link joining the nodes
and Hence, these 2 sets of connections do not share any
common link and hence they do not interfere with each other.
Hence, two wavelengths are sufficient to route all connections
of length 2.
Lemma 4: Under longest link first routing, for
and, connections of same length, and
originating (source) from any 3 nodes which are separated by
exactly one intermediate node do not 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 originating from node index first
use the longer links joining the nodes and , then nodes
with , and so on and finally end with two
consecutive shorter links. Similarly, connections of length
originating from node index, first use the longer links
joining the nodes and, then nodes
with, and so on and finally end with two consecutive
shorter links. Similarly, connections of length originating
from node index, first use the longer links joining 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.
Illustration 1: Wavelength allotment for all-to-all broadcast
in a 12-node bi-directional ring with 3-length extension under
shortest path/longest link first routing.
Consider the 12-node ring with 3-length extension shown in
Fig. 1. The shortest connections in clockwise direction are
considered and listed below, the reasons for this are provided
in next section.
For the connection length for all-to-all broadcast
communications are staring from length 1 to length 6. The
various connections of all-to-all broadcast communication are
grouped as given below:
Group 1: {6,4,1}, Group 2: {3}, Group 3:{2}, Group 4: {5}
The non-overlapping connections in each group can be
combined after each group’s values are stored in ascending
order and a unique wavelength is allocated as shown below:
}
}
Thus, nine wavelengths are required atmost to establish all-
to-all broadcast communication of a 12-node ring with 3-
length extension
3. Two stage Heuristic algorithm and
wavelength allotments
A ring network topology with 3-length extension
comprising of N nodes labeled from 0 to N-1 is taken as the
source of this investigation. All-to-all broadcast
communication is grouped into two clusters of connections
with one cluster aggregating all possible connections
established in clockwise direction while the other cluster
aggregating all possible connections established in
anticlockwise direction. All connections are assumed to be
routed in the shortest path and by adopting longest link first
routing technique. However, clockwise direction is preferred,
if the path length of a connection is same in both clockwise
and anticlockwise direction. Since each optical link is assumed
to be a fiber pair, with each fiber taking care of connections in
one particular direction, set of wavelengths employed for
connections routed through clockwise direction may also be
employed for connections routed through anticlockwise
direction. Hence, connections established in clockwise
direction are only taken for investigation in this paper.
a. Heuristic algorithm
The identification of non-overlapping connections is the key
and is done using a heuristic technique. This technique is
executed in two stages namely stage 1 and stage 2. The first
stage of the algorithm is presented in Fig. 2. The total number
of nodes in the ring N, is inputted to the stage 1 algorithm.
Using the value of N, the algorithm generates the lengths of
various connections of all-to-all broadcast. Obviously, the
length of various connections exists from 1 to till
. Next,
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
141
Volume 21, 2022
these length values are partitioned into two groups. One group
comprises of length values, which output a reminder of 2,
when it is divided by 3 (List A). Further, the elements namely
2 and 5 are then separated from this group, as wavelength
allotment for connections corresponding to it are dealt
separately. The other group comprises of length values, which
output a reminder not equal to 2, when it is divided by 3 (List
B). The stage 1 algorithm then groups the elements of List A
and List B separately into multiple disjoint sets (no two sets
contain a same element) in such a way that the sum of the
elements of each set, excluding the last set, is equal to N. The
reason for making the sum of elements of each set equal to N
is for an efficient wavelength allotment. This ensures that non-
overlapping connections of length equal to each of the value
of the elements in the set (one connection for every length
equal to the value of the elements in the set), when routed
sequentially one after another on a unique wavelength (the
destination of one connection being the source for another
connection), covers a maximum number of available longest
links over a single round along the ring. This strategy ensures
that a particular wavelength is used on maximum number of
longest links for a single round over a ring and may pertain to
optimal wavelength allotment. However, as the sum of the
elements in the last set may not be equal to N, adopting the
above logic may not pertain to optimal wavelength allotment.
If adopted as such, the allotted wavelength may not be present
in an entire round over the ring, which paves the way for more
wavelength requirement. The pseudocode for stage 1
algorithm is displayed in Fig.3. Further, wavelength allotment
for connection lengths equal to the element values of the last
set is deliberated in the heuristic algorithm stage 2.
The second stage of the heuristic algorithm is displayed in
Fig.4. This algorithm first inputs all the elements of last set
obtained through List A of stage 1 algorithm. This algorithm
processes the inputs and outputs either the same input set or
outputs the input elements in two or more disjoint set. The
algorithm first generates a power set with the input elements.
Power set is all possible subsets for the given set of input
elements. Then the subset-sum, which is the sum of all the
element in a subset, is calculated for all the generated subsets
but excluding null set which is omitted as it of no relevance
for the analysis. For every subset, N is made to divide the
subset-sum and the quotient obtained is recorded. The
fractional element of the quotient is zero when, N is integer
multiples on subset-sum. This ensures that non-overlapping
connections of length equal to each of the values of the
elements in the subset (one connection for every length equal
to the value of the elements in the subset and the destination of
one connection being the source for another connection), when
routed sequentially one after another and then repeated z times
where z is the corresponding quotient value, on a unique
wavelength covers a maximum number of available longest
links over a single round along the ring. This strategy ensures
that a particular wavelength is used on maximum number of
longest links for a single round over a ring and may pertain to
optimal wavelength allotment.
A value of non-zero in the fractional part of the quotient
corresponds to the scenario where N is a not an integer
multiple of subset-sum. In this scenario, non-overlapping
connections of length equal to each of the values of the
elements in the subset (one connection for every length equal
to the value of the elements in the subset and the destination of
one connection being the source for another connection), when
routed sequentially one after another and then repeated z times
where z is the corresponding quotient value, on a unique
wavelength do not cover a maximum number of available
longest links over a single round along the ring. The fractional
part of a quotient which has bigger value results in a situation
where the number of longest links getting assigned a unique
wavelength (so as to result in one full round around the ring)
is less. The fractional part of a quotient which has lower value
results in a situation where the number of longest links getting
assigned a unique wavelength (so as to result in one full round
around the ring) is more. However, irrespective of whether the
fractional part is lower or bigger, the connections routed on a
unique wavelength, as said above, do not make one full round.
Hence, among all the subsets generated through power set, the
subset which produced lowest fractional part in its quotient
value is outputted. In the case of more than one subset
producing the same value of fractional part in its quotient, the
subset comprising of more element count is outputted. In the
scenario of having same values in both fractional part and
element count, the subset which was processed first is
outputted.
Once a subset is outputted based on the value of the fractional
part of the quotient, then a decision has to be made regarding
how to employ the elements of the subset towards wavelength
allotment. One option is about employing the elements of the
subset together for wavelength allotment while the other is
passing each and every element of the selected subset
separately for wavelength allotment. Remaining options are
not considered here to reduce the complexity of this study.
This choice to be made is made based on the wavelength-
number requirement and the one which require less is selected.
The logic for wavelength requirement calculation is, suppose
the length of a connection is, and then the maximum
number oflength connections that can be established
without overlapping with each other on the N node ring with
3-length extension is
. For establishing connections of
length , the total wavelength required is
.
Letbe the elements of a subset and if they are
assumed to be independently employed for wavelength
allotment, then the total wavelength-number required is
. On the contrary, if the
elements of a subset are assumed to be employed together for
wavelength allotment, then the wavelength-number required
are
.
Based on the wavelength-number either the elements of the
input are outputted as separate sets or together as one output
set same as input. This set of elements is removed from the
original input list of stage 2 algorithm. Again stage 2
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
142
Volume 21, 2022
algorithm is executed with the remaining inputs, if the input
list A is not empty. Similarly, the same procedure is repeated
again for the last group elements obtained from list B at the
end of execution of stage 1 algorithm. The pseudocode of
stage 2 algorithm is displayed in Fig. 5. The sets outputted
from stage 1 and stage 2 of the heuristic algorithm is used to
complete wavelength allocation by mapping with appropriate
wavelength allotment methods described in the succeeding
section. It is required that the elements of each set need to be
arranged in non-decreasing order. The following additional
points need to be noted here for wavelength allotment: For
mod 3all connections of length and originating
(source) from any 3 consecutive nodes do not interfere with
each other (Lemma 1). Also, for mod 3, all
connections of length from nodes and (if
such nodes exist) do not interfere with each other (Lemma 4).
b. Wavelength allotment methods
Note: Let
Category 1: Let be the elements of a list such
that
Case i)
For let
Then for
let
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case ii)
For let
Then for
let
and
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case iii)
For let
Then for
let
and
.
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Category 2: Let be the solo element of a list such that
where is a positive integer.
Case i )
For
let
Then for
let
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case ii)
For
let
Then for
,
let also
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case iii)
For
let
Then for
let
and
.
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Category 3: Let be the elements of an array
such that where is a positive
integer.
Case i)
For
let
Then for
-1
let
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
143
Volume 21, 2022
be assigned for them. As a result, the wavelength-number
required is
Case ii)
For
let
Then for
let and
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case iii)
For
let
Then for
let and
. As the connections available in
every are non-overlapping with each other, an exclusive
wavelength needs to be assigned for them. As a result, the
wavelength-number required is
Category 4: Let be the elements of a list such
that
Wavelength allotment is identical to Category 1.
Category 5: Let be the solo element of a list such that
where ,are positive integers and
Let
The remaining connections are grouped as each arrangement
no two connections are non-overlapping as per the following
procedure. All the connections available in the series
except
those incorporated inare taken one by one as a matrix of
rows first in column wise and then row wise. Here, all
connections available in a same row do not overlap with each
other. . Hence, an exclusive wavelength required to be
assigned for them. So, wavelength-numbers are
required to route all such connections.
Category 6: Let be the elements of an array
such that
where , are positive
integers and
For, let
Let
The remaining connections are grouped as each arrangement
no two connections are noverlapping as per the following
procedure. All the groups in the sequence
except those included in
are written one by one as a matrix of rows first in
column wise and then row wise. Here, all the connections
present in a same row do not overlap with each other and they
can be on the same wavelength. So, wavelengths are
required to route all connections of length.
Category 7: Let be the elements of a list such
that
Case i)
For let
Then for
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case ii)
For let
Then for
Also,
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case iii)
For let
Then for
Also,
and
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
144
Volume 21, 2022
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case iv)
For let
Then for
Also,
and
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case v)
For let
Then for
Also,
and
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case vi)
For let
Then for
Also,
and
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Category 8: Let be the single element of a list such
that where is a positive integer.
Case i)
For
let G
Then for
let
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case ii)
For
let
Then for
Also
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case iii)
For
let
Then for
Also,
,
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case iv)
For
let
Then for
Also,
,
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case v)
For
let
Then for
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
145
Volume 21, 2022
Also,
,
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case vi)
For
let
Then for
Also
,
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Category 9: Let be the elements of an array
such that where z is a positive
integer.
Case i)
For
let
Then for
let
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case ii)
For
let
Then for
Also
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case iii)
For
let
Then for
Also
,
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case iv)
For
let
Then for
Also
,
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case v)
For
let
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
146
Volume 21, 2022
Then for
Also,
,
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Case vi)
For
let
Then for
Also,
,
As the connections available in every are non-
overlapping with each other, an exclusive wavelength needs to
be assigned for them. As a result, the wavelength-number
required is
Category 10: Let be the elements of a list such
that
Wavelength allotment is same as that given for Category 7.
Category 11: Let be the single element of a list such that
where ,are positive integers and
Let
The remaining connections are grouped as each group no two
connections are non-overlapping as per the following
procedure. All the connections in the series
excluding those available inare taken one by one as a
matrix of
1
l
rows first in column wise and then row wise. It
may be prominent that all connections present in a same row
do not overlap with each other. Hence, a unique wavelength
required to be allotted for them. So, wavelengths are
required to route all such connections.
Category 12: Let be the elements of an array
such that
where z, are positive
integers and
For, let
Let
The remaining groups can be combined as each arrangement
no two connections are noverlapping as per the following
procedure.
All the groups in the series
except those included in are taken one by one as a matrix
of rows first in column wise and then row wise. The
connections of all group present in a same row do not overlap
with each other and they can be on the same wavelength. So,
wavelengths are required to route all connections of
length.
Illustration 2: Wavelength allotment for all-to-all broadcast in
a 28 node WDM optical ring with 3-length extension:
For, . The output of stage 1 and stage 2 heuristic
algorithms are given below:
The connections of the output groups are sorted in ascending
order as shown below,before applying wavelength allotment,
The following output is obtained when are
passed for wavelength allotment:
For Group (By Category 1)
λ1
For Group (By Category 4)
λ11
λ12
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
147
Volume 21, 2022
λ19
λ20
For Group (By Category 2)
37711111515191923
2327273
For Group (By Category 5)
For Group: (By Category 11)
λ25
λ26
λ33
λ34
For Group (By Category 11)
λ35
λ3
6
λ37
λ38
For length 2: (Lemma 3)
For length 5: (Lemma 4)
C. Link load
Let indicate the network link load which is the maximum
number of paths that share a common link. The link load of a
bi-directional ring with 3-length extension is derived as shown
below:
Case i) , where m denotes a positive number.
We can arbitrarily choose one longest link that links the nodes
and. For
nodes available at a
lengthprevious to node in the anti clockwise route,
utilize this longest link to share its information to
instant nodes after the node. Therefore, connections that
utilize this longest link =
We can arbitrarily select any shortest link that links the nodes
and. For
, nodes available at a
lengthprevious to node in the anti clockwise route, utilize
this shortest link to share its information to node and
node (. Similarly nodes available at a length
previous to node in the anti clockwise route, utilize this
shortest link to share its information to node .
Therefore, connections that utilize this shortest link =
. The link load of longest link is higher than that of shortest
link, so the link load of a longest link is the link load of the
network. Therefore, the link load of the network
.
Case ii) , where m denotes a positive number.
We can arbitrarily choose one longest link that links the nodes
and. For
nodes available at a
lengthprevious to node in the anti clockwise route,
utilize this longest link to share its information to
instant nodes after the node. Therefore, connections that
utilize this longest link =
We can arbitrarily select any shortest link that links the nodes
and. For
, nodes available at a
lengthprevious to node in the anti clockwise route, utilize
this shortest link to share its information to node and
node (. Similarly nodes available at a length
previous to node in the anti clockwise route, utilize this
shortest link to share its information to node (.
Therefore, connections that utilize this shortest link =
. The link load of
longest link is higher than that of shortest link, so the link load
of a longest link is the link load of the network. Therefore, the
link load of the network
.
Case iii) , where m denotes a positive number.
We can arbitrarily choose one longest link that links the nodes
and. For
nodes available at a
lengthprevious to node in the anti clockwise route,
utilize this longest link to share its information to
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
148
Volume 21, 2022
instant nodes after the node . Therefore, connections that
utilize this longest link =
We can arbitrarily select any shortest link that links the nodes
and. For
, nodes available at a
lengthprevious to node in the anti clockwise route, utilize
this shortest link to share its information to node and
node (. Similarly For
nodes available
at a lengthprevious to node in the anti clockwise
route, utilize this shortest link to share its information to node
Therefore, connections that utilize this shortest link
=
The link load of longest link is higher than that of shortest
link, so the link load of a longest link is the link load of the
network. Therefore, the link load of the network
.
Case iv) , where m denotes a positive number.
We can arbitrarily choose one longest link that links the nodes
and. For
nodes available at a
lengthprevious to nodein the anti clockwise route,
utilize this longest link to share its information to
instant nodes after the node . Therefore, connections that
utilize this longest link =
We can arbitrarily select any shortest link that links the nodes
and. For
, nodes available at a
lengthprevious to node in the anti clockwise route, utilize
this shortest link to share its information to node ( and
node. Similarly For
nodes available
at a lengthprevious to node in the anti clockwise
route, utilize this shortest link to share its information to node
Therefore, connections that utilize this shortest link
=
The link load of longest link is higher than that of shortest
link, so the link load of a longest link is the link load of the
network. Therefore, the link load of the network
.
Case v) , where m denotes a positive number.
We can arbitrarily choose one longest link that links the nodes
and. For
nodes available at a
lengthprevious to node in the anti clockwise route,
utilize this longest link to share its information to
instant nodes after the node . Therefore, connections that
utilize this longest link =
We can arbitrarily select any shortest link that links the nodes
and. For
, nodes available at a
lengthprevious to node in the anti clockwise route utilize
this shortest link to share its information to node and
node (. Similarly nodes available at a length
previous to node in the anti clockwise route, utilize this
shortest link to share its information to node.
Therefore, connections that utilize this shortest link =
The link load of longest link is higher than that of shortest
link, so the link load of a longest link is the link load of the
network. Therefore, the link load of the network
.
Case vi) , where m denotes a positive number.
We can arbitrarily choose one longest link that links the nodes
and. For
nodes available at a
lengthprevious to node in the anti clockwise
route, utilize this longest link to share its information to
instant nodes after the node . Therefore, connections that
utilize this longest link =
We can arbitrarily select any shortest link that links the nodes
and. For
, nodes available at a
lengthprevious to node in the anti clockwise route, utilize
this shortest link to share its information to node and
node (.
Similarly, nodes available at a lengthprevious to node
in the anti clockwise route, utilize this shortest link to share
its information to node Therefore, connections that
utilize this shortest link =
The link load of longest link is higher than that of shortest
link, so the link load of a longest link is the link load of the
network. Therefore, the link load of the network
.
It may be noted that for a every value of, the link load of all
longest links and shortest links are same. Hence, the
wavelength-number required atmost to establish all-to-all
broadcast must be greater than or equal to the link load. The
outcome of the Table 1 provides the difference between the
wavelength-number required and the link load is less, which
proves that the results are either optimal or near optimal. From
Table 2, it can be observed that the wavelength-number
required 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 required atmost to establish all-to-all
broadcast in a bi-directional ring with 3-length extension is
reduced by a minimum of 13% and a maximum of 33% when
compared to bi-directional ring with 2-length extension.
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
149
Volume 21, 2022
Table 1 Wavelength-number required atmost to establish all-
to-all broadcast along with link load for certain values of node
number N in a bi-directional ring with 3-length extension.
Node
number N
Wavelength-
number
required
Link
load
Difference between
wavelength-number
and link load
25
33
22
11
28
42
30
12
30
48
35
13
40
79
63
16
55
138
117
21
60
164
145
19
70
224
198
26
85
317
287
30
90
355
330
25
100
442
408
34
201
1694
1650
44
500
10483
10375
108
Table 2 Comparison of wavelength-number required atmost to
establish all-to-all broadcast for certain value of node number
Nin a bi-directional ring, bi-directional ring with 2-length
extension and bi-directional ring with 3-length extension.
Node
number
N
Wavelength-number of required atmost to
establish all-to-all broadcast
Bi-
directional
ring [4]
Bi-directional
ring with 2-
length
extension [22]
Bi-directional
ring with 3-
length
extension
25
78
41
33
28
98
53
42
30
113
60
48
40
200
105
79
55
378
189
138
60
450
233
164
70
613
315
224
85
903
449
317
90
1013
518
355
100
1250
638
442
201
5050
2500
1694
500
31250
15688
10483
4. Conclusion
A two stage heuristic algorithm is proposed to identify non-
overlapping connections among the various connections of all-
to-all broadcast in a bi-directional ring with 3-length
extension. Explicit wavelength allotment methods are also
provided for the same. The result obtained shows that the
wavelength-number required is nearly equal to the link load of
the network and so the results are either optimal or near
optimal. Also, the wavelength-number required atmost to
establish all-to-all broadcast in a bi-directional ring with 3-
length extension is reduced by a minimum of 57% and a
maximum of 66% when compared to bi-directional primary
ring. Similarly, the wavelength-number required atmost to
establish all-to-all broadcast for a bi-directional ring with 3-
length extension is reduced by a minimum of 20% and a
maximum of 33% when compared to a bi-directional ring with
2-length extension. This reduction in wavelength-number is at
the expense of directly linking two nodes which are separated
by two intermediate nodes with additional fibers.
Future works incorporate the examining the similar problem
in other network topologies with 2 length and 3 length
extension. Wavelength-number requirement needs to be
investigated with still higher order extensions, to judge the
rate of reduction in wavelength-number requirements. Also,
deriving a generalized expression for wavelength-number
requirement in a 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 an interesting and challenging future
work. The impact of physical layer impairments for these
networks needs to be studied. Another issue that requires
attention is studying wavelengths requirement under multiple
link and node failures in this network.
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] Sabrigiriraj, M, Meenakshi, M &Roopkumar, R 2009a,
'Wavelength assignment for all-to-all broadcast in
wavelength division multiplexing optical ring', IETE
Journal of Research, vol. 55, no. 5, pp. 236-241.
[5] Z.Wang, K.Liu, L.Li.,W.Chen, M.Chen and L.Zhang, “A
novel approach for all-to-all routing in all-optical hyper
square torus network”, Proceedings of CF’16 (ACM),
Italy, 2016.
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
150
Volume 21, 2022
[6] M.Sabrigiriraj “Wavelength assignment for all-to-all
broadcast in WRMD WDM Linear array and Ring”,
Optik, Vol.125, pp.2213–2216, 2014.
[7] 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, pp. 1804-1808, 2009.
[8] M.Sabrigiriraj and M.Meenakshi, “All-to-all broadcast in
optical WDM networks under light-tree model”,
Computer Communications, Vol.31, pp.2562-2565, 2008.
[9] W. Liang and X. Shen, “A general approach for all-to-all
routing in multihop WDM optical networks”, IEEE/ACM
Trans. on Networking, Vol. 14, pp. 914-923, 2006.
[10] Run-Kai Shiu, Meng-Hsin Fang, Peng-Chun Peng,
Yibeltal Chanie Manie, Wei-Chieh Tang and Chung-
Hong Lai, “Hybrid transmission of unicast and broadcast
signals without optical filter for WDM systems”, Optical
Fiber Technology, Vol. 47, pp. 172-177, 2019.
[11] M. Waqar Ashraf, Sevia M.Idrusa, R. Aslamb and Farabi
Iqbala, “Capacity-bounded lightpath routing in WDM
optical networks”, Optical Fiber Technology,Vol. 48, pp.
50-57, 2019.
[12] Y.L. Liu, and J.M. Chang, “Realizing exchanged crossed
cube communication patterns on linear array wdm optical
networks”, International Journal of Foundations of
Computer Science, Vol. 29, No. 06, pp.1003-1021, 2018.
[13] H. H. Chou, T.D. Wilkinson, N. Collings, W.A.
Crossland, and H.T. Chou, “Implementation of
coarse wavelength division multiplexing multi-
wavelength routing switch core for storage area
networks”, IET Optoelectronics, Vol. 4, no. 2, pp. 64 –
77,2010.
[14] Y. Liu, “Routing and wavelength assignment for
exchanged hypercubes in linear array optical networks”,
Information Processing Letters, Vol. 115, pp.203-208,
2015.
[15] Y.Chen and H.Shen, “Routing and wavelength
assignment for hypercube in array-based WDM optical
networks”, Journal of Parallel and Distributed
Computing”, Vol. 70, pp. 59-68, 2010.
[16] C.Yu, X.Yang, J.Zhang and L.He, “Routing and
wavelength assignment for 3-ary n-cube communication
patterns in linear array optical networks for n
communication rounds”, Information Processing Letters,
Vol. 113, pp.677-680, 2013.
[17] C.Shuiying and Z.Yiwen, “Routing and wavelength
assignment for locally twisted cube in linear array optical
network”, Journal of Fuzhou University, Vol.2, 2016.
[18] Pawel Wiatr, Jiajia Chen, Paolo Monti, Lena Wosinska
and Di Yuan, “Routing and wavelength assignment vs.
EDFA reliability performance in optical backbone
networks: An operational cost perspective”, Optical
Switching and Networking, Vol. 31, pp. 211-217, 2019.
[19] 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.
[20] 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.
[21] M. Sabrigiriraj, & K. Manoharan, “Wavelength Allotment
for All-to-All Broadcast in WDM Optical Modified
Linear Array for Reliable Communication”, Journal of
Mobile Networks and Applications, Vol. 24, no. 2, pp
350–356, 2019.
[22] 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
[23] A. Meulenberg, and T. C. Wan, ‘LEO-Ring-Based
Communications Network’, Physics Procedia, Vol. 20,
pp.232-241, 2011.
[24] 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.
[25] M. Sabrigiriraj, and R. Karthik, "Wide-sense nonblocking
multicast in optical WDM networks", Cluster
Computing,pp.1-6, 2017.
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
151
Volume 21, 2022
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
NO
YES
NO
YES
Fig. 2 Flowchart of the stage 1 algorithm for ring with 3-length extension (cont..)
START
Read node number ‘N’
Create two subsets A and B. Subset A contains the elements of S (except 2 and 5), which
divided by 3 gives a remainder value 2. Subset B contains the elements of S, which divided
by 3 gives a remainder not equal to 2.
Further A = { } and A ={S }
CNT1 = No of elements in A and CNT2 = No of elements in B
Unmark all elements of A
Create an empty group, C=0
Copy the first unmarked element of A to
Mark the corresponding element in A, C = C+1
NT1-1.
Read the next unmarked element in A.
SUM1 = Sum of all the elements of with currently read unmarked
element. C = C+1
If (SUM1< =N)
Mark the currently read unmarked element in
A. Copy it in
Compute S =
B
C
A
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
152
Volume 21, 2022
NO
YES
NO
YES
NO
YES
YES
NO
Fig. 2 Flowchart of the stage 1 algorithm for ring with 3-length extension (cont..)
F
If (SUM1==N)
If (C < CNT1)
If (All element of
A marked)
i = i + 1
B
Unmark all elements of B
Create an empty group, F = 0
Copy the first unmarked element of B to
Mark the corresponding element in B, F = F+1
NT1-1.
D
Read the next unmarked element in B.
SUM2 = Sum of all the elements of with currently read unmarked
element. F = F+1
If (SUM2< =N)
Mark the currently read unmarked element in B.
Copy it in
E
A
C
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
153
Volume 21, 2022
YES
YES
YES
NO
NO
NO
YES
Fig. 2 Flowchart of the stage 1 algorithm for ring with 3-length extension
- Total No. of nodes available in the network.
are integer variables.
An array containing length of connections as elements (inputs).
An array containing length of connections as elements (inputs).
An array containing elements as flags for elements of array .
An array containing elements as flags for elements of array .
An array with row as the list number and column as the element index (outputs).
An array with row as the list number and column as the element index (outputs).
Step 1: While ()
Else
End
If (SUM2 == N)
If (F < CNT2)
If (All element of
B marked)
j = j + 1
E
D
STOP
F
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
154
Volume 21, 2022
Step 2: End While.
Step 3: Initialize
Step 4: Assign
Step 5: While
,
Go to Step 4.
End if.
End
Step 6:End while.
Step 7:,go to Step 8.
Else , go to Step 4.
Step 8: Initialize
Step 9: Assign
Step 10:While(
.
Go to Step 4.
End if.
End if.
Step 11:End while.
Step 12:If ,the algorithm is terminated.
Else , go to Step 9.
Fig. 3 Pseudo code of the stage 1 algorithm for ring with 3-length extension
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
155
Volume 21, 2022
NO
NO
YES
YES
NO
YES
Fig. 4 Flowchart of stage 2 algorithm for ring with 3-length extension (cont..)
Input the last group elements of of stage 1 Algorithm
Generate power set using all elements of input
list
For each subset, divide Nby its subset-sum and determine the quotient
Select a subset whose quotient has lowest value in fractional part. If 2 or more
subset has same value in fractional part, select the subset which has more
number of elements count. If number of elements count is also same, then
select a subset which occurs initialin the power set
If (x > y)
If(Input list empty)
If (Element count of
input)
Determine the total wavelength requirement (x), if connections of length equal to values of
each of the elements in the subset are routed separately
x=
Store all the elements of subset as a
new group. Delete the subset
elements from input list
Store each subset elements in
separate group; Delete the subset
elements from input list
Store the input
element as a new
group
Determine the total wavelength requirement (y), if connections of length equal to values
of each element in the subset are joined and routed together
START
Compute subset sum for each subsets. Neglect null set
A
A
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
156
Volume 21, 2022
Total No. of nodes available in the network.
An array containing the last group elements of G[ ][ ]obtained in stage 1 of the algorithm (sorted in
descending order)
An array containing the elements of last group of H[ ][ ]obtained in stage 1 of the algorithm (sorted
in descending order)
An array U (outputs).
An array V (outputs).
An array BUF.
Step 1: Power set of / T[ ]is generated and sorted in descending order based on the number of elements
and subset_sum. For each and every subset of N is divided by its subset sum. Let be
the fractional part of the result. For each subset, If
Number of elements of the corresponding subset, Corresponding Subset whose quotient
has lowest value in fractional part. (If two or more subset has same value in fractional part, select
the subset which has more number of elements count)
Step 2: If
remove elements of from and store it in
, go to Step 4.
Step 3: Repeat
Until Then, the elements of [ ] are deleted from / T[ ].
Step 4: If / T[ ] is not empty, , go to Step 1. Else, the algorithm
is terminated.
Fig. 5 Pseudo code of stage 2 algorithm for ring with 3-length extension
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.19
K. Manoharan, M. Sabrigiriraj
E-ISSN: 2224-2872
157
Volume 21, 2022
