Ch3-4) Principles of reliable data transfer

 

우선, Reliable data transfer의 목적을 살펴보자.

 

• Application을 사용하는 사용자 입장에선, 데이터가 한방향으로만 전송되고, 이미 데이터가 안정적으로 전송될것이라는 사실을 알고 있다.
• 그러나, 설계하는 입장에서 reliable data transfer을 만들기 위해선, “양방향”의 노력이 필요하다.

 

→ 위와 같은 사진처럼, Unreliable channel을 통해 안전하게 데이터를 전송하는 과정을 추상화 하는 것이 바로 Reliable data transfer service의 목적이다.

Architecture of Reliable data transfer: RDT

 

• 우선, 우리는 다음과 같은 4가지의 함수를 통해 rdt에 대해서 살펴볼 것이다.
  • rdt_send() : Application layer에서 데이터를 보내고자 할때 호출된다.
  • udt_send() : Unreliable channel을 통해서 reciever에게 데이터를 전달하기 위해 호출
    • packet loss, delay 등이 일어날 수 있는 채널을 통해서 데이터를 보내는 역할
  • rdt_rcv(): packet이 reciever측 channel에 무사히 도착하면 호출
  • deliver_data() : 전달받은 packet을 상위 계층에 전달.
• 이제 FSM을 통해서, rdt에 대해서 더 자세히 알아보자.
  • **전이를 일으키는 이벤트(event)**는 변화를 표기하는 가로선 위에 나타낸다.
  • 이벤트가 발생했을 때 취해지는 행동, **액션(action)**은 가로선 아래에 나타낸다.
  • 이벤트 발생 시 어떠한 행동도 취해지지 않거나, 어떠한 이벤트 발생 없이 행동이 취해질 때동작이나 이벤트가 없음을 표시하기 위해 각각 가로선 아래나 위에 기호 𝚲를 사용한다.

 

 

 

rdt 1.0 : reliable transfer over a reliable channel

• • no segment loss, corrupted, dupplicated or reordered우선, underlying channel이 완벽하게 안전한 채널이라고 가정해보자.

 

 

 

• sender
  • rdt_send() event에 의해서 호출되어, 데이터를 내려받아 packet을 하나만들어 채널로 송신한다.
• receiver
  • rdt_rcv() event에 의해 하위 채널로부터 패킷을 수선해, 데이터를 추출하고 상위 계층으로 전달한다.

⇒ 이때 완전히 신뢰적인 채널에서는 오류가 생길 수 없으므로, 서로간에 그 어떠한 피드백도 제공할 필요가 없다

• 그래서 서로 신경 쓰지 않고 지 할일만 잘하면 됨 !

rdt 2.0: channel with bit errors occur

• 이제는, bit error가 발생할 수 있는 channel을 통해서 데이터를 주고받는다고 해보자.
• checksum과 같은 방식으로 error을 detect할 수 있다.

⇒ 그럼, 문제는 error을 어떻게 해결할 것인가????? 사람처럼, 받았으면 받았다고 말하면 된다

1. ACK (Acknowledgements)
   • Receiver가 packet을 잘 받았다고 sender에게 보냄
2. NAK (Negative Acknowledgements)
   • Receiver가 packet에 에러가 있다고 sender에게 보냄
   → Sender은 NAK를 받으면, packet을 “ 재전송 “한다.

이떄, Sender가 하나의 패킷을 전송했을 떄 답장을 기다리는 것을 “Stop and wait” 기법이라고 부름.

 

 

이를 FSM으로 나타내면 위와 같다.

이때, 에러가 발생하는 상황에서 Sender와 Receiver의 FSM은 어떻게 변할지 생각해보자.

만약, 에러가 발생하지 않았다면 FSM은 다음과 같다.

 

 

그런데, 만약 중간에 에러가 발생했다면 receiver의 corrupt(rcvpkt) event가 발생해, packet을 재전송하게 된다.

 

⇒ 이러한 rdt2.0 방식에는 아주 큰 허점이 있다. “만약 ACK나 NAK가 corrupt되면 어떡하지?”

• Sender 입장에서는, 잘 받았는지 모르기 떄문에 재전송하는 수 밖에 없고, 이는 data duplicate를 유발한다.
• 이를 해결하기 위해서,

💡 데이터 패킷에 새로운 필드를 추가하고 이 필드 안에 순서 번호(sequence number)를 삽입하는 방식으로 데이터 패킷에 송신자가 번호를 붙인다.

• 수신자는 데이터가 재전송인지 확인하기 위해서 그냥 sequence number만 확인하면 된다.

rdt 2.1: sender, handling garbled(왜곡된) ACK/NAKs

• rdt 2.1은 다음과 같은 2가지 상황을 체크해야 하기에 2.0에 비해 state가 2배 많다.
  1. 프로토콜 상태가 현재 (송신자에 의해) 전송되고 있는지에 대한 반영
  2. (수신자가) 기다리고 있는 패킷이 순서 번호 0 또는 1을 가져야 하는지에 대한 반영
• 우선, 위와같은 상황에서 Sender의 FSM을 살펴보자.
•  

 

 

 

• Sender은, data를 보내고 응답을 기다리다가 NAK나 corrupt임을 발견하면, 다시 재전송하고 응답을 기다린다.(기호 Capital lamda는 idle 상태)
• ACK응답이 도착했고, notcorrupt인 것을 확인했다면 상위 계층으로부터 다음 데이터가 올떄까지 기다렸다가, 같은 과정을 반복한다.
• 정리하자면, sender은 Packet에 #를 붙여서 보낸다
• #는 (0,1)이면 충분한데, 이는 stop and wait 기법을 사용하기 때문이다. (어차피 답장이 와야 다음 패킷 전송)
• 또한 응답온 ACK/NAK 종류를 확인해야한다.

다음은 receiver의 FSM을 살펴보자.

   0. Wait for 0 from below

• packet # 0가 오는 것을 기다렸다가, 만약 에러가 있으면 NAK를 보내 전송하고, 다시 packet #0을 기다린다.
• 만약 에러가 없다면 data를 추출해 상위 layer로 전달하고, ACK 응답을 보낸 후 packet #1를 기다린다.
• 0을 기다리고 있는데 1이 온다? 그럼 그냥 ack 응답 하나 더 보냄
• → 아직 stop and wait 상태이기에, 중복된 #1 패킷에 대한 응답임을 Sender가 인지할 수 있음.

1. Wait for 1 from below
   • pakcet #0을 받은 후 1을 기다리고 있는데, 만약에 에러가 있으면 NAK를 응답하고 대기
   • 에러가 없고 #1이 왔다면 data를 상위 계층해 전달하고 1.상태로 감
   • 근데 #1을 기다리는데 #0이 왔다면 똑같이 그냥 ACK를 전달하고, state는 변하지 않는다.

• 정리하자면, Receiver은
  • packet이 중복된 패킷인지 확인해야한다.
  • 근데, receiver은 마지막으로 보낸 ACK/NAK응답이 sender에게 잘 도착했는지는 알 수 없다.

rdt 2.2 : a NAK-free protocol

• rdt 2.2는, rdt 2.1과 똑같이 작동하지만, ‘NAK’ 응답이 존재하지 않는다
• NAK대신, receiver은 ACK응답을 보낼 때 무슨 seq #에 대한 ACK인지를 패킷에 포함해야한다.
  • 나중에 보겠지만, TCP는 NAK-free protocol이다.
• 또한, sender은 ack응답을 받고, 응답이 온 Packet에 대한 #가 무엇인지 반드시 확인해야한다.
• rdt 2.2의 FSM은 다음과 같다.
•  

 

 

→ 어차피 NAK는 존재하지 않으므로, 그냥 send할 때 ACK만 send하면 돼서 udt_send의 파라미터는 sndpkt밖에 없음.

rdt 3.0 : channels with errors and loss

• 이제는, duplicate 상황도 발생하고 packet lose (data, ACKs)상황도 발생한다고 가정해보자.
• Checksum, seq #, ACKs, retransmission도 뭐 도움이 되긴 하겠지만, 모든 상황에 대한 해결책을 제시해주진 않을 것이다.
• 이때는 다음과 같은 2가지 상황에 대한 부가적인 생각이 존재해야한다.
  • 어떻게 패킷 손실을 검출할 것인가?
  • 패킷 손실을 검출했다면, 어떤 행동을 취할 것인가?

⇒ rdt3.0은 위와같은 상황에서, “Sender”에게 손실된 packet의 검출과 회복에 대한 책임을 부여한다

⇒ 응애~ Sender야 해줘

왜냐면, sender은 receiver가 보낸 ack응답이 손실 되었을 때, ack응답을 받지 못하기 떄문이다.(알아서 손실되었는지 눈치껏 인지해야함)

• 즉, sender은 데이터 패킷이 손실되었는지, ACK가 손실되었는지, 그냥 delay 된 것인지 알지 못한다

⇒ Sender가 패킷이 loss되었다고 확신할 정도의 충분한 시간을 기다릴 수만 있다면, 그냥 재전송하면 된다.

• 만약 중복된 패킷이라고 한다면, seq #가 이를 해결해 줄 것이다.
• 또한 receiver은 packet이 ACK 되었다는 응답을 보낼 때 seq #를 보내, Sender가 중복 송신하는 것을 막을 수 있다.

송신자는 적어도 다음의 시간만큼을 기다려야 한다.

송신자와 수신자 사이의 왕복 시간 지연(중간 라우터에서의 버퍼링을 포함) + 수신 측에서 패킷을 처리하는 데 필요한 시간 = RTT + a

이 상황에 대한 Sender FSM을 확인해보자.

 

1. Wait for call 0 from above
   • 상위 계층에서 data를 전달해주면, seq#를 붙여 패킷을 만들고, 보낸 후 timer를 시작한다.
2. Wait for ACK0
   • 이때 답장이 모종의 이유로 늦게 와서 timeout이 발생하면, packet을 한번 더 보내고 타이머를 다시 가동한다.
   • 잘 받았다는 신호 (ACK, proper seq#)를 확인하면, 타이머를 멈추고 #1을 기다린다.
3. Wait for call 1 from above
   • 상위 계층에서 data를 전달해주면 seq#1을 붙여 패킷을 만들고 보낸 후 timer를 시작한다.
4. Wait for ACK1
   • packet을 잘 받았다는 답장이 늦어서 timeout이 발생하면, packet을 재전송하고 타이머를 다시 가동한다.
   • 잘 받았다는 신호 (ACKA, proper seq#)를 확인하면 타이머를 머무고 다시 초기 상태로 돌아간다.

다양한 상황에서 발생할 수 있는 문제에 대한 flow는 아래 그림과 같다.

 

 

Packet이 loss되면, 당연히 응답이 안올 것이므로 timeout이 발생해 packet을 재전송한다.

 

 

• 만약 Packet은 잘 전송되었는데 응답이 오지 않는 경우에도, Timeout이 발생해 packet을 재전송한다.
• 그런데 문제상황은 (d)에서 발생한다.
• 모종의 이유로 ACK가 delay되어, 보내고 있는 중간에 timeout이 발생해 패킷을 재전송하는 경우다.
• 위와 같은 상황에서는, 불필요한 재전송이 발생할 수 있다.

⇒ 이러한 상황에서, rdt3.0의 개선점을 찾아보기 위해 performance를 측정해보자. (stop-and-wait)

 

 

 

 

 

• 우선, 가정은 위와 같다.
• Sender의 utilizaition은, 보통 link bandwith에 비해서 굉장히 낮다. transfer delay가 8 ms라고 하자.
•  

 

 

위에서 언급했듯, 답장이 도착할 때까지 걸리는 시간은 1RTT인데. 이는 Transfer delay인 8ms에 비하면 굉장히 크다.

 

 

 

즉, 전체 RTT + 8ms 중에 데이터를 보내는 시간은 고작 8ms라는 건데, 성능이 그냥 썩었다. protocol이 channel의 infrastructure을 발목잡는 일이 생겨선 안된다.” 위의 방정식 잘 보랍니다 교수님이”

 

⇒ 이를 해결하기 위해, Pipeline을 구현해보자.

 

 

 

위처럼 3개의 packet을 pipeline으로 작동시키면, utilization을 3배 증가시킬 수 있다 !

하지만 Pipeline을 구현하려면, 다음과 같은 요구사항이 생긴다.

1. Packet에 붙이는 Seq #의 범위가 커져야함.

• 이유는 Pipelining을 도입함에 따라, 각각의 Packet은 고유한 Seq #를 가져야 하기 때문이다.
• 중복 된 Seq#를 사용한다면, 전송 중인 ACK응답이 여러개 생길 수도 있다.

1. Sender과 Receiver은, 1개 이상의 패킷 버퍼링 시스템을 갖추어야 한다.

• Sender 입장에서는, 잘 송신은 했으나 송신한 packet에 대해 응답을 받지 못한 경우를 대비해, packet을 버퍼링 해놓았다가 재전송해야할 수 있다.
• Receiver 입장에서는, 중복 패킷이나 순서가 어긋난 패킷을 처리하기 위해 버퍼링 시스템이 있어야한다.

⇒ 이러한 요구사항을 충족하는 ARQ(Automatic Repeat request) 기법이 바로 GBN과 SR이다.

Go-Back-N

• Go-Back-N에서는, 도중에 잘못된 segment가 발생한 경우 그 segment부터 싹다 전송을 다시 시작한다.
• 이때, Sender은 receiver의 버퍼 오버플로우 ( 너무 한꺼번에 많이 보내서 receiver가 배 터져 죽는 상황)를 방지하기 위해서, Sliding window 기법을 적용한다.

 

• 바로 Window size를 정해놓아, 한번에 pipelining을 통해 전송할 수 있는 segment의 개수를 제한해놓는것이다.
• 확인응답이 안 된 가장 오래된 패킷의 순서 번호를 base로 정의한다.
• 가장 작은 순서 번호를 nextseqnum(전송될 다음 패킷의 순서 번호)으로 정의한다.
• 이 2가지의 term을 통해서 4가지 구간을 define할 수 있다.

1. [0,base-1] : 이미 ack 응답을 받은 패킷
2. [base-1,nextseqnum-1] : 송신은 했지만, 아직 ack 응답을 받지 못한 패킷
3. [nextseqnum-1, base+N-1] : 상위 계층으로부터 데이터가 도착하면 바로 전송될 수 있는 패킷
4. base+N-1 이상 : 아직 사용불가능한 패킷 ( base위치의 패킷이 잘 도착했다는 ack를 받아야 사용 가능)

⇒ 여기서, ack확인이 안된 패킷의 수는 당연하게도 N을 넘을 수 없다.

• 프로토콜이 동작할 때, 이 Window는 오른쪽 방향으로 슬라이딩하며 패킷을 전송하게 된다.
• 송신자가 “ACK(n)까지 받으면, seq #n 까지의 모든 패킷이 잘 도착”했다는 것을 알 수 있다.
  • ACK(n)을 받은 후, window는 n+1로 이동한다.
• 또한, Sender은 가장 오래된 패킷에 대해서 타이머를 설정한다.
• 만약에 “**타이머가 만료되면, 타임아웃이 발생한 패킷부터 그 이후의 모든 패킷을 재전송”**한다.

그럼, 이제 Receiver의 입장도 생각해보자.

 

 

 

 

 

• receiver은 ACK응답만 보내게 되는데, 이때 지금까지 받았던 seq# 중 가장 큰 것에 해당하는 seq#를 함께 보낸다.
  • 이때 중복 ACK가 발생할 수 있지만, 이는 송신자에게 “ seq# 전까지의 패킷은 잘 보냈으니, 이후 패킷을 전송해라”로 해석되기 때문에 상관없다. (sender에게 응답하는 seq#는 rcv_base-1임)
  • 이때 현재 수신대기중인 패킷의 seq#만 기억하면 되며, 이를 rcv_base라고한다.
• 만약 순서가 맞지 않는 패킷을 받았을 때, receiver가 할 수 있는 선택지는 두 가지이다.
  • 폐기
    • 그냥 버리고 재전송해줄때까지 기다리기
  • 버퍼링
    • 순서가 맞지않는 패킷도 나중에 함께 처리할 수도 있으나, 잘 안쓰인다고 함

 

전체적인 flow는 다음과 같다.

 

 

 

정리하자면,

• 송신자가 유지해야 하는 것
  1. 윈도 상위와 하위 경계
  2. 이 윈도 안에 있는 nextseqnum 위치
• 수신자가 유지해야 하는 것 : 다음 순서 패킷의 순서 번호

⇒ 그러나 이는 한 세그먼트에만 문제가 발생해도 모든 세그먼트를 다 보내야하는 overflow가 존재한다.

Selective Repeat (SR)

• Go-Back-n은 n 이후의 모든 패킷을 재전송하는 거였다면, Selective repeat은 그냥 에러난 패킷을 개별적으로 재전송하는 방법이다.
• Selective repeat에서의 window는 어떻게 사용되는지 알아보자.

 

 

 

 

• Sender의 event와 action
  • 상위 계층으로부터 데이터가 수신되면, 다음을 검사한다
    • 패킷 번호가 윈도우 size 내에 존재하는지
    • 존재하지 않으면 다시 돌려보냄 (GBN과 동일)
  • Timeout
    • 타이머는 손실된 패킷을 재전송하기 위해 이용
    • 각 패킷별로 고유한 타이머가 있어야한다.
  • ACK 수신
    • ACK가 수신되었을 때 그 packet이 window 안에 있다면, 그 패킷을 수신된 것으로 표기한다.
    • 만약 수신된 packet이 send_base라면 send_base는 “**가장 작은 순서 번호를 가진 확인응답되지 않은 패킷”**으로 이동한다.
• Receiver의 event와 action
  • [rcv_base , rcv_base + N - 1] 내의 seq #를 가진 패킷이 도착한다.
    • 만약 out-of-order이면 버퍼에 저장
    • 만약 이 패킷이 수신 윈도의 base와 같은 순서 번호를 가졌다면,이 패킷과 이전에 버퍼에 저장되어 연속적으로 번호를 가진(rcv_base로 시작하는) 패킷들은 상위 계층으로 전달된다.
    • 그 후 수신자는 rcv_base를 다음으로 수신을 기다리고 있는 패킷 번호로 업데이트한다.
  • 범위 밖 패킷 n인경우 [rcv_base-N , rcv_base-1]
    • 이미 수신 및 ACK 응답된 패킷일 경우에는, 그냥 ACK(n)을 다시 보낸다.
      • 송신자가 ACK신호를 놓쳤을 경우 다시 리마인드해주는 역할
    • 이유는 아래에서 설명
  • 기타 범위
    • window 밖에 있는 경우는 그냥 무시

이를 flow로 살펴보면 다음과 같다.

 

 

 

한가지 SR에서 알아두어야 할 점은,

💡 송신자와 수신자는 올바른 수신과 그렇지 않은 수신에 대해 항상 같은 관점을 갖지는 않을 것이다.

라는 점이다. 이는 곧 Sender과 receiver의 window는 같지 않음을 뜻한다.

이해가 잘 안될거니까 아래 사례를 살펴보자. 상황의 가정은 아래와 같다.

• seq #s: 0, 1, 2, 3 (base 4 counting)
• window size=3

 

 

 

• 이 사례에서는, duplicate된 sender의 data가 별 문제없이 잘 전송된다.
• 그러나, 아래 사례를 보자.

 

 

• 이 사례에서는, ACK 응답이 끊겨 Sender의 pkt0에서 타임아웃이 발생해 packt0를 재전송하는상황이다.
• 그러나 Receiver 입장에서는 packet 0,1,2를 받아 window가 이동한 상황인데, receicer 입장에서는receiver은 sender의 행동을 볼 수 없기 때문이다.
• 다섯 번째 패킷의 원래 전송(0)과 첫 번째 패킷의 재전송(0)을 구별할 방법은 없다.

→ 이를 방지하기 위해서,

Window size는 SR 프로토콜에 대한 sequence number 공간 크기의 절반보다 작거나 같아야 한다.

• N = 윈도우 크기
• S = 시퀀스 번호 공간 크기
• 라고 하면, S ≥ 2 X N이어야 한다.
• 시퀀스 번호 공간이 윈도우 크기의 2배이면, 시퀀스 번호가 순환된 이후에도 이전 window의 패킷번호와 현재 window의 패킷 번호가 겹칠 일이 없기 때문이다.

⇒ 이제 많이도 왔다. 이 모든건 TCP를 이해하기 위해서 공부한거였다.