[go: up one dir, main page]

CN110784405A - Robust energy efficiency routing method for teaching cloud computing network - Google Patents

Robust energy efficiency routing method for teaching cloud computing network Download PDF

Info

Publication number
CN110784405A
CN110784405A CN201910982647.1A CN201910982647A CN110784405A CN 110784405 A CN110784405 A CN 110784405A CN 201910982647 A CN201910982647 A CN 201910982647A CN 110784405 A CN110784405 A CN 110784405A
Authority
CN
China
Prior art keywords
link
network
criticality
equation
node
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN201910982647.1A
Other languages
Chinese (zh)
Other versions
CN110784405B (en
Inventor
蒋定德
刘恒
齐盛
王雨晴
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
University of Electronic Science and Technology of China
Original Assignee
University of Electronic Science and Technology of China
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by University of Electronic Science and Technology of China filed Critical University of Electronic Science and Technology of China
Priority to CN201910982647.1A priority Critical patent/CN110784405B/en
Publication of CN110784405A publication Critical patent/CN110784405A/en
Application granted granted Critical
Publication of CN110784405B publication Critical patent/CN110784405B/en
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/123—Evaluation of link metrics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/14—Routing performance; Theoretical aspects
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/01—Protocols
    • H04L67/12—Protocols specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D30/00—Reducing energy consumption in communication networks

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Health & Medical Sciences (AREA)
  • Computing Systems (AREA)
  • General Health & Medical Sciences (AREA)
  • Medical Informatics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

该发明公开了一种面向教学云计算网络的鲁棒能效路由方法，属于云计算网络绿色通信领域。本发明应用SRLA来寻找最大的一组可休眠链路，并尽可能地将冗余链路转换为休眠状态，以实现节能网络。在确保正常网络路由的情况REERA能够满足网络鲁棒性要求。MCRA路由算法通过网络关键度来表征整个网络的稳定性，最后，将休眠冗余链路算法与最小关键度路由算法相结合，构建云计算网络的鲁棒高效节能路由，克服了低能效的云计算主干网络运行问题。更重要的是，该方法可以动态地改变和调整链路权重，保证链路可以最大统一使用，避免了云计算网络某些链路过度使用时的流量拥塞，可以提高整个网络的性能。

Figure 201910982647

The invention discloses a robust energy-efficient routing method for a teaching cloud computing network, which belongs to the field of cloud computing network green communication. The present invention applies SRLA to find the largest group of sleepable links, and converts redundant links into sleep states as much as possible, so as to realize an energy-saving network. In the case of ensuring normal network routing, REERA can meet the network robustness requirements. The MCRA routing algorithm characterizes the stability of the entire network through the network criticality. Finally, the dormant redundant link algorithm is combined with the minimum criticality routing algorithm to build a robust, energy-efficient and energy-efficient routing for cloud computing networks, which overcomes the low energy efficiency of cloud computing. Computational backbone network operation problems. More importantly, this method can dynamically change and adjust the link weights to ensure that the links can be used maximally and uniformly, avoid traffic congestion when some links in the cloud computing network are over-used, and can improve the performance of the entire network.

Figure 201910982647

Description

Robust energy efficiency routing method for teaching cloud computing network
Technical Field
The invention belongs to the field of green communication of cloud computing networks, and particularly relates to a robust energy efficiency routing method of a cloud computing network.
Background
Cloud computing services provide a novel collaborative and personalized learning style that has significant impact on learning and teaching due to its wider application offerings than other technologies. However, the tremendous growth in the number of network devices and service types makes it difficult to reduce energy consumption, especially in highly loaded cloud computing networks. In addition, the cost pressure of Internet Service Providers (ISPs) is increasing due to the rising price of energy, and the problem of energy consumption is urgently needed to be solved. Therefore, researchers have developed concepts of energy efficiency, aiming to improve the energy efficiency of the network, and to reduce the carbon footprint and energy consumption of the network. How to provide highly reliable and energy-efficient cloud computing services for learning and teaching is a major challenge in the industry and academia.
In general, a typical ISP network is based on an IP-over-WDM architecture; to meet Quality of service (QoS) requirements, ISP network links typically use a redundant design to respond to network conditions of unexpected congestion and routing failures. The design scheme solves the QoS problem, but also causes the problem of low energy efficiency of the network, and how to design a routing algorithm which can meet the QoS requirement and realize a robust energy-saving network is the main purpose of the invention.
If the method of making the idle router and the link sleep, the utilization rate of network resources and network performance is low, so that the method is not suitable for the cloud computing network. The algorithm herein uses srla (sleeping Redundant Links algorithm) to make Redundant Links in the cloud computing backbone network sleep, and uses mcra (minimum critical routing algorithm) to improve the robustness of the entire cloud computing network. The algorithm can dynamically change and adjust the link weight, ensures that the links can be used uniformly to the maximum extent, and avoids flow congestion when some links of the cloud computing network are excessively used.
Disclosure of Invention
Aiming at the defects of the existing method, the invention provides a Robust Energy Efficiency Routing method (REERA) for a teaching cloud computing network, so as to realize teaching and scientific research of a high-Energy Efficiency network for cloud computing service and simultaneously maintain the stability and robustness of the whole network.
The technical scheme of the invention is realized as follows: a robust energy efficiency routing method for a teaching cloud computing network comprises the following steps:
the method comprises the following steps: calculating link utilization
Establishing a link model and calculating the link utilization rate;
step two: dormancy of redundant links using SRLA algorithm
In the SRLA algorithm, a Dijkstra algorithm is used for calculating a shortest path tree of each router node, then a dispatch mechanism and an entry mechanism obtain a modified path tree, and a redundant link is calculated by comparing an SPT (shortest Path first) and an MPT (Multi-Path first) and is dormant;
step three: establishing REERA model
Establishing a REERA model by using the link weight as the input routing flow of the Dijkstra algorithm;
step four: determining SRLA algorithm parameters
Determining parameters, iteration orders and times which are suitable for an SRLA algorithm, triggering the frequency of the SRLA, and time interval T;
step five: calculating link criticality
Calculating link criticality based on the link capacity matrix;
step six: minimizing network criticality
Mapping the value of the link criticality to the link weight, minimizing the network criticality and realizing the most robust network;
step seven: obtaining an optimal routing path by the network link weight matrix;
the appropriate routing path is selected by the network link weight matrix using Dijkstra's algorithm.
Further, the first step calculates the link utilization, and the specific process is as follows:
the cloud computing backbone network is modeled as G (V, E, W), where V is a set of nodes, E is a set of links, and W represents a link weight matrix of the network. In the model, the link states are defined as follows:
wherein x is ij∈{0,1}，L ijE represents a link from node i to node j;
the link energy consumption comprises a base energy consumption
Figure BDA0002235691750000022
And energy consumption related to flow
Figure BDA0002235691750000023
The basic energy consumption means that the constant energy consumption of the operation link is guaranteed to be expressed as:
wherein,
Figure BDA0002235691750000025
represents a link L ijBasic energy consumption of c ijRepresenting the link capacity, δ is a basic energy related parameter, β represents the ratio of the link's energy consumption to its capacity, and the traffic-related energy consumption is:
wherein f is ij(t) denotes a pass-through link L ijThe flow rate of (a);
Figure BDA0002235691750000027
representing the relationship between link energy consumption and the traffic energy consumption carried by it;
link L ijThe energy consumption of (a) is modeled as:
Figure BDA0002235691750000031
link L in T period ijAverage energy efficiency of Can be expressed as:
Figure BDA0002235691750000033
only the dormancy of redundant links of the network is considered in the network and does not involve the shutdown of network nodes. Thus, the energy efficiency of the entire network
Figure BDA0002235691750000034
Can be expressed as:
Figure BDA0002235691750000035
wherein N is sRepresenting a source node, N dRepresenting a destination node, fl sd(t) denotes a slave source node N sE.g. V to destination node N dInstantaneous flow, x, over e V ijIndicating the state of the link, N iRepresenting a node, p 0Representing the power of nodes in the network, set to a constant value,
Figure BDA0002235691750000036
representing a node N sTo node N dAverage flow rate of L ijRepresents a link from node i to node j, V represents a set of nodes, and E represents a set of links;
L ijthe link utilization of (a) is:
Figure BDA0002235691750000037
wherein,
Figure BDA0002235691750000038
indicating that the link is from L ijAverage flow rate of above; c. C ijRepresents the link capacity;
after T time interval, u ijFor link utilization as:
Figure BDA0002235691750000039
wherein,
Figure BDA00022356917500000310
indicating the average utilization of the initial link upon user request,
Figure BDA00022356917500000311
representing the average utilization of the link.
Further, the specific method of the second step is as follows:
modeling a backbone network of cloud computing as G (V, E, W), wherein V is a node set, E is a link set, N and L are cardinality of the sets V and E respectively, and W represents a link weight matrix of the network; calculating a shortest path tree SPT (v) of each router node by a Dijkstra algorithm, wherein v represents the router nodes in the network; set of active links E ADefined as the set of links E involved in the shortest spanning tree A＝U v∈VSPT(v)，U v∈VRepresents a complete subgraph of diagram G; after a shortest path tree SPT (v) of each router node in a network model of cloud computing is obtained, a degree-out mechanism and a degree-in mechanism are utilized to carry out loop iteration to obtain a modified path tree, wherein the degree-out mechanism is to find a degree-out router node ER with the maximum degree in the network; routing router node IR among the ER's neighbors, computing the shortest path trees of ER and IR, comparing the shortest path trees of ER and IR to generate a modified path tree; and finally, comparing the MPT with the SPT to obtain a redundant link and converting the redundant link into a dormant state, and repeating the steps to realize the SRLA algorithm.
Further, the establishing of the REERA model in the third step:
Figure BDA0002235691750000041
s.t.
Figure BDA0002235691750000042
connection(N s,N d)＝1 (9b)
Figure BDA0002235691750000043
Figure BDA0002235691750000044
Figure BDA0002235691750000045
equation (9a) represents a cost function that maximizes the energy efficiency of the network; equation (9b) shows that any traction node is always connected and the traffic between any two nodes is non-negative; equation (9c) indicates that the link weight is used as the link cost when constructing the route; equation (9d) means link L ijIs equal to the load across link L ijThe sum of the flow rates of all OD (origin destination) streams; equation (9e) indicates that the link utilization is not greater than the link capacity; costl ijRepresents a link l ijOverhead of traffic of w ijA link weight value indicating the end of the request,
Figure BDA0002235691750000046
representing (s, d) passing through the link l ijFlow rate of (c) ijRepresents a link l ijThe capacity of (c).
Further, the fourth step of determining parameters of the SRLA algorithm includes the following specific processes:
in order to maximize network energy efficiency, the number of iterations is set to 3, then the frequency of triggering the SRLA is determined, the time interval is set to T, the effect of the time interval T can be offset in the energy efficiency calculation process, and most user requests can be responded within a time interval.
Further, the link criticality is calculated in the fifth step, and the specific process is as follows:
the smaller the criticality of the network is, the stronger the robustness of the network is; therefore, the criticality τ of the network is:
τ＝2nTr(L +) (10)
where n is the number of network nodes, Tr (-) represents the matrix trajectory,
Figure BDA0002235691750000051
is the Moore-Penrose inverse of Laplace matrix L; in equation (6), the criticality τ of the network represents the sum of the resistive distances between all two nodes;
defining a linear relationship between link capacity and initial link weight value, i.e. c ij＝k·w oij+ a, where the parameters k and a are constants, w oijRepresenting an initial value of link weight, and calculating link criticality based on a link capacity matrix; the normalized form of the network criticality τ is expressed as:
Figure BDA0002235691750000052
the formula for calculating the criticality of the network is as follows:
Figure BDA0002235691750000053
d＝diag(c 1,c 2,…c n) (12b)
L c＝d-W (12c)
Figure BDA0002235691750000054
wherein, A (r) represents the set of active nodes, and W represents the link weight matrix; equation (12a) represents the degree of fanout, c, of node r rjRepresents the link capacity from node r to node j; equation (12b) represents a matrix constructed from diagonal vectors of the link capacity matrix; equation (12c) represents a new matrix consisting of a diagonal vector matrix and a weight matrix of link capacities; equation (12d) represents how to compute the normalized network criticality.
Further, the network criticality is minimized in the sixth step, and the specific process is as follows:
due to the relationship between the network criticality and robustness, the objective equation for implementing the most robust network is:
Minτ (13a)
s.t.
∑ (i,j)∈Lw ij≤c ij,c ijis fixed (13b)
0≤w ij≤c ij(13c)
wherein, c ijIs a link capacity matrix; w is a ijIs a link L ijWeights, which can obtain reasonable network link weight values by optimizing the routing algorithm, thereby improving the robustness of the whole network, equation (13a) represents an objective function, and equations (13b) and (13c) represent limits;
equation (10) indicates that the criticality τ of the network is a network-wide measure and can be used to describe network robustness, the smaller the criticality τ of the network, the more robust the network is; equation (13a) represents an objective function that minimizes the criticality τ of the network, the second and third equations showing the constraints satisfied by the weight of each link; equation (13) represents that by minimizing the criticality τ of the network, the optimal link weight satisfying a plurality of constraints is found, and a robust route is constructed;
equation (12) indicates that when the bandwidth capacity of a link changes, the criticality of the link also changes, and for a high-load link, the influence on the whole network in the routing process is large; thus, the value of link criticality is mapped to the link weight, which is updated as the bandwidth capacity of the network link decreases by the following formula:
τ＝n(n-1)τ′ (14a)
Δτ＝τ-τ 0(14b)
w ij＝b·Δτ+w 0ij(14c)
an initial network criticality value for a time interval T; τ is the network criticality value at the end of time T, τ 0Representing an initial network criticality within a particular time interval T; b is a constant, which is based on a simulation of a real network; n is the number of network nodes; w is a 0ijIs the initial link weight value, w, of time T ijIs the link weight value at the end of time interval T; equation (14a) represents the relationship between the criticality of the network and its normalized value; equation (14b) represents a change in the criticality value of the network; equation (14c) characterizes the relationship between the change in the criticality of the network and the link weight value.
The symbols involved in the present invention are defined as follows:
n denotes the collective V cardinal number (where N | | V |), L denotes the cardinal number of the collective E (where L | | | E |), P ij(t) denotes a link L ijInstantaneous power, f ij(t) denotes a link L ijInstantaneous flow of (fl) sd(t) denotes a source node N sE.v and destination node N dE.g. instantaneous flow between V, P ijIndicating the link L within the period T ijAverage power of f ijIndicating the link L within the period T ijAverage flow of, fl sdRepresents N within the period T sAnd N dIs a constant, and po represents the power of the node in the network, c ijRepresents a link L ijThe capacity of the electric power transmission device is,
Figure BDA0002235691750000061
represents a link L ijβ denotes the link L ijRatio of energy consumption to capacity, delta representing a parameter related to the base energy, x ijIndicating the link status, η ijRepresents a link L ijThe average energy efficiency over a period T, μ represents the change matrix of link utilization after a user request T period, ω ijIndicating the link L at the end of the time interval T ijWeight value, w oijRepresents the initial link L ijWeight values, A (k) represents the active node set, W represents the link weight matrix, τ 0An initial network criticality value representing the time interval T, τ representing the network criticality value at the end of time T, b representing a constant, which is based on a simulation of a real network, and n representing the number of network nodes.
The invention has the beneficial effects that:
the method provided by the invention can meet the QoS requirement, realize a robust energy-saving network and provide highly reliable and energy-efficient cloud computing service for learning and teaching. The present invention applies SRLA to find the largest set of sleepable links and converts redundant links to a sleep state as much as possible to achieve an energy efficient network. The REERA can meet the network robustness requirement under the condition of ensuring normal network routing. The MCRA routing algorithm represents the stability of the whole network through network criticality, and finally, the dormant redundant link algorithm is combined with the minimum criticality routing algorithm to construct a robust, efficient and energy-saving route of the cloud computing network, so that the problem of operation of a cloud computing backbone network with low energy efficiency is solved. More importantly, the method can dynamically change and adjust the link weight, ensures that the links can be used uniformly to the maximum extent, avoids flow congestion when some links of the cloud computing network are used excessively, and can improve the performance of the whole network. Simulation analysis shows that the proposed REERA can save a large amount of energy consumption, and is far superior to the existing network routing algorithm based on OSPF (open Shortest Path first).
Drawings
FIG. 1 is a process flow diagram of the robust energy efficient routing method of the present invention;
FIG. 2 is a model of a cloud computing network connecting different data centers and accessing users;
FIG. 3 is a schematic diagram of a cloud computing backbone robust energy efficient routing algorithm;
fig. 4 is a variation process of a second order SRLA network topology;
FIG. 5 shows a network topology of data used in the simulation process;
fig. 6 is a histogram routing algorithm for link utilization for both. The horizontal axis represents the distribution of link utilization. The vertical axis represents the probability of link utilization. The blue bar corresponds to the proposed Algorithm and the red bar corresponds to the OSPFERA (OSPF-based energy-influencing Routing Algorithm) Algorithm;
fig. 7 shows the distribution of the number of times of failure of user requests due to insufficient bandwidth capacity of the link, in which the horizontal axis represents the time interval and the vertical axis represents the number of user beg requests. The blue bar corresponds to the proposed REERA algorithm; red bar versus ospfara algorithm;
FIG. 8 is a graph of utilization profiles for each link in a network, where the x-axis represents time interval and the y-axis represents link utilization. The curve describes the usage of each link and the row is the average usage of both algorithms. The red curve represents the simulation of REERA. The blue curve represents a simulation of OSPFERA;
FIG. 9 is a distribution of sleep link counts, where the red line corresponds to REERA and the blue line corresponds to OSPFEA;
in fig. 10, the method runs 100 simulations for the same user request to calculate the average run time of both. Where the x-axis represents the number of user requests and the y-axis represents the average time in ms.
Detailed Description
The invention is described in further detail below with reference to the following figures and specific examples:
a robust energy-saving routing method for cloud computing network learning comprises the following specific steps:
step one, calculating the link utilization rate, specifically comprising the following steps:
the cloud computing backbone network is modeled as G (V, E, W), where V is a set of nodes, E is a set of links, and W represents a link weight matrix of the network. In the model, the link states are defined as follows:
Figure BDA0002235691750000081
wherein x is ij∈{0,1}，L ijE represents the link from node i to node j.
The link energy consumption comprises a base energy consumption
Figure BDA0002235691750000082
And energy consumption related to flow
Figure BDA0002235691750000083
The basic energy consumption refers to the constant energy consumption of the guaranteed operation link, and is expressed as:
Figure BDA0002235691750000084
in the formula,
Figure BDA0002235691750000085
represents a link L ijBasic energy consumption of c ijRepresenting the link capacity, δ is a basic energy related parameter, β represents the ratio of the link's energy consumption to its capacity, and the traffic-related energy consumption is:
wherein f is ij(t) denotes a pass-through link L ijThe flow rate of (a);
Figure BDA0002235691750000087
representing the relationship between the link energy consumption and the traffic energy consumption carried by it.
Link L ijThe energy consumption of (a) is modeled as:
Figure BDA0002235691750000088
where B represents the base energy and R represents the flow related energy.
Therefore, the link L in the T period ijThe average energy efficiency of (d) can be expressed as:
Figure BDA0002235691750000091
only dormant network redundant links are considered herein, but not the shutdown node. The energy efficiency of the entire network can be expressed as:
Figure BDA0002235691750000092
wherein N is sRepresenting a source node, N dRepresenting a destination node, fl sd(t) denotes a slave source node N sE.g. V to destination node N dInstantaneous flow, x, over e V ijIndicating the state of the link, N iRepresenting a node, p 0Representing the power of nodes in the network, set to a constant value,
Figure BDA0002235691750000093
representing a node N sTo node N dAverage flow rate of L ijRepresenting a link from node i to node j, V representing a set of nodes, and E representing a set of links.
L ijThe link utilization of (a) is defined as:
Figure BDA0002235691750000094
wherein,
Figure BDA0002235691750000095
indicating that the link is from L ijAverage flow rate of above; c. C ijIndicating link capacity
After T cycles requested by the user, u is set as a variable matrix of link utilization, and the mathematical formula is as follows:
Figure BDA0002235691750000096
wherein,
Figure BDA0002235691750000097
and
Figure BDA0002235691750000098
respectively representing the average utilization rate of the initial link and the average utilization rate of the link after the user requests.
Step two: computing dormant redundant links using SRLA algorithm
Modeling a backbone network of cloud computing as G (V, E, W), wherein V is a node set, E is a link set, N and L are cardinality of the sets V and E respectively, and W represents a link weight matrix of the network. Calculating the shortest circuit of each router node by Dijkstra algorithmA path tree SPT (v), v represents a router node in the network; set of active links E ADefined as the set of links E involved in the shortest spanning tree A＝U v∈VSPT(v)，U v∈VRepresenting a complete sub-diagram of diagram G. After a Shortest Path Tree (SPT) (v) of each router node in a network model of cloud computing is obtained, a degree-out mechanism and a degree-in mechanism are utilized to carry out loop iteration to obtain a Modified Path Tree (MPT), wherein the basic idea of the degree-out mechanism is to find out the degree-out router node (Exproter Router, ER) with the maximum degree in the network; an ingress Router node (IR) among the ER's neighbors computes a shortest path tree of ER and IR, which compares spt (IR) with spt (ER) to generate a Modified Path Tree (MPT). And finally, comparing the MPT with the SPT to obtain a redundant link and converting the redundant link into a dormant state, and repeating the steps to realize the SRLA algorithm.
Establishing a REERA model in the third step, which comprises the following specific processes:
the REERA can be seen as an integrated algorithm of SRLA and MCRA, according to a model of a robust energy routing algorithm in the backbone network. Through the above analysis, a REERA optimization model is established.
REERA can be expressed as the following mathematical expression:
Figure BDA0002235691750000101
s.t.
Figure BDA0002235691750000102
connection(N s,N d)＝1 (9b)
Figure BDA0002235691750000104
Figure BDA0002235691750000105
equation (9a) represents a cost function that maximizes the energy efficiency of the network. Equation (9b) shows that any traction node is always connected and that the traffic between any two nodes is non-negative. Equation (9c) indicates that the link weight is used as the link cost when constructing the route. Equation (9d) means link L ijIs equal to the load across link L ijThe sum of all the OD flows. Equation (9e) indicates that the link utilization is not greater than the link capacity.
Step four, determining the parameters of the SRLA algorithm, which comprises the following specific processes:
to maximize network energy efficiency, the order of the SRLA iteration needs to be determined. Based on the analysis, the number of iterations is set to 3, then the frequency of triggering the SRLA is determined, and the time interval is set to T. The effect of the time interval T can be offset in the energy efficiency calculation process. However, it must be determined that most users' requests can be responded to within a time interval.
Step five, calculating the link criticality, wherein the specific process is as follows:
the less critical the network, the more robust the network is. At the beginning of the initial network link capacity, the value of network criticality is minimal. The robustness of a communication network is reflected using the chain criticality, which is defined directly as:
Figure BDA0002235691750000106
where n is the number of network nodes, Tr (-) represents the matrix trajectory,
Figure BDA0002235691750000107
is the inverse Moore-Penrose transform of the laplacian matrix L. In equation (10), the criticality τ of the network represents the sum of the resistive distances between all two nodes, which is a graph-theory based global metric.
Now define a linear relationship between link capacity and initial link weight value, i.e. c ij＝k·w oij+ a (it)The parameters k and a are constants, w oijRepresenting link weight initial values) based on the link capacity matrix. Normalizing the criticality τ of the network to produce a variable, i.e.
The formula for calculating the criticality of the network is as follows:
d＝diag(c 1,c 2,…c n) (12b)
L c＝d-W (12c)
Figure BDA0002235691750000113
wherein, A (r) represents the set of active nodes, and W represents the link weight matrix; equation (12a) represents the degree of fanout, c, of node r rjRepresents the link capacity from node r to node j; equation (12b) represents a matrix constructed from diagonal vectors of the link capacity matrix; equation (12c) represents a new matrix consisting of a diagonal vector matrix and a weight matrix of link capacities; equation (12d) represents how to compute the normalized network criticality.
And step six, minimizing the network criticality, which comprises the following specific processes:
due to the relationship between the network criticality and the robustness, the network criticality is minimized, and the network with the strongest robustness is realized, wherein the target equation is as follows:
Minτ (13a)
s.t.
∑ (i,j)∈Lw ij≤c ij,c ijis fixed (13b)
0≤w ij≤c ij(13c)
wherein, c ijIs a link capacity matrix; w is a ijIs a link L ijAnd (4) weighting. By optimizing the routing algorithmAnd obtaining a reasonable network link weight value, thereby improving the robustness of the whole network. Equation (13a) represents the objective function, while equations (13b) and (13c) represent the constraints.
Equation (10) indicates that the criticality τ of the network is a network-wide metric and can be used to describe network robustness. The smaller the criticality τ of the network, the more robust the network is. Equation (13a) represents an objective function that minimizes the criticality τ of the network; the second and third equations show the constraints that are satisfied by the weight of each link. Equation (13) indicates that finding optimal link weights that satisfy multiple constraints can help build robust routes by minimizing the criticality τ of the network.
Equation (12) indicates that as the bandwidth capacity of a link changes, the criticality of the link also changes. For a highly loaded link, the available bandwidth of the link capacity is relatively low, and the link has a large impact on the entire network during routing. Thus, the method can map the value of link criticality to link weights, which will vary with τ as the bandwidth capacity of the network link decreases. Updating the weight values of the links by the following formula:
τ＝n(n-1)τ′ (14a)
Δτ＝τ-τ 0(14b)
w ij＝b·Δτ+w 0ij(14c)
wherein, a certain time interval T is a criticality value of the initial network; τ is the network criticality value at the end of time interval T; tau is 0Representing an initial network criticality within a particular time interval T; b is a constant, which is based on a simulation of a real network; n is the number of network nodes; w is a 0ijIs the initial link weight value, w, of time T ijIs the link weight value at the end of time interval T.
Equation (14a) represents the relationship between the criticality of the network and its normalized value; equation (14b) represents a change in the criticality value of the network; equation (14c) characterizes the relationship between the change in the criticality of the network and the link weight value.
And seventhly, obtaining the optimal routing path by the network link weight matrix, wherein the specific process is as follows:
the appropriate routing path is selected by the network link weight matrix using the Dijkstra algorithm, which has been described in step one.
Examples
In the simulation of the present invention, the basic power consumption of each router was set to 10W/h. It is divided into each interface (link) according to the simulated topology. FIG. 5 shows a network topology of data used in the simulation process; there are 23 nodes and 74 links in the graph, that is, the positions of the nodes and the lengths of the links do not represent the specific meaning of the network, and there is a direct relationship between the traffic size and the link weight. In order to analyze the superior robustness of the proposed energy-efficient routing algorithm, REERA is compared with ospfara, and the specific implementation steps are as follows:
the method comprises the following steps: calculating link utilization
Establishing a link model and calculating the link utilization rate; FIG. 6 is a histogram routing algorithm for both link utilization, showing that the algorithm's link utilization is better in the range of 2-5, showing that the algorithm's routing structure can keep the link utilization between 20% and 50%; link utilization is neither too high, resulting in network congestion and link failure, nor too low resulting in considerable waste of resources.
Step two: dormancy of redundant links using SRLA algorithm
In the SRLA algorithm, a Dijkstra algorithm is used for calculating a Shortest Path Tree (SPT) of each router node, then an outbound mechanism and an inbound mechanism obtain a Modified Path Tree (MPT), and a redundant link is calculated and is dormant by comparing the SPT and the MPT;
step three: establishing REERA model
Using the link weight as the input routing flow of Dijkstra algorithm, and establishing a REERA model through analysis;
step four: determining parameters for SRLA algorithms
Determining parameters, iteration orders and times which are suitable for an SRLA algorithm, triggering the frequency of the SRLA, and time interval T;
step five: calculating link criticality
Calculating link criticality based on the link capacity matrix;
step six: minimizing network criticality
Mapping the value of the link criticality to the link weight, minimizing the network criticality and realizing the most robust network; fig. 9 shows the distribution of the number of dormant links, and the link weight of the ospfara algorithm remains unchanged after initialization, so that the network cannot dynamically change the distribution of the routes according to the state of the user request, and cannot realize load balancing, so that the robustness of the network is relatively weak. As shown in fig. 9, the REERA may shut down and wake up the link in a time-varying manner. Simulation experiments show that the REERA proposed herein is effective, not only to improve the energy efficiency of the network, but also to improve the robustness of the network.
Step seven: obtaining optimal routing path from network link weight matrix
Selecting a proper routing path by the network link weight matrix by using Dijkstra algorithm; further verifying the performance of both algorithms, run times for different numbers of user requirements were analyzed, as shown in fig. 10, where the method runs 100 simulations for the same user request to calculate the average run time of both. From the method of fig. 10, it can be seen that REERA and OSPFRA remain low on-time. The method uses a desktop computer with 2 cores 3.2ghz cpu and 16G memory for simulation. Less runtime is obtained if a special hardware platform is used. This indicates that rera is actually feasible, and can dynamically change the link weights, ensure that most links are uniformly used, and avoid traffic congestion when some links of the cloud computing network are excessively used, so that the performance of the whole network is improved. By comparing REERA with an Open Shortest Path First (OSPF) algorithm, simulation results show that REERA is superior to the OSPF algorithm, and REERA can realize an energy-saving routing algorithm under the premise of network robustness constraint.

Claims (6)

1. A robust energy efficiency routing method for a teaching cloud computing network comprises the following steps:
the method comprises the following steps: calculating link utilization
Establishing a link model and calculating the link utilization rate;
step two: dormancy of redundant links using SRLA algorithm
In the SRLA algorithm, a Dijkstra algorithm is used for calculating a shortest path tree of each router node, then a dispatch mechanism and an entry mechanism obtain a modified path tree, and a redundant link is calculated by comparing an SPT (shortest Path first) and an MPT (Multi-Path first) and is dormant;
step three: establishing REERA model
Establishing a REERA model by using the link weight as the input routing flow of the Dijkstra algorithm;
step four: determining SRLA algorithm parameters
Determining parameters, iteration orders and times which are suitable for an SRLA algorithm, triggering the frequency of the SRLA, and time interval T;
step five: calculating link criticality
Calculating link criticality based on the link capacity matrix;
step six: minimizing network criticality
Mapping the value of the link criticality to the link weight, minimizing the network criticality and realizing the most robust network;
step seven: obtaining an optimal routing path by the network link weight matrix;
the appropriate routing path is selected by the network link weight matrix using Dijkstra's algorithm.
The first step is to calculate the link utilization rate, and the specific process is as follows:
the cloud computing backbone network is modeled as G (V, E, W), where V is a set of nodes, E is a set of links, and W represents a link weight matrix of the network. In the model, the link states are defined as follows:
Figure FDA0002235691740000011
wherein x is ij∈{0,1}，L ijE represents a link from node i to node j;
the link energy consumption comprises a base energy consumption And energy consumption related to flow
Figure FDA0002235691740000013
The basic energy consumption means that the constant energy consumption of the operation link is guaranteed to be expressed as:
Figure FDA0002235691740000014
wherein,
Figure FDA0002235691740000015
represents a link L ijBasic energy consumption of c ijRepresenting the link capacity, δ is a basic energy related parameter, β represents the ratio of the link's energy consumption to its capacity, and the traffic-related energy consumption is:
Figure FDA0002235691740000021
wherein f is ij(t) denotes a pass-through link L ijThe flow rate of (a);
Figure FDA0002235691740000022
representing the relationship between link energy consumption and the traffic energy consumption carried by it;
link L ijThe energy consumption of (a) is modeled as:
Figure FDA0002235691740000023
link L in T period ijAverage energy efficiency of Can be expressed as:
Figure FDA0002235691740000025
only the dormancy of redundant links of the network is considered in the network and does not involve the shutdown of network nodes. Thus, the energy efficiency of the entire network Can be expressed as:
Figure FDA0002235691740000027
wherein N is sRepresenting a source node, N dRepresenting a destination node, fl sd(t) denotes a slave source node N sE.g. V to destination node N dInstantaneous flow, x, over e V ijIndicating the state of the link, N iRepresenting a node, p 0Representing the power of nodes in the network, set to a constant value,
Figure FDA0002235691740000028
representing a node N sTo node N dAverage flow rate of L ijRepresents a link from node i to node j, V represents a set of nodes, and E represents a set of links;
L ijthe link utilization of (a) is:
Figure FDA0002235691740000029
wherein,
Figure FDA00022356917400000210
indicating that the link is from L ijAverage flow rate of above; c. C ijRepresents the link capacity;
after T time interval, u ijFor link utilization as:
Figure FDA0002235691740000031
wherein,
Figure FDA0002235691740000032
indicating the average utilization of the initial link upon user request,
Figure FDA0002235691740000033
representing the average utilization of the link.
2. The robust energy efficiency routing method for the teaching cloud computing network as claimed in claim 1, wherein the specific method in the second step is as follows:
modeling a backbone network of cloud computing as G (V, E, W), wherein V is a node set, E is a link set, N and L are cardinality of the sets V and E respectively, and W represents a link weight matrix of the network; calculating a shortest path tree SPT (v) of each router node by a Dijkstra algorithm, wherein v represents the router nodes in the network; set of active links E ADefined as the set of links E involved in the shortest spanning tree A＝U v∈VSPT(v)，U v∈VRepresents a complete subgraph of diagram G; after a shortest path tree SPT (v) of each router node in a network model of cloud computing is obtained, a degree-out mechanism and a degree-in mechanism are utilized to carry out loop iteration to obtain a modified path tree, wherein the degree-out mechanism is to find a degree-out router node ER with the maximum degree in the network; routing router node IR among the ER's neighbors, computing the shortest path trees of ER and IR, comparing the shortest path trees of ER and IR to generate a modified path tree; and finally, comparing the MPT with the SPT to obtain a redundant link and converting the redundant link into a dormant state, and repeating the steps to realize the SRLA algorithm.
3. The robust energy-efficient routing method for educational cloud computing network according to claim 1, wherein the step three of establishing the REERA model:
Figure FDA0002235691740000034
s.t.
Figure FDA0002235691740000035
connection(N s,N d)＝1 (9b)
Figure FDA0002235691740000036
Figure FDA0002235691740000037
Figure FDA0002235691740000038
equation (9a) represents a cost function that maximizes the energy efficiency of the network; equation (9b) shows that any traction node is always connected and the traffic between any two nodes is non-negative; equation (9c) indicates that the link weight is used as the link cost when constructing the route; equation (9d) means link L ijIs equal to the load across link L ijThe sum of the flow rates of all the OD streams; equation (9e) indicates that the link utilization is not greater than the link capacity; costl ijRepresents a link l ijOverhead of traffic of w ijA link weight value indicating the end of the request, representing (s, d) passing through the link l ijFlow rate of (c) ijRepresents a link l ijThe capacity of (c).
4. The robust energy efficiency routing method oriented to the teaching cloud computing network according to claim 1, wherein the fourth step determines parameters of the SRLA algorithm, and the specific process is as follows:
in order to maximize network energy efficiency, the number of iterations is set to 3, then the frequency of triggering the SRLA is determined, the time interval is set to T, the effect of the time interval T can be offset in the energy efficiency calculation process, and most user requests can be responded within a time interval.
5. The robust energy efficiency routing method oriented to the teaching cloud computing network as claimed in claim 1, wherein the link criticality is calculated in the fifth step, and the specific process is as follows:
the smaller the criticality of the network is, the stronger the robustness of the network is; therefore, the criticality τ of the network is:
τ＝2nTr(L +) (10)
where n is the number of network nodes, Tr (-) represents the matrix trajectory,
Figure FDA0002235691740000042
is the Moore-Penrose inverse of Laplace matrix L; in equation (6), the criticality τ of the network represents the sum of the resistive distances between all two nodes;
defining a linear relationship between link capacity and initial link weight value, i.e. c ij＝k·w oij+ a, where the parameters k and a are constants, w oijRepresenting an initial value of link weight, and calculating link criticality based on a link capacity matrix; the normalized form of the network criticality τ is expressed as:
Figure FDA0002235691740000043
the formula for calculating the criticality of the network is as follows:
Figure FDA0002235691740000044
d＝diag(c 1,c 2,…c n) (12b)
L c＝d-W (12c)
wherein, A (r) represents the set of active nodes, and W represents the link weight matrix; equation (12a) represents the degree of fanout, c, of node r rjRepresents the link capacity from node r to node j; equation (12b) represents a matrix constructed from diagonal vectors of the link capacity matrix; equation (12c) represents a new matrix consisting of a diagonal vector matrix and a weight matrix of link capacities; equation (12d) represents how to compute the normalized network criticality.
6. The robust energy efficiency routing method for the teaching cloud computing network as claimed in claim 1, wherein the network criticality is minimized in the sixth step, and the specific process is as follows:
due to the relationship between the network criticality and robustness, the objective equation for implementing the most robust network is:
Min τ (13a)
s.t.
∑ (i,j)∈Lw ij≤c ij,c ijis fixed (13b)
0≤w ij≤c ij(13c)
wherein, c ijIs a link capacity matrix; w is a ijIs a link L ijWeights, which can obtain reasonable network link weight values by optimizing the routing algorithm, thereby improving the robustness of the whole network, equation (13a) represents an objective function, and equations (13b) and (13c) represent limits;
equation (10) indicates that the criticality τ of the network is a network-wide measure and can be used to describe network robustness, the smaller the criticality τ of the network, the more robust the network is; equation (13a) represents an objective function that minimizes the criticality τ of the network, the second and third equations showing the constraints satisfied by the weight of each link; equation (13) represents that by minimizing the criticality τ of the network, the optimal link weight satisfying a plurality of constraints is found, and a robust route is constructed;
equation (12) indicates that when the bandwidth capacity of a link changes, the criticality of the link also changes, and for a high-load link, the influence on the whole network in the routing process is large; thus, the value of link criticality is mapped to the link weight, which is updated as the bandwidth capacity of the network link decreases by the following formula:
τ＝n(n-1)τ′ (14a)
Δτ＝τ-τ 0(14b)
w ij＝b·Δτ+w 0ij(14c)
an initial network criticality value for a time interval T; τ is the network criticality value at the end of time T, τ 0Representing an initial network criticality within a particular time interval T; b is a constant, which is based on a simulation of a real network; n is the number of network nodes; w is a 0ijIs the initial link weight value, w, of time T ijIs the link weight value at the end of time interval T; equation (14a) represents the relationship between the criticality of the network and its normalized value; equation (14b) represents a change in the criticality value of the network; equation (14c) characterizes the relationship between the change in the criticality of the network and the link weight value.
CN201910982647.1A 2019-10-16 2019-10-16 A Robust Energy Efficient Routing Method for Teaching Cloud Computing Networks Expired - Fee Related CN110784405B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201910982647.1A CN110784405B (en) 2019-10-16 2019-10-16 A Robust Energy Efficient Routing Method for Teaching Cloud Computing Networks

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201910982647.1A CN110784405B (en) 2019-10-16 2019-10-16 A Robust Energy Efficient Routing Method for Teaching Cloud Computing Networks

Publications (2)

Publication Number Publication Date
CN110784405A true CN110784405A (en) 2020-02-11
CN110784405B CN110784405B (en) 2021-11-02

Family

ID=69385544

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201910982647.1A Expired - Fee Related CN110784405B (en) 2019-10-16 2019-10-16 A Robust Energy Efficient Routing Method for Teaching Cloud Computing Networks

Country Status (1)

Country Link
CN (1) CN110784405B (en)

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7593341B1 (en) * 2006-06-08 2009-09-22 At&T Corp. Method and apparatus for updating a shortest path graph
CN105323166A (en) * 2015-11-17 2016-02-10 东北大学 Cloud computing-oriented routing method based on network efficiency priority
CN105337861A (en) * 2015-11-18 2016-02-17 东北大学 Routing method based on energy efficiency priority and cognitive theory

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7593341B1 (en) * 2006-06-08 2009-09-22 At&T Corp. Method and apparatus for updating a shortest path graph
CN105323166A (en) * 2015-11-17 2016-02-10 东北大学 Cloud computing-oriented routing method based on network efficiency priority
CN105337861A (en) * 2015-11-18 2016-02-17 东北大学 Routing method based on energy efficiency priority and cognitive theory

Also Published As

Publication number Publication date
CN110784405B (en) 2021-11-02

Similar Documents

Publication Publication Date Title
CN113490254A (en) VNF migration method based on bidirectional GRU resource demand prediction in federal learning
CN103412635B (en) Data center's power-economizing method and device
CN106936645B (en) Optimization Method of Tree Network Topology Structure Based on Queuing Theory
CN103685011B (en) A kind of method and apparatus for determining energy-efficient routing
CN113992259A (en) Method for constructing time slot resource expansion diagram
CN105550159A (en) Power distributing method for network-on-chip of multi-core processor
CN112153715B (en) Hybrid big data transmission topological structure method, system, storage medium and application
CN106095529A (en) A kind of carrier wave emigration method under C RAN framework
CN114785692A (en) Virtual power plant aggregation regulation and control communication network flow balancing method and device
Nace et al. Computing optimal max-min fair resource allocation for elastic flows
CN108173760A (en) A Network-on-Chip Mapping Method Based on Improved Simulated Annealing Algorithm
CN116418694B (en) A service function chain deployment method and system based on deep reinforcement learning algorithm
CN117979370A (en) A method and system for optimizing dynamic slicing of power heterogeneous network resources
CN120371531B (en) A computing power scheduling system and method for a computing power network
CN106230737A (en) A kind of software definition network-building method of state aware
CN111404815A (en) Constrained routing method based on deep learning
CN112601232B (en) Multi-service migration method and system based on load balancing with minimum cost and maximum flow
CN103916266B (en) A kind of energy-efficient virtual network mapping algorithm of active dormancy node and link
CN107528731B (en) Network segmentation optimization algorithm applied to NS3 parallel simulation
CN115016889A (en) A virtual machine optimization scheduling method for cloud computing
CN110784405A (en) Robust energy efficiency routing method for teaching cloud computing network
Yue et al. A deep learning-based virtual network function placement approach in nfv-enabled networks
CN105956937B (en) Data center solving method for small interference stability analysis of power system
Goudarzi et al. A GA-based fuzzy rate allocation algorithm
Qian et al. Dram: Dragonfly routing algorithm on multi-objects by optimal thresholds

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20211102