Scheduling and Traffic Shaping
스케줄링 (Scheduling)
• 패킷 처리 순서를 결정하는 것
• FIFO (선입선출) 큐: 기본 유형
먼저 도착한 패킷이 먼저 처리되고 (전송되는)순서대로 처리됩니다.- FIFO 큐
- 흐름(flow)을 구분하지 않습니다.
- 혼잡 제어(congestion control)가 없습니다.
- 큐가 가득 찬 경우, 마지막 패킷이 삭제됩니다 (테일 드롭).
- 지연시간 측면에서 공정합니다.
- 대역폭을 고려하지 않습니다.
FIFO 큐: 문제점
– 한 플로우가 더 많은 패킷을 보내면, 해당 플로우가 우선적으로 처리됩니다.
• 이는 이기적인 동작을 장려하며,
공격에 사용될 수 있습니다.
– 패킷은 다양한 QoS(서비스 품질)를 필요로 할 수 있지만, FIFO 큐에서는 구현할 수 없습니다.
• 우선순위 큐
– 패킷을 우선순위에 따라 처리합니다.
• 늦게 도착한 패킷이라도 가장 높은 우선순위를 가진 경우, 우선 처리됩니다.
• 우선순위 큐: 문제점
– 낮은 우선순위의 플로우는 굶주릴 수 있습니다.
• 오랜 시간 동안 패킷을 보내지 못할 수 있습니다(굶주림 현상).
- Round Robin
– 각 플로우에 대한 별도의 큐가 존재합니다.
– 각 큐를 순환하면서 각 큐에서 하나의 패킷을 처리합니다.
– FIFO와 비교했을 때, 플로우가 더 많은 패킷을 보내도 더 많은 서비스를 받지 않습니다.
– 큰 패킷을 보내는 플로우는 더 많은 서비스를 받을 수 있습니다.
• 공정 대기
– 각 플로우에 대한 큐가 존재합니다.
– 플로우가 공정한 서비스를 받을 수 있도록 패킷을 스케줄링합니다. • 패킷 크기가 다른 경우에도 공정한 스케줄링이 되어야 합니다.
• 가변 패킷 길이와 함께 하는 공정 대기: 알고리즘 – Si = 플로우 i가 전송한 데이터 양
– 처리할 패킷이 있는 경우, Si가 가장 작은 플로우를 처리합니다.
– 패킷 처리 후에 Si를 업데이트합니다.
• Si = Si + P (패킷 길이)
• 공정 대기: 문제점
– 플로우가 오랜 시간 동안 데이터를 보내지 않고 돌아온 경우
– 해당 플로우의 Si가 매우 작아지게 되며, 긴 시간 동안 독점적인 서비스를 받게 됩니다.
• 해결책
– "사용하거나 잃어버리기"
– Smin = queue i가 비어 있지 않은 경우에 대한 min(Si)로 설정합니다. – 큐 j가 비어 있는 경우, Sj = Smin으로 설정합니다.
• 가중치 공정 대기
– 공정 대기와 유사하지만, 플로우에는 다른 우선순위가 있습니다.
– 각 플로우에는 가중치 wi(플로우 i의 가중치)가 있습니다.
– Si는 다음과 같은 방식으로 계산됩니다. • Si = Si + P/wi
• 가중치 공정 대기
• 가중치 공정 대기: 장점
– 플로우 우선순위에 따른 공정한 스케줄링 – 굶주림 현상 방지
• 가중치 공정 대기: 단점 – 복잡한 상태
• 각 플로우에 대한 별도의 큐
– 복잡한 계산
• 플로우 분리
• 패킷 정렬
• 플로우 추가 또는 제거 시 처리 과정
• S 값이 같은 경우의 우선순위: A > B > C
– 모든 플로우의 가중치가 같은 경우, 패킷 처리 순서는? – WA = 4, WB = 1, WC = 2일 때 패킷 처리 순서는?
FIFO 큐: 문제점
– 플로우가 더 많은 패킷을 보내면 해당 플로우가 더 많은 서비스를 받습니다. • 이는 이기적인 행동을 장려하고,
공격에 사용될 수 있습니다.
– 패킷은 다양한 QoS(서비스 품질)가 필요할 수 있지만 FIFO 큐에서는 구현할 수 없습니다.
• 우선순위 큐
– 패킷을 우선순위에 따라 처리합니다.
• 늦게 도착한 패킷이라도 가장 높은 우선순위일 경우 먼저 처리됩니다.
• 우선순위 큐: 문제점
– 낮은 우선순위 플로우는 굶주릴 수 있습니다.
• 긴 시간 동안 패킷을 보내지 못할 수 있습니다(굶주림).
- Round Robin
– 각 플로우마다 큐가 있습니다.
– 각 큐를 돌아가면서 한 번에 한 개의 패킷을 처리합니다.
– FIFO와 비교했을 때, 플로우가 더 많은 패킷을 보내도 더 많은 서비스를 받지 않습니다.
– 큰 패킷을 보내는 플로우는 더 많은 서비스를 받을 수 있습니다.
• 공정 대기
– 각 플로우마다 큐가 있습니다.
– 플로우에 공정한 서비스를 제공하기 위해 패킷을 스케줄링합니다. • 패킷 크기가 다른 경우에도 공정한 스케줄링이 필요합니다.
• 가변 패킷 길이로 공정 대기: 알고리즘 – Si = 플로우 i가 전송한 데이터 양
– 처리 가능한 패킷이 있는 경우, 가장 작은 Si를 가진 플로우를 처리합니다.
– 패킷 처리 후 Si를 업데이트합니다.
• Si = Si + P (패킷 길이)
• 공정 대기: 문제점
– 플로우가 오랜 시간 동안 데이터를 보내지 않고 돌아온 경우
– 해당 플로우의 Si가 매우 작아지게 되어 긴 시간 동안 독점적인 서비스를 받습니다.
• 해결책
– "사용하거나 잃어버리기"
– Smin = 큐 i가 비어 있지 않은 경우의 min(Si)로 설정합니다.
• 가중치 공정 대기
– 공정 대기와 유사하지만, 플로우에는 다른 우선순위가 있습니다.
– 각 플로우에는 가중치 wi(플로우 i의 가중치)가 있습니다.
– Si는 다음과 같은 방식으로 계산됩니다. • Si = Si + P/wi
• 가중치 공정 대기
• 가중치 공정 대기: 장점
– 플로우 우선순위에 따른 공정한 스케줄링 – 굶주림 현상 방지
• 가중치 공정 대기: 단점 – 복잡한 상태
• 각 플로우에 대한 별도의 큐
– 복잡한 계산
• 플로우 분리
• 패킷 정렬
• 플로우 추가 또는 제거 시 처리 과정
• S 값이 같은 경우의 우선순위: A > B > C
– 모든 플로우의 가중치가 같은 경우, 패킷 처리 순서는? – WA = 4, WB = 1, WC = 2일 때 패킷 처리 순서는?
트래픽 셰이핑 (Traffic Shaping)
• 소스가 네트워크로 보내는 데이터 양을 제어하는 방법
• 토큰 버킷 필터 (Token Bucket Filter)
- 버킷에 토큰이 축적됩니다.
- 버킷이 가득 차면 더 이상 토큰이 축적되지 않습니다.
- 송신자가 데이터 트래픽을 보낼 때, 버킷에서도 토큰을 소비합니다.
- 버킷에 토큰이 없으면 송신자는 트래픽을 보내지 않습니다.
- 토큰 버킷 (Token Bucket)
• 트래픽 특성화 - 토큰 비율: r
- 버킷 깊이: B
- 사용 방법
- 1바이트를 보내기 위해서는 1개의 토큰이 필요합니다.
- 초기에는 버킷에 토큰이 없습니다.
- 1초 동안 r개의 토큰이 축적됩니다.
- 토큰의 개수는 B를 초과할 수 없습니다.
- 입력 트래픽의 추적을 살펴보고, 지연 없이 트래픽을 처리하기 위해 필요한 최소한의 버킷 크기를 찾습니다.
Traffic shaping은 네트워크 트래픽을 제어하여 대역폭 사용을 조절하는 메커니즘입니다. Token bucket은 traffic shaping에서 널리 사용되는 알고리즘 중 하나입니다.
Token bucket은 일정한 속도로 토큰이 채워지는 "통"이라는 버킷을 사용하여 트래픽을 제어합니다. 각 토큰은 패킷을 전송하는 데 필요한 대역폭을 나타냅니다. 패킷이 전송되기 전에 토큰이 사용되며, 토큰이 없는 경우에는 패킷이 대기하게 됩니다.
Token bucket 알고리즘은 다음과 같은 원리로 동작합니다:
- 버킷에는
최대 용량(capacity)이 정해져 있습니다. 이는 한 번에 전송할 수 있는 최대 트래픽 양을 나타냅니다. - 일정한 속도(rate)로 토큰이 버킷에 채워집니다. 이 속도는 네트워크에서 허용되는 대역폭을 나타냅니다.
- 패킷이 전송되기 전에 토큰을 가져와야 합니다. 패킷을 전송하려면 충분한 토큰이 버킷에 있어야 합니다.
패킷을 전송할 때마다 해당 패킷의 크기만큼의 토큰이 사용됩니다. 토큰이 충분하지 않은 경우, 패킷은 대기열에 추가되거나 버려질 수 있습니다.
Token bucket을 사용하여 트래픽을 제어하면 트래픽의 평균 대역폭을 제한할 수 있으며, 네트워크 혼잡을 완화하고 패킷 손실을 줄일 수 있습니다. 또한 트래픽의 버스트(burst)를 제어하여 일정한 전송 속도를 유지할 수 있습니다.
