[Network] CH12. Scheduling and Traffic Shapin

chxxrin·2022년 6월 23일
0

컴퓨터네트워크

목록 보기
13/15

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 알고리즘은 다음과 같은 원리로 동작합니다:

  1. 버킷에는 최대 용량(capacity)이 정해져 있습니다. 이는 한 번에 전송할 수 있는 최대 트래픽 양을 나타냅니다.
  2. 일정한 속도(rate)로 토큰이 버킷에 채워집니다. 이 속도는 네트워크에서 허용되는 대역폭을 나타냅니다.
  3. 패킷이 전송되기 전에 토큰을 가져와야 합니다. 패킷을 전송하려면 충분한 토큰이 버킷에 있어야 합니다.
  4. 패킷을 전송할 때마다 해당 패킷의 크기만큼의 토큰이 사용됩니다. 토큰이 충분하지 않은 경우, 패킷은 대기열에 추가되거나 버려질 수 있습니다.

Token bucket을 사용하여 트래픽을 제어하면 트래픽의 평균 대역폭을 제한할 수 있으며, 네트워크 혼잡을 완화하고 패킷 손실을 줄일 수 있습니다. 또한 트래픽의 버스트(burst)를 제어하여 일정한 전송 속도를 유지할 수 있습니다.

0개의 댓글