Network : Data Link Control : Framing, Flow&Error Control, Protocols, Noisy Channels

Data Link Layer에서 control 담당하는 부분

 

1. Framing

---

Data link layer는 physical layer에서 오는 signal을 frame으로 바꾸거나, frame을 signal로 바꿔서 physical layer로 보낸다.

데이터 배열에 Data, Header, Trailer 등을 넣어서 캡슐화(Encapsulate)를 하는 작업을 말한다.

 

Frame

• Flag는 Frame의 양끝이라고 알려주는 부분이다. 8bit로 되어있다.
• Header에는 Frame에 대한 정보가 들어있다.
• Trailer는 Frame 끝에 존재하며, 이는 Frame이 오류없이 도달했는지 오류검출을 해주기 위해 사용된다.

이 과정에서 framing을 할 때, Fixed-size framing, Variable-size framing을 한다.

 

1-1. Fixed-size Framing

Framing을 할 때 아예 size가 구분자로 쓰는 방법을 말한다. frame 크기를 정해두면, 큰 data, 작은 data 모두 data의 양이 같기 때문에, resource 낭비이기 때문에, 이제 쓰지 않는다.

 

1-2. Variable-size Framing

• Character-Oriented-Protocols : Frame의 data의 크기는 매번 바뀔 것이다. 이는 사용자가 내보내는 size에 의해 달라질 것이다. 이 때, 만약 Flag와 같은 부분이 data 안에 존재한다면 ??? 8bit의 character인 ESC를 넣자! -> ESC는 우리 키보드에서 data 안에 typing 거의 하지 않는 키라서, 이를 구분자로 사용한다.
• Bit-Oriented-Protocols : 거의 대부분의 protocols 에서는 Flag를 "01111110" 으로 지정한다. 위에 ESC 넣는 방법은 혼자 1byte를 차지하기 때문에, Frame의 data 부분의 크기가 너무 방대하게 커지게 된다. 따라서 Bit-Oriented-Protocols 에서는 01111110 을 만드는 것을 막기위해, 1이 5번 반복되면 그 사이에 0을 넣게 된다.

Character-oriented

Bit-oriented

2. Flow & Error Control

---

Data link layer에서 가장 중요한 부분인 Flow Control, Error Control이다.

 

2.1 FLow Control

Flow control은 Frame들을 receiver에게 보내고, 잘 받았는지에 대한 ack (acknowledgement)를 기다린다.

ack가 오기전까지는 data를 한 번에 보내지 않는다. 이러한 이유는 receiver의 buffer (일처리할 때, 너무 많게 되면 data가 쌓이니 잠시 보관해두는 임시저장소) 가 터지지않도록 하기 위함이다. 

-> 나중에 Transport layer도 Socket Buffer 라는 것을 이용해서 Flow Control을 하는데 서로 비슷하게 기억해두면 좋을 듯 하다.

 

2.2 Error Control

Error Control은 data가 변형되지는 않았는지에 대한 부분을 검사한다. 이는 뒤에서 더 자세히 설명할 예정이다.

예를 들면, Physical layer에서 쓰는 Hamming code, Checksum 이 존재한다.

 

 

 

3. Protocols

---

우리가 현대사회 살아가면서 noise가 없는 channel은 없기 때문에, Noiseless channel은 중요하지 않다.

우리는 noisy channel만 확인한다.

 

 

4. Noisy Channels

---

4.1 Stop & Wait ARQ

동작 원리

Stop & Wait 는 말 그대로, "일단 멈추고 기다려보자" 라는 의미를 충분히 이해만 한다면 이해하기는 쉽다.

Stop & Wait에서 Error Detection은 timer가 동작하는 가운데, timer가 time out 된다면, Frame을 다시 보내자!

timer가 time-out 이라면, ack가 도착하지 않았음을 의미하기 때문에, timer의 time-out이 중요하다.

Design of Stop & Wait

Flow Diagram of Stop & Wait

동작

 

 

과정

1. sender는 Frame를 보내고, 잘 도착하면 receiver는 ack1을 보낸다. 이 때 sender의 timer는 start된다. receiver 쪽에서 보낸 ack가 도착하면 timer를 stop한다.
2. 만약 frame이 가다가 lost 된다면, receiver는 ack를 보내지 않기 때문에, sender의 timer는 time-out된다. time out 되면 그 Frame를 다시 보낸다. 
3. 만약 receiver가 Frame를 제대로 받았는데, ack가 가다가 lost 된다면, 이 역시도 sender의 timer는 time-out 된다.
4. 이 역시 그 부분의 Frame를 다시 보낸다. 이 때, 이미 receiver는 Frame를 받았기 때문에, 중복되므로 discard한다.

단점

Stop Wait는 Frame을 하나씩 주고받기 때문에, data를 주고 받는데 시간이 오래걸려 효율성이 좋지가 않다. 

 

 

cf) Bandwidth - delay -product

Bandwidth - delay -product는 receiver로부터 ack가 돌아오는데 얼마나 걸리는지 시간을 확인한다.

Bandwidth-delay product = Bandwidth x delay time

Utilization % of the link = (frame length / Bandwidth-delay product) x 100

이 부분을 계산해서 한다면, Frame이 도착하자마자 뒤에 다른 Frame이 있어, Bandwidth를 낭비하지 않고 계속 쓸수있다.

-> 이 과정을 Pipelining이라고 한다. Data를 끊기지 않고 계속해서 보내는 것을 말한다.

pipelining은 만약 Data의 크기가 크다면, bandwidth-delay-product를 고려해서 data를 끊기지 않고 계속 보낼 수 있다.

 

 

4.2 Go Back N ARQ

동작 원리

Go Back N ARQ는 "window size에 맞춰서 ack가 돌아오기 전에, data를 보내는 것"을 말한다.

만약 Frame이 분실, 손상된다면, 송신자의 window는 그대로 있으며, sender의 timer는 time out 되고, 미결 frame으로 돌아가 그 부분부터 재전송한다.

 

구성

여기에는 sequence number, window size가 존재한다.

sequence number는 frame의 순서를 정해준다. m-bit의 data를 보낸다고 했을 때, sequence number을 2**m -1 만큼을 반복한다. (4bit를 보내면, 0-15번까지 seq No를 정한다.)

window는 한 번에 Data를 보낼 양을 결정한다.

 

window size는 항상 2**m -1 로 해야한다. 그 이유는 밑의 그림으로 보면 답이 나온다.

window size for go back n

단점

만약 window size가 2**m보다 작을 경우 문제는 없지만, window size가 2**m 이라면, 위와 같이 receiver가 ack를 보내지 않은 상황이라면, receiver 입장에서는 모두 0123 받았지만, sender 입장에서는 timer 의 timeout이 걸렸기 때문에, 처음 0123부터 다시 보내게 된다.

(여기서 처음 0123과 그 다음 0123은 당연히 다른 frame이다. sequence number만 같을 뿐!!!!)

 

Flow Diagram for Go Back N

Go Back N의 단점 예시

첫 번째 Flow Diagram을 보면, 처음 initial에서는 Frame 첫 부분을 보내서 ack가 도착하면 Frame을 pipelining해서 보낸다.

Go Back N은 Stop & Wait 처럼 Frame을 하나 보내고 기다리고 하지 않고 Frame을 window size에 맞춰서 보내는 장점이 있다. 또한 Error 가 없다면 pipeline 해두면 다른 방법보다 많이 보내기 때문에, 효율이 급증할 것이다.

 

하지만 두번째 Flow Diagram을 보면, ack가 오지 않은 부분부터, Frame을 다시 보내는 것을 알 수 있다.

이 부분이 단점이다. Discard 하는 Frame이 너무 많기 때문이다. 

 

이를 보완하는 방법이 바로 selective-repeat ARQ이다.

 

 

4.3 Selective-Repeat ARQ

동작 원리

Selective-Repeat ARQ는 Go Back N 을 보완한 방법으로, window size내에서 받지 못한 Frame만 다시 보낸다.

Selective Repeat의 window size는 2**(m-1)로 정해져있다.

만약 window size가 넘어간다면, 위와 같이 sequence number가 맞지 않는다는 것을 알 수 있다.

 

Selective-Repeat ARQ의 window size

 

Flow Diagram of Selective Repeat ARQ

동작 과정

1. Selective Repeat도 Go Back N과 동일하게, 처음 initial을 하나 보낸다. 그 후 window를 옮긴다.
2. 그 후 Frame을 보내는데, sender는 보낸 Frame마다 timer를 걸어둔다. timer는 제대로 받았다면, time out이 발생하고, 제대로 받지 못한다면 NAK를 통해 timer를 재설정 할 것이다.
3. 만약 Frame이 receiver에게 가지 않는다면, receiver는 sequence number를 확인한 후, 없는 번호를 NAK를 통해 sender에게 보내게 된다. NAK를 받고 못 받은 Frame마다 걸어둔 timer는 restart되어 그 해당 Frame만 다시 receiver에게 보내게 된다.
4. 다 받으면 receiver와 sender의 window는 옆으로 옮기게된다.

 

cf) Piggybacking : Full-Duplex Service를 진행할 때, Frame에 ack를 붙여서 보내는 것을 말한다.

Piggybacking

Piggybacking은 위와 같은 방법을 서로의 컴퓨터에서 Data를 주고 받을 때, ACK를 따로 보내는 것이 아니라,

아예 Frame에 묶어서 같이 보내는 것을 의미한다.

이는 양쪽에서 서로 통신할 때, 주로 쓰인다.