http://www.kocw.net/home/cview.do?cid=6166c077e545b736
컴퓨터네트워크
인터넷을 동작시키는 컴퓨터네트워크 프로토폴을 학습한다.
www.kocw.net
rdt3.0 이용률
Reliable한 Data transfer를 하기 위해서 unreliable한 underline link에서 발생하는 문제점인 packet error, packet loss를 해결해야 한다. 해결하기 위한 rdt에 관해 알아보았다. rdt를 실제로 사용할 수 있을까?
rdt를 사용할 수는 있지만 utilization(이용률)이 안좋다.
sender는 transmission time (패킷의 모든 비트가 link에 올라타는데 걸리는 시간)동안 일을 하고 패킷이 receiver에게 도착해서 응답이 오는데 걸리는 시간(RTT)동안 아무 일도 하지 않는다. 이용률은 약 0.00027으로 매우 비효율적이다.
따라서 이용률을 높이기 위해 한번에 여러 packet을 보내고 한번에 여러 feedback을 받는 방식을 지향해야 한다.
pipelining
그러한 방식을 PipeLining이라 한다. 이용률이 높아지는 것을 확인할 수 있다.
TCP는 pipelining을 사용한다.
pipelining을 가능하게 하는 프로토콜은 go back N, selective repeate 두가지가 있다.
go back N
한번에 보내는 packet 수를 window size=N이라 한다. 그리고 cumulative ACK를 feedbck으로 받는다.
ACK(11)은 11번 패킷까지 정상수신했으며 12번을 기다리고 있다는 뜻이다.
패킷을 N개 보낼때 각 패킷에 대한 타이머가 있다.
n번째 패킷에 대해 타임아웃이 발생하면 윈도우에서 n 이상의 번호를 갖는 패킷들을 모두 재전송한다.
gbn에서 receiver는 단순하게 동작한다. 자신이 받아야 할 번호의 패킷만 기다린다.
자신이 기다리는 번호의 패킷이 아니면 다 버린다.
패킷(1)를 수신한 후 ACK(1)를 피드백하고 패킷(2)를 기다린다. 이 때 패킷(3),(4)가 먼저 도착하면 버린다.
그리고 응답은 ACK(1)을 한다. (정상수신한것은 패킷(1)까지이므로)
gbn 예시
window size = 4이고 sender가 pkt0,1,2,3을 보내고 각각 timer를 세팅한다.
receiver는 pkt0을 수신하고 ack0을 피드백한다. sender는 ack0을 수신하면 pkt0에 대한 타이머를 끈다.
그리고 window를 한칸 이동한다. pkt 1,2,3,4가 window가 된다.
window가 이동함에 따라 sender는 pkt4를 보낼 수 있게 되고 pkt4를 보내고 timer를 세팅한다.
마찬가지로 receiver가 pkt1 수신, ack1 피드백, sender는 ack1을 수신하고 window 이동하고 pkt5를 보낸다.
하지만 sender가 보낸 pkt2에 loss가 발생한다. receiver는 pkt1까지 수신해서 pkt2만 기다리는 상황이다.
따라서 이후 도착하는 pkt 3,4,5는 모두 버린다.
시간이 흘러 sender측에서 timeout(2)가 발생한다. 따라서 window에서 2 이상인 2,3,4,5pkt을 재전송한다.
sender 입장에서 packet을 전송하는 것을 생각해보자.
loss나 error가 없다면, pkt 0,1,2,3,4,5, ..... 100,101, ... 과 같이 다음 패킷을 순차적으로 보내게 된다.
pkt5가 loss된다면 pkt 0,1,2,3,4,5,6,7,8 (gbn) 5,6,7,8,9,10 ,,,, 과 같이 8에서 window size 4만큼 돌아와 5부터 다시 보낸다.
이러한 이유로 gbn이라 불리는 것이다.
window에 있는 pkt들은 sender가 buffer에 보관하고 있어야 한다.
왜냐하면 아직 receiver의 정상수신 여부를 모르기 때문에 재전송해야 할 수 도 있기 때문이다.
gbn의 문제점은 불필요한 재전송이 많다는 것이다. pkt5 하나만 유실되더라도 5,6,7,8 4개의 pkt을 재전송한다.
실제 시스템에서는 window가 더 클 것이고 이 문제가 더 부각된다.
selective repeat
gbn을 개선해서 유실된 pkt만 선택적으로 재전송하겠다는 것이다.
ack(n)이 n번까지 전부 정상수신했다는 의미가 아닌 n번에 대해서만 정상수신했다는 의미를 갖는다.
timeout이 발생한 pkt에 대해서만 재전송한다.
receiver는 순서에 맞지 않게 들어온 pkt이더라도 buffer에 저장한다.
즉 receiver가 2번 pkt을 기다리고 있더라도 3번을 수신하면 3번을 버퍼에 저장한다. 그리고 ack3을 해준다.
selective repeat 예시
sender는 ack0, ack1을 피드백받음에 따라 window가 1칸씩 이동하고 pkt 4,5를 보낸다.
pkt2가 loss되었지만 receiver는 pkt3,4,5가 오면 각각 버퍼에 저장하고 ack3,4,5를 보낸다.
sender는 timeout(2)가 발생해서 pkt2를 재전송한다.
receiver는 pkt2를 수신하면 buffer에 pkt 2,3,4,5를 다 얻게 되고 application layer로 올려준다.(deliver)
(pkt을 순서대로 받는 경우는 바로 application layer로 deliver하고 아닌 경우에는 앞에 못받은 pkt 자리를 빼고 buffer에 저장해놓고 받으면 deliver 한다.)
그리고 ack2를 피드백한다.
즉 문제가 발생한 pkt만 선택적으로 재전송한다.
sender는 0,1,2,3,4,5,(2유실),2,6,7,8,... 과 같이 전송한다.
seq# 범위
seq#를 1씩 증가하게 했지만, seq#는 헤더의 필드값이고 작을수록 좋다.
따라서 window size가 n일때 최소 seq#의 범위를 사용하는 것이 좋다.
window size=n일때 seq#의 범위가 n+1이라면?
ack0,1,2가 모두 유실되어서 sender가 0을 다시 보내면 receiver는 pkt0이 다음 window의 pkt0인지 재전송 된 pkt0인지 구분할 수 가 없다. 따라서 duplicated pkt인지 아닌지 알 수 있을 만큼의 seq# 범위를 사용해야 한다.
TCP에서 사용하는 방법은?
TCP에서는 위 두 방법 중 하나를 그대로 사용하지는 않는다. 왜냐하면 window의 모든 pkt에 대해 timer를 설정하는 것은 window size가 커진다면 부하가 상당하기 때문이다.
window르 대표하는 timer를 하나 사용하고 ack는 gbn처럼 cumulative ack를 사용한다. (변형해서)
TCP
개요
- point to point
- 센더1명 리시버1명간의 통신만 한다.
- 엄격하게 말하면 소켓 한 쌍 끼리의 통신을 책임진다.
- reliable, in-order
- pipelined
- send&receive buffers
- 모든 프로세스는 senderd이자 receiver이므로 send buffer와 receive buffer를 모두 갖는다
- send buffer : 재전송하기 위함
- receive buffer : 순서가 어긋난 패킷을 저장해놓기 위함
- full duplex data
- 하나의 connection에서 양방향 데이터 이동 (모든 프로세서는 sender이자 receiver)
- connection oriented
- flow controlled
- sender는 receiver가 받을 수 있는 만큼 전송해야 함
- congestion controll
- network가 감당할 수 있는 만큼 보내야 함
tcp segment 구조
각 layer마다 전송단위가 있다. transport layer의 전송단위는 segment이며 application layer의 전송단위인 message가 segment의 data 부분에 들어오게 된다. 크기는 header가 data에 비해 매우 작다.
헤더에 어떤 필드들이 있는지 보자.
- port# (0~2^16-1 : 16ibt이므로)
- source port # : 보낸사람의 포트번호/ dest port # : 받는사람의 포트번호
- seq#
- ack#
- checksum
- error detection
- receive window
- 내 receive buffer에 유효한 공간을 상대방에게 알려줘 flow controll이 가능하게끔
- 기타 1bit짜리 flag들 ..
하나씩 알아봅시다.
seq# & ack#
seq#는 data의 맨 앞 byte의 번호다.
예를 들어 100byte짜리 message를 10byte씩 나눠서 segment를 만든다면, 첫번째 segment의 seq#는 0, 두번째는 10, 세번째는 20, ... 과 같이 맨 첫번째 byte 번호를 가져다 쓴다.
ack#는 cumulative ack를 사용한다. 다만 gbn에서 cumulative ack랑 다르다.
gbn에서 ack10이면 10번까지 정상수신했다는 뜻이지만 tcp에서는 9번까지 정상수신했고 10번을 보내달라는 뜻이다.
내용 'C'를 보내면 그것을 수신하고 echo back 하는 상황이다.
A에서 만든 seq#를 A의 send buffer에서 관리하고 B의 receive buffer에서 이것에 대응한다.
반대로 B에서 만든 seq#를 B의 send buffer에서 관리하고 A의 receive buffer에서 이것에 대응한다.
A가 seq42,ack79인 1byte 데이터 C를 보냈다.
ack가 79이므로 B는 seq79인 데이터를 보내고 자신은 42까지 수신했으므로 ack는 43으로 보낸다.
A는 다시 ack가 43을 받았으므로 seq43을 보내고 본인은 seq79까지 받았으므로 ack80으로 보낸다.
즉 A에서 보내는 세그먼트면 seq#는 자신의 send buffer에서, ack#는 자신의 receive buffer에서 관리하는 값이다.
tcp에서 실제 ack
실제로는 데이터를 수신하면 500ms정도 기다렸다가 ack를 하라고 권고한다. 2가지 이유가 있다.
- 내가 보낼 데이터가 생길 수도 있고 그럴 경우 ack와 같이 보내는 편이 이득이다.
- tcp에서 ack는 cummulative ack이다. 여러개 pkt이 동시에 오면 즉시 ack하기보다 기다렸다가 마지막 pkt에 대해 ack하는 것이 효율적이다.
timeout value
timer의 시간을 어떻게 설정해야 할까?
길게 설정하면 overhead가 적은 대신 recovery가 느리고, 짧게 하면 리커버리가 빠른 대신 overhead가 커진다.
segment를 전송하고 feedback이 오기 까지의 시간을 RTT라 한다.
RTT를 timeout value로 생각할 수 있다.
다만 RTT도 segment마다 상이하다. 그 이유는 아래와 같다.
- segment마다 이동 경로가 다르다.
- 경로가 같더라도, 각 상황마다 queueing delay가 다르다.
따라서 우리가 사용할 수 있는 것이 estimateRTT값이다.
samplertt가 실제 측정한 rtt값이다. 지금 측정한 rtt값에 alpha를 곱해 network 상황을 지나치게 반영하지 않도록 한다.
실제로 사용하는 timeout 값은 estimatedRTT에 4*devrtt를 더해준다. devrtt는 마진값이다.
식은 중요한게 아니고, timeout은 rtt에 어느정도 마진을 더해서 구한다는 정도를 이해하면 된다.
tcp에서 reliable data transfer
- pipeline 방식
- cumulative acks
- ack10 = 9번까지 잘 받았고 10번 달라
- single retransmission timer
- gbn과 유사하지만, gbn은 timeout(n)이 발생하면 window에서 n 이상의 pkt을 모두 재전송
- tcp는 timeout(n)이 발생하면 pkt n만 재전송
tcp 예시
3번째 시나리오가 cumulative ack의 장점을 보여준다. ack100이 유실되었지만 ack120이 정상 도착해 sender는 seq119까지 정상수신했다는 것을 알고 send buffer에서 199까지 비운다.
fast retransmit
사실 timeout value를 rtt와 마진을 사용해 정했다고 해도 꽤 긴 시간이다. pkt loss를 알 수 있는 다른 방법이 있다.
sender가 세그먼트 0,1,2,3, .... 100 까지 보냈다고 생각해보자.(seq# 1씩 증가) 그리고 세그먼트 10이 유실되었다.
receiver는 ack 0,1,2,3, ...9, 10, 10, 10.. 을 피드백할 것이다.
(tck는 cummulative ack를 사용하고 10이 유실되었으므로 11이후의 세그먼트에 대해서는 모두 ack10을 피드백)
따라서 duplicated ack를 받으면 loss가 발생했음을 알 수 있다.
tcp에서는 권고사항으로 timeout이 발생하기 전에도 duplicated ack를 3번 받으면 재전송 할 것을 권고한다.
(ack 10 받은 이후 3번의 ack 10, 즉 총 4번이)
이 방을 fast retransmit이라 한다.
fast retransmit은 꼭 필요한 기능은 아니지만 더 빠르게 동작하기 위한 최적화 기술이다.
반면 timer는 반드시 있어야 정상적으로 동작한다.
flow control
센더가 리시버의 리시브 버퍼의 가용 공간을 넘는 세그먼트를 보내 봐야 의미가 없다.
tcp 세그먼트 헤더의 receive buffer라는 필드에 가용 공간을 넣어서 알려준다.
flow control은 중요한 기능이지만 해결 방법이 단순하다.
flow control 특이상황
flow control은 보내는 data의 양을 조절하는 것인가? 속도를 조절하는 것인가?
보내는 속도라는것이 보내는양/단위시간이기 때문에 어느 하나를 조절한다고 할 수 없다.
A와 B간의 tcp 연결이 있고, A는 전송만 하고 B는 받기만 한다고 가정하자.
B의 application에서 data를 read하지 않아서 B의 recv buf가 꽉 차있으면 B는 A에게 보내는 세그먼트의 receive buffer 헤더값을 0byte로 보낼 것이다. 이에 따라 A는 세그먼트를 보내지 않을 것이다.
B는 받기만 하니까(보내고자 하는 data가 없으니까) A가 세그먼트를 보내야 그에 대한 응답을 보낸다. 따라서 receive buffer에 공간이 생겨도 A로부터 세그먼트가 오지 않으면 알려줄 수 없다.
A도 B의 receive buffer에 공간이 없다는 정보를 받았으므로 B로 더이상 세그먼트를 보내지 않는다.
즉 A,B 모두 가만히 있는 상황이 발생한다. 이 상황을 어떻게 해결할까?
tcp에서 세그먼트 헤더의 recv buffer 필드값이 0이면 주기적으로 data가 비거나 1byte만 든 세그먼트를 보낸다.
이 세그먼트를 보내야 ack를 받을 수 있고 이 ack의 헤더의 recv buffer 값을 보고 buffer에 다시 빈 공간이 생겼는지 알 수 있기 때문이다.
connection management
tcp 연결을 하기 위해서는 양쪽에 recv buffer와 send buffer 2개의 버퍼가 있어야 한다.
그리고 send buf에서는 나의 seq#를 알아야 하고 recv buf에서는 상대방의 seq#를 트래킹해야한다.
이렇게 세팅을 한 이후부터는 relialbe data transfer를 할 수 있는 것이다.
즉 tcp connection을 위해 아래 세팅들을 해야 한다.
- send buf, recv buf 만들기
- 나의 seq# 만들고 상대에게 알려주기
- 상대의 seq# 알아오기
이것을 connection establishment 또는 3way handshake라 한다.
3 way handshake
이름이 3way handshake인 이유는 3번 왔다갔다 하기 때문이다.
- 클라이언트가 먼저 syn을 보낸다.
- syn은 data가 비어있고 세그먼트 헤더의 syn 필드값이 1이다.
- 위에서 tcp 세그먼트 헤더의 1bit짜리 S로 표시된것이 syn이다.
- tcp 커넥션을 연결하고 싶다는 의미다.
- seq# 필드값도 넣어서 보낸다 (seq# = x)
- syn은 data가 비어있고 세그먼트 헤더의 syn 필드값이 1이다.
- 서버가 seq에대한 피드백 synack를 보낸다
- syn=1
- seq=y로 자신의 seq#알려줌
- 세그먼트 헤더의 ack=1
- acknum = x+1 (클라이언트가 보낸 seq#인 x에 1을 더한값)
- 클라이언트가 synack에 대한 ack를 보낸다
- 이 ack는 syn=0이다.
- data를 포함한다.
즉 tcp 연결을 하기 위해서는 syn -> synack -> ack의 3 way handshake가 필요하다.
이 과정 이후에 send buf, recv buf가 생성된다.
3way가 아닌 2way만 사용하면 서버 입장에서는 본인이 보낸 메세지에 대한 응답을 받지 못하기 때문이다.
즉 HTTP 요청 응답에서 첫번째 request는 3way handshake의 마지막 과정인 ack가 data를 포함하고 있는 것이다.
tcp connection 종료
- 클라이언트가 자신이 보낼 데이터는 다 보냈다는 의미로 FIN을 보낸다. 서버는 이에대해 ack를 보낸다
- 서버가 보낼 세그먼트는 남아있을 수도 있으니 마저 보냄
- 서버도 보낼 세그먼트를 전부 보냈으면 fin을 보낸다. 클라이언트도 fin에 대해 ack를 보낸다.
- timed wait은 buffer를 해제하지 않고 잠시 기다리는 것이다 (약 30초)
- 이것은 클라이언트가 보내는 마지막 ack가 유실되는 common case를 해결하기 위함이다.
- 마지막 ack가 유실되면 서버는 fin에 대한 timeout이 발생해 fin을 재전송한다. 이 때 클라이언트가 자원을 release하고 종료해버렸다면 서버는 영영 fin에 대한 ack를 받지 못해 계속 재전송한다.
congestion control
sender는 nw와 recv중 상태가 더 안좋은 쪽에 data를 보내는 속도를 맞춰야 한다.
즉 recv와 nw의 상태를 계속 tracking해야 한다.
recv의 상태는 앞에서 배운 flow control mechanism에 의해 알 수 있다. (헤더의 receive buffer 값)
하지만 nw의 상태는 어떻게 알 수 있을까..? congestion control mechanism에 의해 알아낸다.
nw가 막혀서 pkt loss나 error 가 발생하면 tcp는 pkt을 재전송한다.
따라서 tcp 관점에서 nw가 막히면 tcp는 overhead를 추가해서 nw 상태를 악화시킨다.
tcp는 그래서 nw 상황이 안좋으면 자기 자신의 속도를 낮춰고 좋아지면 높여야 한다.
네트워크 상황을 아는 방법은 2가지가 있다
- end-end congestion control
- 실제 사용하는 방식
- ACK가 빨리 오는지, 느리게 오는지,, 등 ACK의 동작으로 nw 상태를 유추한다.
- network-assisted congestion control
- 네트워크에서(라우터 등) 정보를 제공해줌
- 라우터는 forwarding만 해도 벅차기 때문에 실제 구현되지 않음
pipe에 물을 붓고 반대쪽에서 받는 상황을 생각해 보자. 물을 무작정 많이 부으면 pipe가 터진다.
따라서 조금만 부어보고 반대편에서 받는데 성공하면 조금 더 부어보는 식으로 적정량을 알아내야 한다.
TCP의 congestion control 역시 비슷하다.
- slow start
- 조금씩 보내는 것 부터 시작한다
- 하지만 1,2,3,4.. 와 같이 보내는 양을 늘린다면 너무 느리다.
- 따라서 늘리는 것은 1,2,4,8,16,32,..와 같이 지수적으로 증가한다
- additive increase
- 다만, threshold에 도달한 시점부터는 linear하게 증가한다
- multiplicative decrease
- pkt loss가 발생하면 1/2로 감소한다
- nw는 공유자원이고 막혔다 싶으면 발을 다같이 빼야 nw가 풀린다.
여기서 말하는 늘리고 줄인다는 것의 단위는 MSS만큼 늘리고 줄인다는 것이다.
MSS는 maximum segment size=500byte이다.
window size가 최초에 1 MSS에 해당한다.
위의 그래프에서 보이는 것 처럼 3가지 과정이 계속 반복된다.
적정값을 찾아서 정착하면 좋겠지만 nw 상태는 계속 변하기 때문에 그러기는 힘들다.
전송속도는 rough하게 위와 같이 나타낼 수 있다.
RTT보다는 congestion window가 변동이 크다. congestion window는 nw의 상황에 따라 결정된다.
즉 전송속도는 nw의 상황에 따라 결정된다고 할 수 있다.
nw의 상황은 많은 사람이 사용하면 안좋아지고 적은 사람이 사용하면 좋아진다.
서로가 서로의 전송속도의 영향을 미치는 상황인 것이다.
slow start
MSS에 해당하는 window size에서 시작해서 점점 늘린다.
지수적으로 증가하기 때문에 이름은 slow start이지만 실제 증가 속도는 빠르다.
하늘색 그래프가 tcp 1버전 타호이다. (80년대, 지금은 사용하지 않음)
타호는 1mss의 window size로 시작한다. 지수적으로 증가하다가 threshold를 넘은 시점부터는 선형적으로 증가한다.
pkt loss가 발생하자 window size를 1로 줄이고 threshold를 loss가 발생한 시점의 window size의 1/2로 설정한다.
이후 다시 slow start를 하고 threshold를 넘는 순간부터 linear increase를 한다.
버전 2 르노가 등장한다.
tcp에서 pkt loss를 판단하는 방법은 2가지다.
- timeout이 발생
- 3 duplicated ack 발생
이 2가지의 상황은 다르다.
2는 특정 pkt만 loss가 발생한 것이다. 뒤의 pkt들은 정상적으로 갔기 때문에 3 dup ack를 수신한 것이다.
반면 1은 여러 pkt이 loss된 것이다. 따라서 nw 상태가 더 안좋은 것은 1 상황이다.
르노는 2로 인해 loss를 감지하면 다르게 대응한다.
threshold와 window size를 모두 loss가 발생한 시점의 window size의 1/2로 줄이고 그 시점부터 선형 증가를 시작한다.
1로 인한 pkt loss 탐지면 타호와 똑같이 window size 1로 가서 시작한다.
최초 threshold는 구현하기 나름이다.
tcp fairness
bandwith R인 링크를 K개의 tcp connection이 공유한다면 R/K로 공평하게 나눠진다.
congestion control에서 선형 증가와 1/2로 줄이는 과정을 반복하다 보면 두 커넥션이 공평하게 사용하는 직선에 수렴한다.
다만 TCP connection 간에 공평한 것이므로 tcp connection을 많이 연 사람은 많이 사용하게 된다.
