Skip to main content

Energy aware two disjoint paths routing

Journal Article


Abstract


  • Network robustness and throughput can be improved by routing each source-to-terminal (sd, td) demand d via two disjoint paths (2DP). However, 2DP routing increases energy usage despite yielding lower link utilization and higher redundancy. In this paper, we address the problem of minimizing the energy usage of networks that use 2DP. Specifically, our problem, called Energy-Aware Two Disjoint Paths Routing (EAR-2DP), is to maximally switch off redundant links while guaranteeing at least 0≤T≤1.0 fraction of all possible (sd, td) 2DPs remain on and their maximum link utilization (MLU) is no greater than a configured threshold. We first prove that EAR-2DP is NP-complete. Then, we design a fast heuristic solution, called Two Disjoint Paths by Shortest Path (2DP-SP). We have extensively evaluated the performance of 2DP-SP on real and/or synthetic topologies and traffic demands with two link-disjoint paths (2DP-L) and two node-disjoint paths (2DP-N). Our simulation results show that 2DP-SP can reduce network energy usage, on average, by more than 20%, even for MLU below 50%. As compared to using Shortest Path (SP) routing, while reducing energy by about 20%, 2DP-SP does not significantly affect the path length of each (sd, td) demand, even for MLU<50%. Furthermore, almost 94.2% of routes produced by 2DP-SP have route reliability up to 35% higher as compared to SP and up to 50% of the routes are only 5% less reliable than those of 2DP routing without energy savings.

UOW Authors


  •   Lin, Gongqi (external author)
  •   Soh, Sieteng (external author)
  •   Chin, Kwan-Wu
  •   Lazarescu, Mihai (external author)

Publication Date


  • 2014

Citation


  • G. Lin, S. Soh, K. Chin & M. Lazarescu, "Energy aware two disjoint paths routing," Journal of Network and Computer Applications, vol. 43, pp. 27-41, 2014.

Scopus Eid


  • 2-s2.0-84900853515

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/2901

Has Global Citation Frequency


Number Of Pages


  • 14

Start Page


  • 27

End Page


  • 41

Volume


  • 43

Place Of Publication


  • United Kingdom

Abstract


  • Network robustness and throughput can be improved by routing each source-to-terminal (sd, td) demand d via two disjoint paths (2DP). However, 2DP routing increases energy usage despite yielding lower link utilization and higher redundancy. In this paper, we address the problem of minimizing the energy usage of networks that use 2DP. Specifically, our problem, called Energy-Aware Two Disjoint Paths Routing (EAR-2DP), is to maximally switch off redundant links while guaranteeing at least 0≤T≤1.0 fraction of all possible (sd, td) 2DPs remain on and their maximum link utilization (MLU) is no greater than a configured threshold. We first prove that EAR-2DP is NP-complete. Then, we design a fast heuristic solution, called Two Disjoint Paths by Shortest Path (2DP-SP). We have extensively evaluated the performance of 2DP-SP on real and/or synthetic topologies and traffic demands with two link-disjoint paths (2DP-L) and two node-disjoint paths (2DP-N). Our simulation results show that 2DP-SP can reduce network energy usage, on average, by more than 20%, even for MLU below 50%. As compared to using Shortest Path (SP) routing, while reducing energy by about 20%, 2DP-SP does not significantly affect the path length of each (sd, td) demand, even for MLU<50%. Furthermore, almost 94.2% of routes produced by 2DP-SP have route reliability up to 35% higher as compared to SP and up to 50% of the routes are only 5% less reliable than those of 2DP routing without energy savings.

UOW Authors


  •   Lin, Gongqi (external author)
  •   Soh, Sieteng (external author)
  •   Chin, Kwan-Wu
  •   Lazarescu, Mihai (external author)

Publication Date


  • 2014

Citation


  • G. Lin, S. Soh, K. Chin & M. Lazarescu, "Energy aware two disjoint paths routing," Journal of Network and Computer Applications, vol. 43, pp. 27-41, 2014.

Scopus Eid


  • 2-s2.0-84900853515

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/2901

Has Global Citation Frequency


Number Of Pages


  • 14

Start Page


  • 27

End Page


  • 41

Volume


  • 43

Place Of Publication


  • United Kingdom