[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN106878192B - Data scheduling method of self-adaptive MPTCP - Google Patents

Data scheduling method of self-adaptive MPTCP Download PDF

Info

Publication number
CN106878192B
CN106878192B CN201611221402.XA CN201611221402A CN106878192B CN 106878192 B CN106878192 B CN 106878192B CN 201611221402 A CN201611221402 A CN 201611221402A CN 106878192 B CN106878192 B CN 106878192B
Authority
CN
China
Prior art keywords
sub
congestion window
flow
size
average
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.)
Active
Application number
CN201611221402.XA
Other languages
Chinese (zh)
Other versions
CN106878192A (en
Inventor
唐碧华
范文浩
罗润文
吴帆
张洪光
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Beijing University of Posts and Telecommunications
Original Assignee
Beijing University of Posts and Telecommunications
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Beijing University of Posts and Telecommunications filed Critical Beijing University of Posts and Telecommunications
Priority to CN201611221402.XA priority Critical patent/CN106878192B/en
Publication of CN106878192A publication Critical patent/CN106878192A/en
Application granted granted Critical
Publication of CN106878192B publication Critical patent/CN106878192B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/12—Avoiding congestion; Recovering from congestion
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/12—Avoiding congestion; Recovering from congestion
    • H04L47/127—Avoiding congestion; Recovering from congestion by using congestion prediction

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

The invention discloses a data scheduling method of self-adaptive MPTCP, which comprises the following steps: establishing a Markov model according to the congestion window of each sub-flow; calculating to obtain the average congestion window size of each sub-flow according to a Markov model; calculating to obtain the current round trip time value of each sub-flow according to the timestamp field; predicting to obtain the average effective throughput rate of each sub-flow according to the average congestion window size and the round trip time value of each sub-flow; dynamically adjusting the size of a congestion window of the minimum sub-flow according to the average effective throughput rate on each sub-flow, so that the minimum sub-flow is prevented from being congested; and adjusting the size of the slow start threshold according to the adjusted size of the congestion window, so that the adjusted sub-flow is still in a congestion avoidance stage. The data scheduling method of the self-adaptive MPTCP overcomes the defects of the existing MPTCP data scheduling and congestion control technology, so that the MPTCP can adaptively perform more reasonable scheduling aiming at the conditions of network fluctuation and network isomerization, and finally the efficiency and reliability of multi-path data transmission can be improved.

Description

Data scheduling method of self-adaptive MPTCP
Technical Field
The invention relates to the technical field of data scheduling and congestion control, in particular to a data scheduling method of self-adaptive MPTCP.
Background
In recent years, with the more and more extensive application of intelligent terminals and the continuous development of internet communication, the demand of network application on traffic is also more and more increased; network applications represented by big data applications, mobile televisions, video calls, and the like, are in urgent need of a high-reliability fast data transmission technology as a support. The existing internet uses the TCP/IP protocol suite, of which the transport layer is most widely studied and used, represented by the TCP protocol. However, the conventional TCP protocol cannot simultaneously utilize multiple communication interfaces (such as an ethernet interface and a WIFI interface) of the intelligent terminal, only one transmission path can be established by using one interface during end-to-end connection, and cannot meet the requirement of increasing throughput, more importantly, the single-path transmission reliability is poor, if interference or transmission congestion occurs, the transmission performance is sharply reduced, and if the transmission congestion is serious, transmission is interrupted. The Multipath-TCP (MPTCP) was developed to make up for the TCP deficiency. The protocol is a multipath parallel transmission protocol based on the traditional TCP, can be compatible with the existing middleware, and has the characteristics of high reliability, high fault tolerance, high throughput, high safety, compatibility with the TCP and the like.
The end-to-end equipment places data on multiple paths through the MPTCP for parallel transmission, and the throughput and the robustness of data transmission can be improved by jointly utilizing multiple interfaces. When data distribution among multiple paths is performed, MPTCP needs to perform path selection in advance among multiple available links, a transmission path with poor link quality needs to be abandoned, and a transmission path with better link quality is selected, so that difference of transmission quality among paths is reduced. On one hand, if a transmitting end does not abandon a poor transmission path in the multipath transmission process, data transmission on the path is easy to cause the problems of timeout, errors, packet loss, retransmission and the like of data packets, a receiving end sequences and combines the data packets received on each path, even if the data transmission on other paths is normal, incomplete data caused by delayed arrival of the data packets on the path can cause delayed delivery to an upper layer application, and further the overall transmission performance of the MPTCP between the transmitting end and the receiving end can be influenced. On the other hand, if the difference in transmission quality between the paths is too large, the data packet carried by the poor path is lost, and the data packet received on the better path will quickly fill the data buffer of the receiving end, thereby causing the problems of data transmission suspension and overtime retransmission of a large amount of data on the better path. Therefore, in MPTCP data transmission, it is very important to schedule data onto reasonable paths and to handle congestion that may occur.
In the existing MPTCP protocol, an evaluation index of path quality mainly utilizes transmission delay of data on the path, the transmission delay is one of visual indexes representing the path quality, and an evaluation method for the index is to measure a Round-Trip Time (RTT) value of the path. RTT on a path represents the total time delay from the start of sending a packet on the path by the sender to the time the sender receives an acknowledgement for the datagram from the receiver on the path (the receiver sends an acknowledgement immediately after receiving the packet). The smaller the RTT, the higher the transmission quality of the path, and vice versa.
The inventor finds that, in the process of implementing the invention, the RTT is used to evaluate the path quality, and then the path selection is performed, although the measurement method is relatively simple and the accuracy is relatively high, the following disadvantages are at least present: 1) when measuring RTT, it needs to send redundant data packet or start actual data transmission, the former measures RTT by sending special data packet and occupies bandwidth resource of path, the latter is equivalent to actually using the path to transmit data, measures RTT by sending data packet in transmission process, if path quality is poor, it can directly cause data loss of receiving end; 2) RTT measurement relates to a process of sending a data packet, a process of receiving and processing a data packet at a receiving end, a process of sending an acknowledgement packet at a receiving end, and a process of receiving an acknowledgement packet and processing an acknowledgement packet at a sending end, and measurement time at least includes round trip time of a data packet, so that there is a certain time delay in measurement. The worse the path quality, the longer the corresponding measurement delay, which will reduce the efficiency of MPTCP path selection.
Disclosure of Invention
In view of this, the present invention is to provide a data scheduling method for adaptive MPTCP, which can improve the efficiency and reliability of multipath data transmission.
Based on the above purpose, the present invention provides a data scheduling method for adaptive MPTCP, which includes:
establishing a Markov model according to the congestion window of each sub-flow;
calculating to obtain the average congestion window size of each sub-flow according to a Markov model;
calculating to obtain the current round trip time value of each sub-flow according to the timestamp field in the data packet;
predicting to obtain the average effective throughput rate on each sub-flow according to the average congestion window size and the round trip time value of each sub-flow;
dynamically adjusting the size of a congestion window of the minimum sub-flow according to the average effective throughput rate on each sub-flow, so that the minimum sub-flow is prevented from being congested;
and adjusting the size of the slow start threshold according to the adjusted size of the congestion window, so that the adjusted sub-flow is still in a congestion avoidance stage.
Optionally, the markov model comprises: the sending state set of the equipment at each moment and the one-step transition probability set of the sending state conversion; wherein, the sending state set comprises the size of the congestion window of each sub-flow; the transition probability set is related to the packet loss rate of each sub-stream.
Optionally, the step of calculating the average congestion window size of each substream according to the markov model includes:
obtaining a transition probability matrix of the sending state of the equipment according to the packet loss rate of each sub-flow;
calculating to obtain ultimate stable distribution according to the probability transition rule of the transition probability matrix;
and calculating the average congestion window size of each sub-flow according to the limit stable distribution.
Optionally, the extreme stationary distribution is recorded as a feature vector μ; and the feature vector meets the following constraints:
μ＝(μ1,μ2…μv)
μP＝μ
μ1+μ2+…+μv-1+μv＝1
μj≥0,j∈{1,2…v}
wherein, the Maximum congestion window limited by the size of the receiving buffer is W MSS (Maximum segment) units, and the minimum congestion window is 2 MSS units, so the value range of the sub-flow congestion window is [2, W]. Let k be the number of substreams, cwi(i∈[1,k]And i belongs to Z) is the size of the congestion window of the sub-flow i, the sending state of the system is represented by each sub-flow congestion window set, and the sending state space is known to be in a k-dimensional discrete stateState space, expressed as I { (cw)1,cw2,…cwi…,cwk)|cwi∈[2,W]And cwiIs left to Z, and the known state space I comprises (W-1)kOne possible element, for convenience of presentation, remember v ═ W-1)k；μjIs the stationary distribution probability on the jth state in the state space; p is a transition probability matrix, and the transition probability matrix is a sparse matrix in (v x v) dimension;
the calculation expression of the average congestion window size is as follows:
Figure BDA0001192430630000031
wherein I is the sequence number of the sub-stream, I is the sending state space, and j is the state sequence number in the state space I; max is the number of elements of the feature vector, i.e., (W-1)k；The congestion window size of the sub-stream I in the jth state in the state space I; mu.sjThe probability of the stationary distribution corresponding to the jth state;
Figure BDA0001192430630000033
is the average congestion window size for sub-stream i.
Optionally, the step of calculating the current round trip time value of each sub-stream according to the timestamp field in the data packet further includes:
smoothing the round trip time value;
the expression of the smoothing process is:
RTTt＝(1-α)RTTnew+αRTTt-1
0<α<1
wherein RTTnewIs the round trip time value of the current moment; RTT (round trip time)t-1Is the round trip time value of the previous moment; RTT (round trip time)tWhich is the smoothed round trip time value, α is the factor by which the smoothed round trip time value is affected by the current round trip time value.
Optionally, the impact factor α is 0.8
Optionally, the calculation expression of the average goodput rate over each sub-stream is:
wherein p isiIs the packet loss rate on sub-stream i; MSSiIs the maximum transmission segment size on substream i;
Figure BDA0001192430630000042
is the average congestion window size over sub-stream i; RTT (round trip time)iIs the round trip time value on sub-stream i;
Figure BDA0001192430630000043
is the average goodput over substream i.
Optionally, the step of dynamically adjusting the size of the congestion window of the minimum sub-stream according to the average goodput rate on each sub-stream includes:
calculating to obtain a throughput rate coefficient according to the average effective throughput rate on each sub-flow; wherein the throughput rate coefficient is the ratio of the maximum sub-stream throughput rate to the minimum sub-stream throughput rate;
and judging whether the throughput rate coefficient is larger than the throughput rate critical value, if so, correspondingly reducing the size of the congestion window of the minimum sub-flow.
Optionally, the step of calculating a throughput coefficient according to the average goodput rate on each sub-stream further includes: and smoothing the throughput rate coefficient, wherein the expression of the smoothing is as follows:
θt＝(1-β)θnew+βθt-1
wherein β is a balance factor, thetanewThe current time throughput rate coefficient; thetat-1Counting an average coefficient for the throughput rate of the previous moment; thetatIs the throughput coefficient after the smoothing process.
Optionally, the calculation expression of the throughput threshold is:
(Gmax-Gmin)+1＜NBuf＜(Gmax-Gmin)+2
Figure BDA0001192430630000044
so as to obtain the compound with the characteristics of,
Figure BDA0001192430630000051
wherein N isBufFor the size of the receiving end buffer, GmaxFor maximum sub-stream throughput, GminIs the minimum substream throughput rate.
From the above, it can be seen that, in the data scheduling method of the adaptive MPTCP provided by the present invention, a markov model is constructed based on the congestion window of each sub-stream, and then the average congestion window size of each sub-stream is obtained through calculation, and then the average effective throughput rate on each sub-stream is obtained through prediction based on the average congestion window size and the round trip time value, so that the size of the congestion window can be adjusted according to the predicted throughput rate, and finally data scheduling and congestion control are realized. On the basis of a heterogeneous network multipath parallel transmission technology, the congestion windows of substreams corresponding to each interface of the wireless mobile equipment and the data scheduling behaviors which can be adopted are researched, the probability model based on the random event accumulation times is established to analyze the state transition probability, a predictable throughput rate feedback model is obtained accordingly, and the data is scheduled to the optimal interface by adopting the scheduling strategy with the optimal throughput rate, so that the advantages of multipath parallel transmission high transmission performance are exerted, and the reliability of data transmission is enhanced. Therefore, the data scheduling method of the self-adaptive MPTCP overcomes the defects of the existing MPTCP data scheduling and congestion control technology, so that the MPTCP can adaptively perform more reasonable scheduling aiming at the conditions of network fluctuation and network isomerization, and finally the efficiency and reliability of multi-path data transmission can be improved.
Drawings
Fig. 1 is a flowchart of an embodiment of a data scheduling method of adaptive MPTCP according to the present invention;
fig. 2 is a flowchart of another embodiment of a data scheduling method of adaptive MPTCP according to the present invention.
Detailed Description
In order to make the objects, technical solutions and advantages of the present invention more apparent, the present invention is described in further detail below with reference to specific embodiments and the accompanying drawings.
It should be noted that all expressions using "first" and "second" in the embodiments of the present invention are used for distinguishing two entities with the same name but different names or different parameters, and it should be noted that "first" and "second" are merely for convenience of description and should not be construed as limitations of the embodiments of the present invention, and they are not described in any more detail in the following embodiments.
The embodiment of the invention mainly relates to a data scheduling and congestion control technology of a Multi-path transmission control Protocol (Multi-path transmission control Protocol), in particular to self-adaptive data scheduling and congestion control under the conditions of network fluctuation and network differentiation realized by an optimized MPTCP throughput prediction method, thereby realizing high reliability of Multi-path data transmission. Aiming at the defects that the traditional TCP transmission only can utilize a single network interface and the limitations of MPTCP transmission data scheduling and congestion control technology, the invention provides a Markov model based on the discrete state of each substream congestion window of MPTCP, establishes a Markov decision process and scientifically predicts the effective throughput rate of each substream, and then provides a self-adaptive congestion window adjusting scheme facing the conditions of network fluctuation and network differentiation, thereby indirectly realizing more reasonable data scheduling and improving the reliability of data transmission in MPTCP.
Specifically, referring to fig. 1, a flowchart of an embodiment of a data scheduling method of adaptive MPTCP according to the present invention is shown. Aiming at the defect that the traditional MPTCP simply carries out data scheduling according to RTT, the invention aims to reasonably schedule data while considering a congestion window by establishing a Markov prediction model of the congestion window of each substream of the MPTCP and combining real-time RTT to realize a dynamic throughput rate prediction algorithm, thereby reducing data packet retransmission, packet loss and congestion and realizing high transmission reliability. The data scheduling method of the self-adaptive MPTCP comprises the following steps:
step 101, establishing a Markov model according to a congestion window of each substream; firstly, on the basis of assuming that data are uniformly scheduled to each substream, combining the packet loss rate of each substream, and integrating the discrete states of the congestion windows of each substream of MPTCP to establish a Markov model.
Optionally, the markov model comprises: the sending state set of the equipment at each moment and the one-step transition probability set of the sending state conversion; wherein, the sending state set comprises the size of the congestion window of each sub-flow; the transition probability set is related to the packet loss rate of each sub-stream. Specifically, let S represent a set of transmission states, and for a multipath parallel transmission device using k network interfaces, the transmission state S of the device at time t is represented by k elements, and the k elements record the congestion window sizes of k transmission sub-streams respectively. For example: CWiIndicating the congestion window size of the ith sub-stream, the transmission state s of the device at time tiDenoted as set S { CW1,CW2…CWk}. Let P(s)t|st-1) Representing the wireless mobile device transmitting state s at time t-1t-1And at time t the transmission state is switched to stThe one-step transition probability. Since the transmission state depends on the size of the congestion window for all sub-streams, which is related to the packet loss rate of each sub-stream, P(s)t|st-1) Indirectly limited by the packet loss rate of each sub-stream within an interval of Δ t, where Δ t represents the time interval between the sending end receiving two adjacent ACK acknowledgement packets.
102, calculating the average congestion window size of each substream according to a Markov model; based on the rule followed by the Markov model, probability distribution that all the sub-flows are finally stabilized in the size of the corresponding congestion window can be determined, so that ultimate stable distribution is obtained, and the size of the average congestion window can be calculated finally.
Optionally, the step of calculating the average congestion window size of each substream according to the markov model includes: obtaining a transition probability matrix of the sending state of the equipment according to the packet loss rate of each sub-flow; calculating to obtain the limit according to the probability transition rule of the transition probability matrixThe distribution is stable; and calculating the average congestion window size of each sub-flow according to the limit stable distribution. Specifically, on the basis of the binary group model (S, P) in the markov model, a transition probability matrix P of the transmission state of the device is first derived according to the packet loss rate of each sub-stream, and if the Maximum congestion window limited by the Size of the receiving buffer is W MSS (Maximum Segment Size) units and the minimum congestion window is 2 MSS units, the value range of the Size of the sub-stream congestion window is [2, W [ ]]. Let k be the number of substreams, cwi(i∈[1,k]And I belongs to Z) is the congestion window size of the sub-stream I, the sending state of the system is represented by each sub-stream congestion window set, and the sending state space is known to be a k-dimensional discrete state space and is represented as I { (cw)1,cw2,…cwi…,cwk)|cwi∈[2,W]And cwiIs left to Z, and the known state space I comprises (W-1)kOne possible element, for convenience of presentation, remember v ═ W-1)k. The transition probability matrix P is a sparse matrix in the dimension (v x v). From this, a limit stationary distribution is calculated, i.e. a probability distribution where all sub-streams eventually settle to the size of the corresponding congestion window, under the probability transition law following the P matrix. The size of the stationary congestion window for each substream can be obtained from the extreme stationary distribution of the Markov model, which is taken as the feature vector μ, where μ is a vector with v elements (μ1,μ2…μv). The feature vector μ satisfies three constraints:
μP＝μ
μ1+μ2+…+μv-1+μv＝1
μj≥0,j∈{1,2…v}
wherein v is the number of smoothly distributed elements, i.e., v ═ W-1)k；μjIs the stationary distribution probability on the jth state in the state space I; p is the transition probability matrix.
Optionally, the stationary distribution can be derived through computer programming, and obviously, the transition probability matrix P is a sparse matrix, so that the time complexity of programming and solving mu is not high, and the feasibility of solving is achieved. After the smooth distribution mu is deduced, the congestion window size of each sub-stream is calculated according to the following expression:
Figure BDA0001192430630000071
wherein I is the sequence number of the sub-stream, I is the sending state space, and j is the state sequence number in the state space I; max is the number of elements of the feature vector, i.e., (W-1)k；
Figure BDA0001192430630000072
Represents the congestion window size, μ, of the sub-stream I in the j-th state in the state space IjRepresenting the probability of the stationary distribution corresponding to the jth state;
Figure 2
is the average congestion window size.
Step 103, calculating to obtain the current round trip time value of each sub-flow according to the timestamp field in the data packet; the Timestamp field of the packet may be used to calculate the current RTT value:
RTT＝Timestamp_Value–Timestamp_Echo_Reply
according to RFC1323, the Timestamp option in the TCP header includes Timestamp _ Value and Timestamp _ Echo _ Reply, where Timestamp _ Value indicates a Timestamp corresponding to the current time when the packet is sent, and Timestamp _ Echo _ Reply is a Timestamp _ Value of a packet that is received last time by a receiving end and recorded in a received ACK packet
In some preferred embodiments, in consideration of the dynamic variation of RTT, a smoothing process needs to be performed on the current RTT value, where the smoothing process is expressed as:
RTTt＝(1-α)RTTnew+αRTTt-1
0<α<1
wherein RTTnewIs the round trip time value of the current moment; RTT (round trip time)t-1Is the round trip time value of the previous moment; RTT (round trip time)tTo smooth the processed round trip time value, α is a factor by which the smoothed round trip time value is affected by the current round trip time valueAnd the data scheduling method of the self-adaptive MPTCP is higher in accuracy and stability.
More preferably, α is 0.8.
104, predicting the average effective throughput rate on each sub-flow according to the average congestion window size and the round-trip time value of each sub-flow by the queuing theory Little theorem; optionally, the calculation expression of the average goodput rate over each sub-stream is:
Figure BDA0001192430630000081
wherein p isiIs the packet loss rate on sub-stream i; MSSiIs the maximum transmission segment size on substream i;
Figure 3
is the average congestion window size over sub-stream i; RTT (round trip time)iIs the round trip time value on sub-stream i;is the average goodput over substream i.
Step 105, dynamically adjusting the size of a congestion window of the minimum sub-flow according to the average effective throughput rate on each sub-flow, so that the minimum sub-flow is prevented from being congested; the average effective throughput rate of each sub-flow is the predicted throughput rate, and whether packet loss is possible to occur in the current sub-flow can be reflected laterally, so that congestion is avoided in advance.
Optionally, the step of dynamically adjusting the size of the congestion window of the minimum sub-stream according to the average goodput rate on each sub-stream includes: calculating to obtain a throughput rate coefficient according to the average effective throughput rate on each sub-flow; wherein the throughput rate coefficient is the ratio of the maximum sub-stream throughput rate to the minimum sub-stream throughput rate; and judging whether the throughput rate coefficient is larger than the throughput rate critical value, if so, correspondingly reducing the size of the congestion window of the minimum sub-flow. Specifically, for the differentiated network, first, a throughput coefficient θ is defined as a ratio of the maximum sub-stream throughput to the minimum sub-stream throughput, that is:
Figure BDA0001192430630000091
secondly, a throughput coefficient critical value theta is presetT，θTIs a critical value for predicting the difference between the maximum substream throughput rate and the minimum substream throughput rate. When theta > thetaTThis means that the predicted throughput difference between the sub-streams is too large, and the sub-stream with the smallest throughput is likely to have a packet loss, and appropriate congestion avoidance processing is performed, so that the congestion window of the sub-stream with the smallest throughput should be appropriately reduced. Here, exceeding this critical value will appropriately reduce the current congestion window of the sub-flow with the minimum predicted throughput rate, so as to address the upcoming congestion or packet loss phenomenon, which is referred to as a pseudo-congestion avoidance phase. Optionally, the congestion window is halved in the congestion avoidance phase with reference to classical congestion control algorithms, since θ > θTThe sub-stream with the lowest throughput rate enters a pseudo-congestion avoidance phase, so that the sub-stream congestion window should be reduced
Figure BDA0001192430630000092
Within the interval, the reduced congestion window size is
Figure BDA0001192430630000093
Optionally, in some embodiments of the present application, a dynamic change of θ is considered, and θ is smoothed, where an expression of the smoothing is: thetat＝(1-β)θnew+βθt-1；0<β<1, wherein β is a balance factor, thetanewThe current time throughput rate coefficient; thetat-1Counting an average coefficient for the throughput rate of the previous moment; thetatIs the throughput coefficient after the smoothing process.
Optionally, the critical value θTDepending on the receive buffer size, i.e., the maximum number of packets that the receiving end can accommodate. The calculation expression for obtaining the throughput threshold is therefore:
(Gmax-Gmin)+1＜NBuf＜(Gmax-Gmin)+2
Figure BDA0001192430630000094
the two formulas are combined to obtain the compound,
Figure BDA0001192430630000095
wherein N isBufFor the size of the receiving end buffer, GmaxFor maximum sub-stream throughput, GminIs the minimum substream throughput rate.
And step 106, adjusting the size of the slow start threshold according to the adjusted size of the congestion window, so that the adjusted sub-flow is still in the congestion avoidance stage.
If the sub-stream congestion window is reduced, comparing the reduced congestion windows cw'iAnd a slow start threshold SSTHreshiIf cw'i＜SSThreshiThen the slow start threshold is adjusted downward such that SSTHresh is seti＝cw′iThis ensures that the sub-streams remain in the congestion avoidance phase after the policy has been enforced.
It can be seen from the foregoing embodiments that, in the data scheduling method of the adaptive MPTCP provided in the present invention, a markov model is constructed based on the congestion window of each sub-stream, and then an average congestion window size of each sub-stream is obtained through calculation, and then an average effective throughput rate on each sub-stream is obtained through prediction based on the average congestion window size and the round trip time value, so that the congestion window size can be adjusted according to the predicted throughput rate, and finally data scheduling and congestion control are implemented. On the basis of a heterogeneous network multipath parallel transmission technology, the congestion windows of substreams corresponding to each interface of the wireless mobile equipment and the data scheduling behaviors which can be adopted are researched, the probability model based on the random event accumulation times is established to analyze the state transition probability, a predictable throughput rate feedback model is obtained accordingly, and the data is scheduled to the optimal interface by adopting the scheduling strategy with the optimal throughput rate, so that the advantages of multipath parallel transmission high transmission performance are exerted, and the reliability of data transmission is enhanced. Therefore, the data scheduling method of the self-adaptive MPTCP overcomes the defects of the existing MPTCP data scheduling and congestion control technology, so that the MPTCP can adaptively perform more reasonable scheduling aiming at the conditions of network fluctuation and network isomerization, and finally the efficiency and reliability of multi-path data transmission can be improved.
Referring to fig. 2, a flowchart of another embodiment of a data scheduling method of adaptive MPTCP according to the present invention is shown.
Firstly, establishing a Markov model;
assuming end-to-end communication between devices having two network interfaces and establishing an MPTCP connection comprising two sub-streams, the sending state at the last instant is expressed in the size of the congestion window of the two sub-streams, i.e. st-1＝{CW1,CW2}. When the sub-flow in the minimum transmission time interval has not lost the packet, the size of the congestion window is reduced by half, otherwise, the size of the congestion window is increased by 1, and s is the possible sending state s at the current time t obtained according to the sending state at the previous timetThere are four possible situations:
Figure BDA0001192430630000101
{CW1+1,CW2+1}
according to the packet loss rates of sub-streams 1 and 2, the four state transition probabilities can be calculated and recorded as
Figure BDA0001192430630000102
p12。
The congestion window size is expressed quantitatively according to the maximum transmission message MSS, and the size range of the sub-flow congestion window is taken to be [2, W ]. The transmit state space is then:
I：{(CW1,CW2)|CW1∈[2,W],CW2∈[2,W]}.
as can be seen from the state space, a transmit state at a certain time may be (W-1)2In this case, the state transition probability matrix from the previous time to the current time is one (W-1)2*(W-1)2Of the matrix of (a). Remember one-step transition probability matrix as P, rootAccording to state transition probabilityp12A one-step transition probability matrix P can be calculated. Note that the ultimate plateau of this mahalanobis chain is:
Figure BDA0001192430630000104
then the conditions of the plateau from the limit:
μ＝μP
μ1+μ2+…+μ(W-1) 2＝1
μi≥0,i∈{1,2,…(W-1)2}
the extreme stationary distribution characteristic vector of the Markov chain can be obtained
Figure BDA0001192430630000117
Secondly, solving the average congestion window size of each sub-flow;
the extreme stationarity vector represents the congestion window size at which the substreams are stable in each state. Deducing smooth distribution mu through computer programming, and solving the congestion window size of each sub-flow according to the following expression after deducing the smooth distribution mu:
Figure BDA0001192430630000111
wherein,
Figure BDA0001192430630000112
represents the congestion window size, μ, of the sub-stream I in the j-th state in the state space IjAnd (3) representing the steadily distributed characteristic vector element corresponding to the jth state, wherein max represents the number of the element of the characteristic vector, and the model can show that: max (W-1)2
The average congestion window size for subflow 1 can be derived from the above equation:
Figure 5
the same can be obtained.
Thirdly, calculating the average value of the statistical RTT of each sub-flow;
the Timestamp field of the packet may be used to calculate the current RTT value:
RTT＝Timestamp_Value–Timestamp_Echo_Reply
optionally, in consideration of a dynamic change of the RTT value, performing a smoothing process on the current RTT value:
RTTt＝(1-α)RTTnew+αRTTt-1
here 0< α <1, α is a factor reflecting that the smoothed RTT value is affected by the current RTT, depending on the network conditions.
Thirdly, predicting the effective throughput rate of each sub-flow;
and combining the average congestion window size and the smooth RTT value to obtain the effective throughput rate of each sub-flow:
Figure BDA0001192430630000115
finally, dynamically adjusting a congestion window and a slow start threshold;
the predicted goodput rates of the two sub-streams are denoted by size Gmax、Gmin. The current time throughput coefficient θ is obtained by the following two equations:
Figure BDA0001192430630000116
θt＝(1-β)θnew+βθt-1
wherein theta ist-1Is the statistical average coefficient at the previous time, and β is an influence factor determined according to the network condition.
Assuming that the predicted throughput difference of the two substreams reaches a certain threshold θTSo that the data packets are piled up by the amountApproaches the buffer size according to the transmit buffer size NBufLimited by the relationship of the maximum substream throughput rate and the minimum substream throughput rate.
(Gmax-Gmin)+1＜NBuf＜(Gmax-Gmin)+2
And is composed of
Figure BDA0001192430630000121
Obtaining a throughput rate coefficient critical value thetaT：
Figure BDA0001192430630000122
Comparison of θtAnd thetaTAnd according to the magnitude relation between the throughput rate coefficient and the critical value, corresponding operations are adopted:
when theta > thetaTReducing the congestion window of the least throughput sub-stream toComparing the reduced congestion windows cw'iAnd a slow start threshold SSTHreshiIf cw'i＜SSThreshiThen the slow start threshold is adjusted downward such that SSTHresh is seti＝cw′i；
When theta is less than or equal to thetaTAnd in time, the size of the congestion window is adjusted only according to the packet loss condition of each sub-stream.
Compared with the existing MPTCP data scheduling and congestion control technology, the invention has at least the following advantages:
1. the smooth RTT value is obtained based on the Timestamp field, and the condition of RTT jitter when the network fluctuates can be effectively handled.
2. And establishing a Markov decision process to dynamically predict the average congestion window size of each sub-flow, and accurately predicting the effective throughput rate of each sub-flow.
3. And the size of a congestion window of the slowest sub-flow is properly reduced according to the predicted throughput rate, and more scientific data scheduling and congestion control are performed aiming at different differential transmission networks with different sub-flow performances.
4. The influence of slow start and quick retransmission is considered, prediction deviation is reduced, and the slow start threshold value is scientifically adjusted aiming at the condition that the congestion window is reduced to be lower than the slow start threshold value.
Those of ordinary skill in the art will understand that: the discussion of any embodiment above is meant to be exemplary only, and is not intended to intimate that the scope of the disclosure, including the claims, is limited to these examples; within the idea of the invention, also features in the above embodiments or in different embodiments may be combined, steps may be implemented in any order, and there are many other variations of the different aspects of the invention as described above, which are not provided in detail for the sake of brevity.
In addition, well known power/ground connections to Integrated Circuit (IC) chips and other components may or may not be shown within the provided figures for simplicity of illustration and discussion, and so as not to obscure the invention. Furthermore, devices may be shown in block diagram form in order to avoid obscuring the invention, and also in view of the fact that specifics with respect to implementation of such block diagram devices are highly dependent upon the platform within which the present invention is to be implemented (i.e., specifics should be well within purview of one skilled in the art). Where specific details (e.g., circuits) are set forth in order to describe example embodiments of the invention, it should be apparent to one skilled in the art that the invention can be practiced without, or with variation of, these specific details. Accordingly, the description is to be regarded as illustrative instead of restrictive.
While the present invention has been described in conjunction with specific embodiments thereof, many alternatives, modifications, and variations of these embodiments will be apparent to those of ordinary skill in the art in light of the foregoing description. For example, other memory architectures (e.g., dynamic ram (dram)) may use the discussed embodiments.
The embodiments of the invention are intended to embrace all such alternatives, modifications and variances that fall within the broad scope of the appended claims. Therefore, any omissions, modifications, substitutions, improvements and the like that may be made without departing from the spirit and principles of the invention are intended to be included within the scope of the invention.

Claims (7)

1. A data scheduling method of adaptive MPTCP is characterized by comprising the following steps:
establishing a Markov model according to the congestion window of each sub-flow;
calculating to obtain the average congestion window size of each sub-flow according to a Markov model;
calculating to obtain the current round trip time value of each sub-flow according to the timestamp field in the data packet;
predicting to obtain the average effective throughput rate on each sub-flow according to the average congestion window size and the round trip time value of each sub-flow;
dynamically adjusting the size of a congestion window of the minimum sub-flow according to the average effective throughput rate on each sub-flow, so that the minimum sub-flow is prevented from being congested;
adjusting the size of a slow start threshold according to the adjusted size of the congestion window, so that the adjusted sub-flow is still in a congestion avoidance stage;
the step of dynamically adjusting the size of the congestion window of the smallest sub-stream according to the average goodput rate on each sub-stream comprises:
calculating to obtain a throughput rate coefficient according to the average effective throughput rate on each sub-flow; wherein the throughput rate coefficient is the ratio of the maximum sub-stream throughput rate to the minimum sub-stream throughput rate;
judging whether the throughput rate coefficient is larger than the throughput rate critical value, if so, correspondingly reducing the size of a congestion window of the minimum sub-flow;
the step of calculating a throughput coefficient according to the average goodput on each substream further comprises: and smoothing the throughput rate coefficient, wherein the expression of the smoothing is as follows:
θt＝(1-β)θnew+βθt-1
wherein β is a balance factor, thetanewThe current time throughput rate coefficient; thetat-1For swallowing at the previous momentCounting an average coefficient of the vomiting rate; thetatThe coefficient of the throughput rate after the smoothing processing;
the calculation expression of the throughput rate critical value is as follows:
(Gmax-Gmin)+1<NBuf<(Gmax-Gmin)+2
Figure FDA0002255891360000011
so as to obtain the compound with the characteristics of,
Figure FDA0002255891360000012
wherein N isBufFor the size of the receiving end buffer, GmaxFor maximum sub-stream throughput, GminIs the minimum substream throughput rate.
2. The method of claim 1, wherein the markov model comprises: the sending state set of the equipment at each moment and the one-step transition probability set of the sending state conversion; wherein, the sending state set comprises the size of the congestion window of each sub-flow; the transition probability set is related to the packet loss rate of each sub-stream.
3. The method of claim 1, wherein the step of calculating the average congestion window size for each substream based on a markov model comprises:
obtaining a transition probability matrix of the sending state of the equipment according to the packet loss rate of each sub-flow;
calculating to obtain ultimate stable distribution according to the probability transition rule of the transition probability matrix;
and calculating the average congestion window size of each sub-flow according to the limit stable distribution.
4. The method according to claim 3, characterized in that the extreme stationary distribution is denoted as eigenvector μ; and the feature vector meets the following constraints:
μ＝(μ1,μ2…μv)
μP＝μ
μ1+μ2+…+μk-1+μv＝1
μj≥0,j∈{1,2…v}
wherein, mujThe probability of a stationary distribution on the jth state in the state space I; p is a transition probability matrix, and the transition probability matrix is a sparse matrix in (v x v) dimension;
the calculation expression of the average congestion window size is as follows:
Figure FDA0002255891360000021
wherein I is the sequence number of the sub-stream, I is the sending state space, and j is the state sequence number in the state space I; max is the number of elements of the feature vector;
Figure FDA0002255891360000022
the congestion window size of the sub-stream I in the jth state in the state space I; mu.sjThe probability of the stationary distribution corresponding to the jth state;
Figure FDA0002255891360000023
is the average congestion window size.
5. The method according to claim 1, wherein the step of calculating the current round trip time value of each sub-flow according to the timestamp field in the data packet further comprises:
smoothing the round trip time value;
the expression of the smoothing process is:
RTTt＝(1-α)RTTnew+αRTTt-1
0<α<1
wherein RTTnewIs the round trip time value of the current moment; RTT (round trip time)t-1Is the previous oneRound trip time value of the moment; RTT (round trip time)tWhich is the smoothed round trip time value, α is the factor by which the smoothed round trip time value is affected by the current round trip time value.
6. The method of claim 5, wherein the impact factor α is 0.8.
7. The method of claim 1, wherein the average goodput rate over each substream is calculated by the expression:
Figure FDA0002255891360000031
wherein p isiIs the packet loss rate on sub-stream i; MSSiIs the maximum transmission segment size on substream i;is the average congestion window size over sub-stream i; RTT (round trip time)iIs the round trip time value on sub-stream i;
Figure FDA0002255891360000033
is the average goodput over substream i.
CN201611221402.XA 2016-12-26 2016-12-26 Data scheduling method of self-adaptive MPTCP Active CN106878192B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201611221402.XA CN106878192B (en) 2016-12-26 2016-12-26 Data scheduling method of self-adaptive MPTCP

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201611221402.XA CN106878192B (en) 2016-12-26 2016-12-26 Data scheduling method of self-adaptive MPTCP

Publications (2)

Publication Number Publication Date
CN106878192A CN106878192A (en) 2017-06-20
CN106878192B true CN106878192B (en) 2020-02-14

Family

ID=59165078

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201611221402.XA Active CN106878192B (en) 2016-12-26 2016-12-26 Data scheduling method of self-adaptive MPTCP

Country Status (1)

Country Link
CN (1) CN106878192B (en)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107733811B (en) * 2017-09-18 2020-02-21 中国电子科技集团公司第五十四研究所 Method for dynamically adjusting coding strength
CN108011780B (en) * 2017-12-01 2019-01-22 北京百度网讯科技有限公司 A kind of message transmission rate measurement method, device, equipment and computer-readable medium
CN108924869B (en) * 2018-07-27 2023-04-07 江西师范大学 Robustness transmission evaluation method based on multipath
CN110266608B (en) * 2019-05-29 2022-08-30 中国石油大学(华东) MPTCP transmission control method based on queue buffer balance factor
CN110535781B (en) * 2019-07-30 2021-08-13 西安交通大学 Flow control method based on window prediction
CN115665060A (en) * 2022-12-26 2023-01-31 中国华能集团清洁能源技术研究院有限公司 Multi-path transmission scheduling method and device for heterogeneous network
CN117674963B (en) * 2023-11-21 2024-07-26 航天恒星科技有限公司 Satellite network multipath data scheduling prediction method, system, equipment and medium

Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101841482A (en) * 2010-05-07 2010-09-22 清华大学 Energy-saving routing method and device for network of data center
CN103888367A (en) * 2014-03-10 2014-06-25 清华大学 Multi-path TCP congestion control method based on packet transmission delay
CN105025524A (en) * 2015-06-09 2015-11-04 北京邮电大学 A multi-path parallel-transmitted data scheduling method and a transmission control protocol
CN105049369A (en) * 2015-08-14 2015-11-11 浙江大学 Video transmission congestion control method based on MPTCP in heterogeneous wireless network
CN105610820A (en) * 2015-12-28 2016-05-25 中国电子科技集团公司第五十四研究所 Multipath transport control protocol (MPTCP) based congestion control method and apparatus
CN105873096A (en) * 2016-03-24 2016-08-17 重庆邮电大学 Optimization method of efficient throughput capacity of multipath parallel transmission system
CN105915466A (en) * 2016-04-15 2016-08-31 北京邮电大学 MPTCP path selection method and apparatus

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101841482A (en) * 2010-05-07 2010-09-22 清华大学 Energy-saving routing method and device for network of data center
CN103888367A (en) * 2014-03-10 2014-06-25 清华大学 Multi-path TCP congestion control method based on packet transmission delay
CN105025524A (en) * 2015-06-09 2015-11-04 北京邮电大学 A multi-path parallel-transmitted data scheduling method and a transmission control protocol
CN105049369A (en) * 2015-08-14 2015-11-11 浙江大学 Video transmission congestion control method based on MPTCP in heterogeneous wireless network
CN105610820A (en) * 2015-12-28 2016-05-25 中国电子科技集团公司第五十四研究所 Multipath transport control protocol (MPTCP) based congestion control method and apparatus
CN105873096A (en) * 2016-03-24 2016-08-17 重庆邮电大学 Optimization method of efficient throughput capacity of multipath parallel transmission system
CN105915466A (en) * 2016-04-15 2016-08-31 北京邮电大学 MPTCP path selection method and apparatus

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
MPTCP联合拥塞控制机制的Markov模型;徐明伟; 张志超;《清华大学学报》;20120915;前言到第4节 *

Also Published As

Publication number Publication date
CN106878192A (en) 2017-06-20

Similar Documents

Publication Publication Date Title
CN106878192B (en) Data scheduling method of self-adaptive MPTCP
US9210063B2 (en) Bandwidth policing apparatus and packet relay apparatus
JP4448341B2 (en) Band control program, method and end system
US20080031149A1 (en) Communications scheduler
US20160308769A1 (en) Setting delay precedence on queues before a bottleneck link based on flow characteristics
US9510354B2 (en) Method and a device for low intrusive fast estimation of the bandwidth available between two IP nodes
JP2006014329A (en) Communication terminal
CN109874031A (en) Multipriority dynamic code rate method of adjustment and system based on network bandwidth prediction
KR20040023719A (en) Method for supporting non-linear, highly scalable increase-decrease congestion control scheme
EP1499073A1 (en) Bit rate control method and device
US20220294727A1 (en) Systems and methods for managing data packet communications
US8565249B2 (en) Queue management system and methods
US9641447B2 (en) Adaptive relative bitrate manager for TCP depending flow control
CN104092625B (en) A kind of self adaptation being used in DCN asks dispatching method in batches
CN111669665B (en) Real-time pushing method of media stream and server
JP3853784B2 (en) Data communication management method
Park et al. Minimizing application-level delay of multi-path TCP in wireless networks: A receiver-centric approach
Huang et al. Packet scheduling and congestion control schemes for multipath datagram congestion control protocol
Pande et al. Study and analysis of different TCP variants
Ko et al. A handover-aware seamless video streaming scheme in heterogeneous wireless networks
WO2014101047A1 (en) Method, device, and system for identifying network packet loss type
CN107733811B (en) Method for dynamically adjusting coding strength
WO2019124290A1 (en) Transmit data volume control device, method, and recording medium
An et al. An adaptive UDT congestion control method with reflecting of the network status
Park et al. A packet scheduling scheme for seamless transmission of life media contents

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