KR20030081254A

KR20030081254A - Tree-based many-to-many reliable multicast congestion control

Info

Publication number: KR20030081254A
Application number: KR1020030065612A
Authority: KR
Inventors: 이동만; 유제영; 강경란
Original assignee: 학교법인 한국정보통신학원
Priority date: 2003-09-22
Filing date: 2003-09-22
Publication date: 2003-10-17

Abstract

일대다 멀티캐스트를 위하여 설계된 종래의 MTCP나 TRAMCC와 같은 트리 기반의 혼잡 제어 기법이 다대다 신뢰적 멀티캐스트에 적용될 때 발생되는 문제점을 해결하기 위해, 본 발명에 따른 트리 기반의 다대다 신뢰적 멀티캐스트 혼잡 제어 기법은 혼잡 윈도우 기법을 기반으로 하며 전송률 제어기를 추가적으로 사용한다.In order to solve the problems caused when conventional tree-based congestion control schemes such as MTCP and TRAMCC, which are designed for one-to-many multicast, are applied to many-to-many multicast, the tree-based many-to-many reliable multi The cast congestion control scheme is based on the congestion window scheme and additionally uses a rate controller.

또한, 본 발명은 혼잡 제어를 위하여 추가적인 피드백 없이 에러 복구를 위한 피드백을 혼잡 제어에 이용함으로써, 수신자들의 처리 부담을 최소화시킬 수 있다.In addition, the present invention can minimize the processing burden of the receiver by using feedback for error recovery in congestion control without additional feedback for congestion control.

본 발명은 동적으로 네트워크 상태의 변화를 반영하는 ACK 타이머와 NACK 타이머 및 빠른 전송률 복구 기법을 통해 세션 내의 흐름들간 공평성을 제공한다.The present invention provides fairness between flows in a session through an ACK timer, a NACK timer, and a fast rate recovery scheme that dynamically reflect changes in network conditions.

Description

Tree-based, many-to-many reliable multicast congestion control scheme {TREE-BASED MANY-TO-MANY RELIABLE MULTICAST CONGESTION CONTROL}

본 발명은 트리 기반의 다대다 신뢰적 멀티캐스트의 혼잡 제어 방법에 관한 것으로, 특히 전송률 제어기와 혼잡 윈도우 기법을 동시에 적용시켜 네트워크 혼잡을 제어하는 트리 기반의 다대다 신뢰적 멀티캐스트의 혼잡제어 기법에 관한 것이다.The present invention relates to a tree-based, many-to-many reliable multicast congestion control method. In particular, the present invention relates to a tree-based, many-to-many reliable multicast congestion control method for controlling network congestion by simultaneously applying a rate controller and a congestion window technique. It is about.

인터넷이 확산됨에 따라 네트워크 가상 환경, 네트워크 게임, 협동 웹 캐싱과 같은 다자간 협동 어플리케이션과 프로세스간 상호 작용 작용이 요구되는 어플리케이션에 대한 관심이 증가하고, 이에 따라 다대다(many-to-many) 신뢰적 멀티캐스트의 필요성이 증대되고 있다.As the Internet proliferates, interest in multi-party collaborative applications, such as network virtual environments, network games, and cooperative web caching, and applications that require inter-process interaction, increases the many-to-many reliability. The need for multicast is increasing.

다대다 멀티캐스트 응용은, VOD나 데이터 분배 등과 같이 송신자와 수신자가 구별되는 일대다 멀티캐스트 응용과 달리 각 참가자가 수신자의 역할뿐만 아니라 송신자의 역할을 담당한다는 특징을 갖는다. 이러한 특징을 고려하여 다대다 세션을 위한 신뢰적 멀티캐스트 프로토콜로 SRM(Scalable Reliable Multicast), LORAX, GAM(Group Aided Multicast)과 같은 ARQ(Automated Repeat Request) 기반의 기법들이 제안되었으며, 이들 중 트리 기반의 프로토콜이 처리 시간 및 대역폭 사용에 있어서 가장 효율적이라는 것이 연구에서 입증되었다.Many-to-many multicast applications, unlike one-to-many multicast applications where senders and receivers are distinguished, such as VOD and data distribution, are characterized by each participant playing the role of sender as well as the receiver. In consideration of these characteristics, Automated Repeat Request (ARQ) -based techniques such as Scalable Reliable Multicast (SRM), LORAX, and Group Aided Multicast (GAM) have been proposed as reliable multicast protocols for many-to-many sessions. Research has shown that the protocol is the most efficient in terms of processing time and bandwidth usage.

이러한 신뢰적 멀티캐스트 프로토콜의 기능 중에서 혼잡 제어(congestion control)는 에러 제어와 함께 가장 핵심적인 기능 중 하나로 간주된다. 적절한 혼잡 제어 기법을 가지지 않은 멀티캐스트 프로토콜은 TCP 흐름에 비해 네트워크 대역폭을 불공평하게 많이 점유하게 되고, 결국에는 네트워크 동작이 중단되는 문제 상황(congestion collapse)을 일으킬 수 있다. 그러므로, 혼잡 제어 기법에서는 회선 상에 공존하는 TCP 흐름과의 공평한 대역폭 사용을 보장할 수 있어야한다. 그리고, 멀티캐스트에서의 혼잡 제어는, 멀티캐스트 세션 내 하나의 수신자들이 서로 상이한 네트워크 환경에 존재하기 때문에, 유니캐스트에서의 혼잡 제어 기법과는 달리 수신자의 네트워크 송수신 능력 등의 상이성이 중요하게 다루어져야 한다.Among the functions of this reliable multicast protocol, congestion control is considered one of the most essential functions along with error control. Multicast protocols without proper congestion control techniques may unfairly occupy much more network bandwidth than TCP flows, and can eventually cause congestion collapse. Therefore, the congestion control scheme should be able to guarantee fair bandwidth usage with TCP flows coexisting on the circuit. In the multicast congestion control, since one receiver in a multicast session exists in a different network environment, unlike the congestion control scheme in unicast, the difference in the receiver's network transmission / reception capability is important. You must lose.

이러한 요구 사항들을 기반으로, 트리 기반의 신뢰적 멀티캐스트를 위한 MTCP 또는 TRAMCC와 같은 단일 전송률 혼잡 제어 기법들이 제안되었다. MTCP와 TRAMCC에서는 복구 트리를 따라 수신자들로부터의 피드백들이 종합되어 송신자에게 전달되기 때문에 수신자들의 상이한 환경에 따른 문제를 해결한다. 그리고, TCP와 유사하게 수신자의 혼잡 윈도우 정보를 사용하여 AIMD(Additive Increase Multiplicative Decrease) 원칙에 따라 증가 시에는 일정량만큼 증가시키고, 감소 시에는 배수로 감소시키기 때문에 TCP 흐름과의 공평한 대역폭 할당을 유지한다.Based on these requirements, single rate congestion control schemes such as MTCP or TRAMCC for tree-based reliable multicast have been proposed. In MTCP and TRAMCC, feedback from receivers is aggregated along the recovery tree and forwarded to the sender, which solves the problem of different environments of receivers. Similarly to TCP, the receiver uses congestion window information to increase the amount by a certain amount when increasing and decreases by multiple when decreasing according to the principle of Additive Increase Multiplicative Decrease (AIMD).

이하에서는, 트리 기반의 단일 전송률 신뢰적 멀티캐스트를 위한 혼잡 제어 기법인 MTCP와 TRAMCC를 설명한다.The following describes MTCP and TRAMCC, which are congestion control schemes for tree-based single rate reliable multicast.

MTCP는 윈도우 기반의 혼잡 제어 기법을 사용하는 멀티캐스트 프로토콜이다. 혼잡 제어를 위하여, MTCP는 복구 트리의 말단 노드를 제외한 모든 노드가 혼잡 윈도우와 전송 윈도우를 관리한다. 혼잡 윈도우의 크기는 슬로우 스타트 및 혼잡 회피 알고리즘을 포함하여 TCP와 비슷하게 관리된다. 전송 윈도우는 자식 노드를로부터 응답되지 않은 패킷의 수를 나타내며, 그 크기는 송신자로부터 새로운 패킷을 받을 때마다 증가하며, 자식 노드로부터 ACK(ACKnowledgement)을 받을 때마다 감소한다. 각 노드는 복구 트리의 부모 노드에게 혼잡 요약을 각 ACK에 포함하여 전송하며, 이때 혼잡 요약에는 자신과 자신의 자식 노드들의 혼잡 윈도우 크기의 최소값(minCwnd) 및 전송 윈도우 크기의 최대값(maxTwnd)이 포함되어 있다. 송신자는 혼잡 요약 정보를 토대로 minCwnd와 maxTwnd의 차이만큼의 데이터 패킷만을 전송한다.MTCP is a multicast protocol that uses a Windows-based congestion control scheme. For congestion control, MTCP manages congestion windows and transmission windows except for the end nodes of the recovery tree. The size of the congestion window is managed similar to TCP, including slow start and congestion avoidance algorithms. The transmission window represents the number of unanswered packets from the child node, and its size increases each time a new packet is received from the sender, and decreases each time an ACK (ACKnowledgement) is received from the child node. Each node sends a congestion summary to each parent node of the recovery tree in each ACK.The congestion summary includes the minimum value of the congestion window size (minCwnd) and the maximum transmission window size (maxTwnd) of itself and its children. Included. The sender transmits only data packets corresponding to the difference between minCwnd and maxTwnd based on the congestion summary information.

TRAMCC는 TRAM을 위한 혼잡 제어 기법으로, 윈도우 기반의 혼잡 제어 기법과 함께 전송율 제어기를 사용한다. 송신자는 수신자들의 혼잡 윈도우가 계속 열려 있는 상태가 되도록 조절한다. TRAMCC는 기본적으로 피드백 및 피드백 조합 부분, 윈도우 조절 부분, 전송률 조절 부분으로 이루어져 있으며, 혼잡 윈도우의 크기는 각 수신자에서 관리된다. 수신자가 혼잡을 인식할 때마다 AIMD 방식으로, 즉 증가 시에는 일정량만큼 증가시키고, 감소 시에는 배수로 감소시킨다. TRAMCC에서 ACK 윈도우는 ACK을 수신하지 않고 한 번에 전송 가능한 패킷들을 의미한다. 그리고, 모든 자식 노드로부터 ACK을 수신한 후에야 복구 트리의 부모 노드에게 ACK를 전송한다.TRAMCC is a congestion control scheme for TRAMs that uses a rate controller with a window-based congestion control scheme. The sender adjusts the receiver's congestion window to remain open. TRAMCC basically consists of feedback, feedback combination, window adjustment, and rate adjustment. The size of the congestion window is managed in each receiver. Whenever the receiver perceives congestion, it increases by a certain amount in the AIMD manner, i.e. increases, and decreases in multiples when reduced. The ACK window in the TRAMCC means packets that can be transmitted at one time without receiving an ACK. The ACK is transmitted to the parent node of the recovery tree only after receiving the ACK from all child nodes.

TRAMCC에서는 현재의 ACK 윈도우 동안의 손실된 데이터 패킷의 수가 바로 전 ACK 윈도우보다 많고, ACK 윈도우의 25% 이상의 데이터 패킷을 손실했을 경우를 혼잡이라고 판단한다.The TRAMCC determines that the number of lost data packets during the current ACK window is larger than the previous ACK window, and that more than 25% of the data packets of the ACK window are lost.

수신자가 혼잡을 인식하면, 혼잡 윈도우의 크기는 현재 크기의 4분의 1로 줄어들며, 그렇지 않을 경우, 두 패킷만큼 증가한다. 수신자로부터의 매 피드백에는 수신자의 혼잡 윈도우의 크기에 대한 정보로서, 연속적으로 받은 패킷 중 가장 높은 패킷 순서 번호와, 수신자가 현재 받을 수 있는 가장 높은 패킷 순서 번호가 포함된다. 전송률은 송신자가 매 ACK 윈도우만큼의 패킷을 보낼 때마다 최근 5초 동안의 평균 전송률을 기준으로 조절된다.If the receiver recognizes congestion, the size of the congestion window is reduced to one quarter of its current size, otherwise it increases by two packets. Each feedback from the receiver includes information about the size of the receiver's congestion window, including the highest packet sequence number of consecutive packets received and the highest packet sequence number currently received by the receiver. The rate is adjusted based on the average rate over the last five seconds each time a sender sends out packets for every ACK window.

어떤 순간에 송신자가 수신자들로부터의 ACK 없이 보낼 수 있는 최대 패킷 수를 ‘열린 윈도우’라고 정의하고, 이 열린 윈도우 크기의 평균이 지난 두 ACK윈도우 동안 증가했을 경우, 전송률을 증가시키고, 그렇지 않을 경우 최근 5초 동안의 전송률을 그대로 유지한다.Define the maximum number of packets that a sender can send at any moment without an ACK from the receivers as an 'open window', and if the average of these open window sizes has increased over the last two ACK windows, then increase the transfer rate, otherwise The transmission rate for the last 5 seconds is maintained.

위의 설명에서와 같이, MTCP와 TRMACC는 근본적으로 일대다 신뢰적 멀티캐스트를 위하여 설계되어 송신자의 처리 부담을 다중의 수신자들에게 분담시킴으로써 전체적으로 참가자들의 처리 부담을 감소시키는 효과가 있지만, 신뢰적 전송을 위해 송신자에게 부과되는 처리 부담을 X라 하고 수신자에게 부과되는 처리 부담을 Y라 할 때, 참가자의 수가 N인 다대다 세션에서 하나의 참가자가 다른 참가자들과 데이터를 주고받는데 드는 총 처리 부담은 X+(N-1)*Y가 된다. 따라서, 다대다 세션에서 참가자 수가 늘어날수록 수신자의 처리 부담이 비례적으로 증가되는 문제점이 있다.As described above, MTCP and TRMACC are fundamentally designed for one-to-many reliable multicast, sharing the sender's processing burden with multiple recipients, reducing the overall processing burden of participants, but with reliable transmission. If we assume that the processing burden imposed on the sender for X and the processing burden imposed on the receiver for Y is the total processing burden for one participant to exchange data with other participants in a many-to-many session with N participants It becomes X + (N-1) * Y. Thus, as the number of participants increases in the many-to-many session, the processing burden of the receiver increases proportionally.

예를 들어 MTCP의 경우를 살펴보면, 각 수신자가 매 송신자들에 대해 해당 송신자들이 전송률을 조절하게 하기 위하여 거의 모든 데이터 패킷에 대하여 ACK을 생성해야만 하므로, 수신자의 처리 부담이 송신자의 수가 증가함에 따라 함께 증가하며, 특히 복구 트리의 중간에 위치한 수신자들은 개별 송신자로 전달되는 ACK들을 종합해야 하기 때문에 처리 부담이 심각하게 증가하여 다대다 세션을 위한 혼잡 제어 기법으로 사용하기 어렵다.For example, in the case of MTCP, each receiver must generate an ACK for almost every data packet in order for the senders to adjust the rate for each sender, so that the receiver's processing burden increases as the number of senders increases. In particular, since the receivers located in the middle of the recovery tree have to aggregate ACKs delivered to individual senders, the processing burden is seriously increased and it is difficult to use it as a congestion control scheme for many-to-many sessions.

또한, TRMACC는 혼잡 제어 윈도우와 더불어 전송률 제어기를 사용하기 때문에 세션 참가자 수 증가로 인한 처리 부담 증가는 MTCP만큼 크지 않으나 전송률 조절 기법에서 한 회선 내에서 대역폭을 경쟁하는 흐름들을 고려하지 않기 때문에 서로 경쟁하는 흐름들이 공평한 대역폭 분할에 대응되는 전송률을 회복하는데 많은시간이 걸리거나 공평한 상태를 유지하지 못하게 된다. 특히, TRMACC가 다대다 세션에 적용되는 경우에 다대다 세션에서는 하나의 회선을 여러 데이터 흐름과 제어 흐름이 공유하게 되어 제한된 대역폭에 대한 경쟁이 일대다 세션에 비해 크게 증가하게 되고, 이로 인하여 데이터의 손실뿐만 아니라 피드백과 재전송 패킷의 손실을 가져오게 되어 혼잡 제어 기법이 올바르게 동작하지 못하게 되는 문제점이 있다.In addition, since TRMACC uses a rate controller with a congestion control window, the increased processing burden due to an increase in the number of session participants is not as great as MTCP, but the rate-adjusting technique does not consider the flows competing for bandwidth within a line. The flows may take a long time or may not remain fair to recover the rate corresponding to the fair bandwidth division. In particular, when TRMACC is applied to many-to-many sessions, in many-to-many sessions, multiple data flows and control flows are shared by one circuit, thereby increasing competition for limited bandwidth significantly compared to one-to-many sessions. In addition to the loss, there is a problem that the congestion control technique does not work properly because it brings about loss of feedback and retransmission packets.

이와 같이, 다대다 신뢰적 멀티캐스트 세션의 개별 참가자는 송신자임과 동시에 다른 참가자들의 수신자이기 때문에 송신자의 처리 부담을 단순히 수신자들에게 분산시키는 기법이 언제나 전체 세션 효율을 증가시킨다고 볼 수 없다. 그리고, 하나의 다대다 세션에서는 데이터 흐름과 제어 흐름들이 하나의 회선을 공유하며 대역폭을 경쟁할 수 있다. 이것은 피드백이나 재전송 패킷의 손실을 증가시킬 수 있으며, 순간적으로 일부의 데이터 흐름이 다른 데이터 흐름에 비해 더 많은 손실을 겪을 수 있는 문제점이 있다. 이러한 문제 상황에 효율적으로 대처하지 못할 경우, 세션 내의 흐름간의 불공평한 전송률을 야기할 가능성이 크다As such, since individual participants in a many-to-many multicast session are both senders and recipients of other participants, the technique of simply distributing the sender's processing burden to the receivers does not always increase the overall session efficiency. And in one many-to-many session, data flows and control flows can share a circuit and compete for bandwidth. This may increase the loss of feedback or retransmission packets, and at the moment there is a problem that some data flows may suffer more losses than other data flows. Failure to deal effectively with these problem situations is likely to cause unfair transfer rates between flows within a session.

트리 기반의 다대다 멀티캐스트 세션을 위한 혼잡 제어 기법 설계 시에 아래의 네 가지 사항이 고려되어야 한다.When designing a congestion control scheme for a tree-based many-to-many multicast session, the following four points should be considered.

첫째, 에러 복구와 함께 혼잡 제어를 위한 처리 부담은 각 참가자들에게 골고루 분산되어야 한다.First, the processing burden for congestion control with error recovery should be evenly distributed to each participant.

둘째, 신뢰적 멀티캐스트 프로토콜은 이미 에러 복구를 위한 피드백 패킷에 대한 처리 부담을 가지므로, 혼잡 제어를 위한 처리 부담을 추가하는 것을 피해야 한다. 즉, 혼잡 제어 기법은 에러 복구를 위한 기존의 피드백을 최대한 이용할 수있어야 한다.Second, since the reliable multicast protocol already has a processing burden on feedback packets for error recovery, it should be avoided adding processing burden for congestion control. In other words, the congestion control technique should make full use of existing feedback for error recovery.

셋째, 피드백과 재전송 패킷의 손실을 효과적으로 대처하기 위하여 ACK 타이머와 NACK 타이머를 사용하되, 각 타이머 값의 동적 추정 알고리즘이 제공되어야 한다. 이때, 너무 짧은 타이머 값은 네트워크를 중복된 피드백이나 재전송 패킷으로 채울 가능성이 있으며, 너무 긴 타이머 값은 혼잡 제어 기법의 반응을 느리게 함으로써 네트워크 상태의 변화에 대한 적응을 느리게 만들 수 있다.Third, in order to effectively cope with the loss of feedback and retransmission packets, an ACK timer and a NACK timer are used, but a dynamic estimation algorithm of each timer value should be provided. In this case, too short timer value may fill the network with duplicate feedback or retransmission packets, and too long timer value may slow down the response of the congestion control scheme to slow the adaptation to changes in network conditions.

넷째, 하나의 회선에 공존하며 대역폭을 경쟁하는 흐름의 수가 증가함에 따라 순간적으로 하나의 흐름은 다른 흐름들보다 높은 손실률을 나타낼 수 있으며, 피드백 손실로 인해 송신자가 전송률 제어를 효과적으로 진행하지 못하는 경우가 발생할 수 있다. 따라서, 전송률 조정 알고리즘은 개별 흐름들이 세션 내 흐름들의 공평한 전송률로 빨리 복구될 수 있도록 설계되어야 한다.Fourth, as the number of flows coexisting on one circuit and competing for bandwidth increases, one flow may have a higher loss rate than other flows at the moment, and the sender may not be able to effectively control the rate due to feedback loss. May occur. Therefore, the rate adjustment algorithm should be designed so that individual flows can be quickly recovered at the fair rate of flows in the session.

본 발명의 목적은 이와 같은 종래 기술의 문제점을 해결하기 위한 것으로, 전송률 제어기를 동반한 혼잡 윈도우 기법을 사용하고 ACK과 NACK을 이용하여 혼잡 제어를 수행함으로써, 자체 시간 조절 기능의 상실 문제 및 수신자의 처리 부담을 최소화할 수 있는 트리 기반의 다대다 신뢰적 멀티캐스트의 혼잡제어 기법을 제공하고자 한다.An object of the present invention is to solve the problems of the prior art, by using a congestion window technique with a rate controller and performing congestion control using ACK and NACK, the problem of loss of self-time adjustment function and We aim to provide a tree-based, many-to-many reliable multicast congestion control scheme that can minimize processing burden.

또한, 본 발명의 다른 목적은, 수신자들로부터 피드백이 도착하지 않아 데이터 패킷 전송이 일시적으로 중단된 경우와 송신자의 전송률 조절에 있어서 실제 적용된 전송률과 예상 전송률을 기반으로 다음 전송률을 계산함으로써, 피드백과 재전송 패킷의 손실에 발생되는 문제 상황을 해결할 수 있는 트리 기반의 다대다 신뢰적 멀티캐스트의 혼잡 제어 기법을 제공하고자 한다.In addition, another object of the present invention is to calculate the next transmission rate based on the actual transmission rate and the expected transmission rate when the data packet transmission is temporarily stopped due to no feedback from the receivers, and in the transmission rate adjustment of the sender, We aim to provide a tree-based, many-to-many reliable multicast congestion control scheme that can solve the problem caused by the loss of retransmission packets.

상기와 같은 목적을 달성하기 위하여 본 발명은, 송신자로부터 ACK 윈도우만큼의 연속적인 데이터 패킷을 성공적으로 수신할 때마다 복구 트리 상의 부모 노드에 ACK을 전송하며, 데이터 패킷 손실이 발견될 때마다 NACK을 전송하는 수신자를 포함하는 트리 기반의 다대다 신뢰적 멀티캐스트의 혼잡 제어 기법에 있어서, 상기 수신자가 수신한 연속적인 데이터 패킷의 마지막 순서 번호(W_L)와 상기 수신자와 자신의 자식의 노드의 최대 허용 데이터 패킷 순서 번호 중에서 최소값(W_R)을 상기 ACK과 NACK에 포함시켜 상기 송신자에게 전송하는 단계와, 상기 ACK과 NACK에 포함된 W_L과 W_R의 차이로 상기 수신자의 혼잡 윈도우 크기를 추정하고, 상기 W_R을 이용하여 상기 송신자가 전송할 수 있는 패킷의 최대 순서 번호로 이용하는 단계를 포함한다.In order to achieve the above object, the present invention transmits an ACK to the parent node on the recovery tree every time a successful reception of consecutive data packets of the ACK window from the sender, and generates a NACK whenever a data packet loss is found. In a tree-based, many-to-many reliable multicast congestion control scheme that includes a transmitting receiver, the last sequence number (W _L ) of consecutive data packets received by the receiver and the maximum number of nodes of the receiver and its children. Estimating a congestion window size of the receiver by including a minimum value (W _R ) among allowed data packet sequence numbers in the ACK and NACK and transmitting the same to the sender, and a difference between W _L and W _R included in the ACK and NACK. And using the W _R as the maximum sequence number of a packet that can be transmitted by the sender.

또한, 본 발명은, 각 송신자 n(n=1, 2, 3,…)에 대하여 혼잡 윈도우 크기인 CW(n)을 관리하고, 피드백 시에 혼잡 윈도우 정보를 세션 내의 부모 노드에게 제공하는 수신자의 혼잡 윈도우 조절 방법에 있어서, 상기 세션 시작 시에 초기 혼잡 윈도우의 크기인 CW(n, 0)를 ‘3×AW(ACK 윈도우의 크기)’로 설정하는 단계와, 상기 송신자로부터 연속적으로 받은 패킷의 최대 순서 번호가 상기 수신자가 ACK을 전송할 시점에 도달하는 동안 데이터 패킷 손실 여부를 판단하는 단계와, 상기 판단 결과, 상기 데이터 패킷의 손실이 있는 경우 복구 트리 상의 부모 노드에게NACK을 전송함과 더불어 상기 송신자의 혼잡 윈도우의 크기를 감소시키고, 상기 데이터 패킷의 손실이 없는 경우 상기 송신자에게 ACK을 전송함과 더불어 상기 송신자의 혼잡 윈도우 크기를 증가시키는 단계를 포함한다.In addition, the present invention manages CW (n), which is the congestion window size, for each sender n (n = 1, 2, 3, ...), and provides the congestion window information to the parent node in the session upon feedback. A congestion window control method, comprising: setting CW (n, 0), which is the size of an initial congestion window at a start of the session, to '3 × AW (size of an ACK window)', and sequentially receiving packets from the sender. Determining whether a data packet is lost while the maximum sequence number reaches a time point at which the receiver transmits an ACK; and if the data packet is lost, transmitting a NACK to a parent node on a recovery tree. Reducing the size of the sender's congestion window and sending an ACK to the sender if there is no loss of the data packet and increasing the sender's congestion window size; It includes.

또한, 본 발명은, 최대 전송률과 최소 전송률로 제한되는 범위 안에서 전송률을 결정하는 송신자의 전송률 조절 방법에 있어서, 세션이 시작할 때 슬로우 스타트 단계로서 i번째 ACK 윈도우에 대응되는 데이터 패킷을 전송한 다음 ACK 윈도우에 대응되는 데이터 패킷을 전송하기 위한 전송률을 수학식 : R_e(i+1)=R_e(i) + △R(i) + r (r=1킬로바이트, i=0,1,2,3 …)로 결정하며, 상기 전송률이 최대 전송률에 도달하거나 상기 송신자가 전송하는 패킷의 순서 번호가 최대 허용 패킷 순서 번호(W_R)에 처음 도달하거나 수신자로부터 NACK을 전송받거나 ACK 타이머가 만료되면 상기 슬로우 스타트 단계를 중지하고, 두 개의 ACK 윈도우 사이의 평균 열린 윈도우 크기(W_o(i) : i번째의 ACK 윈도우의 평균 열린 윈도우 크기)의 변화 상태에 따라 전송률 조절하는 안정 상태 단계로 전환하는 단계를 포함하며, 상기 안정 상태 단계는, 이전 ACK 윈도우 동안 열린 윈도우의 크기가 '0'인 경우 지난 ACK 윈도우에 대한 전송률(R_e(i))과 실제 측정된 전송률(R(i))로 새 ACK 윈도우에 적용할 전송률을 결정하는 단계와, 상기 열린 윈도우 크기가 증가하는 경우(W_o(i)≥W_o(i-1))에 전송률을 증가시키고, 상기 열린 윈도우의 크기가 감소하는 경우에 네트워크 혼잡 상태로 판단하여 전송률을 감소하는 단계를 포함한다.In addition, the present invention, in the rate control method of the sender to determine the transmission rate within the range limited to the maximum rate and the minimum rate, transmitting a data packet corresponding to the i th ACK window as a slow start step at the beginning of the session and then ACK The transmission rate for transmitting the data packet corresponding to the window is expressed as: R _e (i + 1) = R _e (i) + ΔR (i) + r (r = 1 kilobyte, i = 0,1,2, 3…), and if the rate reaches the maximum rate or if the sequence number of the packet transmitted by the sender first reaches the maximum allowed packet sequence number (W _R ), or receives a NACK from the receiver or the ACK timer expires; stopping the slow start phase, and both the average size of the open windows between the two ACK window: in a steady-state step of rate control according to a change of state (W _o (i) the average size of the open window of the i-th ACK window) Comprising the step of ring, the steady-state step, if the size of the open windows for the previous ACK window is '0' data rate for the last ACK window (R _e (i)) and the actual measured transmission rate (R (i) Determining a transmission rate to be applied to the new ACK window, increasing the transmission rate when the open window size increases (W _o (i) ≥ W _o (i-1)), and Determining the network congestion in the case of decreasing, thereby reducing the transmission rate.

도 1은 본 발명이 적용될 네트워크 환경을 도시한 도면이고,1 is a diagram illustrating a network environment to which the present invention is applied.

도 2는 본 발명이 적용된 후 세션 내 참가자들간 공평성을 도시한 그래프이고,2 is a graph showing fairness among participants in a session after the present invention is applied,

도 3은 본 발명과 TCP의 친화성을 도시한 그래프이다.3 is a graph showing the affinity between the present invention and TCP.

＜도면의 주요부분에 대한 부호의 설명＞<Description of the code | symbol about the principal part of drawing>

100, 110, 120 : 라우터 1, 2, 3100, 110, 120: Router 1, 2, 3

131, 132, 133, 134 : GAM 1, 2, 3, 4131, 132, 133, 134: GAM 1, 2, 3, 4

140, 142 : GAM 코어1, 2140, 142: GAM Core 1, 2

이하에서 첨부한 도면을 참조하여 바람직한 실시 예에 대하여 상세히 설명하기로 한다.Hereinafter, exemplary embodiments will be described in detail with reference to the accompanying drawings.

본 발명의 트리 기반의 다대다 신뢰적 멀티캐스트의 혼잡제어 기법(TMRCC : Tree-based Many-to-many Reliable multicast Congestion Control)은 TRAMCC와 같이 단일 전송률의 전송률 제어기를 가진 윈도우 기반의 혼잡 제어 기법이며, 혼잡 제어 기법과 함께 사용되는 에러 복구 기법으로써 Hu 기법을 가정한다. 이때, Hu 기법은 유니캐스트, NACK/재전송, 정기적 ACK을 사용하는 신뢰적 멀티캐스트 프로토콜을 가리킨다.The tree-based many-to-many reliable multicast congestion control (TMRCC) of the present invention is a window-based congestion control scheme with a single rate-rate rate controller, such as TRAMCC. In this case, we assume the Hu method as the error recovery method used with the congestion control method. In this case, the Hu scheme refers to a reliable multicast protocol using unicast, NACK / retransmission, and periodic ACK.

이러한 Hu 기법에서 송신자는 데이터 패킷을 세션에 멀티캐스트하며, 수신자는 패킷 손실을 발견할 때마다 NACK 타이머를 설정하고 복구 트리에서의 부모 노드에게 NACK을 전송한다. 부모 노드는 NACK을 받으면 자식 노드에게 복구 패킷을 유니캐스트하고, 복구 패킷을 수신하지 못하고 NACK 타이머가 종료되었을 경우 수신자는 패킷 손실을 처음 발견한 때와 동일하게 다시 NACK 타이머를 설정하고 NACK을 전송한다.In this Hu scheme, the sender multicasts data packets to the session, and the receiver sets a NACK timer and sends a NACK to the parent node in the recovery tree whenever a packet is found. When the parent node receives the NACK, it unicasts the recovery packet to the child node.If the parent node does not receive the recovery packet and the NACK timer expires, the receiver sets the NACK timer again and transmits the NACK in the same manner as when the packet was first detected. .

복구 트리의 자식 노드가 부모 노드에게 ACK을 유니캐스트하면, 부모 노드는 유지하고 있던 데이터 패킷들을 안전하게 메모리에서 삭제할 수 있다.If a child node of the recovery tree unicasts an ACK to the parent node, the parent node can safely delete the data packets it has held in memory.

본 발명의 트리 기반의 다대다 신뢰적 멀티캐스트의 혼잡제어 기법은 크게 수신자 피드백과 혼잡 윈도우 조절, 전송률 조절로 나눌 수 있으며, 이에 대한 설명은 아래와 같다.The tree-based, many-to-many reliable multicast congestion control scheme of the present invention can be largely divided into receiver feedback, congestion window control, and rate control.

먼저, 수신자 피드백에 관하여 설명하면, 트리 기반의 다대다 신뢰적 멀티캐스트의 혼잡제어 기법은 수신자로부터 피드백되어 온 정보, ACK과 NACK을 에러 복구뿐만 아니라 혼잡 제어를 위하여 사용한다.First, with respect to receiver feedback, the tree-based many-to-many reliable multicast congestion control scheme uses information fed back from the receiver, ACK and NACK for congestion control as well as error recovery.

정상적인 상황에서 연속적으로 받은 데이터 패킷의 수가 ACK 윈도우에 도달할 경우 각 수신자는 복구 트리의 부모 노드에게 ACK을 보내고, 데이터 패킷 손실이 발견되면 즉시 부모 노드에게 NACK을 전송한다. 이때 ACK을 전송하는 경우에 조건은 아래의 수학식 1과 같다.Under normal circumstances, when the number of received data packets reaches the ACK window, each receiver sends an ACK to the parent node of the recovery tree, and immediately sends a NACK to the parent node when data packet loss is found. In this case, the condition in the case of transmitting the ACK is shown in Equation 1 below.

여기서, W_L(n, i)은 i 번째 ACK에서 보고하는 연속적으로 수신된 패킷의 최대 순서 번호를 의미하며, AW는 ACK 윈도우의 크기를 나타낸다. 송신자 n에 대한 각 수신자의 W_R(n)은 W_L(n)과 송신자 n에 대한 혼잡 윈도우의 크기의 합으로 계산된다. 즉, 혼잡 윈도우의 크기는 W_R(n)과 W_L(n)간의 차이를 이용하여 산출할 수 있다.Here, W _L (n, i) means the maximum sequence number of consecutively received packets reported by the i-th ACK, AW represents the size of the ACK window. W _R (n) of each receiver for sender n is calculated as the sum of W _L (n) and the size of the congestion window for sender n. That is, the size of the congestion window can be calculated using the difference between W _R (n) and W _L (n).

ACK와 NACK은 수신자의 혼잡 윈도우에 대한 정보로서, 다음의 두 가지 값을 포함한다. 수신자가 연속적으로 수신한 데이터 패킷의 마지막 순서 번호(W_L)와 자신과 자신의 자식 노드의 최대 허용 데이터 패킷 순서 번호의 최소값(W_R)이다. 즉, 트리 기반의 다대다 신뢰적 멀티캐스트의 혼잡제어 기법은 혼잡 윈도우의 크기를 W_R과 W_L의 차이로 추정할 수 있다.ACK and NACK are information on the congestion window of the receiver and include the following two values. The last sequence number (W _L ) of data packets consecutively received by the receiver and the minimum value (W _R ) of the maximum allowable data packet sequence number of itself and its child nodes. That is, the tree-based many-to-many reliable multicast congestion control technique can estimate the size of the congestion window as the difference between W _R and W _L.

이러한 수신자로부터 제공되는 피드백 정보는 복구 트리를 따라 종합되기 때문에 최종적으로 송신자에게 전달되는 W_R은 세션 내에서 해당 송신자에 대한 전체 수신자의 W_R중 최소값이 된다.The feedback information provided from these receivers is aggregated along the recovery tree, so that W _R finally delivered to the sender is the minimum of all recipients' W _Rs for that sender within the session.

송신자는 자신의 자식 노드들로부터 전달받은 W_R(n) 값들 중 최소값을 자신이 전송할 수 있는 패킷의 최대 순서 번호로 사용한다.The sender uses the minimum value of W _R (n) values received from its child nodes as the maximum sequence number of the packet that can be transmitted.

TMRCC에서는 피드백과 복구 패킷의 손실에 효과적으로 대처하기 위하여 ACK 타이머와 NACK 타이머 값을 동적으로 변경한다. 송신자에서는 ACK의 손실을 인지하기 위해 ACK 타이머를 사용하고, ACK 타이머가 만료되었을 경우 송신자는 복구 트리 상에서 아직 ACK을 전송하지 않은 자식 노드에게 ACK을 명시적으로 요청한다. 이것은 모든 수신자로부터 ACK를 수신하게 될 때까지 복구 트리를 따라 반복적으로 수행된다.The TMRCC dynamically changes the ACK timer and NACK timer values to cope with the loss of feedback and recovery packets. The sender uses the ACK timer to recognize the loss of the ACK. When the ACK timer expires, the sender explicitly requests an ACK from the child node that has not yet sent an ACK on the recovery tree. This is done repeatedly along the recovery tree until it receives ACKs from all receivers.

송신자는 이러한 ACK 타이머 값의 올바른 선택을 위하여, ACK 응답 시간(ACK Response Time, ART)을 측정한다. 이때 ACK 응답 시간이란 ACK 윈도우의 마지막 패킷이 전송된 후부터 복구 트리의 모든 자식 노드들로부터 해당 ACK 윈도우에 대한 ACK을 받기까지의 시간을 의미한다. 다음 ACK 윈도우에 사용될 추정 ART(ART_e)는 아래의 수학식 2에서 표현된 바와 같이 관측된 ART와 이전 ACK 타이머 값을 위해 계산된 추정 ART를 사용한 EWMA(Exponentially Weighted Moving Average)로 계산된다.The sender measures the ACK Response Time (ART) for the correct selection of this ACK timer value. In this case, the ACK response time means a time from when the last packet of the ACK window is transmitted until receiving an ACK for the corresponding ACK window from all child nodes of the recovery tree. The estimated ART (ART _e ) to be used for the next ACK window is calculated as EWMA (Exponentially Weighted Moving Average) using the estimated ART calculated for the observed ART and the previous ACK timer value as represented by Equation 2 below.

일반적으로 네트웍상 노드들의 최대 RTT는 500ms를 넘지 않는다고 가정할 수 있기 때문에 초기 추정 ART인 ART_e(0)는 500ms로 설정되고, 본 발명의 TMRCC에서는 ??를 TCP에서 ACK 타이머값을 설정할 때 일반적으로 사용되는 값과 같이 0.1로 설정한다. (i+1)번째 ACK을 위해 실제 사용되는 ACK 타임아웃 값(ATO)은 아래의 수학식 3과 같다.In general, since it can be assumed that the maximum RTT of the nodes on the network does not exceed 500 ms, the initial estimated ART ART _e (0) is set to 500 ms. In the TMRCC of the present invention, when setting the ACK timer value in TCP, Set to 0.1 as the value used for. The ACK timeout value ATO actually used for the (i + 1) th ACK is expressed by Equation 3 below.

또한, 본 발명의 TMRCC는 NACK 패킷의 손실이나 복구 패킷의 손실에 대처하기 위해 NACK 타이머를 사용하며, NACK 타이머 값을 결정하는 방법은 ACK 타이머 값을 결정하는 방법과 유사하다. 즉, 각 NACK에 대해 측정한 NACK 응답 시간(NACK Response Time, NRT)을 활용함으로써 NACK 타이머 값을 네트워크 상태에 동적으로 대응하도록 갱신해갈 수 있다. 여기서, NACK 응답 시간이란 NACK을 보낸 시점부터 보낸 NACK에 대한 첫 번째 복구 패킷이 도착할 때까지 걸린 시간을 의미한다. 송신자 n에 대해 (i+1)번째로 전송되는 NACK에 대한 추정 NRT인 NRT_e(n, i+1)는 아래의 수학식 4와 같다.In addition, the TMRCC of the present invention uses a NACK timer to cope with the loss of the NACK packet or the loss of the repair packet, and the method of determining the NACK timer value is similar to the method of determining the ACK timer value. That is, by using the NACK Response Time (NRT) measured for each NACK, the NACK timer value can be updated to dynamically correspond to the network state. Here, the NACK response time refers to the time taken from when the NACK is sent to the arrival of the first recovery packet for the sent NACK. NRT _e (n, i + 1), which is an estimated NRT for the (i + 1) th NACK transmitted to the sender n, is expressed by Equation 4 below.

이때, 송신자 n에 대한 초기 추정 NRT값(NRT_e(n, 0))은 해당 세션에 대한 멀티캐스트 RTT(MRTT)을 사용하여 아래의 수학식 5를 이용하여 계산되며, 모든 송신자에 대해 동일한 값이 적용된다.At this time, the initial estimated NRT value (NRT _e (n, 0)) for the sender n is calculated using Equation 5 below using the multicast RTT (MRTT) for the session, and the same value for all senders. This applies.

송신자 n으로부터의 데이터 패킷에 대한 (i+1)번째 NACK 타이머의 값, 즉 NACK 타임아웃(NTO) 값은 최종적으로 아래의 수학식 6과 같이 계산된다.The value of the (i + 1) th NACK timer, that is, the NACK timeout (NTO) value, for the data packet from the sender n is finally calculated as shown in Equation 6 below.

여기서, s는 평균 패킷의 크기를 의미하며, R(n)은 송신자 n에 대한 현재 측정된 수신률을 의미한다. NACK 타임아웃(NTO)값을 결정하는데 있어서, 패킷당 지연 시간(s/R(n))을 사용하는 이유는 하나의 NACK 패킷에 하나 이상의 복구 패킷에 대한 요청이 포함될 수 있기 때문이다.Here, s means the average packet size, and R (n) means the currently measured reception rate for the sender n. The reason for using the per packet delay time (s / R (n)) in determining the NACK timeout (NTO) value is that a request for one or more recovery packets may be included in one NACK packet.

다음으로, 본 발명의 혼잡 제어 기법인 TMRCC 중에서 혼잡 윈도우 조절에 대해서 설명하면 아래와 같다.Next, the congestion window control in the TMRCC which is the congestion control technique of the present invention will be described below.

세션의 각 수신자는 각 송신자 n에 대하여 혼잡 윈도우 크기인 CW(n)을 관리하고, 매 피드백에 혼잡 윈도우 정보를 담아서 부모 노드에게 알린다. 세션이 시작될 때, 초기 혼잡 위도우의 크기는 아래의 수학식 7과 같이 설정되고, 수신자가 ACK을 복구 트리의 부모 노드로 전송할 때마다 수신자는 혼잡 윈도우의 크기를 조절한다. 연속적으로 받은 패킷의 최대 순서 번호가 위의 수학식 1에서 정의하고 있는 W_L(n)에 도달할 동안 데이터 패킷의 손실이 없었다면, 혼잡 윈도의 크기는 아래의 수학식 8과 같이 증가한다. 그 반대로 패킷 손실이 있었다면, 아래의 수학식 9와 같이 혼잡 윈도우의 크기는 줄어든다.Each receiver of the session manages a congestion window size CW (n) for each sender n and informs the parent node with congestion window information in every feedback. When the session starts, the size of the initial congestion window is set as shown in Equation 7 below, and the receiver adjusts the size of the congestion window whenever the receiver sends an ACK to the parent node of the recovery tree. If there is no loss of the data packet while the maximum sequence number of consecutively received packets reaches W _L (n) defined in Equation 1 above, the size of the congestion window increases as shown in Equation 8 below. On the contrary, if there was a packet loss, the size of the congestion window is reduced as shown in Equation 9 below.

CW(n, 0) = 3AWCW (n, 0) = 3AW

CW(n, i+1) = CW(n, i) + IF 단, IF>0이고, i=0,1,2,3,…CW (n, i + 1) = CW (n, i) + IF where IF> 0, i = 0,1,2,3,...

CW(n, i+1) = 1/DF × CW(n, i)CW (n, i + 1) = 1 / DF × CW (n, i)

여기서, CW(n, i)은 송신자 n에 대한 i번째 ACK 윈도우 동안 혼잡 윈도우의 크기를 의미하며, IF는 혼잡 윈도우 크기의 증가량을 의미하고, DF는 혼잡 윈도우의 감소 비율을 의미한다.Here, CW (n, i) means the size of the congestion window during the i-th ACK window for the sender n, IF means an increase amount of the congestion window size, DF means a reduction rate of the congestion window.

그 다음으로는 본 발명의 TMRCC에서 전송률 조절 과정을 설명한다.Next, the rate control process in the TMRCC of the present invention will be described.

개별 송신자의 데이터 전송률은 최소 전송률(R_min)과 최대 전송률(R_max)로 제한되는 범위 안에서 결정되는데, 최소 전송률(R_min)과 최대 전송률(R_max)은 응용 프로그램 개발자에 의해 설정될 수 있다. 송신자는 전송하는 데이터 패킷의 패킷 순서번호가 ACK 윈도우의 배수에 이를 때마다 다음 ACK 윈도우의 데이터 패킷에 적용할 전송률을 결정한다.The data rate of an individual sender is determined within the range limited by the minimum data rate (R _min ) and the maximum data rate (R _max ). The minimum data rate (R _min ) and the maximum data rate (R _max ) can be set by the application developer. . The sender determines a transmission rate to be applied to the data packet of the next ACK window whenever the packet sequence number of the transmitting data packet reaches a multiple of the ACK window.

세션 초기는 ‘슬로우 스타트 단계’로서 최대한 적정한 전송률에 빨리 도달하기 위해 아래의 수학식 10과 같이 전송률을 조절한다.The initial session is a 'slow start phase' to adjust the transmission rate as shown in Equation 10 below to reach the proper rate as soon as possible.

수학식 10에서 R_e(i+1)은 (i+1)번째 ACK 윈도우의 전송률을 의미하며, i 번째 ACK 윈도의 마지막 데이터 패킷 전송 후에 사용되는 수식으로, 초기 전송률 R_e(0)는 최소 전송률(R_min)을 사용하고, 초기 전송률 증가분 ??R(0)은 ‘0’이다. 슬로루 스타트 단계는 네 가지 조건, 전송률이 최대 전송률(R_max)에 도달하는 경우, 전송하는 패킷의 일련번호가 최대 허용 패킷 일련번호(W_R)에 처음으로 도달하는 경우, 송신자에게 NACK이 전달된 경우 및 ACK 타이머가 만료된 경우 중 하나만 만족되면 전송을 중지한 다음 '안정 상태 단계'로 전환된다.In Equation 10, R _e (i + 1) denotes a transmission rate of the (i + 1) th ACK window, and is used after the last data packet transmission of the i th ACK window, and the initial transmission rate R _e (0) is the minimum. Using the rate R _min , the initial rate increment ?? R (0) is '0'. The slew-start phase consists of four conditions: when the rate reaches the maximum rate (R _max ), a NACK is sent to the sender when the serial number of the transmitting packet reaches the maximum allowed packet serial number (W _R ) for the first time. If only one of the ACK timer expires and the ACK timer expires, the transmission stops and then transitions to a 'stable state'.

안정 상태 단계에서는 최근의 두 ACK 윈도우 사이의 평균 열린 윈도우의 변화 방향에 따라 다른 전송률 조절 정책이 적용된다. 열린 윈도우 크기는 TRMCC에서 정의하고 있는 것과 동일한 의미로 사용되며, W_R과 송신자가 전송 중인 패킷의 일련번호간의 차이로 계산된다. i번째 ACK 윈도우의 평균 열린 윈도우 크기(W_O(i))는 아래의 수학식 11과 같다.In the steady state phase, different rate adjustment policies are applied depending on the direction of change in the average open window between the two most recent ACK windows. The open window size is used in the same meaning as defined in the TRMCC and is calculated as the difference between W _R and the serial number of the packet being sent by the sender. The average open window size W _O (i) of the i-th ACK window is expressed by Equation 11 below.

이때 j는 데이터 패킷의 일련번호를 가리키며, AW는 ACK 윈도우를 의미하며, W_R(j)는 일련번호 j인 데이터 패킷이 전송되는 순간의 최대 허용 패킷 순서 번호를 의미한다.In this case, j denotes a serial number of a data packet, AW denotes an ACK window, and W _R (j) denotes a maximum allowable packet sequence number at the moment a data packet having a serial number j is transmitted.

본 발명의 TMRCC는 위의 수학식 11을 이용하여 평균 열린 윈도우 값을 산출하고, 산출된 평균 열린 윈도우 값을 이용하여 다음 세 가지 경우의 전송률 조절 방법 중 하나를 적용한다.The TMRCC of the present invention calculates an average open window value using Equation 11 above, and applies one of the following three cases of rate adjustment using the calculated average open window value.

첫 번째 경우는 열린 윈도우가 지난 ACK 윈도우 동안 한 번이라도 0이 되어 빠른 복구가 필요한 경우로써, 본 발명의 TMRCC는 아래의 수학식 12를 이용하여 전송률을 계산한다.In the first case, when the open window becomes zero at least once during the last ACK window and needs fast recovery, the TMRCC of the present invention calculates a transmission rate using Equation 12 below.

여기서, R(i)은 지난 ACK 윈도우 동안 실제 전송률을 의미하는데, 열린 윈도우가 0이 되면 데이터 패킷이 전송되지 못하기 때문에 R(i)은 R_e(i)보다 작은 값을 갖게 된다. ACK 윈도우가 0이 되는 경우는 네트워크 혼잡으로 인해 데이터 패킷의 손실이 커서 수신자들로부터 ACK이 수신되지 않았거나 수신자들이 전송한 피드백이네트워크 상에서 손실되어 송신자에게 전달되지 못한 경우이다. 이러한 경우는 상술한바와 같이 다대다 세션에서 한 회선에 다수의 데이터 흐름과 제어 흐름의 수가 공존함으로써 발생한다. 이때, 이전 ACK 윈도우에서 사용한 전송률을 그대로 적용하면 네트워크의 혼잡 상태를 반영할 수 없고, 실제 전송률만을 적용하면 전송률이 낮은 값에서 머물게 되기 때문에 세션 내 흐름간 공평한 전송률에 도달하지 못하는 경우가 발생한다. 이런 이유로, 본 발명의 TMRCC는 지난 ACK 윈도우에 대한 전송률 R_e(i)과 실제 측정된 전송률 R(i)의 EWMA로 새 ACK 윈도우에 적용할 전송률을 결정한다.Here, R (i) means the actual transmission rate during the last ACK window. When the open window is 0, R (i) has a smaller value than R _e (i) because data packets are not transmitted. If the ACK window is zero, the data packet is lost due to network congestion, so that an ACK is not received from the receivers, or feedback transmitted by the receivers is lost on the network and thus cannot be transmitted to the sender. This case is caused by the coexistence of multiple data flows and control flows on one line in a many-to-many session as described above. In this case, if the transmission rate used in the previous ACK window is applied as it is, the congestion state of the network cannot be reflected, and if only the actual transmission rate is applied, the transmission rate remains at a low value, and thus a fair transmission rate between flows in a session may not be reached. For this reason, the TMRCC of the present invention determines the transmission rate to be applied to the new ACK window with the EWMA of the transmission rate R _e (i) for the last ACK window and the actually measured transmission rate R (i).

두 번째 경우는 전송률의 증가가 필요한 경우로써, W_O(i)≥W_O(i-1)일 경우, 즉 열린 윈도우가 증가하는 것은 네트워크에서 손실되는 데이터 패킷의 수가 감소하고 있는 것이기 때문에 네트워크 상태가 현재의 전송률보다 더 높은 전송률을 허용한다는 것으로 판단하여, 본 발명의 TMRCC는 아래의 수학식 13을 적용하여 전송률을 증가시킨다.In the second case, if the case as an increase in the data rate _{_{required, W O (i) ≥W O}} (i-1), i.e., I believe that the open windows increase network conditions, because that reduces the number of data packets lost in the network, Is determined to allow a higher data rate than the current data rate, the TMRCC of the present invention increases the data rate by applying Equation 13 below.

위의 수학식 13에서, R_e(i)은 i 번째 ACK 윈도우에 적용하도록 계산된 전송률을 의미하며, △R′은 전송률의 증가치로써, 본 발명의 TMRCC에서는 최대 패킷 크기와 같은 값을 사용한다.In Equation 13, R _e (i) means a rate calculated to apply to the i-th ACK window, ΔR 'is an increase in the rate, the same value as the maximum packet size in the TMRCC of the present invention .

세 번째 경우는 전송률의 감소가 필요한 경우로써, 편균 열린 윈도우 크기가감소할 때, 즉 네트워크에서 손실되는 데이터 패킷의 수가 증가하고 있는 것이기 때문에 네트워크가 혼잡 상태에 있는 것으로 판단하여, 본 발명의 TMRCC는 아래의 수학식 14를 이용하여 전송률을 감소시킨다.In the third case, the transmission rate needs to be reduced, and it is determined that the network is in a congested state when the average open window size decreases, that is, the number of data packets lost in the network is increasing. Equation 14 below is used to reduce the data rate.

상기와 같은 본 발명의 TMRCC가 실제 네트워크 환경에서 적용되는 과정은 도 1, 도 2 및 도 3을 참조하여 설명한다. 도 1은 본 발명이 적용될 네트워크 환경을 도시한 도면이고, 도 2는 본 발명이 적용된 후 세션 내 참가자들간 공평성을 도시한 그래프이고, 도 3은 본 발명과 TCP의 친화성을 도시한 그래프이다.The process of applying the TMRCC of the present invention as described above in an actual network environment will be described with reference to FIGS. 1, 2, and 3. 1 is a diagram illustrating a network environment to which the present invention is applied, FIG. 2 is a graph showing fairness among participants in a session after the present invention is applied, and FIG. 3 is a graph showing the affinity between the present invention and TCP.

실제 네트워크 환경에 적용하기에 앞서, 도 1에 도시된 바와 같이, 라우터1(100)과 라우터2(110) 및 라우터1(100)과 라우터3(120) 사이의 회선 대역폭은 T1 회선에 해당하는 1.544Mbps로 설정하였으며, 네트워크 상에는 두개의 GAM 코어1, 2(140, 142)와 네 개의 세션 참가자 GAM1, 2, 3, 4(131, 132, 133, 134)가 존재한다. 이때, GAM 코어1, 2(140, 142)는 세션 참가자들의 에러 복구를 전담하는 역할을 수행하는데, 즉, GAM 코어1(140)은 라우터 1(100)의 지역 네트워크 내 참가자 GAM1, 2(131, 132)들에게 에러 복구 서비스를 제공하며, GAM 코어2(142)는 라우터 2, 3(110, 120)의 지역 네트워크 내 참가자 GAM3, 4(133, 134)에게 에러 복구 서비스를 제공한다. 여기서, IP 멀티캐스트 라우팅을 위하여 PIM-SM이 사용되고 라우터1(100)을 RP로 설정한다.Prior to applying to a real network environment, as shown in FIG. 1, the line bandwidth between router 1 100 and router 2 110 and router 1 100 and router 3 120 corresponds to a T1 line. It is set to 1.544Mbps, and there are two GAM cores 1, 2 (140, 142) and four session participants GAM1, 2, 3, and 4 (131, 132, 133, 134) on the network. In this case, the GAM core 1, 2 (140, 142) is responsible for error recovery of the session participants, that is, the GAM core 1 (140) is a participant GAM1, 2 (131) in the local network of the router 1 (100) 132 provides error recovery services, and GAM Core 2 142 provides error recovery services to participants GAM3, 4 (133, 134) in the local network of routers 2, 3 (110, 120). Here, PIM-SM is used for IP multicast routing and router 1 (100) is set to RP.

실제 네트워크 환경의 적용에서 세션 내 공평성을 측정하기 위하여 GAM/TMRCC 세션의 각 참가자들은 5M 바이트의 데이터를 전송하였으며, 그 적용 결과, 도 2에 도시된 바와 같이, 각 참가자들은 유사한 전송률을 유지하면서 데이터를 전송한다.In order to measure the fairness of the session in the application of the actual network environment, each participant of the GAM / TMRCC session transmitted 5M bytes of data. As a result, as shown in FIG. 2, each participant maintained data while maintaining similar data rates. Send it.

또한, 실제 네트워크 환경 적용에서 TCP 친화성을 측정하기 위하여 GAM/TMRCC 세션의 각 참가자들은 15M 바이트의 데이터를 전송하며, GAM/TMRCC 세션의 중간에 8M 바이트의 데이터를 전송하는 TCP 세션이 시작한다. 이때, TCP 세션의 송신자와 수신자의 위치는 GAM1, 2(131, 132)와 동일한 방향으로 데이터가 전달된다.In addition, in order to measure TCP affinity in a real network application, each participant of the GAM / TMRCC session transmits 15M bytes of data, and a TCP session starts transmitting 8M bytes of data in the middle of the GAM / TMRCC session. At this time, data of the sender and receiver of the TCP session is transmitted in the same direction as the GAM1, 2 (131, 132).

TCP 친화성 실험 결과는, 도 3에 도시된 바와 같이, GAM1(131)과 GAM2(132)가 TCP 흐름의 전송률과 유사하게 전송률이 조절되는 것을 알 수 있다.As shown in the TCP affinity test result, it can be seen that the GAM1 131 and the GAM2 132 have a data rate adjusted similarly to the data rate of the TCP flow.

이상 설명한 바와 같이, 본 발명은 혼잡 윈도우 기법에 전송률 제어기를 이용함으로써, 순수하게 윈도우 기법만을 기반으로 한 혼잡 제어 기법에서 발생할 수 있는 자체 시간 조절 기능의 상실 문제를 해결할 수 있다.As described above, the present invention can solve the problem of loss of self-time adjustment function that can occur in the congestion control scheme based solely on the window scheme by using the rate controller in the congestion window scheme.

또한, 본 발명은 혼잡 제어를 위한 추가적인 피드백 없이 손실 복구를 위한 피드백을 활용하여 혼잡 제어를 수행함으로써, 수신자의 처리 부담을 최소화시킬 수 있다.In addition, the present invention can minimize the processing burden of the receiver by performing the congestion control by utilizing the feedback for loss recovery without additional feedback for the congestion control.

본 발명은 수신자들로부터 피드백이 도착하지 않아 데이터 패킷 전송이 일시적으로 중단된 경우와 송신자의 전송률 조절에 있어서 실제 적용된 전송률과 예상전송률을 기반으로 다음 전송률을 계산함으로써, 피드백과 재전송 패킷의 손실에 의해 발생되는 세션 내 흐름 간의 불공평한 대역폭 분할을 해결할 수 있다.The present invention calculates the next transmission rate based on the actual transmission rate and the expected transmission rate when the data packet transmission is temporarily interrupted due to no feedback from the receivers and the transmission rate adjustment of the sender. Unfair bandwidth partitioning between flows in the session that occurs can be resolved.

또한, 본 발명은 ACK 타이머와 NACK 타이머의 값을 네트워크 상태에 따라 동적으로 조절함으로써, 중복된 재전송 및 피드백 요청이나 불필요한 대기 시간을 피하여 송신자의 전송률을 효율적으로 조절할 수 있다.In addition, according to the present invention, by dynamically adjusting the values of the ACK timer and the NACK timer according to the network state, the transmission rate of the sender can be efficiently controlled by avoiding redundant retransmission, feedback request, and unnecessary waiting time.

Claims

A tree-based, many-to-many reliable that includes a receiver that sends an ACK to the parent node on the recovery tree whenever it successfully receives as many consecutive data packets as the ACK window from the sender, and sends a NACK whenever a data packet loss is found. In the congestion control scheme of multicast,

The ACK and NACK are included in the ACK and NACK by including a minimum value W _R among the last sequence number W _L of consecutive data packets received by the receiver and the maximum allowed data packet sequence numbers of the node of the receiver and its children. Transmitting,

Estimating a congestion window size of the receiver based on a difference between W _L and W _R included in the ACK and NACK, and using the W _R as the maximum sequence number of a packet that can be transmitted by the sender.

Tree-based many-to-many reliable multicast congestion control scheme, including

The method of claim 1,

The sender,

When there is a child node not transmitting an ACK on a recovery tree, an ACK request is made to a child node not transmitting the ACK and an ACK timer is started.

The timeout value (ATO) of the ACK timer is an ACK response time (ART) after the sender transmits the ACK for the ACK window from all child nodes on the recovery tree after the last packet of the ACK window is transmitted to the receiver. ), And ART is expressed by the following equation (ART _e (i + 1) = (1-α) × ART _e (i) + α × ART (i), where 0 <α <1, i = After calculating the estimated ART value ART _e to be used for the next ACK window by applying to 0, 1, 2, ...), calculating the ACK timeout value ATO by 1.5 times the calculated ART _e . A tree-based, many-to-many reliable multicast congestion control scheme.

The method of claim 1,

The recipient,

In addition to transmitting the NACK to the sender when the data packet loss occurs, it drives a NACK timer,

The timeout value (NTO) of the NACK timer corresponds to a time taken for the receiver to receive the first recovery packet for the NACK when a data packet is lost, that is, according to the NACK response time (NRT) and the next NACK. Calculated using the estimated NRT value NRT _e ,

In this case, s means average packet size, and R (n) means the reception rate currently measured for the sender n, tree-based many-to-many reliable multicast congestion control scheme.

The method of claim 3, wherein

NRT _{e which} is the estimated NRT value is,

It is defined by the following equation,

Equation: NRT _e (n, i + 1) = (1-α) × NRT _e (n, i) + α × NRT (n, i)

However, 0 <α <1 and i = 0, 1, 2,...

In this case, using the initial estimated NRT value is 'multicast RTT (MRTT)' for the session, NRT _e (n, 0) is 2 x MRTT. Congestion Control Technique.

In the receiver congestion window control method for managing the CW (n), the congestion window size for each sender n (n = 1, 2, 3, ...), and provides the congestion window information to the parent node in the session at the time of feedback ,

Setting CW (n, 0), which is the size of the initial congestion window at the start of the session, to '3 × AW (size of ACK window)';

Determining whether a data packet is lost while the maximum sequence number of packets continuously received from the sender reaches the time when the receiver transmits an ACK;

As a result of the determination, when there is a loss of the data packet, a NACK is transmitted to a parent node on a recovery tree and the size of the congestion window of the sender is reduced, and when there is no loss of the data packet, an ACK is transmitted to the sender. Increasing the sender's congestion window size

Tree-based many-to-many reliable multicast congestion control scheme, including

The method of claim 5,

When the size of the congestion window increases, the size of the congestion window is

It is increased by the following equation,

Equation: CW (n, i + 1) = CW (n, i) + IF where IF> 0, i = 0,1,2,3...

In this case, the IF is a tree-based many-to-many reliable multicast congestion control technique, which means an increase in congestion window size.

The method of claim 5,

When the size of the congestion window is reduced, the size of the congestion window is

Reduced by the following equation,

The DF is a tree-based, many-to-many reliable multicast congestion control scheme, characterized in that it represents a reduction ratio of the congestion window.

In the rate control method of the sender to determine the transmission rate within the range limited by the maximum rate and the minimum rate,

When the session starts, the data rate corresponding to the i-th ACK window is transmitted as a slow start step, and then the rate for transmitting the data packet corresponding to the ACK window is expressed as: R _e (i + 1) = R _e (i) Determining ΔR (i) + r (r = 1 kilobyte, i = 0,1,2,3…),

When the transmission rate reaches the maximum transmission rate, when the sequence number of the packet transmitted by the sender first reaches the maximum allowed packet sequence number (W _R ), when the NACK is transmitted from the receiver, and when the ACK timer expires. When at least one of the same conditions is satisfied, the slow start step is stopped and the change state of the average open window size (W _o (i): average open window size of the i th ACK window) between two ACK windows is stopped. Transitioning to a steady state step of adjusting the rate according to,

The steady state step is applied to the new ACK window at the rate R _e (i) and the actual measured rate R (i) for the last ACK window when the size of the window opened during the previous ACK window is '0'. Determining a baud rate to perform,

The step of increasing the data rate if _{_{(W o (i) ≥W o}} (i-1)) at which the open window size is increased and reduce the data rate is determined by the network congestion state in the case where the size of the open windows reduced

Tree-based many-to-many reliable multicast congestion control scheme, including

The method of claim 8,

If the size of the window opened during the previous ACK window is '0', the rate is

R _e (i + 1) = (1-β) × R _e (i) + β × R (i), provided that 0 <β <1, i = 0,1,2,3,...

A tree-based, many-to-many reliable multicast congestion control technique characterized in that