WFQ 동작 과정 (패킷 처리 예제)

패킷 교환망(Packet Switched Network)은 기본적으로 guranteed service가 아닌 best-effort service를 제공한다.
호스트 하나하나마다 전용선이 있는 것이 아닌 망을 여러 호스트가 공유해서 쓰기 때문이다.

* Guranteed Service : 정해진 대역폭, 지연등의 서비스 품질을 보장하는 서비스
* Best-Effort Service : 최선을 다한다는 말은 성능 보장은 안 한다는 말이다.

이러한 패킷 교환망에서도 기존구조는 그대로 두면서 차별화된 서비스를 해줄 필요가 있게 되었다.

* QoS(Quality of Service) : '서비스의 질'인데, QoS는 'Level of Performance'(성능의 등급)을 두어서 등급에 따라 차별화된 서비스를 제공하는 것 이라고 볼 수 있다. 우리가 집에서 사용하는 인터넷도 '라이트', '프리미엄'서비스에 따라 제공되는 링크속도가 다른데, 이렇게 QoS를 통해서 Service Provider는 등급별로 다른 서비스를 제공해주고 요금도 다르게 받는다.


그렇다면 패킷 교환망에서 어떻게 차별화된 서비스를 제공할 수 있을까?

패킷이 저장되었다가 나가는(store and forward) 곳 - 라우터와 같은 장비에서 이런 서비스가 가능하다.

차별화된 서비스는 TCP와 같은 커넥션별로 제어하는 것이 아니라, 보통 호스트별로 제어된다.
집에서 사용하는 PC의 랜선으로 연결된 장비가 있을 것이다. 내가 보낸 패킷 또는 프레임은 그 장비를 거쳐갈때 등급이 붙는다.(marking)
TCP 헤더 안에 안 쓰는 필드같은 것을 활용해서 표시를 한다.


이제 이렇게 등급이 표시된 패킷을 차별하여 처리해야 한다.(말이 좀 그렇다. 차별이라니 흐흐)

이러한 작업은 라우터와 같은 장비의 버퍼 큐(Queue)에서 할 수 있다.
차별화된 서비스가 제공되지 않는다면 버퍼에 패킷이 들어온 순서대로 처리를 해주면 될 것이다.

차별화된 서비스를 위해 몇 가지 방법이 제시되었지만 가장 확실하게 그것을 가능케 한 방법이 WFQ를 사용하는 것이다.


WFQ (Weighted Fair Queue)

억지로 해석하면 '가중된 공평한 큐' 쯤 되겠다.
fair라는게 '공평한'이라는 뜻도 있지만 사전을 보니 '규칙에 따른' 이란 뜻도 있다.
대충 '가중치를 가지고 공평하게 동작하는 큐'라고 하면 되려나.. 가중치를 가진다고 해놓고 공평하다니, 공평하단 뜻은 아닌가 보다. 어쨋든!!

WFQ는 시스코 라우터에는 구현이 되어 있다고 한다. 다른 회사거에도 있겠지. 요센 QoS가 거의 필수니.

WFQ개념

그럼 이제 WFQ가 어떻게 동작하는지 알아보자.

먼저 가정부터 한다.

1. 시스템에는 클락이 하나있다.
2. 단위 시간당 처리할 수 있는 패킷은 하나이다.
3. 각 커넥션(큐/포트)에는 가중치(weight)가 있다.

Flow Connection(포트번호)    weight(가중치)       차지하는 비율
             1                                         2                        2/12 = 1/6
             2                                         4                        4/12 = 1/3
             3                                         6                        6/12 = 1/2

- 전체 가중치 : 2 + 4 + 6 = 12

1번 포트는 전체 대역폭의 2/12를 차지한다고 이해하면 된다.

커넥션에는 각각의 로컬 클락(타이머)이 있다.


       ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ
1번포트                                                    ㅁ              ㅁ          ㅁ              ㅁ    
       ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ
2번포트                        ㅁ                      ㅁ          ㅁ      ㅁ                      ㅁ  ㅁ    
       ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ
3번포트                        ㅁ      ㅁ                  ㅁ  ㅁ              ㅁ          ㅁ  ㅁ          ㅁ
       ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ
 클락  25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10   9   8   7   6   5   4   3   2   1   0


ㅁ는 패킷을 나타내며, ㅁ위치에 시스템클락 시각에 패킷이 도착했다고 보자.

시스템 클락 단위 시간당 각 포트가 차지하는 비율만큼 패킷을 처리한다고 보면된다.
편의상 시스템 클락의 시간단위는 초라고 하겠다.


처리패킷
(port)                  1   2   3       3       1   2   3   2   3       1   2   3       3   2   3   1   2  3
       ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ
1번포트 <                      ><                      ><  ㅁ              ㅁ  ><      ㅁ             >ㅁ    
       ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ
2번포트             <         >ㅁ       <          ><  ㅁ      ><  ㅁ     >ㅁ   <          ><      ㅁ >ㅁ    
       ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ
3번포트                 <     >ㅁ<    >ㅁ       <      ><  ㅁ >ㅁ       <     >ㅁ<     ><  ㅁ >ㅁ   <     >ㅁ
       ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ  ㅣ
 클락  25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10   9   8   7   6   5   4   3   2   1   0


> 는 virtual service start time을 나타내며 < 는 virtual service finish time을 나타낸다.

패킷이 들어온 순간부터 처리가 시작 된다고 하면

3번 포트에서 0초에 도착한 패킷 하나를 처리한다고 하면 3번 포트가 전체 대역폭에서 차지하는 비율은 1/2이다. 매 초당 패킷을 1/2씩 처리한다고 볼 수 있으므로 이 패킷은 2초에 처리가 끝난다. 다시말해 단위시간당 패킷을 1/2만큼 처리했다고 보면 된다.

2번 포트에서 1초에 도착한 패킷은 4초에 처리가 끝날것이다. 단위시간당 1/3패킷을 처리하므로 3초가 지나야 패킷 하나를 처리할 수 있다.
가상으로 이렇게 패킷 하나가 이 정도의 시간뒤에 처리가 끝날 것이라는 말이다.

2번 포트에서 2초에 도착한 두번째 패킷은 첫번째 패킷이 처리되고 난 다음 부터 처리를 시작(4초에시작)해서 7초에 끝난다고 볼 수 있다.

이런식으로 실제 패킷이 도착한 시간과 별개로 virtual service start time, finish time을 패킷마다 표시해둔다.

0초에 처리해야할 패킷은 3번포트의 패킷 뿐이므로 3번포트의 패킷을 처리한다.

1초에 도착한 1번과 2번포트의 패킷중에서 먼저 처리해야할 패킷은 2번포트의 패킷이다. 왜냐하면 2번포트 패킷의 virtual finish time이 더 빠르기 때문이다.

2초에, virtual start time이 시작되었고 아직 처리되지 않은 패킷은 1번 포트의 첫번째 패킷뿐이므로 처리한다.

3초에서는 3초와 3초이전에 실제로 도착한, 아직 처리하지 않은 패킷은 2번포트의 두번재 패킷과 3번포트의 두번재 패킷이다.
이때, 2번포트의 두번째 패킷은 virtually 4초에 처리를 시작하게 되어 있으므로 아직 처리를 해서는 안된다.
따라서 3번포트의 두번째 패킷을 처리한다.

virtual finish time이 같은 패킷이 여러개인 경우 아무거나 처리한다.
패킷 두개의 virtual finish time이 같고, 더이상 처리시간이 없는 경우처럼
둘다 이번에 처리 못하면 virtual finish time이 초과되는 경우는 발생하지 않는다.

WFQ의 핵심은 실제 처리하는 시간이 virtual time을 기준으로 정해 진다는 것이다.
virtual start time은 처리 시작 할 수 있는 시각이고, virtual finish time이 빠를 수록 우선 처리해야 할 패킷이 된다.
현재 시간에 처리할 패킷이 없는데 실제 패킷이 도착한 경우 그 패킷의 virtual start time이 현재시간이 아니라면 이번 시간에는 아무것도 처리하지 않는다.

1번포트의 첫번째 패킷의 실제 처리시각이 2초라고 해서 virtually service start time인 1초가 바뀌진 않는다.
virtual service start/finish time은 실제 처리시작과 상관없이 처음 계산 그대로 사용된다.