Scheduling
: 라우터의 packet의 처리 순서 정하기
FIFO queue
- basic
- (src->des)flow가 구별되지 않는다.
- congestion control 없다.
- queue가 다 차면, last packet이 drop된다(tail drop)
- 지연시간에 대해서는 fair하다
- bandwidth가 고려되지 않는다.
[문제] - 어떤 flow가 많이 보내면, 독식한다.
- Qos의 다양한 타입들을 packet이 필요할 수 있는데, FIFO 큐에선 못함
ex) 우선, 긴급 traffic 먼저 못보냄
Priority queue
- 우선순위에 의해 패킷 processing
[문제] 우선순위가 낮은 패킷들은 무한정 지연될 수 있다.(starvation)
Round Robin
- flow별로 queue에 삽입(src, des 확인 후, new flow구나!)
- 각 queue마다(flow마다) 하나의 packet을 처리한다.
- 패킷을 더 많이 보낸다고, service를 더 많이 갖지 않는다.(FIFO 큐와 반대)
- 그러나, 큰 패킷을 보내는 flow는 더 많은 service를 갖는다.
Fair Queuing
- packet size에 따라 service 다르게 하여 fair service!
- 각 flow마다 각 큐
- Si = flow i가 보낸 데이터의 양
- 가장 작은 Si 가진 flow가 보낼 패킷이 있다면, 처리한다.
- Si = Si + p(packet length)
[문제] S가 작은게, 우선순위에서 뒤로 밀려서 그런게 아니라, 원래부터 해당 flow가 긴시간동안 보내지 않아서, 그동안 다른 flow가 많이 보내서 Si가 컸다면,,,
갑자기 점수가 매우 작았던 flow만 한동안 service 받을 수 있다.
[해결] "use it or lose it" - 일정 시간 지나면, 다른 큐들중 가장 막내 점수(최소점수)를 부여한다.
- 너는 밀린게 아니라, 너가 안보낸거니까
Weighted Fair Queing
- flow(큐) 별로 점수 weight 가중치가 있다!
- Si = Si + P/wi
- weight가 높을 수록 Si가 낮아져서 우선순위가 높아진다!
- 장점:
- avoid starvation( weight가 낮아도 언젠가는 기회가 온다)
- flow 우선순위에 따른 fair scheduling
ex)
Traffic Shaping
: 라우터로 들어오는 data pattern이 bursty할 때 일정하게 바꿔주기
(왜냐하면, bursty 한 경우에 받는 쪽에서 buffer overflow 발생 가능)
Token bucket filter
- sender)traffic 보낼때마다 token을 쓴다.
- 남은 토큰이 없으면 보낼 수 없다. 찰 때까지 기다린다.
- bucket이 다차면, token은 더이상 쌓일 수 없다.
- bucket은 일정한 속도로 찬다.
- bucket size는 정해져 있음
- Token rate : r(bps) 토큰이 차는 속도, 1초에 r token씩 찬다.
- Bucket depth : B(bit) 버캣의 크기, token의 개수는 최대 B
- 1 토큰은 1byte 보내는데 필요
- 초기 bucket: token이 다 찬 상태
예제: minimum bucket size 구하기 SH
예제: delay가 생기지 않는 min bucket size 구하기
1. input traffic 같은 구간별로 계산
2. (쓰는 token속도 - 차는 token 속도) * 걸리는시간 구하기
3. 시간순서대로 더하는데, 항상 양수값 유지! 음수가 되더라도 0이라 생각하고 계산
4. 더하는 과정 속 maximum data가 곧, min bucket의 size
