CN117221126A - Network collaboration flow-oriented route scheduling method and system - Google Patents
Network collaboration flow-oriented route scheduling method and system Download PDFInfo
- Publication number
- CN117221126A CN117221126A CN202311487370.8A CN202311487370A CN117221126A CN 117221126 A CN117221126 A CN 117221126A CN 202311487370 A CN202311487370 A CN 202311487370A CN 117221126 A CN117221126 A CN 117221126A
- Authority
- CN
- China
- Prior art keywords
- coflow
- scheduling
- routing
- bandwidth allocation
- network
- 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
Links
- 238000000034 method Methods 0.000 title claims abstract description 41
- 230000005540 biological transmission Effects 0.000 claims description 19
- 238000004422 calculation algorithm Methods 0.000 claims description 15
- 238000013468 resource allocation Methods 0.000 claims description 8
- 238000006243 chemical reaction Methods 0.000 claims description 4
- 238000004590 computer program Methods 0.000 claims description 3
- 238000001914 filtration Methods 0.000 claims description 3
- 238000013461 design Methods 0.000 abstract description 3
- 238000012545 processing Methods 0.000 description 8
- 238000004891 communication Methods 0.000 description 7
- 238000010586 diagram Methods 0.000 description 6
- 238000004364 calculation method Methods 0.000 description 4
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 238000011160 research Methods 0.000 description 2
- 230000006978 adaptation Effects 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000000903 blocking effect Effects 0.000 description 1
- 238000007405 data analysis Methods 0.000 description 1
- 238000007418 data mining Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The application discloses a network collaborative flow-oriented route scheduling method and a network collaborative flow-oriented route scheduling system. The method is an online Coflow routing scheduling method, and can realize instant routing and bandwidth allocation of the Coflow under the condition of not needing any priori knowledge of the Coflow. Compared with the traditional Coflow scheduling work, the method and the system for scheduling the data center network, based on the actual start of the data center network, design of efficient and reasonable scheduling strategies by combining with the routing and bandwidth allocation of the Coflow, enable the scheduling strategies to be more accurate and practical, can be used for online real-time scenes, and achieve efficient scheduling of collaborative traffic in the data center network.
Description
Technical Field
The application belongs to the field of computer network traffic scheduling, and particularly relates to a routing scheduling method and system for network cooperative traffic.
Background
In modern data center networks, clustered computing applications serve diversified computing requirements, and are widely used in the fields of mass data processing, online data analysis, data mining, computing and the like due to good computing performance and lower hardware cost. The relationship of the computation and communication phases in a clustered computing application can be modeled as a Directed Acyclic Graph (DAG). For example, the Map and Reduce phases are typical of the computation phases in a Map-Reduce parallel computation model. The calculation phase depends on the output of the previous phase and cannot be started until all inputs are completed. The computation phase is represented as a point on the DAG graph, the communication phase is represented as a directed edge connecting nodes, and the data streams of the communication phase originate from different computation nodes and are interleaved on the communication device, i.e. a Coflow. In order to ensure the service quality, the computing node and the communication stage need to be completed within a certain time, and for a single communication stage, different Coflow scheduling strategies also result in different communication transmission times, so that the completion time of the whole computing task, namely the Coflow, is affected.
The research on the completion time of the Coflow is more, but in various specific scenes, the design of a proper Coflow scheduling scheme to optimize the completion time of the task has great difficulty. In a data center network, the Coflow scheduling scheme needs to consider the scheduling of different subflows in one Coflow at the same time, and also needs to consider the scheduling among different coflows, and the scheduling process needs to consider various factors such as the size of the data flow, the instantaneity of the scheduling strategy and the like. Thus, designing an optimized Coflow scheduling scheme has proven to be an NP-hard problem. Current research is mainly focused on two points: on one hand, the data center network is abstracted into a large-scale non-blocking switch, only the scheduling of Coflow on an inlet port and an outlet port of the switch is considered, however, the abstracting method is too simplified, links such as routing and bandwidth allocation are omitted, and the key factors influencing the overall scheduling time are also omitted; on the other hand, the existing method for scheduling the Coflow only considers the scheduling of the internal subflows of the Coflow or the scheduling of the flows between the Coflows, however, in practical application, the scheduling of the flows between the internal subflows of the Coflow and the Coflows exists at the same time, so that a method for simultaneously considering the scheduling of the flows between the internal subflows of the Coflows and the Coflows is needed to realize the efficient scheduling of the data center network Coflows.
Disclosure of Invention
The application aims at overcoming the defects of the prior art and provides a routing scheduling method and system for network cooperative traffic.
In order to achieve the above purpose, the present application provides a routing scheduling method for network cooperative traffic, which includes the following steps:
(1) Acquiring Coflow and sub-flow information thereof, and calculating and traversing a routing path between any two devices in a data center network;
(2) Taking the routing path between any two devices in the Coflow substream information and the data center network as input, and solving the approximate optimal solution of the routing and bandwidth allocation of the single Coflow internal substream through an approximate algorithm;
(3) Routing and bandwidth allocation are carried out on each Coflow internal sub-flow, residual available bandwidth on each routing path in the data center network is traversed, and routing and bandwidth allocation scheduling strategies of the updated Coflows are adjusted;
(4) When a certain Coflow transmission is completed or a new Coflow arrives, updating a routing and bandwidth allocation scheduling strategy of the Coflow;
(5) And converting the updated routing and bandwidth allocation scheduling policy into a scheduling policy executable by the SDN controller.
Further, in the step (1), a routing path between any two devices in the data center network is calculated and traversed through a breadth-first algorithm.
Further, the step (2) includes the following sub-steps:
(2.1) performing routing and bandwidth allocation of a single Coflow internal substream based on the Coflow substream information and a routing path between any two devices in a data center network;
(2.2) modeling the routing and bandwidth allocation problems of the internal substreams of the Coflow into a first integer programming problem, and constructing constraint conditions of the first integer programming problem, so as to minimize the transmission time of the Coflow;
and (2.3) solving an approximate optimal solution of single Coflow scheduling through an approximate algorithm based on the constraint condition of the first integer programming problem.
Further, in the substep (2.2), the constraint of the first integer programming problem comprises: each sub-stream is allocated to a candidate route path; the sum of sub-stream bandwidth allocation on any one routing path is smaller than the bandwidth capacity of the path; the transmission time of any one of the Coflow substreams is not longer than the total transmission time of the Coflow.
Further, the step (3) includes the following sub-steps:
(3.1) modeling the problems of computing resource allocation and bandwidth allocation among the Coflows into a second integer programming problem, and solving by an approximation algorithm to obtain an approximate optimal solution of the resource allocation;
(3.2) respectively carrying out routing and bandwidth allocation on all the Coflows which can be scheduled at the current moment, and obtaining a sub-flow scheduling approximate optimal solution of each Coflow;
(3.3) calculating the bandwidth adjustment coefficient of the routing path based on the sub-flow scheduling approximate optimal solution of each Coflow obtained in the sub-step (3.2), and counting the sum of the bandwidth allocation of the routing path and the residual available bandwidth thereof;
and (3.4) adjusting and updating the bandwidth allocation condition of the Coflow according to the bandwidth adjustment coefficient of the routing path to obtain the routing and bandwidth allocation scheduling strategy.
Further, in the substep (3.1), the constraint of the second integer programming problem comprises: the sum of the CPU core numbers distributed by all Coflow is not more than Q; the CPU core number allocated by any Coflow is a positive integer.
Further, the step (5) specifically comprises: after the updated routing and bandwidth allocation scheduling policy is converted into the scheduling policy executable by the SDN controller, the scheduling policy is input into the SDN controller, the SDN controller is converted into a routing table entry, and the converted routing table entry is sent to the data plane forwarding equipment to realize the scheduling of the network cooperative traffic.
In order to achieve the above object, the present application further provides a routing scheduling system for network cooperative traffic, including:
the single-Coflow sub-flow scheduling module is used for modeling the internal sub-flow scheduling problem of the Coflow into an integer programming problem, filtering the output after the problem is solved, and taking the filtered result as the input of the multi-Coflow scheduling module;
the planning solving module is used for solving the modeling problem of the single-Coflow sub-flow scheduling module, obtaining an approximate optimal solution through an approximate algorithm, and outputting an optimal routing path, bandwidth allocation and Coflow transmission time of the sub-flow;
the multi-Coflow scheduling module is used for proportionally adjusting the bandwidth allocation of each Coflow, and generating a routing path and a bandwidth allocation scheduling strategy;
and the scheduling policy conversion module is used for converting the routing path and the bandwidth allocation scheduling policy generated by the multi-Coflow scheduling module into the scheduling policy executable by the SDN controller.
To achieve the above object, the present application also provides an electronic device including a memory and a processor, the memory being coupled to the processor; the memory is used for storing program data, and the processor is used for executing the program data to realize the routing scheduling method for the network collaboration traffic.
To achieve the above object, the present application further provides a computer readable storage medium having a computer program stored thereon, the program when executed by a processor implementing the above-mentioned network-oriented cooperative traffic routing scheduling method.
Compared with the prior art, the application has the beneficial effects that: firstly, the application starts from the actual scene of the data center network, and takes the route of the forwarding equipment and the bandwidth of the link into the consideration category of the Coflow scheduling, thereby realizing the optimization of the Coflow scheduling of the whole link; secondly, the application solves the approximate optimal solution of the routing path and the bandwidth allocation of the subflow in the Coflow, considers the bandwidth competition among the Coflows and carries out the bandwidth allocation adjustment, thereby realizing the multi-granularity Coflow scheduling; finally, the method for scheduling the Coflow does not need to use any priori knowledge of the Coflow, can give a scheduling strategy when the Coflow arrives, meets the instantaneity requirement of the Coflow scheduling, and can be used as a method for scheduling the Coflow on-line of a data center network.
Drawings
In order to more clearly illustrate the technical solutions of the embodiments of the present application, the drawings that are needed in the description of the embodiments will be briefly described below, it being obvious that the drawings in the following description are only some embodiments of the present application, and that other drawings may be obtained according to these drawings without inventive effort to a person skilled in the art.
FIG. 1 is a flow chart of the method of the present application;
FIG. 2 is a schematic diagram of the present application;
FIG. 3 is a schematic diagram of a method for Coflow routing scheduling according to the present application;
FIG. 4 is a schematic diagram of a system of the present application;
fig. 5 is a schematic diagram of an electronic device.
Detailed Description
Reference will now be made in detail to exemplary embodiments, examples of which are illustrated in the accompanying drawings. When the following description refers to the accompanying drawings, the same numbers in different drawings refer to the same or similar elements, unless otherwise indicated. The implementations described in the following exemplary examples do not represent all implementations consistent with the application. Rather, they are merely examples of apparatus and methods consistent with aspects of the application as detailed in the accompanying claims.
The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the application. As used in this specification and the appended claims, the singular forms "a," "an," and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It should also be understood that the term "and/or" as used herein refers to and encompasses any or all possible combinations of one or more of the associated listed items.
It should be understood that although the terms first, second, third, etc. may be used herein to describe various information, these information should not be limited by these terms. These terms are only used to distinguish one type of information from another. For example, first information may also be referred to as second information, and similarly, second information may also be referred to as first information, without departing from the scope of the application. The word "if" as used herein may be interpreted as "at … …" or "at … …" or "responsive to a determination", depending on the context.
The present application will be described in detail with reference to the accompanying drawings. The features of the examples and embodiments described below may be combined with each other without conflict.
Under the scene of cooperative flow scheduling, the application designs an online scheduling method by considering the routing and bandwidth allocation strategy between the internal subflow of the Coflow and the Coflow on the premise of not needing any priori knowledge, so as to realize the overall time consumption minimization of the network cooperative flow scheduling.
As shown in fig. 1 and fig. 2, the method for routing and scheduling network-oriented cooperative traffic provided by the application includes the following steps:
(1) Information on each Coflow is obtained using { (C) i , T i , D i ) Represented by i.e. [1, N ]]N is the total number of all Coflows at the current moment, C i Represents the ith Cofow, T i Represents the arrival time of the ith Coflow, D i Indicating the data size to be processed in the calculation stage of the ith Coflow; obtain the substream information of Coflow by { (start) j ,end j ,s j ) The start represents j Start device, end, representing the jth substream in Coflow j Endpoint device, s, representing the j-th substream in a Coflow j The flow size of the j-th sub-flow in the Coflow is shown; calculating and traversing a routing path between any two devices in a data center network, the routing path being for a set { P } k Represented by P k Represents the kth routing path, see fig. 3.
The step (1) specifically comprises the following substeps:
(1.1) obtaining information on each Coflow by { (C) i , T i , D i ) Represented by i.e. [1, N ]]N is the total number of all Coflows at the current moment, C i Represents the ith Cofow, T i Represents the arrival time of the ith Coflow, D i Representing the size of the data that needs to be processed in the calculation phase of the ith Coflow, where the set { (C) is used i , T i , D i ) Form representation, facilitating subsequent steps for scheduling and routing of the Coflow.
(1.2) obtaining the substream information of Coflow with { (start) j ,end j ,s j ) The start represents j Start device, end, representing the jth substream in Coflow j Indicating the endpoint device of the j-th substream in the Coflow; s is(s) j The flow size of the j-th sub-flow in the Coflow is indicated, namely the size of the transmitted data message.
(1.3) calculating and traversing any possible routing paths (avoiding path existence loops or looping) between any two devices in the data center network by breadth-first algorithm, storing the possible routing paths into a set { P } k }。
(2) Paths for single Coflow internal substreamsThe problem is modeled as a first integer programming problem by sum bandwidth allocation, and the transmission time t of the Coflow is minimized on the basis of ensuring that the routing and bandwidth allocation of the Coflow substreams are achieved. With the Coflow substream information { (start) collected in step (1) j ,end j ,s j ) Sum routing path { P } k As input, solving a first integer programming problem by an approximation algorithm, outputting an approximately optimal solution { (x) for routing and bandwidth allocation scheduling of single-Coflow internal substreams jk ,b jk T), where x jk The value of the routing path is 0 or 1, and the routing path selected by the j-th substream of the Coflow is p when the value of the routing path is 1 k When the value is 0, the j-th sub-flow representing the Coflow does not select a routing path, b jk Indicating that the jth substream of the Coflow is on the routing path p k And the bandwidth allocated on the top, t represents the total transmission time of all sub-streams in the Coflow.
The step (2) specifically comprises the following substeps:
(2.1) acquiring the Coflow substream information { (start) in step (1) j ,end j ,s j ) Sum routing path { P } k -as input; and carrying out routing and bandwidth allocation of the single Coflow internal substreams based on the routing paths between any two devices in the Coflow substream information and the data center network.
(2.2) modeling the routing and bandwidth allocation problems of the internal substreams of the Coflow into a first integer programming problem with the goal of minimizing the transit time of the Coflow, constraints including: a) Each sub-stream can be allocated to only one candidate route path; b) The sum of sub-stream bandwidth allocation on a certain routing path must be smaller than the bandwidth capacity of the routing path; c) The transmission time of any one of the Coflow substreams is not longer than the total transmission time of the Coflow. The mathematical expression is as follows:
（1）
（2）
（3）
（4）
in the above formula (1), t represents the transmission time of a single Coflow, and since the substreams can be transmitted in parallel, t is not equal to the sum of the time consumed by all substreams, but t must not be less than the transmission time of any substream, as in the formula (4); the sum of sub-stream bandwidth allocation on any routing path needs to be no greater than its remaining available bandwidth, e.g. equation (2), re k Representing the path P k Is not allocated to the remaining available bandwidth; equation (3) shows that each sub-stream can be allocated to only one candidate routing path.
(2.3) using a planning solution module to solve the approximate optimal solution { (x) of single Coflow scheduling by an approximation algorithm for the formula (1) and three constraint conditions, namely the formula (2), the formula (3) and the formula (4) jk ,b jk ,t)}。
(3) And (3) considering the problems of limited computational resources and limited network resources under the condition of parallel scheduling of a plurality of Cofiow, and carrying out the computational resource allocation and bandwidth allocation among the Cofiow. Firstly, considering the limitation of computing resources, modeling the problems of computing resource allocation and bandwidth allocation between Coflows into a second integer programming problem so as to realize the maximization of resource utilization; and secondly, bandwidth allocation adjustment is based on routing and bandwidth allocation of each Coflow internal sub-flow in the step (2), traversing the residual available bandwidth on each routing path in the data center network, and proportionally adjusting and updating the routing and bandwidth allocation scheduling strategy of the Coflow so as to ensure that congestion does not occur on each path.
The step (3) specifically comprises the following substeps:
(3.1) considering computational resource constraints, the Coflow information is known { (C) i , T i , D i ) Under the condition of CPU core number maximum quota Q in the computing stage of the Coflow, computing resource allocation and bandwidth allocation among the Coflows are allocatedThe questions are modeled as a second integer programming problem to maximize resource utilization. The constraint conditions of the second integer programming problem are: (a) the sum of the CPU cores allocated by all Coflows is not more than Q; (b) the number of CPU cores allocated by any Coflow must be a positive integer. The mathematical expression is as follows:
（5）
（6）
（7）
（8）
the constraint (b) in the substep (3.1) corresponds to the above formula (6), which indicates that the number of CPU cores allocated to any Coflow must be a positive integer; equation (7) corresponds to constraint (a) in substep (3.1), and the sum of the numbers of CPU cores allocated by all Coflows is not greater than the maximum quota Q; the formula (8) shows the CPU core number distribution condition of the ith Coflow, and the data volume ratio in the calculation stage is multiplied by the maximum CPU quota Q and then is obtained by rounding downwards. Then the planning solution module obtains the approximate optimal solution { (C) of the resource allocation through approximate algorithm solution i , T i , y i ) -wherein y i Indicating the number of CPU cores allocated by the ith Coflow.
(3.2) respectively carrying out routing and bandwidth allocation on the internal subflows of the Cofiow aiming at all the Cofiow which can be scheduled at the current moment to obtain the approximate optimal solution of the subflow scheduling of each CofiowWhere i, j represent the ith Coflow and its internal jth substream, respectively.
(3.3) sub-stream scheduling of each Coflow based on sub-step (3.2)Like the optimal solution, the routing path P is counted k Is calculated by calculating the route path P by the sum of the bandwidth allocations of the (B) and the remaining available bandwidth k Bandwidth adjustment coefficient of (a)，Representing assignment to routing path P k Re, sum of all bandwidths of (a) k Representing a routing path P k Is used for the remaining available bandwidth.
(3.4) according to the bandwidth adjustment coefficient of the routing path, adjusting the bandwidth allocation condition of the updated Coflow to obtain the routing and bandwidth allocation scheduling policy of the jth subflow in the ith Coflow as follows。
(4) When a certain Coflow transmission is completed or a new Coflow arrives, the Coflow subflow which is not transmitted yet needs to be subjected to the process of readjusting the routing and bandwidth allocation scheduling strategy of the Coflow based on the current residual available bandwidthI.e. re-executing step (2) and step (3).
(5) The method comprises the steps of (1) distributing the routing and bandwidth of the Coflow output in the step (4) to a scheduling policy conversion moduleThe method comprises the steps of converting into a scheduling strategy executable by an SDN controller, inputting the scheduling strategy into the SDN controller, converting into a routing table entry by the SDN controller, and transmitting the converted routing table entry to data plane forwarding equipment to realize efficient scheduling of network cooperative traffic.
Corresponding to the embodiment of the routing scheduling method for the network cooperative traffic, the application also provides an embodiment of the routing scheduling system for the network cooperative traffic.
Fig. 4 is a schematic structural diagram of a routing system for network cooperative traffic. Referring to fig. 4, the system may include:
the single-Coflow sub-flow scheduling module is used for modeling the internal sub-flow scheduling problem of the Coflow into an integer programming problem, filtering the output after the problem is solved, and taking the filtered result as the input of the multi-Coflow scheduling module;
the planning solving module is used for solving the modeling problem of the single-Coflow sub-flow scheduling module, obtaining an approximate optimal solution through an approximate algorithm, and outputting an optimal routing path, bandwidth allocation and Coflow transmission time of the sub-flow;
the multi-Coflow scheduling module is used for proportionally adjusting the bandwidth allocation of each Coflow by considering the bandwidth capacity of each routing path in the data center network based on the output result of the single-Coflow sub-flow scheduling module, and generating a routing path and a bandwidth allocation scheduling strategy;
and the scheduling policy conversion module is used for converting the routing path and the bandwidth allocation scheduling policy generated by the multi-Coflow scheduling module into the scheduling policy executable by the SDN controller.
Further, the system may further include: the environment component module comprises data plane forwarding equipment and an SDN controller; the data plane forwarding device is used for acquiring information of the Coflow, including quantity, arrival time and the like; the information of the Coflow substream comprises a start-stop equipment node and a flow size; the SDN controller is used for acquiring and calculating candidate routing paths between any two equipment nodes of the data center network, generating routing table items after receiving an executable scheduling strategy and sending the routing table items to the data plane forwarding equipment.
The specific manner in which the various modules perform the operations in relation to the systems of the above embodiments have been described in detail in relation to the embodiments of the method and will not be described in detail herein.
Corresponding to the foregoing embodiment of the network-oriented cooperative traffic routing scheduling method, an embodiment of the present application further provides an electronic device, including: one or more processors; a memory for storing one or more programs; the one or more programs, when executed by the one or more processors, cause the one or more processors to implement a network-oriented collaborative traffic routing scheduling method as described above. As shown in fig. 5, a hardware structure diagram of an arbitrary device with data processing capability, where the network-oriented cooperative traffic routing scheduling method provided by the embodiment of the present application is located, is except for a processor, a memory, a DMA controller, a disk, and a nonvolatile memory shown in fig. 5, where the arbitrary device with data processing capability in the embodiment is located, generally, may further include other hardware according to an actual function of the arbitrary device with data processing capability, which is not described herein.
Corresponding to the foregoing embodiment of the network cooperative traffic oriented routing scheduling method, the embodiment of the present application further provides a computer readable storage medium, where a program is stored, and when the program is executed by a processor, the network cooperative traffic oriented routing scheduling method in the foregoing embodiment is implemented.
The computer readable storage medium may be an internal storage unit, such as a hard disk or a memory, of any of the data processing enabled devices described in any of the previous embodiments. The computer readable storage medium may be any device having data processing capability, for example, a plug-in hard disk, a Smart Media Card (SMC), an SD Card, a Flash memory Card (Flash Card), or the like, which are provided on the device. Further, the computer readable storage medium may include both internal storage units and external storage devices of any data processing device. The computer readable storage medium is used for storing the computer program and other programs and data required by the arbitrary data processing apparatus, and may also be used for temporarily storing data that has been output or is to be output.
The foregoing description of the preferred embodiments of the application is not intended to be limiting, but rather to enable any modification, equivalent replacement, improvement or the like to be made within the spirit and principles of the application.
Other embodiments of the application will be apparent to those skilled in the art from consideration of the specification and practice of the disclosure herein. This application is intended to cover any variations, uses, or adaptations of the application following, in general, the principles of the application and including such departures from the present disclosure as come within known or customary practice within the art to which the application pertains. The specification and examples are to be regarded in an illustrative manner only.
It is to be understood that the application is not limited to the precise arrangements and instrumentalities shown in the drawings, which have been described above, and that various modifications and changes may be effected without departing from the scope thereof.
Claims (10)
1. A routing scheduling method for network cooperative traffic is characterized by comprising the following steps:
(1) Acquiring Coflow and sub-flow information thereof, and calculating and traversing a routing path between any two devices in a data center network;
(2) Taking the routing path between any two devices in the Coflow substream information and the data center network as input, and solving the approximate optimal solution of the routing and bandwidth allocation of the single Coflow internal substream through an approximate algorithm;
(3) Routing and bandwidth allocation are carried out on each Coflow internal sub-flow, residual available bandwidth on each routing path in the data center network is traversed, and routing and bandwidth allocation scheduling strategies of the updated Coflows are adjusted;
(4) When a certain Coflow transmission is completed or a new Coflow arrives, updating a routing and bandwidth allocation scheduling strategy of the Coflow;
(5) And converting the updated routing and bandwidth allocation scheduling policy into a scheduling policy executable by the SDN controller.
2. The method for routing and scheduling network-oriented collaborative traffic according to claim 1, wherein in the step (1), a routing path between any two devices in the data center network is calculated and traversed by a breadth-first algorithm.
3. The method for routing and scheduling network-oriented cooperative traffic according to claim 1, wherein the step (2) comprises the following sub-steps:
(2.1) performing routing and bandwidth allocation of a single Coflow internal substream based on the Coflow substream information and a routing path between any two devices in a data center network;
(2.2) modeling the routing and bandwidth allocation problems of the internal substreams of the Coflow into a first integer programming problem, and constructing constraint conditions of the first integer programming problem, so as to minimize the transmission time of the Coflow;
and (2.3) solving an approximate optimal solution of single Coflow scheduling through an approximate algorithm based on the constraint condition of the first integer programming problem.
4. A network collaborative traffic oriented routing scheduling method according to claim 3 wherein in the substep (2.2) the constraint of the first integer programming problem comprises: each sub-stream is allocated to a candidate route path; the sum of sub-stream bandwidth allocation on any one routing path is smaller than the bandwidth capacity of the path; the transmission time of any one of the Coflow substreams is not longer than the total transmission time of the Coflow.
5. The method for routing and scheduling network-oriented cooperative traffic according to claim 1, wherein the step (3) comprises the following sub-steps:
(3.1) modeling the problems of computing resource allocation and bandwidth allocation among the Coflows into a second integer programming problem, and solving by an approximation algorithm to obtain an approximate optimal solution of the resource allocation;
(3.2) respectively carrying out routing and bandwidth allocation on all the Coflows which can be scheduled at the current moment, and obtaining a sub-flow scheduling approximate optimal solution of each Coflow;
(3.3) calculating the bandwidth adjustment coefficient of the routing path based on the sub-flow scheduling approximate optimal solution of each Coflow obtained in the sub-step (3.2), and counting the sum of the bandwidth allocation of the routing path and the residual available bandwidth thereof;
and (3.4) adjusting and updating the bandwidth allocation condition of the Coflow according to the bandwidth adjustment coefficient of the routing path to obtain the routing and bandwidth allocation scheduling strategy.
6. The network collaborative traffic oriented routing scheduling method of claim 5 wherein in the substep (3.1), the constraint of the second integer programming problem comprises: the sum of the CPU core numbers distributed by all Coflow is not more than Q; the CPU core number allocated by any Coflow is a positive integer.
7. The method for routing and scheduling network-oriented cooperative traffic according to claim 1, wherein the step (5) specifically comprises: after the updated routing and bandwidth allocation scheduling policy is converted into the scheduling policy executable by the SDN controller, the scheduling policy is input into the SDN controller, the SDN controller is converted into a routing table entry, and the converted routing table entry is sent to the data plane forwarding equipment to realize the scheduling of the network cooperative traffic.
8. A network-oriented cooperative traffic routing and scheduling system, comprising:
the single-Coflow sub-flow scheduling module is used for modeling the internal sub-flow scheduling problem of the Coflow into an integer programming problem, filtering the output after the problem is solved, and taking the filtered result as the input of the multi-Coflow scheduling module;
the planning solving module is used for solving the modeling problem of the single-Coflow sub-flow scheduling module, obtaining an approximate optimal solution through an approximate algorithm, and outputting an optimal routing path, bandwidth allocation and Coflow transmission time of the sub-flow;
the multi-Coflow scheduling module is used for proportionally adjusting the bandwidth allocation of each Coflow, and generating a routing path and a bandwidth allocation scheduling strategy;
and the scheduling policy conversion module is used for converting the routing path and the bandwidth allocation scheduling policy generated by the multi-Coflow scheduling module into the scheduling policy executable by the SDN controller.
9. An electronic device comprising a memory and a processor, wherein the memory is coupled to the processor; wherein the memory is configured to store program data, and the processor is configured to execute the program data to implement the network-oriented cooperative traffic routing method of any of claims 1 to 7.
10. A computer readable storage medium having stored thereon a computer program, wherein the program when executed by a processor implements a network collaborative traffic oriented routing scheduling method according to any one of claims 1-7.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311487370.8A CN117221126B (en) | 2023-11-09 | 2023-11-09 | Network collaboration flow-oriented route scheduling method and system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311487370.8A CN117221126B (en) | 2023-11-09 | 2023-11-09 | Network collaboration flow-oriented route scheduling method and system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN117221126A true CN117221126A (en) | 2023-12-12 |
| CN117221126B CN117221126B (en) | 2024-02-13 |
Family
ID=89046712
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202311487370.8A Active CN117221126B (en) | 2023-11-09 | 2023-11-09 | Network collaboration flow-oriented route scheduling method and system |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN117221126B (en) |
Citations (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105306280A (en) * | 2015-12-03 | 2016-02-03 | 中国人民解放军理工大学 | Data driving network construction maintenance system and method for efficient substream transmission |
| WO2017032157A1 (en) * | 2015-08-25 | 2017-03-02 | 上海交通大学 | Coflow scheduling method for distributed computer platform |
| US20170230298A1 (en) * | 2016-02-09 | 2017-08-10 | Flowtune, Inc. | Network Resource Allocation |
| WO2017161982A1 (en) * | 2016-03-25 | 2017-09-28 | 华为技术有限公司 | Method and device for multi-flow transmission in sdn network |
| CN108712305A (en) * | 2018-05-04 | 2018-10-26 | 电子科技大学 | A kind of Coflow dispatching methods based on subflow flow value method of estimation |
| CN110708259A (en) * | 2019-09-25 | 2020-01-17 | 江苏省未来网络创新研究院 | Information-agnostic Coflow scheduling system capable of automatically adjusting queue threshold and scheduling method thereof |
| EP3654594A1 (en) * | 2018-11-15 | 2020-05-20 | Siemens Aktiengesellschaft | Method for data transmission, communication device, computer program and computer readable medium |
| CN113946455A (en) * | 2021-10-15 | 2022-01-18 | 国网安徽省电力有限公司信息通信分公司 | Multi-stage feedback queue flow scheduling method based on bottleneck perception |
| CN114465941A (en) * | 2022-04-13 | 2022-05-10 | 之江实验室 | Cluster computing flow simulation method, system and device based on packet receiving and transmitting cooperation |
| CN114666283A (en) * | 2022-03-07 | 2022-06-24 | 国家电网有限公司信息通信分公司 | Application-aware multi-tenant flow scheduling method and system |
| CN114866474A (en) * | 2022-04-29 | 2022-08-05 | 鹏城实验室 | End network cooperative traffic scheduling method, device, system and storage medium |
| CN115987891A (en) * | 2021-10-14 | 2023-04-18 | 南京航空航天大学 | Online routing and scheduling method for data center network mixed flow |
-
2023
- 2023-11-09 CN CN202311487370.8A patent/CN117221126B/en active Active
Patent Citations (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2017032157A1 (en) * | 2015-08-25 | 2017-03-02 | 上海交通大学 | Coflow scheduling method for distributed computer platform |
| CN105306280A (en) * | 2015-12-03 | 2016-02-03 | 中国人民解放军理工大学 | Data driving network construction maintenance system and method for efficient substream transmission |
| US20170230298A1 (en) * | 2016-02-09 | 2017-08-10 | Flowtune, Inc. | Network Resource Allocation |
| WO2017161982A1 (en) * | 2016-03-25 | 2017-09-28 | 华为技术有限公司 | Method and device for multi-flow transmission in sdn network |
| CN108712305A (en) * | 2018-05-04 | 2018-10-26 | 电子科技大学 | A kind of Coflow dispatching methods based on subflow flow value method of estimation |
| EP3654594A1 (en) * | 2018-11-15 | 2020-05-20 | Siemens Aktiengesellschaft | Method for data transmission, communication device, computer program and computer readable medium |
| CN110708259A (en) * | 2019-09-25 | 2020-01-17 | 江苏省未来网络创新研究院 | Information-agnostic Coflow scheduling system capable of automatically adjusting queue threshold and scheduling method thereof |
| CN115987891A (en) * | 2021-10-14 | 2023-04-18 | 南京航空航天大学 | Online routing and scheduling method for data center network mixed flow |
| CN113946455A (en) * | 2021-10-15 | 2022-01-18 | 国网安徽省电力有限公司信息通信分公司 | Multi-stage feedback queue flow scheduling method based on bottleneck perception |
| CN114666283A (en) * | 2022-03-07 | 2022-06-24 | 国家电网有限公司信息通信分公司 | Application-aware multi-tenant flow scheduling method and system |
| CN114465941A (en) * | 2022-04-13 | 2022-05-10 | 之江实验室 | Cluster computing flow simulation method, system and device based on packet receiving and transmitting cooperation |
| CN114866474A (en) * | 2022-04-29 | 2022-08-05 | 鹏城实验室 | End network cooperative traffic scheduling method, device, system and storage medium |
Non-Patent Citations (5)
| Title |
|---|
| LI SHI等: "Coflow Scheduling in Data Centers: Routing and Bandwidth Allocation", 《IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS》, vol. 32, no. 11 * |
| 李道全;黄泰铭;于波;王雪;: "基于流量分配倾向度的SDN多路径负载均衡", 计算机工程与设计, no. 10 * |
| 马腾;胡宇翔;张校辉;: "基于深度增强学习的数据中心网络coflow调度机制", 电子学报, no. 07 * |
| 黄鸿: "软件定义数据中心网络Coflow调度机制与仿真平台研究", 《中国优秀硕士学位论文全文数据库》 * |
| 黄鸿;莫李思;孙罡;: "一种基于端口聚合流量的Coflow调度机制", 通信技术, no. 07 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN117221126B (en) | 2024-02-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Sallam et al. | Shortest path and maximum flow problems under service function chaining constraints | |
| Li et al. | TrafficShaper: Shaping inter-datacenter traffic to reduce the transmission cost | |
| CN111030835A (en) | Task scheduling model of TTFC network and message scheduling table generation method | |
| CN103036792B (en) | Transmitting and scheduling method for maximizing minimal equity multiple data streams | |
| CN109582448A (en) | A kind of edge calculations method for scheduling task towards criticality and timeliness | |
| CN114071582A (en) | Service chain deployment method and device for cloud-edge collaborative Internet of things | |
| Ye et al. | Diffusion limit of fair resource control—stationarity and interchange of limits | |
| Zuo et al. | Bandwidth reservation strategies for scheduling maximization in dedicated networks | |
| Yuan et al. | Delay-aware NFV resource allocation with deep reinforcement learning | |
| CN107483355B (en) | Data center-oriented online scene low-bandwidth overhead traffic scheduling scheme | |
| Li et al. | Efficient adaptive matching for real-time city express delivery | |
| CN117221126B (en) | Network collaboration flow-oriented route scheduling method and system | |
| Dong et al. | TINA: A fair inter-datacenter transmission mechanism with deadline guarantee | |
| CN113765825A (en) | Planning method and system architecture for chain type service flow scheduling | |
| Xia et al. | Distributed resource management and admission control of stream processing systems with max utility | |
| CN114884893B (en) | Forwarding and control definable cooperative traffic scheduling method and system | |
| CN114885028B (en) | Service scheduling method, device and computer readable storage medium | |
| Brun et al. | Weighted scheduling of time-sensitive coflows | |
| Dong | LINA: A fair link-grained inter-datacenter traffic scheduling method with deadline guarantee | |
| Dong et al. | Slardar: Scheduling information incomplete inter-datacenter deadline-aware coflows with a decentralized framework | |
| CN115208765A (en) | Slice arranging method and system for power business | |
| CN102594670A (en) | Multiport multi-flow scheduling method, device and equipment | |
| Tao et al. | Pota: Maximizing profit for task-level scheduling for data center networks | |
| Luangsomboon et al. | A round-robin packet scheduler for hierarchical max-min fairness | |
| CN117278557B (en) | Wide area deterministic algorithm network scheduling method, system, device and medium based on double-layer planning |
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 |