Scheduling

• packet processing의 순서를 결정한다

FIFO queue

• First-In First-Out
• pakcet arrived first is processed first
  

특징

• flows are NOT distinguished
  • 우선순위가 따로 없다. 공평하다(?)
• NO congestion control
• 큐가 꽉 차면, 마지막 packet이 drop된다. (tail drop)
• fair in terms of delay
• bandwidth is NOT considered

문제점

• 한 flow가 많이 보내면, 그 flow는 more served
  • 이기적인 행동이 발생할 수 있다. (무작정 많이 집어넣어)
  • router 다운시키려는 attack 목적으로 사용될 수 있다
• packet은 다양한 종류의 QoS(서비스 품질)이 필요할 수 있다.
  QoS네는 우선 순위, 대역폭 할당, 지연 제어, 손실률 제어 등이 있다.
  예를 들어 실시간 통화는 낮은 지연 제어가 필요하다.
  어쨌든 FIFO에서는 이를 구현할 수 없다.

---

Priority Queue

• process packet depending on priority
• packet이 늦게 왔더라도, 높은 priority를 가지면 먼저 process된다.
  

문제점

• low-priority flow can be starved
  • 너무 오랜 시간동안 packet을 보낼 수 없다. (starvation)

---

Round Robin

• each flow마다 queue가 있다.
• takes turns to go around each queue and
  process one packet per each queue
• FIFO와 다르게, 무작정 많이 보낸다고 더 많은 service를 받지 않는다.
• large packet을 보내는 flow가 더 많은 service를 받는다
  

---

Fair queuing

• each flow마다 queue가 있다.
• flow가 fair service를 받도록 packet을 schedule한다
  • packet size가 다르더라도 scheduling이 fair하다
    

Algorithm

• Si = amount of data flow i has sent
• process flow with minimum Si, if it has packets to process
• Update Si after processing packet
  • Si = Si + P (packet length)

문제점

• 만약 어떤 flow가 한동안 계속 안보내다가 돌아왔다면,
  그 flow는 Si가 아주 작을 것이다.
  그럼 얘 혼자 service alone for a long time
• 우선순위가 없다 (-> weighted fair queuing)

Solution

• timer를 두고 일정 시간 안들어오면 없는걸로 친다.
• 그러다가 들어오면 존재하는 Si 중에 가장 작은 값을 준다.
  (if queue j is empty, set Sj = Smin)

---

Weighted Fair Queuing

• fair queuing과 비슷하지만,
  각 flow가 다른 priority를 갖는다.
• Each flow has a weight, wi (우선순위) : weight of flow i
• Si = Si + P/wi
  

장점

• fair scheduling based on flow priorities
• avoid starvation

단점

• 처리가 복잡하다
• 계산이 복잡하다
  • flow separation,
  • packet sorting,
  • processing when a flow is added or removed

---

Traffic Shaping

• A method to control amount of data
  
  • data가 들어오는데, 어떤 flow에 대해 우르르르 들어오다가
    또 안들어왔다가 또 우르르 들어온다 (bursty)
  • 내가 이렇게 받았다고 내 다음 애한테도 이렇게 보내주지 말고,
    속도를 좀 맞춰서 보내주자 : traffic shaping

Token bucket filter

• Token이 bucket에 일정 속도로 쌓인다
  • 만약 bucket이 꽉 차면, token은 더이상 쌓이지 않는다
• Sender가 data traffic을 보낼 때, bucket에 token을 쓴다.
• 만약 bucket에 token이 없으면, sender는 traffic을 보내지 않는다.
  

Characterization

• token rate : r
• bucket depth : B

Use

• n byte를 보내려면 n개의 token이 필요하다
• 처음에는 bucket에 token이 없고,
  1초에 r개의 token이 쌓인다.
• token의 개수는 B를 넘을 수 없다.
  

Exercise

Look at the trace of input traffic, and find the minimum bucket sizeso that the traffic is NOT delayed

• r = 15kbps.
• 맨 처음에는 bucket이 꽉 차있다고 가정한다.
• r = 15kbps이므로 1초에 15kbit씩, 1ms에 15bit씩 들어온다

• Suppose B = 500
• 10ms에서, 처음으로 token 소비가 시작.
  소비 : -40kbps, 수입 : +15kbps => -25kbps
  30ms 되면 -25 * 20 = -500. 모두 바닥난다.
• 그럼 30ms에서 rate가 50kbps여도, 15kbp로밖에 보낼 수 없다.
• 즉, 500은 minumum bucket size가 아니다.

• Calculate minimum bucket size
• 10 ~ 30 : -25 * 20 = -500
• 30 ~ 40 : -35 * 10 = -350
• 40 ~ 60 : +5 * 20 = +100
• 60 ~ 100 : -5 * 40 = -200
  => minimum size = 950

• 단순히 편차 * 시간 계산해서 다 더하는 게 아니고,
  starting from the left, find the maximum data that is can be accumulated in the buffer

• 위 그림에서, 방금 전과 같이 단순하게 계산만 하면,
  (-15 * 20) + (+5 * 40) + (-25 * 30) = -850이지만,
  실제 minimum bucket size = 750

• minimum bucket size = 700

• 한 번에 다 쏟아버리는 경우를 주의하자