[데이터통신] 3. Data Link Layer(데이터링크 계층, DLC functions)

데이터 링크 계층

데이터 링크 계층이 하는 일은 "node-to-node" 통신이다. 패킷의 최종 목적지엔 크게 관심이 없고, 당장 다음 노드로 잘 보내기만 하면 된다. 유선, 무선으로 연결해 1대1 연결도 가능하고 broadcast도 가능하다. 

 

 

데이터 링크 계층에서 제공하는 서비스를 이해하기 위해서는 데이터 링크 계층의 sublayer를 이해해야 한다.

데이터 링크 계층의 오류를 제어하는 등의 역할을 하는 Data-link-control(DLC) Sublayer와 데이터 전송의 타이밍을 결정하는 Media-Access-control(MAC) Sublayer가 있다. MAC은 broadcast 할 때만 사용되는데, 그 이유는 여러 명에게 송신할 때 충돌이 발생할 수 있기 때문에 어떻게 보낼지 결정하는 MAC이 필요하다.

 

 

DLC Functions

Data-link-Control(DLC)는 두 인접 노드의 통신 과정을 관리한다. DLC는 Framing과 Error Control 기능을 제공한다.

 

Framing

데이터 링크 계층에서는 물리 계층으로부터 들어온 비트열을 프레임으로 바꾸어서 보낼 필요가 있다. 이 계층에서 말하는 framing이란, 메세지를 쪼개서 송신자 주소와 수신자 주소를 추가해 보내는 걸 말한다. 메세지를 최대한 작게 쪼개서 보내야 에러가 발생할 확률이 줄어든다. 이 프레임 크기는 고정이 될 수 있고, 바뀔 수도 있다. 고정이 되면 상관 없지만 프레임의 길이가 매번 바뀌면 프레임 헤더에 길이를 명시해줘야 한다.

 

Character-Oriented Framing

모든 데이터를 8bit로 정의하고 헤더와 트레일러에 정보를 덧붙인다. 헤더에는 출발지와 목적지 주소, control 정보가 저장되어 있다. 트레일러에는 에러 탐지를 위한 redundancy bit가 저장되어 있다. 한 프레임을 구분하기 위해서, 헤더의 앞, 트레일러의 후에 Flag라는 것이 붙는다. 

 

수신자는 Flag 패턴을 보고 프레임의 끝이라고 생각하고 다음 프레임을 정의한다. 그러나, 이때 flag가 아닌 데 flag와 같은 패턴을 가져 헷갈릴 수 있다. 그래서 Byte-Stuffing를 통해 추가 byte를 넣어서 flag와 같은 패턴의 데이터를 오해하는 것을 방지한다. 이때 사용하는 것을 ESC(Escape Character)이라 한다. 이는 미리 정의된 비트 패턴이고 수신자가 ESC 패턴을 읽으면 데이터가 아니라 ESC임을 인식하고, 그 다음에 오는 패턴을 Flag로 오인하지 않고 데이터로 잘 받을 수 있는 것이다.

 

Bit-Oriented Framing

연속된 비트열로 구성되며 8bit의 flag(01111110)를 헤더와 트레일러 앞뒤에 붙여 사용한다. 그러나 Byte-Oriented Framing과 마찬가지로, 데이터를 flag로 오인할 수 있기 때문에 Bit Stuffing이 필요하다. flag에 연속된 6개의 1이 존재하기 때문에 데이터에 연속된 1이 5개 이상 있으면 중간에 0을 붙이는 방법이다. 

 

Error Control

DLC의 또다른 기능은 오류를 제어하는 일이다. 오류를 탐지할 수도 있고 이를 정정할 수도 있다. 오류를 탐지하면 수신자에게 오류 발생을 알리고 프레임을 재전송하도록 하는 기능이 포함되어 있다. 오류를 제어하기 위해서 사용하는 방법이 coding이다. 오류를 제어하는 추가 정보인 redundancy를 실제 데이터에 추가하는 일을 말한다.

일반적으로 오류 탐지가 오류 정정보다 훨씬 쉽다. 오류를 정정하려면 더 많은 비트가 필요하다. 즉, Redundancy를 더 많이 추가해야 한다. 에러가 많은 채널에서는 재전송에 드는 overhead가 더 크기 때문에 redundancy를 늘려준다. 그에 비해 오류를 탐지하는 것을 redundancy가 짧지만 재전송해야 한다.

 

 

Block Coding

메세지를 데이터 비트열로 쪼개는 일을 한다. 메세지를 비트열로 쪼갠 것을 dataword, 비트열에 redundancy를 추가한 것을 codeword라 한다. 

 

이때 redundancy가 너무 짧으면 오류 탐지의 성능이 좋지 않다. 예를 들어 A가 B에 3bit 코드워드를 전송하는데 B는 000을 수신했다고 하자. 이는 유효한 코드워드이기 때문에 데이터 워드는 00으로 추출해 오류가 없다고 판단한다.

 

이때 Minimum Hamming Distance라는 것을 사용한다. Hamming Distance는 같은 크기의 코드 간의 비트 차이를 말하는데, 두 코드를 XOR 연산하고 나온 수의 1의 개수를 세면 된다. Minimum Hamming Distance는 에러를 탐지할 수 있는 최소 Hamming Distance를 말한다. Minimum Hamming Distance 값이 3이라면, 2bit 오류를 탐지할 수 있다. 

Dmin = s + 1이면, s bit 오류를 탐지할 수 있다.

 

 

Linear Block Codes

최근에 사용하는 것은 대부분은 Linear Block Code이다. 두 코드워드에 XOR 연산을 취하고 2로 나눈 나머지 값을 취한다. linear block code에서 Minimum Hamming distance는 1의 개수가 가장 작은 코드워드의 1의 개수를 말한다.

 

Parity-Check Code

에러 탐지에 가장 유명한 기술로, 기존의 dataword에 1bit parity bit를 붙여 오류를 탐지한다. 이때, 4bit codeword에서 1의 개수를 짝수로 만드는 0 또는 1의 parity bit를 추가한다. dataword를 보고 1의 개수가 홀수이면 1을 추가하고, 짝수이면 0을 추가한다는 의미이다. 수신측에서 codeword의 오류를 확인하는 방법은 5bit 전체를 더해서 2로 나눈 수로 syndrome을 생성한다. 이때 syndrome이 0이면 수신, 1이면 오류가 발생했다는 의미로 판단해 버린다.

 

예를 들어, 문제를 풀어보자. 데이터워드 1011에서 코드워드 10111를 생성했다. 이때 5가지 경우의 수를 따져보자.

1. 에러가 없이 10111을 수신한 경우, 수신 측에서 생성한 syndrome이 0이기 때문에, 데이터워드 1011을 정상적으로 추출한다.

2. 데이터워드 a0에 오류가 발생해 10011을 수신한 경우, 수신 측에서 syndrome = 1이다. 따라서 이 수신한 데이터를 버린다.

3. parity bit r0에 오류가 발생해 10110을 수신하였다. 수신 측에서 생성한 syndrome = 1이다. 따라서 수신한 데이터를 버린다.

4. 2bit 오류가 발생해 00110을 수신하였다. 수신 측 syndrome = 0이므로 데이터 워드를 추출한다.

5. 3bit 오류가 발생하여 01011을 수신하여 수신 측 syndrome = 1이므로 수신한 데이터를 버린다.

 

위를 일반화하면, 아래와 같다.

1. 코드워드에서 1의 개수가 4이므로, Dmin = 4이고 3bit 까지 오류를 탐지할 수 있다.
2. Parity-Check Code는 오류가 어디에서 발생했는지 할 수 없기 때문에 오류를 정정할 수 없다.
3. 짝수개 오류는 탐지할 수 없고, 홀수개 오류만 탐지할 수 있다.

 

Cyclic Codes

Cyclic Code는 한 가지 추가 특성을 가지는 linear block code이다. Cycle를 돌면서 codeword를 생성하는 방법으로, 에러를 정정할 수 있다. 이는 Cyclic Redundancy Check(CRC)로 구현된다.

 

책에서 소개하는 방식은 데이터워드에 3bit를 추가해 codeword를 생성한다. encoder와 decoder 동작 과정은 아래와 같다.

 

수신 측에서 생성한 syndrome이 000이 아닌 경우 모두 버린다.

encoder와 decoder은 서로 divisor을 공유하며 값을 비교한다. redundancy bit 길이가 8이라면, divisor은 9bit, 길이가 10이라면 divisor은 11을 설정한다. 

 

CRC의 성능은 아래와 같다.

• single bit 에러만 탐지할 수 있다.
• 3으로 나누어 떨어지는 홀수만 오류를 탐지할 수 있다.

 

Cyclic Code를 사용하면 하드웨어와 소프트웨어에서 구현하기 쉽고 하드웨어에서 특별히 속도가 빠르다. 

 

 

데이터 전송 필수 요소

데이터를 전송할 때 오류를 최대한 줄이려면 어떻게 해야할까?

먼저, 송신자가 프레임을 보내고 나서 잘 받았는지 확인하기 위해서 ACK을 사용한다. 프레임이 정상적으로 도착하면 수신 측에서 ACK을 전송한다.

 

ACK이 사라지면 어떻게 될까? 송신 측에서는 잘 받았다고 ACK이 오지 않았기 때문에 계속 기다려 다음 프레임을 전송할 수 없다. 이때 무한정 기다리는 것을 대비하여 timeout을 사용한다. 일정 시간 동안 ACK이 오지 않으면 같은 프레임을 다시 전송한다. 

 

같은 프레임을 다시 전송하면, 수신 측에서는 재전송된 프레임인지 모르고 서로 다른 프레임으로 착각할 수 있다. 따라서 프레임에 번호를 붙여서 같은 번호가 오면 버려서 중복을 방지한다.

 

만약에, 수신 측이 프레임 0번을 전송했는데, timeout이 발생했다. 그러면 0번 프레임을 재전송하는데, 그 와중에 ACK이 도착했다고 하자. 수신 측은 0번 프레임에 대한 ACK이라고 착각하고 1번 프레임을 전송한다. 이때 1번 프레임이 도착하지 않고 0번 프레임 다시 와서 ACK을 보내고 중복된 0번 프레임을 버린다. 이 상황에서 송신 측에서는 어떤 프레임에 대한 ACK인지 모르기 때문에 오류가 발생한다. 그래서, ACK에도 번호를 부여해서 어떤 프레임이 정상적으로 도착했는지 확인해야 한다.

 

추가로 데이터 없이 ACK만 계속 보내는 것은 낭비이다. 양방향 통신이 가능하기 때문에 양쪽에서 데이터에 ACK을 추가해 보내기도 한다. 이러한 방식을 Piggy Backing이라 한다. 네트워크 혼잡을 조금 줄일 수 있다.

 

Sliding Window Protocol

오류가 발생했을 때, 재전송은 어떻게 해야 할까? 데이터 링크 계층에서 정해놓은 재전송 프로토콜을 알아보자. 

일단 Window 라는 것은 버퍼 사이즈를 의미한다. 송신 측과 수신 측에서 ACK 없이 보낼 수 있는 프레임의 개수를 말한다.

• Stop-and-Wait ARQ : 데이터를 보낸 다음 멈추고 ACK이 올 때까지 기다리는 방식, 보통 윈도우 사이즈 = 1
• Go-Back-N ARQ : ACK이 올 때까지 기다리지 않고 window size만큼 연속적으로 프레임을 전송함. 못 받은 데이터에 대한 NACK이 수신되면 못 받은 데이터부터 다시 재전송
• Selective Repeat ARQ : Go-Back-N ARQ와 비슷한데, 못받은 데이터만 재전송, buffer가 필요
• Adaptive ARQ : 네트워크의 상태에 따라 윈도우 사이즈를 조절해 전송