핵심 인사이트 (3줄 요약)

  1. 본질: 리키 버킷(Leaky Bucket)과 토큰 버킷(Token Bucket)은 앞서 배운 폴리싱(Policing)과 쉐이핑(Shaping)이 패킷을 썰어버릴지 담아둘지를 결정할 때 사용하는 **"계약 속도 측정용 수학적 양동이 알고리즘"**이다.
  2. 리키 버킷 (구멍 난 양동이): 양동이에 구멍이 뚫려 있어 아무리 물(트래픽)을 한꺼번에 콸콸 부어도, 바닥 구멍으로는 무조건 똑같은 속도(일정한 10Mbps)로만 물이 쫄쫄 새어 나오게 만드는 아주 꽉 막힌(Burst 불허) 쉐이핑 알고리즘이다.
  3. 토큰 버킷 (동전 양동이, 현대 표준): 일정 시간마다 양동이에 통과용 동전(Token)이 100개씩 쌓인다. 패킷이 지나갈 때마다 동전을 하나씩 쓴다. 만약 트래픽이 없어서 동전이 가득 모여있다면, 갑자기 데이터가 쏟아질 때(Burst) 모아둔 동전을 한방에 써서 순간적으로 계약 속도를 초과하는 광속 전송(융통성)을 허용하는 똑똑한 폴리싱/쉐이핑 표준 알고리즘이다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

  • 개념: 네트워크로 유입되는 트래픽의 전송률(Rate)을 측정하고, 돌발적인 폭주(Burst) 트래픽을 평탄화(Smoothing)하거나 제한하기 위해 고안된 두 가지 고전적인 트래픽 계측 알고리즘.

  • 필요성: 라우터에 "10Mbps로 속도 제한해!"라고 명령어를 쳤다. 컴퓨터가 0.1초 동안 20Mbps로 쏘고 나머지 0.9초를 쉬면 평균은 10Mbps 이하다. 이걸 막아야 할까 봐줘야 할까? **"순간적인 폭주(Burst)를 용납하지 않고 칼같이 썰어버릴 것인가, 아니면 평균값만 맞으면 융통성 있게 한 번에 훅 통과시켜 줄 것인가?"**를 결정하는 판단 기준이 필요했다.

  • 💡 비유: 두 버킷은 놀이공원의 **"입장 게이트 통제 방식"**과 같습니다.

    • Leaky Bucket: 회전문입니다. 밖에 1,000명이 몰려와도 무조건 "1초에 1명씩만" 돌아갑니다. 극도의 안정성을 주지만 융통성이 0입니다.
    • Token Bucket: 게이트 직원이 1초마다 '입장권(Token)'을 10장씩 발급해 바구니에 모아둡니다. 손님이 없어서 입장권이 1,000장 쌓였습니다. 이때 단체 관광객 1,000명이 훅 몰려오면? 직원이 모아둔 입장권을 한 번에 다 주고 **1,000명을 0.1초 만에 논스톱으로 통과(Burst 허용)**시켜 줍니다.

📢 섹션 요약 비유: 리키 버킷은 아무리 링거액을 세게 틀어도 핏줄에는 **무조건 한 방울씩 똑똑 떨어지게 만드는 "수액 조절기"**이고, 토큰 버킷은 평소에 돈(토큰)을 저축해 두었다가 세일 기간(폭주)이 오면 모아둔 돈을 **한방에 터뜨려 물건을 쓸어 담는(허용) "스마트 저축 계좌"**입니다.

Ⅱ. 두 알고리즘의 동작 원리와 실무 적용 (Deep Dive)

1. Leaky Bucket (리키 버킷) - 절대 평탄화

ATM(비동기 전송 모드) 네트워크에서 주로 썼던 구형 방식이다.

  • 동작: 물(패킷)을 양동이 위로 들이붓는다. 양동이 밑바닥엔 구멍이 뚫려 있어 일정 속도로만 물이 빠져나간다.
  • 결과: 입력 속도가 아무리 지멋대로 뛰어도, 출력 속도는 무조건 $V$ 라는 상수(Constant Rate)로 100% 일정하게 고정된다.
  • 오버플로우: 너무 많이 부어서 양동이 위로 물이 넘치면? 그 패킷들은 가차 없이 버려진다(Drop).
  • 특징: Burst(순간 폭주)를 단 1%도 허락하지 않는다.

2. Token Bucket (토큰 버킷) - 현대 QoS의 지배자

시스코(Cisco)를 비롯한 모든 현대 라우터의 쉐이핑/폴리싱 명령어(police cir..., shape average...)의 근간이 되는 수학 모델이다.

  • $Tc$ (Time Interval): 보통 1초의 1/1000 단위. 토큰을 채워 넣는 주기.
  • $Bc$ (Committed Burst): 양동이의 크기 (최대 모을 수 있는 동전 개수).
  • $CIR$ (Committed Information Rate): 계약한 속도. 1초에 동전을 몇 개씩 부어줄 것인가.
  • 동작 원리:
    1. 시스템이 일정 시간마다 양동이에 토큰(동전)을 떨어뜨린다.
    2. 패킷 1바이트가 지나가려면 바구니에서 토큰 1개를 빼서 내야(지불해야) 나갈 수 있다.
    3. 바구니에 토큰이 없으면? 패킷은 버려지거나(Policing) 큐에 대기(Shaping)한다.
    4. 마법의 순간(Burst): 밤새 통신을 안 해서 바구니에 토큰이 1억 개 꽉 찼다. 아침에 직원이 출근해서 1억 바이트짜리 파일을 던진다. 바구니에 토큰이 1억 개나 있으므로, 1억 바이트가 단 0.1초 만에 빛의 속도로 톨게이트를 뚫고 나간다. (계약 속도를 초과하는 융통성 발휘!)
 ┌─────────────────────────────────────────────────────────────┐
 │                Token Bucket 폴리싱의 실무 파라미터(Bc, Be)        │
 ├─────────────────────────────────────────────────────────────┤
 │                                                             │
 │   라우터 명령어: police cir 10000 bc 1500 be 2000                │
 │                                                             │
 │   1. CIR (10M): 평소에 초당 채워주는 기본 토큰의 양 (계약 속도).        │
 │   2. Bc (기본 양동이): 토큰을 최대 1,500개까지만 저축할 수 있는 바구니.   │
 │   3. Be (초과 양동이, Excess): Bc 양동이가 꽉 차면, 옆에 있는 비상용     │
 │                           Be 양동이에 추가로 2,000개를 더 저축함!   │
 │                                                             │
 │   ▶ 패킷이 들어올 때:                                           │
 │     Bc 토큰으로 결제 -> 통과 (정상, 초록색)                       │
 │     Bc 없고 Be 토큰으로 결제 -> 통과 (근데 노란색 딱지 붙여서 강등함)  │
 │     Bc, Be 토큰 다 없음 -> 사살! (Drop, 빨간색)                 │
 │                                                             │
 │   ▶ "이것이 통신사 망에서 쓰이는 Two-Rate Three-Color Policer다!"  │
 └─────────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 토큰 버킷은 통신사가 고객에게 제공하는 **"이월 가능한 데이터 요금제"**입니다. 이번 달에 데이터를 안 쓰면 다음 달로 이월(토큰 저축)되어, 다음 달에 갑자기 유튜브를 미친 듯이 봐도(Burst) 안 끊기고 쾌적하게 볼 수 있게 해주는 합리적인 정산 시스템입니다.