Energy-efficient traffic scheduling algorithm for SDN data center network based on multi-layer virtual topology

11057300 ยท 2021-07-06

Assignee

Inventors

Cpc classification

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 custom characterCOScustom character+.sub.vVCOST.sub.vy.sub.v wherein G(V, L) represents a data center network, L represents a data link set, custom character represents any link, V represents a set of switch nodes, v represents any switch node, COScustom character represents energy consumption of any link custom character, 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.fFb.sub.fz.sub.f.sup.lc.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, custom character represents a state of the data flow f borne by the link custom character, 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: .Math. L b f z f - .Math. L b f z f = { - b f v = v f s , f F b f v = v f d , f F 0 v v - { v f s , v f d } , f F wherein L.sub.v represents a set of links connected to a switch v, L.sub.v represents a set of incoming links of the node, L.sub.v represents a set of all outgoing links, and v.sub.f.sup.s and v.sub.f.sup.d represent a source and a destination of any data flow.

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.0V.sub.1V.sub.0; and b) a link set of VG2 is defined as L.sub.0L.sub.1L.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 custom character>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 custom character>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 custom character 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 custom character 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

(1) FIG. 1 is a flowchart of an energy-efficient traffic scheduling algorithm according to the present invention;

(2) FIG. 2 shows a Fat-Tree topological structure according to the present invention;

(3) FIG. 3 shows energy consumption ratios in a Random mode in simulation experiments according to the present invention;

(4) FIG. 4 shows energy consumption ratios in a Staggered mode in simulation experiments according to the present invention;

(5) FIG. 5 shows energy consumption ratios in a Stride mode in simulation experiments according to the present invention; and

(6) FIG. 6 shows completion time ratios of algorithms in different communication modes in simulation experiments according to the present invention.

DETAILED DESCRIPTION

(7) 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.

(8) 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.

(9) This embodiment includes the following steps:

(10) 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.

(11) 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.

(12) 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.

(13) S4: the controller selects a suitable path from a K-shortest path set in the currently booted virtual topology, to route the data flow.

(14) The integer linear programming (ILP) mathematical optimization model in step S1 is specifically as follows:

(15) min .Math. L COST �� + .Math. v V COST v y v ( 1 ) .Math. f F b f z f c x L ( 2 ) .Math. L b f z f - .Math. L b f z f = { - b f v = v f s , f F b f v = v f d , f F 0 v v - { { v f s , v f d } , f F ( 3 ) x y v v V , L v ( 4 ) y v .Math. L v x v V ( 5 ) x , y v , z f { 0 , 1 } f F , L , v V ( 6 )

(16) Total energy consumption of the data center network is defined as energy consumption of all active (working-state) switches and links in the network.

(17) Graph G(V, L) represents a data center network, where L is a data link set, and a capacity of a link custom character 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. COScustom character represents energy consumption of any link custom character, 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 custom character represent decision variables, x.sub.l indicates whether the link custom character is in an active state, y.sub.v indicates whether the switch is in a working state, and custom character indicates whether the link l bears a data flow f.

(18) Formula (1) is the objective function, which is to minimize the total energy consumption of the data center network.

(19) 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.

(20) 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.

(21) 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.

(22) 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.

(23) Formula (6) illustrates value ranges of the variables.

(24) 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.

(25) Referring to FIG. 1, in the initialization stage of the energy-efficient scheduling algorithm, a set of K-shortest paths between any two terminal nodes is calculated according to the topological structure of the data center network, and the physical topology is divided into multiple layers of virtual sub-topologies (that is, multiple layers of virtual sub-topologies such as a first layer, a second layer, and a third layer). The first-layer virtual topological structure is booted, and other higher-layer virtual topological structures are made dormant. For a data flow that newly arrives at the network, the maximum link utilization u.sub.l is calculated first, and it is determined, according to the value of the maximum link utilization, whether to boot the topology in the upper layer. Then, a suitable path is selected from the K-shortest path set in the currently booted virtual topology, to route the data flow.

(26) The division into the multiple layers of virtual sub-topologies in step S2 specifically includes the following steps:

(27) S21: the SDN controller collects topology information of the data center network by using an address resolution protocol (ARP).

(28) 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).

(29) S23: select G0 as a first-layer virtual topology VG1=(V0, L0).

(30) 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:

(31) a) a node set of VG2 is defined as V.sub.0V.sub.1V.sub.0; and

(32) b) a link set of VG2 is defined as L.sub.0L.sub.1L.sub.0.

(33) 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.

(34) 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.

(35) 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.

(36) 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:

(37) S31: if custom character>threshold 1, pre-boot the virtual topology in the upper layer, and render all the links therein in yellow; otherwise, go to step 34.

(38) S32: if custom character>threshold 2, boot the virtual topology in the upper layer, and render all the links therein in green; otherwise, go to step 34.

(39) 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.

(40) 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.

(41) 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.

(42) Simulation Experiments:

(43) 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.

(44) An energy consumption ratio and an average completion time of a data flow are used as indicators for measuring the performance of the algorithm.

(45) The energy consumption ratio is calculated by using the following formula

(46) Energy consumption ratio = COST e COST 0 ( 7 )

(47) 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.

(48) 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.

(49) 1. Experiment Settings

(50) 1.1 Network Topology

(51) A Fat-tree network topology with k=4, as shown in FIG. 2, is selected, and simulation experiments are carried out in the Mininet platform. All switches are OpenFlow switches with 48 ports, and each link has a bandwidth of 100 Mb/s.

(52) 1.2 Traffic Mode

(53) 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.

(54) (1) Random: a host i sends data to a host j randomly at an equal probability p.

(55) (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).

(56) (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.

(57) 1.3 Switch Energy Consumption

(58) 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.

(59) 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

(60) 2. Comparison of Energy Consumption Ratios

(61) 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. FIG. 3 to FIG. 5 show the comparison results of the three algorithms in the three traffic modes, where the abscissa represents the experiment duration, and the ordinate represents the energy consumption ratio of the data center network. The solid line in the figure represents the energy consumption ratio when the EMV-SDN is adopted, and the dashed line and dotted line represent the energy consumption ratio when the ECMP algorithm and the Dijkstra algorithm are adopted respectively.

(62) 2.1 Random Traffic Mode

(63) FIG. 3 shows a comparison result of the energy consumption ratios of the three algorithms in the Random mode. As can be learned from the figure, compared with the ECMP algorithm, the EMV-SDN algorithm reduces the energy consumption ratio by 1.5% to 7.81%, and the energy consumption ratio is reduced by 2.25% on average. Compared with the Dijkstra algorithm, the EMV-SDN algorithm reduces the energy consumption ratio by 0.75% to 42.92%, and the energy consumption ratio is reduced by 6.52% on average.

(64) 2.2 Staggered Mode

(65) In the Staggered mode, values of p.sub.e and p.sub.p are 0 and 0.2 respectively. FIG. 4 shows the energy consumption ratios of the three algorithms in the Staggered mode. As can be learned from the figure, compared with the ECMP algorithm, the EMV-SDN algorithm reduces the energy consumption ratio by 1.44% to 24.61%, and the energy consumption ratio is reduced by 2.52% on average. Compared with the Dijkstra algorithm, the EMV-SDN algorithm reduces the energy consumption ratio by 1.25% to 42.91%, and the energy consumption ratio is reduced by 6.65% on average.

(66) 2.3 Stride Mode

(67) In the Stride mode, the value is set to 6. FIG. 5 shows the energy consumption ratios of the three algorithms in the Stride mode. As can be learned from the figure, compared with the ECMP algorithm, the EMV-SDN algorithm reduces the energy consumption ratio by 0.75% to 24.62%, and the energy consumption ratio is reduced by 4.27% on average. Compared with the Dijkstra algorithm, the EMV-SDN algorithm reduces the energy consumption ratio by 0.63% to 42.89%, and the energy consumption ratio is reduced by 10.77% on average.

(68) It can be learned from FIG. 3 to FIG. 5 that, in the three communication modes, the proposed EMV-SDN algorithm has lower energy consumption than the ECMP algorithm and the Dijkstra algorithm, because in the EMV-SDN algorithm, the working state of the virtual sub-topology in the upper layer can be dynamically adjusted according to the current link utilization, thereby saving energy. In addition, in the EMV-SDN algorithm, 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. In the ECMP algorithm, the link state is not taken into consideration, and the flow is randomly scheduled to a shortest path, failing to adjust the path according to topological changes. The Dijkstra algorithm only calculates a shortest path, but cannot combine the link state and the link utilization desirably, which may cause links on the shortest path to be overcrowded. As a result, the virtual sub-topology in the upper layer is booted too early, causing the energy consumption to be higher than that of the other two algorithms.

(69) 3. Comparison of Average Completion Times

(70) FIG. 6 is a diagram showing average completion times of the three algorithms, namely, EMV-SDN, ECMP and Dijkstra. In the figure, the abscissa represents the three traffic modes, the ordinate represents the average completion time, and the data series respectively represent the average completion times of the three algorithms. As can be seen from the figure, the EMV-SDN algorithm has the shortest average completion time in the three communication modes. Compared with ECMP and Dijkstra, the energy-efficient scheduling algorithm EMV-SDN reduces the average completion time of the data flow by 22% and 40% respectively in the Random mode; in the Staggered mode, the average completion time is reduced by 14% and 31% respectively; in the Stride mode, the average completion time is reduced by 21% and 39% respectively. In terms of the average completion time, the EMV-SDN algorithm outperforms ECMP and Dijkstra, because in the EMV-SDN algorithm, a path can be calculated in time according to the link color and link utilization when the topological structure changes, to schedule the data flow, thereby reducing link congestion, so that the data flow can quickly reach the destination. In the ECMP algorithm, the link utilization is not taken into consideration in flow scheduling, and the traffic is randomly allocated to a shortest path, which may result in link congestion and delay the arrival time of the flow. In the Dijkstra algorithm, a shortest path is found to route the data flow, while the link utilization is not taken into consideration either. Moreover, the Dijkstra algorithm is not adaptive to changes of the network virtual topology. As a result, the data flow scheduled by using the Dijkstra algorithm has the longest average completion time.

(71) 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.

(72) 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.