최대 최소 공정성
Max-min fairness통신 네트워크, 다중화 및 희소한 자원의 분배에서, 최대 최소 공정성은 할당이 실현 가능하고, 어떤 참가자의 할당을 증가시키려는 시도가 반드시 같거나 작은 할당을 가진 다른 참가자의 할당을 감소시키는 경우에 한해 할당에 의해 달성된다고 한다.이온
best effort 통계 멀티플렉싱에서는 선착순(FCFS) 스케줄링 정책이 자주 사용됩니다.FCFS에 대한 max-min 공정성의 이점은 트래픽쉐이핑이 발생한다는 것입니다.즉, 대량의 데이터 패킷 또는 다수의 패킷의 버스트로 구성된 잘못된 흐름은 다른 흐름은 아닌 자기 자신만 처벌합니다.그 결과, 네트워크의 congestion는 어느 정도 회피됩니다.
균등화 큐잉은 통계 다중화 및 best effort 네트워크의 max-min 균등화 패킷스케줄링 알고리즘의 일례입니다.이는 활성화 된 이후 가장 낮은 데이터 레이트를 달성한 사용자에게 스케줄링 우선순위를 부여하기 때문입니다.크기가 동일한 데이터 패킷의 경우 라운드 로빈 스케줄링은 max-min으로 충분합니다.
리소스 공유를 위한 다른 정책과의 비교
일반적으로 낮은 수준의 공정성을 특징으로 하는 자원 공유 정책(공정성 측정 참조)은 높은 평균 throughput을 제공하지만 서비스 품질은 낮은 안정성을 제공합니다.즉, 달성된 서비스 품질은 다른 사용자의 동작에 따라 시간에 따라 달라집니다.이러한 불안정성이 심할 경우 사용자가 보다 안정적인 다른 통신 서비스를 선택하는 불행한 결과를 초래할 수 있습니다.
max-min 균등 자원 공유는 작업 절약형 [further explanation needed]자원 균등 공유 정책보다 평균 throughput(또는 무선 네트워크에서의 시스템스펙트럼 효율)이 높고 자원 사용률이 향상됩니다.균등한 공유에서는 일부 데이터 플로우가 자원의 "균등하게 배분"된 부분을 활용하지 못할 수 있습니다.균등한 공유를 위한 정책은 데이터 플로우가 다른 어떤 흐름보다 많은 리소스를 획득하지 못하도록 하고 네트워크 내의 빈 리소스를 이용하는 것을 방지합니다.
한편, max-min 공정성에서는 최대 throughput 자원 관리보다 평균 throughput이 낮습니다.이 경우 가장 비용이 적게 드는 흐름에는 사용할 수 있는 모든 용량이 할당되어 가장 비용이 많이 드는 흐름에는 용량이 남아 있지 않을 수 있습니다.무선 네트워크에서 고가의 사용자는 일반적으로 높은 신호 감쇠에 노출된 기지국에서 멀리 떨어진 모바일 스테이션입니다.단, 최대 스루풋정책은 고가의 흐름을 고갈시켜 '행복한 고객'을 줄일 수 있습니다.
max-min 공정성과 최대 throughput 스케줄링의 타협은 비례 공정성입니다.이 경우 리소스가 각 사용자에게 동일한 비용을 달성하거나 데이터 흐름에 도달하는 단위당 최대 비용을 최소화한다는 목표에 따라 분할됩니다.고가의 데이터 흐름은 비례적으로 다른 데이터 흐름보다 낮은 서비스 품질을 달성하지만 굶주림에 시달리지는 않습니다.최대한의 공정성은 보다 안정적인 서비스 품질로 이어지며, 따라서 더 많은 "행복한 고객"이 될 수 있습니다.
최대 최소 균등화 링크 용량 사전 할당
통신 네트워크의 max-min 공정성에서는 best effort형 네트워크가 아닌 사전에 플로우에 자원(통신 링크의 capacity)이 할당되어 있는 것을 전제로 하고 있습니다.
i 데이터 흐름(사용자 또는 소스라고도 함)을 고려합니다.각 데이터 흐름은 정의된 초기 노드, 대상 노드 및 원하는 데이터 레이트를 가집니다.네트워크를 통과하는 경로상의 흐름은 로드밸런싱 방식에서 "병렬" 링크로 분할될 수 있습니다.
i번째 좌표가 흐름에 대한 할당, 즉 사용자 i가 데이터를 방출할 수 있는 속도인 할당 벡터 x.
비율 x의 배분은 실현 가능한 배분 영역 내에서 비율의 증가가 이미 더 작은 비율의 감소 원가에 해당해야 하는 경우에만 "max-min fair"이다.문제에 따라 max-min 균등 배분이 존재할 수도 있고 존재하지 않을 수도 있습니다.그러나 그것이 존재한다면, 그것은 유일합니다.
"max-min"이라는 이름은 알고리즘에 의해 가능한 한 큰(최대화된) 흐름의 속도가 작은(또는 최소) 흐름의 속도라는 생각에서 유래했습니다.따라서 작은 흐름에 상대적으로 높은 우선순위를 부여합니다.플로우가 C/N(링크 용량/플로우 수)보다 많은 양을 소비하도록 요구하는 경우에만 알고리즘에 의해 대역폭이 억제될 위험이 있습니다.
병목 링크
데이터 플로우 i의 보틀넥 링크는 충분히 이용(포화)되는 링크이며, 이 링크를 공유하는 모든 플로우 중 데이터 플로우 i는 전체 최대 [1]데이터 레이트를 달성한다.이 정의는 병목현상의 일반적인 의미와는 크게 다릅니다.또, 이 정의에서는, 복수의 플로우간에 단일의 보틀 넥 링크를 공유하는 것을 금지하고 있지 않습니다.
데이터 레이트 할당은 2개의 노드 간의 데이터 흐름에 적어도1개의 병목 링크가 있는 경우에만 공평합니다.
프로그레시브 필링 알고리즘
네트워크 노드에 미리 자원을 할당하면 프로그레시브 필링 알고리즘을 사용하여 max-min 공정성을 얻을 수 있다.0인 모든 레이트로 시작하여 1개 또는 여러 링크 용량 제한에 도달할 때까지 모든 레이트를 같은 속도로 증가시킵니다.이러한 링크를 사용하는 소스의 환율은 더 이상 증가하지 않으며, 다른 소스의 환율은 계속 증가합니다.정지된 모든 소스에는 병목 링크가 있습니다.이는 포화된 링크를 사용하고 있으며, 포화된 링크를 사용하는 다른 모든 소스가 동시에 정지되거나 이전에 정지되었기 때문에 레이트가 작거나 같기 때문입니다.알고리즘은 증가할 수 없을 때까지 계속됩니다.마지막으로 알고리즘이 종료되면 모든 소스가 어느 시점에서 정지되어 보틀넥 링크가 생깁니다.이 할당은 max-min 공정합니다.
「 」를 참조해 주세요.
- 공정성 측정
- 멀티태스킹 운영체제에서의 스케줄링
- 평등주의적 사회적 선택 규칙 - max-min 원칙에 기초한 대안 중 선택.
