토큰 버킷

토큰 버킷은 패킷 교환 네트워크 및 통신 네트워크에서 사용되는 알고리즘입니다.패킷 형식의 데이터 전송이 대역폭 및 버스트성의 정의된 제한(트래픽 흐름의 불균등 또는 변동의 척도)에 준거하고 있는 것을 체크하기 위해서 사용할 수 있습니다.대역폭 및 버스트성에 대해 설정된 제한에 적합한 전송 타이밍을 결정하기 위한 스케줄링 알고리즘으로도 사용할 수 있습니다.네트워크 스케줄러를 참조해 주세요.

개요

토큰 버킷알고리즘은 보통 바이트 단위 또는 미리 정해진 크기의 단일 패킷을 나타내는 토큰이 고정 환율로 추가되는 고정 용량 버킷의 유추에 기초하고 있습니다.패킷이 정의된 제한에 준거하고 있는지 여부를 체크하는 경우 버킷에 충분한 토큰이 포함되어 있는지 여부가 검사됩니다.이 경우, 예를 들면 바이트 단위의 패킷 길이와 같은 적절한 수의 토큰이 삭제되고("캐시인") 패킷이 예를 들어 전송을 위해 전달됩니다.버킷에 토큰이 부족하여 버킷의 내용이 변경되지 않으면 패킷은 적합하지 않습니다.부적합 패킷은 다양한 방법으로 처리할 수 있습니다.

드롭될 수 있습니다.
버킷에 충분한 토큰이 축적되면 후속 전송을 위해 큐에 넣을 수 있습니다.
이러한 패킷은 송신될 가능성이 있습니다만, 적합하지 않은 마크가 붙어 있을 가능성이 있습니다.네트워크에 과부하가 걸렸을 경우, 그 후에 드롭 될 가능성이 있습니다.

따라서 적합 흐름은 토큰이 버킷에 추가되는 속도까지의 평균 레이트를 가진 트래픽을 포함할 수 있으며 버킷의 깊이에 따라 버스트성이 결정됩니다.이 버스트성은 지터 허용치, 즉 패킷이 평균 환율 제한에서 예상되는 것보다 얼마나 빨리(예를 들어 도착 또는 전송), 또는 버스트 허용치 또는 최대 버스트사이즈, 즉 일정 기간 동안 평균 트래픽레벨보다 얼마나 더 많은 지터 허용치 또는 최대 버스트 허용치 또는 최대 버스트사이즈.

알고리즘.

토큰 버킷알고리즘은 개념적으로 다음과 같이 이해할 수 있습니다.

토큰은 1 $\displaystyle$ 1/ $r초마$ 다 $1/r$ 버킷에 추가됩니다.
버킷에는 $b개의$ 토큰을 저장할 수 있습니다.버킷이 꽉 찼을 때 토큰이 도착하면 토큰은 폐기됩니다.
n바이트의 패킷(네트워크층 PDU)이 도착하면
- 버킷에 적어도n개의 토큰이 있는 경우 버킷에서n개의 토큰이 삭제되어 패킷이 네트워크로 송신됩니다.
- 사용 가능한 토큰이n개 미만일 경우 버킷에서 토큰은 삭제되지 않으며 패킷은 비일관성으로 간주됩니다.

바리에이션

1 $/$ \ $displaystyle$ 1/ $r초마$ 다 $1/r$ 버킷에 단일 토큰을 $1/r$ 하는 데 필요한 클럭 해상도가 부족한 플랫폼에서의 이 알고리즘의 구현자는 대체 공식을 고려할 수 있습니다.S 밀리초마다 토큰버킷을 갱신할 수 있는 경우, S 밀리초마다 추가하는 토큰의 수 $(r*S)/1000$ ( $(r*S)/1000$ S ) $/$ $(r*S)/1000$ { { $displaystyle ( r$ * $S$ ) / $1000$ } 。

특성.

평균 환율

장기적으로 보면 적합 패킷의 출력은 토큰 레이트 $(r\displaystyle$ r $r$ 에 의해 제한됩니다.

버스트 사이즈

$(\displaystyle$ M $)$ 을 $M$ 바이트/초 단위로 최대 전송 레이트로 합니다.

$T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ 으로 r $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ < $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ 의 경우 $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ { $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ / ( $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ - $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ ) 。{ $displaystyle$ T _ { \ $text$ { $max$ } = $subbegin$ { $cases$ } b / ( M - r $)&$ { \ $text$ { $if }r$ < $M$ \ \ \ \ $infty$ & { \ $text$ { } } $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ $m$ m m m m m m m m m m m m m m m m m m m m m m m m m m 、 { \ \ \ \ \\ \ $text$ { \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \

$B_{\text{max}}=T_{\text{max}}*M$ 최대 버스트 사이즈는 B max $=$ $B_{\text{max}}=T_{\text{max}}*M$ $B_{\text{max}}=T_{\text{max}}*M$ $B_{\text{max}}=T_{\text{max}}*M$ M {\ $displaystyle B_{\text{max$ }}= $T_{\text{max}}*M}$

사용하다

토큰 버킷은 트래픽쉐이핑 또는 트래픽폴리싱 중 하나로 사용할 수 있습니다.트래픽 폴리싱에서는 부적합 패킷이 폐기(폐기)되거나 priority가 저하될 수 있습니다(congestion가 발생했을 경우 다운스트림트래픽 관리 기능이 폐기됩니다).트래픽 쉐이핑에서는 패킷이 적합할 때까지 지연됩니다.트래픽 폴리싱과 트래픽쉐이핑은 일반적으로 과잉 또는 과잉 버스트트래픽으로부터 네트워크를 보호하기 위해 사용됩니다.「대역폭 관리 및 폭주 회피」를 참조해 주세요.트래픽 쉐이핑은, 네트워크내의 트래픽 관리 기능에 의해서 전송이 파기되는 것을 막기 위해서, 호스트의 네트워크인터페이스에서 일반적으로 사용됩니다.

누출 버킷과의 비교

토큰 버킷알고리즘은 ^[1]^[2]^[3]^[4]매뉴얼에 기재되어 있는2가지 버전의 누출 버킷알고리즘 중 하나에 직접 비교가 됩니다.이와 동등한 버전의 누출 버킷은 관련 Wikipedia 페이지에서 누출 버킷 알고리즘(미터)으로 설명되어 있습니다.이것은 토큰 버킷의 미러 이미지입니다.이러한 이미지에서는 토큰버킷 알고리즘의 적합 패킷에 의해 삭제된 토큰과 동등한 유체가 유한 용량버킷에 추가됩니다.이러한 유체는 일정 속도로 배출됩니다.이는 토큰이 고정 속도로 추가되는 프로세스와 동일합니다.

단, 관련 Wikipedia 페이지에서 큐로서의 누출 버킷알고리즘이라고 기술되어 있는 누출 버킷알고리즘의 ^[2]다른 버전이 있습니다.이는 누출 버킷의 특수한 경우로 미터로서 버킷을 통과하는 적합 패킷으로 설명할 수 있습니다.따라서 큐로서의 리크 버킷은 트래픽쉐이핑에만 적용 가능하며 일반적으로 출력 패킷스트림의 버스트성(지터 프리)을 허용하지 않습니다.따라서 토큰버킷 알고리즘과는 크게 다릅니다.

이 두 가지 버전의 누출 버킷알고리즘은 모두 같은 이름으로 매뉴얼에 기재되어 있습니다.이로 인해 그 알고리즘의 속성과 토큰버킷 알고리즘과의 비교에 상당한 혼란이 발생하고 있습니다.단, 기본적으로 2개의 알고리즘은 동일하며 올바르게 구현되어 같은 파라미터가 주어져 있는 경우 적합 및 부적합 패킷이 정확히 일치한다고 간주됩니다.

계층형 토큰버킷

계층형 토큰버킷(HTB)은 Linux의 ^[5]Class-Based Queueing(CBQ; 클래스 기반 큐잉) 큐잉 규율을 대체하는 고속 기능입니다.제한된 클라이언트가 총 대역폭을 포화시키지 않도록 클라이언트의 다운로드/업로드 속도를 제한하면 유용합니다.

개념적으로 HTB는 계층에 배열된 임의의 수의 토큰버킷입니다임의의 디바이스의 프라이머리 출력 큐잉 방식(qdisc)은 루트 qdisc라고 불립니다.루트 qdisc에는 클래스가 1개 포함됩니다.이 단일 HTB 클래스는 레이트와 ceil이라는2개의 파라미터로 설정됩니다.이러한 값은 최상위 클래스에서 동일해야 하며 링크에서 사용 가능한 총 대역폭을 나타냅니다.

HTB에서 rate는 특정 클래스에서 사용할 수 있는 보증 대역폭을 의미하며 ceil은 클래스에서 사용할 수 있는 최대 대역폭을 나타냅니다.레이트와 ceil 사이에 사용되는 대역폭은 모두 부모 클래스에서 차용됩니다.따라서 레이트와 ceil은 최상위 클래스에서 동일해야 합니다.

계층형 토큰버킷은 Linux 트래픽컨트롤 시스템에 클래스 풀 큐잉 메커니즘을 구현하고 레이트와 ceil을 제공하여 사용자가 특정 트래픽클래스에 대한 절대 대역폭을 제어할 수 있도록 하고 추가 대역폭이 사용 가능하게 되었을 때의 대역폭 분배 비율(최대 ceil)을 나타냅니다.

최상위 클래스의 대역폭을 선택할 때 트래픽쉐이핑은 LAN과 인터넷 사이의 보틀 넥에만 도움이 됩니다.일반적으로 이것은 전체 LAN이 DSL 또는 T1 접속에 의해 서비스되는 가정 및 사무실 네트워크 환경에서 발생합니다.

「」를 참조해 주세요.

레퍼런스

^ Turner, J., 커뮤니케이션의 새로운 방향(또는 정보화 시대로 가는 방향)IEEE Communications Magazine 24 (10): 8 ~15 。 ISSN 0163-6804, 1986.
^ ^a ^b 앤드류 S.Tanenbaum, Computer Networks, 제4판, ISBN 0-13-166836-6, 프렌티스홀 PTR, 2003, 401페이지.
^ ATM 포럼, 사용자 네트워크 인터페이스(UNI), 버전 3.1, ISBN 0-13-393828-X, 프렌티스 홀 PTR, 1995.
^ ITU-T, B ISDN에서의 트래픽 제어 및 congestion 제어, 권고 I.371, 국제전기통신연합, 2004, Annex A,
^ "Linux HTB Home Page". Retrieved 2013-11-30.

추가 정보

John Evans, Clarence Filsfils (2007). Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice. Morgan Kaufmann. ISBN 0-12-370549-5.
Ferguson P., Huston G. (1998). Quality of Service: Delivering QoS on the Internet and in Corporate Networks. John Wiley & Sons, Inc. ISBN 0-471-24358-2.

[Turner-1] Turner, J., 커뮤니케이션의 새로운 방향(또는 정보화 시대로 가는 방향)IEEE Communications Magazine 24 (10): 8 ~15 。 ISSN 0163-6804, 1986.

[Tanenbaum-lbaq-2] 앤드류 S.Tanenbaum, Computer Networks, 제4판, ISBN 0-13-166836-6, 프렌티스홀 PTR, 2003, 401페이지.

[ATMF-GCRA-3] ATM 포럼, 사용자 네트워크 인터페이스(UNI), 버전 3.1, ISBN 0-13-393828-X, 프렌티스 홀 PTR, 1995.

[ITU-T-GCRA-4] ITU-T, B ISDN에서의 트래픽 제어 및 congestion 제어, 권고 I.371, 국제전기통신연합, 2004, Annex A,

[Linux_HTB-5] "Linux HTB Home Page". Retrieved 2013-11-30.

[1]

[2]

[3]

[4]

[5]

Search

토큰 버킷

네임스페이스

더

목차

개요