# Energy Efficient Routing and Network Coding in Core Networks

Mohamed Musa  Taisir Elgorashi  Jaafar Elmirghani

###### Abstract

We propose network coding as an energy efficient data transmission technique
in core networks with non-bypass and bypass routing approaches. The
improvement in energy efficiency is achieved through reduction in the traffic
flows passing through intermediate nodes. A mixed integer linear program
(MILP) is developed to optimize the use of network resources, and the results
show that our proposed network coding approach introduces up to 33% power
savings for the non-bypass case compared with the conventional architectures.
For the bypass case, 28% power savings are obtained considering futuristic
network components’ power consumption. A heuristic based on the minimum hop
count routing shows power savings comparable to the MILP results. Furthermore,
we study how the change in network topology affects the savings produced by
network coding. The results show that the savings are proportional to the
average hop count of the network topology. We also derive power consumption
analytic bounds and closed form expressions for networks that implement
network coding and thus also verify the results obtained by the MILP model.

###### Index Terms:

Core network; IP/WDM; Mixed Integer Linear Program; Network coding; Energy
Efficiency;

##  I Introduction

The exponential growth in the use of ICT has intensified the interest in
energy efficiency approaches. The current ICT systems are not energy
efficient, and the inefficiency gap is continuously expanding. This inherent
engineering problem is steering attention towards new designs with energy
efficiency objectives in mind. Economic factors, especially after the increase
in energy prices, have increased the pressure to push the efficiency to its
limits. These factors alongside the ecological factors will probably be one of
the important bottlenecks to ICT expansion. The total emissions of ICT are
estimated in The GeSI SMARTer 2030 report [1] to constitute 1.97% of all
emissions by the year 2030.
Greening the Internet was first introduced in 2003 [2] as a concept. The
authors of [3] provide a survey of energy efficiency improvement approaches
used in optical networks. Previously, our work has addressed the core network
energy efficiency with renewable energy sources [4], core networks with
communication between data centers [5] and data centres with dis-aggregated
servers [6], design and optimization of physical topology [7], the efficient
distribution of clouds [8], future energy efficient high definition TV [9],
Peer to Peer content distribution [10, 11], big data management [12, 13, 14],
energy efficient embedding of virtual network [15], network function
virtualization [16] and the improvement in energy efficiency resulting from
multiple combined methods in the GreenTouch GreenMeter [17, 18].
In 2000, Ahlswede et. al proposed the idea of network coding in wireless
networks for multicast connections [19], achieving a throughput improvement by
using all network nodes, which participate in the coding process as opposed to
the conventional routing approach. This throughput improvement means a
possible opportunity for energy efficiency improvement. In [20] a good review
of the applications of network coding is provided. However, most of the work
on network coding focused on wireless networks. The most notable work in
optical networks is in passive optical networks [21, 22, 23] or protection for
mesh optical networks [24, 25, 26, 27] and our previous work [28, 29]. These
applications of network coding rely on the multicast advantage of the PON and
the multipath requirement of the protection mechanism. The rest of the efforts
addressed the impact of using multicast enabled optical switches for network
coding [30, 31] as well as the requirement to do network coding in the
physical layer [32]. The authors in [33] and [34] proposed approaches to
reduce the network coding resource in the network, and in [35] the authors
proposed approaches that allow fairly general coding across flows.
In this paper we expand on our previous work in [36, 37] and present a
detailed investigation of a new energy efficient routing and network coding
mechanism in unicast settings where opposite flows passing through
intermediate nodes get encoded using a simple xor operation before being sent
back to their destination. This calls for simple hardware changes at the IP
layer only.
Although the idea we present is similar in principle to the work of [38] in
wireless networks, our work is different because a wired implementation of
network coding is very different from its wireless counterpart. This is
because the benefit in the wireless case is due to the shared broadcast domain
between nodes, whereas the benefit in the wired case is less clear since wired
switched networks have a smaller collision domain between neighbours and
support full duplex communication, and therefore need to be explored and
understood. We use a MILP model followed by a heuristic to determine the
performance of our new network coding approach, and similar to our approach in
[28, 29], we provide analytic bounds and closed form expressions to validate
the MILP model and the heuristic. We consider different approaches for
implementing network coding to address the possibility of packet size
mismatch, and also our work makes a sensible quantified estimate of the
benefit that could be achieved in practice.
Section II of this paper introduces network coding and proposes a novel node
architecture to support network coding in non-bypass IP over WDM networks. In
Section III the new approach is modelled using mixed integer linear
programming (MILP), with the analysis of results presented in Section IV. In
Section V we compare two approaches of network coding with partitioning and
with zero padding of flows, and we investigate implementing network coding in
bypass IP over WDM networks in Section VI. Section VII presents power
consumption analytic bounds and closed form expressions of the conventional
and the network coding scenarios. Finally, Section VIII concludes the paper.

##  II Concept description

Network coding is commonly illustrated by the well-known butterfly network
shown in Fig. 1 (a). Here the sources $k$ and $n$ want to multicast two units
of information, $X$ and $Y$, to two receivers, $d2$ and $d1$, respectively.
Assuming all links have a unit capacity in the direction shown in the Figure,
tracing the flows will lead to a bottleneck in link $(m,u)$. Instead of
doubling the link capacity to resolve this bottleneck, the link capacity can
be shared by the two flows by encoding the flows by an XOR operation in node
$m$ and multicasting the encoded flow to $d1$ and $d2$ from node $u$.

nmk$Y$$X$$X\oplus Y$$X\oplus Y$nmkd1ud2$Y$$X$$X\oplus Y$$X\oplus Y$$X\oplus
Y$$Y$$X$(a)(b) Figure 1: The butterfly network (a) and the three nodes network
(b)

Fig. 1 (b) shows a special case of the butterfly network where each of the
nodes pairs $(n,d1)$, $(m,u)$ and $(k,d2)$ are considered as a single node,
where the links connecting them are regarded as storage rather than
communication links, this converts the butterfly network to a 3 node network
$n,m$ and $k$. This special butterfly can perform network coding in a unicast
scenario. Suppose node $k$ wants to transmit the information units $X$ to node
$n$, and node $n$ wants to transmit $Y$ to node $k$. Both flows will go
through the intermediate node $m$, which can combine the flows using the XOR
gate and multicast back the encoded flow to both end nodes. Each node
retrieves the information unit intended to it by XOR coding the received unit
with the stored information unit. In the middle node where coding is
performed, we encounter resource savings.
The new approach is described in Fig. 2. At end nodes where flows originate or
terminate, the same ports as the conventional routing approach will be used.
At intermediate nodes, however, two conventional ports are replaced by a
single port that implements the coding functionality. In this paper, the term
conventional port (architecture) is used to mean the current implementation,
and the NC port (architecture) for the network coding enabled IP port. The
coding functionality used here is the mere modulo-2 addition (XOR). For the
three nodes example shown in Fig. 2 ,four conventional ports are reduced to a
single NC port and two conventional ports. The amount of power savings depends
on the ratio of the power consumed by the two types of ports and the
assignment of flows to their routes.

ABCABCConventional PortNC port(b)(a) Figure 2: Conventional architecture (a),
and Network coding architecture (b)

The IP over WDM network is the current core networks implementation; traffic
collected from edge routers is passed to core IP routers, and the optical
layer provides transport over the high bandwidth optical fibres. Transponders
convert the electric signal into optical and optical cross connects provide
the optical layer switching. In each fiber, multiple wavelengths are used
through wavelength division multiplexing with the aid of
multiplexers/demultiplexers. Erbium doped fiber amplifiers (EDFAs) provide
optical signal amplification to support transmission over long distances. The
existence of the IP and the WDM layers presents two approaches to route the
traffic. The first is referred to as the non-bypass approach which routes
traffic from its originating IP router to its destination IP router passing
through each IP router in intermediate nodes. The second approach bypasses
intermediate IP routers and is hence referred to as the bypass approach.
Our proposed architecture of the network coding enabled IP over WDM node is
illustrated in Fig. 3. The new NC enabled port uses two receivers to receive
the two flows that will be encoded and transmitted using the single
transmitter. A coupler is used to multicast the flow from the single
transmitter to the two neighbouring nodes. Storage is needed to perform the
synchronization task prior to encoding. Note that, even if we perform the
synchronization in the IP layer, different data flows may not arrive at the
intermediate node at the same time. Therefore, storage is essential here. The
XOR unit is used to encode the flows. An amplifier is used for splitting power
loss compensation and to support long distance optical transmission. Note that
an alternative architecture that uses an optical implementation of the XOR
gate is a straightforward extension of Fig. 3. The storage unit in source
nodes and destination nodes are used to store the original data and the XOR is
used to decode the received encoded flow. The cost of the additional storage
is mitigated by performing the coding in the IP layer and therefore storage
and the xor functionality can be included as part of the available processing
power.

TxRxTxRxRxRxTxStorageStorageStoragexorxorxorsplitternode (n)intermediate node
(m)node(k)$x$$y$$x+y$$x+y$xy Figure 3: Network coding node architecture

Network coding can be performed at all intermediate nodes of bidirectional
flows. Fig. 4 illustrates how the network coding is performed in a
bidirectional flow traversing two intermediate hops. We consider an example
where node $n1$ needs to send packets $1$, $2$ and $3$ to node $n4$ and node
$n4$ needs to send packets $A$, $B$, and $C$ to node $n1$. The packets being
sent, received or processed by a node are shown above the node.

t=1t=2t=3t=4t=5t=6n1n2n3n4n1n2n3n4n1n2n3n4n1n2n3n4n1n2n3n4n1n2n3n4123323ABC1ABCC2A1B3B+1A+2CA+2AB+11A+2+C3+B+13+B+1BA+2+C2A+2+CC3+B+13
Figure 4: Network coding at two intermediate nodes

  * •

At $t=1$, packets ($1$) and ($A$) are being prepared for transmission by
($n1$) and ($n4$), respectively.

  * •

At $t=2$, packets ($1$) and ($A$) arrive at their neighbouring intermediate
nodes, meanwhile packets ($2$) and ($B$) are being prepared by nodes ($n1$)
and ($n4$), respectively. As intermediate nodes ($n2$) and ($n3$) receive only
a single packet from one side no coding takes place and the packets are
forwarded to the next node.

  * •

At $t=3$, packets ($1$) and ($B$) arrive at node ($n3$) and packets ($A$) and
($2$) arrive at node ($n2$). Nodes ($n2$) and ($n3$) encode their packets and
produce ($2+A$) and ($1+B$) respectively. The encoded packets are multicast to
the two neighbouring nodes (e.g. for node ($n2$) it goes to nodes ($n1$) and
($n3$)).

  * •

At $t=4$, end node ($n1$) receives packet ($A+2$) and decodes it using the
stored packet ($2$). The same applies to node ($n4$) decoding packet ($B+1$)
with the stored packet ($B$). Meanwhile, intermediate nodes ($n2$) and ($n3$)
receive packets ($B+1$) and ($A+2$). First they decode them using the stored
packets ($1$) and ($A$), to produce packets ($B$) and ($2$), ($n2$) then
encodes ($B$) with ($3$) to produce ($B+3$), and ($n3$) encodes ($C$) with
($2$) to produce ($C+2$), which both are multicast to their two intended
neighbours.

  * •

At the remaining time slots, end nodes decode their received coded packets
using their stored packets in a straightforward manner.

We assume that packets are fully synchronized at reception (buffering can be
used to help the synchronisation process). Nodes decide which packets are
encoded in a given packet from a metadata, which is carried in the header and
negligible in size compared to packet sizes. Another possibility is to do
coding on established paths in a circuit switched network, where paths are
decided, and hence encoding possibilities, will be decided beforehand. We also
assume the control and management overhead is negligible since it can be
performed as a result of a software upgrade to the system.

##  III The MILP model

This section describes the MILP model developed whose objective is to minimize
the total power consumption of a non-bypass IP over WDM network with the
aforementioned network coding implementation by optimizing the routes each
demand takes, and optimizing the number and location of conventional and NC
ports, for a given network topology and demands matrix. Below are lists of
sets, parameters and variables defined in the MILP model:

TABLE I: The sets of the MILP model and their description Set |  description
---|---
$\mathcal{N}$ |  Set of network nodes
$\mathcal{N}_{m}$ |  Set of neighbouring nodes connected to node $m$
TABLE II: Model parameters and their description Parameter |  Parameter’s description
---|---
$\lambda^{sd}$ |  The traffic volume of the demand $(s,d)$ in multiples of wavelengths
$L^{mn}$ |  The length of the physical link $(m,n)$
$B$ |  The wavelength capacity in Gbps
$W$ |  wavelengths count in each fibre
${s,d}$ |  A tuple denoting the demand source and destination.
${m,n}$ |  Denotes end nodes of a given physical link
$p_{p}$ |  Conventional router port power consumption
$p_{x}$ |  Network coding based router port power consumption.
$p_{t}$ |  Transponder power consumption.
$p_{e}$ |  EDFA power consumption.
$p_{o}$ |  Optical switch power consumption.
$p_{md}$ |  Multiplexer/demultiplexer power consumption.
$S$ |  Distance required between two neighbouring EDFAs
TABLE III: Model variables and their description Variable |  Variable description
---|---
$P_{T}$ |  The total power consumption of the whole network (W)
$w^{sd}_{m,n}$ |  The traffic flow between source and destination node pair $(s,d)$ that traverses the optical link $(m,n)$, in Gbps
$b^{sd}_{m,n}$ |  Binary equivalent of $w^{sd}_{m,n}$, $b^{sd}_{m,n}=1$ if $w^{sd}_{m,n}>0$, $b^{sd}_{m,n}=0$ otherwise
$c^{sd}_{nmk}$ |  $c^{sd}_{nmk}=1$ if demand $(s,d)$ traverses links $(n,m)$ and $(m,k)$ (i.e. bidirectional traffic flows can be encoded in node $m$)
$Y_{m}$ |  Number of conventional ports at node $m$
$X_{m}$ |  Number of NC ports at node $m$
$X^{m}_{nk}$ |  Number of NC ports at node $m$ catering for the traffic encoding between the node pair $(n,k)$
$A_{mn}$ |  The total number of EDFAs on a physical link $(m,n)$. This is calculated using $A_{mn}=\lfloor L_{mn}/S-1\rfloor$. $S$ is the separating distance between neighbouring amplifiers.
$f_{mn}$ |  The total number of fibres used on physical link $(m,n)$
$w_{mn}$ |  The total traffic flow carried on physical link $(m,n)$
$w^{m}_{nk}$ |  The total traffic flow between node pair $(n,k)$ that goes through the intermediate node $m$
$Npo_{mn}$ |  The number of conventional router ports where the traffic starts at source node $m$ and terminates in a node $n$
$Npi_{mn}$ |  The number of conventional router ports where the traffic terminates at destination node $n$ and starts in a node $m$
$Np_{mn}$ |  The number of conventional router ports at node $m$ interfacing node $n$

The model is defined as follows:
Objective: minimize the power consumption of the network coding enabled IP
over WDM network:

$\displaystyle
P_{T}=\sum_{m\in\mathcal{N}}\bigg{(}p_{p}Y_{m}+p_{x}X_{m}+p_{o}+p_{md}$
$\displaystyle+\sum_{n\in\mathcal{N}_{m}}{\left(p_{t}w_{mn}+p_{e}A_{mn}f_{mn}\right)}\bigg{)}.$

The power consumption outlined in the objective function is made of the
following components:

  * •

The power consumption of conventional router ports

$\sum_{m\in\mathcal{N}}p_{p}Y_{m}.$ (1)

  * •

The power consumption of NC router ports

$\sum_{m\in\mathcal{N}}p_{x}X_{m}.$ (2)

  * •

The power consumption of optical switches

$\sum_{m\in\mathcal{N}}p_{o}.$ (3)

  * •

The total power consumption contribution from multiplexers and demultiplexers

$\sum_{m\in\mathcal{N}}p_{md}.$ (4)

  * •

The total power consumption contribution from transponders

$\sum_{m\in\mathcal{N}}\sum_{n\in\mathcal{N}_{m}}p_{t}w_{mn}.$ (5)

  * •

The power consumption of all the EDFAs in the network

$\sum_{m\in\mathcal{N}}\sum_{n\in\mathcal{N}_{m}}p_{e}A_{mn}f_{mn}.$ (6)

Subject to:

$\sum_{n\in\mathcal{N}_{m}}b_{mn}^{sd}-\sum_{n\in\mathcal{N}_{m}}b_{nm}^{sd}=\left\\{\begin{array}[]{lr}1&:m=s\\\
-1&:m=d\\\ 0&:otherwise\end{array}\right\\}$ (7)

$\forall s,d,m\in\mathcal{N}$

. Constraint (7) represents the flow conservation constraint. It ensures
traffic routing from source to destination.

$w_{mn}^{sd}=\lambda^{sd}b_{mn}^{sd},$ (8)

$\forall s,d\in\mathcal{N},\forall m\in\mathcal{N},n\in\mathcal{N}_{m}$

. Constraint (8) calculates the flow of a traffic demand that traverses a link
based on the binary variable $b_{mn}^{sd}$.

$w_{mn}=\sum_{s\in\mathcal{N}}\sum_{d\in\mathcal{N}:s\neq d}w_{mn}^{sd},$ (9)

$\forall m\in\mathcal{N},n\in\mathcal{N}_{m}$

. Constraint (9) calculates the aggregate traffic on a given link which is
represented by the total flow of all demands passing through that link.

$\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\ s\neq
d\end{subarray}}w_{mn}^{sd}\leq WBf_{mn},$ (10)

$\forall s,d,m\in\mathcal{N},n\in\mathcal{N}_{m}$

. The link capacity conservation constraint is ensured by constraint (10),
where the total flow on a link must not surpass the total capacity of all
fibres on that link.

$Npo_{mn}=\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s\neq d\\\ s=m\end{subarray}}\frac{w_{mn}^{sd}}{B}.$ (11)
$Npi_{mn}=\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s\neq d\\\ d=m\end{subarray}}\frac{w_{mn}^{sd}}{B}.$ (12)

Equation (11), and (12) are used in the MILP implementation instead of the
more accurate
$\lceil\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\ s\neq
d\\\ s=m\end{subarray}}\frac{w_{mn}^{sd}}{B}\rceil$ and
$\lceil\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\ s\neq
d\\\ d=m\end{subarray}}\frac{w_{mn}^{sd}}{B}\rceil$ respectively which select
the next integer greater than a given real value. This is due to relaxation of
the MILP model.
Now that the number of conventinoal ports leaving and entering a node are
determined by equations (11) and (12) respectively, and noting that router
ports have a pair (i.e. Tx and Rx components), then under the asymmetric
traffic the larger of the outgoing and the incoming traffic at a node
determines the number of conventional router ports needed as shown in Equation
13.

$Np_{mn}=\max(Npo_{mn},Npi_{mn})$ (13)

$\forall m\in\mathcal{N},n\in\mathcal{N}_{m}$

The total number of conventional ports is then given by:

$Y_{m}=\sum_{n\in N_{m}}Np_{mn},$ (14)

$\forall m\in\mathcal{N}$

.

$c_{nmk}^{sd}\leq b_{nm}^{sd},$ (15) $c_{nmk}^{sd}\leq b_{mk}^{sd},$ (16)
$c_{nmk}^{sd}\geq b_{nm}^{sd}+b_{mk}^{sd}-1,$ (17)

$\forall s,d\in\mathcal{N},\forall m,n,k\in\mathcal{N}:m\neq n\neq k$

. Constraints (15, 16, 17) calculate the variable $c_{nmk}^{sd}$ for each node
and different traffic flows, the three constraints are equivalent to the
$c_{nmk}^{sd}=b_{nm}^{sd}b_{mk}^{sd}$, and they are used to maintain the
linearity of the model that is otherwise lost due to the multiplication of
variables.

$X^{m}_{nk}=\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s\neq
d\end{subarray}}{max(\frac{c_{nmk}^{sd}\lambda^{sd},c_{nmk}^{ds}\lambda^{ds}}{B})},$
(18)

$\forall m,n,k\in\mathcal{N}:m\neq n\neq k$

. Constraint (18) calculates the total number of coded ports at node $m$ that
encodes the bidirectional traffic between nodes pair $(n,k)$. Note that the
number of NC ports at a given node is determined according to the maximum flow
of the bidirectional traffic demand of which the node is intermediate due to
zero padding of the smaller flow to match the size of the larger flow. The
presence of the $max()$ function in equation (18) makes the model nonlinear,
hence we use instead the following six constraints collectively to maintain
the linearity of the model.

$w_{nk}^{m}=\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s\neq d\end{subarray}}{c_{nmk}^{sd}\lambda^{sd}}.$ (19)

Constraint (19) calculates the traffic flow value from node $n$ to node $k$
passing through node $m$. To determine the maximum of the bidirectional flows
(i.e. between $w^{m}_{nk}$ and $w^{m}_{kn}$), the variables $\Delta^{m+}_{nk}$
and $\Delta^{m+}_{nk}$ are introduced as binary variables, used to tell if the
difference of opposite flows is positive or negative. The variable
$\Delta^{m}_{nk}$ calculates the difference of the bidirectional traffic
between nodes $n,k$ that passes through node $m$, calculated in Constraint
(20).

$\Delta^{m}_{nk}=w_{nk}^{m}-w_{kn}^{m},$ (20)

$\forall m,n,k\in\mathcal{N}:m\neq n\neq k$

.

$\Delta^{m}_{nk}\leq M\Delta^{m+}_{nk}.$ (21)

$\Delta^{m}_{nk}\geq-M\Delta^{m-}_{nk}.$ (22)

The binary indicator variables $\Delta^{m+}_{nk}$ and $\Delta^{m-}_{nk}$ are
used to tell if the bidirectional flow difference variable (i.e.
$\Delta^{m}_{nk}$) is positive or negative. If $\Delta^{m}_{nk}$ is positive,
then $\Delta^{m+}_{nk}$ is set to $1$, and if $\Delta^{m}_{nk}$ is negative,
then $\Delta^{m-}_{nk}$ is set to $1$. The case of $\Delta^{m}_{nk}=0$ means
both $\Delta^{m+}_{nk}$ and $\Delta^{m-}_{nk}$ can take the value $0$ or $1$,
and to resolve this ambiguity, constraint (23) is used to ensure that they are
not both set to $1$.

$\Delta^{m+}_{nk}+\Delta^{m-}_{nk}\leq 1.$ (23)

$X^{m}_{nk}=\left\\{\begin{array}[]{l l}\frac{w_{nk}^{m}}{B}&\quad\text{if
$\Delta^{m+}_{nk}$ =1}\\\
\frac{w_{kn}^{m}}{B}&\quad\text{otherwise}\end{array}\right\\}$ (24)

$\forall m,s,d\in\mathcal{N},n,k\in\mathcal{N}_{m},n<k$

.

$X_{m}=\sum_{n\in\mathcal{N}_{m}}\sum_{\begin{subarray}{c}k\in\mathcal{N}_{m}\\\
n<k\end{subarray}}X^{m}_{nk}$ (25)

Constraint (25) calculates the number of NC ports at each given node.

##  IV Network Performance Evaluation

We use regular and common network topologies in our analysis. For regular
topologies we analyze the ring, line, star and full mesh topologies and for
real world core networks we consider the NSFNET and the USNET networks
topologies in USA. In Fig. 5 the NSFNET is shown and is composed of 14 nodes
and 21 bidirectional links, with an average hop count equal to 2.17. The
USNET, depicted in Fig. 6, has an average hop count of 3, with 43 links
connecting 24 nodes.

123456789101112131426025232438086841611402482722927041036212224752668536408684664353
Pacific standard time (PST) Mountain standard time (MST) Central standard time
(CST) Eastern standard time (EST) Figure 5: The NSFNET topology

We model traffic demands by using the average traffic demands of the network
as shown in Fig. 7 [5]. The traffic follows a uniform probability distribution
with values ranging from 20 Gb/s to 120 Gb/s. The peak value is observed at
22:00. This peak shifts according to the time zones by 1 hour. The actual
traffic matrix is generated randomly and ensures that the average traffic at
each time zone (including intra-zone traffic and inter-zone traffic) is that
of Fig. 7. This traffic model shows two kinds of variations, the first is the
variation between different times of the day and the second between different
nodes at a given time point. The traffic demands between node pairs takes
values between 10 and 230 Gbps.

123456789101112131415161718192021222324252216220432360304280368364464262360328440272364572288236244320320268344648280332368272224288272280168364280188216164260180PSTMSTCSTEST Figure 6: The USNET topology $0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$18$$19$$20$$21$$22$$23$$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$110$$120$$130$Time of the dayAverage Traffic Demand Per Node Pair (Gbps)EST areaCST areaMST areaPST area Figure 7: Average traffic demands at different times of the day[4] TABLE IV: Network Parameters Parameter | Value
---|---
Separating distance between EDFAs | 80 km
Number of wavelengths in a single fibre (W) | 16
Capacity of a single wavelength (B) | 40 Gbps
Conventional port power consumption (Pp) [39] | 1 kW
NC port power consumption (Px) | 1.1 kW
Transponder power consumption (Pt) [40] | 73 W
Optical Switch power consumption (PO) [41] | 85 W
MUX/DeMUX power consumption [42] | 16 W
EDFAs power consumption (Pe) [43] | 8 W

Other network parameters are shown in Table IV , including the power
consumption of various network elements. The power consumption of the network
devices is derived from [39, 40, 41, 42, 43]. The 100 Watts increase in power
consumption for the NC ports represents a moderate estimate of the power
consumption of the processing of the XOR operation and the added transmitter
and amplifier at the physical interface module of the port. In the
calculations, a partially used wavelength was assumed to consume part of a
router port and a transponder proportional to traffic volume. This assumes
either grooming or a proportional power profile for router ports and
transponders and such a proportional power profile is desirable and is a goal
of the current equipment manufactures and grooming can be practically
achieved. The optimization was carried out using IBM CPLEX software suite and
the AMPL language and was executed on a high performance computing cluster
with 256GB RAM and 16 cores of CPU. The problem falls under the NP-complete
complexity class as it can be reduced to the standard multi-commodity flow
problem (an NP-complete problem), and is further complicated by the need to
consider the assignment of coding nodes and accounting for the zero padding
and partitioning of traffic.
For the solution scenarios considered in the paper, the MILP model runs in the
order of days. The heuristic, on the other hand, have a running time in the
order of seconds.

###  IV-A Example Topologies

Fig. 8 and Fig. 9 show the power consumption of the NSFNET and USNET
topologies, on a full day at 2 hours granularity, respectively. Daily average
savings of 27% and 33% are observed as a result of using network coding in the
NSFNET and USNET topologies, respectively. Note that the higher average hop
count of the USNET topology has a limited effect in terms of increasing the
power savings. Although a topology with a higher hop count means higher number
of conventional ports are replaced by Network Coding enabled ports, however it
also means more conventional ports are required to establish flows between
neighbouring nodes, in which scenario the data flows cannot be encoded.
Therefore, the total power savings produced by using network coding depends on
the ratio of the traffic between neighbouring nodes (which cannot be coded) to
the traffic between non-neighbouring nodes (which can be coded). Higher
savings can be obtained for networks of high hop counts as discussed below.

Fig. 10 compares the distribution of conventional ports and NC ports across
the NSFNET nodes. The conventional ports tend to be almost equally distributed
among nodes, while NC ports are used more in the middle of the network at
nodes with high nodal degree. This is because middle nodes are more likely to
serve as intermediate nodes to traffic flows. Node 6 deploys the highest
number of NC ports as it is located in the network centre, having a nodal
degree equal to 4. Nodes of lower hop count and/or not centrally located
deploy lower number of NC ports.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$22$$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$\cdot
10^{6}$Time of the dayPower (W)NC (MILP) NC
(Heuristic)Conventional$20$$40$$60$$80$$100$$saving\%$Heuristic savingsMILP
savings Figure 8: The NSFNET network power consumption with and without
network coding $0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$0$$1$$2$$3$$4$$5$$\cdot
10^{6}$Time of the dayPower (W)NC (MILP)NC (Heuristic)
Conventional$20$$40$$60$$80$$100$$saving\%$Heuristic savingsMILP savings
Figure 9: The USNET network power consumption with and without network coding
$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$10$$20$$30$$40$Node
numbernumber of PortsNC portsConventional ports Figure 10: Comparison between
the number of the two port types in the NSFNET nodes

The routes selected by the solution of the MILP model show no departure from
the minimum hop routes selected by the conventional scenario. The energy
efficient routing heuristic used in our case can be simply described by
routing all demands following the minimum hop path between the source and
destination nodes, selecting the shortest path in case two alternative paths
have the same minimum hops. Based on this flow allocation, network coding
takes place at all intermediate nodes, then the total power consumption and
the amount of conventional ports and NC ports are calculated. This fact can
help facilitate the migration to the new architecture. Consequently, the
amount of required coded ports at each node can be estimated at the time of
design.
Fig. 8 and 9 show that the average power savings of the energy efficient
heuristic in network coding enabled networks (19% and 22% considering the
NSFNET and the USNET networks, respectively) compared with the energy
efficient network coding MILP model.

###  IV-B Regular Topologies

To investigate the impact of the topology, we reconfigured the NSFNET network
into a bidirectional ring, and a star as seen in Fig. 11, as well as a line
(by removing link (12-14) from the ring), and a full mesh. Note that a star
topology can result in practice if the traffic due to a large data centre
dominates the network. The full mesh can be an attractive network topology if
delay and power consumption are key metrics [7]. The ring and line topologies
have high average hop counts and hence were considered. The distances (in km)
shown on these links are estimates according to nodes locations. Network
coding contributes the highest reduction in network power consumption (33%
daily average saving) in the line topology. The high power saving of the line
topology is attributed to its high average hop count of 5, increasing the
number of intermediate nodes, which increases the number conventional ports to
be replaced by NC ports. On the other hand network coding adds no gain to the
full mesh topology, as all the demands are routed through single hop routes.
The savings obtained by the other topologies exist between these two extremes.
Implementing network coding in a bidirectional ring topology (average hop
count of 3.77) has saved 30% of the network power consumption while a star
topology centred at node 5 with an average hop count of 1.85 has saved 16% of
the network power consumption.

1234567891011121314260300248292212224540408480352500704416252

1234567891011121314572500420248272504728800126010501330

Figure 11: The NSFNET connected by ring and star topologies

The topologies we considered, vary from the full mesh topology having the
maximum number of links, to the star topology, having the lowest number of
links while maintaining connectivity.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$22$$0$$1$$2$$3$$\cdot 10^{6}$Time of
the dayPower (W)LineLine NCRingRing NCStarStar NC Figure 12: Ring and Star
topologies power consumption with and without network coding (MILP results)
LineRingNSFNETStarFull Mesh$0$$10$$20$$30$$40$TopologySavings % Figure 13:
Maximum, minimum and average daily power savings in different network coded
topologies

We extended the physical network topology MILP design model in [7] to perform
network coding at intermediate nodes of bidirectional traffic flows. We
carried out extensive scenario evaluations. For example examined the optimum
physical topology with a constraint of a minimum nodal degree of 1 per node,
and 21 links (number of links in the NSFNET). The optimum topology considering
network coding was in agreement with that obtained in [7].

##  V Network coding with partitioning

In the previous sections we assumed that the smaller of the two bidirectional
flows (packets) is padded with zeros before encoding it with the other flow;
hence the maximum of the two bidirectional flows is used to calculate the
resources used. An alternative approach to prepare packets for network coding
is to partition the bigger packet (flow) into two parts, the first part has
the size of the smaller packet (flow) to be encoded, and the other part will
be routed normally without encoding. Fig. 14 (a) and (b) shows the zero
padding approach (a) and the partitioning approach (b), respectively.

Figure 14: Approaches to ports calculation

The zero padding approach is the easier of the two, but less resource
efficient. The partitioning approach, on the other hand, saves resources at
the expense of adding control and management overheads to decide when and how
to partition packets for the maximum benefit. We update the model in Section
III to support the partitioning approach by changing the previous definition
of the variable $Y_{nk}^{m}$ to represent the difference between the two
packet sizes calculated as

$Y_{nk}^{m}=\frac{w_{nk}^{m}-w_{nk}^{m}}{B},$ (26)

and changing the variable $X_{nk}^{m}$ to represent the minimum of the
opposite flows, this will mean constraint (18) will change into

$X^{m}_{nk}=\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s\neq
d\end{subarray}}{min(\frac{c_{nmk}^{sd}\lambda^{sd},c_{nmk}^{ds}\lambda^{ds}}{B})}.$
(27)

and constraint (24) will be replaced by

$X^{m}_{nk}=\left\\{\begin{array}[]{l l}\frac{w_{nk}^{m}}{B}&\quad\text{if
$\Delta^{m-}_{nk}$ =1}\\\
\frac{w_{kn}^{m}}{B}&\quad\text{otherwise}\end{array}.\right.$ (28)

The network coding with partitioning is subject to all the constraints in
Section III except for constraint (9) that calculates the total number of
conventional ports which is replaced by

$Y_{m}=\sum_{n\in\mathcal{N}_{m}}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s\neq
d\end{subarray}}\frac{w^{sd}_{nm}}{B}+\sum_{n\in\mathcal{N}_{m}}\sum_{\begin{subarray}{c}k\in\mathcal{N}_{m}\\\
k<n\end{subarray}}Y^{m}_{nk}$ (29)

The first term of equation (29) is used to calculate the number of
conventional ports in the zero padding case, where the zero padding case used
the max() function in (13). The use of the max function was necessary as
traffic was asymmetric. If source nodes, for instance, sum the traffic leaving
plus entering and divide this sum by the wavelength rate, this will lead to an
underestimation of the required number of ports. The correct number for the
zero padding approach is dictated by the larger of the two traffic volumes
leaving and entering the port, hence the max() function is needed in (13). In
the partitioning case, however, the asymmetry is removed by the partitioning
process and the residual traffic is handled using conventional network ports.
The first term of equation (29) accounts for the conventional ports at source
and destination nodes, while the second term accounts for the residual flow
from the partitioning process. For example, if the bidirectional flow is
80Gbps in one direction and 50Gbps in the other, then in intermediate nodes
50Gbps will use a coded port while the rest (i.e. 30Gbps) will be served using
conventional ports.
Fig. 15 shows that the improvement obtained by implementing the partitioning
approach is limited compared to the zero padding approach under the uniform
traffic profile. This is because the bidirectional flows of the traffic
demands are comparable. The advantage of the partitioning approach under an
asymmetric traffic profile will be discussed later.

All the previous results are based on the estimation of the NC port’s power
consumption given in Section III. Fig. 16 studies how the savings obtained by
network coding are effected as $r$ (the ratio of the network coding scheme’s
power consumption (i.e. router ports and transponders) and the conventional
scheme) grows. The savings achieved compared to the conventional case reduces
as $r$ increases. While the zero padding approach out performs the
conventional approach up to $r=1.6$, the benefit of the partitioning approach
can be observed up to $r=2$.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$22$$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$1$$1.1$$1.2$$1.3$$\cdot
10^{6}$Time of the dayPower (W)ConventionalNC (zero padding)NC
(partitioning)NC Heuristic (partitioning) Figure 15: Power consumption of the
NSFNET under NC with partitioning approach

Fig. 16 shows the power consumption dependence in the network coding case on
the ports ratio $r=\frac{p_{x}+p_{t}}{p_{p}+p_{t}}$ for the conventional and
the the network coding case with packet partitioning and zero padding under
random traffic using the MILP model. It shows that the port ratio has an
impact on the savings, which are better in the case of the packet
partitioning. We observe savings as long as the power consumption of the NC
port (including the transponder) is less than twice that of the power
consumption of the conventional port.

$1$$1.1$$1.2$$1.3$$1.4$$1.5$$1.6$$1.7$$1.8$$1.9$$2$$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot
10^{6}$Ports ratioPower (W)ConventionalNC PartitioningNC Zero Padding Figure
16: Power consumption versus ports ratio using the MILP model

##  VI Network coding considering the bypass routing approach

In the previous sections we showed that network coding can provide up to 33%
power savings when the non-bypass routing approach is used. Here we extend
this evaluation for the bypass case to evaluate its impact. In bypass routing,
the traffic stays in the optical layer after being converted at the source
until its converted electronically back at the destination [44]. In a
bidirectional flow, source and destination nodes use non network coding
transponders while intermediate nodes use network coding transponders. Flows
between neighbouring nodes use standard non network coding transponders.
The MILP model for this scenario uses all the constraints in the previous non-
bypass model and decides the optimum number and locations of encoding
transponders, and the power consumption of the network for different coded
ports power consumption. The objective function takes into consideration
changes in the required resources in intermediate nodes as compared to the
non-bypass approach. The results in this section are compared with the
conventional scenario without network coding as well as the one with network
coding in non-bypass approach. We also carry out a sensitivity analysis to
account for the possibility of different power consumption values that the
coded port can take in relation to the conventional port and assess the impact
of this value on the overall savings.

TABLE V: Network Parameters for the bypass case [45] Parameter | Value
---|---
Separating distance between EDFAs | 80 km
Wavelengths count in a single fibre (W) | 32
Capacity of a single wavelength (B) [45] | 400 Gbps
Conventional port power consumption (Pp) [39] | 46.7 W
Coded transponder’s power consumption (Px) | 360 kW
Transponder’s power consumption (Pt) [40] | 332.6 W
Optical Switch’s power consumption (PO) | 8.5 W
EDFAs power consumption (Pe) [43] | 15.3 W

The power consumption of the network devices are shown in Table V. The reason
behind using the GreenTouch 2020 power consumption values [45] is that the
power savings of network coding under the 2010 power consumption values are
very small as router ports are the most significant power consumption
equipment in the network, which reduces significantly the contribution of
savings in transponders due to network coding. However, in 2020, the
GreenTouch consortium expects the transponders to consume more power than the
router ports which makes network coding savings become more significant. This
is because transponders are expected to use more digital signal processing at
higher data rates but routers are expected to drop significantly in power
consumption due to the use of optical interconnects, and packet size
adaptation. To match the projected capacity increase in 2020, a wavelength of
capacity 400 Gbps is used. We also assume the power consumption of the network
coding results in network coding ports that consume 10% and 50% higher than
the conventional ports accounting for the extra required elements. To cover a
wide range of this ratio, we show the results for ratios between of 0% and
100%.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$22$$0$$1$$2$$3$$4$$5$$\cdot
10^{5}$Time of the dayPower (W)Non bypassbypassNC bypass (500W)NC bypass
(360W) Figure 17: Power consumption of the NSFNET with bypass at different
time of the day

Fig. 17 shows that under the bypass approach, savings up to 28% can be
obtained under the NSFNET topology with 10% increase in coded transponders
power consumption and 19% considering the 50% increase. These savings are with
reference to the non-bypass approach, but when compared to the conventional
approach, savings of 18% and 9% respectively are obtained for the two
investigated transponders power consumption values.

$330$$360$$390$$420$$450$$480$$510$$540$$570$$600$$630$$660$$2.8$$3$$3.2$$3.4$$3.6$$3.8$$\cdot
10^{5}$Power per coded transponder (W)Power (W)Conventional Non
BypassConventional BypassNC Bypass Figure 18: Power consumption of the network
for different coded transponders’ power values for the NSFNET

In Fig. 18, the total power consumption is plotted at different power
consumption values for the coded transponder while the conventional
transponders power consumption remains fixed to account for the uncertainty in
the additional power consumption that is needed to implement the additional
functions related to network coding. This sensitivity analysis is useful in
determining the value of the coded transponder power consumption at which the
network coding approach seizes to provide savings. The figure shows that the
network coding approach with bypass outperforms both the conventional bypass
and the conventional non-bypass even if the network coding transponder
consumes 660W at 400 Gbps, and even much higher when compared with the
conventional non-bypass case.
In our analysis we considered only the power consumption of the network as the
objective function to be minimized. As studied in [46], network performance
can be affected. This opens the door for additional study that takes into
account additional metrics (e.g. delay) into the optimization. The MILP model
minimizes the network power consumption at different times of the day by
optimizing the number of resources needed at each node. This number represents
the resources that are switched on at that time. For dimensioning the network
the maximum number of each component at each node throughout the day is
considered. It is worth noting that we have used multiple traffic matrices at
different times of the day to represent the multi-hour traffic as opposed to
relying on the dominant matrices technique in [47] for network dimensioning.

##  VII analytic bounds and closed forms

###  VII-A Conventional scenario

Let $G(\mathcal{N},E)$ be a network composed of a collection of undirected
edges, $E$, connecting a set of nodes, $\mathcal{N}$. We define the
bidirectional traffic demand as the triple $(s,d,\lambda^{sd})$, where
$s\in\mathcal{N}$ and $d\in\mathcal{N}$ are end nodes of the demand and
$\lambda^{sd}$ is the data rate requirement of the demand. Assuming each
demand follows a single path, i.e. no traffic bifurcation, the hop count
traversed by a single traffic flow of the bidirectional demand is given by

$h^{sd}=\sum_{m\in\mathcal{N}}\sum_{n\in\mathcal{N}_{m}}b^{sd}_{mn},$ (30)

where $b_{mn}^{sd}$ is a binary variable, $b_{mn}^{sd}=1$ if the flow between
node pair $(s,d)$ is routed through link $(m,n)$, $b_{mn}^{sd}=0$ otherwise.
The average hop count for all flows in the network is given by

$h=\frac{1}{N(N-1)}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s\neq d\end{subarray}}h^{sd}.$ (31)

The power consumption of a single traffic flow, $(s,d)$, of the bidirectional
demand in a conventional IP over WDM network under the non-bypass approach is
given by

$P_{sd}=(p_{p}+p_{t})\sum_{m\in\mathcal{N}}\sum_{n\in\mathcal{N}_{m}}\frac{w^{sd}_{mn}}{B}.$
(32)

Note that we considered only the most power consuming devices; router ports
and transponders for simplicity. Also note that the use of traffic grooming
results in efficient wavelength and router resources utilisation and improves
the accuracy of (32). Assuming all demands of the network are equal, i.e.
$\lambda^{sd}=\lambda,\forall s,d\in\mathcal{N},s\neq d$,

$\sum_{m\in\mathcal{N}}\sum_{n\in\mathcal{N}_{m}}w^{sd}_{mn}=\lambda\sum_{m\in\mathcal{N}}\sum_{n\in\mathcal{N}_{m}}b^{sd}_{m,n}=\lambda
h^{sd}.$ (33)

Therefore the power consumption of the single flow can be given as

$P_{sd}=\left(\frac{P_{t}+P_{p}}{B}\right)\lambda h^{sd}.$ (34)

The total network power consumption can be given as

$P=\left(\frac{P_{t}+P_{p}}{B}\right)\lambda\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s\neq d\end{subarray}}h^{sd}.$ (35)

Let $P^{sd}_{\lambda}=\left(\frac{P_{t}+P_{p}}{B}\right)\lambda^{sd}$ be the
single hop power consumption and $P^{sd}_{\lambda}=P_{\lambda},\forall
s,d\in\mathcal{N},s\neq d$; then the power consumption can be given as

$P=P_{\lambda}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s\neq d\end{subarray}}h^{sd}.$ (36)

The hop count of a traffic demand in the network can be given as a function of
the average hop count $h$ as

$\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\ s\neq
d\end{subarray}}h^{sd}=N(N-1)\frac{\sum_{s}\sum_{d}h^{sd}}{N(N-1)}=N(N-1)h.$
(37)

Therefore the power consumption of the IP over WDM network can be given as

$P=P_{\lambda}hN(N-1).$ (38)

###  VII-B Network coding scenario

For network coding enabled IP over WDM network, both flows of the
bidirectional demand are routed through the same path so network coding is
performed at intermediate nodes. In this case the power consumption of the two
flows of the bidirectional demand $((s,d)$ and $(d,s))$ is given as

$\tilde{P^{sd}}=2\left(\frac{P_{t}+P_{p}}{B}\right)\lambda^{sd}+\left(\frac{P_{t}+P_{x}}{B}\right)\lambda^{sd}(h^{sd}-1),$
(39)

$\forall s,d,\in\mathcal{N},s<d$

. The first term in Equation (39) gives the power consumption of end nodes
where a conventional port is used to send and receive the flows at each end.
Note that the XOR gate and storage at the end nodes have small power
consumption and are not included here. The second term is attributed to
intermediate nodes where coding is implemented. We evaluate equation (39) for
all values of $s<d$, as opposed to the $s\neq d$ used in the conventional
case, because here we take flows in pairs, and hence $\tilde{P^{sd}}$ accounts
for the total power consumed for the flow $(s,d)$ and $(d,s)$. The power
consumption can be re arranged as

$\tilde{P^{sd}}=2\lambda^{sd}\frac{P_{t}+P_{p}}{B}\left(1+\frac{p_{t}+p_{x}}{p_{t}+p_{p}}\left(\frac{h^{sd}-1}{2}\right)\right).$
(40)

Let $r=\frac{p_{t}+p_{x}}{p_{t}+p_{p}}$ represent the ratio of the power
consumption of the network coding scheme (router ports and transponders) and
the conventional scheme, then the power consumption of the bidirectional
demand can be written as

$\tilde{P^{sd}}=2P^{sd}_{\lambda}\left(1+r\frac{h^{sd}-1}{2}\right).$ (41)

The total power consumption with network coding is

$\tilde{P}=2\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}\left(P^{sd}_{\lambda}+P^{sd}_{\lambda}r\frac{h^{sd}-1}{2}\right),$
(42)

giving

$\tilde{P}=2\left(\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}P^{sd}_{\lambda}\left(1-\frac{r}{2}\right)+\frac{r}{2}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}P^{sd}_{\lambda}h^{sd}\right).$ (43)

We start with the equal traffic demands case where all the demands in the
network have the same value, i.e. $P^{sd}_{\lambda}=P_{\lambda},\forall
s,d\in\mathcal{N}$. The total power consumption becomes

$\tilde{P}=2P_{\lambda}\left(\left(1-\frac{r}{2}\right)\left(\frac{N(N-1)}{2}\right)+\frac{rN(N-1)h}{4}\right),$
(44) $\tilde{P}=P_{\lambda}N(N-1)\left(1+\frac{r}{2}(h-1)\right).$ (45)

The power savings $\phi$ is then given by

$\phi=1-\frac{\tilde{P}}{P}=1-\left(\frac{P_{\lambda}N(N-1)\left(1+\frac{r(h-1)}{2}\right)}{P_{\lambda}hN(N-1)}\right),$
(46)

which gives

$\phi=\left(1-\frac{1+0.5r(h-1)}{h}\right).$ (47)

Using the power consumption values of the conventional and NC ports given in
Table IV, $r\approx 1.1$, reducing the savings expression to

$\phi=\left(1-\frac{1+0.55(h-1)}{h}\right).$ (48)
$\phi=\left(0.45\frac{h-1}{h}\right).$ (49)

The derived expression is used to calculate the maximum saving gained by
implementing network coding in regular topologies (star, ring, line) as the
number of nodes grows to infinity.

####  VII-B1 Star topology

$\phi=\left(0.45\frac{\frac{2(N-1)}{N}-1}{\frac{2(N-1)}{N}}\right)=\left(0.45\frac{N-2}{2(N-1)}\right).$
(50)
$\lim_{n\to\infty}\phi=\lim_{n\to\infty}\left(0.45\frac{\frac{2(N-1)}{N}-1}{\frac{2(N-1)}{N}}\right)=0.225.$
(51)

####  VII-B2 Ring topology: Odd number of nodes

$\phi=\left(0.45\frac{\frac{N+1}{4}-1}{\frac{N+1}{4}}\right)=\left(0.45\frac{N-3}{N+1}\right).$
(52)
$\lim_{n\to\infty}\phi=\lim_{n\to\infty}\left(0.45\frac{N-3}{N+1}\right)=0.45.$
(53)

####  VII-B3 Ring topology: Even number of nodes

$\phi=\left(0.45\frac{\frac{N^{2}}{4(N-1)}-1}{\frac{N^{2}}{4(N-1)}}\right)=\left(0.45(\frac{N-2}{N})^{2}\right).$
(54)
$\lim_{n\to\infty}\phi=\lim_{n\to\infty}\left(0.45(\frac{N-2}{N})^{2}\right)=0.45.$
(55)

####  VII-B4 Line topology

$\phi=\left(0.45\frac{\frac{N+1}{3}-1}{\frac{N+1}{3}}\right)=\left(0.45\frac{N-2}{N+1}\right).$
(56)
$\lim_{n\to\infty}\phi=\lim_{n\to\infty}\left(0.45\frac{N-2}{N+1}\right)=0.45.$
(57)

The savings asymptotically reach 45% for the ring and line topologies and
22.5% for the star topology. With network coding ports as power efficient as
conventional ports (i.e. $r=1$), the savings increase to 50% and 25%
respectively.

$20$$40$$60$$80$$100$$120$$0$$0.5$$1$$\cdot 10^{6}$Demand volume (Gbps)Power
(W)Conventional (MILP)NC (MILP)NC (Heuristic)Conventional (Analytical)NC
(Analytical) Figure 19: Power consumption of the analytical and MILP models
for the NSFNET under the zero padding approach

Fig. 19 shows a comparison between the MILP model, the analytical bounds
derived and the heuristic for the case of equal traffic demands between all
nodes for the zero padding approach. The small difference between the
analytical model and the MILP model is attributed to the simplicity of the
analytical formulae which takes into account only the routers and
transponders.

$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$110$$120$$130$$140$$150$$0$$5$$10$$15$$20$$25$$30$$35$$40$$45$$50$NSFNETUSNETNetwork
size (number of nodes)Power savings %Line (A)Ring (A)Star (A)Line (H)Ring
(H)Star (H) Figure 20: Effect of network coding on large network sizes
(A:analytical and H:Heuristic)

Fig. 20 shows the power savings as calculated by the analytical formulae for
the line, ring and star topologies up to a network size of 150 nodes and
compares these savings to the savings of the minimum hop routing heuristic for
the network coding enabled networks for the zero padding approach. For each
network size, the topologies are built with link distances equal to the
average NSFNET link distance. The figure also provides results for the NSFNET
and USNET to show an example of where common core networks are located. The
analytically calculated power savings confirm those of the heuristic. The
savings saturate just below 45% and 22.5% as the size increases. The figure
shows that the ring topology converges to the maximum value faster than the
line topology. Note that the power consumption of the analytical results does
not take into account the power consumption of EDFAs, multiplexers and optical
switches; therefore the power savings of the heuristic are lower than the
analytically calculated power savings.

For the general case when the bidirectional traffic demand volume is randomly
distributed we prove first that the previous case of equal average traffic
demands has better power efficiency compared to the random demands case.
Considering the case of random traffic demands, equation (42) becomes

$\tilde{P}=\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}\bigg{[}2\max(P^{sd}_{\lambda},P^{ds}_{\lambda})+\max(P^{sd}_{\lambda},P^{ds}_{\lambda})r(h^{sd}-1)\bigg{]}.$
(58)

The first part of equation (58) accounts for the power consumption at end
nodes which uses conventional ports, while the second part accounts for the
power consumption at intermediate nodes which uses NC ports. We treat demands
in pairs and hence the use of $(d<s)$ under the summation and the reason for
the multiplication by $2$.

The value of $\max(P^{sd}_{\lambda},P^{ds}_{\lambda})$ can be written as

$\max(P^{sd}_{\lambda},P^{ds}_{\lambda})=\left(\frac{p_{t}+p_{x}}{B}\right)\max(\lambda^{sd},\lambda^{ds}).$
(59)
$\max(\lambda^{sd},\lambda^{ds})=\max(\lambda+\Delta^{sd},\lambda+\Delta^{ds})\\\
=\lambda+\max(\Delta^{sd},\Delta^{ds}),$ (60)

where $\lambda$ is the average traffic of all the network. The total power of
the NC case can be written as

$\tilde{P}=2\left(\frac{p_{t}+p_{p}}{B}\right)\sum_{\begin{subarray}{c}s,d\in\mathcal{N}\\\
d<s\end{subarray}}\bigg{[}\lambda+\max(\Delta^{sd},\Delta^{ds})\bigg{]}\bigg{[}1+r\frac{h^{sd}-1}{2}\bigg{]}$
(61)

which can be written as

$\tilde{P}=P_{\lambda}N(N-1)\bigg{[}1+r\frac{h-1}{2}\bigg{]}+\\\
2\left(\frac{p_{t}+p_{p}}{B}\right)\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}\max(\Delta^{sd},\Delta^{ds})\bigg{[}1+r\frac{h^{sd}-1}{2}\bigg{]}.$
(62)

The first two components of equation (62) are the power consumption of the
network coded case, when the traffic demands are all equal to the average. We
call it $\tilde{P^{(1)}}$ and we call the second part $\tilde{P^{(2)}}$.
Therefore

$\tilde{P^{(1)}}=P_{\lambda}N(N-1)\left(1+r\frac{h-1}{2}\right).$ (63)
$\tilde{P^{(2)}}=2\left(\frac{p_{t}+p_{p}}{B}\right)\sum_{\begin{subarray}{c}s,d\in\mathcal{N}\\\
d<s\end{subarray}}\left(\max(\Delta^{sd},\Delta^{ds})\bigg{[}1+r\frac{h^{sd}-1}{2}\bigg{]}\right).$
(64)

The value $\tilde{P^{(1)}}$ represents the total power consumption of the
network coding case when all demands are equal, the same as given by equation
(45).

By dividing the set of all demands into subsets, each identified by the number
of hops they take, i.e. $H_{k}$ is the set of demands with minimum hop paths
of $k$ hops, then equation (64) can be written as

$\tilde{P^{(2)}}=\frac{p_{t}+p_{p}}{B}\bigg{[}r\sum_{\begin{subarray}{c}(s,d)\in
H_{2}\\\ d<s\end{subarray}}\max(\Delta^{sd},\Delta^{ds})+\\\
2r\sum_{\begin{subarray}{c}(s,d)\in H_{3}\\\
d<s\end{subarray}}\max(\Delta^{sd},\Delta^{ds})+...+\\\
(k-1)r\sum_{\begin{subarray}{c}(s,d)\in H_{k}\\\
d<s\end{subarray}}\max(\Delta^{sd},\Delta^{ds})\bigg{]}+\\\
2\frac{p_{t}+p_{p}}{B}\sum_{s\in N}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}\max(\Delta^{sd},\Delta^{ds}).$ (65)

Let $g_{z}(\lambda^{sd})=\max(\Delta^{sd},\Delta^{ds})$, then

$\tilde{P^{(2)}}=\left(\frac{p_{t}+p_{p}}{B}\right)\bigg{[}\sum_{k}\sum_{\begin{subarray}{c}(s,d)\in
H_{k}\\\ d<s\end{subarray}}(k-1)rg_{z}(\lambda^{sd})\\\
+2\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}g_{z}(\lambda^{sd})\bigg{]}.$ (66)

The value of $\tilde{P^{(2)}}$ depends on the given topology (reflected in
$H_{k}$) and the given traffic volume distribution $g_{z}(\lambda^{sd})$. This
produces three lower bounds , one by setting all hop counts to the minimum,
another by setting the traffic to a value that minimises the total power, and
a third by setting the hop count and the traffic components to their minimum
values. The same applies for the three upper bounds.

The bounds for the total power $\tilde{P}$ are as follows: For a given
topology, the minimum value is when
$g_{z}(\lambda^{sd})=\max(\Delta^{sd},\Delta^{ds})=0$ when
$\Delta^{sd}=\Delta^{ds}=0$. These values are attained when demands are equal.
This gives the following expression of $\tilde{P}$ as

$\tilde{P}\geq P_{\lambda}N(N-1)\left(1+r\frac{h-1}{2}\right),$ (67)

reducing the case to the previous case of the equal average demands.

For the optimal topology and generic traffic demands, we attain the following
minimum value, when all demands have a single hop route $(i.e.h=1)$ when the
network is connected in full mesh:

$\tilde{P}\geq P_{\lambda}N(N-1).$ (68)

This means, the higher the variation, the higher the power consumption. Also,
when given a set of traffic demands with a given variation, the lowest power
consumption will be when bidirectional demands with the highest variance
happen to be allocated the route with the minimum hop count.

Likewise, We can also find the maximum value of $\tilde{P^{(2)}}$ by
considering the topology and traffic dimensions. Considering the traffic
dimension, starting from equation (58) and by using the fact that
$max(P^{sd}_{\lambda},P^{ds}_{\lambda})\leq\frac{p_{t}+p_{p}}{B}\lambda_{max}$
where $\lambda_{max}$ is the upper limit to the traffic value, assuming
uniform traffic distribution

$\tilde{P}\leq
2\frac{p_{t}+p_{p}}{B}\lambda_{max}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}\bigg{[}1+r\frac{h^{sd}-1}{2}\bigg{]},$ (69)

this gives

$\tilde{P}\leq\frac{p_{t}+p_{p}}{B}\lambda_{max}N(N-1)\bigg{[}1+r\frac{h-1}{2}\bigg{]}.$
(70)

An upper bound considering the maximum hop count and the exact traffic is
given by setting the hop count for each demand to the maximum in the network,
i.e. $h^{s,d}=h_{max}$ in equation (64), which gives

$\tilde{P^{(2)}}\leq
2\left(\frac{p_{t}+p_{p}}{B}\right)\bigg{[}1+r\frac{h_{max}-1}{2}\bigg{]}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}g_{z}(\lambda^{sd}).$ (71)

Therefore this bound for the total power consumption becomes

$\tilde{P}\leq P_{\lambda}N(N-1)\left(1+r\frac{h-1}{2}\right)+\\\
2\left(\frac{p_{t}+p_{p}}{B}\right)\bigg{[}1+r\frac{h_{max}-1}{2}\bigg{]}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}g_{z}(\lambda^{sd}).$ (72)

Considering both the maximum traffic and hop count, we have the following
upper bound:

$\tilde{P}\leq\frac{p_{t}+p_{p}}{B}\lambda_{max}N(N-1)\bigg{[}1+r\frac{h_{max}-1}{2}\bigg{]}.$
(73)

The upper bound given by considering the maximum hop count is tighter than the
one considering the maximum possible traffic demand, due to the lower variance
the hop count has compared to the traffic demands variance. For the
partitioning approach, we develop closed form expression the same way we did
with the zero padding approach. The number of NC ports $X$ in the network for
the partitioning case is given by

$X=\frac{1}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}\min(\lambda^{sd},\lambda^{ds})(h^{sd}-1).$ (74)

The number of conventional ports will be covering the traffic at source and
destination nodes and the remaining traffic of the partitioning process at
intermediate nodes.

$Y=\frac{1}{B}\left(\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d\neq s\end{subarray}}\lambda^{sd}+\sum_{s\in
N}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}(h^{sd}-1)|\lambda^{sd}-\lambda^{ds}|)\right).$ (75)

So the total power consumption will be

$P_{t}=\frac{p_{x}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}\min(\lambda^{sd},\lambda^{ds})(h^{sd}-1)+\\\
\frac{p_{p}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d\neq s\end{subarray}}\lambda^{sd}+\\\
\frac{p_{p}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s<d\end{subarray}}(h^{sd}-1)|\lambda^{sd}-\lambda^{ds}|.$ (76)

Terms can be combined together to give

$P_{t}=\frac{p_{p}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d\neq s\end{subarray}}\lambda^{sd}+\\\
\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}(h^{sd}-1)\bigg{(}\frac{p_{x}+p_{t}}{B}\min(\lambda^{sd},\lambda^{ds})+\\\
\frac{p_{p}+p_{t}}{B}|\lambda^{sd}-\lambda^{ds}|\bigg{)}.$ (77)

By arranging terms we get

$P_{t}=\frac{p_{p}+p_{t}}{B}N(N-1)\lambda+\\\
\frac{p_{p}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}(h^{sd}-1)\bigg{(}r\min(\lambda^{sd},\lambda^{ds})+\\\
|\lambda^{sd}-\lambda^{ds}|\bigg{)}.$ (78)
$P_{t}=\frac{p_{p}+p_{t}}{B}N(N-1)\lambda+\\\
\frac{p_{p}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}(h^{sd}-1)\bigg{[}\Delta+r\min(\lambda^{sd},\lambda^{ds})\bigg{]}.$
(79)

where
$\Delta=|\lambda^{sd}-\lambda^{ds}|=\max(\lambda^{sd},\lambda^{ds})-\min(\lambda^{sd},\lambda^{ds})$.
When this is substituted in equation (79) it gives

$P_{t}=\frac{p_{p}+p_{t}}{B}N(N-1)\lambda+\frac{p_{p}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}(h^{sd}-1)\\\
\bigg{[}\max(\lambda^{sd},\lambda^{ds})-\min(\lambda^{sd},\lambda^{ds})+r\min(\lambda^{sd},\lambda^{ds})\bigg{]}.$
(80)

Grouping similar terms gives

$P_{t}=\frac{p_{p}+p_{t}}{B}N(N-1)\lambda+\\\
\frac{p_{p}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
d<s\end{subarray}}(h^{sd}-1)\bigg{[}\max(\lambda^{sd},\lambda^{ds})+\\\
(r-1)\min(\lambda^{sd},\lambda^{ds})\bigg{]}.$ (81)

Let the function $g_{p}(\lambda^{sd})$ be defined as

$g_{p}(\lambda^{sd})=\max(\lambda^{sd},\lambda^{ds})+(r-1)\min(\lambda^{sd},\lambda^{ds}).$
(82)

The function $g_{p}(\lambda^{sd})$ represents the maximum traffic imbalance in
a network where the network coding ports and the conventional ports consume
the same power.

The total power becomes

$P_{t}=\frac{p_{p}+p_{t}}{B}N(N-1)\lambda+\frac{p_{p}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s<d\end{subarray}}(h^{sd}-1)g_{p}(\lambda^{sd}).$ (83)

The lower bound considering the traffic dimension is found from minimising
equation (82)

$g_{p_{min}}(\lambda^{sd})=\bar{\lambda}^{sd}+(r-1)\bar{\lambda}^{sd}=r\bar{\lambda}^{sd},$
(84)

where $\bar{\lambda}^{sd}$ is the traffic volume between $(s,d)$ when the
maximum value equals the minimum value and the average. The total power then
becomes

$P_{t}=\frac{p_{p}+p_{t}}{B}N(N-1)\lambda+\frac{p_{p}+p_{t}}{B}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s<d\end{subarray}}(h^{sd}-1)\bar{\lambda}^{sd}r.$ (85)

By using Chebyshev’s inequality shown in (86) where a lower bound on the
average of the inner product of two vectors of size $n$ is

$\frac{1}{n}\sum_{k=1}^{n}a_{k}b_{k}\geq\left(\frac{1}{n}\sum_{k=1}^{n}a_{k}\right)\left(\frac{1}{n}\sum_{k=1}^{n}b_{k}\right),$
(86)

then equation 85 becomes

$P_{t}\geq\frac{p_{p}+p_{t}}{B}N(N-1)\lambda\\\
+\frac{p_{p}+p_{t}}{B}\sum_{k=1}^{\frac{N(N-1)}{2}}\frac{1}{\frac{N(N-1)}{2}}(h^{k}-1)\sum_{k=1}^{\frac{N(N-1)}{2}}r\bar{\lambda}^{k}.$
(87)

By further reducing the second term of the inequality (87) we get

$P_{t}\geq\frac{p_{p}+p_{t}}{B}N(N-1)\lambda\\\
+\frac{p_{p}+p_{t}}{B}\bigg{[}\frac{1}{\frac{N(N-1)}{2}}\left(h\frac{N(N-1)}{2}-\frac{N(N-1)}{2}\right)r\lambda\frac{N(N-1)}{2}\bigg{]}.$
(88)

This is reduced to

$P_{t}\geq\frac{p_{p}+p_{t}}{B}N(N-1)\lambda\bigg{[}1+(h-1)\frac{r}{2}\bigg{]}.$
(89)

When we consider the topology dimension

$P_{t}\geq
P_{\lambda}N(N-1)+\frac{p_{p}+p_{t}}{B}(h_{min}-1)\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s<d\end{subarray}}g_{p}(\lambda^{sd}),$ (90)

since $h_{min}=1$

$P_{t}\geq P_{\lambda}N(N-1).$ (91)

For the upper bound, considering the topology dimension

$P_{t}\leq
P_{\lambda}N(N-1)+\frac{p_{p}+p_{t}}{2B}(h_{max}-1)\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s<d\end{subarray}}g_{p}(\lambda^{sd}),$ (92)

and considering the traffic dimension, using the fact that the maximum power
consumption of the network under network coding occurs when network coding is
not used. Under the partitioning approach, network coding is not used when the
bidirectional traffic is fully asymmetric, i.e. in one direction
$\lambda^{sd}=\lambda_{max}$ and in the other $\lambda^{sd}=0$. Then equation
(83) becomes:

$P_{t}\leq
P_{\lambda}N(N-1)+\frac{p_{p}+p_{t}}{B}\lambda_{max}\sum_{s\in\mathcal{N}}\sum_{\begin{subarray}{c}d\in\mathcal{N}\\\
s<d\end{subarray}}(h^{sd}-1),$ (93)

which gives:

$P_{t}\leq
N(N-1)\frac{p_{p}+p_{t}}{B}\bigg{[}\lambda+\lambda_{max}\frac{h-1}{2}\bigg{]}.$
(94)

When we consider both the largest hop count and the maximum traffic in the
network we get the following upper bound in (96). This upper bound is
important as the previous two special upper bounds (considering the topology
and considering the traffic separately) can have a varying performance. The
bound with the max traffic volume is generally higher than the one with the
maximum hop count, but in the case of a network with a flat traffic and a very
large hop count the opposite occurs.

$P_{t}\leq
P_{\lambda}N(N-1)+\frac{p_{p}+p_{t}}{B}(h_{max}-1).\lambda_{max}\frac{N(N-1)}{2}$
(95) $P_{t}\leq
N(N-1)\frac{p_{p}+p_{t}}{B}\bigg{[}\lambda+\lambda_{max}\frac{h_{max}-1}{2}\bigg{]}.$
(96)

We notice that the power consumption given by network coding with traffic
partitioning approach under equal traffic demands between all node pairs given
by equation (90) is the same as the one given by the zero padding case with
equal traffic demands given by equation (90). Also the lower bounds are the
same in both cases, when optimising the topology, giving the full mesh which
produces no contribution from network coding, or the minimal traffic case when
both bidirectional flows are equal to the average.

As mentioned above, the upper bound given by considering the maximum hop count
is tighter than the one considering the maximum possible traffic demand.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$22$$0$$2$$4$$6$$8$$\cdot 10^{6}$Time
of the dayPower (W)Upper boundUpper bound (max traffic)Upper bound (max hop
count)MILP resultsEqual trafficlower bound Figure 21: MILP results, the upper
and lower bounds of the zero padding network coding approach
$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$22$$0$$2$$4$$6$$\cdot 10^{6}$Time of
the dayPower (W)Upper boundUpper bound (max traffic)Upper bound (max hop
count)MILP resultsEqual trafficLower bound Figure 22: MILP results, the upper
and lower bounds of the partitioning network coding approach

Figures (21) and (22) show the upper and lower bounds along side the MILP
results of the power consumption of network coding under the zero padding and
partitioning approaches respectively. The MILP results lie between these
bounds. The power consumption under equal traffic demands which are equal to
the average traffic demand is shown to be an approximate representation of the
case of random traffic demands. This is due to the fact that multiple demands
end up having comparable volumes in most cases, and also because the aggregate
bidirectional flows passing through a node, from multiple demands reduce
traffic variation and thus the traffic approaches the equal demand case,
making the equal traffic formulas of significant value. However, if the MILP
was used in a case where one data centre dominates for example, the MILP and
the analytical case with equal average traffic volumes may not agree.

##  VIII Conclusions

In this work, we introduced a technique that can be used to improven energy
efficiencyt technique forin IP over WDM networks using network coding. The
idea presented here proposes a departure from the conventional router ports,
and offers a new architecture that encodes bidirectional flows using a simple
xor operation. In order to evaluate the potential power savings, we formulated
a MILP model, with the objective of minimising the operational power and
developed a minimum hop count routing heuristic for our network coding
approach. The results suggest that network coding improves power efficiency,
as daily average savings of 27% and 33% are obtained when the networks
evaluated were NSFNET and USNET respectively. We investigated the impact of
network topology on the savings by first replacing the NSFNET by line, ring,
star and full mesh topologies. The highest savings are obtained in the line
topology (33%) as a result of the high average hop count of this topology.
Network coding offers no energy saving in the full mesh topology (which has an
average hop count of 1) due to the unavailability of intermediate nodes that
can perform network coding. The minimal contribution of network coding for the
star topology is due to its low average hop count (1.85). It is also shown
that energy efficient routing protocols in the conventional approach are
portable to the network coded approach as the minimum hop routing heuristic is
used to route traffic flows in network coding enabled IP over WDM networks
where network coding is performed in all intermediate nodes traversed by
bidirectional traffic flows. The power savings gained by the heuristic
approach match those obtained by the MILP model. We also presented a
sensitivity analysis showing the impact on savings as a result of varying the
amount of power the network coded ports consume to account for the uncertainty
in our estimation. The highest energy efficiency is obtained when the network
coded port consumes the same power as the conventional port while losses can
be encountered if the NC ports power consumption exceeds twice the power of
the conventional port under typical parameters. We analysed two approaches for
coding imbalanced bidirectional traffic. The first pads the smaller flow with
zeros and the second partitions the larger flow into two components one of
them the size of the smaller packet and hence gets coded; while the other
component is routed in a conventional manner. We showed that the packet
partitioning approach is superior to the zero padding approach especially
under asymmetric traffic. We also studied the implementation of network coding
when the network employs bypass routing. In this case network coding is
performed in the optical layer. Rather than saving resources at the IP layer,
resources are saved in the transponders of the intermediate nodes. We have
shown that implementing network coding in the optical layer (bypass case)
offers less energy savings when compared to the IP layer implementation
(nonbypass case) as the IP routers are the highest power consuming devices in
the network. In contrast, when considering the expected improvement in router
ports power consumption efficiency as suggested by Greentouch and the rise in
power consumption of transponders, the savings of the bypass approach become
more significant. Analytic closed form expressions and bounds are derived and
the MILP results are verified. The formulas are developed for the zero padding
and partitioning network coding approaches for the cases of equal traffic
volumes as well as the uniformly distributed traffic demands. These formulas
are used to study regular networks as their size grows.

## Acknowledgments

This authors would like to acknowledge support from the Engineering and
Physical Sciences Research Council (EPSRC), INTERNET (EP/H040536/1), STAR
(EP/K016873/1) and TOWS (EP/S016570/1) projects. All data are provided in full
in the results section of this paper.

## References

  * [1] GeSI, “GeSI SMARTer 2030: ”ICT Solutions for 21st Century Challenges”,” 2015\.
  * [2] M. Gupta and S. Singh, “Greening of the internet,” Karlsruhe, Germany, pp. 19–26, 2003.
  * [3] Y. Zhang, P. Chowdhury, M. Tornatore, and B. Mukherjee, “Energy Efficiency in Telecom Optical Networks,” vol. 12, no. 4, pp. 441–458, 2010.
  * [4] X. Dong, T. El-Gorashi, and J. M. Elmirghani, “Ip over wdm networks employing renewable energy sources,” _Lightwave Technology, Journal of_ , vol. 29, no. 1, pp. 3–14, 2011.
  * [5] X. Dong, T. El-Gorashi, and J. M. H. Elmirghani, “Green IP Over WDM Networks With Data Centers,” _Journal of Lightwave Technology_ , vol. 29, no. 12, pp. 1861–1880, Jun. 2011. [Online]. Available: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5756625
  * [6] H. M. M. Ali, T. E. El-Gorashi, A. Q. Lawey, and J. M. Elmirghani, “Future energy efficient data centers with disaggregated servers,” _Journal of Lightwave Technology_ , vol. 35, no. 24, pp. 5361–5380, 2017.
  * [7] X. Dong, T. E. H. El-gorashi, and J. M. H. Elmirghani, “On the Energy Ef fi ciency of Physical Topology Design for IP Over WDM Networks,” vol. 30, no. 12, pp. 1931–1942, 2012.
  * [8] A. Lawey, T. El-Gorashi, and J. Elmirghani, “Distributed energy efficient clouds over core networks,” _Lightwave Technology, Journal of_ , vol. 32, no. 7, pp. 1261–1281, April 2014.
  * [9] N. Osman, T. El-Gorashi, L. Krug, and J. Elmirghani, “Energy-efficient future high-definition tv,” _Lightwave Technology, Journal of_ , vol. 32, no. 13, pp. 2364–2381, July 2014.
  * [10] A. Lawey, T. El-Gorashi, and J. Elmirghani, “Bittorrent content distribution in optical networks,” _Lightwave Technology, Journal of_ , vol. 32, no. 21, pp. 4209–4225, Nov 2014.
  * [11] Z. T. Al-Azez, A. Q. Lawey, T. E. El-Gorashi, and J. M. Elmirghani, “Energy efficient iot virtualization framework with peer to peer networking and processing,” _IEEE Access_ , vol. 7, pp. 50 697–50 709, 2019.
  * [12] M. S. Hadi, A. Q. Lawey, T. E. El-Gorashi, and J. M. Elmirghani, “Patient-centric cellular networks optimization using big data analytics,” _IEEE Access_ , vol. 7, pp. 49 279–49 296, 2019.
  * [13] M. S. Hadi, A. Q. Lawey, T. E. El-Gorashi, and J. M. Elmirghani, “Big data analytics for wireless and wired network design: A survey,” _Computer Networks_ , vol. 132, pp. 180–199, 2018.
  * [14] A. M. Al-Salim, A. Q. Lawey, T. E. El-Gorashi, and J. M. Elmirghani, “Energy efficient big data networks: Impact of volume and variety,” _IEEE Transactions on Network and Service Management_ , vol. 15, no. 1, pp. 458–474, 2017.
  * [15] L. Nonde, T. El-Gorashi, and J. Elmirghani, “Energy efficient virtual network embedding for cloud networks,” _Lightwave Technology, Journal of_ , vol. 33, no. 9, pp. 1828–1849, May 2015.
  * [16] A. N. Al-Quzweeni, A. Q. Lawey, T. E. Elgorashi, and J. M. Elmirghani, “Optimized energy aware 5g network function virtualization,” _IEEE Access_ , vol. 7, pp. 44 939–44 958, 2019.
  * [17] J. Elmirghani, T. Klein, K. Hinton, L. Nonde, A. Lawey, T. El-Gorashi, M. Musa, and X. Dong, “Greentouch greenmeter core network energy-efficiency improvement measures and optimization,” _IEEE/OSA Journal of Optical Communications and Networking_ , vol. 10, no. 2, pp. A250–A269, 2018.
  * [18] M. O. Musa, T. E. El-Gorashi, and J. M. Elmirghani, “Bounds on greentouch greenmeter network energy efficiency,” _Journal of Lightwave Technology_ , vol. 36, no. 23, pp. 5395–5405, 2018.
  * [19] R. Ahlswede, C. Ning, S. Y. R. Li, and R. W. Yeung, “Network information flow,” _Information Theory, IEEE Transactions on_ , vol. 46, no. 4, pp. 1204–1216, 2000.
  * [20] C. Fragouli and E. Soljanin, _Network coding applications_. Now Publishers Inc, 2007.
  * [21] M. Belzner and H. Haunstein, “Network coding in passive optical networks,” in _Optical Communication, 2009. ECOC ’09. 35th European Conference on_ , 2009, pp. 1–2.
  * [22] K. Fouli, M. Maier, and M. Medard, “Network coding in next-generation passive optical networks,” _Communications Magazine, IEEE_ , vol. 49, no. 9, pp. 38–46, 2011.
  * [23] X. Liu, K. Fouli, R. Kang, M. Maier, and S. Member, “Network-Coding-Based Energy Management for Next-Generation Passive Optical Networks,” vol. 30, no. 6, pp. 864–875, 2012.
  * [24] S. A. Aly and A. E. Kamal, “Network Protection Codes Against Link Failures Using Network Coding,” in _Global Telecommunications Conference, 2008. IEEE GLOBECOM 2008. IEEE_ , 2008, pp. 1–6.
  * [25] A. E. Kamal, A. Ramamoorthy, L. Long, and L. Shizheng, “Overlay Protection Against Link Failures Using Network Coding,” _Networking, IEEE/ACM Transactions on_ , vol. 19, no. 4, pp. 1071–1084, 2011.
  * [26] P. Babarczi, J. Tapolcai, P.-H. Ho, and M. Médard, “Optimal dedicated protection approach to shared risk link group failures using network coding,” in _Communications (ICC), 2012 IEEE International Conference on_. IEEE, 2012, pp. 3051–3055.
  * [27] X. Chen, A. Engelmann, A. Jukan, and M. Médard, “Linear network coding and parallel transmission increase fault tolerance and optical reach,” _IEEE/OSA Journal of Optical Communications and Networking_ , vol. 9, no. 4, pp. 244–256, 2017.
  * [28] M. Musa, T. Elgorashi, and J. Elmirghani, “Bounds for energy-efficient survivable ip over wdm networks with network coding,” _IEEE/OSA Journal of Optical Communications and Networking_ , vol. 10, no. 5, pp. 471–481, 2018\.
  * [29] M. Musa, T. Elgorashi, and J. Elmirghani, “Energy efficient survivable ip over wdm networks with network coding,” _IEEE/OSA Journal of Optical Communications and Networking_ , vol. 9, no. 3, pp. 207–217, 2017.
  * [30] E. D. Manley, J. S. Deogun, and X. Lisong, “Network coding for optical-layer multicast,” in _Broadband Communications, Networks and Systems, 2008. BROADNETS 2008. 5th International Conference on_ , 2008, pp. 452–459.
  * [31] E. D. Manley, J. S. Deogun, L. Xu, and D. R. Alexander, “All-Optical Network Coding,” _Optical Communications and Networking, IEEE/OSA Journal of_ , vol. 2, no. 4, pp. 175–191, 2010.
  * [32] Z. Liu, M. Li, L. Lu, C.-K. Chan, S.-C. Liew, and L.-K. Chen, “Optical Physical-Layer Network Coding,” _IEEE Photonics Technology Letters_ , vol. 24, no. 16, pp. 1424–1427, Aug. 2012. [Online]. Available: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6226828
  * [33] M. Kim, V. Aggarwal, U.-M. O’Reilly, M. Médard, and W. Kim, “Genetic representations for evolutionary minimization of network coding resources,” _Applications of Evolutionary Computing_ , pp. 21–31, 2007.
  * [34] X.-B. Hu and M. S. Leeson, “Evolutionary computation with spatial receding horizon control to minimize network coding resources,” _The Scientific World Journal_ , vol. 2014, 2014.
  * [35] Y. Cui, M. Médard, E. Yeh, D. Leith, and K. Duffy, “Optimization-based linear network coding for general connections of continuous flows,” in _Communications (ICC), 2015 IEEE International Conference on_. IEEE, 2015, pp. 4492–4498.
  * [36] M. Musa, T. El-Gorashi, and J. Elmirghani, “Energy Efficient Core Networks Using Network Coding,” in _Transparent Optical Networks (ICTON), 2015 17th International Conference on_ , July 2015.
  * [37] M. Musa, T. E. El-Gorashi, and J. M. Elmirghani, “Network coding for energy efficiency in bypass ip/wdm networks,” in _2016 18th International Conference on Transparent Optical Networks (ICTON)_. IEEE, 2016.
  * [38] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Muriel, #233, Dard, and J. Crowcroft, “XORs in the air: practical wireless network coding,” _SIGCOMM Comput. Commun. Rev._ , vol. 36, no. 4, pp. 243–254, 2006.
  * [39] Cisco, “Cisco crs-1 16-slot single-shelf system.” [Online]. Available: http://www.cisco.com/c/en/us/products/collateral/routers/crs-1-16-slot-single-shelf-system/product_data_sheet09186a008022d5f3.html
  * [40] Cisco, “Cisco ONS 15454 10-Gbps Multirate Transponder Card.” [Online]. Available: http://www.cisco.com/c/en/us/products/collateral/optical-networking/
ons-15454-m12-multiservice-transport-platform-
mstp/product_data_sheet0900aecd80121bf7.html

  * [41] Cisco, “Data sheet of Glimmerglass Intelligent Optical System 500.” [Online]. Available: http://www.glimmerglass.com/products/intelligent-optical-system-500
  * [42] Cisco, “Data sheet of Cisco ONS 15454 100-GHz 4-CH Multi/Demultiplexer.” [Online]. Available: http://www.cisco.com/c/en/us/products/collateral/optical-networking/
ons-15454-series-multiservice-provisioning-
platforms/product_data_sheet09186a00801a5572.html

  * [43] Cisco, “Cisco ONS 15501 Erbium Doped Fiber Amplifier Data Sheet.” [Online]. Available: http://www.cisco.com/en/US/products/hw/optical/ps2011/
products_data_sheet09186a008008870d.html

  * [44] G. Shen and R. S. Tucker, “Energy-Minimized Design for IP Over WDM Networks,” _Journal of Optical Communications and Networking_ , vol. 1, no. 1, p. 176, Jun. 2009.
  * [45] “Greentouch final results from green meter research study,” http://www.ourenergypolicy.org/wp-content/uploads/2015/06/ GreenTouch_Green_Meter_Final_Results_18_June_2015.pdf, accessed: 30-09-2016.
  * [46] P. Wiatr, P. Monti, and L. Wosinska, “Power savings versus network performance in dynamically provisioned wdm networks,” _IEEE Communications Magazine_ , vol. 50, no. 5, 2012.
  * [47] P. Pavon-Marino, B. Garcia-Manrubia, and R. Aparicio-Pardo, “Multi-hour network planning based on domination between sets of traffic matrices,” _Computer Networks_ , vol. 55, no. 3, pp. 665–675, 2011.

Mohamed Musa received the BSc degree (first-class Honours) in Electrical and
Electronic Engineering from the University of Khartoum, Sudan, in 2009, the
MSc degree (with distinction) in Broadband Wireless and Optical Communication
from University of Leeds, UK, in 2011. He received the PhD from University of
Leeds in 2016 in energy efficient network coding in optical networks. He is
currently a postdoctoral research fellow at University of Leeds, UK. His
current research interests include energy optimization of ICT networks,
network coding and energy efficient routing protocols in optical networks.
---
Dr. Taisir Elgorashi received the B.S. degree (first-class Honors) in
electrical and electronic engineering from the University of Khartoum,
Khartoum, Sudan, in 2004, the M.Sc. degree (with distinction) in photonic and
communication systems from the University of Wales, Swansea, UK, in 2005, and
the Ph.D. degree in optical networking from the University of Leeds, Leeds,
UK, in 2010. She is currently a Lecturer of optical networks in the School of
Electrical and Electronic Engineering, University of Leeds. Previously, she
held a Postdoctoral Research post at the University of Leeds (2010–2014),
where she focused on the energy efficiency of optical networks investigating
the use of renew- able energy in core networks, green IP over WDM networks
with data centers, energy efficient physical topology design, energy
efficiency of content distribution networks, distributed cloud computing,
network virtualization, and big data. In 2012, she was a BT Research Fellow,
where she developed an energy efficient hybrid wireless-optical broadband
access network and explored the dynamics of TV viewing behavior and program
popularity. The energy efficiency techniques developed during her postdoctoral
re- search contributed three out of the eight carefully chosen core network
energy efficiency improvement measures recommended by the GreenTouch
consortium for every operator network world- wide. Her work led to several
invited talks at GreenTouch, Bell Labs, the Optical Network Design and
Modeling conference, the Optical Fiber Communications Conference, the
International Conference on Computer Communications, and the EU Future
Internet Assembly in 2013 and collaboration with Alcatel Lucent and Huawei.
---
Prof. Jaafar Elmirghani is the Director of the Institute of Communication and
Power Networks within the School of Electronic and Electrical Engineering,
University of Leeds, UK. He joined Leeds in 2007 and prior to that (2000–2007)
as chair in optical communications at the University of Wales Swansea he
founded, developed and directed the Institute of Advanced Telecommunications
and the Technium Digital (TD), a technology incubator/spin-off hub. He has
provided outstanding leadership in a number of large research projects at the
IAT and TD. He received the Ph.D. in the synchronization of optical systems
and optical receiver design from the University of Huddersfield UK in 1994 and
the DSc in Communication Systems and Networks from University of Leeds, UK, in
2014. He has co-authored Photonic switching Technology: Systems and Networks,
(Wiley) and has published over 500 papers. He has research interests in
optical systems and networks. Prof. Elmirghani is Fellow of the IET, Fellow of
the Institute of Physics and Senior Member of IEEE. He was Chairman of IEEE
Comsoc Transmission Access and Optical Systems technical committee and was
Chairman of IEEE Comsoc Signal Processing and Communications Electronics
technical committee, and an editor of IEEE Communications Magazine. He was
founding Chair of the Advanced Signal Processing for Communication Symposium
which started at IEEE GLOBECOM’99 and has continued since at every ICC and
GLOBECOM. Prof. Elmirghani was also founding Chair of the first IEEE
ICC/GLOBECOM optical symposium at GLOBECOM’00, the Future Photonic Network
Technologies, Architectures and Protocols Symposium. He chaired this
Symposium, which continues to date under different names. He was the founding
chair of the first Green Track at ICC/GLOBECOM at GLOBECOM 2011, and is Chair
of the IEEE Sustainable ICT Initiative within the IEEE Technical Activities
Board (TAB) Future Directions Committee (FDC) and within the IEEE
Communications Society, a pan IEEE Societies Initiative responsible for Green
and Sustainable ICT activities across IEEE, 2012-present. He is and has been
on the technical program committee of 38 IEEE ICC/GLOBECOM conferences between
1995 and 2019 including 18 times as Symposium Chair. He received the IEEE
Communications Society Hal Sobol award, the IEEE Comsoc Chapter Achievement
award for excellence in chapter activities (both in 2005), the University of
Wales Swansea Outstanding Research Achievement Award, 2006, the IEEE
Communications Society Signal Processing and Communication Electronics
outstanding service award, 2009, a best paper award at IEEE ICC’2013, the IEEE
Comsoc Transmission Access and Optical Systems outstanding Service award 2015
in recognition of “Leadership and Contributions to the Area of Green
Communications”, received the GreenTouch 1000x award in 2015 for “pioneering
research contributions to the field of energy efficiency in
telecommunications”, the 2016 IET Optoelectronics Premium Award and shared
with 6 GreenTouch innovators the 2016 Edison Award in the “Collective
Disruption” Category for their work on the GreenMeter, an international
competition, clear evidence of his seminal contributions to Green
Communications which have a lasting impact on the environment (green) and
society. He is currently an editor of: IET Optoelectronics, Journal of Optical
Communications, IEEE Communications Surveys and Tutorials and IEEE Journal on
Selected Areas in Communications series on Green Communications and
Networking. He was Co-Chair of the GreenTouch Wired, Core and Access Networks
Working Group, an adviser to the Commonwealth Scholarship Commission, member
of the Royal Society International Joint Projects Panel and member of the
Engineering and Physical Sciences Research Council (EPSRC) College. He was
Principal Investigator (PI) of the £6m EPSRC INTelligent Energy awaRe NETworks
(INTERNET) Programme Grant, 2010-2016 and is currently PI of the £6.6m EPSRC
Terabit Bidirectional Multi-user Optical Wireless System (TOWS) for 6G LiFi
Programme Grant, 2019-2024. He has been awarded in excess of £30 million in
grants to date from EPSRC, the EU and industry and has held prestigious
fellowships funded by the Royal Society and by BT. He was an IEEE Comsoc
Distinguished Lecturer 2013-2016.
---