일반 세포율 알고리즘
Generic cell rate algorithm일반 셀 속도 알고리즘(GCRA)은 ATM(Asynchronous Transfer Mode) 네트워크에서 사용되는 네트워크 스케줄러를 위한 누출형 버킷형 스케줄링 알고리즘이다.[1][2]셀이 속한 VC 또는 VP의 트래픽 계약에 포함된 대역폭 및 지터 한계에 대해 가상 채널(VC) 및 가상 경로(VP)의 셀 타이밍을 측정하는 데 사용된다.교통 계약에 의해 주어진 한계에 부합하지 않는 셀은 교통 형태에 있어서 재타이밍(지연)되거나, 교통 치안 유지에 있어 우선순위를 떨어뜨리거나(폐기) 감소(시범)될 수 있다.그런 다음 우선 순위가 감소된 부적합한 셀은 혼잡을 겪고 있는 네트워크의 다운스트림 컴포넌트에 의해 우선 순위가 높은 셀보다 더 높은 셀을 삭제할 수 있다.또는 계약에 관한 한 셀이 초과되었음에도 불구하고 이들을 위한 용량이 충분하다면 목적지(VC 또는 VP 종료)에 도달할 수 있다. 우선순위 제어를 참조하라.
GCRA는 사용자-네트워크 인터페이스(UNI) 또는 네트워크 간 인터페이스 또는 네트워크-네트워크 인터페이스(INI/NNI)에서 네트워크 연결의 트래픽을 점검하기 위한 참조로 제공된다.[3]로 가스냉각로 협회만 레로 주셨어 그것은 또한 세포(ATMPDU Data_Requests)ATM네트워크에 호스트의 유앤아이 .[3]의 사용자 측에 이것은 세포 UPC/NCP에 의해 네트워크에서, 즉 유앤아이의 네트워크 면 위에 버려지지 않도록 보장하고 있는 네트워크 인터페이스 카드(NIC), 즉에 의해 전달되는 시기에 대한 기준으로. 하지만 부여된다.fe네트워크 제공자와 사용자는 동일한 결과를 제공하는 다른 알고리즘을 사용할 수 있다.
GCRA 설명
GCRA는 사용자-네트워크 인터페이스(UNI)[1]의 ATM 포럼과 B-ISDN의 교통 제어와 혼잡 제어의 ITU-T에 의해 설명된다.[2] 두 소스는 모두 GCRA를 가상 스케줄링 알고리즘과 연속 상태 누출 버킷 알고리즘의 두 가지 동등한 방법으로 설명한다(그림 1).
누출 버킷 설명
누출이 있는 버킷 알고리즘에 대한 설명은 누출이 있는 버킷의 단순한 비유에 기초하기 때문에 개념적인 관점에서 이해하기가 더 쉬울 수 있다: 누출이 있는 버킷 페이지의 그림 1을 참조하십시오.그러나 GCRA로 넘어간 알고리즘을 생산하기 위해 새는 버킷 비유를 적용하는 것을 두고 문헌에 혼선이 빚어졌다.GCRA는 누출이 많은 버킷을 대기열로 사용하기보다는 계량기로서 누출이 많은 버킷의 버전으로 간주해야 한다.
단, 이 누출되는 버킷 설명을 이해하는데는 가능한 장점이 있지만, 직접 구현한다고 해서 반드시 최상의(가장 빠른) 코드가 되는 것은 아니다.이는 두 가지 설명에 대해 흐름도에서 수행해야 할 조치의 상대적인 수로 증명된다(그림 1).
연속 상태 누출 버킷 알고리즘에 관한 설명은 ITU-T에 의해 다음과 같이 제시된다: "연속 상태 누출 버킷은 실제 가치의 콘텐츠가 시간 단위당 1단위의 연속적인 비율로 유출되고 각각의 준수 셀에 대한 증가 T로 콘텐츠가 증가하는 유한 용량 버킷으로 볼 수 있다.…셀 도착 시 버킷의 함량이 한계값 τ보다 작거나 같으면 셀은 준수하고, 그렇지 않으면 셀은 부적합하다.버킷(카운터의 상한)의 용량은 (T + τ)"이다.[2]누출은 단위시간당 내용물의 한 단위이므로 각 셀 T에 대한 증분 및 한계값 τ이 시간 단위로 되어 있다는 점에 주목할 필요가 있다.
연속 상태 누출 버킷 알고리즘의 흐름도를 고려할 때 T는 방출 간격이고 τ은 한계값이다.셀이 도착하면 버킷의 상태는 마지막 준수 셀인 X가 도착했을 때의 상태로부터 계산되며, 그 간격인 ta – LCT에서 얼마가 누출되었는지 계산한다.이 현재 버킷 값은 X'에 저장되며 한계값 τ과 비교된다.X'의 값이 τ보다 크지 않으면 셀이 너무 일찍 도착하지 않아 계약 매개변수에 부합하고, X'의 값이 τ보다 크면 준수하지 않는다.만일 그것이 그 때 순응한다면, 즉 그것이 늦었기 때문에 순응한다면, 즉 빈 물통(X' <= 0), X는 T로, 만약 이른 것은 아니지만 너무 이르지 않았다면( ( >= X') X는 X' + T로 설정된다.
따라서 유량도는 버킷의 아날로그 역할을 하는 X와 X의 역할을 하면서 누출되는 버킷 유추(미터로 사용)를 직접 모방한다.
가상 스케줄링 설명
가상 스케줄링 알고리즘은 누출되는 버킷과 같이 쉽게 접근할 수 있는 비유와 분명히 관련이 없지만 GCRA가 무엇을 하고 그것이 어떻게 가장 잘 구현될 수 있는지에 대한 보다 명확한 이해를 제공한다.결과적으로, 이 버전의 직접 구현은 누출 버킷 설명을 직접 구현하는 것보다 더 작고, 따라서 더 빠른 코드를 초래할 수 있다.
가상 스케줄링 알고리즘에 관한 설명은 ITU-T에 의해 다음과 같이 제시된다: "가상 스케줄링 알고리즘은 소스가 작용했을 때 세포가 Ⅱ [= 1/T]에 해당하는 방출 간격 T에서 균등하게 전송된다고 가정하는 세포의 '명목' 도착 시간인 이론적 도착 시간(TAT)을 업데이트한다.아이브. 만약 세포들의 실제 도착 시간 'too' 이른 게 아닌 태국 관광청과 관용 τ은 셀 전송률과 관련된, 즉은 실제 도착 시간 그 이론적인 도착 시간이 지난 후는 영하가 제한 값(분명>태국 관광청 – τ), 세포 자폭하는 순간이, 그렇지 않으면 세포는nonconforming" .[2]만약 세포는 비준 수가 있다면 태국 관광청은 l.에 비례unceft교수형. 만약 셀이 준수하고 있고, 그것의 TAT(버킷이 비어 있지 않고 한계치 이하인 것과 동일) 전에 도착했다면, 다음 셀의 TAT는 단순히 TAT + T. 그러나 만약 셀이 TAT 다음에 도착한다면, 다음 셀의 TAT는 TAT가 아니라 이 셀의 도착 시간으로부터 계산된다.이는 전송에 공백이 있을 때 신용이 쌓이는 것을 방지한다(버킷이 비어 있는 것보다 작아지는 것과 동일).
이 알고리즘 버전은 지터가 없는 경우보다 셀이 얼마나 더 빨리 도착할 수 있는지를 정의하기 때문에 작동한다: 누출 버킷: 지연 변동 허용오차를 참조한다.또 다른 방법은 TAT는 버킷이 다음에 비워질 때를 나타내는 것이므로 그 이전의 시간 bucket은 버킷이 정확히 한계값까지 채워지는 것이다.따라서 어느 쪽이든 TAT보다 arrives 이상 먼저 도착한다면, 순응하기에는 너무 이르다.
토큰 버킷과 비교
GCRA는 토큰 버킷 알고리즘의 구현과 달리 버킷 업데이트 프로세스(토큰 누출 또는 정기적으로 토큰 추가)를 시뮬레이션하지 않는다.오히려 셀이 도착할 때마다 버킷의 레벨이 마지막으로 계산된 이후 또는 버킷의 다음 빈 시간(= TAT)을 기준으로 버킷이 누출되는 양을 계산한다.이는 본질적으로 누출 프로세스를 (실시간) 클럭으로 대체하는 것으로 대부분의 하드웨어 구현이 이미 보유하고 있을 가능성이 높다.
이러한 프로세스를 RTC로 대체하는 것은 ATM 셀이 고정된 길이(53바이트)를 가지고 있기 때문에 T는 항상 상수이며, 새로운 버킷 레벨(또는 TAT)의 계산은 어떠한 곱이나 나눗셈도 수반하지 않기 때문에 가능하다.그 결과 소프트웨어에서는 계산이 빠르게 이루어질 수 있으며, 토큰 버킷에 의해 취해진 것보다 셀이 도착했을 때 더 많은 조치가 취해지지만, 작업을 수행하는 프로세서에 대한 부하 측면에서는 이를 보완하는 것 이상의 별도의 업데이트 프로세스가 없다.더욱이 버킷 업데이트의 시뮬레이션이 없기 때문에, 연결이 정지되어 있을 때는 프로세서 로드가 전혀 없다.
그러나, 가변 길이 패킷(Link Layer PDUs)이 있는 프로토콜에서 패킷/프레임 속도가 아닌 대역폭으로 제한하기 위해 GCRA를 사용한다면, 기본적으로 각 준수 패킷에 대해 버킷(또는 TAT)에 추가된 값은 패킷 길이에 비례해야 하는 반면, GCRA는 de de de de de.스크래핑된 버킷의 물은 시간의 단위를 가지고 있다. 가변 길이 패킷의 경우 패킷 길이와 시간의 산물인 단위를 가져야 한다.따라서 고속 하드웨어 승수(FPGA와 같이)에 액세스하지 않고 가변 길이 패킷의 대역폭을 제한하기 위해 GCRA를 적용하는 것은 실용적이지 않을 수 있다.그러나, 패킷이나 셀 속도를 제한하는데 항상 사용될 수 있다. 단, 패킷의 길이가 무시되는 한 말이다.
듀얼 누출 버킷 컨트롤러
다중 GCRA 구현은 VC 또는 VP에 동시에 적용할 수 있으며, 예를 들어 가변 비트 전송률(VBR) VC에 적용되는 듀얼 누출 버킷 트래픽 정책 또는 트래픽 쉐이핑 기능에서는 적용할 수 있다.이것은 이 VBR VC의 ATM 셀을 지속적 셀 속도(SCR)와 최대 버스트 크기(MBS)로 제한할 수 있다.동시에 이중 누출 버킷 트래픽 감시 기능은 버스트 내 셀 속도를 최고 셀 속도(PCR) 및 최대 셀 지연 변동 허용 오차(CDVt)로 제한할 수 있다. 교통 계약#교통 매개변수 참조.
이는 VBR VC의 전송이 일정 간격 또는 메시지 간 시간(IMT)으로 전송되고 이를 운반하기 위해 다수의 셀, MBS를 사용하는 고정 길이 메시지(CPCS-PDU)의 형태인 경우에 가장 잘 이해할 수 있지만, VBR 트래픽의 설명과 이중 누출 버킷의 사용은 이러한 SI에 제한되지 않는다.등록금이 경우 IMT 간격 동안의 평균 셀 속도는 SCR(=MBS/IMT)이다.개별 메시지는 PCR에서 전송될 수 있으며, 이는 물리적 링크(1/Δ)의 대역폭과 SCR 사이의 값이 될 수 있다.이를 통해 메시지 인스턴스 간의 간격이 있는 메시지 간격 IMT보다 작은 기간에 메시지를 전송할 수 있다.
듀얼 누출 버킷에서는 메시지에서 셀 수인 MBS를 제공하는 배출 간격이 1/SCR이고 한계값 τ인SCR 트래픽에 버킷 1개를 적용한다: 누출 버킷#최대 버스트 크기를 참조하십시오.두 번째 버킷은 배출 간격이 1/PCR이고 연결 경로의 해당 지점까지 CDV를 허용하는 한계값 τ을PCR 가진다: 누출되는 버킷#Delay 변동 허용오차를 참조하십시오.그런PCR 다음 PCR에서 최대 수의 MBS 셀까지 지터로 셀이 통과하도록 허용된다.다음 MBS 셀 버스트는 첫 번째 버스트 이후 MBS x 1/SCR 시작을 통해 허용된다.
If the cells arrive in a burst at a rate higher than 1/PCR (MBS cells arrive in less than (MBS - 1)/PCR - τPCR), or more than MBS cells arrive at the PCR, or bursts of MBS cells arrive closer than IMT apart, the dual leaky bucket will detect this and delay (shaping) or drop or de-prioritize (policing) enough cells to make the connection conform.
그림 3은 CLP(Cell Loss Priority) 값 1(낮음)과 0(높음) 셀 흐름 모두에 대해 SCR과 PCR 제어를 위한 기준 알고리즘을 보여준다. 즉, 두 우선 순위 값을 모두 가진 셀이 동일하게 취급된다.높은 우선순위 셀과 낮은 우선순위 셀이 다르게 처리되는 유사한 기준 알고리즘도 부속서 A에서 I.371에 제시되어 있다.[2]
