Data Link Contorl(DLC)
이전 내용에서는 매번 데이터가 전송된다고만 했지, 정확히 각 계층에서 어떤 일이 일어나는지에 대해서는 언급이 없었다.
오늘은 data link 계층에서 데이터를 어떻게 다루는지에 대해 알아보려고 한다.
그래서 이름도 data link control(DLC)이다.
Data link control이 정확히 뭘 하는건데? 라고 물어본다면, 크게 세 가지로 나눌 수 있다.
1. Framing
2. Flow Control
3. Error Control
각각이 뭔지에 대해 하나씩 알아보도록 하자.
Framing
Data link 계층은 상위 계층인 Network 계층에서 데이터를 받아 주소를 붙이고 Physical 계층을 통해 목적지로 보내곤 했다.
이때 "주소를 붙이고" 와 관련된 일들을 Framing 이라고 한다.
왜 하필 framing인가? 라고 물어본다면, 각 계층에서 다뤄지는 객체의 이름을 떠올려보자.
Data link 계층에서 다루는 객체의 이름이 frame 이다.
따라서 상위 계층인 Network 계층으로부터 datagrame을 받아서 frame으로 만들기 때문에 framing이라고 한다.
Character-Oriented Framing
앞으로 종종 언급되겠지만, Character-Oriented라는 말은 Byte-Oriented라는 말과 같다.
즉, 바이트로 이루어져 있다.
어떤 식으로 frame을 만드는가에 대한 답은 위와 같다.
Flag : Frame의 시작 또는 마지막을 의미한다.
Header : 출발지와 목적지에 대한 주소등.. data와 관련된 정보들이 들어있다.
Data : 상위 계층인 Network 계층에서 받은 data, 가변적인 길이(Variable Number)를 가진다.
Trailer : Error 검출을 위해 포함된다.(CRC, Checksum 등)
위를 framing에서 사용되는 protocol이라고 부른다.
그냥 보면 그럴듯 해보이지만, 사실 생각해보면 문제점을 알 수 있다.
만약 data를 이루는 byte들 중에 Flag와 값이 같은 데이터가 들어있으면 어떡하지?
이게 왜 문제냐면, 잘못해서 frame이 요상한 위치에서 끝날 수 있기 때문이다.
Byte Stuffing 과 Unstuffing
그래서 byte stuffing이라는게 나왔다.
먼저 Escape Character(ESC)라는 특별한 값을 정의한다.
그래서 Flag나 ESC와 같은 값을 갖는 부분 앞에 ESC를 추가해준다. --> Byte Stuffing
그리고 나중에 Frame을 받아서 data부분을 볼때, ESC가 보이면 제거하고 ESC 다음값은 데이터로 받아들인다. --> Unstuffing
Flow Control
Data link 계층에서 데이터를 주고받는 두 node를 떠올려보자.
더 간단하게 환경을 바꿔서 한쪽은 데이터를 전송하기만 하고, 다른 쪽은 데이터를 받기만 한다고 생각해보자.
이때 데이터를 전송하는 속도를 $S$, 데이터를 받아서 처리하는 속도를 $R$ 이라고 하면 세가지 상황이 발생할 수 있다.
1. $S == R$
가장 이상적인 상황이다.
주는대로 받아서 처리한다.
아무 문제가 없어 평화롭다.
2. $S < R$
받아서 처리하는 속도가 보내지는 속도보다 빠르다면 어떨까?
잘 처리해서 좀 당황스럽긴 하지만, 별로 문제가 되지는 않는다.
시스템이 조금 비효율적으로 변하는 거 말고는 큰 문제는 없다.
3. $S > R$
보내는 속도가 받아서 처리하는 속도보다 빠르면 어떻게 될까?
보내지는 데이터를 어디다가 저장해놓지 않는 이상, 분명 유실되는 데이터가 존재한다.
받는 쪽이 보내는 쪽이랑 대화를 할 수 있었다면, 분명 적당히 보내면 안되겠냐고 말했을 상황이다.
그래서 준비했습니다..
위 사진에서 보이는 Flow control이 적당히 보내라는 말을 하는 부분이다.
Flow control은 $S > R$ 인 상황을 해결하기 위해 나왔다.
Flow control을 어떤 식으로 할지에 대해 네 가지의 protocol이 준비되어있다.
1. Simple Protocol
2. Stop and Wait Protocol
3. Go-Back-N Protocol
4. Selective-Repeat Protocol
이제 하나씩 힘내서 알아보자.
Simple Protocol
Simple protocol은 $S == R$ 인 상황을 가정하고 만들어졌다.
기억해야할건 위에서 말했듯, 주는 대로 처리한다는 가정을 하고 만들어진 protocol임을 알자.
가정에 의해 보내는 쪽으로 뭔가 알림을 줄 필요(Flow control)도 없다.
Stop-and-Wait Protocol
이름에서 유추해볼 수 있듯, 보내는 걸 멈추고 기다리는 식으로 작동한다.
이제 보내는 쪽과 받는 쪽을 나누어서 어떻게 동작하는 지 알아보자.
먼저 보내는 쪽은 다음과 같이 동작한다.
1. Frame을 전송하고, 동시에 Timer를 정해진 시간만큼 동작시킨다.
이때 전송된 frame을 잠시 저장한다.
ACK가 올때까지 기다린다.
2-1. 시간이 다 가기전에 받는쪽으로부터 ACK가 도착한 경우
저장된 frame을 버린다.
Timer를 멈추고, 1번을 수행한다.
2-2. 시간이 다 갈때까지 받는쪽으로부터 ACK가 도착하지 않은 경우
저장된 frame에 대해 1번을 수행한다.
이때 ACK(Acknowledgment)란 frame을 잘 받았다는 응답이다.
이때 ACK에 CRC라는 error 검출용 코드가 붙어있는데, 이를 확인해서 문제가 생긴 ACK라면 폐기한다.
받는 쪽은 다음과 같이 동작한다.
1. Frame이 잘 도착한 경우
ACK를 전송한다.
어이가 없을정도로 하는게 없다.
만약 frame의 CRC를 확인해서 오류가 있는 frame이라면 폐기한다.
위 flow diagram으로부터 세 가지 상황이 발생할 수 있다.
1. 정상적으로 처리된 경우
Frame이 잘 도착하고, ACK가 잘 전송됐다.
2. 보내진 frame에 문제가 생겼거나, 잃어버린 경우
받는 쪽에서는 아무것도 하지 않기 때문에 timer가 다 끝날때까지 아무일도 일어나지 않는다.
Timer가 정해진 시간만큼 다 돌았다면, 다시 frame이 보내진다.
3. 보내진 ACK에 문제가 생겼거나, 잃어버린 경우
보내는 쪽은 ACK가 오지 않았으므로(혹은 왔는데, 문제가 생겨서 폐기했으므로) 아무것도 하지 않기 때문에 timer가 다 끝날때까지 아무일도 일어나지 않는다.
Timer가 정해진 시간만큼 다 돌았다면, 다시 frame이 보내진다.
이 경우는 문제가 된다.
받는쪽은 이미 잘 처리한 frame을 다시 받아야하기 때문이다.
따라서 이를 위해 주고받는 frame이나 ACK에 숫자를 붙이게 변경되는데, 이는 다른 protocol에서 다시 설명하겠다.
Stop-and-Wait Protocol은 그냥 봐도 낭비되는 시간이 너무 많아보인다.
그렇다고 timer가 동작하는 시간을 줄이자니, ACK가 늦게오는 경우가 걱정되고
timer가 동작하는 시간을 늘리자니, 너무 많은 시간을 낭비하는 것 같다.(ACK에 오류가 생기는 경우를 생각해보자.)
Utilization
얼마나 낭비가 되는지 utilization 측면에서 간단한 상황을 가정해 생각해보자.
우리가 사용하는 line의 대역폭이 1 Mbps($10^6$ bit per sec)이다.
그리고 Stop-and-Wait 때문에 1 bit가 갔다가 오는데(왕복시간, round trip 이라고 한다) 20ms($10^{-3}$ sec) 가 걸린다고 하자.
만약 우리가 보내려는 frame의 크기가 1,000bit 라면, 한 frame을 보내는데 line을 얼마나 활용하는 것일까?
우선 우리는 1 Mbps의 대역폭을 갖는 link를 가지고 있다.
이를 ms단위로 바꿔보면, $\frac{1,000,000 \ \ bit}{1,000 \ \ ms} = \frac{1,000 \ \ bit}{1 \ \ ms}$ 이다.
이때 1 bit 를 보내는데 아무리 용써도 20ms 가 걸리기 때문에 대역폭의 단위를 20ms로 변환해보자.
그럼 $\frac{20,000 \ \ bit}{20 \ \ ms}$ 가 된다.
이는 round trip을 고려할때, 우리는 한번에 20,000 bit를 보낼 수 있다는 말이 된다.
Frame 하나를 보내는데, 크기는 1,000 bit 라고 했다.
Round trip을 고려했을때 최대로 보낼 수 있는 비트의 양은 20,000 bit 이므로 우리는 $\frac{1,000}{20,000} = 0.05$, 즉 링크의 5%만 사용하게 된다는 말이 된다.
따라서 utilization이 매우 안 좋다는 것을 알 수 있다.
Throughput
얼마나 낭비가 되는지 throughput 측면에서 간단한 상황을 가정해 생각해보자.
Frame의 크기는 1,460 byte 이고, round trip 시간이 100ms 라고 해보자.
이 말은 100ms(0.1초) 마다 하나의 frame을 보낼 수 있다는 말이고, throughput은 $\frac{1,460 \ \ byte}{100 \ \ ms}$ 라는 말이 된다.
그럼 1초에는 10개의 frame, 즉 14,600 byte 를 보낼 수 있다는 말이 된다.
만약 link의 대역폭이 10 Mbps( = $\frac{10,000,000}{8}$ Bps) 였다면, link 용량의 1% 밖에 사용하지 않는다.
따라서 Throughput 측면에서도 굉장히 비효율적이라는 것을 알 수 있다.
Go-Back-N Protocol
Go-Back-N Protocol은 Stop-and-Wait과 비교해서 두 가지 요소들이 더 추가됐다.
1. 하나씩만 frame을 보냈던것과는 달리 한번에 여러개의 frame을 보내고, 동시에 여러개의 ACK를 받게된다.
2. 보낸 frame과 ACK에 번호를 붙여서 flow control을 더 효율적으로 진행한다.
이를 처리하기 위해 window라는 개념을 사용한다.
Window
먼저 보내는 쪽의 window를 알아보자.
우선 window의 요소들이 가진 번호는 보낼 frame의 번호가 된다.
왜 0~7을 반복하냐고 묻는다면, 위의 예시가 그렇게 정했기 때문이다.
저 숫자를 정하는 방식부터 알아보자.
먼저 임의의 숫자 $M$을 정한다.
이때 window의 요소들은 0~($M-1$) 까지의 숫자들이 반복해서 나타나는 형태로 이루어진다.
예를들어 $M = 5$ 라고 하면, [0,1,2,3,4,0,1,2,3,4,0, ...] 이다.
이때 각 번호들은 보냈거나, 보내질 frame의 번호가 된다.
이제 이 $M$을 기준으로 window size를 정의한다.
Window size는 0보다 크고 $M$ 보다 작아야하는데, 왜 그런지는 맨 마지막에 설명할 예정이다.
우선은 그냥 $M$보다 작은 수로 설정한다는 것만 알아두자.
정해진 window size를 $S_{size}$ 라고 하자.
위에서 한번에 여러개의 frame을 보낸다고 했다.
이때 보내버린 frame을 outstanding packet 이라고 부른다.
또한 outstanding packet은 아직 해당 packet의 ACK가 오지 않은 상태라는 것을 기억하자.
Outstanding packet들 중, 가장 처음에 보내진 frame을 $S_f$ 라고 하자.
만약 $N$ 개의 frame을 보냈다면, $S_f$ ~ $(S_f + (N-1))$ 까지가 outstanding packet이 된다.
그리고 다음에 보내질 frame들은 $S_f + N$ 부터 시작한다.
이때 다음에 보내질 frame들중 가장 첫번째 frame을 $S_n = S_f + N$ 이라 하자.
다음에 보내질 frame들은 $(S_f + N)$ ~ $(S_f + (S_{size} - 1))$ 이 된다.
나머지 범위 중, $S_f$의 왼쪽 frame 들은 모두 ACK가 도착해서 처리가 완료된 frame들이고, $S_f + S_{size}$ 오른쪽은 아직은 처리할 수 없는 frame이 된다.
이제 받는 쪽의 window를 살펴보자.
window의 요소들은 0~($M-1$) 까지의 숫자들이 반복해서 나타나는 형태로 이루어지는 것은 보낸 쪽과 동일하다.
그러나 window size는 1로 고정된다.
받는 쪽의 window는 항상 다음에 받을 frame의 번호를 보고있다.
이제 보내는 쪽과 받는 쪽이 어떻게 동작할지 알아보자.
먼저 알아둬야 할것은 frame을 보낼때와 ACK를 보낼때, 각 객체들의 번호를 같이 보낸다는 것이다.
이때 번호는 위에서 알아본 window의 요소들이 가진 번호와 같다.
Frame이 보내질때, 해당 frame의 번호를 seqNo 라고 하고
ACK가 보내질때, 해당 ACK의 번호를 ackNo 라고 한다.
이제 보내는 쪽의 동작을 알아보자.
1. $N$개의 frame을 전송하고, timer를 정해진 시간만큼 동작시킨다.
이때 $S_n = S_f + N$ 이다.
Outstanding frame들은 임시로 저장한다.
2. Timer가 동작하는 동안, ACK가 성공적으로 들어왔다면
- ackNo와 $S_f + 1$과 같은 경우
window를 오른쪽으로 한 칸 움직이고 timer를 다시 처음부터 동작시킨다.
$S_f$를 $S_f + 1$로 만든다.
- 만약 ackNo가 $S_f$ 와 같거나, lost 된 경우 무시한다.
3-1. 마지막으로 들어온 ACK의 ackNo와 $S_n$이 같다면
Timer를 종료하고, $S_f$를 $S_n$으로 만든후, 다시 1번을 수행한다.
3-2. Timer가 종료되었다면
$S_n$을 다시 $S_f$로 만든 뒤, 다시 1번을 수행한다.
이때 ackNo가 $S_f$와 같으면 안되는 이유는 받는쪽에서 동작하는 방식을 알아야 이해가 수월하다.
받는 쪽은 다음과 같이 동작한다.
1. Frame이 들어온 경우 seqNo를 확인한다.
현재 window가 보고있는 번호를 $R_n$ 이라고 하자.
이때 seqNo와 $R_n$이 같다면, window를 한칸 오른쪽으로 옮긴다.
ackNo가 $R_n + 1$인 ACK를 전송한다.
seqNo와 $R_n$이 다르다면, ackNo가 $R_n$인 ACK를 전송한다.
Frame이 lost 되었다면 무시한다.(아무 동작을 하지 않는다)
받는 쪽은 항상 frame이 들어왔을 때만 ACK를 보낸다는 것을 기억하자.
받는쪽은 항상 다음에 받을 frame의 번호를 ACK에 담아서 보내게 된다.
따라서 보내는 쪽에서 받은 ACK의 ackNo가 $S_f$와 같다면, 이는 맨 첫번째 frame부터 lost되었다는 말이 된다.
결론적으로 timer가 끝날때까지 기다린 후, 다시 첫 frame 부터 차례대로 보내게 된다.
Flow diagram으로 예시를 들자면 다음과 같다.
맨 처음 packet부터 lost 되었다.
따라서 받는 쪽에서는 seqNo가 1이 아닌 frame이 오면 계속 ACK에 받아야할 frame의 번호를 넣어서 보낸다.
보내는 쪽은 ACK가 오긴 왔는데, ackNo가 $S_f$와 같기 때문에 계속 무시한다.
그리고 결국 timer가 종료된다.
정상적인 경우라면 다음과 같이 flow 가 이루어진다.
위의 경우 한 개의 frame을 보낸다.
받는 쪽은 정상적인 frame을 받았으므로 window를 오른쪽으로 이동한 후, ACK를 전송한다.
보내는 쪽은 정상적인 ACK를 받았기 때문에 window를 오른쪽으로 옮기고 timer를 멈춘다.
Window size는 중요하다.
위에서
Window size는 0보다 크고 $M$ 보다 작아야하는데, 왜 그런지는 맨 마지막에 설명할 예정이다.
라고 했는데 그 이유를 설명하려 한다.
우리가 임의의 숫자 $M$을 $2^m$으로 잡았다고 해보자.($2^m$ 은 아무 의미가 없고, 그냥 교재에서 맘대로 정한 값이다.)
그럼 보내는 쪽이나 받는 쪽 모두 widnow의 요소들이 $0 \ ~ \ (2^m-1)$ 이 반복되는 식으로 나열된다.
위 예시 의 시나리오는 받는 쪽에서 보내는 ACK들이 모두 lost된다고 가정했다.
이런 경우 window size와 $2^m$이 같을 경우 b의 경우가 발생한다.
받는 쪽은 seqNo가 0인 fram부터 $2_m$개의 frame들이 잘 들어왔다.
따라서 frame을 처리할 때마다 window가 계속 오른쪽으로 옮겨진다.
그러다 받는 쪽의 window가 보고있는 번호가 0이 되었을때 사고가 발생한다.
보내는 쪽은 아무런 ACK도 받지 못했기 때문에 다시 seqNo가 0인 frame 부터 보내기 시작한다!
그럼 받는 쪽은 똑같은 frame 들을 다시 받게 되는데, 우리가 정의한 동작에서 이런 상황이 오류라고 판단할 조건들이 아무것도 없다.
즉, 문제가 되는 frame들을 정상적으로 다시 처리하게 된다.
따라서 a의 경우처럼 window size가 $2^m$ 보다 작게 만들어줘야 불필요한 frame들을 다시 받는 참사가 일어나지 않게 된다.
Selective-Repeat Protocol
Go-Back-N 방식은 받는 쪽에서 너무 깐깐하게 받고싶은 frame을 순서대로 하나씩 받았다.
사실 하나씩 받지 않았더라면, 정상적으로 들어온 frame들을 미리 처리해놓을 수 있었을 것이다.
그래서 selective-repeat protocol은 받는 쪽도 여러개를 동시에 받고
문제가 되는 frame이 있다면 문제가 된 frame만 다시 보낸다.
window
보면 window에서 잘 도착한 ACK의 ackNo에 해당하는 요소는 체크한다는 것을 알 수 있다.
Go-Back-N과 가장 큰 차이점이 바로 이 부분인데, 받는 쪽의 window size와 보내는 쪽의 window size가 같다.
또한 보내는 쪽과 마찬가지로 잘 들어온 frame의 seqNo에 해당하는 요소는 체크한다.
근데, 위 사진에서 의문이 드는 부분은 window size가 $2^{m-1}$이라는 것이다.
Window의 최대 크기가 임의로 정한 값 $M$의 절반이라는 것인데, 이는 뒤에서 다시 설명할 예정이다.
이제 자세한 동작을 알아보자.
먼저 보내는 쪽은 다음과 같이 동작한다.
1. $N$개의 frame을 전송하고, timer를 정해진 시간만큼 동작시킨다.
이때 $S_n = S_f + N$ 이다.
Outstanding frame들은 임시로 저장한다.
2. 들어온 ACK의 ackNo가 $S_f$와 같다면 window를 오른쪽으로 한칸 움직인다.
ackNo가 $S_f$와 다르더라도 outstanding frame의 번호와 같은 ackNo가 있다면 체크한다.
그 외 lost된 ACK가 있다면, 무시한다.
3. Timer가 종료되었을때, ACK를 받지 못한 outstanding frame이 존재한다면 다시 보낸다.
그리고 timer를 다시 시작한다.
4. Window가 오른쪽으로 이동되다가 $S_n$과 같아지는 상황이 오면 timer를 종료시키고 1번 동작을 다시 수행한다.
Go-Back-N 과 다른 점은 ACK를 다루는 부분인데, 이는 받는 쪽의 동작을 확인하면서 이해해보자.
받는 쪽은 다음과 같이 동작한다.
1. 도착한 frame의 ackNo와 같은 번호를 갖는 window의 번호를 체크한다.
이후 ackNo와 같은 번호를 가진 ACK를 전송한다.
2. 만약 들어온 frame의 seqNo와 window의 첫 요소의 번호($R_n$)가 같다면 window를 오른쪽으로 한칸 움직인다.
Flow diagram을 보면, 맨 처음 frame은 lost 되어 전송되지 않았다.
그러나 나머지 frame은 잘 전송되었고, 그에 대한 ACK도 잘 받아서 이를 체크한다.
Timer가 멈추면 아직 ACK를 받지 못한 frame이 있는 경우 다시 보내고, timer를 다시 시작한다.
이후 받는 쪽은 맨 첫번째 outstanding frame에 대한 ACK가 들어왔고,
보내는 쪽도 맨 첫번째 frame이 들어와서 처리되었으므로 양쪽 모두 window를 오른쪽으로 이동시킨다.
Window size
위 내용중 window size 부분에서
Window의 최대 크기가 임의로 정한 값 $M$의 절반이라는 것인데, 이는 뒤에서 다시 설명할 예정이다.
라고 했었다.
그 이유를 알아보자.
Go-Back-N 과 마찬가지로 ACK들이 모두 lost 되는 상황이다.
만약 window size가 임의로 설정한 값 $M = 2^m = 4$ 의 절반인 $\frac{2^m}{2} = 2$ 보다 크다면 어떻게 되는지 b에 나와있다.
받는 쪽의 window가 오른쪽으로 이동하다가, 결국 똑같은 frame(seqNo == 0)을 다시 처리해버린다.
반면 설정할 수 있는 최대 크기인 2로 설정하면, 새로 들어온 frame을 자연스레 폐기하게 된다.
'CS > 데이터 통신' 카테고리의 다른 글
| [데이터 통신] Media Access Control(MAC) (2) | 2023.05.29 |
|---|---|
| [데이터 통신] Error Detection 과 Correction (4) | 2023.04.19 |
| [데이터 통신] Data-link Layer 집중탐구 (0) | 2023.04.18 |
| [데이터 통신] Spread Spectrum (0) | 2023.04.12 |
| [데이터 통신] Multiplexing (0) | 2023.04.12 |