슬라이딩 윈도우 프로토콜

Sliding window protocol
"슬라이딩 윈도우"는 여기서 리디렉션된다. 자연 언어 처리에 사용하려면 슬라이딩 창 기반 스피치 부분 태그를 참조하십시오.

슬라이딩 윈도우 프로토콜은 패킷 기반 데이터 전송 프로토콜의 특징이다. 슬라이딩 윈도우 프로토콜은 전송 제어 프로토콜(TCP)뿐만 아니라 데이터 링크 계층(OSI 계층 2)에서와 같이 패킷의 신뢰할 수 있는 주문형 전달이 필요한 경우에 사용된다. 그것들은 또한 채널이 높은 지연 시간을 포함할 수 있을 때 효율을 향상시키는데 사용된다.

패킷 기반 시스템은 수신자가 정확하게 수신되었는지 확인할 수 있는 추가 데이터, 즉 체크섬을 수신할 수 있도록 하는 추가 데이터와 함께 데이터 일괄, 즉 패킷을 전송하는 아이디어에 기초한다. 새로운 패킷의 진입을 허용하고 이미 인정된 패킷을 거부하기 위해 옆으로 미끄러지는 창과 유사한 패러다임이다. 수신자가 데이터를 확인하면, 수신자에게 수신확인 신호, 즉 "ACK"를 다시 송신자에게 보내 다음 패킷을 송신할 수 있음을 표시한다. 단순 자동 반복 요청 프로토콜(ARQ)에서 송신자는 모든 패킷 뒤에 정지하고 ACK로 수신기를 기다린다. 이렇게 하면 한 번에 하나만 보낼 수 있기 때문에 패킷이 올바른 순서로 도착할 수 있다.

ACK 신호가 수신되는 데 걸리는 시간은 패킷 전송에 필요한 시간과 비교하여 상당한 시간을 나타낼 수 있다. 이 경우 전체 처리량은 이론적으로 가능한 것보다 훨씬 낮을 수 있다. 이 문제를 해결하기 위해 슬라이딩 윈도우 프로토콜은 ACK를 기다릴 필요 없이 선택한 수의 패킷, 즉 윈도우를 보낼 수 있도록 허용한다. 각 패킷은 시퀀스 번호를 받고, ACK는 그 번호를 되돌려 보낸다. 프로토콜은 어떤 패킷이 ACKed되었는지 추적하고, 패킷이 수신되면 더 많은 패킷을 전송한다. 이렇게 해서 전송을 구성하는 패킷의 흐름을 따라 창이 미끄러진다.

슬라이딩 윈도우는 많은 프로토콜의 핵심 부분이다. TCP 프로토콜의 핵심 부분으로, 패킷이 순서에 맞지 않게 도착하도록 본질적으로 허용하고 있으며, XMODEM과 같은 비창기 프로토콜에 비해 효율을 향상시키는 방법으로 UUCP-g, ZMODEM과 같은 많은 파일 전송 프로토콜에서도 발견된다.

기본개념

개념적으로 전송의 각 부분(대부분의 데이터 링크 계층에서는 패킷, TCP에서는 바이트)에 고유 연속 시퀀스 번호가 할당되며, 수신자는 수신된 패킷을 올바른 순서로 배치하기 위해 숫자를 사용하여 중복 패킷을 삭제하고 누락된 패킷을 식별한다. 이에 대한 문제는 요구될 수 있는 시퀀스 번호의 크기에 제한이 없다는 점이다.

슬라이딩 윈도우 프로토콜은 일정한 시간에 송신하거나 수신할 수 있는 패킷의 수에 제한을 두어, 고정 크기 시퀀스 번호를 사용하여 무제한의 패킷을 통신할 수 있게 한다. 송신기 쪽의 "창"이라는 용어는 수신자가 아직 인식하지 못한 총 패킷 수의 논리적 경계를 나타낸다. 수신기는 각 수신 패킷의 송신기에 현재 최대 수신기 버퍼 크기(창 경계)를 알려준다. TCP 헤더는 16비트 필드를 사용하여 송신자에게 수신기 창 크기를 보고한다. 따라서 사용할 수 있는 가장 큰 창은 216 = 64 킬로바이트다.

슬로우 스타트 모드에서는 송신기가 낮은 패킷 카운트로 시작하여 수신자로부터 수신확인 패킷을 수신한 후 각 전송의 패킷 수를 증가시킨다. 수신된 모든 ack 패킷에 대해 창은 하나의 패킷(논리적으로)을 미끄러져 하나의 새로운 패킷을 전송한다. 윈도우 임계값에 도달하면 송신기는 수신한 하나의 ack 패킷에 대해 하나의 패킷을 전송한다.

윈도우 제한이 10 패킷이면 송신기가 저속 시작 모드에 있는 경우 송신기가 한 패킷에 이어 두 패킷을 전송하기 시작할 수 있으며, 그 다음 두 패킷을 전송하기 전에 한 패킷을 수신해야 하며, 그 후 10 패킷까지 3 패킷 등을 전송할 수 있다. 그러나 10개의 패킷에 도달한 후, 추가 전송은 한 개의 ack 패킷이 수신한 것에 대해 전송되는 하나의 패킷으로 제한된다. 시뮬레이션에서 이것은 마치 창이 수신된 모든 ack 패킷에 대해 하나의 패킷 거리만큼 이동하는 것처럼 나타난다. 수신기 쪽에서도 창은 수신한 모든 패킷에 대해 하나의 패킷을 이동시킨다.

슬라이딩 윈도우 방식은 네트워크상의 교통 혼잡을 방지한다. 송신자와 수신자 측의 TCP가 패킷 버퍼의 슬라이딩 윈도우를 구현함에 따라, 애플리케이션 계층은 여전히 네트워크 트래픽 혼잡 문제를 걱정하지 않고 TCP로의 전송을 위한 데이터를 제공할 것이다. 창 크기는 네트워크 트래픽에 따라 동적으로 달라질 수 있다.

가능한 가장 높은 처리량을 위해서는 송신기가 하나의 왕복 지연 시간(RTT)보다 먼저 슬라이딩 윈도우 프로토콜에 의한 전송을 강제로 중지하지 않는 것이 중요하다. 수신 대기 전에 전송할 수 있는 데이터 양 제한은 통신 링크의 대역폭 지연 제품보다 커야 한다. 그렇지 않으면 프로토콜은 링크의 유효 대역폭을 제한한다.

동기

오류 제어를 위한 자동 반복 요청에 기초한 통신 프로토콜에서, 수신자는 수신 패킷을 승인해야 한다. 송신기가 합리적인 시간 내에 수신확인을 받지 못하면 데이터를 재전송한다.

수신확인을 받지 못하는 송신기는 수신기가 패킷을 실제로 받았는지 알 수 없다. 송신 중 분실 또는 손상되었을 수 있다. 오류 감지 메커니즘이 손상된 경우, 패킷은 수신자에 의해 무시되고 수신자에 의해 부정적이거나 중복된 승인이 전송된다. 또한 수신기는 어떠한 승인도 보내지 않도록 구성할 수 있다. 마찬가지로, 수신자는 보통 자신의 인정서가 수신되고 있는지에 대해 불확실하다. 수신확인이 전송되었지만 송신 매체에서 분실 또는 변질된 것일 수 있다. 이 경우, 수신자는 데이터가 계속 재전송되는 것을 방지하기 위해 재전송을 인정해야 하지만 그렇지 않으면 무시해야 한다.

프로토콜 운용

송신기와 수신기는 각각 전류 시퀀스 번호 n과t n을r 가지고 있다. 그들은 각각 w와t w의r 창 사이즈를 가지고 있다. 창 크기는 다양할 수 있지만 보다 간단한 구현에서는 고정되어 있다. 진행하려면 윈도우 크기가 0보다 커야 한다.

일반적으로 구현된 대로 n은t 다음 전송되는 패킷, 즉 아직 전송되지 않은 첫 번째 패킷의 시퀀스 번호다. 마찬가지로 n은r 아직 수신되지 않은 첫 번째 패킷이다. 이 두 수치는 시간이 지날수록 단조롭게 증가하고 있다. 다만 늘었을 뿐이다.

또한 수신기는 지금까지 수신된 가장 높은 시퀀스 번호를 추적할 수 있다. 변수s n은 수신된 가장 높은 시퀀스 번호의 시퀀스 번호보다 한 개 더 많다. 순서에 따라 패킷(wr = 1)만 수신하는 단순 수신기의 경우, 이것은r n과 동일하지만 w > 1이면r 더 클 수 있다. 유의사항: n 이하의r 모든 패킷은 수신되었고 n보다s 높은 패킷은 수신되지 않았으며 n과r n 사이에서는s 일부 패킷이 수신되었다.

수신자가 패킷을 받으면 변수를 적절하게 업데이트하고 새로운 n으로r 수신확인을 전송한다. 송신기는 n을a 받은 가장 높은 수신확인을 추적한다. 송신기는 n을a 포함하지는 않지만 n을 포함한 모든 패킷이 수신되었다는 것을 알고a 있지만, n과 ns 사이의 패킷에 대해서는 불확실하다ar. 즉s, n ;.

순번호는 항상a n nr n ns n nt n na n + w라는t 규칙을 따른다. 즉,

  • na ≤ nr: 송신기에 의해 수신되는 가장 높은 인정은 수신자가 인정한 가장r 높은 n보다 클 수 없다.
  • nr ≤ ns: 완전히 수신된 패킷의 범위는 부분적으로 수신된 패킷의 끝을 초과할 수 없다.
  • ns ≤ nt: 수신된 가장 높은 패킷은 전송된 가장 높은 패킷보다 클 수 없다.
  • nt ≤ na + wt: 전송된 가장 높은 패킷은 수신된 가장 높은 승인과 전송 창 크기에 의해 제한된다.

송신기 작동

송신기에 전송할 데이터가 있을 때마다, 송신기는 최신 수신확인a n보다 최대t w 패킷을 전송할 수 있다. 즉, 패킷 번호 n을t nt < na+w만큼t 길게 전송할 수 있다.

통신 오류가 없는 경우 송신기는 곧 전송한 모든 패킷에 대한 수신확인을 수신하여 n은a n과t 같다. 만약 이것이 합리적인 지연 후에 발생하지 않는다면, 송신기는 n과a n사이의t 패킷을 재전송해야 한다.

"합리적인 지연"을 정의하는 기법은 매우 정교할 수 있지만 효율에만 영향을 미친다. 슬라이딩 윈도우 프로토콜의 기본 신뢰성은 세부사항에 따라 달라지지 않는다.

수신기 작동

x로 번호가 매겨진 패킷이 수신될 때마다 수신자는 수신 창인 nr ≤ x < nr+wr. (가장 간단한 수신자는 하나의 값 nr=n만을s 추적하면 된다.) 만약 그것이 창문 안에 떨어지면, 수신자는 그것을 받아들인다. 번호가 n이면r 수신 시퀀스 번호가 1씩 증가하며, 이전에 연속된 패킷을 수신하여 저장한 경우 더 많을 수 있다. x > n이면r 패킷은 앞의 모든 패킷이 수신될 때까지 저장된다.[1] x≥n일s 경우, 후자는 ns=x+1로 업데이트된다.

패킷의 번호가 수신 창 내에 있지 않으면, 수신자는 그것을 무시하고 n이나r n을s 수정하지 않는다.

패킷이 허용되었는지 여부에 관계없이, 수신자는 현재의 n을r 포함하는 수신확인을 전송한다. (승인에는 n 또는r n사이에s 수신된 추가 패킷에 대한 정보도 포함될 수 있지만, 효율성에만 도움이 된다.)

송신 창 w보다t 더 큰 수신r 창을 갖는 것은 의미가 없다는 점에 유의하십시오. 왜냐하면 전송되지 않을 패킷을 받는 것에 대해 걱정할 필요가 없기 때문이다. 유용한 범위는 1 wr w ; w이다t.

필요한 시퀀스 번호 범위

주 기사: 일련 번호 산술
시퀀스 번호 modulo 4(wr=1 포함) 초기에는 nt=nr=0

지금까지 이 프로토콜은 마치 시퀀스 번호가 무제한의 크기, 끊임없이 증가하는 것처럼 설명되어 왔다. 그러나 메시지에서 전체 시퀀스 번호 x를 전송하기보다는 일부 유한 N에 대해 x mod N만 전송하는 것이 가능하다(N은 보통 2의 검정력이다).

예를 들어, 송신기는 n부터a n까지의t 범위(포함)에서만 수신한다. n-nta ≤ w를t 보장하므로, 주어진 시간에 도착할 수 있는 가능한 시퀀스 번호는 최대 wt+1이다. 따라서, 송신기는 N > w만큼t 긴 시퀀스 번호를 모호하지 않게 해독할 수 있다.

수신자가 더 강한 제약을 가한다. 프로토콜의 작동은 수신자가 새로운 패킷(수락 및 처리되어야 함)을 이전 패킷의 재전송(폐기되어야 함, 마지막 수신확인 재전송)과 신뢰성 있게 구별할 수 있는가에 따라 달라진다. 이것은 송신기의 창 크기에 대한 지식으로 이루어질 수 있다. x로 번호가 매겨진 패킷을 받은 후, 수신자는 x < na+wt, 그래서 n > x-w라는at 것을 안다. 따라서, x-wt 번호의 패킷은 다시는 재전송되지 않을 것이다.

앞으로 우리가 받게 될 가장 낮은 순번호는 n-w이다st.

또한 송신기의 n은a 지금까지 전송된 가장 높은 수신인, 즉 n보다r 높을 수 없다는 것도 수신자는 알고 있다. 그래서 우리가 볼 수 있는 가장 높은 순번호는 nr+wt ≤ ns+w이다t.

따라서, 수신자가 한 번에 받을 수 있는 2w의t 서로 다른 시퀀스 번호가 있다. 그러므로 우리가 N ≥ 2w를t 가져야 하는 것처럼 보일 수도 있다. 그러나 실제 한계는 더 낮다.

추가적인 통찰은 수신기가 너무 낮거나(n보다r 작거나) 너무 높은(ns+w보다r 크거나 같은) 시퀀스 번호를 구별할 필요가 없다는 것이다. 어느 경우든 수신기는 수신확인 재전송을 제외하고 패킷을 무시한다. 따라서 N ≥ wt+w만r 있으면 된다. wr(예t: 아래 Go-Back-N 참조)를 갖는 것이 일반적이기 때문에 고정 N 내에서 더 큰 w를t 허용할 수 있다.

예

가장 간단한 슬라이딩 창: 중지 및 대기

일반적으로 슬라이딩 윈도우 프로토콜과 구별되지만, 중지-대기 ARQ 프로토콜은 실제로 가능한 가장 간단한 구현이다. 송신 창은 1패킷이고, 수신 창은 1패킷이다. 따라서 N = 2개의 가능한 시퀀스 번호(단일 비트로 쉽게 표현됨)가 필요하다.

모호성 예

송신기는 "이상한"과 "짝수"로 표시된 패킷을 번갈아 보낸다. 답례도 마찬가지로 "이상한"과 "짝짝짝짝짝"이라고 말한다. 홀수 패킷을 전송한 송신기가 홀수 수신 확인을 기다리지 않고 대신 다음과 같은 짝수 패킷을 즉시 전송했다고 가정해 보자. 그러면 그것은 "다음에는 이상한 패킷을 기대한다"는 회신을 받을 수 있을 것이다. 이것은 송신기를 곤경에 빠뜨릴 것이다: 수신자가 두 패킷을 모두 수신했는가, 아니면 둘 다 수신하지 않았는가?

Go-Back-N

Go-Back-N ARQ는 wt >1이 있는 슬라이딩 윈도우 프로토콜이지만 wr=1이 고정되어 있다. 수신자는 다음 패킷을 제외한 어떤 패킷도 순차적으로 받기를 거부한다. 패킷이 전송 중에 손실된 경우, 누락된 패킷이 재전송될 때까지 다음 패킷은 무시되며, 이는 최소 한 번의 왕복 시간 손실이다. 이 때문에 패킷 손실이 잦은 링크에서는 효율성이 떨어진다.

모호성 예

일반적으로 HDLC에 사용되는 것과 같은 3비트 시퀀스 번호를 사용하고 있다고 가정해 보십시오. 이것은 N=23=8이다. wr=1이므로 우리는 7원을t 제한해야 한다. 7개의 패킷을 전송한 후 다음과 같은 8가지 결과가 가능하기 때문이다. 0에서 7까지의 패킷이 성공적으로 수신될 수 있었다. 이것은 8가지 가능성이며, 송신기는 그것들을 모두 구별할 수 있는 충분한 정보가 필요하다.

송신기가 수신확인을 기다리지 않고 8개의 패킷을 전송했다면, 수신확인은 8개의 패킷이 모두 성공적으로 수신되었다는 것을 의미하는 것인가, 아니면 하나도 수신되지 않았다는 것인가?

선택적 반복

슬라이딩 윈도우 프로토콜의 가장 일반적인 경우는 선택적 반복 ARQ이다. 이것은r 현재 n보다 높은 시퀀스 번호를 가진 패킷을 받아들여 갭이 채워질 때까지 저장할 수 있는 훨씬 더 유능한 수신기가 필요하다.

단, 송신기에 재전송이 필요하다는 것을 알 수 있기 전에 한 번의 왕복 시간 동안 정확한 데이터를 폐기할 필요가 없다는 것이 장점이다. 따라서 신뢰성이 낮거나 대역폭 지연이 높은 링크에 선호된다.

창r 크기는 허용할 수 있는 연속적인 손실 패킷 수보다 커야 한다. 따라서 작은 가치관이 대중적이다; wr=2는 일반적이다.

모호성 예

매우 인기 있는 HDLC 프로토콜은 3비트 시퀀스 번호를 사용하며 선택적 반복을 위한 선택적 제공이 있다. 단, 선택적 반복을 사용할 경우t n+nr 8 8의 요건은 유지되어야 하며, w를r 2로 늘릴 경우 w를t 6으로 줄여야 한다.

일반적으로r HDLC의 Go-Back-N 변종에서 사용되는 wt =2 그러나 수정되지 않은 송신기가 w =7과 함께 사용된다고 가정하자. 또한 수신기가r n =ns =0으로 시작된다고 가정하십시오.

수신기가 다음과 같은 일련의 패킷(모든 modulo 8):

0 1 2 3 4 5 6 (11) 0

wr =2이기 때문에, 수신자는 패킷 7의 재전송을 요청하면서 최종 패킷 0(시리즈에서 패킷 8이라고 생각함)을 받아들이고 저장할 것이다. 그러나 송신기가 어떤 수신확인도 받지 못하고 패킷 0을 재전송했을 가능성도 있다. 이 후자의 경우에, 수신자는 잘못된 패킷을 패킷 8로 받아들일 것이다.

용액은 송신기가 wt ≤6을 제한하는 것이다. 이 제한으로, 수신자는 만약 모든 수신확인이 손실되었다면, 송신기는 5번 패킷 이후에 정지했을 것이라는 것을 안다. 패킷 6을 수신할 때, 수신자는 송신기가 패킷 0(전송기의 na ≥1)에 대한 수신확인을 수신하였음을 유추할 수 있으므로, 0에 번호가 매겨진 다음 패킷은 반드시 패킷 8이어야 한다.

확장

프로토콜을 확장할 수 있는 여러 가지 방법이 있다.

  • 위의 예는 패킷이 전송 중에 재주문되지 않는다고 가정하고, 패킷은 전송 중에 손실될 수 있지만(오류 감지를 통해 손실에 해당하는 손상을 만들 수 있음) 결코 순서가 잘못된 것으로 나타나지 않는다. 프로토콜은 거리를 경계로 할 수 있는 한 패킷 재정렬을 지원하도록 확장할 수 있다. 시퀀스 번호 계수 N은 최대 오순 거리만큼 확장되어야 한다.
  • 일시 정지가 있으면 결국 수신확인이 전송되는 한 모든 패킷을 인정하지 않는 것이 가능하다. 예를 들어, TCP는 보통 매 초의 패킷을 승인한다.
    • 패킷 시퀀스의 간극이 감지되면 송신기에 즉시 알리는 것이 일반적이다. HDLC에는 이를 위한 특별한 REJ(거부) 패킷이 있다.
  • 전송 및 수신 창 크기는 통신 중에 변경될 수 있다. 일반적으로 전송 및 수신 창 크기는 각각 해당 한도를 존중하는 최대값이 할당되지만 주어진 시간의 작업 값은 최대값보다 작을 수 있다. 특히:
    • 포화나 혼잡을 피하면서 링크 속도에 맞춰 전송 속도를 늦출 수 있도록 전송창 크기를 줄이는 것이 일반적이다.
    • 선택적 반복의 일반적인 단순화는 SREJ-REJ ARQ라고 불린다. 이것은 wr=2와 함께 작동하고 패킷을 간격에 따라 버퍼링하지만 단일 손실 패킷만 허용한다. 그 패킷을 기다리는 동안 wr=1과 두 번째 패킷이 손실되면 더 이상 버퍼링되지 않는다. 이것은 더 간단한 구현으로 전체 선택적 반복 프로토콜의 성능 편익의 대부분을 제공한다.

참고 항목

참조

  1. ^ 피터슨, 래리 L. & 데이비, 브루스 S. "[1]," 모건 카우프만, 2000. ISBN1-55860-577-0
  • Comer, Douglas E. "TCP/IP, 제1권: 원칙, 프로토콜 및 아키텍처", 1995년 프렌티스 홀. ISBN 0-13-216987-8

외부 링크