Congestion

📌 Congestion 이란?
혼잡이라는 뜻을 가지며, 네트워크 상에서 패킷들이 너무 많아 혼잡이 발생한 경우를 말한다.
여기서는 Data traffic에 포커스를 두고 지켜봐야 한다.

예를 들어, Router 내부의 CPU에서 패킷을 처리하는 속도보다 Router의 incoming buffer로 패킷이 들어오는 속도가 더 빠르다면 incoming buffer에 패킷이 쌓이게 될 것이다. 이를 Congestion이라고 한다. 뒤에서 자세히 다룰 예정이다.

이런 Congestion을 Control하기 위해서는 두 가지 방법이 존재한다. 첫 번째 방법은 Traffic Congestion이 일어날 상황을 피하는 것이고, 두 번째 방법은 Congestion이 일어났을 때 이를 제거하는 방법이다.

QoS

먼저 Traffic의 종류에 대해 알아봐야 한다.

Traffic은 파일과 같은 일반 데이터 트래픽과 비디오 같은 실시간성 트래픽이 존재한다. 실시간성 트래픽들은 Delay와 Jitter가 발생하지 않도록 해야 한다. 특히, 패킷간의 간격이 일정하지 못해서 발생하는 Jitter의 경우는 너무 패킷이 안 들어오면 끊김이 발생할 수 있기 때문에 이를 해결하기 위해 Client는 버퍼링을 줘서 패킷을 받아도 조금 기다렸다가 재생하는 등의 방법을 사용한다.

반면, 일반 데이터 트래픽은 도착하는 시간은 조금 늦어도 괜찮지만, 데이터의 손실이 일어나서는 안된다. 예를 들어, 비디오의 경우에는 화면이 조금 깨져도 괜찮지만, 1억원을 송금하는 일반 데이터 트래픽에서 0이 하나 빠지면 안되기 때문이다.
이는 곧 일반 데이터 트래픽은 시간에 크게 구애받지는 않지만 Loss가 발생해서는 안된다는 의미이다. 반면, 비디오의 경우에는 약간의 손실이 있더라도 빠른 전송 속도를 보장받는 것이 더 중요하다. 이렇게 데이터 트래픽들은 서로 다른 특성들을 가지고 있기 때문에 각기 원하는 서비스의 퀄리티가 다르다. 이렇게 트래픽을 생성하는 application 단의 동작에 맞게 네트워크 디바이스가 해당 서비스의 퀄리티를 만족시키기 위해 하는 동작을 QoS라고 한다.

뒤에서 더 다뤄보기로 하고 우선 넘어가보자.

Traffic 종류

Traffic 종류를 다시 보면 다음과 같다.

Constant bit rate를 가지는 트래픽은 초당 전송되는 비트율이 항상 일정하다. 예를 들어, 사람의 목소리를 PCM으로 인코딩하면 말을 하거나 안하거나 상관없이 1/8000초 당 8비트가 전송된다.

Variable bit rate를 가지는 트래픽은 영화 같이 때에 따라 발생하는 트래픽 양이 달라지는 것이다. 예를 들어, 영화에서 배경이 많이 바뀌는 장면에서는 트래픽이 많이 발생되지만, 배경이 동일한 정적인 장면에서는 배경에 대한 데이터가 새로 잘 들어오지 않기 때문에 트래픽이 적어진다.

마지막, Bursty 한 트래픽은 어떻게 보면 극단적인 Variable bit rate라고 볼 수 있다. 예를 들면, 웹 브라우저에서 한번 클릭으로 발생하는 트래픽들은 한번에 많이 생겼다가 상호작용하지 않는다면 트래픽이 발생하지 않는 것처럼 말이다.

이 트래픽들은 각 CBR, VBR, Bursty data Traffic이라고 하는데, CBR이 가장 처리하기 수월하고, Bursty data가 가장 처리하기 어렵다.

그렇다면 이런 상황에서 Congestion은 무슨 상황을 말하는거고 어떻게 일어날까?

예를 들어, 어떤 라우터는 평균 300Mbps의 속도로 패킷을 처리한다고 해보자. 이런 라우터에 Constant bit rate traffic이 발생하여 일정하게 200Mbps의 속도로 패킷을 라우터로 보낸다면, 문제가 발생하지 않는다.

그러나, Constant bit rate traffic이 아니라 Bursty data traffic이라고 해보자. 이런 트래픽이라면, 처음 1초 동안은 1Gbps의 속도로 패킷을 보내다가 다음 1~4초동안은 패킷을 보내지 않을 수 있다.(0Mbps의 속도)

이렇게 되면, 평균적으로는 250Mbps의 속도로 패킷을 보낸 것이지만, 처음 1초 동안은 해당 라우터가 감당할 수 있는 크기, 즉 해당 네트워크가 감당할 수 있는 크기보다 더 많은 입력이 들어오게 된 것이다. 이렇게 되면, incoming buffer에 들어오는 패킷의 속도가 나가는 패킷의 속도보다 빠르기 때문에 buffer에 쌓이다가 사라지는 Overflow가 발생하게 되고 이 현상을 Congestion이라고 한다.

🔥 Congestion 🔥
Network에서 처리할 수 있는 용량보다 더 많은 트래픽이 들어온 경우, Buffer에서 Overflow가 발생하는 현상

반대로, incoming buffer가 아닌 outgoing buffer에서도 Congestion이 발생할 수 있다. CPU에서 outgoing buffer로 패킷을 넣는 속도보다 outgoing buffer에서 인터페이스로 빠져나가는 패킷의 속도가 더 느리다면 outgoing buffer에 패킷이 쌓여 Congestion이 발생할 수 있다.

즉, Congestion은 버퍼 등에서 Waiting이 발생한다면 일어날 가능성이 높아진다.

Congestion Control (Open-loop VS Closed-loop)

앞선 설명에서 Congestion을 Control하기 위한 방법으로는 Congestion이 일어나지 못하게 막는 방법과, 발생했을 때 이 Congestion을 버리는 방법이 있다고 했다. 여기서 막는 방법이 Open-loop Congestion Control 혹은 Preventive라고 하고, 버리는 방법을 Closed-loop Congestion Control, Reactive 또는 Removal이라고 한다.

여기서 몇 가지만 살펴보자.

Backpressure method

3번 자리에서 Buffer Overflow가 일어났다면, Congestion이 발생한 것이다.

이 Congestion이 발생한 이유는 input이 너무 빨리 들어왔기 때문이므로, Congestion이 발생한 라우터는 congestion이 일어난 인터페이스로 패킷을 전송한 바로 전 단계의 라우터에게 트래픽을 그만보내라고 전달한다.

이 Backpressure 메시지를 받은 라우터는 Congestion이 어딘가에서 발생했다는 것을 알아채고 다시 자신의 Source에게 이 메시지를 보낸다. 이 과정을 반복하여 최종적으로는 Source host에게 이 메시지가 전달되는 방식이다. 마치 Datalink layer의 Flow Control에서 봤던 busy 수신 이벤트와 유사하다.

그러나, 이 방법은 실제로 IP에서는 사용할 수 없다. IP는 Connectionless 한 서비스만을 지원하기 때문에 이런 메커니즘이 존재하지 않는다. 그래서 IP에서는 다음과 같은 방법을 쓴다.

Choke packet

Congestion이 일어난 라우터가 패킷을 버리고, 패킷을 보낸 Source에게 바로 너 때문에 Loss가 발생했으니 그만 보내라! 라는 메시지를 전달하는 방식이다.

이 메시지가 바로 ICMP Message의 Source quench이다. 이 Source quench 메시지를 받은 Source는 보내는 트래픽의 양을 줄여 Congestion이 발생하지 않도록 한다.
이때, IPv6에서 사용하는 ICMPv6에서는 Source quench가 없다. 그래서 이 IPv6에서는 Transport layer에서 Destination이 Source에게 Congestion이 났다는 것을 알려주는 방향으로 이를 해결한다.

Loss와 Congestion의 차이
Congestion은 네트워크 트래픽이 과도하게 증가하여 네트워크 자원이 포화되는 현상이다. 이 Congestion의 결과로 Buffer에서 Overflow가 일어나 Loss가 발생할 수 있다.
다른 표현으로는 Loss는 단순히 인접 장치 간에 발생하는 것이고, Congestion은 한 곳에서 일어나면 이로 인해 다른 곳들에도 다 퍼지게 되는 것이 Congestion이다. Loss가 일어난다고 인접한 네트워크에 Loss가 일어나진 않지만(단순 전파 방해 등의 이유면 여기만 없어진건데), Congestion이 일어나면 인접한 네트워크에도 Congestion이 일어날 수 있다(네트워크의 용량을 넘어선 트래픽이므로 전체적으로 영향이 감).

QoS

다음은 데이터 트래픽의 특성들을 나열한 것이다.

• Reliability : 보내는 데이터가 온전히 모두 전송되어야 함.
  - 일반적인 데이터 트래픽이 이런 특성을 가지고 있다.
• Delay : Sender가 보낸 것을 Receiver가 가능한 너무 늦지 않은 시간에 수신해야 한다.
• Jitter : 패킷과 패킷 간의 간격이 너무 일정하지 않으면 안된다.
• Bandwidth : 초당 전송되는 데이터의 양이 어느 정도 이상을 보장했으면 한다.

이런 특징들을 기반으로 QoS를 향상시키기 위해서는 다음과 같은 것들을 사용해야 한다.

Scheduling

일반적인 경우이다. 우리가 라우터에서 생각했던 Buffer가 Queue의 역할을 하여 FIFO하게 패킷이 처리된다. 하지만, 이런 방식은 트래픽을 구분하지 못하기 때문에 트래픽의 우선순위를 고려하지 못한다. 예를 들어, 비디오 트래픽과 데이터 트래픽이 들어왔을 때 데이터 트래픽이 먼저 많이 들어와있다면, 비디오 트래픽은 Delay와 Jitter에 예민하기 때문에 패킷이 빨리 전송되어야 하는데, 데이터 트래픽들로 인해 전송되는 시간이 늦어지게 된다.

그래서 다음과 같이 사용한다.

Buffer를 2개 두어 해결한다. 한쪽은 높은 우선순위들이 들어오는 queue로 설정하고, 다른 쪽은 낮은 우선순위들이 들어오는 queue로 설정하여 높은 우선순위의 queue에 있는 트래픽이 먼저 전송될 수 있도록 만드는 것을 Priority queueing이라고 한다.

그러나, 이 방식도 문제가 존재한다. High priority queue가 계속 채워져있다면 Low priority queue에 들어간 트래픽이 나갈 수가 없거나 너무 늦게 빠져나가게 될 수 있다는 것이다.

이런 단점을 개선한 방식이 Round Robin 방식으로 Scheduling하는 것이다. 높은 우선순위의 queue에서부터 하나씩 패킷을 보내는 방식이다. 이렇게 하면 낮은 우선순위의 queue에서 패킷이 빠져나가지 못하는 문제는 해결된다.

여기서 RR을 조금 변형해서 우선순위에 따라 가중치를 두어 패킷을 처리하면 Weighted Fair Queueing이라고 한다.

여기서는 우선순위가 높을 수록 가중치를 높게 설정하여 가중치만큼 패킷을 처리하는 방식의 그림이다.

그렇다면 여기서 들어온 패킷의 우선순위는 어떻게 판단하는걸까?

정답은 Header의 Service Type을 보고 확인할 수 있다. 정확하게는 Service Type의 Diffserv를 보고 결정한다. 이 필드는 6bit로 구성되어 있기 때문에 총 2^6개 만큼의 트래픽 타입을 명시할 수 있다. 즉, 2^6개만큼의 우선순위 queue(incoming buffer)를 배치할 수 있다.

_추가로 Service Type의 ECN은 네트워크 혼잡 상황을 알려주는 데 사용된다. 만약 네트워크에 혼잡이 발생하면, 라우터가 패킷의 ECN 비트를 설정한다. 이 패킷을 받은 수신자는 송신자에게 혼잡 상황을 알려준다. 그러면 송신자는 전송 속도를 줄여서 네트워크 혼잡을 해소하려고 시도한다.

Traffic Shaping

Traffic Shaping도 역시 Congestion이 발생하지 않도록 해준다.
앞서 Congestion은 트래픽이 Bursty하게 들어올 때 발생할 수 있다고 했다. 이 Traffic shaping은 Bursty하게 들어온 트래픽을 Constant하게 바꿔줄 수 있다. 예를 들어, 어떤 네트워크가 300Mbps의 성능을 가지는데, 여기에 1Gbps의 트래픽을 넣으면 Congestion이 발생한다. 그래서 이를 4초동안 250Mbps로 보내도록 만들어 보내는 것이다. 즉, Source가 네트워크에 전송하는 트래픽의 양을 조절하는 방법을 Traffic Shaping이라고 한다.

예를 들면, 휴대폰 요금제에서 지정된 용량을 다 쓰면 속도가 느려지는 무제한 데이터를 사용하는 경우가 바로 이 경우이다.

그래서 이 Traffic Shaping이라는 네트워크에서 네트워크로 전송되는 트래픽 양을 제어하기 위해 사용하는 방법은 Leaky Bucket이랑 Token Bucket이라는 방법으로 나뉜다.

Leaky Bucket

이렇게 Leaky Bucket은 일정하지 않은 flow의 트래픽이 들어와도 일정한 시간과 양으로 패킷을 보내는 방법이다. 즉, Bursty한 트래픽이 Serial해질 수 있다.
이 방법을 프로그래밍 한다고 하면 다음과 같이 구현할 수 있겠다.

//Leaky Bucket
if (packet arrive){
	if (buffer is full) 
    	discard(packet);
    else 
    	stored(packet);
    
    run(timer)
    
    while(buffer is not empty){
    	if (timeout){
    		if (buffer is not empty) 
        		send(packet);
            	rerun(timer);		//다시 타이머를 구동시키고 다시 timeout 되면 시행 
        	else
        		reset(timer);
    	}
    }
}

Token Bucket

Token Bucket 방식은 토큰이 있어야만 Buffer에서 패킷을 보낼 수 있다. 패킷이 들어오면 Buffer에 패킷을 저장하고, 토큰이 있으면 패킷을 하나 보내면서 토큰을 없앤다. 이 토큰은 일정 시간마다 생성된다.
예를 들어, 토큰이 3개 있는 상태에서 패킷들이 들어온다면, 한번에 패킷 3개를 보낼 수 있지만, 토큰을 모두 사용한 시점에서는 토큰이 들어오기를 기다렸다가 들어오자마자 바로 하나씩 보내는 방식을 사용한다. 그래서 처음에는 와르르 보내다가 그 뒤로는 일정한 양과 속도로 보내는 방식이 Token Bucket 방식이다. 이때, Bucket에 들어올 수 있는 토큰의 수는 정해져있다.

이 Token Bucket 방식을 코드로 구현하면 다음과 같다.

//Token Bucket으로 패킷 처리 
if(packet arrive){
	if (buffer is full) 
    	discard(packet);
    else
    	stored(packet);
    
    while(token && (buffer is not empty)){
    	send(packet);
        token--;
    }
}
===================================================
//Timer로 토큰 생성
void generateToken(){
if (token.size() < bucketSize){
	token++;
}

while (buffer is not empty && token.size() > 0){
	send(packet);
    token--;
}

run(timer.generateToken());
}

가볍게 이해를 돕기 위한 코드로 봐주면 좋을 것 같다. 대부분의 동작 방식들은 Token Bucket을 따른다.

Traffic Shapping Example

다음과 같은 상황을 통해 이해해보자.

• 컴퓨터는 25Mbytes/sec의 데이터를 제공(200Mbps)한다.
• 라우터는 짧은 인터벌동안 오직 25Mbytes/sec를 다룬다.(200Mbps)
• 오랜 인터벌 동안은 최고의 rate를 제공하는 속도는 2Mbytes/sec를 넘지 않도록 일한다.(16Mbps)
• Bucket으로 들어오는 패킷의 속도는 25MB/sec의 속도로 40msec 동안 들어온다.

여기서는 sec와 msec가 혼용되어 사용되므로, msec 단위로 생각하면 이해가 쉽다.

초기에 들어오는 트래픽은 다음과 같다. Bursty하게 들어오지만, Traffic Shaping을 사용해보자.

그림으로 보면 다음과 같은 차이가 있다. Leaky Bucket은 속도가 일정한 반면, Token Bucket은 처음에는 최고 속도로 빠져나가다가 뒤로는 감소된 속도로 일정하게 간다. 자세하게 계산해보자.

Leaky Bucket 방식은 어차피 빠져나가는 속도가 일정해야 한다. 이 속도가 예시에서 규정한 2MBps라고 한다면, 1msec 당 빠져나가는 패킷의 양은 2KByte가 된다. 총 들어오는 데이터의 양은 1msec 당 25KByte의 양이 40msec 동안 들어오므로 1MByte이다. 이 1MByte를 2KByte/msec의 속도로 전송하면 총 500msec의 시간이 소요된다.

Token Bucket 방식은 좀 까다로울 수 있다. 역시 이 경우에도 마찬가지로 25KByte/msec의 속도로 Buffer로 패킷이 들어온다. 이때, 토큰을 담고 있는 Bucket의 크기가 250KB이고, 토큰이 들어오는 속도가 2MBps, 즉 2KByte/msec의 속도로 토큰이 들어온다.
이때, 버켓은 새로 들어오는 토큰을 바로 사용한다고 하면 기존 버켓에서 꺼내서 사용해야 할 토큰의 양은 1msec 당 25KByte - 2KByte = 23KByte가 된다. 버켓의 총 용량은 250KB이기 때문에, 250KB/23KB = 11s라는 시간 동안에는 버켓에 토큰이 존재하기 때문에 가장 빠른 속도인 25MBps, 즉 25KByte/msec로 패킷을 보낼 수 있다. 11초 이후부터는 버켓에 사용할 수 있는 토큰이 없기 때문에 토큰이 다시 들어오기를 기다렸다가 들어오자마자 바로 토큰을 사용해야 한다. 그래서 2MB/sec의 속도로 토큰이 충전되기 때문에 11초 이후의 패킷 전송 속도는 2MB/sec로 고정되는 것이다.

Resource Reservation

Resoure Reservation은 Source가 데이터를 보낼 때, 이 데이터는 Bandwidth가 이정도이니까 모든 라우터들에게 이 정도의 Bandwidth를 보장해줘야 한다는 것이다. 비단, Bandwidth 뿐만 아니라 Resource, Velocity, Bandwidth 등을 포함한다.
예를 들어, 회사들이 ISP에게 얼마만큼의 돈을 줄테니 전체 라인 중에서 10MBps의 속도를 나에게 보장해달라! 라고 요구하는 것이 Resource Reservation이 될 수 있겠다.

Admission control

이렇게 회사들이 ISP에게 Resource Reservation을 요청했다고 해보자. 예를 들어 전체 1GBps의 속도를 가지는 자원을 회사 5개가 300MBps씩 Resource Reservation을 요청했다면, 먼저 예약한 3개의 회사들에게는 가능하지만 이후 회사들에게 자원 예약을 약속한다면 전체 성능이 떨어지게 되어 보장하겠다고 한 성능을 지키지 못하게 된다.
이렇게 Resource Reservation을 요청했을 때 이를 받을 수 있는 지 없는 지를 결정하는 것이 Admission Control이다.

여기서 Resource Reservation과 Admission Control은 개념만 알아도 충분하다.