Token Bucket
Token Bucket방식
Buket 자체를 FIFO 큐로 사용하지 않고, 트래픽을 제어하기 위한 제어용 토큰을 관리하는 용도로 사용한다. 트래픽은 토큰의 유무에 따라 흐름의 제어를 받게 된다. 또한 항상 정해진 일정량만 통과하도록 되어 있는 Simple Leaky Bucket과는 달리 트래픽이 버스트 한 경우에도 정해진 한계치 범위 내에서는 통과가 가능하다.
Leaky Bucket방식
일정하지 않는 트래픽을 일정하게 유지시커 전송시키기 이한 방식으로 ATM네트워크에서 셀 트래픽의 속도를 조절하기 위해 제안되었으나 패킷 네트워크의 제 3계층에서도 사용된다. Bucket의 깊이와 전송율은 일반적으로 사용자가 조절이 가능하며, 바이트 단위로 표시된다.
이 방식은 네트워크 내의 한 종류의 트래픽 양을 조절하는 임의의 임계치로 사용할 수 있는 방식인 반면, 여러 종류의 트래픽 속도를 지원해야 하는 경우에는 비 효과적이다. Peak rate가 고정된 값을 가지므로 네트워크 자원의 여유가 많을 때에도 충분히 활용할 수 있는 적응성을 가지지 못하는 단점을 가지고 있다.
Dual Leaky Bucket방식
먼저 Token Bucket으로 트래픽 양의 버스트를 허용하면서 조절한 후, Simple Leaky Bucket을 이용헤서 특정 한계치의 값만큼 일정하게 트래픽을 전송하는 방식이다.
>> 상세
Token bucket은 Traffic Policing과 Traffic shaping에서 사용되고 있는 기본 알고리즘입니다.
Committed Access Rate(CAR), Class-based Policing, Generic Traffic Shaping(GTS), Frame Relay Traffic Shaping(FRTS)등에서 사용이 되고 있습니다.
기본적으로는 single rate token bucket을 사용해 왔지만, IOS 12.2(4)T버전부터는 Traffic Policing에 대하여 dual rate token bucket도 도입이 되었습니다.
token bucket을 결정짓는 중요한 변수들은 다음과 같습니다. 우선 먼저 FRTS에서 사용되는 변수부터 살펴보겠습니다.
CIR = Mean rate or Committed Information Rate(CIR), in bits per second
Bc = Conformed Burst Size(Bc), in bits
Be = Excess Burst Size(Be), in bits
Tc = Measuring Time Interval(Tc)
이 네가지 변수를 일단 잘 이해하는 것이 중요합니다.
이렇게 생각하죠.
bucket(양동이, 빠께스)에다 수도꼭지를 틀고 물을 받는다고 생각을 하겠습니다.
잠시후면 그 bucket에 물이 꽉차 흘러넘치기 시작하겠죠. 이때 수도꼭지를 끝까지 돌려서 최고의 속도로 물을 받을 수도 있고, 조금만 틀어 비교적 천천이 물을 받을 수도 있을 겁니다. 이렇게 물이 공급되는 속도(CIR)는 bucket의 크기(Bc)와 bucket에 물이 끝까지 다차는데까지 걸린 시간(Tc)으로 표현할 수 있습니다. bucket에 물을 가득채웠을 때의 물의 양이 15리터고, 그때까지 걸린 시간이 30초라면, 물이 공급되는 속도는;
15리터 / 30초 = 0.5리터 / 1초 = 0.5lps (liter per second)
15리터 / 30초 = 20리터 / 1분 = 20lpm(liter per minute)
15리터 / 30초 = 120리터 / 1시간 = 120lph(liter per hour)
위의 계산에서는 세가지로 표현을 하였는데, 기준이 되는 시간이 무엇이냐에 따라서 여러가지로 표현할 수 있다는 것을 알아두시기 바랍니다.
만약, bucket에 담긴 물을 30초에 한번씩 여러사람들이 퍼마신다고 생각을 하죠. 그렇다면 한번에 먹을 수 있는 최대용량은 15리터가 됩니다. 이번에 물을 다마시지 않고 10리터만 마시고 5리터는 남겨두었다고 하더라도 30초후에는 15리터만 남아있게 됩니다. 물을 담는 bucket의 한계가 15리터이기때문에 나머지는 흘러넘쳐 버려지겠죠.... 이렇게 버려지는 물이 아깝습니다..... 해결방법은? 예 당연히 bucket의 크기를 늘리는 겁니다. 30초마다 공급되는 물의 양인 15리터보다 5리터(Be)더 큰 20리터짜리 bucket을 둔다면 더 많이 담아둘수 있겠죠. 그렇다고 하더라도 30초마다 공급되는 물의 양은 변함이 없이 15리터입니다. 단지 어떤 interval에 마실수 있는 물의 양이 최고 20리터까지 늘어난거죠... 그렇다고 매번 30초마다 20리터씩 먹을 수 있는 것은 아닙니다. 그 전 30초전에 먹을때 남겨둔 양이 있어야 한다는 거죠. 장기적인 관점인 1시간을 놓고 볼때 최대로 마실수 있는 물의 양은 120리터인 것임에는 변함이 없습니다.
위의 예를 network에 적용해 보겠습니다. 우리가 Traffic Shaping이란 용어를 처음 접하는 곳은 역시 Frame Relay가 아닐까 생각합니다. 이때부터 실은 머리 아프기 시작하죠.
어느상황에서 traffic shaping이 필요한 걸까요? 다음은 IOS 12.2 documents에 나오는 내용입니다.
Policing and Shaping Overview - Why Use Traffic Shaping?
- Control access to bandwidth when, for example, policy dictates that the rate of a given interface should not on the average exceed a certain rate even though the access rate exceeds the speed.
- Configure traffic shaping on an interface if you have a network with differing access rates. Suppose that one end of the link in a Frame Relay network runs at 256 kbps and the other end of the link runs at 128 kbps. Sending packets at 256 kbps could cause failure of the applications using the link.
- If you offer a subrate service. In this case, traffic shaping enables you to use the router to partition your T1 or T3 links into smaller channels.
Frame Relay서비스를 Service Provider(SP)로부터 살때 256kbps의 CIR을 샀다면, 초당 256kbps까지는 전송을 보장받았다는 것을 의미합니다. 만약 이때 port speed 역시 256kbps라면 Traffic Shaping은 의미가 없습니다. 굳이 customer측에서 throttling해 줄 필요가 없는 거죠. 어차피 물리적으로 256kps이상은 전송할 수 없으니까요. 하지만, 만약 port speed가 T1이라면 이때는 traffic shaping이 필요합니다. 이걸 해주지 않게 되면 Service Provider측에서 256kbps가 넘은 traffic은 drop시키거나, DE bit를 marking하는 등의 policing을 할텐데, 이렇게 drop되는 traffic이 voice거나 TCP와 같은 adaptive flow control하는 경우라면 문제가 되겠죠. 그래서 SP측에서 policing을 하기 전에 미리 허용된 범위에 맞게 조절(throttling)해서 보낸다면 SP측에서 drop시킬 염려는 없는 거겠죠. 왜냐면 256kbps는 guaranteed된 traffic이기 때문이죠.
256kbps의 CIR을 샀는데, port speed인 T1분량의 data(frame header포함1536kbits: 8k는 signal)를 traffic shaping없이 한꺼번에 T1속도로 전송 했다면 어떻게 될까요, 상대편에서 첫번째 bit와 마지막 bit를 받을때까지 1초가 걸립니다. 우리가 CIR을 통해서 유추할 수 있는 것은 1초에 256kbits만 받아들인다는 것입니다. 하지만 이것만 가지고는 상대편에서 이 data를 처리할 방법은 여러가지가 있습니다. 예를 몇가지 들어보겠습니다.
1. 전송한 순서대로 먼저 전송한 256kbits(1~256000)까지만 받아들이고 나머지는 모두 drop시킨다
2. 1초를 8로 나누어, 125ms(1/8초)동안은 처음 32kbits(1~32000)만 받아들이고, 나머지는 drop시킨다. 이렇게 8번 반복한다.
3. 극단적인 방법으로 3.9us(1/256000초)마다 1bit만 받아들인다. 이 경우는 심지어 바이트 단위로 전송도 어려운 거겠죠.
뭐, 어떤식으로 하던지 1초에 256kbits만 받아들이는데는 이상이 없어 보입니다. 위 3가지 방법은 모두 초단위로 환산을 했을 경우에 256kbps가 나오는 겁니다. 하지만 위의 3가지의 경우에 drop되는 bit는 전혀 다릅니다. 그래서 Frame Relay를 계약할때는 다른 변수를 보아야 합니다. CIR 256kbps만 가지고는 부족한 것이죠.
즉 측정시간(Tc)과 그 측정시간동안 허용된 양(Bc)을 나타내 주는 수치가 실제로 중요한 것이고, CIR은 이 두가지 값에 의해 자동으로 유추된 것입니다.
위의 3가지 방법은 모두 CIR 256kbps지만,
1. Bc = 256kbits, Tc = 1초 (CIR = 256kbits/1초 = 256kbps)
2. Bc = 32kbits, Tc = 125ms (CIR = 32kbits/125ms = 256kbps) - 일반적인 유형
3. Bc = 1bit, Tc = 3.9us (CIR = 1bit/3.9us = 256kbps)
다시말해서, 측정시간은 1초일 필요가 없다는 겁니다. 실제로 SP와 계약한 서비스는 일정시간(Tc)동안 얼마(Bc)까지 허용된다는 것입니다. 이걸 초단위로 환산을 하니까 CIR이 나온겁니다.
그런데, 우리의 이해에 혼란을 부채질하는 것은 측정시간을 흔히 초단위로 생각하는데에 있는 것 같습니다. 이것은 우리의 일상생활에서 "초"라는 시간이 가장 작은 시간단위쯤으로 여겨지고 있기 때문이죠. 하지만, network에서의 second란 위의 수도물의 예에서의 시간단위쯤으로 생각하시면 될 것 같습니다. 즉 아주 아주 더 세부적으로 나뉘어 질 수 있는 단위로 생각하셔야 합니다.
실제로 SP와 계약한 서비스가 2번과 같다면, 무조건 port speed대로 data를 전송할 것이 아니라, 계약한 허용치에 맞게 보내서 drop되지 않게 하는 것이 중요할 것입니다. 이걸 위해서 사용되는 것이 token bucket입니다.
위에서 수도꼭지에서 나오는 물을 token이라고 생각하시면 됩니다. 위의 예에서 수도꼭지에서 물이 끊임없이 쏟아지는 것처럼, token이 일정한 속도(CIR)로 끊임없이 공급됩니다. Tc의 시간이 되면 token이 bucket에 Bc만큼 채워질 겁니다. 이때 채워진 token수만큼 data를 전송한다면 SP쪽에서 걸어놓은 traffic policing에 걸리지 않고 data를 온전히 전송할 수 있을 겁니다. 만약 이때 SP측에서 허용한 Excess burst가 있다면 그것은 위의 예에서 설명한 것처럼, bucket의 크기를 늘려서 그 이전 Tc타임시에 다 쓰지 않고 남은 Token이 있다면 이게 축적(credit building)되어서 최대 한번의 Tc시간동안 Bc + Be까지도 전송할 수 있다는 것을 의미합니다.
이제 구체적인 예를 들어 설명하겠습니다.
CIR = 64000
Bc = 9600
Be = 9600
Tc = 150ms
여기서, 먼저 bucket의 크기는 Bc + Be = 9600 + 9600 = 19200입니다.
그리고 bucket이 텅빈 상태에서 150ms(Tc)가 지나면 bucket에 token이 9600(Bc)까지 채워질 겁니다. 이때를 Tc(0)라고 하고, 다음과 같이 전송할 data가 있다고 가정하겠습니다. 토큰 한개를 1bit로 생각하면 됩니다.
1. Tc(0); queue에 대기하고 있는 전송할 data(0) = 6000, bucket(0) = 9600
- bucket에서 6000을 꺼내 data를 전송합니다. 이제 bucket에는 token이 3600이 남아 있습니다.
2. Tc(1); data(1) = 6000, bucket(1) = 13200
- Tc인 150ms동안 새로이 추가된 token과 전에 쓰고 남은 토큰을 합해서 13200의 token이 있습니다. 역시 bucket에서 6000을 꺼내 data를 전송합니다. 이제 bucket에는 7200이 남아있습니다.
3. Tc(2); data(2) = 0, bucket(2) = 16800
- 새로이 추가된 token을 더해 16800이 있습니다.
4. Tc(3); data(3) = 19200, bucket(3) = 19200
- 새로이 추가된 token을 더해 16800 + 9600 = 26400이지만, 7200의 token은 흘러넘쳐 버려졌습니다. 보낼 data만큼의 token이 있으므로 19200모두 전송이 됩니다. 이때 이렇게 전송된 data중 SP쪽에서 허용된 Bc인 9600이상의 data외의 나머지 Be 9600은 DE bit를 세팅하여 Frame Relay Cloud로 전송하여 cloud내에서 congestion발생시 우선적으로 drop시킵니다. 이제 bucket에는 남아있는 token이 없습니다.
5. Tc(4); data(4) = 12800, bucket(4) = 9600
- 새로이 추가된 token을 더해 9600되었지만, 이 경우에는 token이 모자릅니다, 이때는 packet scheduler에 의해 결정된 순서에 따라 앞부분 9600만 전송을 하고, 나머지data 3200은 다음 tc에 보냅니다.
6. Tc(5); data(5) = 800 + 3200(data(4)에서 남은 것), bucket(5) = 9600
- 새로이 추가된 token을 더해 9600이 되었고, Tc(4)에서 전송하지 못한 3200까지 더해 모두 4000을 전송하면 남은 token은 5600이 됩니다.
음, 위의 설명을 자세히 들여다 보면 생기는 의문이 있을 겁니다. Tc마다 한번씩 한꺼번에 전송합니다. 이게 상당히 불합리해 보입니다. 그러지 않고 그냥 token이 확보되는대로 전송하는 것이 더 효율적이지 않을까 하는 생각을 해 보았는데, 그러면 문제가 생기더군요. 예를 들어 bucket에 가득 token이 채워진 상태에서 갑자기 3*Bc(28800)만큼 data가 들어왔다면 어떻게 될까 생각해 보시길 바랍니다. 그러면 일단 19200은 전송을 하고 나서 Token이 확보되는대로 나머지 9600을 150ms동안 전송을 할 겁니다. 이렇게 되면 한번의 Tc시간동안 총 3*Bc만큼 전송이 되어서 뒤에 보낸 9600은 Excess Burst를 고려하더라도 drop될수 밖에 없게 됩니다.
이런 stop-and-go 전송이 대부분의 경우에는 큰 문제가 없지만, 이것이 voice의 경우에는 문제가 됩니다. Tc가 serialization delay가 되기 때문이죠. 그래서 voice를 사용하는 경우에는 Tc를 10ms로 할 것을 권장합니다.
