Protocol Stack - Data Link Layer

 

Overview

Physical Layer를 다룬 이전 포스팅에 이어 이번 포스팅에서는 Data Link Layer를 다뤄보려 합니다. Signal Element의 형태로 수신자에게 들어온 신호는 Physical Layer를 통해 "011010"과 같은 비트 스트림으로 변환됩니다. (특정 매체의 경우 Forward Error Correction을 거쳐서 어느 정도 보정된 데이터를 올려 보내기도 합니다.) 이 데이터는 Data Link Layer로 전달되어 프레임의 단위로 해석됩니다. Data Link Layer는 이 프레임을 온전한 형태로 안전하게 상위 레이어(대개 Internet Layer)로 전달하는 역할을 합니다.

This layer is concerned with access to and routing data across a network for two end systems attached to the same network. In those cases where two devices are attached to different networks, procedures are needed to allow data to traverse multiple interconnected networks. This is the function of the internet layer

 

이 Protocol Stack 포스팅 시리즈는 Network Protocol Stack에 대한 전반적인 그림을 가볍게 다루는 글이므로 복잡한 수식이나 최적화를 위한 Utilization 계산은 최대한 생략할 예정이며, 특정 부분에 대한 깊은 지식을 요구하는 부분들은 생략하면서 진행될 예정입니다.

 

Frame Sync

Frame은 상위 레이어에서 내려온 datagram을 Data Link Layer에서 메타데이터를 추가해 한번 감싼 형태의 데이터로, 이 레이어에서 통신의 단위가 됩니다. 하지만 결국 이 Frame도 Physical Layer로 내려가 인코딩 되어 매체를 통해 전송된 뒤, 다시 수신 측의 Physical Layer의 decoding을 거쳐 Data Link Layer로 해석되어야 하며, 이는 수신 측에서 송신 측에서 보낸 Frame의 시작 부분과 끝 부분을 정확하게 구분할 수 있어야 한다는 것을 의미합니다. 

 

 

Data Link Layer에서는 전형적으로 각 프레임의 앞과 뒤에 특정 bit 패턴을 추가로 넣는 "bit stuffing"을 사용해서 Frame Sync를 수행합니다. 즉, 송신 측에서 프레임과 프레임사이에 특정 패턴의 비트를 추가해서 전송하고 수신 측에서 이 패턴의 비트를 감지하면, 이를 프레임을 구분하는 기준으로 사용해서 프레임을 구분하는 것입니다. (frame 앞에 붙는 비트를 preamble, 뒤에 붙는 비트를 postamble이라고 합니다.) 

In data transmission and telecommunication, bit stuffing (also known—uncommonly—as positive justification) is the insertion of non-information bits into data. Stuffed bits should not be confused with overhead bits.

 

 

 

Flow Control

네트워크쪽 관련된 글들을 읽거나 검색을 해보셨다면 "ACK", "NACK"와 같은 용어를 어디선가 들어보신 적이 있으실 것입니다. 이는 "Acknowledged", "Not Acknowledged"의 약자로, Flow Control System에서 사용되는 용어들 중 하나입니다. (Flow Control System에서 사용한다고 해서 반드시 Data Link Layer에 국한된 용어는 아닙니다. 이후 포스팅에서도 설명하겠지만, Transmission Layer(TCP / IP)도 Flow Control System을 갖고 있으며, 여기서도 동일한 용어가 다시 등장하게 됩니다.)

 

Flow Control은 송신 측에서 수신자가 받을 수 있을 만큼의 데이터만 전송할 수 있도록 보장하는 기술입니다. 즉, 송신자가 보낼 데이터가 아직 남아있다 하더라도, 수신 측의 Buffer가 가득 차있는 상태라면 바로 데이터를 전송하지 않고 기다려 안정적인 전송이 가능하도록 합니다. 이 Flow Control에는 Stop & Wait과 Sliding Window 방식이 있으며, 각각의 방식은 이후 Error Control 방식에도 영향을 미치게 됩니다.

 

Flow control is a technique for assuring that a transmitting entity does not overwhelm a receiving entity with data. The receiving entity typically allocates a data buffer of some maximum length for a transfer. When data are received, the receiver must do a certain amount of processing before passing the data to the higher-level software. In the absence of flow control, the receiver’s buffer may fill up and over- flow while it is processing old data.

 

Stop & Wait

가장 단순한 Flow Control Scheme입니다. 송신 측에서 프레임을 하나 보내고, 수신 측에서 이 프레임을 정상적으로 수신했으면 송신 측에 ACK 프레임을 전송합니다. ACK 프레임을 받기 전까지 송신 측은 추가적인 Frame을 보내지 않고 기다리다가(Stop & Wait) ACK 프레임이 도착하면 다음 프레임을 전송하고, ACK 프레임이 도착하지 않으면 특정 Timeout 시간까지 기다리다가 Timeout이 나면 동일한 프레임을 다시 전송합니다.

 

ACK는 여러가지 이후로 도착하지 않을 수 있습니다. 수신 측에서 프레임을 받지 못했거나, 수신 측에서 프레임을 받았지만 ACK 프레임이 중간에 유실되어 송신 측에서 ACK 프레임을 받지 못하는 경우입니다. Stop & Wait는 이 모든 케이스에 대응이 가능하지만, 하나의 프레임이 완전히 전송이 성공된 이후에야 다음 프레임을 보낼 수 있으므로, 다량의 프레임을 보내야 하는 경우에는 성능이 다소 떨어지는 문제가 생기게 됩니다.

 

 

Sliding Window

Sliding Window 방식은 앞서 설명한 Stop & Wait 방식의 단점(하나의 프레임에 대한 ACK가 도착해야만 다음 프레임을 보낼 수 있으므로, 여러 개의 프레임을 보내야 할 때 성능이 떨어짐)을 개선하기 위한 방식입니다. 특정 크기의 윈도우(W)를 정해두고, 프레임을 ACK 없이 W개까지 연속으로 보냅니다. 송신측에서는 W개의 프레임을 보내고 ACK이 하나 도착하면  그다음 프레임을 하나 보내고, 그 와중에 또 ACK이 하나 도착하면 또 그다음 프레임을 하나 보내는 식으로 최대 W개까지 연속적으로 프레임을 보낼 수 있도록 하여 성능을 개선합니다. 프레임을 보내는 방식이 창문을 열고 닫는 것과 비슷하다고 하여 Sliding Window라는 이름이 붙게 되었습니다.

 

아래 예시를 통해 Sliding Window 방식이 어떻게 동작하는지 간단하게 살펴보도록 하겠습니다. A가 송신 측, B가 수신 측이라고 가정하겠습니다. A는 7개의 Sending Window를 가지고 있으며, B는 7개의 Receiving Window를 갖고 있습니다. (Full-Duplex 방식에서는 양측 다 Sending Window와 Receiving Window를 갖습니다.) A에서 0~2번까지 3개의 프레임을 보냅니다. 아직 ACK가 하나도 도착하지 않은 상황이므로 A는 ACK 없이 최대 4개의 프레임을 더 보낼 수 있습니다. B가 3개의 프레임을 받은 뒤에 이에 대한 ACK를 보내면(실제 시스템에서는 ACK도 오버헤드이기 때문에 여러 개의 ACK를 하나로 묶어서 보내기도 합니다.) A는 다시 3개만큼 Window 개수가 늘어나므로 다시 최대 7개의 프레임을 보낼 수 있는 상황이 됩니다. A가 다시 3~6번 프레임을 보내고 B가 3번이 도착했을 때, ACK를 보내고 이후 4~6번 프레임을 수신한 경우, A는 7개의 프레임을 보낼 수 있는 상황에서 4개의 프레임을 보냈으므로 남은 윈도 크기가 3개인 상황에서 4번 프레임에 대한 ACK만 도착했으므로 남은 윈도 크기는 1개만큼 커진 4개가 됩니다. 

 

 

 

 

Stop & Wait 방식으로 통신했다면 F0을 보내고, 이에 대한 ACK을 받은 뒤에야 F1을 보낼 수 있었겠지만, Sliding Window 방식을 사용하면 ACK 없이 최대 7개의 프레임을 빠르게 보낼 수 있으므로 Propagation Delay가 줄어들어 성능이 좋아집니다. 

 

 

Error control

모든 프레임이 성공적으로 전송된다면 좋겠지만, 실제 네트워크 환경에서는 여러 가지 이유로 패킷이 유실되거나 변경됩니다. 따라서 상위 레이어로 안정적인 데이터를 보낼 책임이 있는 Data Link Layer는 이 오류를 수정할 책임도 지닙니다. Data Link Layer에서는 크게 Forward Error Control과 Backware Error Control의 2가지 방식으로 에러를 수정합니다.

 

Forward Error Control

이전 포스팅에서도 살펴보았던 것처럼 프레임에 추가적인 정보(Data Redundancy)를 추가하여 수신 측에서 재전송 없이 오류를 수정하는 방식을 Forward Error Control이라고 합니다. CRC나 Parity Check를 통해 에러를 감지하고(Error Detection), BCH Code, Hamming Code 등의 에러 수정 방식(Error Correction)을 사용하여 에러를 재전송 없이 수정합니다. Error Correction 알고리즘은 다소 복잡한 방식을 통해 수행되므로 자세한 내용은 아래 링크를 참고해 주세요

https://en.wikipedia.org/wiki/BCH_code

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

 

Backward Error Control

Forware Error Correction만으로 에러가 수정될 수 없는 경우들도 자주 발생하며, 이 경우에는 수신 측에서 에러를 수정하기보다는 송신 측에 프레임을 재전송하는 방식으로 에러를 수정하는 방식을 사용합니다. 이를 Backward Error Control이라고 하며 Automatic Repeat reQuest(ARQ)라는 방식을 사용해 프레임 재전송을 요청합니다.

 

Stop and Wait ARQ

Stop and Wait 방식에서 발생하는 프레임 에러에 대해 재전송을 요구하는 방식으로 한 번에 하나의 프레임만 전송하고, ACK을 기다리기 때문에 송신 측에서는 ACK이 오지 않으면 설정해 둔 Timeout시간까지 기다렸다가 프레임을 다시 보내고, 수신 측에서는 프레임을 받으면 ACK을, 받았지만 처리할 수 없으면 NACK을 보내는 방식으로 작동합니다. 

 

Go-back-N ARQ

Sliding Window에서 발생하는 프레임 에러에 대해 재전송을 요구하는 방식으로 수신 측에서 여러 개의 프레임을 받았지만 그중 하나에서 에러가 감지되면, 그 이후의 프레임을 모조리 버리고 재전송을 요구합니다. 예를 들어 아래의 그림에서 송신 측이 4, 5, 6번 프레임을 보냈지만 4번 프레임에서 에러가 발생한 경우 수신 측은 정상적으로 도착한 5, 6번 프레임도 버리게 되며, 이에 따라 송신 측에서는 4, 5, 6번 프레임을 모두 다시 보내야 합니다. 이는 아래에서 설명할 Selective-reject 방식보다 전송 효율이 떨어지지만, 구현이 간단하고 수신 측에서 별도의 버퍼를 관리할 필요가 없다는 이점으로 인해 널리 사용되는 ARQ 방식입니다.

If the destination station detects an error in a frame, it may send a negative acknowledgment (REJ = reject) for that frame, as explained in the fol- lowing rules. The destination station will discard that frame and all future incoming frames until the frame in error is correctly received. Thus, the source station, when it receives a REJ, must retransmit the frame in error plus all succeeding frames that were transmitted in the interim.

 

Selective-reject ARQ

Go-back-N 방식과 마찬가지로 Sliding Window에서 발생하는 프레임에 에러에 대해 재전송을 요구하는 방식입니다. 다만 Go-back-N과는 다르게 여러 개의 프레임 중 하나의 프레임에서 에러가 발생할 경우, 해당 프레임만 재전송을 요구하므로 전송효율이 높아집니다. 대신에 수신 측에서 별도의 버퍼와 로직을 통해 어떤 프레임에서 에러가 났고 어떤 프레임은 성공했는지에 대한 관리를 해주어야 하며 이로 인해 복잡도가 높아집니다. 이 방식은 프레임을 재전송하는 데 걸리는 시간이 오래 걸리는 경우(e.g 위성통신)에 주로 사용됩니다.

 

With selective-reject ARQ, the only frames retransmitted are those that receive a negative acknowledgment, in this case called SREJ, or those that time out.

Selective reject would appear to be more efficient than go-back-N, because it minimizes the amount of retransmission. On the other hand, the receiver must maintain a buffer large enough to save post-SREJ frames until the frame in error is retransmitted and must contain logic for reinserting that frame in the proper sequence. The transmitter, too, requires more complex logic to be able to send a frame out of sequence. Because of such complications, selective-reject ARQ is much less widely used than go-back-N ARQ. Selective reject is a useful choice for a satellite link because of the long propagation delay involved.

 

 

 

High-level Data Link Control (HDLC)

지금까지 Data Link Layer가 무엇이며 어떤 역할을 수행하는지에 대해 고수준의 추상화 단계에서 간단하게 살펴보았습니다. 아래에서 소개할 HDLC라는 개념은 위에서 살펴본 Data Link Layer의 기능을 수행하기 위해 정의된 프로토콜 입니다. 이는 현재 사용되는 프로토콜의 기반이 되는 중요한 개념들을 많이 포함하고 있기 때문에 Data Link Layer가 실제로 어떻게 주어진 역할을 수행하는지를 이해하는데 많은 도움을 줍니다. 

The most important data link control protocol is HDLC (ISO 3009, ISO 4335). Not only is HDLC widely used, but it is the basis for many other important data link control protocols, which use the same or similar formats and the same mechanisms as employed in HDLC.

 

Frame Structure

Data Link Layer의 기본 데이터 단위는 Frame 입니다. HDLC 프로토콜에서는 이 Frame을 다음과 같은 구조로 구성합니다.

 

Flag

Flag는 수신측에서 Frame Sync를 맞추기 위해 추가한 bit를 의미합니다. 

Flag fields delimit the frame at both ends with the unique pattern 01111110. A single flag may be used as the closing flag for one frame and the opening flag for the next. On both sides of the user-network interface, receivers are continuously hunting for the flag sequence to synchronize on the start of a frame.

 

Control

Control 필드는 프레임의 종류를 구분하기 위해 사용됩니다. 프레임은 데이터를 전송하기 위한 Information Frame, ACK, NACK를 전송하기 위해 사용되는 Supervisory Frame, 링크 관리를 위해 사용되는 Unnumbered Frame으로 구분되며 이를 Control 필드의 비트를 사용해 구분합니다. Information Frame의 경우 Duplex 방식에서 사용될 때, A에서 B에게 데이터를 전송할 때 사용하는 Information Frame에 B가 전송한 데이터를 받았다는 응답(ACK)을 포함해서 보내기도 하는데, 이를 Piggyback ACK라고 합니다. (즉, ACK를 보내기 위해서 무조건 Supervisory Frame을 사용해야 하는 것은 아니며, Piggyback ACK를 사용해서 Duplex 방식에서 전송 효율을 높일 수 있습니다.)

HDLC defines three types of frames, each with a different control field format. Information frames (I-frames) carry the data to be transmitted for the user (the logic above HDLC that is using HDLC). Additionally, flow and error control data, using the ARQ mechanism, are piggybacked on an information frame. Supervisory frames (S-frames) provide the ARQ mechanism when piggy- backing is not used. Unnumbered frames (U-frames) provide supplemental link control functions.

 

 

FCS

FCS는 Frame Check Sequence의 약자로 CRC와 같이 Frame의 Error Detection을 수행하기 위한 추가적인 비트를 의미합니다.

 

Conclusion

지금까지 Physical Layer에 이어 Data Link Layer가 무엇이며, 어떤 기능을 하는지에 대해 간략하게 살펴보았습니다. Data Link Layer는 인접한 두 노드 간의 데이터 전송이 안정적으로 수행될 수 있도록 Flow Control과 Error Control을 제공합니다. 이 레이어의 기능을 수행하기 위한 프로토콜로 HDLC라는 프로토콜이 있으며, 이 프로토콜은 Flag, Control, FCS와 같은 추가적인 정보들을 프레임에 포함함으로써 레이어의 기능을 수행하는데 도움을 줍니다.

 

다음 포스팅에서는 Ethernet과 IP를 다루는 Network Layer에 대해 살펴보도록 하겠습니다.