균등화 큐잉

Fair queuing

균등화 큐잉은 일부 프로세스 및 네트워크 스케줄러에서 사용되는 스케줄링 알고리즘 패밀리입니다.이 알고리즘은 한정된 자원을 공유할 때 예를 들어 작은 작업을 생성하는 큰 패킷 또는 프로세스가 있는 플로우가 다른 흐름이나 프로세스보다 throughput 또는 CPU 시간을 소비하지 않도록 하기 위해 설계되었습니다.

일부 고급 네트워크 스위치 및 라우터에서는 균등화 큐잉이 구현되어 있습니다.

역사

균등화 큐잉이라는 용어는 1985년 John Nagle에 의해 만들어졌으며, 불량 동작하는 [1][2][3]호스트로부터의 네트워크 중단을 줄이기 위해 로컬에리어 네트워크와 인터넷 사이의 게이트웨이에서 라운드 로빈 스케줄링을 제안하고 있습니다.

바이트 가중 버전은 1989년 Alan Demers, Srinivasan Keshav 및 Scott Shenker에 의해 제안되었으며, 초기 Nagle 공정 [4][5]큐잉 알고리즘에 기초하였다.바이트 가중치 균등화 큐잉 알고리즘은 각 패킷의 이론적인 출발일을 계산함으로써 비트당 멀티플렉싱을 모방하는 것을 목적으로 합니다.

이 개념은 가중치 균등화 큐잉 및 보다 일반적인 트래픽쉐이핑 개념으로 더욱 발전했습니다.이러한 트래픽쉐이핑에서는 큐잉 우선순위가 동적으로 제어되어 원하는 흐름의 QoS(Quality of Service) 목표를 달성하거나 일부 흐름을 가속화할 수 있습니다.

원칙

균등화 큐잉에서는 패킷흐름마다 1개의 큐를 사용하여 각 플로우가 "리소스의 동일한 부분"[1][2]을 얻을 수 있도록 이들을 순환 처리합니다.

기존의 First In First Out(FIFO; 선입선출) 또는 priority 큐잉에 비해 장점은 큰 패킷 또는 다수의 데이터 패킷으로 구성된 고데이터 레이트플로우가 링크캐퍼시티의 공평한 점유율 이상을 차지할 수 없다는 것입니다.

균등화 큐잉은 버퍼에서 패킷을 전송하는 라우터, 스위치 및 통계 멀티플렉서에서 사용됩니다.버퍼는 데이터 패킷이 전송될 때까지 일시적으로 저장되는 큐잉시스템으로 기능합니다.

링크 데이터 레이트가 R인 경우, 항상 N개의 액티브 데이터 플로우(빈 큐가 아닌 것)는 각각 평균 데이터 레이트 R/N으로 처리됩니다.패킷이 차례로 전달되기 때문에 짧은 시간 내에 데이터 레이트가 이 값 주변에서 변동할 수 있습니다.

공정성

네트워크 스케줄링의 맥락에서 공정성에는 여러 정의가 있습니다.Nagel의 기사에서는 [2]패킷의 라운드로빈 스케줄링을 사용하고 있습니다.이것은 패킷의 수에 관해서는 공평하지만 패킷의 사이즈가 다른 경우에는 대역폭 사용에 대해서는 공평하지 않습니다.max-min 공정성, Worst-case [6]공정성 및 공정성 [7]지수를 포함한 공정성 측정의 몇 가지 공식 개념이 정의되었다.

가중 공유로의 일반화

초기 아이디어는 각 흐름에 동일한 속도를 제공합니다.자연스러운 확장은 사용자가 각 흐름에 할당되는 대역폭의 일부를 지정함으로써 가중치 균등화 큐잉과 일반화된 프로세서 공유를 가능하게 하는 것입니다.

바이트 가중 균등화 큐잉 알고리즘

이 알고리즘은 경쟁 흐름 간의 링크자원 비트 라운드 로빈 공유의 공정성을 에뮬레이트하려고 합니다.단, 패킷 기반 흐름은 패킷 단위로 순차적으로 전송해야 합니다.바이트 가중치 균등화 큐잉 알고리즘은 각 패킷의 종료 시간을 비트 단위로 라운드 로빈으로 전송할 수 있는 것처럼 모델링하여 패킷의 전송 순서를 선택합니다.이 모델링에 따라 가장 빠른 종료 시간을 가진 패킷이 다음으로 전송 대상으로 선택됩니다.

알고리즘의 복잡도는 O(log(n)입니다.n은 큐/플로우 수입니다.

알고리즘 상세

실제 종료 시간의 모델링은 실현 가능하지만 계산 부하가 높습니다.이 모델은 패킷이 전송 대상으로 선택될 때마다, 그리고 새로운 패킷이 임의의 큐에 도착할 때마다 실질적으로 재계산되어야 합니다.

계산 부하를 줄이기 위해 가상 시간의 개념이 도입되었습니다.각 패킷의 종료 시간은, 단조롭게 증가하는 이 대체 가상 타임 스케일에 근거해 계산됩니다.가상 시간은 패킷의 송신이 완료되는 시간을 정확하게 모델화하지는 않지만, 풀 기능 모델의 목적을 달성하기 위해 전송이 발생하는 순서를 정확하게 모델화합니다.가상 시간을 사용하면 이전에 큐잉된 패킷의 종료 시간을 재계산할 필요가 없습니다.종료시간은 절대적인 관점에서 기존 패킷의 경우 새로운 착신에 의해 영향을 받을 수 있지만 가상 타임라인의 종료시간은 변경되지 않습니다.가상 타임라인은 새로운 전송에 대응하기 위해 실시간에 대해 뒤틀립니다.

새로 큐잉된 패킷의 가상 종료 시간은 가상 시작 시간과 패킷 크기를 합한 값으로 지정됩니다.가상 시작 시간은 동일한 큐의 이전 가상 종료 시간과 현재 순간 사이의 최대 시간입니다.

균등화 큐잉은 모든 후보 패킷(즉, 비어 있지 않은 모든 흐름 큐의 선두에 있는 패킷)의 가상 종료 시간을 계산하고 가상 종료 시간을 비교하여 최소 하나를 선택합니다.가상 종료 시간이 최소인 패킷이 송신됩니다.

유사 코드

공유 변수는 큐의 N // Nb를 설정합니다[ 1 .N] // lastVirFinish [1..N] // 마지막 가상 종료 순간
receive(패킷) queueNum : = [ queue ]를 선택합니다.enqueue(패킷) update Time(패킷, queueNum)
 
updateTime(패킷, queueNum) // virStart는 virStart : = max ( now lastVirFinish [queueNum ]) 패킷의 가상 시작입니다.virFinish : = packet . size + virStart lastVirFinish [ queNum ] : = packet . virFinish
send() queueNum : = selectQue() packet : = queue [ queueNum ].dequeue() 리턴 패킷
 
selectQue() it : = 1 minVirFinish = 1 minVirFinish =  N do queue : = queue [ it ](큐.empty및 queue.head.head.VirFinish 큐가 아닌 경우 큐[ [it]를 선택합니다) = 1 minVirFinish 큐를 반환합니다.

receive() 함수는 패킷을 수신할 때마다 실행되며 send()는 전송할 패킷을 선택해야 할 때마다 실행됩니다.즉, 링크가 아이돌 상태이고 큐가 비어 있지 않은 경우입니다.이 의사 코드는 현재 가상 시간을 반환하는 함수 now()와 패킷이 큐잉되는 큐를 선택하는 함수 chooseQue()가 있다고 가정합니다.

selectQueue() 함수는 가상 종료 시간이 최소인 큐를 선택합니다.가독성을 위해, 구동 장치 따위를 생각해낸 선형으로 조사를 하다.하지만은 정렬된 목록을 유지하는 로그 시간에, O(로그(n))복잡도로 연결하는 하지만 더 코드 복잡한 구현할 수 있다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b John Nagle: "무한 스토리지를 갖춘 패킷 스위치", RFC 970, IETF, 1985년 12월
  2. ^ a b c Nagle, J. B. (1987). "On Packet Switches with Infinite Storage". IEEE Transactions on Communications. 35 (4): 435–438. CiteSeerX 10.1.1.649.5380. doi:10.1109/TCOM.1987.1096782.
  3. ^ Phillip Gross (January 1986), Proceedings of the 16-17 January 1986 DARPA Gateway Algorithms and Data Structures Task Force (PDF), IETF, pp. 5, 98, retrieved 2015-03-04, Nagle presented his "fair queuing" scheme, in which gateways maintain separate queues for each sending host. In this way, hosts with pathological implementations can not usurp more than their fair share of the gateway’s resources. This invoked spirited and interested discussion.
  4. ^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). "Analysis and simulation of a fair queueing algorithm". ACM SIGCOMM Computer Communication Review. 19 (4): 1–12. doi:10.1145/75247.75248.
  5. ^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1990). "Analysis and Simulation of a Fair Queueing Algorithm" (PDF). Internetworking: Research and Experience. 1: 3–26.
  6. ^ Bennett, J. C. R.; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing". Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. Vol. 1. p. 120. doi:10.1109/INFCOM.1996.497885. ISBN 978-0-8186-7293-4.
  7. ^ Ito, Y.; Tasaka, S.; Ishibashi, Y. (2002). "Variably weighted round robin queueing for core IP routers". Conference Proceedings of the IEEE International Performance, Computing, and Communications Conference (Cat. No.02CH37326). p. 159. doi:10.1109/IPCCC.2002.995147. ISBN 978-0-7803-7371-6.