Energy and Delay Aware Routing Algorithm

Energy and Delay Aware Routing Algorithm

Asad Ali, Kanza Ali, Aftab Ahmad Shaikh

Faculty of Information and Communication Technology,

Balochistan University of Information Technology, Engineering and Management Sciences, Quetta

Email: {asad.ali, kanza.ali, aftab.ahmad}@buitms.edu.pk

Abstract—Access networks consume significant portion of the overall energy consumed by internet. The power consumption growth rate of internet is higher then any other consumer of energy. With the introduction of more and more bandwidth hungry applications, there is a huge pressure to reduce network energy consumption while still growing network capacity and functionality. We propose an energy and delay aware routing algorithm for Fiber-Wireless (Fi-Wi) Networks (EDAR) which not only reduce the energy consumption of the FiWi networks and but also does not degrade the overall delay of the network. We introduce dynamic thresholds for switching nodes into sleep and active mode. Our analysis shows a significant reduction in the energy consumption of the Fi-Wi networks while keeping the performance of the network up to an acceptable limit.

Keywords: fiber-wireless networks, energy efficiency, delay, routing

I.  INTRODUCTION

On one hand where ICT tends to reduces energy consumption by allowing us to do online shopping, Tele-working, making virtual offices and enhancing our life styles, increasing productivity. On the other hand energy consumption of the ICT itself has increased significantly due to the high growth of internet traffic. This traffic will continue to grow faster in the coming years due to the introduction of a lot of bandwidth hungry applications. More traffic leads to more ICT equipments thereby increasing the energy consumption of the ICT significantly. Therefore there is an increased economic and environment pressure to reduce power consumption while still growing the networks capacity and functionality. Electricity consumption of internet alone in US is in several billions of dollars [2] [15] According to various estimations of 2009, ICT consumes about 8% total worldwide energy consumption while this portion is will grow to 20% by 2020 [3][4]. In the internet, most of the nodes remain idle most of the time. They do not take part in any kind of routing or other decision making quite frequently. A large portion of energy is consumed by these idle network elements. According to an estimate, utilization of network equipment is even less then 15%. So we can conserve significant amount energy, if we somehow switch these idle nodes into sleep mode. Also access network comprises a large portion of the internet. It consumes more then 75% of overall energy consumed by internet [5] [15]. If the energy of the access network is reduced somewhow, it will result in the conservation of considerable amount of energy.

Literature is full of energy saving algorithms. A detailed survey on energy efficient protocol can be found in [6]. The author provides a summary of all the work focusing on energy efficient and low power design across data link, network, transport, OS/middleware and application layers of wireless networks protocol stack. Gupta and Sing [7] have identified some changes to the internet protocols in order for the devices to be put into sleep mode for saving energy. [9] has evaluated and compared the energy consumption of various access of networks like point-to-point, PON, WiMax and FTTH. The authors drew the conclusion that PON consumes least energy among all the types of networks discussed in the paper. In [8] the author has shown the importance of energy efficient solutions in ICT. The author has also presented the concept of thin client to save energy by delegating all the processing and storage tasks of client’s personal computer to the server. [17] highlights some of the technique that are normally employed to conserve energy in ICT. A survey on energy efficiency in telecom optical networks is provided in [4]. There has been a lot of work done on the energy efficiency of the Passive Optical Networks (PON) and its variants like Gigabit PON (GPON) and Ethernet PON (EPON). In [18] the author has tried to improve the energy efficiency of different PON variants e.g GPON and EPON through energy efficient devices and IC technology. [11] has proposed the coordinated sleeping mechanism and also proposed two new architecture of PON to enable them to switch to sleep mode when it is experiencing low load in its queue. Energy Management Mechanism for EPON is proposed in [10]. The author has given the idea of switching ONUs into sleep mode and determining a suitable wakeup time schedule at Optical Line Terminal (OLT). They have exploited the famous Multi-Point Control Protocol (MPCP) messages to formulate energy consumption. Work in [12] has proposed a new MAC by which a PON is switched into sleep mode when it has low load in its queue. In [18, 19, and 20] too the authors have worked on making different variants of PON energy efficient. [19] has introduced sleep state for PON physical equipments. PON is only a segment of a FiWi network whereas in this paper we have worked on entire FiWi network. A lot of research is being carried out for making FiWi networks energy efficient. A survey on FiWi networks is shown in [21] where the author has discussed some enabling technologies for FiWi networks. The author has also discussed various possible FiWi architectures. In [1] the authors gives the design scheme to minimize the number of active ONUs and energy aware routing algorithm is provided that uses the path having least residual capacity for forwarding the packet to active ONUs while keeping the wireless routers in active state. Power consumption of an Optical Line Terminal (OLT) is almost 20 time of an ONU’s power consumption [4]. Enabling OLT to enter sleep mode will further conserve a significant amount of energy. Realizing this, authors in [13] have worked on switching OLTs into sleep mode. The authors have taken multiple access networks into account, calling a single access network as a segment. Once traffic is below a certain threshold all the optical modules of a segment will switch to sleep mode.

In this paper we have worked on reducing energy consumption at both optical and wireless part of the FiWi network. The proposed (EDAR) algorithm switch maximum number of nodes into sleep mode while keeping the performance of the network to an acceptable limit. There are basically two parts of our proposed scheme. The first part is related to reducing delay in the network, so that even if we switch wireless or optical nodes of the FiWi network into sleep mode, the performance of the network should not affect. The second part energy aware routing which is related to reducing energy consumption of the network. Normally nodes having lesser load then a certain threshold are switched to sleep mode. The thresholds used to switch a node into sleep mode and from sleep mode back to active mode are static. In this paper we propose a scheme in which the threshold will is a dynamic one thus more efficiently saving the energy. By employing EDAR we not only save considerable amount of energy but also the performance of the overall network is not affected.

Rest of the paper is organized as follows. In section II we give an overview of architecture of FiWi networks, and then delay and energy aware routing is shown. Then we show the simulation results in section III and finally conclusion in section IV.

II.  Energy and Delay Aware Routing

In this section we present the architecture of FiWi Networks, the proposed algorithm for reducing delay and energy.

A.  Architecture of a FiWi Network

A FiWi or WOBAN (according to [1, 14, and 15]) is an optimal combination of an optical back-end and a wireless front-end. Figure 1 shows the architecture of a typical FiWi network. At the back end, there is a Central office (CO). The Optical Line Terminal (OLT) resides in CO. Wireless end normally consists of Wireless Mesh Networks (WMN). The CO and the wireless part are connected through a trunk fiber. Optical part ends at the Optical Network Units (ONU) where the optical signal is converted to electrical signal. ONUs are connected to gateway routers. The rest of the wireless nodes are connected to these gateway routers. The distance between the ONU and the CO is almost 20Kms. However, this distance can be decreased or increased depending upon the requirement and the number of ONUs to be supported. End-users whether stationary or mobile, are connected to the network through the wireless nodes. There is an optical splitter between the OLT and the ONUs which splits the signal equally among the entire ONUs. The optical splitter, being passive device, so overall the architecture is more robust.

The WMN in FiWi networks contain so many WMN nodes thus traffic can routed through multiple paths at the same time it enables us to switch these nodes into sleep mode in order to conserve a considerable amount of energy. However, in the wireless part of FiWi networks, when we tend to switch of wireless nodes, there arises a connectivity problem for the end users. The routers may not be able to forward their packets. Thus traffic could not be routed from end user to the specific gateway. In order to resolve the connectivity issue in wireless part, we propose hybrid architecture of FiWi networks.

According to our proposed architecture, we put WiMAX BTSs in the front end of the FiWi networks along with WMN nodes. Thus the front end too becomes the hybrid of WMN and WiMAX. WiMAX BTSs have much longer range then a WMN router. During the low load hours when most of WMN nodes switch to sleep mode, a WMN node having a data packet to forward to a particular gateway, knowing that the nearby node is in sleep mode or there is no other node to whom the packet may be forwarded, will forward the data packet to WiMAX BTS. In this way connectivity issue can be resolved.

Figure 1: Architecture of a FiWi Network

B.  Energy Aware Routing (EDAR)

For routing purpose we have exploited the work of [14] to forward the data through the least delay path. We need to forward the data through a path having least delay. A packet normally suffers fours kind of delays, that is,

1.  Transmission delay which depends on the capacity of each link and is given by, where is the average packet size and C is the capacity between link ab.

2.  Slot Synchronization delay which occurs because each arriving packet will have to wait for synchronizing to the time slot for forwarding. Slot synchronization delay is given by

3.  Queuing Delay which depends upon arrival rate and service rate and is given by , where is the load between link ab.

4.  Propagation delay which is almost negligible.

So the total delay of a link will be the sum of these four types of delays and the total delay between two nodes is the sum of all the delays on each link that comes between the two nodes.

In this paper we have two objective functions that is, maximizing the number of nodes in sleep mode and on the same time reducing the system wide delay. If N is the total number of wireless nodes and Nis the total number of nodes in sleep mode, then we would liketo be maximum. Also we would like system wide delay (D) to be as lesser as possible. Apart from making the FiWi networks energy efficient, we should route traffic through the best possible path that is a path having least delay and maximum capacity in order to avoid congestion and to have better throughput. Also for better performance of the network, capacities to the link must be assigned a priori to the packet arrival. Dividing the capacity of a node according to the load or traffic arrival would result in better throughput, less congestion and better performance. Since each node advertises state of its entire links using Link State Advertisement (LSA). So we can easily get we can easily get from LSAs and thus easily assign capacities to the link. Let the total traffic in the network be, let the load be, whereas on any link ab will be

= (1)

If be the traffic on an individual nodes, then

(2)

If (N) is the set of nodes in the wireless front end of the network, then system wide delay D is given by

; a, b(N); ab (3)

. So if cis the capacity of any node a, capacity C on link ab can be derived as

(4)

If the flow and capacity on each link is known a priori, it is possible to estimate the delay on each link through link state advertisements, each node can disperse the flow and capacity information on its surrounding links to all other nodes, and each node can compute the shortest delay locally.

After finding the least delay path, the next step would be to energy saving. The proposed energy aware routing algorithm saves energy by switching maximum nodes to sleep mode. According to the proposed algorithm first of all, a list of k paths will be created based on. The paths will be used in the increasing order of delays for forwarding the packet. Depending upon the load, use minimum paths to route the traffic while switching the nodes of other paths having higher delays into sleep mode. While a node is switching to sleep mode, it will broadcast a message indicating its switch to sleep mode.