Energy-Efficient Routing Algorithm Based on Multipath Routing in Large-Scale Networks

Haijun Geng,Qidong Zhang,Jiangyuan Yao,Wei Wang,Zikun Jin,Han Zhang and Yangyang Zhang

1School of Computer and Information Technology,Shanxi University,Shanxi,030006,China

2School of Computer Science and Cyberspace Security,Hainan University,Haikou,570228,China

3School of Cyber Space and Technology,Beihang University,Beijing,100191,China

4College of Engineering Northeastern University,Boston,02115,MA,USA

Abstract:A reduction in network energy consumption and the establishment of green networks have become key scientific problems in academic and industrial research.Existing energy efficiency schemes are based on a known traffic matrix, and acquiring a real-time traffic matrix in current complex networks is difficult.Therefore, this research investigates how to reduce network energy consumption without a real-time traffic matrix.In particular,this paper proposes an intra-domain energy-efficient routing scheme based on multipath routing.It analyzes the relationship between routing availability and energy-efficient routing and integrates the two mechanisms to satisfy the requirements of availability and energy efficiency.The main research focus is as follows:(1)A link criticality model is evaluated to quantitatively measure the importance of links in a network.(2) On the basis of the link criticality model, this paper analyzes an energy-efficient routing technology based on multipath routing to achieve the goals of availability and energy efficiency simultaneously.(3)An energy-efficient routing algorithm based on multipath routing in large-scale networks is proposed.(4)The proposed method does not require a real-time traffic matrix in the network and is thus easy to apply in practice.(5)The proposed algorithm is verified in several network topologies.Experimental results show that the algorithm can not only reduce network energy consumption but can also ensure routing availability.

Keywords: Energy-efficient routing; multipath routing; link criticality model; energy-saving ratio; large-scale network

1 Introduction

The rapid development of the Internet has expanded the scale and number of autonomous systems running on it.This phenomenon has caused many problems that urgently need to be solved, particularly those concerning routing availability [1] and energy-efficient routing [2].Research on network failure measurement has shown that network failure occurs frequently and inevitably.When a failure occurs, the traditional routing protocol cannot complete convergence within 50 ms; the network convergence time requirements of real-time applications, such as IP voice, online stock trading, remote surgery, video streaming media, and instant messaging, are difficult to meet [3].However, early in the design phase, network topology is designed to address sudden failure and peak traffic on the network.Numerous energy-consuming redundant devices are widely deployed on the Internet, which not only induces high economic costs, but also causes a serious waste of resources and adverse impacts on the environment.Research indicates that energy consumed by the Internet accounts for 10% of total global energy consumption [4].Carbonreducing energy conservation has become a common goal worldwide.Thus, improved availability of intra-domain routing and reduced network energy consumption have become key scientific issues to be solved.

The following challenges are encountered in current intra-domain routing availability and energy-efficient routing:

(1) For energy-efficient routing, an algorithm should determine the link utilization in accordance with a real-time traffic matrix in the network and prioritize links with low utilization to achieve energy conservation.However, accurately measuring the real-time traffic matrix in an actual network and calculating the link utilization rate are difficult, and the design of an energyefficient routing algorithm requires an overall understanding of network topology.Consequently,a distributed energy-efficient routing algorithm based on traffic perception is difficult to design.Determining how to design centralized energy-efficient routing based on topology awareness is an important issue.

(2) Most schemes for routing availability and energy-efficient routing address these two problems separately, without considering the differences and connections between them.In fact, a close relationship exists between routing availability and energy-efficient routing.Hence, exploring a mechanism that can integrate these two factors is important to meet the goals of availability and energy conservation concurrently.

The close relationship between routing availability and energy-efficient routing is explained as follows.1) An evident constraint exists between these two factors.ISPs usually deploy numerous redundant links in the network to improve the availability of intra-domain routing, which increases network energy consumption and hinders routing energy conservation.However, the industry generally reduces network energy consumption by shutting down or putting network elements(nodes and links) to sleep, which inevitably reduces routing availability and hinders the goal of increased routing availability.2) A particular relationship exists between these two factors.To improve the availability of intra-domain routing, the industry usually adopts a routing protection algorithm to address frequent network failures.To reduce the energy consumption of the Internet,the industry typically uses an energy-efficient routing algorithm to close network elements (nodes,links).Routing availability mainly solves the problem of random failures in the network.Energyefficient routing can be understood as the planned closing of network elements to achieve the goal of energy conservation.Closed network elements in energy-efficient routing constitute a special form of network failure.Routing availability mainly addresses a single failure situation that appears randomly in the network, whereas energy-efficient routing mainly addresses planned concurrent failures in the network.

As mentioned, existing research schemes for routing availability and energy-efficient routing examine these two scientific problems separately, without considering the differences and connections between them.Therefore, the present research addresses how to design a mechanism for integrating the two to meet the demands of both routing availability and energyefficient routing.

This research first deeply investigates the relationship between routing availability and energy conservation and then combines these two factors to prevent the one-sided approach of studying a particular problem in isolation.Finally, it explores a mechanism to combine these two factors to meet the goals of availability and energy conservation simultaneously.In particular, our contribution is summarized as follows:

? We study the relationship between routing availability and energy-efficient routing.

? We investigate the link criticality model in the network.

? We propose an energy-efficient routing algorithm in large-scale networks (EERALN).

? We verify the proposed algorithm in several topologies.

2 Related Work

2.1 Research Progress in Routing Availability

Numerous studies on network failure have shown that failures occur frequently and inevitably in a network [5].Academic and industrial generally adopt a routing protection scheme [6] to address frequent failures in the network.Equal-cost multipath routing (ECMP) is one of the earliest and simplest routing protection schemes, but research has shown that this scheme cannot provide high routing availability [7].In view of the problems with ECMP, the Internet Engineering Task Force has released a framework for fast rerouting.On the basis of this framework, Loop free alternate (LFA), a not-via-based route protection scheme [8], and a tunnel-based route protection scheme [9] are proposed.Among all routing protection schemes, LFA has received close industry attention because of its simplicity and has been deployed and supported by the Huawei and Huasan router manufacturers.Although LFA is simple and easy to deploy, it has a critical disadvantage, that is, LFA cannot address all possible single failure situations in the network.To overcome this problem, one author analyzed the problem of the LFA failure coverage rate by using graph theory [10].The routing availability of LFA was increased by adjusting the cost of links in the network, but this method could not guarantee the handling of all single failure situations.Therefore, the relationship between LFA routing availability and network topology was further analyzed in detail [11], and single failure protection of LFA could be improved by adding links.One author [12] studied how to deploy LFA in software-defined networking (SDN)to address all possible single failure situations.This author determined how to rapidly calculate backup paths for all node pairs in a large-scale SDN to address all possible single-link failures in the network.The method divides the process of calculating backup paths into two stages:Index and query stages.In the index phase, only intermediate results are calculated, and the entire backup path is not needed.In the query phase, the final backup path is calculated using the intermediate results obtained in the index phase.In another study [13], the method of failure recovery in SDN was first reduced to an integer linear programming model, and an effective heuristic algorithm (calfr) was then designed to solve the problem.Considerable simulation effort showed that calfr can not only achieve fast recovery but can also prevent network congestion during failure recovery.A local fast rerouting (LFR) algorithm with flow aggregation in SDN was proposed in another study [14].In LFR, if a link failure is detected, then all traffic flows affected by the failure are aggregated into a new large flow.The SDN controller dynamically deploys local rerouting paths for aggregate flows.LFR reduces the number of flow operations between the SDN controller and switch.The experimental results showed that the algorithm can achieve fast recovery from network failure on the premise of ensuring the minimum flow of SDN.

One study [15] proposed a congestion-aware fast failure recovery scheme (Caffe), which can not only rapidly recover the affected flows from various failure scenarios but can also prevent potential congestion in the network after recovery.The experimental results showed that Caffe can achieve fast recovery of network faults with low overhead in switches and controllers.A new failure recovery system sentinel for software-defined WAN traffic engineering was proposed [16].This sentinel calculates the backup path in advance to accelerate failure recovery.When a link fails, the switch redirects the traffic affected by the failure to the backup tunnel and recovers it in the data plane immediately, which can greatly reduce network congestion.The sentinel needs only to introduce a few additional forwarding rules to easily achieve network failure recovery, and it can be easily implemented on OpenFlow switches.

2.2 Research Progress in Energy-Efficient Routing

Research has shown that the energy consumption of network equipment in information and communications technology accounts for 10% of global energy consumption [17], increasing yearly.With the gradual expansion of the scale of the Internet, network equipment deployed on the Internet has increased steadily, and network energy consumption has risen accordingly.Therefore, determining how to reduce network energy consumption has become an important research topic [18].Although network topology is designed to address sudden failure and peak traffic on the network, the shortest path forwarding message, which does not utilize redundant links in the network, is adopted in the routing protocol deployed on the Internet.The link utilization rate of a backbone network is only 30% at peak traffic and less than 5% most of the time.This condition provides an opportunity to study Internet energy-saving mechanisms.

One group of researchers [19] elucidated the energy-saving optimization problem in SDN and then proposed a heuristic method for flow engineering based on energy perception to solve this problem.The experimental results showed that the method could save approximately 60%of energy consumption.Another paper [20] considered the maximum number of inactive links and the minimum transmission rate as goals for energy saving in SDN; the problem was then reduced to a mixed-integer programming problem.On this basis, a greedy algorithm with low complexity that could maximize traffic on the network and converge in the active link was proposed.The experimental results showed that this method could save 17.18%-32.97% in terms of energy consumption.Virtual machine layout and the flow scheduling of routing in energyefficient routing were studied in another paper [21].A new method for evaluating the importance of virtual machines and allocating traffic was proposed.The experimental results showed that the scheme could reduce the number of active devices, such as servers and network components, and thus greatly save energy.In view of the energy-saving problem in hybrid SDN, one paper [22]discussed the challenges and opportunities faced in deploying energy-saving schemes in hybrid SDN.Another paper [4] proposed a problem of optimizing the deployment location of an SDN router.The author presented a heuristic algorithm with low complexity that makes the router deployment maximize consideration of the financial factor and network control capability without increasing upgrade costs.The energy-saving flow engineering problem in hybrid SDN was also examined [23].First, a mathematical optimization model of energy-saving flow engineering in mixed SDN was established.Then, the problem was shown to be an NP-hard problem.Finally, a fast heuristic algorithm based on energy and flow perception was proposed to solve the problem.The experimental results showed that the proposed algorithm can considerably reduce energy consumption of the network in mixed SDN.The relationship between the number of SDN nodes deployed in the network and energy saving was studied in another paper [24], where these two factors were considered using a genetic algorithm.The experimental results showed that the genetic algorithm could achieve the same energy-saving effect as SDN when 50% of SDN nodes were reduced.

3 Problem Description

3.1 DC

The main intra-domain routing protocols presently deployed on the Internet are link-state routing protocols, such as IS-IS and OSPF.In these two routing protocols, all routers in the network have complete topology in their own autonomous domain.When the network is in a stable state, the topology stored in all routers is consistent.Each router in the network uses the shortest-path-first algorithm to calculate the shortest path tree with its own root in accordance with the network topology and then constructs a routing table with the tree.From the above description, current intra-domain routing protocols use the shortest path to forward packets.However, when the next hop from the source node to the destination node fails, the packets transmitted to the node will be lost, which will cause network interruption and will greatly reduce the user experience.Therefore, DC was proposed to cope with all single-link failure scenarios.DC can be expressed as follows:

DC:For packets forwarded to destinationd, nodec(c/=d)can forward them to any neighboring nodexwhencost(x,d)

3.2 Link Criticality Model and Problem

In this research, energy-efficient routing is achieved by closing links in the network.However,the importance of each link in the network differs.Closing important links in the network will seriously affect network performance, which is not conducive to the implementation of an energyefficient routing algorithm.Therefore, we analyzed a link criticality model that can quantitatively measure the importance of links.

Existing energy-efficient routing schemes usually use link utilization to measure the importance of links and to prioritize links with low utilization.Nevertheless, a real-time traffic matrix in an actual network is difficult to measure accurately.In this work, the importance of links is measured using easily obtained network topology characteristics.The topological characteristics considered include link betweenness and energy.Link betweenness considers the importance of a link in the process of forwarding packets, and link energy considers the energy consumed by a link.The studied link criticality model is composed of link betweenness and energy.However, their simple calculation does not meet the requirements of the link criticality model.The proportions of the two in the link criticality model should be considered; however, we should consider their difference in terms of a numerical value.Thus, we evaluate how to use link betweenness and energy to effectively measure the importance of links in the network.

In accordance with the routing availability model based on routing protection, routing availability is related to the betweenness and energy of a link.Therefore, we establish a link criticality model for quantitatively measuring the contribution of links to energy-efficient routing, which can be expressed as follows:

In Eq.(1),B(l)is the betweenness of the link;BmaxandBminrepresent the maximum and minimum of link betweenness, respectively;XmaxandXminrepresent the maximum and minimum values of the link energy, respectively; andαrefers to the adjustment factors that control the importance of the betweenness and energy consumption in the network.Thus, link importance is correlated positively with betweenness and negatively with energy consumption.The model normalizes link betweenness and energy and solves the problem that a considerable difference may exist between the two values.

Considering network topology, this research determines how to design an energy-efficient routing algorithm that can meet network availability and energy-efficient routing requirements simultaneously.

4 EERALN

This section describes an algorithm (EERALN) that can meet routing availability and energyefficient routing requirements simultaneously.The main rationale behind EERALN is as follows:

(1) In accordance with DC rules, the paths between all source destination pairs in the network are calculated.

(2) In accordance with the link criticality model, the criticality of all links in the network is calculated.

(3) In accordance with all the paths and link criticality in the network, the links in the network are closed as much as possible to achieve an energy-saving effect.

We elucidate EERALN in detail below to solve the above-mentioned problem.For any source destination pair in the network, the paths between all pairs are calculated in accordance with DC rules (lines 1-5).For any link in the network, the criticality of all links is calculated on the basis of the link criticality model (lines 6-8).The set of closed links is initialized to null (line 9).A priority queue, which stores links and their criticality and adds all links and their corresponding criticality to the priority queue, is created (lines 10-12).When the priority queue is not empty,the algorithm performs the following operation to extract the first element from the counterpart of the priority queue that has the least criticality (line 14).If all nodes in the network do not contain the link, then the link is added to the set of closed links.For all source destination pairs,the path that contains the link is deleted (lines 17-23).When the program is finished, it returns to the set of closed links (line 26).

Algorithm:EERALN Input:G=(V,E)Output:M,M ?V 1:For s ∈V do 2:For d ∈V do 3:compute all paths for source destination (s,d) pairs P(s,d)4:EndFor 5:EndFor 6:For e ∈E do

7:compute link criticality for all links in the network c(e)8:EndFor 9: M ←?10:For e ∈E do 11:Enqueue(Q, e,c(e))12:EndFor 13:While Q is not empty do 14: l ←Dequeue (Q)15:If ?(s,d),?l /∈P(s,d) then 16:M ←M ∪{l}17:For s ∈V do 18:For d ∈V do 19:If l ∈p(s,d) then 20:P(s,d)←P(s,d)?p(s,d)21:EndIf 22:EndFor 23:EndFor 24:EndIf 25:EndWhile 26:return M

5 Performance Evaluation

This section evaluates EERALN in terms of the energy-saving ratio.To indicate the performance of EERALN, we compare its results with those of distributed least flow (DLF).The algorithms are implemented on a PC (Intel i7, 3.7 GHz CPU, and 8 G memory).The experimental results correspond to the average values of 50 random experiments.

(1) Power consumption of line card

The power consumption of different line cards is set according to reference [25] and is assumed to be independent of traffic.Specifically, OC-3 consumes 60 W, OC-12 consumes 80 W,OC-48 consumes 140 W, and OC-192 consumes 174 W.The gravity model [25] is used to generate network traffic.

(2) Evaluation index

This research compares EERALN with DLF [2], which uses a greedy algorithm to determine a set of links that can be closed and tries to close one link with the least utilization ratio each time until no link can be closed.Our evaluation indexes include the energy-saving ratio.A PC is used in this experiment.The CPU is Intel i7, the main frequency is 1.7 GHz, and memory is 2 G.The related algorithm is implemented using C++.The experimental results are the average value of 20 calculation results.

(3) Topology

We conduct the simulations on a wide range of relevant topologies, including real, inferred,and synthetic.The real topologies include Abilene, USLD, ITALY, NJLATA, and TORONTO,as well as six ISP topologies that are inferred from the measurement results of rocketfuel.The parameters for real and rocketfuel topologies are summarized in Tab.1.We also use brite [26]to generate several topologies; the node number ranges from 100 to 1000, and the average node degree ranges from 5 to 40.Detailed parameters for brite are shown in Tab.2.

Table 1:Parameters for rocketfuel topology

Table 2:Parameters for brite topology

(4) Energy-saving ratio

Fig.1 indicates the energy-saving ratio obtained using different algorithms for real and rocketfuel topologies.EERALN can save more energy than DLF.

Fig.2 illustrates the relationship between the energy-saving ratio and topology size for the generated topologies when the average node degree is 6.The energy-saving ratio of EERALN is lower than that of DLF for all topologies.

Fig.3 shows the relationship between the energy-saving ratio and average node degree for the brite topology when the topology size is 1000.As the average node degree increases, the energy-saving ratios of both algorithms increase accordingly.Nonetheless, EERALN has better performance between the tested algorithms.

Figure 1:Energy-saving ratio for real and rocketfuel topologies

Figure 2:Energy-saving ratio for brite topology

Figure 3:Energy-saving ratio for brite topology

6 Conclusions

This paper presents an energy-efficient routing method for large-scale networks.The method requires only network topology, excluding complex real-time traffic matrixes, which makes it easy to apply in practice.It first calculates all source destination paths in accordance with DC rules and then closes links one by one on the basis of link criticality, thus achieving energy savings.The experimental results show that EERALN can save more energy than DLF.The experiments were all conducted in a simulated environment.We will study how to deploy the algorithm in a real network in future research.

Funding Statement:This work is supported by the Program of Hainan Association for Science and Technology Plans to Youth R&D Innovation (QCXM201910), the National Natural Science Foundation of China (Nos.61702315, 61802092), the Applied Basic Research Plan of Shanxi Province (No.2201901D211168), and the Key R&D Program (International Science and Technology Cooperation Project) of Shanxi Province China (No.201903D421003).

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the study.