KR20180013597A - Method for controlling a congestion window for multi path TCP in heterogeneous network - Google Patents

Abstract

A congestion window control method of a multi-path transmission control protocol (TCP) in a heterogeneous network, the congestion window control method comprising: increasing a congestion window size when packet transmission / reception is normally performed without packet loss; And decreasing the size of the congestion window when a packet loss occurs, wherein a reduction factor for reducing the size of the congestion window is determined differently according to the throughput of each sub-flow, and the reduction factor of the sub- It is determined to have a larger value than the decrease factor of the lower sub-flow, so that the decrease in the congestion window size of the sub-flow is reduced.
According to the present invention, it is possible to improve the traffic mobility by reducing the recovery time from failure in the path with the smallest congestion, and to increase the throughput of the MPTCP in the heterogeneous network. It also improves fairness in separate bottleneck scenarios for competing TCP and MPTCP protocols, and improves throughput in shared bottleneck scenarios

Description

[0001] The present invention relates to a congestion window control method for a multi-path transmission control protocol (TCP) in a heterogeneous network,

The present invention relates to congestion control of a transmission control protocol (TCP), and more particularly, to a congestion window control method of a multipath transmission protocol (TCP) in a heterogeneous network.

Transmission control protocol (hereinafter referred to as 'TCP') is a transmission protocol applied to a communication network to ensure packet transmission through flow control and congestion control, It provides adaptability. In particular, TCP not only shows low delay and high throughput in a high-speed network, but it also enables seamless service by controlling data flow in a congested network.

TCP uses a mechanism of flow control and congestion control to guarantee end-to-end reliable transmission. Flow control is a method by which the sender adjusts the flow on the network by receiving less advertised window size from the receiver, and congestion control is the method by which the sender controls the flow itself by looking at the network conditions.

However, TCP has a problem in that streaming transmission is difficult in a network with low reliability such as a wireless environment, and a congestion network can not be avoided when a single TCP path uses a congested network.

In order to solve this problem, a multipath transmission control protocol (MPTCP) has been proposed.

Recently, a mobile terminal has a multi-home function, which enables multi-path transmission. MPTCP allows data to be transmitted over multiple paths. In the TCP protocol, congestion control is successfully performed to enable efficient use of Internet functions. This congestion control is done by congestion control algorithm and it is able to actively control the rate according to congestion degree and link capacity.

TCP congestion control is a necessary technique for efficient resource utilization among a large number of network users. The congestion control is a method for congestion control that automatically reduces the transmission performance of the source device based on the gathered context and collects the congestion situation when the context for the congestion is collected. it is possible to utilize network resources smoothly between destinations.

Here, congestion refers to a phenomenon in which certain packets are not correctly processed when a packet exceeding the capability of a router, which is responsible for delivering a packet to another network, is introduced into the network.

Generally, for reliability, TCP sends a sequence number of a packet received by a receiving-side apparatus to a calling apparatus to inform that the packet arrived safely. Here, if the receiving device receives a packet that does not match the order, it sends back a sequence number corresponding to the order to be received to the calling device to inform that the packet has not arrived normally. In this case, when the sequence number of the response received by the source apparatus is the same, it is referred to as a duplicate response, and when receiving a sequence number larger than the previously received sequence, it is referred to as an acknowledgment. In the case of packet loss, many of these duplicated responses occur. Therefore, conventional TCP collects the redundant responses based on the situation and performs congestion control.

In other words, congestion control refers to a technique that resolves congestion that is caused by traffic entering a network device beyond the capabilities it can handle, or traffic concentrated on a particular port, that is, the device is continuously overloaded. The main purpose of TCP congestion control is to directly control the transmission rate of the transmitting terminal to retransmit the lost data due to congestion. TCP is a protocol belonging to the four layers of the OSI reference model, and operates end-to-end regardless of the number of nodes between the transmitting terminal and the receiving terminal. TCP forms a loop that connects the transmitting terminal and the receiving terminal at both ends and transmits the acknowledgment information, the window, and the timeout function transmitted from the receiving side to the loop, Mechanism.

More specifically, if three or more duplicate responses are received for one sequence number for fast congestion control, it is determined that the corresponding packet is lost, and congestion control is performed by determining that the packet has been lost due to congestion in the network . When congestion control occurs, the transmission rate is halved for the session, and the performance is greatly reduced, and the packet determined to be lost is retransmitted.

In general, TCP congestion control algorithms reduce congestion by lowering the transmission rate when packet loss occurs. In the case of multipath, since packets are transmitted through paths having different bandwidths, delays and congestion patterns, not only the inherent functions of congestion control such as fairness and throughput but also traffic shifting, , Load balancing, and so on, must also be satisfied. Therefore, the requirements of Multipath Congestion Control Algorithm (MCCA) are as follows.

First, throughput should be improved. MPTCP should have higher throughput than single-path TCP, which is transmitted at least the best route. Second, there should be no harm to other TCP routes (no harm). MPTCP should operate in a way that does not harm existing TCP. In other words, the bottleneck link should behave like single path TCP. Third, there must be a balance of congestion. MPTCP should use the least congested path.

The first of these requirements indicates that the available path should be used efficiently compared to the single path TCP. The second and third are the fairness, the responsiveness, and the traffic shifting of MPTCP. .

In order to meet such a requirement, the multi-path congestion control algorithm (MCCA) maintains the transmission rate of all sub-flows and must be adjusted to a level that can satisfy the design goal. There are many MPTCP protocols such as Linked Increase Algorithm (LIA), Weighted Vegas (wVegas), and Opportunistic Linked Increase Algorithm (OLIA).

Among the conventional MPTCP protocols, the LIA algorithm, which will be described in the present invention, works very well. However, this algorithm is considered only when a response packet is successfully received in the existing single-path TCP Reno. If packet loss occurs, Nothing has changed. Therefore, it is necessary to improve the algorithm to meet MPTCP design goals when packet loss occurs in MPTCP.

In order to improve the MPTCP congestion control algorithm when packet loss occurs in the MPTCP, the present invention improves the traffic movement by reducing the recovery time from the failure in the path with the least congestion when packet loss occurs And to provide a congestion window control method of a multipath transmission control protocol (TCP) capable of improving the throughput of MPTCP in heterogeneous networks.

According to another aspect of the present invention, there is provided a congestion window control method for a multi-path transmission control protocol (TCP) according to the present invention. The congestion window control method for a multipath transmission control protocol (MPTCP) Increasing the congestion window size; And decreasing a congestion window size when a packet loss occurs, wherein a reduction factor for reducing the size of the congestion window is determined differently according to the throughput of each sub-flow, and the reduction factor of the higher- Is determined to have a larger value than the reduction factor of the lower sub-flow, so that the decrease in the size of the congestion window of the sub-flow is reduced.

The reduction factor is determined differently according to the size ratio of the congestion window to the round trip time (RTT) of each sub-flow,

&Quot; (5) "

Obtaining an average throughput of the MPTCP connection; And calculating the average throughput of the MPTCP with respect to a packet loss occurring in a predetermined sub-flow by using Equation (5).

Wherein the congestion window size is determined by multiplying the current congestion window size by the computed reduction factor.

According to the multi-path TCP transmission congestion control method in the heterogeneous network according to the present invention, it is possible to improve the traffic shift by reducing the recovery time from the failure in the path with the smallest congestion and to improve the traffic rate of the MPTCP in the heterogeneous network, .

In addition, the existing LIA (Linked Increment Algorithm) defines the behavior when packet loss occurs, improves fairness in separate bottleneck scenarios for TCP and MPTCP protocol competition, and improves throughput in shared bottleneck scenarios.

FIG. 1 is a flow chart illustrating an embodiment of a congestion window control method for an MPTCP according to the present invention.
FIG. 2 shows a bottleneck link scenario for explaining the separated bottleneck scenario.
Figure 3 shows the throughput of MPTCP connections using a single path TCP flow and other congestion control algorithms and shows throughput of the entire multipath using two single TCP flows and various congestion control algorithms.
Figure 4 shows a shared link scenario to illustrate a shared bottleneck scenario.
5 compares the throughputs of the congestion control algorithms of the single path TCP and the various MPTCPs in the shared bottleneck scenario.

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. The embodiments described in the present specification and the configurations shown in the drawings are merely preferred embodiments of the present invention and are not intended to represent all of the technical ideas of the present invention and therefore various equivalents And variations are possible.

MPTCP is an extension of TCP standardized by the Internet Engineering Task Force (IETF). MPTCP allows a single TCP to use multiple interfaces on a client or server. MPTCP does not modify applications and can operate on existing Internet. MPTCP spreads traffic to other interfaces between hosts and moves traffic from congested links to other links while balancing them with single-path TCP. What matters in MPTCP is the application layer and network backward compatibility. MPTCP preserve the socket API used by most application layers.

One MPTCP flow has two or more sub-flows, each operating as a single TCP. When the connection is initiated, the MPTCP option is included in the SYN segment, allowing the destination node to verify that it supports MPTCP, and is also used to exchange tokens to identify the connection. For reference, when starting a TCP connection for the first time, a segment called SYN is transmitted to the destination node to start the connection. In order to enable MPTCP access at this time, both the source and the destination must support the MPTCP protocol. Therefore, the MPTCP option is included in the SYN segment and is sent to the destination.

An additional TCP subflow may be associated with the MPTCP, which carries the token that was exchanged in the three-way handshake. MPTCP separates application layer data into all configured sub-flows to maximize the available resources. Multipath congestion control algorithm (MCCA) considers how much traffic is delivered to each sub-flow. Therefore, allocating traffic to each sub-flow determines the efficiency of each algorithm. As described above, various types of congestion control algorithms for implementing the transmission control protocol (TCP) have been proposed, among which LIA is an extension of TCP New Reno. The LIA compensates for the inconsistency of the RTT by considering the round trip time (RTT), which is the time taken for the round trip in the data transmission, from the increase factor of the congestion window size.

Here, New Reno is a protocol of TCP, and LIA is modified by applying this protocol to MPTCP. TCP's flow control is based on the principle that if the state of the link is bad, the packet loss will not occur by lowering the transmission speed, and if the state of the link is further improved, the speed is increased. It is the most basic standard. However, in the case of normal TCP, there is one flow. In MPTCP, since there are two or more flows, the RTT between the two links may be different, so that a discrepancy in transmission speed may occur between the two links. LIA is a complement to this point

[Equation 1]

In Equation (1), a is a parameter of the MPTCP algorithm and indicates the aggressiveness of the MPTCP connection. This value is calculated as shown in Equation (2).

&Quot; (2) "

α =

는

번째 서브 플로우의 혼잡 윈도우 크기이며,

는

번째 서브 플로우의 RTT를 나타낸다. 따라서 LIA는 최적의 자원 관리와 민감성(responsiveness) 사이의 균형을 이루는 것이다. 최근에 LIA의 변형으로 OLIA(Opportunistic Linked Increases Algorithm)가 제안되었으며, 이 알고리즘은 LIA에서 발생하는 “flappy” 현상을 방지할 수 있다. 참고로, MPTCP에서는 다수의 경로가 존재하기 때문에 여러 개의 경로가 좋은 상태이면 트래픽(traffic)이 임의로 아무 경로를 선택해서 전송될 수 있으며, 이러한 현상을 “floppiness”라고 한다. 따라서 이러한 현상은 가능한 제거되어야 한다. 즉 non-flappy가 보장되어야 한다.In Equation 2,

The

Th sub-flow,

The

Th sub-flow. Thus, the LIA is a balance between optimal resource management and responsiveness. Recently, OLIA (Opportunistic Linked Increasing Algorithm) has been proposed as a variant of LIA, and this algorithm can prevent "flappy" phenomenon in LIA. For reference, since there are many paths in MPTCP, if several paths are in good condition, traffic can be arbitrarily selected in any path, and this phenomenon is called "floppiness". Therefore, this phenomenon should be removed as much as possible. That is, non-flappy should be guaranteed.

이 증가한다.For the ACK of each sub-flow r, a congestion window

.

&Quot; (3) "

here,

은 MPTCP 접속의 전체 서브 플로우 수를 나타내며,

는 집합 B에는 속하지만 집합 M에는 속하지 않는 서브 플로우의 수를 나타내고,

는 반대로 집합 M에는 속하지만 집합B에는 속하지 않는 서브 프로우의 수를 나타낸다. 따라서 OLIA에서 링크의 상태는 좋지만 윈도우 크기가 작은 서브 플로우의 윈도우는 빠르게 증가하지만, 최대 윈도우 크기를 갖는 서브 플로우의 윈도우 크기는 그 보다 느리게 증가한다.In Equation (3), B represents an optimal path from the viewpoint of throughput at time t as a set of sub-flows, and M represents a set of sub-flows having the largest congestion window size at time t.

Represents the total number of sub-flows of the MPTCP connection,

Represents the number of sub-flows belonging to set B but not set M,

Represents the number of subroutines belonging to the set M but not belonging to the set B, on the contrary. Therefore, the window of a subflow with a small window size increases rapidly but the window size of a subflow with a maximum window size increases more slowly.

wVegas is an algorithm that extends TCP Vegas. For reference, Vegas is one of the TCP protocols and wVagas is an algorithm that is extended to apply it to MPTCP.

에 의해 계수화된 임계 값(threshold)과 비교해서 혼잡 윈도우 크기를 증가 또는 감소시킨다.This algorithm is a delay-based algorithm for multipath TCP (MPTCP) and uses the queue delay time of the packet as a congestion signal. wVegas assigns a weight factor to the rate of increase or decrease of each sub-flow and adjusts these values according to the degree of congestion. wVegas calculates the sub-flow r for each RTT as shown in Equation 4

To increase or decrease the congestion window size compared to the threshold value that is digitized by the receiver.

&Quot; (4) "

와

는 서브 플로우 r에 대한 최소 RTT와 현재의 RTT를 각각 나타내며,

은 기대 처리율(expected throughput)/전체 처리율(total throughput)의 비율이다.In Equation (4), α and β are threshold values defined in TCP Vegas.

Wow

Represents the minimum RTT and the current RTT for the sub-flow r, respectively,

Is the ratio of expected throughput / total throughput.

FIG. 1 is a flow chart illustrating an embodiment of a congestion window control method for an MPTCP according to the present invention. 1, data is transmitted using a multi-path transmission control protocol (MPTCP) transmission congestion control algorithm in a heterogeneous network (step S100). In step S100, whether a loss occurs in a packet to be transmitted and whether transmission / reception of packet data is normal (Step S110) If the packet transmission / reception is normally performed without packet loss, the congestion window size is increased (Step S120). However, if packet loss occurs, the congestion window size is decreased (Step S130)

At this time, the reduction factor for reducing the size of the congestion window is determined differently depending on the throughput of each sub-flow. That is, the decrease factor of the subflow having a high throughput rate is determined to have a value larger than the decreasing factor of the subflow having a low throughput, so that the decrease in the congestion window size of the subflow is made small. The reduction factor is determined according to the size ratio of the congestion window to the RTT (round trip time) of each sub-flow.

The reduction factor determination may be performed by obtaining the average throughput of the MPTCP connection and obtaining the average throughput of the MPTCP with respect to the packet loss occurring in the predetermined subflow, In this case, the congestion window size is preferably determined by multiplying the current congestion window size by the calculated reduction factor.

The congestion window control method of the MPTCP according to the present invention will be described in more detail. The congestion window control method of the MPTCP according to the present invention focuses on the change of the congestion window size when the packet loss occurs and the congestion balance which is the third necessary condition of the MCCA. This implies that MPTCP should use the least congested link, which reduces the load on the congested path. To this end, the present invention proposes a congestion window control method according to the following technical idea. In other words, the time to recover bandwidth again after congestion occurs in a good subflow is shorter than the time to recover the bandwidth in a bad subflow. Therefore, instead of the decrease factor 0.5 used in the standard TCP, the reduction factor should be determined according to the throughput in each sub-flow. Therefore, in the present invention, the reduction factor? Is defined as follows in one embodiment.

&Quot; (5) "

=

는 혼잡 윈도우 크기

와 RTT 값

를 갖는

서브 플로우의 RTT에 대한 혼잡 윈도우 크기의 비율이며,

는 n개의 서브 플로우를 갖는 MPTCP 접속의 혼잡 윈도우 크기에 대한 RTT의 평균 비율이다. 그리고 수학식 6과 같이 LIA이 적용되었다.In Equation (5)

=

Congestion window size

And the RTT value

Having

The ratio of the congestion window size to the RTT of the subflow,

Is the average ratio of the RTT to the congestion window size of the MPTCP connection with n sub-flows. And LIA is applied as shown in Equation (6).

&Quot; (6) "

=

=

The minimum value in the range of β is used as 0.5, which applies to the low rate for a single transmission or to a congested path on a low rate path. The median of the β coefficient shows that the path with higher throughput than the average will recover the bandwidth faster than the other path. As a result, traffic is transmitted in the least congested path. However, this path also has to reduce the transmission rate if congestion occurs. A high β value of 0.8 means that the transmission rate should be lowered.

ALIA is implemented in a Linux kernel supporting MPTCP as an embodiment of ALIA using the MPTCP congestion window control method according to the present invention. ALIA is basically an extension of LIA. In the congestion window control method of MPTCP according to the present invention, the b coefficient is applied when the window size is reduced due to packet loss. In the congestion avoidance step, not only the additive increase but also the fast retransmission and recovery Is the same as LIA. An important part of the present invention is the ratio between the average throughput of the MPTCP connection and the congested sub-flows. Here, the average throughput of the MPTCP connection refers to a value obtained by averaging the traffic on the MPTCP, and a congested subflow represents a flow in which the throughput or the transmission rate drops due to congestion among the various paths.

This ratio is easily calculated by updating the average throughput of the entire MPTCP connection every time an ACK occurs, as follows:

를 증가시킨다. MPTCP 접속의 평균 처리율을 갱신한다. 경로 r에서 발생한 패킷 손실에 대해서 MPTCP의 평균 처리율을 알아내고, 수학식 5에 의해서 β 계수를 계산한다. 혼잡 윈도우 크기

를 β*

만큼 감소시킨다.For each ACK for path r, the alpha coefficient is updated as in the LIA and the congestion window size < RTI ID = 0.0 >

. Update the average throughput of the MPTCP connection. The average throughput of the MPTCP is calculated for the packet loss occurring at the path r, and the beta coefficient is calculated by the equation (5). Congestion window size

Lt; RTI ID =

.

On the other hand, performance evaluation of ALIA throughput and traffic shifting is performed in heterogeneous networks to meet the purpose of MPTCP and compared with other MPTCP Congestion Control Algorithm (MCCA). Other MPTCP algorithms such as ALIA, LIA, OLIA, and wVegas using the MPTCP congestion window control method according to the present invention are implemented in the Linux kernel. Then, a test bed was constructed and each algorithm was performed in a laboratory environment. The testbed includes routers, switches, etc., as well as hosts that implement the protocol. In addition, we use a software bridge that can run dummynet to generate various RTT delays. Iperf was used on servers and clients to generate and measure traffic.

FIG. 2 shows a bottleneck link scenario for explaining the separated bottleneck scenario. Referring to FIG. 2, the ALIA performance was evaluated in terms of fairness required in the MCCA in the first test bed and compared with the performance of another MCCA, especially the original algorithm of ALIA, LIA. The topology of the test bed is symmetric, and A1-B1 and A2-B2 are bottleneck links, with each link shared with one MPTCP flow. In order to observe the traffic movement effect between the two paths of the algorithm, the load of the two paths is different.

Therefore, the link capacity of the first path A1-B1 is set to 100 Mbps, and the capacity of the second path A2-B2 is changed to 30, 50, 75 and 100 Mbps according to the test case. To adjust the link capacity, we set the desired capacity using the dummynet bridge on the second path. Single path TCP and MPTCP started and ended simultaneously, and observed the throughput (Mb / s) of each connection.

Figure 3 shows the throughput of MPTCP connections using a single path TCP flow and other congestion control algorithms and shows throughput of the entire multipath using two single TCP flows and various congestion control algorithms. Referring to FIG. 3, it can be seen that the multipath access using ALIA exhibits a slightly lower throughput as compared with the use of other algorithms, and in particular, the throughput of the link capacity of three cases is lower than that of the LIA. However, we can see that the throughput of MPTCP is higher than that of other single-path TCPs, and it can be seen that ALIA is friendly to two single-path TCPs compared to other MPTCP algorithms.

This result can be confirmed again in the fairness index calculated in Table 1. Table 1 compares fairness indices for different congestion control algorithms. As shown in Table 1, the fairness index using ALIA is the highest in all tests. The Jain's Fairness Index (JFI) was used to calculate the fairness index for the average user throughput as shown in Equation (7).

&Quot; (7) "

은

번째 접속의 처리율이며, n은 경쟁하는 접속의 수이다.In Equation (7)

silver

Th connection, and n is the number of competing connections.

[Table 1]

Figure 4 shows a shared link scenario to illustrate a shared bottleneck scenario. Referring to FIG. 4, a test bed is configured such that MPTCP having two sub-flows and single-path TCP Cubic share a bottleneck link. In this scenario, we tested whether the throughput of the first MPTCP is better than that of the single-path TCP. In this test bed, all links are set to have a bandwidth of 100 Mbps, and various delays are generated using the dummynet bridge.

Especially, in this scenario, the delay of the first MPTCP subflow and the single path TCP flow are made equal and 100 ms is good. However, the second sub-flow is set to have four delay conditions of 50, 100, 150 and 200 ms. To do this, I used the IP address filter (ipfw) function of the dummynet bridge. In this scenario, single-path TCP and MPTCP flows were started and concurrently started at the same time.

5 compares the throughputs of the congestion control algorithms of the single path TCP and the various MPTCPs in the shared bottleneck scenario. In general, heterogeneous network environments have a large impact on MPTCP. In a good network environment with a delay of less than 100 ms, the performance of MPTCP is higher than that of TCP, but the higher the delay, the lower the throughput or the lower the single-path TCP. This is because the time for processing the reordering of packets received in the receiving buffer is greatly increased. It is not easy to overcome the time delay involved in reordering incoming packets through paths with different characteristics, such as different delays. In multipath TCP, if the packets are received out of order, the throughput is greatly reduced.

However, by using the new β factor, ALIA makes it possible to keep the throughput high when the delay is low or high, by using less congested links. Thus, it can be seen that ALIA improves the throughput by making it possible to use less congested paths more efficiently than other algorithms.

The present invention proposes an Adaptive Linked Increase Algorithm (ALIA) congestion control algorithm, which is an extension of the existing MPTCP algorithm, LIA. In order to evaluate the performance of ALIA, a protocol was implemented in Linux and a throughput and fairness were evaluated by constructing a test bed with the implemented protocol. ALIA performance was compared with other algorithms in separate bottleneck link scenarios and shared bottleneck scenarios in order to compete with TCP and MPTCP protocols. The test results show that the ALIA algorithm using the present invention improves the fairness in the separate bottleneck scenario and improves the throughput in the shared bottleneck scenario.

The present invention can be embodied as a computer readable code on a computer-readable recording medium (including all devices having an information processing function). A computer-readable recording medium includes all kinds of recording apparatuses in which data that can be read by a computer system is stored. Examples of computer-readable recording devices include ROM, RAM, CD-ROM, magnetic tape, floppy disk, optical data storage, and the like.

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, the true scope of the present invention should be determined by the technical idea of the appended claims.

Claims (4)

A congestion window control method of a multipath transmission control protocol (MPTCP)
Increasing the congestion window size if packet transmission / reception is normally performed without packet loss; And
Reducing the congestion window size if packet loss occurs,
The reduction factor that reduces the size of the congestion window is
And the reduction factor of the subflow with a high throughput is determined to be larger than the factor of decrease of the subflow with a low throughput so that the decrease in the size of the congestion window of the subflow becomes small. Congestion Window Control Method of Path Transmission Control Protocol (MPTCP). 2. The method of claim 1,
Wherein the congestion window size is determined differently according to the size ratio of the congestion window to the round trip time (RTT) of each sub-flow. 3. The method of claim 2, wherein the reduction factor is
&Quot; (5) "

Obtaining an average throughput of the MPTCP connection; And
And obtaining the average throughput of the MPTCP for a packet loss occurring in a predetermined sub-flow, and calculating the average throughput of the MPTCP according to Equation (5). 4. The method of claim 3, wherein the congestion window size is
And multiplying the current congestion window size by the computed reduction factor. ≪ RTI ID = 0.0 > 8. < / RTI >

Images