Joint overlay routing and relay assignment for green networks

Power consumption of information and communication technologies (ICT) has increasingly become an important issue in the last years. Both energy costs and environmental concerns call for energy aware “green” networking solutions in wired networks. Overlay routing is an attractive method to enhance the performance and reliability of routing mechanisms without the need to change the standards of the current underlying routing. In this work, we focus on overlay routing in wired networks from an energy efficiency perspective. We formulate an optimization problem called JORRA (Joint Overlay Routing and Relay Assignment), which jointly determines the overlay routing paths and relay nodes. We consider issues such as the relay costs, whether the network elements can be put into sleep mode or not as well as the energy efficiency and reliability tradeoff for source and destination pairs in the network. We formulate JORRA as an integer linear program and prove that it is APX-Hard in addition to being NP-Hard even in its special cases. We then show that another special case of JORRA admits a 2-approximation algorithm. Moreover, we propose two polynomial time heuristic algorithms and demonstrate through performance evaluation that our heuristics are suitable for practical implementation.