한국정보과학회 학술대회 논문작성양식

Size: px

Start display at page:

Download "한국정보과학회 학술대회 논문작성양식"

나은 성
5 years ago
Views:

1 SACK 을이용한 TCP 의효율적인손실복구기법 황재현 O 유시환유혁고려대학교컴퓨터학과 {jhhwang O, shyoo, hxy}@os.korea.ac.kr An Efficient Loss Recovery Algorithm for TCP with SACK Jae-Hyun Hwang O See-Hwan Yoo Hyuck Yoo Department of Computer Science, Korea University 요약전통적으로 TCP는네트워크상황에따라전송률을조절하는혼잡제어알고리즘을가진다. 특히손실에대한빠른복구알고리즘은 TCP로하여금일시적인네트워크혼잡에잘대응하도록함으로써처리량을높이는데기여한다. 그러나현재의 TCP는빠른복구완료이후에비로소혼잡회피구간으로진입하기때문에한윈도우내에다수의손실이발생할경우윈도우가새로열리는시간이지연되며이는처리량의저하로이어진다. 또한복구구간동안의고정된혼잡윈도우의크기는복구시간을더지연시킨다. 따라서본논문에서는패킷손실에대한복구지연시간을효율적으로감소시켜주는새로운손실복구기법을제안한다. 제안하는기법은패킷의손실감지후윈도우의크기를절반으로줄이고곧바로혼잡회피구간으로진입시킴으로써마치빠른복구기간이제거된것과같은효과를낸다. 시뮬레이션실험을통해기존의, SACK 및 과비교하여제안하는기법이가장효율적으로동작함을확인하였다. 1. 서론 TCP(Transmission Control Protocol) 는널리알려진신뢰성을제공하는종단간전송계층프로토콜이다. TCP 는신뢰성을제공하기위해손실된패킷에대한재전송, 시퀀스의순서정렬등의메커니즘을사용한다. 이와더불어네트워크의혼잡정도에따라전송률을조정하는혼잡제어를수행한다. 혼잡제어를위해서는무엇보다도네트워크혼잡을감지할수있어야하는데, TCP 는패킷손실을혼잡에대한신호로가정하고있다. 이를위해기본적으로재전송타이머를두고있지만, 일반적으로 3 개의중복 ACK 을받으면타이머의만료를기다리지않고빠르게혼잡에대응하는것이가능하다. TCP Reno 에서는중복 ACK 에의한혼잡감지에대한대응으로빠른재전송 (fast retransmission) 및빠른복구 (fast recovery) 메커니즘을사용해왔다 [1]. 그러나이것은단일손실 (single drop) 에는효과적인반면, 한윈도우내의다중손실 (multiple drop) 에는매우취약하다는단점이있다. 이를극복하기위해 에서는빠른복구구간동안부분 ACK(partial ACK) 을이용하여보다효율적으로다중손실에대응할수있도록하였다 [2]. 그러나기존의 ACK 방식은연속으로도착된가장높은시퀀스번호만을알려주기때문에부분 ACK 을이용한다하더라도 RTT 당하나의패킷만이복구가가능하다. 이후에제안된 SACK(Selective ACK) 은 TCP 헤더의옵션필드를사용하여수신측에잘도착한패킷시퀀스에대해알려주기때문에송신측은 SACK 을통해알려진손실패킷들을보다빠르게재전송가능하게되었 다 [3][4]. 이렇게지금까지제안되어온빠른재전송, 빠른복구, 부분 ACK, SACK 등은현재까지도대부분의변종에널리적용되고있는복구메커니즘이다. 그러나 SACK 등의옵션을활용한다하더라도여전히다중손실하에서는복구에대한지연시간이발생한다. 즉, 이미혼잡에대한대응은윈도우의크기를절반으로줄인것으로끝났음에도, 복구구간을빠져나오기전까지는정상적인혼잡회피 (congestion avoidance) 구간으로들어가지못한다는것이다. 따라서복구를효율적으로수행하는것이패킷손실에의한성능저하를막는데중요한요인으로작용한다. 우리는기존의복구메커니즘들이연속적다중손실에취약한원인을윈도우감소이후복구구간에의한지연오버헤드때문이라고판단하고있다. 즉, 복구구간동안윈도우크기가고정됨에따라 TCP 가복구에서벗어나는시간을지연시키며결과적으로혼잡회피로의진입이늦어지면서성능저하로이어진다. 이러한오버헤드를줄이고자본논문에서는별도의복구구간없이곧바로혼잡회피구간으로진입한뒤, 손실된패킷을윈도우가허용하는전송량내에한번에모두재전송하여복구에대한지연오버헤드를해소할수있는새로운복구알고리즘을제안한다. 이알고리즘은 TCP 가 3 개의중복 ACK 으로패킷손실을발견하여윈도우크기를절반으로줄인후마치곧바로복구가끝난것과같이동작하게하여항상기존의복구메커니즘보다빠른복구시간을가진다. 더불어슬라이딩윈도우 (sliding window) 의운용에있어전방 ACK(forward ACK) 정보

2 를이용하여윈도우의움직임이보다원활하도록하였다. 또한제안하는알고리즘은송신측의수정만으로도동작이가능하기때문에배포가쉽다는장점이있다. 본논문에서는이를기존의, SACK 및 과비교하였으며, 시뮬레이션실험을통해그우수성을입증하였다. 본논문은다음과같이구성된다. 2 절에서는제안하는복구알고리즘의연구동기와동작과정에대해자세하게설명한다. 3 절에서시뮬레이션을통해성능평가및기존의복구메커니즘과비교한뒤, 마지막으로 4 절에서결론을맺는다. 2. 효율적인손실복구기법 본절에서는기존의손실복구기법에대한간단한설명을포함하여제안하고자하는복구알고리즘에대한연구동기, 가정, 그리고세부적인복구과정에대해자세히설명하도록한다. 2.1 연구동기본논문에서제안하는복구기법의궁극적인목표는 TCP 의혼잡제어와빠른복구를완전히분리시킴으로써복구구간에의한오버헤드를최소화하는데에있다. 기존에제안되어온모든복구기법들은손실된패킷에대한복구가끝난뒤에야비로소혼잡회피구간으로넘어가게된다. 이것은기본적으로한윈도우내의모든패킷에대한 ACK 을받아야윈도우사이즈를하나증가시키는전통적인혼잡회피전략과맞아떨어진다. 그러나복구시간이길어지면길어질수록새로혼잡윈도우값이증가되기시작하는타이밍이늦어지게되며, 이는한윈도우내에서다수의손실이발생될수록더욱복구오버헤드가커짐을의미한다. 만약 3 개의중복 ACK(duplicate ACK) 을통해윈도우크기를절반으로줄인뒤손실된패킷을복구할필요가없다고가정해보자. 이때 TCP 가취할수있는가장자연스러운동작은줄어든윈도우크기에서부터곧바로다시혼잡회피를수행하는것이다. 제안하는복구기법은이러한직관적통찰을가지고패킷손실후빠르게안정상태로진입할수있게하였다. 즉, SACK 에의해얻어진가장높은시퀀스의패킷 ( 전방 ACK) 까지모든패킷이수신측에도착되었다고가정하고여기서부터곧바로혼잡회피를수행하여복구에의해발생하는지연오버헤드를제거하는것이다. 또한손실된패킷들은이후새롭게열려진윈도우가허용하는한도내에서재전송시키고, 남은여유분에대해서는새로운패킷을전송시키도록하면혼잡제어로부터복구구간을분리해내는것이가능하다. 2.2 가정사항앞서설명한바와같이빠른복구가가능하게하기 위해서는한가지가정을전제로한다. 즉, 3 개의중복 ACK 이후에 SACK 에의해알려진홀 (hole) 들은손실된것으로가정하는것이다. 일반적으로 SACK 블럭사이의홀, 즉아직수신측에도착되지않은패킷에대하여송신측은 2 가지경우로판단가능하다. 첫번째는 IETF 의 SACK 표준안과같이아직네트워크상에존재하는것으로판단하는것이다. 두번째는모든홀에대해손실된것으로간주하는것인데, (Forward ACK) 이이를가정한복구메커니즘을가진다 [5]. 그러나 SACK 블럭에의한홀이전적으로손실이라고받아들여지기어려운까닭은바로패킷재배열 (packet reordering) 때문이다 [6][7]. 일반적으로 TCP Reno 로부터파생된대부분의변종들은중복 ACK 의개수가 3 개를넘어설때에빠른복구를수행하게된다. 반면 은 SACK 의정보를통해전방 ACK(forward ACK) 과중복 ACK 의시퀀스차이가 3 개를넘어서면복구가수행된다 [5]. 따라서네트워크상에패킷재배열현상이발생한다면하나의 SACK 에의해빠른복구기법이수행될수도있다. 즉, 의경우 Reno 보다빠른복구기법이잘못수행될확률이높아지며, 이는윈도우의크기를불필요하게절반으로줄이기때문에성능저하를야기시킨다. 그럼에도불구하고재배열현상이발생하지않는다면 알고리즘은손실패킷에대한빠른복구를통해 TCP 의성능을향상시킬수있다. 이러한이유로리눅스 TCP 의경우기본적으로 을사용하고있으며, 재배열이발견되는경우 기능을사용하지않는전략을사용한다 [8]. 우리는 의성급한판단을완화하여윈도우의크기를줄이는시점을 Reno 와동일하게중복 ACK 의개수를통해복구가수행되도록하였으며, 다만수행이후의홀에대해서는손실로간주하도록하여윈도우가허용하는범위내에서빠르게재전송가능하도록하였다. 2.3 복구기법알고리즘본논문에서제안하는복구기법의핵심은기존의전통적인빠른복구구간을제거하는데있다. 즉, 손실확인이후별도의복구구간없이곧바로혼잡회피구간으로넘어가는것이다. 이것은앞서설명한가정사항과 SACK 을이용한전방 ACK 정보를통해가능하다. 즉, 윈도우크기가 n 이라고했을때, m 개의패킷이손실되었다고가정해보자. 송신측이 n-m 개 (n-m 3) 의중복 ACK 을받은후 SACK 블럭간의홀을패킷손실로간주한다면이시점에서는네트워크상에전송중인패킷이존재하지않게되기때문에새롭게윈도우를여는것이가능해진다. 이것은결국기존의 TCP 가빠른복구이후의동작을곧바로수행하는것과같은효과를낸다. 이러한기법은손실된패킷이복구될때까지혼잡회피구간으로의진입이지연되는것을효과적으로제거함으로써 TCP 가패킷손실에대한대

3 응이빠르게이루어지도록돕는다. 그림 1 은송신자가패킷을받았을때제안하는복구기법의동작을간단한수도코드 (pseudo code) 형태로나타낸것이다. IF recovery == false then // normal mode IF ack_no > moment_ack then moment_ack = ack_no open congestion window ELSE IF packet loss is detected then recovery = true halve congestion window ELSE // recovery mode open congestion window IF holes of SACK blocks is covered? then retransmit = retransmit # of holes covered IF ack_no covers all loss packets? then recovery = false moment_ack = ack_no ELSE moment_ack = forward ACK number 그림 1 패킷수신함수 수신함수에서 recovery 변수가각모드를나타내며, 패킷손실을감지했을때 ( 즉, 중복 ACK 수가 3 개이상일때 ) 윈도우크기를줄이고복구모드로바뀐다. 여기서 moment_ack 변수는슬라이딩윈도우의왼쪽편 ( 닫히는방향 ) 을나타내는것으로, 일반모드 (normal mode) 일때는마지막 ACK 시퀀스 (ack_no 변수 ) 와동일하며, 복구모드 (recovery mode) 에서는마지막 SACK 시퀀스 ( 즉, 전방 ACK) 를가리키게된다. 패킷과동등하게간주하여혼잡회피알고리즘에반영한다. retransmit 변수는재전송된패킷의수를카운트하여전송패킷수와재전송패킷수의합이전체윈도우의크기를넘지않도록한다. 그림 3 은송신함수를나타낸것이다. 제안하는복구알고리즘은개념적으로복구를위한재전송과혼잡제어를분리시키기때문에수신함수에서는별도의재전송을수행하지않고, 송신함수에서먼저재전송할패킷이있는지를확인한다. 여기서도재전송이이루어질때마다 retransmit 변수를증가시킴으로써 cwnd retransmit 가허용하는범위내에서패킷이전송되도록하였다. WHILE next_seq <= moment_ack + cwnd retransmit IF no retransmission is needed then seqno = next_seq next_seq = next_seq + 1 ELSE seqno = next retransmitting packet retransmit = retransmit + 1 send a seqno packet 그림 3 패킷송신함수 그림 4 는제안하는복구기법의동작에대한하나의예를보여준다. 먼저첫번째턴에서 1-6 번패킷을전송한뒤 1 번패킷이손실되었다면, 두번째턴에서중복 ACK 을통해패킷손실을감지하게된다. 이때윈도우는절반으로줄고 moment_ack 에의해 7-9 가새로열리게되지만, 1 번패킷을재전송하기때문에혼잡윈도우크기 (cwnd) 가허용하는범위내에서 1, 7, 8 번패킷을전송한다. 세번째턴에서재전송패킷을포함한 3 개의패킷에대해모든 ACK 이도착하면다시 9 번부터 cwnd/2 + 1 만큼의패킷을전송하게된다. 결국손실에대한복구와무관하게손실감지이후곧바로혼잡회피구간이수행됨을알수있다. 그림 2 패킷손실감지시슬라이딩윈도우의이동 그림 2 는제안하는기법의복구모드에서의슬라이딩윈도우를표현한것으로이는 의동작과유사하다. 다만손실이발생하는윈도우턴을제외하고는항상윈도우를증가시키게함으로써손실복구구간에대한오버헤드를최소화시킨다. 또한재전송한패킷역시일반 그림 4 혼잡제어와재전송동작의예

4 3. 시뮬레이션실험 본절에서는제안하는알고리즘의효율성을보이기위해 ns-2( 버전 2.31) 시뮬레이터 [9] 를이용하여실험을수행하였다. 먼저 ns-2 내에제안하는복구알고리즘을구현하였으며, 이를, + SACK 및 과비교하였다. 기존의변종들은 ns-2 구현및기본세팅값을그대로사용하였다. 다만 의경우 Slow-but-Steady 와 Impatient 두가지의복구방법이존재하는데 [1], 본논문의실험에서는 Slowbut-Steady 가좀더나은복구성능을보여이를사용하였다. 즉, 모든부분 ACK(partial ACK) 에대해재전송타이머를재설정하도록하여, 복구가끝날때까지타임아웃 (timeout) 이발생하지않도록하였다. 모든시뮬레이션은하나의병목링크를가지는간단한 Dump-Bell 토폴로지상에서이루어졌으며, 약 2ms 의왕복전파지연 (round-trip propagation delay) 시간과 1Mbps 의네트워크용량을가지도록설정하였다. 패킷손실의경우, 다른기법과의동등한비교를위해의도적으로발생시킨손실을제외하고발생하지않도록 중간라우터의버퍼를충분히크게설정하였다. 그밖에패킷크기는 1bytes 로고정하였고, 지연 ACK (delayed ACK) 은사용하지않았다. 그림 5 는본논문에서제안하는복구기법을포함하여기존복구메커니즘들의동작을시퀀스번호로나타낸것으로, 검은색점은패킷의전송시점을, 빨간색점은 ACK 의도착시점을나타낸다. Slow-start 임계값 (ssthresh) 은초기값을 1 으로설정하여손실이발생되기전에이미혼잡회피상태로진입되었다. 패킷손실은시퀀스번호 24 부터 3 번까지모두동일하게발생시켰고, 손실전까지의동작은네경우모두동일하였으며, 패킷손실직전의혼잡윈도우 (cwnd) 의크기는약 11.4 였다. 먼저 의경우를살펴보면, 손실이발생한턴에서중복 ACK 2 개까지추가로패킷을전송한뒤 3 개째빠른재전송을수행하고윈도우를절반으로줄인다. 이후복구가완료될때까지매 RTT 당하나의손실패킷을재전송하며, 일시적으로중복및부분 ACK 을통해슬라이딩윈도우를이동시켜 4 번째재전송패킷부터추가적으로전송이다시이루어지는것을볼수있다. 5 5 (Mod 5) (Mod 5) (a) (Slow-but-Steady) (b) + SACK 5 5 (Mod 5) (Mod 5) (c) Forward ACK () (d) 그림 5 다수의패킷손실에대한복구동작비교

5 는기본적으로다수의손실에대해꾸준한복구가가능하지만, 복구시간이손실된패킷수 * RTT가됨에따라다중손실이발생하면다시정상적인혼잡회피구간에진입하는데많은시간이소요된다. 즉, 슬라이딩윈도우의왼쪽편이손실패킷으로인해이동이더디기때문에복구전까지윈도우의이동에대한흐름이원활하지않게된다. 두번째로 SACK 옵션을사용하는경우는이보다빠른복구가가능해진다. 그러나 SACK은 pipe 변수에의해전체네트워크상에존재하는패킷수를추정하기때문에줄어든윈도우크기에제한을받아 SACK 블록간의홀을감지하더라도곧바로모든패킷을재전송하지않는다. 대신부분 ACK(partial ACK) 을통해 2개의패킷을재전송할수있기때문에 7개의손실패킷들이세번에나누어재전송되는것을알수있다. 이역시복구구간에진입후다시혼잡회피로의진입까지약 4 RTT가소요되었다. 또한복구구간동안 cwnd가동결되어안정상태로의진입을지연시킴을알수있다. 의경우 SACK의홀에대해모두손실로판단하여한꺼번에많은양의손실패킷을재전송시키기때문에 SACK보다빠른복구가이루어진다. 다만그림 5(c) 에서알수있듯이 은손실패킷이전의중복 ACK에대해서는추가적인패킷을전송하지않는다. 이는앞서설명한바와같이 이 SACK 홀을통해손실을판단하기때문인데, 이는패킷재배열에보다취약한점외에작은윈도우에서손실감지가어렵다는단점이있다. 예를들어윈도우크기가 3일때첫번째패킷이손실되면, 기존방식은중복 ACK에대한추가적인전송으로손실을감지할수있지만, 의경우그렇지못하기때문에결국타임아웃 (timeout) 을발생시켜야한다. 마지막으로본논문의복구기법의경우를살펴보자. 그림 5(d) 에서제안된복구기법은손실발생후다음턴에서곧바로줄어든 cwnd 값, 즉재전송패킷을포함하여 5만큼전송을수행한다. 다음 RTT 후에는 = 6만큼전송이수행되어매턴윈도우크기를하나씩증가시키는혼잡회피가적절히수행됨을알수있다. 또한손실감지이후 SACK의홀정보를손실로가정하기때문에최종복구에대한 ACK의도착시점도 과비슷하게빠른속도를보여준다. 그림 6은그림 5에대한혼잡윈도우의변화량을보여주는그래프로, 제안하는복구기법이윈도우크기를줄인이후곧바로혼잡회피를수행하고있음을단적으로보여주고있다. 나머지변종들은그림 5와비교했을때모든손실패킷에대한도착을포함하는 ACK이도착한이후에실질적으로혼잡회피로진입하고있다. 진입시점의차이는 와약 6 RTT, + SACK 과약 3 RTT, 과약 1 RTT 정도를보였다. 그림 7은윈도우크기가약 11정도였을때한윈도우내에서발생하는패킷손실의수를변화시켜가며시퀀 Congestion window Algorithm + SACK 그림 6 혼잡윈도우의증가량비교 스의증가량을나타낸그래프이다. 그림 7(a)-(c) 는윈도우의절반이하로손실을발생시킨경우이며, (d)-(f) 는절반이상의연속적인다중손실을발생시킨경우이다. 그래프에서알수있듯이동일한시퀀스의패킷손실에대해제안하는알고리즘이기존의복구기법에비해항상더나은시퀀스의증가량을보였으며, 이는패킷의손실수가증가할수록보다뚜렷한차이를보인다. 즉, 기존기법들의복구시간이길어지면길어질수록혼잡회피구간으로의진입이지연되기때문에제안하는알고리즘의효율성은증대된다. 또한복구시간은 RTT 에비례하기때문에 RTT 가큰환경일수록이들간의성능향상비율은보다커지게된다. 결과적으로본논문에서제안하는복구기법은기존복구기법들의지연오버헤드를효율적으로제거함으로써 TCP 의성능향상을유도함을알수있다. 4. 결론및향후연구 본논문에서는 TCP 의복구메커니즘을효율적으로개선한새로운복구알고리즘을제안하였다. 전통적으로 TCP 는중복 ACK 을통해패킷손실을감지한뒤빠른복구모드로진입하며, 손실된패킷에대한복구가모두끝난이후비로소혼잡회피를수행한다. 복구구간동안에는사실상혼잡윈도우값이동결되기때문에복구시간이길어지면길어질수록 TCP 의성능은저하된다. 제안하는복구알고리즘은 TCP 의혼잡제어와손실복구메커니즘을분리시켜손실감지이후곧바로혼잡회피구간으로진입할수있도록하여복구지연오버헤드를효율적으로감소시켰다. 시뮬레이션실험을통해우리는제안하는복구기법이기존의, + SACK 및 등과비교하였을때가장최적의방식으로동작함을확인할수있었으며, 한윈도우내에서패킷의손실이많이발생할수록성능차이가보다뚜렷함을보였다.

6 SACK SACK SACK (a) One packet drop (b) Two packet drops (c) Three packet drops SACK SACK SACK (d) Six packet drops (e) Seven packet drops (f) Eight packet drops 그림 7 패킷손실수의변화에따른시퀀스증가량비교 향후연구로는, 보다다양한환경하에서복구시간을비교할필요가있으며, 논문내에서의가정이얼마나타당한지확인하는작업이요구된다. 즉, 중복 ACK 3 개이후의 SACK 홀들을손실로가정하는것이패킷재배열측면에있어서다른변종들과비교할만큼강인한지분석해보아야하며, 가능하다면기존의패킷재배열에강인한 TCP 변종알고리즘을포함할수있도록개선하여야할것이다. 마지막으로본논문에서제안하는복구알고리즘을적용한 TCP 간의공평성 (fairness) 및이를사용하지않는다른변종과의친밀성 (friendliness) 에대해비교하는작업이요구된다. 관련연구 [1] W. R. Stevens, TCP/IP Illustrated - Volume 1 (The Protocols), Addison Wesley, Nov [2] S. Floyd, T. Henderson, The Modification to TCP s Fast Recovery Algorithm, IETF, RFC 2582, Apr [3] K. Fall, S. Floyd, Simulation-based Comparisons of Tahoe, Reno, and SACK TCP, ACM Computer Communication Review, vol. 26(3), Jul [4] S. Floyd, J. Mahdavi, M. Mathis, M. Podolsky, A. Romanow, An Extension to the Selective Acknowledgement (SACK) Option for TCP, IETF, RFC 2883, Jul. 2. [5] M. Mathis, J. Mahdavi, Forward Acknowledgement: Refining TCP Congestion Control, In Proceedings of ACM SIGCOMM, Aug [6] A. Gurtov, R. Ludwig, Responding to Spurious Timeouts in TCP, In Proceedings of IEEE INFOCOM, Apr. 23. [7] M. Zhang, B. Karp, S. Floyd, and L. Peterson, RR-TCP: A Reordering-Robust TCP with DSACK, In Proceedings of IEEE ICNP, Nov. 23. [8] P. Sarolahti, A. Kuznetsov, Congestion Control in Linux TCP, In Proceedings of the USENIX Annual Technical Conference, Jun. 22. [9] ns-2 (online). [1] N. Parverz, A. Mahanti, C. Williamson, TCP : Slow-but-Steady or Impatient?, In Proceedings of IEEE ICC, Jun. 26.

Microsoft PowerPoint - Chap09_TCP와 UDP [호환 모드]

Microsoft PowerPoint - Chap09_TCP와 UDP [호환 모드] 2011 년봄학기데이터통신 Chapter 09 TCP 와 UDP 목차 마스터텍스트 TCP스타일을의특성과스트림편집합니다전송둘째수준 1 1 셋째수준 2 TCP 세그먼트형식과기능넷째수준 2 다섯째수준 3 3 4 흐름제어 (Flow control) 기법 오류제어 (Error control) 기법 3 3 혼잡제어 (Congestion control) 기법 3 3 5