지수 백오프

지수 백오프는 피드백을 사용하여 일부 프로세스의 속도를 곱하여 감소시켜 점차 허용 속도를 찾는 알고리즘입니다.이러한 알고리즘은 다양한 시스템 및 프로세스에서 사용되고 있으며, 특히 무선 네트워크와 컴퓨터 네트워크가 두드러집니다.

지수 백오프 알고리즘

지수 백오프 알고리즘은 불리한 이벤트에 대한 응답으로 제어된 프로세스의 속도를 감소시키는 폐쇄 루프 제어 시스템의 한 형태입니다.부작용이 발생할 때마다 공정의 속도는 몇 가지 승수만큼 감소합니다.부작용의 예로는 네트워크트래픽의 충돌, 서비스로부터의 에러 응답, 레이트 삭감을 위한 명시적 요구(즉, 「백오프」) 등이 있습니다.

속도 감소는 지수 함수로 모델링할 수 있습니다.

t=b^{c}

또는

f=snapfrac {1}{b^{c}}}

$여기$ 서 t는 작용 사이에 적용되는 시간 지연, $b$ 는 승수 또는 "기준", $c$ 는 관측된 부작용의 수, $f$ 는 프로세스의 빈도(또는 속도)이다(즉, 시간 단위당 작용 수).c $값$ 은 역행사가 관찰될 때마다 증가하여 지연이 기하급수적으로 증가하고 그에 따라 반비례 비율이 높아집니다.b = $2가$ 이진 지수 백오프 알고리즘이라고 하는 $지수$ 백오프 알고리즘입니다.

이 비율이 부작용에 대응하여 감소된 경우, 일반적으로 영원히 감소된 수준을 유지하지는 않는다.회복 시간 또는 냉각 기간이라고 하는 부작용이 일정 기간 동안 관찰되지 않는 경우, 이 비율은 다시 증가할 수 있다.레이트 증가를 다시 시도하기 전에 경과해야 하는 시간 자체는 지수 백오프 알고리즘에 의해 결정됩니다.일반적으로 레이트 회복은 백오프로 인한 레이트 감소보다 더 느리게 이루어지며 ^[1]레이트의 변동을 피하기 위해 세심한 조정이 필요한 경우가 많습니다.정확한 복구 동작은 구현에 따라 다르며 다양한 환경 요인에 의해 알 수 있습니다.

시스템에서 실질적으로 환율 저감을 실현하는 메커니즘은 단순한 시간 지연보다 더 복잡할 수 있습니다. $경우$ 에 따라서는 값 t는 특정 시간 지연 값이 아닌 시간 지연에 대한 상한을 나타낼 수 있습니다."지수적 백오프"라는 이름은 부작용 카운트와 지연 시간 사이의 정확한 수치적 관계가 아니라 백오프의 지수적 성장 특성을 의미한다.

환율 제한

지수 백오프는 일반적으로 웹 서비스 등의 컴퓨터 시스템에서 환율 제한 메커니즘의 일부로 사용되며, 리소스에 대한 액세스를 공평하게 분배하고 네트워크 폭주를 방지합니다.서비스가 클라이언트에 요구를 너무 자주 송신하고 있다고 통지할 때마다 클라이언트는 클라이언트의 요구 레이트가 허용 가능한 균형에 도달할 때까지 미리 정해진 비율만큼 레이트를 낮춥니다.클라이언트가 요구를 너무 자주 송신하는 경우, 요구에 대한 응답을 거부함으로써 레이트 제한을 강제할 수 있기 때문에, 잘못된 동작의 클라이언트는 할당된 자원을 초과할 수 없습니다.

고정 환율 제한을 넘어 지수 백오프 알고리즘을 사용하는 이점은 클라이언트에 사전 정보를 제공하지 않고 환율 제한을 동적으로 달성할 수 있다는 것입니다.부하가 크거나 서비스가 중단되는 등 리소스가 예기치 않게 제약되는 경우 서비스로부터의 백오프 요구 및 오류 응답에 의해 클라이언트의 요구 속도가 자동으로 저하될 수 있습니다.이를 통해 서비스의 과부하가 아닌 일정 수준의 가용성을 유지할 수 있습니다.또, 예를 들면, 부하가 높은 시간대에 전화 네트워크상의 긴급 통화의 백오프를 삭감하는 등, 각각의 중요도에 근거해 특정의 클라이언트에 대해서 서비스 품질의 우선순위를 부여할 수 있습니다.

알고리즘의 간단한 버전에서는 메시지는 소정의 시간(랜덤하지 않은 시간)만큼 지연됩니다.예를 들어 신뢰할 수 없는 트랜스포트(UDP 등)를 사용한SIP 프로토콜에서는 클라이언트는 T1초(통상은 500밀리초, 라운드 트립 시간의 추정치)에서 시작하여 재발송신 후 T2초(디폴트로는 4초)에 도달할 때까지 2배의 간격으로 요구를 재발송합니다.이것에 의해, 재발송신 간격은 500 밀리초, 1 초, 2 초, 4 초, 4 초,^[2] 4 초 등입니다.

충돌 회피

지수 백오프 알고리즘을 사용하면 네트워크의 충돌을 방지할 수 있습니다.포인트 투 멀티 포인트 또는 멀티 포인트 네트워크에서는, 복수의 송신자가 단일의 공유 채널을 개입시켜 통신합니다.2명의 송신자가 동시에 메시지를 송신하려고 하거나 서로 「대화」하면, 충돌이 발생해, 메세지가 파손되거나 없어집니다.그 후, 각 송신자는, 같은 메시지의 재발송신을 시도하기 전에 취소할 수 있습니다.

결정론적 지수 백오프 알고리즘은 이 사용 예에 적합하지 않습니다.이는 각 송신자가 같은 시간 동안 백오프하여 동시에 재발송신하고 또 다른 충돌을 일으키기 때문입니다.대신에, 콜리젼 회피의 목적으로, 재발송신 간격은 랜덤화되어 지수 백오프 알고리즘에 의해서 가능한 지연치의 범위가 설정됩니다.통상, 시간 지연은 슬롯 단위로 측정됩니다.슬롯은 네트워크상의 고정 길이의 기간(또는 「슬라이스」)입니다.이진 지수 백오프 알고리즘( $즉$ , b = $2$ )에서, c $충돌$ 후, 각 재전송은 0 ~ 2 - $1$ $사이$ 의 $임의$ 의^c 슬롯 횟수만큼 지연됩니다. 첫 번째 충돌 후, 각 송신자는 0 또는 1 슬롯 횟수를 기다립니다.두 번째 충돌 후 송신자는 0 ~3 슬롯 회(포함)의 범위에서 대기합니다.세 번째 충돌 후 송신자는 0 ~7 슬롯 회(포함)의 범위에서 대기합니다.재발송신 시행 횟수가 증가함에 따라 지연 가능성이 기하급수적으로 증가합니다.이렇게 하면 충돌 확률은 감소하지만 평균 지연 시간은 증가합니다.

지수 백오프는 Carrier-Sense Multiple Access with Collision Avoid(CSMA/CA; 콜리젼 회피) 및 Carrier-Sense Multiple Access with Collision Detection(CSMA/CD; 콜리젼 검출 포함 캐리어 감지 다중 액세스) 네트워크의 프레임 재발송신 중에 사용됩니다.이더넷 네트워크에서는, 콜리젼 후의 재발송신의 스케줄에 알고리즘이 일반적으로 사용됩니다.재발송신은, 슬롯 시간으로부터 도출된 시간(예를 들면, 512 비트의 송신에 걸리는 시간, 즉 512 비트 타임)과 재발송신의 시행 횟수만큼 지연됩니다.

예

이 예는, ^[3]송신 호스트가 프레임을 송신하고 있을 때에, 콜리젼이 발생한(즉, 다른 호스트가 송신을 시도한) 것을 확인할 수 있는 이더넷프로토콜로부터의 것입니다.양쪽 호스트가 콜리전이 발생하자마자 재전송을 시도하면 또 다른 콜리전이 발생하고 패턴은 영원히 계속됩니다.호스트는 이 상황이 발생하지 않도록 허용 범위 내에서 임의의 값을 선택해야 합니다.따라서 지수 백오프 알고리즘이 사용됩니다.이 예에서는 10 Mbit/s 이더넷 회선의 슬롯 시간이기 때문에 51.2 μs 값이 사용되고 있습니다.그러나 실제로는 51.2 μs를 임의의 양의 값으로 대체할 수 있다.

충돌이 처음 발생하면 "걸림 신호"를 전송하여 더 이상의 데이터가 전송되지 않도록 하십시오.
0초 또는 51.2μs 중 하나를 랜덤으로 선택한 후 프레임을 재발송합니다.
이것이 실패했을 경우는, 0 초, 51.2 μs, 102.4 μs, 또는 153.6 μs 후에 프레임을 재발송합니다.
그래도 실패하면 k · $51.2μs$ 후에 $프레임$ 을 재발송합니다. $여기$ 서 k는 0 ~ $23$ - 1 사이의 임의의 정수입니다.
이후 실패의 경우 c번째 실패 후 k · $51.2μs$ 후에 $프레임$ 을 재발송합니다. $여기$ 서 k는 0 ~ $2 c$ - $1$ 사이의 랜덤 정수입니다.

잘린 지수 백오프

알고리즘의 '절단' 변형은 c에 대한 $제한$ 을 도입합니다.이것은 단순히 일정 수의 증가 후에 지수가 멈춘다는 것을 의미합니다.c 의 $제한$ 이 없는 경우, 송신자가 네트워크 서비스의 저하등의 악영향을 반복해 관찰하는 경우는, 송신간의 지연이 바람직하지 않게 길어질 가능성이 있습니다.랜덤화 시스템에서는 이것이 우연히 발생하여 예측할 수 없는 지연이 발생할 수 있습니다. $c$ 의 무한증가에 의한 지연이 길어질 가능성은 기하급수적으로 낮아지지만 큰 수의 법칙에 의해 비지 네트워크에서는 사실상 피할 수 없습니다. $c$ 를 제한하면, 전송 지연이 예기치 않게 길어질 가능성을 저감 해, 일시적인 정지 후의 회복 시간을 단축할 수 있습니다.

예를 들어, (IEEE 802.3 CSMA/CD^[4] 표준에서와 같이) 잘린 이진수 지수 백오프 알고리즘에서 상한선이 i = $10$ 으로 $설정$ 되어 있는 경우, 최대 지연은 1023 슬롯 시간, 즉 $210$ - $1$ 이 됩니다.

시스템에 대한 적절한 백오프 한계를 선택하려면 충돌 확률과 지연 시간 간의 균형을 고려해야 합니다.천장을 높임으로써 각 전송 시도에서 충돌 확률이 기하급수적으로 감소합니다.동시에, 제한을 증가시키면, 송신에 있어서의 가능한 레이텐시 시간의 범위도 기하급수적으로 증가해, 결정성이 낮은 퍼포먼스와 평균 레이텐시의 증가로 이어집니다.시스템의 최적 제한값은 구현과 ^[5]환경 모두에 따라 다릅니다.

예상되는 백오프

백오프 시간의 분포가 균일할 경우 예상되는 백오프 시간은 가능성의 평균입니다.이진수 지수 백오프 알고리즘에서 c 충돌이 발생한 후 지연은 [ $0, 1$ , $...,$ $N]$ 슬롯에서 무작위로 선택됩니다. $여기$ 서 N = $2 c$ - $1$ , 예상 백오프 시간(슬롯 내)은 다음과 같습니다.

\operatorname {E} (c)=sum _{i=0}^{N}i=superfrac {1}{N+1}{\frac {N(N+1)}{2}}}=flac {N}{2}.

예를 들어, 세 번째( $c$ = $3$ ) 충돌에 대한 예상 백오프 시간, 먼저 최대 백오프 시간 N:

N=2^{c}-1

N=2^{3}-1=8-1

N=7,

다음으로 백오프 시간 가능성의 평균을 계산합니다.

1

}}=flac {N}{

2}}=

flac {2^{c

}-1

}{

2

\operatorname {E} (c)={\frac {1}{N+1}}\sum _{i=0}^{N}i={\frac {1}{N+1}}{\frac {N(N+1)}{2}}={\frac {N}{2}}={\frac {2^{c}-1}{2}}

즉, 예를 $들어$ E( $3) =$ 3.5 $슬롯$ 입니다.

「」를 참조해 주세요.

제어 이론

레퍼런스

^ Tanenbaum & Wetherall 2010, 395페이지
^ 로젠버그 외RFC3261 – SIP: Session Initiation Protocol.인터넷 소사이어티.2002.
^ Peterson, Larry L.; Davie, Bruce S. (2022). "Chapter 2: Direct Links". Computer Networks: A Systems Approach (Sixth ed.). Morgan Kaufmann Publishers. p. 120. ISBN 978-0-12-818200-0.
^ "IEEE Standard 802.3-2015". IEEE. Retrieved 20 March 2022. (표준)
^ Tanenbaum & Wetherall 2010, 285페이지

참고 문헌

Tanenbaum, Andrew; Wetherall, David (2010). Computer Networks (5th ed.). Pearson. ISBN 978-0132126953.

이 문서에는 General Services Administration 문서의 퍼블릭도메인 자료가 포함되어 있습니다.

[1] Tanenbaum & Wetherall 2010, 395페이지

[sip-2] 로젠버그 외RFC3261 – SIP: Session Initiation Protocol.인터넷 소사이어티.2002.

[3] Peterson, Larry L.; Davie, Bruce S. (2022). "Chapter 2: Direct Links". Computer Networks: A Systems Approach (Sixth ed.). Morgan Kaufmann Publishers. p. 120. ISBN 978-0-12-818200-0.

[IEEE_802_3-4] "IEEE Standard 802.3-2015". IEEE. Retrieved 20 March 2022. (표준)

[5] Tanenbaum & Wetherall 2010, 285페이지

[1]

[2]

[3]

[4]

[5]

Search

지수 백오프

네임스페이스

더

목차