리키 버킷

누출형 버킷은 물이 유입되는 평균 속도가 버킷이 누출되는 속도를 초과하거나 버킷 용량보다 많은 물을 한꺼번에 쏟아 부을 경우 누수가 지속되는 버킷이 어떻게 넘칠지 유추한 알고리즘이다. 이산형 이벤트의 일부 시퀀스가 평균 및 피크 속도 또는 빈도에 대해 정의된 한계치를 준수하는지 여부를 결정하는 데 사용할 수 있다. 예를 들어, 이러한 이벤트와 관련된 조치를 이 속도로 제한하거나 비율에 부합할 때까지 지연시킬 수 있다. 또한 적합성을 점검하거나 평균 비율만으로 제한(즉, 평균에서 변동을 제거하는 것)할 때도 사용할 수 있다.

패킷 교환 컴퓨터 네트워크와 통신 네트워크 양쪽의 패킷 교환 컴퓨터 네트워크와 데이터 전송의 트래픽 조절과 형태 모두에서,^{[note 1]} 대역폭과 버스트성에 대한 한계를 정의하기 위해 사용된다(트래픽 흐름의 불균일성 또는 변동의 척도). 또한 네트워크에서 적용되는 대역폭과 버스트리티에 대해 설정한 한계에 부합하는 전송의 타이밍을 결정하는 스케줄링 알고리즘으로도 사용될 수 있다: 네트워크 스케줄러를 참조하십시오.^[1][2][3][4] 누출되는 버킷의 버전인 일반 셀 속도 알고리즘은 사용자-네트워크 인터페이스의 사용/네트워크 매개변수 제어에서 비동기 전송 모드(ATM) 네트워크^[5] 또는 네트워크 간 인터페이스 또는 네트워크를 통해 라우팅된 연결의 과도한 트래픽 수준으로부터 네트워크를 보호하는 것이 권장된다. 일반적인 셀 속도 알고리즘 또는 이와 동등한 것은 네트워크 인터페이스 카드에 의한 전송을 ATM 네트워크(즉, 사용자-네트워크 인터페이스의 사용자측)로 형상화하는 데 사용될 수도 있다. 예를 들어, 네트워크상에서 사용/네트워크 매개변수 제어에 대해 설정된 수준보다 낮은 수준으로 그 연결을 더 제한하기 위한 조치를 취하는 것을 방지하기 위해 네트워크 인터페이스 카드에 의한 전송을 형상화하는 데 사용될 수 있다. 누출 버킷 알고리즘은 누출 버킷 카운터에서도 사용된다. 예를 들어, 결함이나 고장과 같은 무작위 또는 확률적 사건이나 확률적 프로세스의 평균 또는 최고 속도가 정의된 한계를 초과하는 경우를 탐지하기 위해 사용된다.

최소한 누출이 있는 버킷의 일부 구현은 토큰 버킷 알고리즘의 미러 이미지로, 동등한 매개변수가 주어진 경우 동일한 제한에 부합하거나 준수하지 않는 정확히 동일한 이벤트 순서를 결정한다. 그러나 새는 양동이에 대한 적어도 두 가지 서로 다른 묘사가 있어 혼란을 야기할 수 있었다.^[1][2][6]

개요

이 누출되는 버킷 비유를 적용하는 두 가지 다른 방법이 문헌에 설명되어 있다.^[1][2][3][4] 이러한 알고리즘은 두 개의 서로 다른 알고리즘으로 보이는 것을 제공하며, 두 알고리즘 모두 누출되는 버킷 알고리즘이라고 하며 일반적으로 다른 방법을 참조하지 않는다. 이로 인해 새는 버킷 알고리즘이 무엇인지, 그 속성이 무엇인지에 대한 혼동을 초래했다.

유추를 적용하는 한 버전에서 버킷의 아날로그는 트래픽 흐름이나 이벤트의 스케줄링과는 별도로 카운터나 변수다.^[1][3][4] 이 카운터는 트래픽 또는 이벤트가 다음 제한을 준수하는지 확인하는 데만 사용된다. 카운터는 각 패킷이 체크가 이루어지거나 이벤트가 발생하는 지점에 도착할 때 증가하는데, 이는 버킷에 간헐적으로 물을 추가하는 방법과 동일하다. 카운터도 양동이의 물이 새어 나오는 방식과 맞먹는 고정된 속도로 노쇠된다. 그 결과, 카운터의 값은 유추 버킷의 물의 수준을 나타낸다. 패킷이 도착하거나 이벤트가 발생할 때 카운터가 지정된 제한 값 미만으로 유지되는 경우, 즉 버킷이 오버플로되지 않는 경우, 이는 대역폭 및 버스트성 제한 또는 평균 및 피크 속도 이벤트 제한에 대한 적합성을 나타낸다. 그래서 이 버전에서 물의 아날로그는 패킷이나 사건에 의해 운반되고, 도착하거나 발생할 때 버킷에 추가되고, 그리고 나서 새어 나간다. 이 버전은 여기서 새는 버킷을 미터라고 한다.

두 번째 버전에서 버킷의 아날로그는 트래픽 흐름의 대기열이다.^[2] 이 대기열은 그 흐름을 직접 제어하기 위해 사용된다: 패킷은 도착하면서 대기열에 입력되는데, 이는 버킷에 추가되는 물과 같다. 그런 다음 이러한 패킷은 대기열에서 제거된다(선착, 선착순 제공). 예를 들어 버킷에서 물이 새는 것과 동등한 후속 전송을 위해 고정된 속도로. 결과적으로, 대기열이 정비되는 속도는 트래픽의 전진 전송 속도를 직접 제어한다. 따라서 그것은 그것을 확인하는 것보다 순응을 부과하고, 큐가 고정된 속도로 서비스되는 곳(그리고 패킷이 모두 같은 길이인 곳)에서는 결과적인 트래픽 스트림에는 반드시 버스트나 지터가 없다. 그래서 이 버전에서는 교통 자체가 물통을 통과하는 물의 아날로그적인 것이다. 이 비유를 적용하는 버전이 이산형 사건의 비율을 확인하는 데 어떻게 사용될 수 있는지는 명확하지 않다. 이 버전은 여기서 대기열로 새는 버킷이라고 한다.

계량기로 새는 버킷은 토큰 버킷 알고리즘(거울 이미지)과 정확히 동일하다. 즉, 새는 버킷에 물을 추가하는 과정은 준수되는 패킷이 도착할 때 토큰을 제거하는 과정, 새는 버킷에서 물이 새는 과정은 정기적으로 토큰을 추가하는 과정을 정확히 반영한다.s 토큰 버킷으로, 새는 버킷이 넘치지 않는 테스트는 토큰 버킷에 충분한 토큰이 포함되어 있고 '언더플로우'되지 않는 테스트의 거울이다. 따라서, 등가 매개변수가 주어지면, 두 알고리즘은 적합성 또는 부적합성과 동일한 트래픽을 볼 것이다. 줄처럼 새는 양동이는 계량기로 새는 양동이의 특수한 경우로 볼 수 있다.^[6]

미터로

조너선 S. 터너는 누수 버킷 알고리즘의 원래 설명을 인정받아^[7] 다음과 같이 설명하고 있다: "사용자가 패킷을 보낼 때마다 연결로 송신하는 각 사용자와 관련된 카운터가 증가하여 주기적으로 감소한다. 카운터가 증가했을 때 임계값을 초과하면 네트워크는 패킷을 무시한다. 사용자는 카운터가 감소하는 속도(이것은 평균 대역폭을 결정한다)와 임계값(버스트성의 측정치)^[1]을 지정한다." 버킷(카운터와 아날로그)은 패킷을 직접 제어하기 위한 대기열이 아니라 패킷의 적합성을 테스트하기 위한 미터로 사용된다.

본질적으로 동일한 알고리즘의 동일한 미터 버전인 일반 셀 속도 알고리즘에 대한 또 다른 설명은 ITU-T가 권장사항 I.371과 ATM 포럼의 UNI 사양에 제시한다.^[3][4] :"continuous-state게 새는 양동이의 실수를 사용한 내용 시간 단위당의 콘텐트는 1단위의 지속적인 속도와 콘텐츠는 T로 e.으로 증가한다를 내보낸다 유한한 용량 물통으로 간주될 할 수 있을 것은 용어 세포 터너의 description[1]에 패킷에 해당합니다 그 설명은 ITU-T에 의해서 주어진다교류H following cell... 셀 도착 시 버킷의 함량이 한계값 τ보다 작거나 같으면 셀은 준수하고, 그렇지 않으면 셀은 부적합하다. 버킷의 용량(카운터의 상한)은 (T + τ)"^[4]이다. 또한 이 규격은 제한된 용량 때문에 적합성을 시험할 때 버킷의 내용이 한계값보다 크면, 따라서 셀이 부적합하면 버킷은 변경되지 않고 그대로 유지되며, 즉, 버킷이 넘칠 경우 물이 추가되지 않는다고 명시하고 있다.

데이비드 E. 맥디산과 대럴 L. 스포언은 ITU-T/ATM 포럼이 제공한 설명에 대해 논평을 제공한다. 이 내용에서는 "누수 버킷 유추에서는 [ATM] 셀이 실제로 버킷을 통해 흐르지 않으며, 합격 여부 확인만 가능하다"^[6]고 명시한다. 그러나 문헌에 나와 있는 설명에서 드물게 맥디산과 스포언은 "트래픽 쉐이핑의 한 구현은 실제로 버킷을 통해 셀이 흐르게 하는 것이라는 점에 유의하라"^[6]는 식으로 누출되는 버킷 알고리즘을 큐로 언급하기도 한다.

ITU-T 버전의 알고리즘의 작동을 설명하면서, McDysan과 Spohn은 "허구적인 '그렘린'의 대기열에 일반적으로 사용되는 개념"^[6]을 실행한다. 이 그레믈린은 버킷의 레벨을 검사하고 레벨이 한계값보다 높은 경우 조치를 취한다. τ : 치안유지(그림 2)에서, 도착하는 패킷을 떨어뜨리게 하는 트랩 도어를 당겨 버킷에 물이 들어가지 못하게 하고, 형태(그림 3)에서 플랩을 위로 밀어 올려 도착하는 패킷을 지연시키고 디데를 방지한다.양동이의 수위가 τ 이하로 떨어질 때까지 간을 맞춘다.

터너와 ITU-T/ATM 포럼이 제시한 설명의 차이점은 터너의 설명은 교통 치안 유지에 특유한 반면 ITU-T/ATM 포럼은 교통 치안 유지와 교통 형태 형성에 모두 적용 가능하다는 것이다. 또한 터너는 카운터 내용이 패킷 준수에만 영향을 받아야 하며, 이것이 한계를 초과하지 않을 때에만 증가되어야 한다고 명시하지 않는다. 터너는 버킷의 용량이나 카운터의 최대값이 유한하다는 것을 명시적으로 언급하지 않는다. 터너의 설명이 ITU-T와 명확하게 일치하도록 하려면, "카운터가 증가했을 때 임계값을 초과하면, 네트워크는 패킷을 무시한다"는 문구를 "카운터가 증가되었을 때 [ITU-T 설명에서 버킷 깊이, T + τ과 동일한 임계값]을 초과한다면, 네트워크와 같은 것으로 변경해야 할 것이다. 패킷과 카운터가 증가하지 않는다." 즉, ITU-T 설명의 버킷 깊이보다 작거나 같을 때만 증가된다.

터너에 의해 제공된 설명은 카운터가 패킷 준수만으로 영향을 받아야 한다는 것을 명시하지 않지만, 부적합한 패킷을 포함하는 연결을 제한하는 과도한 열성은 문제가 되지 않을 수 있는 교통 치안 기능의 관점에서 제시된다. 실제로 가변 비트 전송률(VBR) 전송과 같은 일부 상황에서, 한 패킷의 손실은 OSI 네트워크 계층 PDU와 같은 상위 계층 메시지 전체를 손상시킬 수 있다. 이 경우 손상된 PDU의 다음 패킷을 모두 폐기하면 불필요한 네트워크 부하가 손실된다. 그러나 순응 테스트에 실패한 패킷이 순응이 다음에 발생할 수 있는 기간에 영향을 미치는 것은, 즉, 순응을 위해 후속 패킷을 테스트하는 행위가 현재 순응 대기 중인 패킷이 대기해야 하는 시간을 변화시키는 경우, 패킷이 순응 테스트를 통과하지 못하는 것은 전적으로 허용되지 않을 것이다. 이는 후속적으로 부적합한 패킷이 수면을 상승시키고 따라서 준수 대기 중인 패킷이 더 오래 기다리게 하기 때문에, 부적합한 패킷에서 나온 물을 버킷에 추가한다면 정확히 일어날 일이다.

터너도 ITU-T도 가변 길이 패킷의 문제는 다루지 않는다. 그러나 ITU-T에 따른 설명은 고정 길이 패킷인 ATM 셀에 대한 것으로 터너는 특별히 가변 길이 패킷을 배제하지 않는다. 따라서, 두 경우 모두, 적합한 패킷에 대해 버킷 콘텐츠나 카운터가 증가되는 양이 패킷 길이에 비례하는 경우, 그들은 둘 다 길이를 설명하며 알고리즘이 패킷 속도를 제한하기 보다는 트래픽의 대역폭을 명시적으로 제한할 수 있게 된다. 예를 들어, 더 짧은 패킷은 버킷에 더 적게 추가되며, 따라서 더 작은 간격으로 도착할 수 있는 반면, 더 긴 패킷은 더 많은 패킷을 추가할 수 있고 따라서 순응하기 위해 비례적으로 더 큰 간격으로 분리되어야 한다.

운영개념

교통 치안 또는 교통 형태 형성에 사용할 수 있는 계량기로서 Leaky Buket Algorithm의 운용 개념에 대한 설명은 다음과 같이 명시될 수 있다.

• 각 가상 연결 또는 사용자와 관련된 고정 용량 버킷은 고정 속도로 누출된다.

• 양동이가 비어 있으면 새는 것을 멈춘다.

• 패킷이 순응하려면 버킷에 특정 양의 물을 추가할 수 있어야 한다. 적합한 패킷에 의해 추가된 특정 양은 모든 패킷에 대해 같거나 패킷 길이에 비례할 수 있다.

• 만약 이 정도의 물이 버킷의 용량을 초과하게 된다면, 포켓이 맞지 않고 버킷의 물은 변하지 않은 채로 남게 된다.

사용하다

계량기로서 새는 버킷은 교통 형태나 교통 치안 유지에 사용될 수 있다. 예를 들어 ATM 네트워크에서는 일반 셀 속도 알고리즘의 형태로 VC나 VP에 대해 셀이 도착할 수 있는 속도와 최대 지터 또는 도착 간 간격의 변동을 지정된 한계와 가상 채널(VC) 또는 가상 경로(VP)에서 트래픽의 대역폭과 버스트성을 비교하는 데 사용된다. 교통정리를 할 때, 이러한 한계(비적합한 셀)에 부합하지 않는 셀은 폐기(드롭)되거나 우선순위를 감소시킬 수 있다(혼잡 시 하류 교통관리 기능이 저하되는 경우). 교통 형태에서, 세포는 그들이 순응할 때까지 지연된다. UPC/NPC에서는 초과되거나 과도하게 폭발적인 트래픽으로부터 네트워크를 보호하기 위해 트래픽 감시 및 트래픽 형성이 일반적으로 사용된다. 대역폭 관리와 혼잡 방지를 참조하십시오. 트래픽 쉐이핑은 전송이 대역폭이나 지터 제한을 초과하고 네트워크의 트래픽 관리 기능에 의해 폐기되는 것을 방지하기 위해 일반적으로 호스트의 네트워크 인터페이스에서 사용된다. (스케줄링(컴퓨팅) 및 네트워크 스케줄러를 참조하십시오.)

누설되는 버킷 알고리즘을 계량기로써도 누설되는 버킷 카운터에 사용하여 무작위 또는 확률적 공정의 비율을 측정할 수 있다. Leaky 버킷 카운터는 이벤트의 평균 또는 피크 속도가 일부 허용 가능한 배경 수준, 즉 버킷이 오버플로되는 경우를 감지하는 데 사용할 수 있다.^[8] 그러나 오버플로를 야기하지 않는 이벤트, 즉 충분히 낮은 비율을 가지고 있고 시간이 지남에 따라 잘 분포되어 있는 이벤트는 무시할 수 있다. 예를 들어, 이러한 누출이 있는 버킷 카운터를 사용하여 수정 가능한 메모리 오류가 갑자기 터지거나 평균 속도가 점진적이지만 유의하게 증가했을 때를 감지할 수 있으며, 이는 곧 고장이 발생할 수 있음을 나타낼 ^[9]수 있다.

새는 버킷 카운터에서 새는 버킷 알고리즘을 사용하는 것은 미터기로 사용한다는 점에서 트래픽 관리에서 사용하는 것과 유사하다. 기본적으로 이벤트는 설명의 패킷을 대체하며, 각 이벤트로 인해 버킷에 많은 양의 물이 추가된다. 이벤트의 결과로 버킷이 오버플로되면 이벤트는 제한 초과 이벤트와 관련된 작업을 트리거해야 한다. 일부 implementations[8]에서 최대 값은 카운터 볼지에 대해서 어떤 명확한 제한, 한번은 카운터가 문턱을 넘어섰다 하더라도, 그것은 이전 상태로 전달되고 있던, 못은 기간 크게 배출을 구간의 동등한 것을 넘은까지 돌아오지 않을 것을 의미한다 터너의 description,[1]에 필적하는 것 같다.y 그렇지 않으면 어떤 일이 일어날 것인가에 따라 증가한다. 그러나 다른 구현에서는 카운터가 오버플로되는 동안 카운터를 증가시키지 않을 수 있으므로, 다음과 같은 이벤트가 일치하는지 여부를 정확하게 판단할 수 있다.

매개변수

누출이 많은 버킷 알고리즘의 경우, 트래픽의 한계는 출력의 대역폭과 버스트가 될 수 있다.^{[3][4][note 2]}

연결에 대한 대역폭 제한과 버스트성 제한은 트래픽 계약에 명시될 수 있다. 대역폭 제한은 패킷 또는 프레임 속도, 바이트 또는 비트 전송률 또는 패킷 간의 방출 간격으로 지정할 수 있다. 버스트성에 대한 한계는 지터 또는 지연 변동 공차 또는 최대 버스트 크기(MBS)로 지정할 수 있다.

누출 버킷 알고리즘의 여러 인스턴스를 사용하여 연결에 여러 계약 매개변수 집합을 동시에 적용할 수 있으며, 각각 대역폭과 버스트성 한계가 필요할 수 있다: 듀얼 누출 버킷 컨트롤러를 참조하십시오.

방출 간격

버킷 누출 속도가 대역폭 제한을 결정하는데, 이를 터너에^[1] 의한 평균 속도라고 하고, 그 반을 ITU-T에 의한 방출 간격이라고 한다. 패킷이 고정된 길이를 갖는 이 간격이 무엇인지 설명하기가 가장 쉽다. 따라서 이 설명의 첫 번째 부분은 이를 가정하며, 가변 패킷 길이의 의미는 별도로 고려된다.

이전 트래픽에 의해 정확히 상단으로 채워지는 버킷을 고려하십시오. 즉, 최대 허용 버스트가 이미 발생한 경우, 즉 패킷 또는 셀의 최대 수가 대역폭 및 지터 제한을 여전히 준수할 수 있는 최소 시간 내에 도달한 경우. 다음 패킷이 순응할 수 있을 때까지의 최소 간격은 버킷이 패킷에 의해 전달되는 물의 양을 정확히 누설하는데 걸리는 시간이며, 만약 패킷이 테스트되고 그 시간에 순응한다면, 이것은 정확히 한 번 더 버킷을 채울 것이다. 따라서 버킷이 채워지면 패킷이 준수할 수 있는 최대 속도는 각 패킷 사이의 이 간격과 일치한다.

터너는^[1] 이 비율을 평균이라고 말하는데, 그 반대가 평균 간격임을 암시한다. 그러나 평균 비율과 구간이 무엇인지에 대해서는 다소 모호한 부분이 있다. 패킷은 어떤 낮은 속도로도 도착할 수 있기 때문에, 이것은 고정된 값이 아니라 상한이기 때문에 기껏해야 평균 속도의 최대값이라고 할 수 있다. 또한, 최대 버스트가 발생하는 시간 동안 패킷은 더 작은 간격으로 도착할 수 있으며 따라서 이보다 더 높은 비율로 도착할 수 있다. 따라서 무한대보다 작은 기간에 대해 실제 평균 속도는 이보다 클 수 있으며(그러나 반드시 그렇지는 않다) 평균 간격은 방출 간격보다 작을 수 있다(그러나 반드시 그렇지는 않다). 따라서, 이러한 모호성 때문에, 배출 간격은 다음에 사용된다. 그러나 장기 평균 구간이 취할 수 있는 최소값은 배출 구간인 경향이 있는 것은 사실이다.

버킷에 추가된 양이 패킷 길이에 비례하는 가변 길이 패킷의 경우, 패킷을 준수할 수 있는 최대 속도는 패킷이 패킷 길이에 비례하는 경우 버킷이 패킷 길이에 따라 완전히 누출되어야 하는 양이다. 버킷을 채운 이전 패킷과 그것 사이의 간격 따라서 가변 길이 패킷에 대해 특정 방출 간격을 지정할 수 없으며 대역폭 제한은 초당 비트 또는 바이트 단위로 명시적으로 지정해야 한다.

지연 변동 공차

패킷의 길이가 고정된 경우 이 허용오차가 무엇인지 설명하는 것이 가장 쉽다. 따라서 이 설명의 첫 번째 부분은 이를 가정하며, 가변 패킷 길이의 의미는 별도로 고려된다.

ITU-T는 버킷 용량보다 작은 한계값인 τ을 T(각 준수 셀에 대해 버킷 함량이 증가하는 양)로 정의하여 버킷의 용량은 T + τ이다. 이 제한 값은 패킷이 정확히 방출 간격을 두고 도착할 때 패킷이 일반적으로 예상할 수 있는 것보다 얼마나 더 빨리 도착할 수 있는지를 명시한다.

다음과 같은 상황을 상상해보라: 버킷이 초당 1단위의 물에서 새기 때문에 한계값인 τ과 패킷에 의해 추가된 물의 양이 효과적으로 초 단위로 된다. 이 버킷은 빈 채로 시작되기 때문에, 패킷이 버킷에 도착할 때, 물 T를 추가하여 버킷을 제대로 채우지 못하며, 버킷은 현재 용량보다 ³ 낮다. 따라서 다음 패킷이 도착할 때 버킷은 T – τ로만 배수하면 이것이 순응할 수 있다. 따라서 이 두 패킷 사이의 간격은 T보다 τ만큼 적을 수 있다.

이는 순차적으로 여러 패킷으로 확장된다. 다음 사항을 상상해 보십시오. 버킷은 다시 빈 상태로 시작되므로, 먼저 도착하는 패킷은 반드시 일치해야 한다. 그런 다음 버킷은 순응 가능한 최소 시간 내에 다수의 패킷 N이 도착한 후에 정확히 가득 차게 된다. 마지막(Nth) 패킷이 순응하려면 버킷이 이전 N – 1 패킷(((N – 1) * T 초')에서 충분히 물이 새야 이 시간에 정확히 한계값 τ에 도달할 수 있다. 따라서 누수된 물은 (N – 1)T – leak인데, 누수가 초당 1단위이기 때문에 누수에 정확히 (N – 1)T – τ 초가 걸렸다. 따라서 모든 N 패킷이 도착하고 준수할 수 있는 가장 짧은 시간은 (N – 1)T – τ 초이며, 이는 패킷이 정확한 배출 간격에 도달했을 때 걸린 시간보다 정확히 τ이 적다.

그러나 패킷은 이전 패킷에 의해 버킷이 채워지지 않는 T 미만의 간격으로만 도착할 수 있다. 그렇다면 다음 패킷이 준수하기 전에 버킷이 전체 T만큼 배수된 것이어야 한다. 따라서 일단 이 허용오차가 T보다 작은 패킷에 의해 사용되면, 후속 프레임은 T보다 작은 간격으로 도착해야 한다. 그러나 그들은 더 큰 간격으로 도착할 수 있다. 이때 양동이는 그들이 채우지 않을 것이다. 이 경우, 패킷은 허용오차가 다시 사용될 때까지 T보다 작은 간격으로 도착할 수 있다. 그러나, 양동이 비어 있을 때 새는 것을 멈추기 때문에, T보다 큰 간격에 의해 얼마나 많은 허용오차가 발생할 수 있는가에 대한 제한(제한)이 항상 존재하지만, T보다 훨씬 크거나 많은 허용오차가 있을 수 있다.

한계값 τ은 패킷이 예상한 것보다 얼마나 빨리 도착할 수 있는가를 정의하기 때문에, 적합성 시험이 이루어지고 있는 시점(패킷이 지터 없이 생성된다고 가정)까지의 최대 지연과 최소 지연 사이의 차이에 대한 제한이다. 따라서 ATM에서 이 매개변수에 대해 셀 지연 변동 허용오차(CDVt)라는 용어를 사용한다.

예를 들어, 지연 변동의 가능한 원천은 스위치 출력에서 다수의 연결(패킷 스트림)이 함께 멀티플렉싱되는 곳이다. 이러한 연결의 대역폭 합계가 출력값의 합보다 적다고 가정하면, 결국 도달하는 모든 패킷은 전송될 수 있다. 그러나, 예를 들어 스위치의 다른 입력에 도달하기 때문에 도착이 독립적일 경우, 여러 개가 동시에 또는 거의 동시에 도착할 수 있다. 출력은 한 번에 한 패킷만 전송할 수 있기 때문에 다른 패킷은 전송될 차례가 될 때까지 버퍼에 대기해야 한다. 그러면 이 버퍼는 입력에 도달한 패킷과 출력에 의해 전송되는 패킷 사이에 추가적인 지연을 도입하며, 이 지연은 버퍼에 이미 대기 중인 다른 패킷의 수에 따라 달라진다. 여러 패킷의 릴리스 시간이 같거나 유사한 경우 호스트 출력(NIC)에서도 유사한 상황이 발생할 수 있으며, 이러한 지연은 일반적으로 가상 출력 버퍼의 지연으로 모델링될 수 있다.

주어진 패킷에 의해 추가된 물의 양이 그 길이에 비례하는 가변 길이 패킷의 경우, τ은 패킷 크기에 따라 달라지기 때문에 패킷이 도착했을 때 버킷이 얼마나 가득 찰 수 있는가에 대한 한계로 볼 수 없다. 그러나 이 수준에서 비워지는 데 걸리는 시간은 여전히 패킷이 대역폭 한도로 전송될 때 패킷이 예상보다 얼마나 빨리 도착할 수 있는지이다. 따라서, 적합성 시험을 적용하고 있는 시점까지의 전송 지연의 최대 변동이며, 따라서 최대 지연 변동에 대한 허용오차는 여전히 허용된다.

최대 버스트 크기

한계값 또는 지연 변동 허용오차는 또한 버스트에 도착할 수 있는 패킷의 수를 제어하는데, 이는 단일 패킷에 필요한 용량에 대한 버킷의 과도한 깊이에 의해 결정된다. 따라서 MBS도 버스트니스나 지터의 척도로서 버스트성을 MBS로 지정하고 이것으로부터 한계값 τ을 도출하거나 지터/지연 변동 허용오차/한계값으로 지정하여 MBS를 도출하는 것이 가능하다.

패킷 버스트 또는 뭉치는 방출 간격 T에 의해 결정되는 것보다 더 높은 속도로 도착할 수 있다. 이는 버스트의 패킷이 연속적으로 도착할 때 물리적 계층 연결의 회선 속도일 수 있다. 그러나 ATM에서와 마찬가지로 공차는 더 낮은 비율에 적용될 수 있는데, 이 경우 지속 가능한 셀 속도(SCR)와 패킷(셀)의 버스트는 더 높은 비율로 도달하지만, 이 경우 최대 셀 속도(PCR)는 물리적 계층의 라인 속도보다 작다. 그러면 MBS는 상위 계층 패킷을 전송하는 데 필요한 셀의 수가 될 수 있다(분할 및 재조립 참조). 여기서 패킷은 SCR에 의해 결정되는 최대 대역폭으로 전송되고 패킷 내의 셀은 PCR에서 전송된다. 따라서 패킷의 마지막 셀과 패킷 자체는 상당한 얼을 얻을 수 있다.셀이 (MBS-1)/SCR이 아닌 SCR: 전송 지속시간 = (MBS-1)/PCR로 전송되는 경우보다 더 중요하다. PCR에서의 이러한 폭발은 SCR에서의 전송보다 스위치 출력 버퍼와 같은 공유 자원에 현저하게 높은 부하를 가하므로 버퍼 오버플로 및 네트워크 정체를 야기할 가능성이 더 높다. 단, 한계값인 τ으로_SCR SCR에서 전송하는 것보다 이러한 자원에 대한 부하가 적어서 회선 속도로 MBS 셀을 전송하고 연속적으로 도착하게 한다.

If the limit value is large enough, then several packets can arrive in a burst and still conform: if the bucket starts from empty, the first packet to arrive will add T, but if, by the time the next packet arrives, the contents is below τ, this will also conform. Assuming that each packet takes δ to arrive, then if τ (expressed as the time it takes the bucket to empty from the limit value) is equal to or greater than the emission interval less the minimum interarrival time, T – δ, the second packet will conform even if it arrives as a burst with the first. Similarly, if τ is equal to or greater than (T – δ) × 2, then 3 packets can arrive in a burst, etc.

The maximum size of this burst, M, can be calculated from the emission interval, T; the maximum jitter tolerance, τ; and the time taken to transmit/receive a packet, δ, as follows:^[3]

${\displaystyle M=\left\lfloor 1+{\frac {\tau }{T-\delta }}\right\rfloor }$

Equally, the minimum value of jitter tolerance τ that gives a specific MBS can be calculated from the MBS as follows:^[3]

${\displaystyle \tau =\left(M-1\right)\left(T-\delta \right)}$

In the case of ATM, where technically MBS only relates to the SCR tolerance, in the above equation the time it takes each packet to arrive, δ, is the emission interval for cells at the PCR T_PCR, and the emission interval, T, is the emission interval for the SCR T_SCR. Where MBS is to be the number of cells required to transport a segmented packet, the limit value in the above, τ, should be that for the SCR τ_SCR. However, at the UNI or an NNI, where cells at the PCR will have been subjected to delay variation, it should be the limit value for the SCR plus that for the PCR τ_SCR + τ_PCR.

For variable length packets, the maximum burst size will depend on the lengths of the packets in the burst and there is no single value for the maximum burst size. However, it is possible to specify the total burst length in bytes, from the byte rate of the input stream, the equivalent byte rate of the leak, and the bucket depth.

토큰 버킷 알고리즘과 비교

누출이 있는 버킷 알고리즘은 토큰 버킷 알고리즘과 대비되기도 한다. 그러나 계량기로서 누출이 있는 버킷에 대한 위의 작동 개념을 토큰 버킷 알고리즘과 직접 비교할 수 있으며, 이 알고리즘에 대한 설명은 다음과 같다.

• 토큰은 매 1/r초마다 버킷에 추가된다.

• 그 버킷은 가장 많은 b 토큰을 담을 수 있다. 버킷이 가득 찼을 때 토큰이 도착하면 폐기된다.

• "n" 바이트의 패킷(네트워크 계층 PDU)[sic]^{[note 1]}이 도착하면, 버킷에서 토큰이 n개 제거되고 패킷이 네트워크로 전송된다.

• 사용할 수 있는 토큰이 n개 미만일 경우 버킷에서 토큰이 제거되지 않으며, 패킷은 부적합한 것으로 간주된다.

이는 위에서 반복한 조작의 개념과 비교할 수 있다.

• 각 가상 연결 또는 사용자와 관련된 고정 용량 버킷은 고정 속도로 누출된다.

• 양동이가 비어 있으면 새는 것을 멈춘다.

• 패킷이 순응하려면 버킷에 특정 양의 물을 추가할 수 있어야 한다. 적합한 패킷에 의해 추가된 특정 양은 모든 패킷에 대해 같거나 패킷 길이에 비례할 수 있다.

• 만약 이 정도의 물이 버킷의 용량을 초과하게 된다면, 포켓이 맞지 않고 버킷의 물은 변하지 않은 채로 남게 된다.

볼 수 있듯이, 이 두 가지 설명은 기본적으로 서로에 대한 미러링 이미지인데, 하나는 정기적으로 버킷에 무언가를 추가하고, 다른 하나는 패킷을 0의 한계까지 준수하기 위해 무언가를 빼앗아 버킷 용량의 한계까지 준수하기 위해 정기적으로 패킷을 추가한다는 것이다. 그렇다면, 적합한 패킷에 토큰을 추가하고 일정한 비율로 제거하는 구현은 누출되는 버킷이나 토큰 버킷의 구현인가? 마찬가지로, 적합한 패킷을 위해 물을 제거하고 고정된 속도로 물을 추가하는 구현에 사용되는 알고리즘은 무엇인가? 사실 두 가지 모두 사실상 동일하다. 즉, 누출이 많은 버킷과 토큰 버킷의 구현은 서로 다르게 기술된 동일한 기본 알고리즘이기 때문이다. 따라서 동일한 매개변수를 가진 두 알고리즘이 준수 또는 비적합성과 정확히 동일한 패킷을 볼 수 있는 이유가 설명된다. 따라서 누출 및 토큰 버킷 알고리즘의 구현 속성 및 성능의 차이는 전적으로 구현의 차이에서 비롯된다. 즉, 기본 알고리즘의 차이에서 기인하지 않는다.

The points to note are that the leaky bucket algorithm, when used as a meter, can allow a conforming output packet stream with jitter or burstiness, can be used in traffic policing as well as shaping, and can be implemented for variable length packets.

As a queue

The leaky bucket as a queue is essentially a way of describing a simple FIFO buffer or queue that is serviced at a fixed rate to remove burstiness or jitter. A description of it is given by Andrew S. Tanenbaum, in (an older version of) his book Computer Networks as "The leaky bucket consists of a finite queue. When a packet arrives, if there is room on the queue it is appended to the queue; otherwise it is discarded. At every clock tick one packet is transmitted (unless the queue is empty)".^[2] An implementation of the leaky bucket as a queue is therefore always a form of traffic shaping function.

As can be seen this implementation is restricted in that the packets are only ever transmitted at a fixed rate. To underline this, Tanenbaum also states that "The leaky bucket algorithm enforces a rigid output pattern at the average rate, no matter how bursty the [input] traffic is".^[10] However, this assertion is only strictly true as long as the queue does not become empty: if the average arrival rate is less than the rate of clock ticks, or if the input is sufficiently bursty that the losses bring the rate of the remainder below the clock tick rate (i.e. gaps in the input stream are long enough and the queue is small enough that it can become empty), there will be gaps in the output stream.

A further restriction is that the leaky bucket as a queue traffic shaping function only transmits packets on the ticks; hence, if it is used within a network, equivalent to UPC and NPC, it also imposes a fixed phase on the onward transmission of packets. Whereas, when using a leaky bucket meter to control onward transmission, a packet is transmitted as soon as it conforms, i.e. relative to the previous one or, if it already conforms, its arrival time; not according to some arbitrary local clock. Perversely, in the context of the transfer delay, this imposition of a fixed phase that may, over time, differ from that of an otherwise conforming input packet stream, constitutes a delay variation and hence a jitter. Jitter caused in this particular way could only be observed where the delay is measured as the transit time between two separate measurement points, one either side of the leaky bucket as a queue shaping function. However, in the context of real-time data transmissions, it is this end-to-end delay that determines the latency of received data. Hence, the leaky bucket as a queue is unsuitable for traffic shaping real-time transmissions.

누출이 많은 버킷 알고리즘을 큐로 사용하여 가변 길이 패킷을 제한하는 것은 고정 길이 패킷보다 훨씬 더 복잡하다. Tanenbaum은 가변 길이 패킷에 대한 "바이트 카운팅" 누출 버킷에 대한 설명을 다음과 같이 제공한다: "각 눈금에서 카운터는 n으로 초기화된다. 큐의 첫 번째 패킷이 카운터의 현재 값보다 적은 바이트를 갖는 경우 전송되며, 카운터는 그 바이트 수로 감소한다. 카운터가 충분히 높기만 하면 추가 패킷도 보낼 수 있다. 카운터가 큐에 있는 다음 패킷의 길이 아래로 떨어지면 다음 틱까지 전송이 중지되며, 이때 잔여 바이트 수가 [n]으로 재설정되고 흐름이 계속될 수 있다."^[2] 고정 길이 패킷의 버전과 마찬가지로, 이 구현은 전송 단계에 강한 영향을 미치며, 가변적인 엔드투엔드 지연을 초래하고 실시간 트래픽 형성에 적합하지 않다.

사용하다

대기열로 새는 버킷은 출력에 지터가 없는 지정된 대역폭으로 트래픽을 조절하는 데만 사용할 수 있다.^[10] 대역폭 관리의 일부로 네트워크 내에서 사용될 수 있지만, 호스트의 네트워크 인터페이스에서 트래픽 형성에 더 적합하다. Nginx의 ngx_http_limit_conn_module 모듈에서 Leaky 버킷 알고리즘을 사용하여 단일 IP 주소에서 발생하는 동시 연결 수를 제한한다.^[11]

매개변수

대기열로 누출되는 버킷 알고리즘의 경우, 이 알고리즘에 대해 정의된 제한은 출력 대역폭뿐입니다.^{[10][note 2]}

연결에 대한 대역폭 한계는 트래픽 계약에 명시될 수 있다. 대역폭 제한은 패킷 또는 프레임 속도, 바이트 또는 비트 전송률 또는 패킷 간의 방출 간격으로 지정할 수 있다.

비효율성

누출 버킷을 대기열로 구현하는 것은 가용 네트워크 자원을 효율적으로 사용하지 않는다. 일정한 간격으로만 패킷을 전송하기 때문에 트래픽 볼륨이 매우 낮고 네트워크 자원의 많은 부분(특히 대역폭)이 사용되지 않는 경우가 많을 것이다. 그러므로 누출 버킷 구현에는 개별 흐름이 포트 속도로 폭발할 수 있도록 대기열로서 메커니즘이 존재하지 않으며, 네트워크에 자원 경합이 일어나지 않을 때 네트워크 자원을 효과적으로 소비한다. 그러나 토큰 버킷과 누출 버킷을 미터처럼 구현하면 출력 트래픽 흐름이 버스트 특성을 가질 수 있다.

Comparison between the two versions

Analysis of the two versions of the leaky bucket algorithm shows that the version as a queue is a special case of the version as a meter.

Imagine a traffic shaping function for fixed length packets that is implemented using a fixed length queue, forming a delay element, which is serviced using a leaky bucket as a meter. Imagine also that the bucket in this meter has a depth equal to the amount added by a packet, i.e. has a limit value, τ, of zero. However, the conformance test is only performed at intervals of the emission interval, when the packet at the head of the queue is transmitted and its water is added. This water then leaks away during the next emission interval (or is removed just prior to performing the next conformance test), allowing the next packet to conform then or at some subsequent emission interval. The service function can also be viewed in terms of a token bucket with the same depth, where enough tokens for one packet are added (if the bucket is not full) at the emission intervals. This implementation will then receive packets with a bursty arrival pattern (limited by the queue depth) and transmit them on at intervals that are always exact (integral) multiples of the emission interval.

However, the implementation of the leaky bucket as a meter (or token bucket) in a traffic shaping function described above is an exact equivalent to the description of the leaky bucket as a queue:^[2] the delay element of the meter version is the bucket of the queue version; the bucket of the meter version is the process that services the queue, and the leak is such that the emission interval is the same as the tick interval. Therefore for fixed length packets, the implementation of the leaky bucket as a queue is of a special case of a traffic shaping function using a leaky bucket (or token bucket) as a meter in which the limit value, τ, is zero and the process of testing conformance is performed at the lowest possible rate.

The leaky bucket as a queue for variable packet lengths can also be described as equivalent to a special case of the leaky bucket as a meter. The suggested implementation^[2] can, like the fixed length implementation, be seen as traffic shaping function in which the queue is a delay element, rather than the bucket, and the function that services the queue is, in this case, explicitly given as a token bucket: it is decremented for conforming packets and incremented at a fixed rate. Hence, as the leaky bucket as a meter and token bucket are equivalent, the leaky bucket as a queue for variable packet lengths is also a special case of a traffic shaping function using a leaky bucket (or token bucket) as a meter.

There is an interesting consequence of seeing the leaky bucket as a queue for variable packet lengths as a specific implementation of the token bucket or leaky bucket as a meter in traffic shaping. This is that the bucket of the meter has a depth, n, and, as is always the case with the token bucket, this depth determines the burstiness of the output traffic (perhaps in relation to the average or minimum number of tokens required by the packets). Hence, it is possible to quantify the burstiness of the output of this "byte counting" leaky bucket as a meter, unless all packets are of the maximum length when it becomes pointless. However, this ability to define a burstiness for the output is in direct contradiction to the statement that the leaky bucket (as a queue) necessarily gives an output with a rigid rate, no matter how bursty the input.

See also

• Generic cell rate algorithm
• UPC and NPC
• Traffic contract
• Token bucket
• Fluid queue

Notes

References