Flow control

Sliding Window

Sliding Window 방식을 사용하여 Flow control을 제공한다. Sliding Window란 무엇일까?

Window는 Ack 없이 Sender가 보낼 수 있는 최대 바이트의 개수, 즉 범위를 말한다. 저런 Window가 움직이면서 Window 안에 들어온 바이트들은 전송이 가능하다! 라는 것이 Sliding Window 방식이다.

그렇다면 이 Window의 크기는 어떻게 정해질까? 그림에서 나온 것처럼 Receiver가 Sender에게 Advertise한 rwnd과 Congestion control을 위한 cwnd 중에 더 작은 값이 바로 Window size가 된다. rwnd는 TCP 연결 때 서로 3-way handshaking을 하면서 알 수 있었고, cwnd는 추후에 다뤄볼 예정이다.

이런 Sliding window protocol은 Datalink layer에서도 발견할 수 있었다. 이 레이어에서는 Window size가 7이고 1부터 7까지가 해당 window 범위일 때, Ack 4를 받으면 4부터 11까지가 window 범위 안에 들어갔다. 즉, 한번 Window size가 고정되면 이 크기는 변하지 않았다.

그러나, TCP에서는 Window 사이즈가 늘어나거나 줄어들 수 있다. 해당 그림에서처럼 Window size가 7이었을 때, Ack 4를 받는다고 해보자. TCP에서는 단순히 Ack number만 받는 것이 아닌 Receiver의 rwnd도 꾸준히 수신하고, cwnd도 수신하고 있기 때문에 Window size가 10으로 늘어 4부터 13까지가 Window 범위 안에 들어가거나,

혹은 Window size가 5가 되어 4부터 8까지가 범위에 들어가거나 할 수 있다. 이때, window size가 아무리 감소해도 기존 window 범위 내에 있던 7이 window 범위 밖으로 밀려나거나 하진 않는다. 위 그림에서는 Window size가 아무리 감소해도 3이 되어 4부터 6까지가 범위로 설정되는 일이 생긴다면 OS나 프로그램에 문제가 생긴 것으로 간주할 수 있다.

이런 Sliding window를 사용하는 목적은 Datalink layer에서와 동일하다. Destination에 있는 buffer가 오버플로우 나지 않으면서도 전송을 효율적으로 만들기 위해 사용하는 것이다.

만약, 이런 상황이 있다고 생각해보자. Sender는 Segment 1번을 먼저 보내고 이에 따른 Ack를 기다린다. 이때, Receiver가 Ack를 보냈지만, rwnd가 0이기 때문에 Sender는 더 이상의 Segment를 보낼 수 없게 된다. 이후, Receiver가 다시 rwnd를 1000으로 설정하여 Ack를 보내주면 다시 Sender는 Segment를 보낼 수 있게 된다.

그러나, rwnd가 0인 Ack를 Sender가 수신한 이후 rwnd가 1000인 Ack가 없어졌다면, Sender는 계속해서 Segment를 보내지 못하는 상황이 발생할 수 있다. 이를 Deadlock 상황에 빠졌다고 표현하는데, 이를 방지하기 위해 Sender는 rwnd가 0인 Ack를 받은 시점부터 타이머를 구동시켜, 타이머가 타임아웃 될 때마다 Receiver에게 아직도 rwnd가 0인 지를 확인받는다. Receiver는 여전히 자신의 buffer 공간이 없다면 rwnd가 0임을 다시 Ack를 보내 알려주면 되고, 공간이 있다면 rwnd를 조정하여 다시 Ack를 보내준다.

Silly window syndrome

우리가 메시지를 보내는 상황을 생각해보자.
ㅋㅋㅋㅋㅋ 를 보내는 상황과
ㅋ
ㅋ
ㅋ
ㅋ
ㅋ
를 보내는 상황은 엄연히 다른 상황이다.
Sender 입장에서는 application layer에서 Enter키를 눌렀을 때의 메시지가 아래 단계 layer로 내려가 이 메시지가 Segment가 되어 전송된다. 즉, ㅋ를 하나만 보내도 이 ㅋ 하나만 가지고도 Segment로 만들어져 전송되게 된다. 이렇게 되면 전체 네트워크에서 Segment의 수가 훨씬 많아지고, 심지어 이 보낸 Segment에 의해 돌아오는 Ack도 발생하기 되니 네트워크에 Segment의 수가 매우 늘어나게 된다. Segment의 수가 많아지면 라우터에서 이 Segment 하나하나에 대해 처리해줘야 하기 때문에 네트워크의 성능이 저하된다. Data를 4000Byte만큼 포함하는 Segment 1개를 보내면 될 거를 1Byte data짜리 Segment를 4000개 만드는 상황이 발생하면 안되기 때문이다.

또한, 1Byte 데이터를 보내기 위해 TCP, IP header 각각 20Byte까지 총 40Byte가 추가로 붙게 되고, 이로 인해 비효율적인 운영 방식이 탄생한다.

또는 이런 상황을 생각해볼 수도 있다. Receiver에서 buffer에 들어온 데이터를 읽는 속도가 너무 느린 상황이다. Sender는 100Byte만큼을 보내고 싶은데, Receiver에서 데이터를 소모하는 속도가 너무 느리다면 계속해서 조금씩 데이터를 Sender가 보내야 하는 상황이 생길 수도 있다.

이런 비효율적인 상황이 발생하는 것을 Silly window syndrome이라고 한다. 즉, 이 Silly window syndrome은 Sender가 데이터를 천천히 내려보내거나 Receiver에서 데이터를 천천히 소비할 때 발생할 수 있다.

이런 Silly window syndrome을 해결하기 위한 방법으로는 두 가지가 존재한다.

Nagle's algorithm (created by sender)

Sender가 데이터를 천천히 만들어내어 아주 작은 Segment가 여러 개를 만들어져 보내는 상황을 해결하기 위한 방법이다. 핵심 내용은 1byte가 들어오면 이걸 곧이곧대로 Segment로 만드는 것이 아니라 좀 모아둔 후에 한번에 보내자는 것이다.

이 방법은 처음 들어온 데이터는 Segment로 만들어서 보내지만, 이 Segment에 대한 Ack가 오기 전까지 Application layer에서 내려온 데이터들을 buffer에 저장하고 있다가, Ack가 오면 한번에 Segment로 만들어서 보내는 방식으로 작동한다.

이때, Buffer에 쌓이는 데이터의 크기가 buffer size만큼 채워져 buffer가 꽉 차거나, 즉 Segment의 Data 필드에 들어갈 수 있는 최대 Byte 수만큼 채워지거나 rwnd의 반 정도가 차있으면 Ack가 오지 않았더라도 Segment로 만들어서 보낼 수 있게 한다.

이렇게 되면 상위 Layer인 Application layer에서 데이터가 느리게 내려온다면 Ack가 들어와서 데이터를 보낼 수 있고, 데이터가 빨리 내려온다면 Segment의 Maximum data size만큼 데이터가 쌓이거나 Window size의 반을 채우게 되어 데이터를 보낼 수 있다.

이로 인한 장점은 알고리즘이 간단하고, Application program의 속도에 맞춰 동작할 수 있다라는 장점이 있지만, 실시간성이 요구되는 Traffic들에서는 바로 데이터를 보내지 않기 때문에 적합하지 않을 수 있다.

이런 실시간성이 요구되는 Realtime traffic들에서는 효율을 생각해서 Nagle's algorithm을 적용하면 안되고, 빨리 보내야 한다. 여기서 사용되는 것이 Push operation 이다,

Push operation
Push bit(PSH)를 1로 설정하면 Application program이 TCP에게 이 트래픽은 실시간 트래픽이니까 효율 생각해서 Nagle's algorithm을 사용하지 말고, 그냥 들어오자마자 바로 Send하라고 전달할 수 있다. 그러면 Sending TCP는 이걸 받아서 바로 Segment로 만들어 전송하게 되고, Receiving TCP는 이걸 받아 바로 Receiving Application program으로 전송시키고 Ack를 전송하게 된다.

Clark's solution

이번에는 Receiver의 데이터 소비 속도가 너무 느려 Syndrome이 발생하는 상황을 해결하기 위한 방법이다.

이 문제가 생기는 이유가 Receiver에서 데이터를 소비하자마자 남은 Window size를 보내줄 때, 이 size가 너무 작아서 기인한 문제이므로, Window에 자리가 생겨도 일단 rwnd를 0으로 하는 Ack를 보낸 후, 조금 기다렸다가 Ack를 보내주면 된다는 해결책이다. 역시 Nagle's algorithm과 유사하게 Buffer에 Segment의 data 필드 최대 사이즈만큼 비어있거나, 버퍼의 절반이 비어있을 때(= Window size의 절반)는 바로 Ack를 보낼 수 있다.

Delayed acknowledgment

혹은 아예 Clark's solution과 달리 rwnd가 0인 Ack를 먼저 보내는 것이 아니라 Ack 자체를 늦게 보낼 수도 있다. 그러나, 이렇게 되면 Sender가 Segment를 보내고 Ack를 기다리는 타이머에서 타임아웃이 될 수 있기 때문에 타임아웃이 발생하기 전에는 Ack를 보내줘야 한다. 이 Delay를 조절하지 못하면 Sender에서는 Segment를 재전송할 수도 있기 때문에 주의해야 한다.

Window scale factor option

Flow control의 방식은 2가지가 있었다. Go back N 방식과 Selective repeat 방식이 그 두 가지 방식이다. 이 두 방식은 각각이 가지는 Maximum Sequence Number가 달랐다. TCP Header를 보며 알아보자.

여기서 Sequence number는 32bit로 표현되므로, Go back N 방식에서는 2^32 - 1개만큼의 Maximum SN 값을 가지고, Selective repeat 방식에서는 2^31만큼의 Maximum SN 값을 가질 수 있다.

그러나, 이에 비해 Window size는 16bit만을 사용한다. 이 사이즈가 과연 충분한 크기를 가지는걸까?

Window size를 16bit로 표현했을 때의 최댓값은 2^16 * 8개만큼의 bit를 보낼 수 있다는 것이 된다. 이에 따른 Utilization을 계산해보자. 만약 두 컴퓨터가 1.2Gbps 속도의 전송 속도를 보장받고, 거리는 10,000km만큼 떨어져있다고 해보자.

Utilization(%) = Transmission Delay(TD) / (TD + (2 * Propagation Delay(PD))) * 100

TD는 전송량을 전송 속도로 나눈 것이므로 대략 600,000 / (1.2 * 10^9)이고, PD는 전송 거리를 전송 속도로 나눈 것이기 때문에 10,000 / 200,000 (신호의 속도) 가 된다.

이렇게 계산한 Utilization은 매우 작은 값이 나온다. 즉, Utilization이 엄청 안 좋은 비효율적인 방식이라는 말이 된다. 이 이유는 역시 Ack없이 한번에 보낼 수 있는 Window size가 너무 작기 때문이다.

이 Window size보다 좀 더 많은 데이터를 보낼 수 있게 해주는 것이 바로 Window scale factor option이다. 이 옵션은 Window size의 크기를 늘려줄 수 있는 옵션이기 때문에 새로운 Window size는 기존 헤더에서 정의했던 Window size 값에 2 ^ Scale factor 만큼을 곱한다. 만약 Scale factor값이 8이라면 2 ^ 8만큼 기존 Window size에 곱하면 그게 새로운 New Window size가 되는 것이다.