UDP: User Datagram Protocol/Principles of Reliable Data Transfer

UDP란?

• UDP란 User Datagram Protocol의 약자로, 데이터를 데이터그램 단위로 처리하는 프로토콜이다. 
  • 각 segment는 독립적으로 처리됨
• UDP는 비 연결형 프로토콜로, 필요한 최소한의 것들만 갖춘 프로토콜이다.
  • 그렇기에 데이터가 손실될 수도, 순서가 뒤바뀌어 전송될 수도 있다. (그럼에도 사용하는 이유는 빠르기 때문. 즉, 신뢰성 < 연결성이 더 중요한 서비스에서 사용 ex) streaming)
  • 비연결형이기 때문에 handshake 과정이 없다.
• UDP는 checksum을 이용해 최소한의 오류검출을 한다

UDP segment format

Flow Control: 데이터를 송신하는 곳과 수신하는곳의 데이터 처리속도를 조절하여 수신자의 오버플로우를 방지. 송신측이 수신측의 처리 속도에 맞게 데이터를 전송할 수 있도록 제어.

Congestion Control: 네트워크 내의 패킷 수가 넘치게 증가하지 않도록 방지 -> 패킷을 조금만 전송

 

Flow control 은 수신측의 처리 속도를 맞추는데에 중점, Congestion control은 네트워크 전체의 처리 속도를 최적화 하는것에 중점.

 

Checksum

• 전송되는 모든 데이터를 16비트 워드 단위로 구분 -> 1의 보수 -> SUM
• 수신측에서도 동일한 계산 진행
• 전송측의 checksum 필트와 수신측의 checksum 계산값이 같으면 may be no error(순서 바뀜), 다르면 에러가 있음

checksum 진행과정

Reliable Data Transfer(RDT)

신뢰성 있는 데이터 교환을 의미하며, 송/수신하는 데이터가 오류 없이 온전히 전송되는 것을 뜻한다.

오류의 예로는 Corruption(Bit Error) 와 패킷 손실이 있다.

RDT Protocol example

Finite State Machine (FSM)

FSM은 유한 상태 기계를 뜻한다. 프로그램이나 시스템 등이 특정한 입력에 따라 다양한 상태를 거치며 출력을 생성하는 과정을 표현하기 위해 사용된다. 

즉, 특정 event 에 의해 어떤 state 로 변하는지를 보여주는 모델이다.

다음은 기본적인 FSM이다.

RDT 1.0

여기서의 가정은, reliable transfer/ reliable channel이다. 즉, 비트에러나 패킷손실이 일어나지 않음을 가정하는 것이다. 

Sender는 데이터를 체널로 보내고 Receiver는 체널로부터 데이터를 읽어온다.

rdt1.0 FSM

• rdt_send() 라는 event가 일어났을때, sender는 패킷을 만들고 receiver 측으로 데이터를 보내게 된다
• rdt_rcv() 라는 event가 일어났을때, receiver는 패킷을 추출하고 데이터를 전달한다.

 

RDT 2.0

여기서의 가정은 패킷손실은 일어나지 않지만, 비트에러가 발생할 수 있다는 것이다. 

그렇다면 어떻게 에러로부터 복구할까?

• ACK 패킷 사용
  • ACK 는 데이터 전송의 성공 여부를 나타내는 패킷이다. 
  • Acknowledgement(ACK): Receeiver가 sender에게 패킷을 잘 받았다는 신호
  • Negative Acknowledgement(NAK): Receiver 가 sender에게 패킷이 에러가 있었다는 신호
    • Sender는 NAK를 받았을 때, 제전송한다.

rdt2.0 FSM

• rdt2.0은 Stop-and-Wait 방식이다 -> sender가 패킷 하나를 보내고 receiver가 응답하기를 기다린다.

에러가 없는 경우

• Sender 가 Receiver에게 패킷을 보낸다
• Receiver는 패킷이 not corrupt인것을 확인 후 sender측에 ACK를 보낸다
• Sender는 ACK 신호를 받고 종료한다.

에러가 있는 경우

• Sender 가 Receiver에게 패킷을 보낸다
• Receiver는 패킷이 corrupt인것을 확인 후 NAK 신호를 sender로 보내고 대기한다.
• Sender는 NAK 신호를 받고 데이터를 다시 전송한다
• Receiver에서 패킷이 not corrupt인것이 확인되면 sender측으로 ACK 신호를 보낸다.
• Sender는 ACK 신호를 받고 종료한다.

RDT2.0은 치명적인 결함이 있다.

• ACK/NAK 신호에 오류 및 손실
• 패킷의 중복 전송

 

RDT 2.1

rdt2.1은 패킷에 시퀀스 번호를 추가하여 2.0의 문제점을 해결한 것이다.

FSM Sender

• Sender 는 패킷을 보낼때 0번의 시퀀스 번호를 붙어혀 보낸뒤 ACK/NAK 0 신호를 기다린다
• 0 번 패킷이 전송된 후 NAK 0 이 돌아왔다면, 수신측으로 0번 패킷을 재전송 한다. ACK 0 이 돌아왔다면 다음 패킷인 1번 패킷을 전송한다. 
• 0번 패킷과 마찬가지로 ACK/NAK 1을 기다리며 모든 패킷에 대해 반복한다.

FSM&nbsp;Receiver

• 0번 패킷에 오류가 있음 -> NAK 0, 오류가 없음 -> ACK 0
• 1번패킷 -> 위와 동일

RDT 2.2

RDT2.2는 NAK-Free protocol이다. NAK 신호가 없고 오직 ACK 신호만 사용하여 하는 프로토콜이다. 

rdt2.2 FSM

• 중복되는 ACK 신호를 받으면 현재 패킷 재전송
• Receiver 측은 잘못된 패킷을 받았을 경우 ACK의 시퀀스 번호를 유지시켜 Sender로 다시 보낸다.
• Sender는 중복되는 ACK를 받았을 경우 다시 전송한다.

RDT 3.0

지금까지 rdt는 패킷 손실에 대응할 수 없다는 단점을 가지고 있다.

그렇기에 rdt 3.0 에서는 일정시간동안 기다리고 receiver측에서 응답이 없을 경우 패킷을 재전송 한다. 

sender FSM

receiver FSM

• Sender는 패킷을 보냄과 동시에 타이머를 작동시킨다.
• 일정 시간이 지나도 패킷이 오지 않아 timeout 상태가 되면 sender는 다시 패킷을 보내고 다시 타이머를 작동시킨다
• Receiver에서 ACK 가 오게 됐을 경우 또한 타이머를 멈추고 중복 확인을 한 뒤 다음 패킷을 보낸다.
• Receiver 의 FSM 은 2.2와 동일하다.

• (a): 패킷이 손실없이 잘 전달 될 경우
• (b): 패킷이 손실되어 rcv에 도착하지 않는 경우
• (c): 패킷은 잘 갔으나 ACK 가 손실된 경우(b 와 다른점은 rcv 측에서 중복을 감지한다는점)
• (d): 이경우를 자세히 살펴보자
  • Sender 는 패킷 1을 보내고 ACK 1 신호를 기다린다
  • ACK가 아주 느리게 전송되어 Sender 측은 timeout이 걸려 패킷 1을 재전송 하였다.
  • 패킷 1을 보낸뒤, timeout 걸리기 전에 보냈던 ACK 1이 도착
  • Sender는 ACK 1을 받았으니 다음 패킷 전송...

RDT 3.0 은 성능이 좋지 못하다

• ex) 1 Gbps link, 15ms prop delay, 8000bit packet
  • Dtrans = L/R  = 8000 bits / 10^9 bits/sec == 8 microseconds
  • Usender= fraction of time sender busy sending
    • (Dtrans)/(RTT+Dtrans) = 0.008 / 30.008 (RTT 는 30msec으로 가정)
    • 이 경우 1KB packet / 30 seconds: 33kb/sec (266kps) throughput over 1Gbps link

Pipelining 사용시