가중 균등화 큐잉

Weighted Fair Queueing(WFQ; 가중치 균등화 큐잉)은 네트워크 스케줄링 알고리즘입니다.WFQ는 Generalized Processor Sharing(GPS; 일반화 프로세서 공유) 정책의 패킷 기반 구현이며 Fair Queuing(FQ; 공정 큐잉)의 자연스러운 확장입니다.FQ는 링크의 캐퍼시티를 동일한 서브부분으로 공유하는 반면 WFQ를 사용하면 스케줄러는 각 흐름에 대해 어떤 캐퍼시티가 부여될지를 지정할 수 있습니다.

가중치 균등화 큐잉은 패킷별 GPS(PGPS 또는 P-GPS)라고도 불리는데, 이는 "도착 ^[1]패턴에 관계없이 1 패킷 전송 시간 내에" 일반화된 프로세서 공유에 가깝기 때문입니다.

파라미터화 및 공정성

다른 GPS와 같은 스케줄링 알고리즘과 마찬가지로 가중치 선택은 네트워크 관리자에게 맡겨집니다.'공정'에 대한 고유한 정의는 없습니다(자세한 내용은 '공정 큐잉' fairness '공정' 참조).

WFQ 가중치를 동적으로 규제함으로써 WFQ를 사용하여 서비스 품질 제어, 예를 들어 보증 데이터 ^{[citation needed]}레이트를 달성할 수 있습니다.

가중치를 w $w_{i}=1/c_{i}$ $=$ $w_{i}=1/c_{i}$ ${\$ }= $1/c_{i$ 로 $w_{i}=1/c_{i}$ 하면 비례적으로 공정한 동작을 달성할 수 있습니다. $c_{i}$ 서 c $c_{i}$ ${\$ $displaystyle$ $c_{i}$ 는 $c_{i}$ 데이터 $흐름$ i {\displaystyle i $i$ 의 데이터 비트당 비용입니다. 예를 들어 CDMA 스펙트럼 확산 셀룰러 네트워크에서는 필요한 에너지(간섭취)일 수 있습니다.nce level) 및 동적 채널 할당 시스템에서는 비용은 동일 주파수 채널을 사용할 수 없는 인근 기지국 사이트의 수가 될 수 있으며, 이는 공동 채널 간섭을 피할 수 있습니다.

알고리즘.

WFQ에서는 N개의 $플로우$ 를 처리하는 스케줄러는 플로우마다 1개의 $w_{i}$ $w_{i}$ 로 $w_{i}$ 설정됩니다. $다음$ 으로 번호 $i$ 의 $i$ 흐름은 ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ 1 ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ + ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ 2 ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ + ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ . + ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ ) $R$ {\ $displaystyle {w_{i}}{(w_{1}+w_{2}+...)$ 의 ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ 데이터 레이트를 달성합니다. $+w_{N}}}}R$ 여기서 $(\displaystyle$ R $)$ 은 $R$ 링크환율입니다모든 무게가 동일한 WFQ 스케줄러는 FQ 스케줄러입니다.

모든 균등화 큐잉스케줄러와 마찬가지로 각 흐름은 다른 흐름으로부터 보호됩니다.데이터 플로우가 리크 버킷에 제약되어 있으면 엔드 투 엔드의 지연이 ^[2]보증된다는 것을 증명할 수 있습니다.

WFQ의 알고리즘은 FQ의 알고리즘과 매우 유사합니다.각 패킷에 대해 가상 이론상의 출발 날짜가 계산됩니다.이 날짜는 스케줄러가 완벽한 GPS 스케줄러일 경우 출발 날짜로 정의됩니다.다음으로 출력 링크가 아이돌일 때마다 날짜가 가장 작은 패킷이 송신 대상으로 선택됩니다.

의사 코드는 가상 출발 시간의 계산을 다음과 같이 대체함으로써 FQ 중 하나에서 간단히 얻을 수 있습니다.

packet.virFinish = virStart + packet.size / Ri

$R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ i $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ i ( $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ 1 $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ + $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ + $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ . + $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ N ) $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ { \ $displaystyle R$ _ { i } = $specfrac$ { $w$ _ { $i$ } { ( $w$ _ { $1}$ + $w$ _ {2 $}$ +... $+w_{N}}}}}R$ 입니다.

GPS 근사치로서의 WFQ

WFQ는 PGPS라는 이름으로 "GPS에 대한 뛰어난 근사치"로 설계되었으며 "도착 ^[1]패턴에 관계없이 1 패킷 전송 시간 내에 GPS를 근접시키는 것으로 입증되었습니다.

WFQ의 실장은 균등화 큐잉과 비슷하기 때문에 O(log(n)의 복잡도는 같습니다.여기서 n은 흐름의 수입니다.이 복잡성은 패킷이 전송될 때마다 가상 종료 시간이 가장 짧은 큐를 선택해야 하기 때문에 발생합니다.

WFQ 이후 GPS의 다른 구현이 몇 가지 정의되었습니다.

WFQ가 이상적인 GPS 정책보다 "1 패킷" 늦게라도 임의로 앞설 수 있습니다.Worst-case Fair Weighted Fair Queueing(WF2Q; 균등화 균등화 큐잉)은 각 패킷에 가상 서비스 시작을 추가하여 패킷을 수정하고 가상 서비스 시작이 현재 시간보다 ^[3]작지 않은 경우에만 패킷을 선택합니다.
가상 종료 시간이 최소인 큐를 선택하는 것은 와이어 스피드로 구현하기 어려울 수 있습니다.그 후, GPS의 다른 근사치(예: 적자 라운드로빈)는 덜 복잡한 것으로 정의되었습니다.

역사

FQ에 대한 확장 가능성으로서의 마지막에 기재되어 있는 임의의 방법으로 대역폭을 공유하는 파라미터의 도입.weighted라는 용어가 처음 표시됩니다.^[1]

「」를 참조해 주세요.

레퍼런스

^ ^a ^b ^c Parekh, A. K.; Gallager, R. G. (1993). "A generalized processor sharing approach to flow control in integrated services networks: The single-node case" (PDF). IEEE/ACM Transactions on Networking. 1 (3): 344. doi:10.1109/90.234856.
^ Stiliadis, D.; Varma, A. (1998). "Latency-rate servers: A general model for analysis of traffic scheduling algorithms" (PDF). IEEE/ACM Transactions on Networking. 6 (5): 611. doi:10.1109/90.731196.
^ 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.
^ Demers, A.; Keshav, S.; Shenker, S. (1989). "Analysis and simulation of a fair queueing algorithm". ACM SIGCOMM Computer Communication Review. 19 (4): 1. doi:10.1145/75247.75248.

[GPS-1] Parekh, A. K.; Gallager, R. G. (1993). "A generalized processor sharing approach to flow control in integrated services networks: The single-node case" (PDF). IEEE/ACM Transactions on Networking. 1 (3): 344. doi:10.1109/90.234856.

[2] Stiliadis, D.; Varma, A. (1998). "Latency-rate servers: A general model for analysis of traffic scheduling algorithms" (PDF). IEEE/ACM Transactions on Networking. 6 (5): 611. doi:10.1109/90.731196.

[WF2Q-3] 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.

[FQ-4] Demers, A.; Keshav, S.; Shenker, S. (1989). "Analysis and simulation of a fair queueing algorithm". ACM SIGCOMM Computer Communication Review. 19 (4): 1. doi:10.1145/75247.75248.

[1]

[2]

[3]

Search

가중 균등화 큐잉

네임스페이스

더

목차

파라미터화 및 공정성

알고리즘.

GPS 근사치로서의 WFQ

역사

「」를 참조해 주세요.

레퍼런스

Search

가중 균등화 큐잉

파라미터화 및 공정성

알고리즘.

GPS 근사치로서의 WFQ

역사

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.