rdt 1.0
rdt 1.0 : 완벽하게 신뢰적인 채널상에서의 신뢰적인 데이터 전송 프로토콜
- 하위 채널이 완전히 신뢰적인 가장 간단한 경우
유한 상태 머신(FSM) 정리
rdt 1.0의 송수신자 FSM
- rdt1.0 송신자와 수신자에 대한 유한상태 머신(finite-state machine)
- (a) : FSM은 송신자의 동작을 정의
- (b) : FSM은 수신자의 동작을 정의
- 송신자와 수신자는 분리된 FSM을 가진다.
- 해당 그림에서 송신자와 수신자 FSM은 각각 하나의 상태만을 가진다.
- 하나의 상태를 가지므로, 전이는 그 상태로부터 자신으로 되돌아옴
유한 상태 머신 표기
점선 화살표 : FSM의 초기 상태액션(action) : 이벤트가 발생했을 때 취해지는 것
이벤트(event) : 전이를 일으킴
기호 ∧ : 동작이나 이벤트가 없음을 명확하게 표시하기 위해 각각 가로선 아래나 위에 표기
- 이벤트 발생 시 어떠한 행동도 취해지지 않거나,
어떠한 이벤트 발생 없이 행동이 취해질 수도 있음
FSM 과정
- rdt의 송신 측
- 상위 계층 애플리케이션의 프로시저 호출에 의해
rdt_send(data) 발생
rdt_send(data) 이벤트에 의해 상위 계층으로부터 데이터를 받음- 데이터를 포함한 패킷을 생성 →
make_pkt(data) 사용
- 패킷을 채널로 송신
- rdt의 수신 측
- 하위 계층 프로토콜로부터의 프로시저 호출에 의해
rdt_rcv(packet) 발생
rdt_rcv(packet) 이벤트에 의해 하위의 채널로부터 패킷을 수신- 패킷으로부터 데이터 추출 →
extract(packet, data)에 사용
- 추출한 데이터를 상위 계층으로 전달 →
deliver_data(data)
rdt 1.0 프로토콜의 특징
- 간단한 프로토콜로 데이터 단위와 패킷의 차이점이 없다.
- 모든 패킷 흐름은 송신자로부터 수신자까지이다.
→ 완전히 신뢰적인 채널에서는 오류가 생길 수 없다.
→ 수신 측이 송신 측에게 어떤 피드백도 제공할 필요가 없다.
- 수신자는 송신자가 데이터를 송신하자마자 데이터를 수신할 수 있다고 가정했음
→ 수신자가 송신자에게 천천히 보내라는 것을 요청할 필요도 없음
rdt2.0
rdt2.0 : 비트 오류가 있는 채널상에서의 신뢰적 데이터 전송
- 비트 오류가 발생하는 경위
→ 패킷이 전송/전파되거나 버퍼링 될 때 네트워크의 물리적 구성요소에서 발생
- 전송된 모든 패킷이 송신된 순서대로 수신된다고 가정
자동 재전송 요구(ARQ) 프로토콜
- 컴퓨터 네트워크 설정에서 재전송을 기반으로 하는 신뢰적인 데이터 전송 프로토콜
- Automatic Repeat reQuest, ARQ
제어 메시지
- 올바르게 수신됐는지, 또는 재전송이 필요한지를 수신자가 송신자에게 알려줄 수 있게 함
긍정 확인 응답(Positive acknowledgment) : OK → 올바르게 수신됨부정 확인 응답(negative acknowldegment) : 반복해 주세요 → 재전송 요청
ARQ에게 요구되는 3가지 부가 프로토콜 기능
오류 검출 : 비트 오류가 발생했을 때, 수신자가 검출할 수 있는 기능이 필요
- 이러한 기술은 수신자가 패킷 비트 오류를 검출하고 복구할 수 있게 한다.
- 송신자로부터 수신자에게 전송되는 추가적인 비트가 요구된다.
- 전송되어야 하는 본래의 데이터 비트들 이상을 뜻함
- 이러한 비트들은 rdt2.0 데이터 패킷의 패킷 체크섬 필드에 저장
수신자 피드백 : 수신자가 송신자에게 피드백을 제공하여 수신자의 상태를 송신자에게 알림
- 송신자와 수신자가 일반적으로 수천 킬로미터 떨어진 각기 다른 종단 시스템에서 동작하기 때문
- 예시
- 메시지 명령 시나리오에서 확인응답(ACK)과 부정 확인응답(NAK)
- 수신자로부터 송신자 쪽으로 ACK와 NAK 패킷을 전송
- 이러한 패킷은 한 비트 길이면 됨(ex : NAK(0) ACK(1))
재전송 : 수신자에게 오류를 가지고 수신된 패킷은 송신자에 의해 재전송된다.
rdt2.0의 FSM
송신 측
rdt 2.0 송신측 FSM
- rdt2.0의 송신 측은 2개의 상태를 가진다.
- 동작 과정
- 가장 왼쪽 상태에서 송신 측 프로토콜은 상위 계층으로부터 데이터가 전달되기를 기다림
rdt_send(data) 이벤트가 발생
→ 패킷 체크섬과 함께 전송될 데이터를 포함하는 패킷(sndpkt)을 생성
- 그 패킷을
udt_send(sndpkt) 동작을 통해 전송
- 가장 오른쪽 상태에서 송신자 프로토콜은 수신자로부터 ACK 또는 NAK 패킷을 기다림
- ACK 패킷이 수신되는 경우
← rdt_rcv(rcvpkt) && isACK(rcvpkt)를 통해 패킷이 정확히 수신되었음을 앎
- 프로토콜은 상위 계층으로부터 데이터를 기다리는 상태로 돌아간다.
- NAK가 수신되는 경우
- 마지막 패킷을 재전송 후, 재전송된 데이터 패킷에 대한 ACK 또는 NAK를 기다림
- 송신자가 ACK 또는 NAK를 기다리는 상태에 있을 때
→ 상위 계층으로부터 더 이상 데이터를 전달받을 수 없다.(rdt_send() 이벤트 X)
rdt_send()는 송신자가 ACK를 수신하고 기다리는 상태를 떠난 후에 발생
→ 송신자는 수신자가 현재의 패킷을 정확하게 수신했음을 알기 전까진
새로운 데이터를 전달하지 않는다.
→ 전송 후 대기(stop-and-wait) 프로토콜로 불림
수신 측
rdt 2.0 수신측
- rdt2.0에 대한 수신자 측 FSM은 단일 상태를 갖는다.
- 패킷이 도착했을 때, 수신된 패킷이 손상되었는지에 따라 ACK 또는 NAK로 응답
rdt_rcv(rcvpkt) && corrupt(rcvpkt) : 패킷이 수신되고 오류가 검출되는 이벤트에 대응
프로토콜 rdt2.0의 결함
- ACK 또는 NAK 패킷이 손상될 수 있다.
→ 이러한 오류를 검출하기 위해 ACK와 NAK 패킷에 대한 체크섬 비트를 추가
- 어떻게 프로토콜이 ACK 또는 NAK 패킷 오류로부터 복구되는가?
- 어려운 점
- ACK 또는 NAK가 손상된다면 송신자는 수신자가 전송된 데이터의
마지막 부분을 올바르게 수신했는지 알 방법이 없다.
손상된 ACK/NAK 처리를 위한 세 가지 가능성
- 송신자가 수신자로부터의 ACK/NAK 응답을 이해하지 못했을 때,
송신자가 “뭐라고 하셨죠?”를 의미하는 질문을 수신자에게 던진다.
→ 프로토콜에 새로운 송신자-수신자 패킷을 도입
- 이 새로운 패킷이 손상될 가능성도 존재
- 왜곡된 문장이 명령의 일부인지 마지막 응답을 반복하기 위한 요청인지 모름
→ 수신자는 또 “뭐라고 하셨죠?”를 의미하는 패킷을 던짐
- 송신자가 검출뿐만 아니라 비트 오류로부터 회복할 수 있도록 충분한 체크섬 비트를 추가
- 해당 방식은 패킷이 손상될 순 있으나 손실되지 않는 채널의 경우, 즉각 문제 해결 가능
- 송신자가 왜곡된 ACK/NAK 패킷을 수신할 때 현재 데이터 패킷을 단순히 다시 송신
- 이 방식은 송신자에서 수신자 간의 채널로
중복 패킷을 전송한다.
→ 도착하는 패킷이 새로운 데이터를 포함하고 있는지, 재전송인지를 사전에 알지 못함
- 중복 패킷의 근본적인 어려운 점
→ 마지막으로 전송된 ACK/NAK가 송신자에게 정확하게 수신됐는지 알 수 없다.
위 가능성에서 발생하는 새로운 문제에 대한 해결책
- 데이터 패킷에 새로운 필드를 추가하고,
이 필드 안에 순서 번호를 삽입하는 방식으로 데이터 패킷에 송신자가 번호를 붙임
- TCP를 포함한 현존하는 모든 데이터 전송 프로토콜에 채택된 방식
- 수신자는 수신된 패킷이 재전송인지를 결정할 때 이 순서 번호만 확인하면 됨
- 송신자의 전송 후 대기 프로토콜에서 한 비트 순서 번호면 재전송인지 아닌지 판별 가능
- 재전송인 경우
→ 수신된 패킷의 순서 번호는 가장 최근에 수신된 패킷과 같은 순서 번호를 가짐
- 새로운 패킷인 경우
→ 순서 번호가 변한다.
- 순서 번호가 변하면, 모듈로(modulo) 2 연산으로 진행한다.
- 일반적으로 패킷은 손실되지 않는 채널을 가정
→ ACK/NAK 패킷 자체는 확인 중인 패킷의 순서 번호를 나타낼 필요가 없음
- 송신자는 수신된 ACK/NAK 패킷이 최신 전송 데이터 패킷에 대한 응답임을 앎
rdt2.1의 FSM
rdt2.1
- rdt2.0의 수정된 버전
- rdt2.1 송신자와 수신자는 FSM은 전보다 두 배 많은 상태를 가지고 있다.
- 이유?
- 프로토콜 상태가 현재 송신자에 의해 전송되고 있는지를 반영 위해
- 수신자가 기다리고 있는 패킷이 순서 번호 0/1을 가져야 하는지를 반영 위해
rdt 2.1의 송신자측 FSM
rdt 2.1의 수신자 측
- 0번 패킷이 송신되고 있거나 기다리는 상태에서의 동작
→ 1번 패킷이 송신되고 있거나 기다리고 있는 상태의 미러 이미지
→ 단지 순서 번호의 차이만 존재
- 수신자로부터 송신자까지의 긍정 확인 응답과 부정 확인 응답을 모두 포함
- 순서가 바뀐 패킷이 수신된 경우
→ 수신자는 이미 전에 수신한 패킷에 대한 긍정 확인응답을 전송
- 손상된 패킷이 수신된 경우
→ 수신자는 부정 확인응답을 전송
- NAK 송신 대신, 가장 최근에 정확하게 수신된 패킷에 대한 ACK를 송신
→ 이를 통해 NAK를 송신한 것과 같은 효과를 얻을 수 있음
- ACK를 송신하는 이유 : 송신자는 2개의 ACK(중복 ACK)를 수신하기 때문
→ 송신자는 수신자가 두 번 ACK 한 패킷의 다음 패킷을 수신하지 못했음을 알 수 있음
rdt2.2
rdt 2.2 송신자 측
rdt 2.2의 수신자측
- rdt2.1과의 차이
- 수신자가 반드시 ACK 메시지에 의해 확인 응답되는 패킷의 순서 번호를 포함해야 한다.
- 수신자 FSM의
make_pkt()에 ACK, 0 또는 1인 인수를 넣어 수행
- 송신자는 수신된 ACK 메시지에 의해 확인응답된 패킷의 순서 번호를 반드시 검사해야 함
- 송신자 FSMdml
isACK()에 0 또는 1인 인수를 넣어서 수행