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하다
- 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
- data가 들어오는데, 어떤 flow에 대해 우르르르 들어오다가
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
- 한 번에 다 쏟아버리는 경우를 주의하자
