ENERGY-EFFICIENT TRAFFIC SCHEDULING ALGORITHM FOR SDN DATA CENTER NETWORK BASED ON MULTI-LAYER VIRTUAL TOPOLOGY
20210111994 · 2021-04-15
Inventors
Cpc classification
H04L41/122
ELECTRICITY
International classification
Abstract
An energy-efficient traffic scheduling algorithm based on multiple layers of virtual sub-topologies is provided. First, a mathematical optimization model for an energy-efficient traffic scheduling problem is established, to minimize network energy consumption while ensuring the capability of bearing all network data flows. Then, the mathematical optimization model is resolved using an energy-efficient traffic scheduling algorithm based on a multi-layer virtual topology, to obtain an energy-efficient scheduling scheme of the data flows. The virtual topology and switch ports in an upper layer are made dormant to save energy. The method can dynamically adjust the working state of the virtual sub-topology in the upper layer according to current link utilization. A path with a minimum number of hops and lowest maximum link utilization can be found in the booted sub-topology, to route the data flow, solving the problem that a “rich-connection” data center network has low energy resource utilization at low load.
Claims
1. An energy-efficient network traffic scheduling algorithm for a Software Defined Networking (SDN) data center based on a multi-layer virtual topology, comprising the following steps: S1: establishing an integer linear programming (ILP) mathematical optimization model for an energy-efficient traffic scheduling problem, wherein an objective function is to minimize network energy consumption, and conditions to be satisfied comprise a link bandwidth constraint condition and a flow conservation constraint condition, and then resolving the model by using an energy-efficient traffic scheduling algorithm; S2: in an initialization stage of the energy-efficient scheduling algorithm, dividing, by an SDN controller, a collected topological structure of a data center network into multiple layers of virtual topologies, and booting a first-layer virtual topology while putting other higher-layer virtual topological structures to dormancy; S3: first calculating, by the SDN controller, maximum link utilization u.sub.l for a data flow that newly arrives at the network, and determining to boot or turn off the virtual topology in an upper layer according to a value of the maximum link utilization; and S4: selecting, by the controller, a suitable path from a K-shortest path set in the currently booted virtual topology, to route the data flow.
2. The energy-efficient traffic scheduling algorithm for an SDN data center network based on a multi-layer virtual topology according to claim 1, wherein the ILP mathematical optimization model in step S1 comprises minimizing the network energy consumption while bearing all network load, and the objective function is as follows:
min COS
+Σ.sub.vϵVCOST.sub.vy.sub.v wherein G(V, L) represents a data center network, L represents a data link set,
represents any link, V represents a set of switch nodes, v represents any switch node, COS
represents energy consumption of any link
, COST.sub.v represents energy consumption of the switch node v, x.sub.l and y.sub.v represent a link state and a switch state respectively, 0 represents turning off, and 1 represents booting.
3. The energy-efficient traffic scheduling algorithm for an SDN data center network based on a multi-layer virtual topology according to claim 2, wherein the link bandwidth constraint condition of the ILP mathematical optimization model in step S1 is:
Σ.sub.f∈Fb.sub.fz.sub.f.sup.l≤c.sub.lx.sub.l wherein F represents a set of data flows borne by the data center network, f represents a data flow, b.sub.f represents a bandwidth of the data flow, c.sub.l represents a link bandwidth, represents a state of the data flow f borne by the link
, 0 represents the data flow is not borne, and 1 represents that the data flow is borne.
4. The energy-efficient traffic scheduling algorithm for an SDN data center network based on a multi-layer virtual topology according to claim 3, wherein the flow conservation constraint condition of the ILP mathematical optimization model in step S1 is:
5. The energy-efficient traffic scheduling algorithm for an SDN data center network based on a multi-layer virtual topology according to claim 1, wherein the division into the multiple layers of virtual topologies in step S2 specifically comprises the following steps: S21: collecting, by the SDN controller, topology information of the data center network by using an address resolution protocol (ARP); S22: generating, by using a minimum spanning tree algorithm, a plurality of independent minimum spanning trees with core switches as root nodes according to the number n of the core switches; and storing the core switch and links in each minimum spanning tree into a Gi(Vi, Li); S23: selecting G0 as a first-layer virtual topology, VG1=(V0, L0); S24: combining the first-layer virtual topology VG1 with G1 to form a second-layer virtual topology VG2, wherein a forming method is defined as follows: a) a node set of VG2 is defined as V.sub.0∪V.sub.1−V.sub.0; and b) a link set of VG2 is defined as L.sub.0∪L.sub.1−L.sub.0; S25: combining the second-layer virtual topology VG2 with G2 to form a third-layer virtual topology VG3, and so on, to sequentially form higher-layer topologies; and S26: booting the first-layer virtual topology VG1, that is, booting switches in the first-layer virtual topology VG1 and setting all the links to a working state, and rendering the links in green; setting all switches and links in other higher-layer topologies to a dormant state, and rendering all the links in red.
6. The energy-efficient traffic scheduling algorithm for an SDN data center network based on a multi-layer virtual topology according to claim 1, wherein step S3 specifically comprises the following steps: S31: if the maximum link utilization >threshold 1, pre-booting the virtual topology in the upper layer, and rendering all the links therein in yellow; otherwise, going to step 34; S32: if the maximum link utilization
>threshold 2, booting the virtual topology in the upper layer, and rendering all the links therein in green; otherwise, going to step 34; S33: if the virtual topology in the upper layer is pre-booted/booted, putting ports with no connected links in the newly booted switches to dormancy; S34: selecting a path from K-shortest paths, so that all links on the path are green and the maximum link utilization
is smallest, and routing the data flow on the path; and S35: collecting and calculating the maximum link utilization u.sub.l, and if duration in which
is less than the threshold 1 is longer than T and the topology in the upper layer has been booted, putting the upper layer to dormancy after transfer of the data flow is finished, that is, putting the switches to dormancy and rendering all the links in red.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
[0041]
[0042]
[0043]
[0044]
[0045]
[0046]
DETAILED DESCRIPTION
[0047] To help a person of ordinary skill in the art better understand the technical solution of the present invention, the technical solution of the present invention is further described with reference to the embodiments.
[0048] In this embodiment, an energy-efficient traffic scheduling algorithm based on multiple layers of virtual sub-topologies (EMV-SDN) is implemented in an SDN data center network with a Fat-Tree topology. First, a mathematical optimization model for an energy-efficient traffic scheduling problem is established, to minimize network energy consumption while ensuring the capability of bearing all network data flows. Then, the mathematical optimization model is resolved using an energy-efficient traffic scheduling algorithm based on a multi-layer virtual topology, to obtain an energy-efficient scheduling scheme of the data flows. The virtual topology and switch ports in an upper layer are made dormant to save energy.
[0049] This embodiment includes the following steps:
[0050] S1: establish an integer linear programming (ILP) mathematical optimization model for an energy-efficient traffic scheduling problem, where an objective function is to minimize network energy consumption, and conditions to be satisfied include a link bandwidth constraint condition and a flow conservation constraint condition, and then resolve the model by using an energy-efficient traffic scheduling algorithm.
[0051] S2: in an initialization stage of the energy-efficient scheduling algorithm, an SDN controller divides a collected topological structure of a data center network into multiple layers of virtual topologies, and boots a first-layer virtual topology while putting other higher-layer virtual topological structures to dormancy.
[0052] S3: the SDN controller first calculates maximum link utilization u.sub.l for a data flow that newly arrives at the network, and determines to boot or turn off the virtual topology in an upper layer according to a value of the maximum link utilization.
[0053] S4: the controller selects a suitable path from a K-shortest path set in the currently booted virtual topology, to route the data flow.
[0054] The integer linear programming (ILP) mathematical optimization model in step S1 is specifically as follows:
[0055] Total energy consumption of the data center network is defined as energy consumption of all active (working-state) switches and links in the network.
[0056] Graph G(V, L) represents a data center network, where L is a data link set, and a capacity of a link is c.sub.l. V is a set of switch nodes, and v represents any switch node. L.sub.v represents a set of links connected to the switch v, L.sub.v′ represents a set of incoming links of the node, and L.sub.v″ represents a set of all outgoing links. A set of data flows borne by the data center network is denoted by F, and for any data flow, its source, destination and bandwidth are denoted by v.sub.f.sup.s, v.sub.f.sup.d, and b.sub.f respectively. COS
represents energy consumption of any link
, and is energy consumption of two endpoints (that is, switch ports) of the link. COST.sub.v represents energy consumption of the switch node v, and refers to energy consumption of a rack and a line card of the switch. x.sub.l, y.sub.v and
represent decision variables, x.sub.l indicates whether the link
is in an active state, y.sub.v indicates whether the switch is in a working state, and
indicates whether the link l bears a data flow f.
[0057] Formula (1) is the objective function, which is to minimize the total energy consumption of the data center network.
[0058] Formula (2) is the link bandwidth constraint condition. It indicates that a total bandwidth of data flows that can be borne by any active link should not exceed a total bandwidth of the link, and a link in a dormant state cannot bear any data flow.
[0059] Formula (3) is the flow conservation constraint condition. For any data flow f, if the node v is a source node of the data flow, the node only has an outgoing data flow; if v is a destination node of the data flow, the node only has an incoming data flow; otherwise, for any intermediate node v, an incoming data flow is the same as an outgoing data flow.
[0060] Formula (4) indicates that for any switch node v, if v is in a dormant state, all links connected to the node are in a dormant state.
[0061] Formula (5) means that if all links connected to the switch node v are in a dormant state, the switch v may be set to a dormant state.
[0062] Formula (6) illustrates value ranges of the variables.
[0063] To resolve the mathematical optimization model established above, the present invention provides an energy-efficient traffic scheduling algorithm based on a multi-layer virtual topology (MVE-SDN) for the SDN data center network. In this algorithm, the topology of the data center network is first divided into multiple layers of virtual topologies, and a first-layer virtual topology is booted. Then, for a data flow that newly arrives, it is determined whether to boot or turn off the topology in an upper layer according to maximum link utilization of the virtual topology in the current layer. Finally, a path is computed by using an improved greedy algorithm to schedule the data flow.
[0064] Referring to
[0065] The division into the multiple layers of virtual sub-topologies in step S2 specifically includes the following steps:
[0066] S21: the SDN controller collects topology information of the data center network by using an address resolution protocol (ARP).
[0067] S22: generate, by using a minimum spanning tree algorithm (kruskal algorithm), a plurality of independent minimum spanning trees MSTi (i=0, 1, 2 . . . , n) with core switches as root nodes according to the number n of the core switches; and store the core switch and links in each MSTi into a graph Gi(Vi, Li) (i=0, 1, 2 . . . , n).
[0068] S23: select G0 as a first-layer virtual topology VG1=(V0, L0).
[0069] S24: combine the first-layer virtual topology VG1 with G1 to form a second-layer virtual topology VG2, where a forming method is defined as follows:
[0070] a) a node set of VG2 is defined as V.sub.0∪V.sub.1−V.sub.0; and
[0071] b) a link set of VG2 is defined as L.sub.0∪L.sub.1−L.sub.0.
[0072] S25: combine the second-layer virtual topology VG2 with G2 to form a third-layer virtual topology VG3, and so on, to sequentially form higher-layer topologies, where the forming method is described above. For the Fat-Tree topological structure, each MSTi is unique, and a top-layer topology formed after combination is the original physical topology.
[0073] S26: boot the first-layer virtual topology VG1, that is, boot switches in the first-layer virtual topology VG1 and set all the links to a working state, and render the links in green; and set all switches and links in other higher-layer topologies to a dormant state, and render all the links in red.
[0074] The higher-layer virtual topologies are sequentially formed by using the foregoing method to achieve the following objectives: first, when the virtual topology in an upper layer, such as VG2, is to be booted, it is only necessary to boot dormant nodes and links, without repeatedly booting the nodes and links in VG1; moreover, when the virtual topology in an upper layer, such as VG2, is to be turned off, it is only necessary to turn off the exclusive nodes and links thereof. This not only simplifies the operation but also saves the storage space of the topological structure.
[0075] When the mathematical model is resolved by using the energy-efficient traffic scheduling algorithm, step S3 of calculating maximum link utilization u.sub.l for a data flow that newly arrives at the network, and determining whether to boot the topology in an upper layer according to a value of the maximum link utilization specifically includes the following steps:
[0076] S31: if >threshold 1, pre-boot the virtual topology in the upper layer, and render all the links therein in yellow; otherwise, go to step 34.
[0077] S32: if >threshold 2, boot the virtual topology in the upper layer, and render all the links therein in green; otherwise, go to step 34.
[0078] S33: if the virtual topology in the upper layer is pre-booted/booted, put ports with no connected links in the newly booted switches to dormancy.
[0079] S34: select a path from K-shortest paths, so that all links on the path are green and the maximum link utilization is smallest, and route the data flow on the path.
[0080] S35: collect and calculate the maximum link utilization u.sub.l, and if duration in which u.sub.l is less than the threshold 1 is longer than T and the topology in the upper layer has been booted, put the upper layer to dormancy after transfer of the data flow is finished, that is, put the switches to dormancy and render all the links in red.
[0081] Simulation Experiments:
[0082] To check the performance of the proposed energy-efficient traffic algorithm based on a multi-layer virtual topology (EMV-SDN), a data center network topology of a Fat-tree type is built by using a Floodlight controller and a Mininet simulation platform.
[0083] An energy consumption ratio and an average completion time of a data flow are used as indicators for measuring the performance of the algorithm.
[0084] The energy consumption ratio is calculated by using the following formula
[0085] where COST.sub.e is energy consumption when the energy-efficient scheduling algorithm is adopted, and COST.sub.0 is energy consumption without any energy-saving measures. As can be learned, for different energy-efficient scheduling algorithms, a lower energy consumption ratio indicates a better energy-saving effect of the algorithm.
[0086] In the multi-layer virtual topology, the proposed EMV-SDN is compared with the ECMP algorithm and the Dijkstra shortest path algorithm. Experiment results show that the EMV-SDN outperforms other two algorithms in terms of the energy consumption ratio, the average completion time and the like.
[0087] 1. Experiment Settings
[0088] 1.1 Network Topology
[0089] A Fat-tree network topology with k=4, as shown in
[0090] 1.2 Traffic Mode
[0091] The tool software Iperf is selected to generate a data flow in the data center network. Each host generates a flow with a different length at a different time. The lengths of the data flows comply with the exponential distribution, and the generation times of the flows comply with the Poisson distribution. A destination node of the data flow is determined by using a Random mode, a Staggered mode, and a Stride mode respectively.
[0092] (1) Random: a host i sends data to a host j randomly at an equal probability p.
[0093] (2) Staggered (p.sub.e, p.sub.p): a host i sends data to an upper-layer edge switch of the same pod at a probability of p.sub.e, sends data to a host of the same pod at a probability of p.sub.p, and sends data to hosts of other pods at a probability of 1−(p.sub.e+p.sub.p).
[0094] (3) Stride (x): a host i sends data to hosts (i+x)mod n, where n is the total number of hosts in the data center network.
[0095] 1.3 Switch Energy Consumption
[0096] Energy consumption of a switch includes energy consumption of components such as a rack, a line card, and ports. Components in different types of switches have different energy consumption. Table 1 shows energy consumption data of components in different types of switches.
TABLE-US-00001 TABLE 1 Energy consumption of switch components (unit: watt) Rack & All ports All ports Switch type Port Line booted booted Edge switch 0.90 135 178 183 Core switch 1.19 176 233 239
[0097] 2. Comparison of Energy Consumption Ratios
[0098] In the foregoing three traffic modes, the energy consumption ratio of the EMV-SDN algorithm is compared with those of the ECMP and Dijkstra algorithms. Multiple experiments are carried out, and each experiment lasts about 30 minutes. The energy consumption of the data center network is calculated by taking the 10 minutes in the middle.
[0099] 2.1 Random Traffic Mode
[0100]
[0101] 2.2 Staggered Mode
[0102] In the Staggered mode, values of p.sub.e and p.sub.p are 0 and 0.2 respectively.
[0103] 2.3 Stride Mode
[0104] In the Stride mode, the value is set to 6.
[0105] It can be learned from
[0106] 3. Comparison of Average Completion Times
[0107]
[0108] To solve the problem that a “rich-connection” data center network has low energy resource utilization at low load, the present invention provides an energy-efficient traffic scheduling mechanism for an SDN data center network of a Fat-Tree type. First, an integer linear programming (ILP) mathematical optimization model for an energy-efficient traffic scheduling problem is established. Then, the mathematical model is resolved using an energy-efficient traffic scheduling algorithm based on a multi-layer virtual topology, to obtain an energy-efficient data flow scheduling path. Idle network switch devices and ports are made dormant to achieve the objective of reducing the total energy consumption of the data center. Simulation experiment results show that the proposed energy-efficient traffic scheduling mechanism based on the multi-layer virtual topology (EMV-SDN) is better than the ECMP algorithm and the Dijstra shortest path algorithm. In three different communication modes, EMV-SDN outperforms the other two algorithms in terms of the energy consumption ratio and the average completion time.
[0109] The basic principles, main features, and advantages of the present invention are shown and described above. It should be understood by those skilled in the art that, the present invention is not limited by the aforementioned embodiments. The aforementioned embodiments and the description only illustrate the principle of the present invention. Various changes and modifications may be made to the present invention without departing from the spirit and scope of the present invention. Such changes and modifications all fall within the claimed scope of the present invention. The protection scope of the present invention is defined by the appended claims and their equivalents.