유한상태머신(FSM) 정의
- 화살표 : 한 상태로부터 다른 상태로의 전이
- 전이를 일으키는 이벤트 : 가로선 위에 나타냄
- 이벤트가 발생했을 때 취해지는 액션(행동) : 가로선 아래에 나타냄
- 어떠한 행동도 취해지지 않거나(액션x) 이벤트 발생없이 행동이 취해질 때 이벤트가 없음(이벤트x)을 표시하기 위해 각각 위치에 **기호 A ** 사용
- FSM 초기상태는 점선 화살표로 표시
완벽하게 신뢰적인 채널상에서의 신뢰적인 데이터 전송 : rdt1.0
하위채널이 완전이 신뢰적인 경우 (rdt1.0)
송신자와 수신자에 대해 분리된 FSM 송신자와 수신자는 각각 하나의 상태만을 가짐
-
rdt 송신측
- rdt_send(data) 이벤트에 의해
- 상위계층으로부터 데이터를 받아들임
- 데이터를 포함한 패킷 생성 (make_pkt(data))
- 패킷을 채널로 송신 (rdt_send(data)이벤트는 상위계층 애플리케이션 프로시저 호출에 의해 발생)
- rdt_send(data) 이벤트에 의해
-
rdt 수신 측
- rdt_rcv(packet) 이벤트에 의해 하위 채널로부터 패킷 수신
- 패킷으로부터 데이터 추출 (extract(packet,data))
- 데이터를 상위계층으로 전달(deliver_data(data))
(rdt_rcv(packet)이벤트는 하위계층 프로토콜로부터의 프로시저 호출에 의해 발생)
간단한 프로토콜에서는 데이터 단위와 패킷의 차이점이 없음
모든 패킷의 흐름은 송신→수신
완전히 신뢰적인 채널에서는 오류가 생길 수 없으므로 수신→송신으로 어떤 피드백도 제공할 필요가 없음
수신자는 송신자가 데이터를 송신하자마자 데이터를 수신할 수 있다고 가정 따라서 수신자가 송신자에게 천천히 보내라는 것을 요청할 필요가 없음
비트 오류가 있는 채널상에서의 신뢰적 데이터 전송 : rdt2.0
패킷 안의 비트들이 하위 채널에서 손상되는 모델 패킷이 전송,전파,버퍼링 될 때 네트워크의 물리적 구성요소에서 일반적으로 발생
자동 재전송 요구 프로토콜(ARQ)
- 긍정 확인응답(Positive acknowledgment, “OK”)
- 부정 확인응답(Negative acknowledgment, “그것을 반복해주세요”) 패킷이 정확하게 수신되었는지, 잘못 수신되어 반복이 필요한지 수신자가 송신자에게 알려줄 수 있게 하는 프로토콜
비트 오류 처리를 위해 요구되는 세가지 부가 프로토콜 기능
- 오류 검출
- 비트 오류가 발생했을 때 수신자가 검출할 수 있는 기능(checksum)
- 수신자가 패킷 비트 오류를 검출하고 복구할 수 있게 해줌
- 송신자로부터 수신자에게 전송되는 추가적인 비트들이 요구된다
- 이러한 비트들은 rdt2.0 데이터 패킷의 패킷 체크섬 필드로 모아짐
- 수신자 피드백
- 송신자가 수신자의 상태를 알기 위한 유일한 방법
- 수신자→송신자로 ACK와 NAK 패킷 전송
- 1비트 길이 (0 또는 1)
- 재전송
- 오류를 가지고 수신된 패킷은 송신자에 의해 재전송
송신자
- 왼쪽 상태 : 상위계층으로부터 데이터 전달을 기다림
- rdt_send(data) 이벤트 발생
- 송신자는 패킷 체크섬과 함께 전송될 데이터를 포함하는 패킷 생성
- 그 패킷을 udt_send(sndpkt) 동작을 통해 전송
- rdt_send(data) 이벤트 발생
- 오른쪽 상태 : ACK / NAK 패킷을 기다림
- ACK 패킷 수신
- 송신자는 가장 최근에 전송한 패킷이 정확하게 수신되었음을 인지
- 상위 계층으로부터 데이터를 기다리는 상태로 돌아감
- NAK 패킷 수신
- 마지막 패킷 재전송
- 재전송된 패킷에 대한 ACK or NAK를 기다림
- ACK 패킷 수신
-
ACK, NAK를 기다리는 상태에선 상위 계층으로부터 데이터를 전달받을 수 없음
-
송신자는 수신자가 현재 패킷을 정확하게 수신했음을 확신하기 전까지 새로운 데이터를 전달하지 않음
-
전송 후 대기 프로토콜로 알려져있다
수신자 -
단일 상태를 가짐
-
수신된 패킷이 손상되었는지 여부에 따라 ACK 또는 NAK로 응답
-
rdt2.0의 결함
- ACK, NAK 패킷이 손상될 경우 : 전송된 데이터의 마지막 부분을 올바르게 수신했는지 알 수 없음
손상된 ACK, NAK를 처리하기 위한 방법
- 송신자가 검출뿐만 아니라 비트 오류로부터 회복할 수 있도록 체크섬 비트를 추가
- 패킷이 손상될 순 있지만 손실되지 않는 경우 즉각적으로 해결 가능
- 송신자가 왜곡된 ACK 또는 NAK 패킷을 수신할 때 현재 데이터 패킷을 다시 송신
- 이 방식은 송신자에서 수신자 간에 중복 패킷을 전송함
- 마지막으로 전송된 패킷이 송신자에게 정확하게 수신되었는지 알 수 없음
- 수신자는 도착하는 패킷이 새로운 데이터를 포함한 것인지 재전송인지 사전에 알 수 없음
해결책
- 데이터 패킷에 새로운 필드를 추가하고 ** 순서번호(시퀀스)를 삽입하는 방식**
- 송신자는 수신된 패킷이 재전송인지 새로운 패킷을 전송한 것인지 알 수 있다
rdt2.1
이전보다 두 배 많은 상태를 가지고 있다
- 프로토콜 상태가 현재 전송되고 있는지 반영
- 수신자가 기다리고 있는 패킷이 순서번호 0 또는 1을 가져야 하는지 반영
수신자로부터 송신자까지의 긍정 확인 응답과 부정 확인 응답을 모두 포함
- 순서가 바뀐 패킷이 수신
- 수신자는 이미 전에 수신한 패킷에 대한 긍정 확인응답 전송
- 손상된 패킷이 수신
- 수신자는 부정 확인 응답 전송
- NAK를 전송하는 것 대신에 가장 최근에 정확하게 수신된 패킷에 대해 ACK를 송신함으로써 NAK를 송신한 것과 같은 효과를 얻을 수 있다
- 같은 패킷에 대해 2개의 ACK(중복 수신)를 수신한 송신자는 수신자가 두번 ACK 한 패킷의 다음 패킷을 정확하게 수신하지 못한것을 알게됨
2.1과 2.0의 차이
수신자가 반드시 ACK 메시지에 의해 확인되는 패킷의 순서 번호를 포함해야 함 송신자는 수신된 ACK 메시지에 의해 확인응답된 패킷 순서 번호를 반드시 검사해야 함
비트 오류와 손실있는 채널상에서의 신뢰적인 데이터 전송 : rdt3.0
하위 채널이 패킷을 손실하는 경우
- 어떻게 패킷을 검출할 것인가
- 패킷 손실이 발생했을 때 어떤 행동을 할 것인가를 다루어야 함
송신자에게 손실된 패킷의 검출과 회복 책임을 부여
송신자가 데이터 패킷을 전송하고 패킷 또는 수신자의 패킷에 대한 ACK를 손실했다고 가정, 송신자에게는 수신자로부터 어떠한 응답도 없을 경우
만약 송신자가 패킷을 잃어버렸다고 확신할 정도로 충분한 시간을 기다릴 수만 있다면 데이터 패킷은 재전송 될 수 있음
그러나 송신자는 적어도 송신자와 수신자 사이의 왕복 시간 지연 + 수신측에서 패킷을 처리하는데 필요한 시간 만큼을 기다린다
실제상황에서 채택한 접근 방식 : 패킷 손실이 일어났을만한 시간을 선택하여 패킷을 재전송 하는것 중복 데이터 패킷의 가능성을 포함하지만 순서 번호 기능을 통해 중복되었을 경우를 처리할 수 있다
시간 기반의 재전송 메커니즘 구현을 위해 주어진 시간이 지난 후에 송신자를 인터럽트(중단)할 수 있는 카운트다운 타이머가 필요하다
- 매 패킷(첫번째 또는 재전송 패킷)이 송신된 시간에 타이머를 시작
- 타이머 인터럽트에 반응
- 타이머를 중지
프로토콜이 패킷과 손실 또는 지연없이 동작하는 과정과 손실된 데이터 패킷을 처리하는 과정
- 패킷의 수신 시간은 전송 지연과 전파 지연때문에 패킷 전송시간보다 늦다
- 패킷의 순서번호가 0과 1이 번갈아 일어나므로, 얼터네이팅 프로토콜이라고 부른다