Grace

❗ Congestion control의 필요성

TCP 통신시에 sender는 네트워크 환경과 receiver의 역량, 2가지를 고려하여 자신의 flow를 조정해야 한다.

두가지 변수 중에 상황에 따라 상대적으로 더 좋지 않은 변수에 맞춰야한다.

congestion control은 네트워크 환경을 고려하여 통신하는 TCP의 원리이다.

network 환경은 기본적으로 public이다. 누구나 인터넷을 사용할 수 있다. 그래서 아무런 제약없이 인터넷을 사용하도록 해두면 네트워크가 막힐 수 밖에 없다. TCP의 reliable을 보장하는 특성상, 패킷이 유실될 경우 재전송을 하기 때문에 네트워크가 제약없는 상태에서 막히면 막힐 수록 상황은 더욱 악화되기 마련이다. 내가 양보를 해야지 나도 살고 너도 살고 우리가 살게 되는 것이다. 네트워크는 아주 소중한 자원이기 때문에 서로 적절히 양보하며 자원을 사용해야 한다.

그렇다면 congestion control은 어떻게 네트워크 환경을 고려하여 통신을 진행할 수 있을까?

접근할 수 있는 방법은 크게 보면 2가지가 존재한다. 네크워크에서 직접적으로 정보를 받는 방식과 통신하는 노드를 통해 정보를 받는 방식이다. 라우터를 할일이 굉장히 많기 때문에 현실적인 제약으로 네크워크에서 직접적으로 정보를 받는 방식은 구현되지 않고 있다. congestion control은 후자, 그중에서도 노드간의 통신에서 간접적 정보를 통해 판단을 내리는 방식을 채택한다. 간단히 말하면 조금씩 조금씩 보내보다가 괜찮으면 좀 더 보내고 그러다가 유실이 발생하면 window size를 줄이는 방식이다.

❗ congestion control의 원칙과 작동원리

1. slow start

통신의 초기에는 네트워크의 상황이 어떠한지 판단이 불가능하기 때문에 세그먼트 1개 즉 1MMS크기의 window size를 갖고 통신을 시작한다. 1MSS로 시작하여 threshold 값 까지 exponential 하게 증가한다. threshold를 모르는 초기에는 유실이 발생할 때 까지 exponential하게 window size를 늘린다.

MSS(Maximun Segment Size : 세트먼트가 갖을 수 있는 최대크기, 500byte)

2. addtive increase

window size가 threshold를 지나간 시점부터는 linear하게 증가한다.

3. multiplicative decrease

유실이 발생했을 경우 threshold를 window size의 절반으로 떨어뜨린다. 그리고 window size는 유실판단 기준에 따라 달라지게 된다. 유실은 timeout과 3 duplication ack를 받은 경우로 나뉜다. 1) timeout의 경우 정말로 패킷이 유실되어 오지 않은 경우이기 때문에 네트워크 상황이 좋지 않다고 판단하여 window size가 1MSS로 설정된다. 2) 3 duplication ack의 경우는 네트워크 상황이 나쁘지는 않지만 하나의 패킷이 유실된 경우이기 때문에 window size를 threshold값으로 설정하여 바로 linear한 통신을 진행하게 된다.

최적의 threshold값을 찾아 그 언저리 값으로 통신하면 되는거 아니야? 하고 생각할 수 있지만 threshold는 네트워크 상황과 리시버의 환경에 따라 계속해서 변화하기 때문에 congestion control은 변화하는 threshold값을 계속해서 찾아나가는 과정이라고 보는 것이 맞는것 같다.

❗ Is Tcp fair?

TCP는 독립적인 노드들이 자신의 Flow를 조정하는 방식으로 작동하는데, 이것이 과연 모두에게 공평한가에 대한 의문을 가질 수 있다. 만약 네트워크 사용량이 R이라면 n명의 사용자가 있을때 모두 R/n 만큼 사용가능한가 라는 것이다. 직관적인 이해를 조금 힘들 수 있지만 결국 R/n으로 수렴한다고 한다.

TCP 통신을 진행하기 위해서는 각 노드가 4가지를 선제적으로 알고 있어야 한다.

바로 send buffer size, receive buffer size , 자신의 seq#, 상대의 seq# 이다.

이것은 그 유명한 3way-handshake 과정에서 세팅된다.

3way-handshake 과정

tcp header 중 syn bit값을 넣는 필드가 있다. syn은 tcp handshake과정에서만 1bit로 설정되는 필드이다.

1. client는 server에게 syn bit = 1, 자신의 seq#=x를 담은 빈 세그먼트를 보낸다.
2. server는 client에게 syn bit = 1, 자신의 seq#=y, ack=1, acknum=x+1을 담은 빈 세그먼트를 보낸다.
3. client는 server에게 ack=1, acknum=y+1을 담은 세그먼트를 보낸다.

3번 과정에서의 패킷 안에는 http request가 함께 포함되어서 갈 수 있다.

연결 끊는 과정

1. client는 server에게 FIN을 보낸다. 이때 client는 더이상 데이터를 보내지 않는다. (client close)
2. server는 client에게 ACK를 보낸 후 자신이 미처 보내지 못한 데이터들을 모두 보낸다.
3. 그 후 server는 client에게 FIN을 보낸다.
4. client는 server에게 FIN에 대한 ACK을 보낸다.

timed wait

4번 과정 이후 client는 timed wait을 가지면서 자신이 통신과정에서 사용했던 데이터들을 버리지 않고 기다린다. 이는 만약 4번의 ACK가 유실되었을 경우 ACK를 받지 못한 server가 client를 향해 무한 FIN을 보낼 수 있기 때문이다. 데이터를 일정시간(timeout value와 유사한)동안 갖고 있어야지 FIN에 대한 대처가 가능하다.

flow control이란?

tcp 통신시 각 노드에게는 send buffer / receive buffer가 존재한다. cumulative ack를 사용하는 특성으로 인해 패킷유실, 네트워크환경 등에 의해서 순서대로 오지 못한 패킷들을 임시로 저장해놓기 위해서이다.

process가 소켓에서 read를 하게 되면 갖고 있는 receive buffer에서 데이터를 올려받게 된다. 따라서 컴퓨터의 성능이나 다른 해야할 작업들이 많은 상황에서 receive buffer의 데이터들이 올라가는것이 딜레이가 될 수 있다. 이런 다양한 이유로 receiver가 데이터를 받을 수 있는 역량, 즉 receiver buffer의 남은 용량을 고려하여 통신이 진행될 수 있도록 하는 것이 flow control이다. flow는 하천, 강물과 같은 느낌이 있다. flow control는 이 flow를 조절하면서 통신하는 것이라고 기억하면 편할 것 같다.

구현방식

구현 방식은 생각보다 매우 간단한다. tcp segment의 header에 receiver buffer라는 필드가 있다. receiver는 ack를 보낼때 receiver buffer 필드의 수용가능한 데이터 용량을 기입하게 된다.

issue

A와 B가 tcp 통신 중이라고 가정해보자. 통신이 진행되는 중간에 B의 receive buffer가 가득차게 되어서 B는 receive buffer필드에 0을 넣은 ACK를 A에게 보내게 된다. 이것을 받은 A의 반응은 무엇일까? B의 버퍼가 가득차서 B에게 데이터를 보낼 수 없으니 아무것도 할 수 있는게 없다.

=> 실제 TCP구현에서는 A가 데이터가 들어있지 않는 세그먼트를 주기적으로 B에게 보내는 방식으로 처리된다.

tcp는 통신과정의 신뢰성을 확보하기 위해 패킷에러와 패킷유실에 대해 대처한다. 그 중에서 패킷의 유실을 처리하기 위한 메커니즘으로 타이머를 이용한다.

타이머를 통한 패킷유실 처리 원리와 타이머의 시간이 얼마로 설정되는지에 대해 알아보자

Packet loss 대처

- timer

만약 sender가 패킷을 보내고 receiver에게 도달하기도 전에 패킷이 유실되었다면 어떻게 될까. receiver는 자신에게 어떤 패킷도 오지 않았으므로 그저 침묵이 흐를 것이다. 이러한 경우에 대비하기 위해 timer를 사용한다. timer를 통해서 일정시간동안 feedback이 오지 않을 경우 패킷이 유실되었다고 판단하여 재전송을 한다.

- timer의 시간설정 문제

그렇다면 timer의 시간은 얼마로 설정해야 할까? 결론만 말하자면 정답은 없다. ‘적당히’ 설정해야 한다. 짧으면 무조건 좋을까? 만약 짧다면 네트워크 상황으로 인해 패킷이 약간 지연될 경우 오는 도중에 timer가 터져서 재전송이 진행될 수 있다. 정말로 패킷유실이었다면 빠른 대처가 되는 것이지만 그렇지 않을 경우에는 중복된 패킷으로 인해 네트워크 상황만 더 혼잡하게 만드는 가능성이 있다. 너무 길면 통신 자체가 원할하지 않을 수 있겠다.

TimeOut Value

timeout의 값은 어떻게 설정해야 할까? 일단 segment가 전송이 되었다가 되돌아오는 시간인 RTT(Round trip time)을 기준으로 한다. 하지만 RTT는 패킷마다 다르고 같은 경로를 지나간다고 하더라도 네트워크 상황에 따라 라우터에서 발생하는 queueing daley 등으로 인해 RTT가 달라질 수 있다. 즉 RTT는 상황에 따라 천차만별이다. 따라서 현재시점까지의 RTT 샘플을 계산하여 고려한 EstimatedRTT를 사용한다.

EstimatedRTT = (1-a)*EstimatedTRR + a*SampleRTT

하지만 EstimatedRTT를 사용하면 타임아웃의 기준이 다소 빡빡할 수 있다. 그래서 실제 tcp통신에는 Deviation(편차)의 4배 정도를 더한 값으로 사용한다.

TimeOut Value = EstimatedRTT + 4*DevRTT

RTT를 기준으로 하되 마진을 더해주는 느낌이다.

Fast Retransmission

timer가 터지기 전에 패킷의 유실을 판단할 수 있는 tcp의 권고사항이다. tcp는 cumulative ack를 사용하기 때문에 만약에 중간에 10번째 패킷이 유실되었다면 그 이후에 보내진 패킷들에 대해 모두 ack10이라는 피드백을 받을 것이다. 하지만 10번째 패킷이 다소 늦게도착해서 먼저 도착한 11,12,13…번째 패킷에 대해 ack10을 받은 것일 수도 있다. tcp에서는 3번의 duplication ack를 받은 경우 즉 4번의 같은 ack를 받은 경우 유실로 판단해도 좋다고 권고하고 있다. 이는 tcp의 필수구성 요건은 아니며 timer의 optimizaion이다.

풀이

1. \0가 아닌 .을 기준으로 문자열을 입력받기 위해 getline을 사용하여 .을 delimiter로 한다.

2. 받은 문자열을 쭉 돌면서 (이나 [인 경우에는 스택에 push한다.

3. 받은 문자열을 쭉 돌면서 )이나 ]인 경우에 짝이 맞지 않거나 스택이 비어있는 경우 등 균형이 잡히지 않는 경우는 걸러내준다. bool res = fasle;

4. res를 기반으로 결과를 출력한다.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(){
    while(1){ // if same, return 0
        stack<int> st;
        string input;
        bool res= true;
        getline(cin, input);
        if(input.compare(".") == 0) break;
        
        for(int i=0; i<input.length(); i++){
            if(input[i] == '(' || input[i] == '['){
                st.push(input[i]);
            }
            if(input[i] == ')'){
                if(st.empty()){
                    res = false;
                }else if(st.top() == '('){
                    st.pop();
                }else{
                    res = false;
                }
            }
            if(input[i] == ']'){
                if(st.empty()){
                    res = false;
                }else if(st.top() == '['){
                    st.pop();
                }else{
                    res = false;
                }
            }
        }
        if(!st.empty()) res = false;
        
        if(res) printf("yes\n");
        else printf("no\n");
    }

    return 0;
}

tcp의 reliable을 충족시키는 protocol은 pipeline 방식을 사용한다. 현실에서는 데이터를 보내는 시간보다 RTT(Round Trip Time)가 훨씬 길기 때문에 더욱 효율적인 통신을 위해 pipeline을 사용한다. 다시 말해서 하나씩 하나씩 패킷을 전송하는 방식이 아니라 일정한 패킷단위를 쏟아붇는 방식으로 통신이 진행된다는 것이다.

pipeline protocol의 기본 접근방법, 개념적인 형태 2가지에 대해 알아보자

1. Go-Back-N

1) window size

pipeline 방식으로 통신하기 위해 sender와 receiver는 window size를 갖는다. 얼마만큼의 패킷을 한번에 전송하고 받느냐에 관한 크기이다.

2) cumulative ACK

Go-Back-N에서의 ACK는 cumulative한 ACK이다. 만약 ACK 11을 받았다면 11번 패킷을 를 포함한 그 전의 패킷를 모두 받았다는 것을 의미한다.

3) Receiver No buffer

버퍼가 없다. cumulative ack이기 때문에 만약 11번 패킷을 받을차례인데 11번 패킷이 유실되어 그 다음패킷인 12번 패킷이 온다면 receiver는 10번까지의 패킷을 모두 받은 상태에 11번 패킷을 받아야 하므로 12번 패킷을 버리게 된다.

4) time out

window size안에 있는 모든 패킷에 대해 timer가 설정이 된다. 만약 window size가 4이고 6번 패킷이 유실된 상황이라면, windows는 ACK6을 받을 수 없기때문에 6~9패킷에 머물러 있을 것이다. 시간이 흐르면 6번 패킷의 타이머가 터지게 되고 6번부터 시작하여 다시 패킷을 재전송하게 된다. 이때 9번패킷에서 다시 n만큼 돌아와 6번패킷부터 재전송하게 되므로 n만큼 되돌아온다고 하여 Go-Back-N이다.

2. Selective Repeat

1) window size

pipeline 방식으로 통신하기 위해 sender와 receiver는 window size를 갖는다. 얼마만큼의 패킷을 한번에 전송하고 받느냐에 관한 크기이다.

2) non-cumulative ACK

개별 패킷에 응답하여 ack를 보낸다.

3) timeout

receiver에게 buffer가 존재하기 때문에 go-back-n처럼 n만큼 되돌아가서 재전송하지 않고, ack를 받지 못한 패킷에 한해서만 개별적으로 재전송을 한다.

TCP는 GBN과 selective repeat의 장점들만 모은 복합적인 형태의 protocol을 차용하고 있다.

TCP는 신뢰성있는 통신을 제공한다고 알려져있다. 그렇다면 TCP를 사용하지 않으면 신뢰성 확보할 수 없다는 것이다. 왜 그럴까? transport밑으로 존재하는 계층들이 현실적으로 완벽하지 않기 때문이다. 어떤 기술이든 완벽한것은 없기 마련이다. 특히 router의 queue에서 90% 이상의 Loss가 발생한다.

그렇다면 신뢰성을 확보하기 위해서는 어떤것을 해주어야 할까?

packet error와 packet loss. 이 두가지에 대해 대처해주면 완벽한 신뢰성이 확보되었다고 할 수 있다. error와 loss를 해결하기 위해 어떤 기술적 원칙들이 사용되는지 확인해보자.

1. Packet error 대처

- error detection

ckecksum을 통해서 패킷에 에러가 있는지 없는지 확인을 해야 한다.

- feedback

만약 에러가 있다면 에러가 있는 데이터를 받았기 때문에 재전송을 요구하는 피드백을 보내고, 정상적인 패킷을 받았다면 잘 받았다는 피드백을 보낸다.

- retransmission

만약 에러가 있는 패킷을 받았다는 피드백을 받은 경우 sender는 동일 패킷을 재전송을 한다.

- sequence #

그런데 문제가 발생한다. 재전송되어서 온 패킷이 receiver입장에서는 재전송되어서 온것인지 아니면 sender 동일한 패킷을 보낸 것인지 판단할 수 없다. 이 문제를 해결하기 위해서 패킷을 특정할 수 있는 seq #를 사용하여 통신한다.

2. Packet loss 대처

- timer

만약 sender가 패킷을 보내고 receiver에게 도달하기도 전에 패킷이 유실되었다면 어떻게 될까. receiver는 자신에게 어떤 패킷도 오지 않았으므로 그저 침묵이 흐를 것이다. 이러한 경우에 대비하기 위해 timer를 사용한다. timer를 통해서 일정시간동안 feedback이 오지 않을 경우 패킷이 유실되었다고 판단하여 재전송을 한다.

- timer의 시간설정 문제

그렇다면 timer의 시간은 얼마로 설정해야 할까? 결론만 말하자면 정답은 없다. ‘적당히’ 설정해야 한다. 짧으면 무조건 좋을까? 만약 짧다면 네트워크 상황으로 인해 패킷이 약간 지연될 경우 오는 도중에 timer가 터져서 재전송이 진행될 수 있다. 정말로 패킷유실이었다면 빠른 대처가 되는 것이지만 그렇지 않을 경우에는 중복된 패킷으로 인해 네트워크 상황만 더 혼잡하게 만드는 가능성이 있다. 너무 길면 통신 자체가 원할하지 않을 수 있겠다.

Transport layer에서 UDP든 TCP든 상관없이 제공하는 기능 2가지가 있다. 바로 Mutilplexing / Demultiplexing과 error check이다.

1. Mutilplexing / Demultiplexing

Mutilplexing은 application단에서 여러개의 소켓을 통해 내려온 message들을 network단으로 내려주는 것을 말하며 Demultiplexing은 network단에서 올라온 packet을 적절한 socket으로 올려주는 것을 말한다.

UDP의 경우 dest ip/port # 만을 확인하여 올려보내고 TCP의 경우 dest ip/port #, src ip/port # 4개를 모두 확인한다. 이는 TCP가 connection-oriented 한 특성을 갖기때문이다. 반면 UDP는 연결의 개념이 아니기에 src를 확인하지 않는다.

2. error check

UDP/TCP Segment header의 checksum이라는 테크를 이용해서 데이터의 에러발생 유무를 확인한다. UDP의 경우에는 에러가 발생한 segment라면 버리게 되고 TCP의 경우에는 reliable한 통신을 제공하기 때문에 sender쪽의 재전송을 통해 다시금 데이터를 받게 된다.