Data Link Layer

상위 문서: 컴퓨터 네트워크

개요

Data-link layer는 한 노드에서 물리적으로 인접한 노드로 데이터그램을 전송하는 계층이다. 이때 link layer는 각 링크에 따라 개별적으로 구현되므로, 데이터그램은 각기 다른 링크들에서 각기 다른 link layer의 프로토콜을 통해 전송된다. 예를 들어 첫 링크는 Ethernet 프로토콜을, 중간 링크들은 frame relay 프로토콜을, 마지막 링크는 802.11 프로토콜을 활용할 수 있다. 이때 각각의 링크 프로토콜들은 서로 다른 서비스를 제공한다. 예를 들어, 어떤 프로토콜은 reliable data transfer(RDT)를 지원할 수도 있고, 안 할 수도 있다.

용어 정리

노드(node)란 해당 문서와 그 하위 문서에서는 link layer을 실행하는 모든 장치를 의미한다. 노드에는 호스트, 라우터, 스위치, WiFi 액세스 포인트 등이 포함된다. 또한 링크(link): 통신 경로를 따라 인접한 노드들을 연결하는 통신 채널(channel)들을 의미한다. 따라서 데이터그램이 송신 호스트로부터 수신 호스트로 전달되기 위해서는, 그 종단 간(end-to-end) 경로를 구성하는 각 개별 링크들을 통해 이동되어야 한다. 이때 각 링크에서 송신 노드는 데이터그램을 link layer의 데이터 단위인 프레임으로 캡슐화하고 이를 링크로 전송한다.

The Services Provided by the Link Layer

Link layer의 기본적인 서비스는 하나의 통신 링크를 통해 데이터그램을 한 노드에서 인접한 다른 노드로 전송하는 것이다. 하지만 실제로 제공되는 서비스의 세부 사항은 각 link layer의 프로토콜마다 다를 수 있다. 이때, link layer가 제공할 수 있는 가능한 서비스들은 다음과 같다:

• Framing: 거의 모든 link layer의 프로토콜들은 각각의 데이터그램들을 link layer의 데이터 단위인 프레임(frame)으로 캡슐화한 후 이를 링크를 통해 전송한다.
  • 프레임은 데이터 필드와 여러 헤더 필드로 구성된다. 이때, 프레임의 세부적인 구조는 해당 프레임을 전송하는 link layer 프로토콜에 의해서 결정된다.
• Link access: 네트워크에서 두 장치가 데이터를 주고 받을 때, 같은 통신 링크를 여러 장치가 공유할 수 있으며, 이 경우 충돌(collision)이 일어날 수 있고 그로 인해 통신이 실패할 수 있다.
  • 이를 해결하기 위해 MAC 프로토콜이 사용된다. MAC 프로토콜이란 누가, 언제, 어떻게 링크를 사용할지를 정하는 규칙을 의미한다. 이를 통해 여러 노드가 한 통신 매체(medium)를 사용할 때 충돌 없이 데이터를 전송하게 조율하는 역할을 한다.
• Reliable delivery: 어떤 링크 계층 프로토콜은 (RDT)reliable data transfer를 제공하는데, 이는 각 데이터그램을 오류 없이 링크를 통해 전송할 것을 보장한다.
  • 이는 무선 링크(wireless link)와 같이 오류가 많이 일어나는 링크에서 주로 사용된다. 하지만 대부분의 유선 링크(wired link)와 같이 오류가 잘 일어나지 않는 링크에서는 해당 서비스가 불필요한 오버헤드로 간주될 수 있으므로 잘 사용되지 않는다.
• Error detection: 수신 노드의 link layer 하드웨어는 프레임 내의 비트가 원래는 1이었지만, 오류로 인해 0이라는 잘못된 비트를 수신할 수 있다. 이러한 비트 오류를 가지고 있는 데이터그램은 전송할 가치가 없으므로, 많은 link layer의 프로토콜은 비트 오류를 검출할 수 있는 메커니즘을 제공한다.
  • 이는 송신 노드가 오류 검출용 비트(error-detection bits)를 프레임에 포함시키고, 수신 노드가 오류 검사를 수행하는 방식으로 이루어진다.
  • Transport/Network layer도 internet checksum을 통해 제한적인 형태의 오류 검출을 제공하지만, link layer에서의 오류 검출은 더욱 정교하며, 하드웨어를 통해 구현된다.
• Error correction: Error correction은 error detection과 유사하지만, 비트 오류를 검출하는 것 뿐만 아니라, 프레임 내의 정확히 어떤 위치에서 오류가 발생했는지 식별하고, 이를 수정하기까지 한다.
• Half-duplex vs Full-duplex
  • Half-duplex: 양 끝 노드가 서로에게 데이터그램을 전송할 수 있지만, 동시에는 전송할 수 없는 구조이다.
  • Full-duplex: 양 끝 노드가 서로에게 동시에 데이터그램을 전송할 수 있는 구조이다.

Where is the link layer implemented?

Figure 1. Network adapter: Its relationship to other host components

Link layer는 라우터에서는 기본적으로, 입력 포트(input port) 내에 구현되어 있다. 하지만 이는 라우터 내에서의 구현 방식일 뿐, 호스트에서 구현된 방식과 일치하지는 않는다. 실제로, link layer는 모든 호스트 내에 구현된다. Figure 1은 전형적인 호스트의 아키텍쳐를 보여준다. 대부분의 경우 link layer는 네트워크 어댑터(network adapter)에 구현된다. 네트워크 어탭터에는 link-layer controller가 존재하며, 이는 특수 목적의 단일 칩으로, 프레이밍, 링크 접근, 오류 검출 등과 같은 많은 링크 계층 서비스를 구현한다. 또한 네트워크 어댑터는 link-layer는 물론, physical layer의 구현에도 주요한 역할을 한다. 즉, link-layer controller의 대부분의 기능은 하드웨어적으로 구현되어 있으며, 아래는 그 예시이다:

• Ethernet card
• WiFi(802.11) card

송신측에서 controller는 호스트 메모리에 저장된 데이터그램을 가져와, link layer 프레임으로 캡슐화하고, link access 프로토콜을 따르면서 프레임을 통신 링크로 전송한다. 수신 측에서 controller는 프레임을 수신하고, 그 안에서 데이터그램을 추출한다. 또한 해당 link layer의 프로토콜이 error detection 기능을 수행한다면, 송신 컨트롤러는 프레임 헤더에 오류 검출 비트를 설정하고, 수신 컨트롤러는 오류 검출을 수행한다.

또한 figure 1은 네트워크 어댑터가 호스트의 bus에 연결되어 있는 것을 보여주며, 이는 네트워크 어댑터가 다른 호스트의 구성 요소들에게 일반적인 I/O 장치처럼 보인다는 것을 의미한다. 그리고 figure 1은 대부분의 link layer가 하드웨어를 통해 구현되어 있지만, 그럼에도 일부는 호스트의 CPU에서 실행되는 소프트웨어로 구현되어 있음을 보여준다. Link layer의 소프트웨어 구성요소는 다음과 같은 고수준(high-level)의 link layer 기능을 구현한다:

• link-layer addressing information을 조합하기
• controller 하드웨어를 활성화

또한, 수신측에서는 link layer의 소프트웨어가 controller의 Interrupts (Asynchronous Exceptions)#인터럽트(interrupt)에 응답하고, 비트 오류가 존재하는지 검출하며, 데이터그램을 network layer로 넘긴다. 따라서 link layer는 하드웨어와 소프트웨어의 결합을 통해서 구현된다고 볼 수 있으며, 프로토콜 스택>에서 소프트웨어와 하드웨어 사이의 접점이라고 할 수 있다.

Error Detection/Correction

FIgure 2. Error-detection/correction scenario

해당 문단에서는 link layer에서 비트 오류를 검출하고 수정할 수 있는 간단한 기법 몇가지에 대해 다룬다. Figure 2는 해당 문단에서 다룰 상황을 보여준다. 송신 노드에서는, 비트 오류로부터 보호할 데이터 비트 D에 EDC(Error Detection and Correction) 비트가 추가된다. 송신 노드는 D와 EDC를 프레임에 담아 수신 노드로 전송하며, 수신 노드에선 D'과 EDC'이라는 비트열이 수신된다. 수신 노드는 자신이 받은 D'이 송신 노드가 보낸 데이터인 D와 같은 데이터인지 D'와 EDC'만을 이용해 판단해야 한다는 것이다. 이때 주의할 점은 오류 검출이 100% 완벽하지 않다는 것이며, 프로토콜이 낮은 확률로 일부 비트 오류를 놓칠 수 있다는 것이다. 이때 EDC 비트의 크기가 클 수록 더 좋은 수준의 오류 검출과 수정 능력을 제공한다.

Parity Checks

FIgure 3. One-bit even parity

Sigle parity bit를 사용하는 parity checks 기법은 가장 단순한 비트 오류 검출 기법 중 하나이다. Figure 3와 같이 전송하려는 데이터인 D가 d개의 비트로 구성되어 있다고 가정하자. 이때 짝수 parity 방식(even parity scheme)에서는, 송신 노드가 단순히 sigle parity bit를 추가하고, 그 결과인 d+1 개의 비트 전체에서 1의 개수가 짝수가 되도록 parity bit의 값을 정한다. 반대로, 홀수 parity 방식(odd parity scheme)에서는, 1의 개수가 홀수가 되도록 parity bit 값을 설정한다.
수신 노드의 동작 또한 single parity bit를 사용할 경우 매우 단순하다. 수신 노드는 수신한 d+1 개의 비트에서 1의 개수만 세면 된다. 만약 짝수 parity 방식을 사용하는데 1의 개수가 홀수라면, 수신 노드는 최소한 하나의 비트 오류가 발생했음을 알 수 있다. 하지만 짝수 개의 비트 오류가 발생하였다면, 이 경우에는 검출되지 않는 비트 오류(undetected error)가 발생한다. 비트 오류의 확률이 작고, 오류가 각 비트마다 독립적으로 발생한다고 가정한다면, 하나의 패킷 내에서 여러 비트 오류가 동시에 발생할 확률은 매우 작으므로, 이 경우에는 single parity bit로 충분할 수도 있다. 하지만 실제 측정에 따르면, 비트 오류는 독립적으로 발생하기보다는 종종 “버스트(burst)” 형태로 함께 발생한다. 이러한 버스트 오류 조건에서는, 단일 비트 패리티로 보호된 프레임에서 검출되지 않는 오류의 확률이 50%에 이를 수 있다.

Figure 4. Two-dimensional even parity

Single parity 방식을 2차원으로 일반화(two-dimensional generalization)는 해당 방식을 통해 비트 오류의 수정이 가능함을 보여준다. 이 상황은 figure 4에 잘 드러나있다. 해당 상황에서 데이터 D의 d비트는 i개의 행과 j개의 열로 구성되며, 각 행과 각 열에 대해 i+j+1개의 parity 값을 계산한다. 이때 만약 원래의 데이터 D의 비트 d 중 어떤 비트 하나에 오류가 발생하였다면, 그 비트가 위치한 행과 열의 parity가 모두 잘못된다. 따라서 수신 노드는 해당 오류가 발생했음을 검출할 수 있을 뿐 아니라, 어떤 비트가 손상되었는지를 식별하고, 이를 수정할 수 있다. Figure 4에서는 (2,2) 위치의 1값 비트가 손상되어 0으로 바뀐 예시를 보여준다.

Checksumming Methods

Checksum 기법의 작동 원리는 checksum 문서를 참조하십시오.

Checksum 기법은 패킷 오버헤드가 상대적으로 적다. 예를 들어, TCP와 UDP에서의 checksum 기법은 16비트만 사용한다. 하지만 checksum 기법은 CRC 기법과 비교했을 때, 오류에 대한 보호 능력이 상대적으로 약하다. 하지만 checksum 기법은 transport layer에서 자주 사용되는 반면, CRC는 link layer에서 자주 사용된다. Checksum이 오류에 대해 상대적으로 취약함에도 불구하고 transport layer에서 사용되는 이유는 그 오버헤드가 상대적으로 적기 때문이다. Transport layer는 보통 호스트의 OS의 일부로서 소프트웨어로 구현되기 때문에, 최대한 단순하고 빠른 방식인 checksum 기법을 선호한다. 하지만 link layer에서의 오류 검출은 네트워크 어댑터 내의 전용 하드웨어로 구현되며, 이를 통해 더 복잡한 연산을 빠르게 수행할 수 있으므로, 오류를 더욱 잘 잡을 수 있는 CRC 기법을 선호한다.

Cyclic Redundancy Check (CRC)

오늘날의 컴퓨터 네트워크에서 널리 사용되는 오류 검출 기법 중 하나는 CRC(Cyclic Redundancy Check) 코드에 기반한다. CRC 코드는 다항식 코드(polynomial codes)라고도 불리는데, 그 이유는 전송할 bit string을 계수가 0 또는 1인 다항식으로 간주할 수 있기 때문이다. 이때 비트 문자열에 대한 연산은 다항식 산술로 해석된다.

Figure 5. CRC

송신 노드가 수신 노드로 전송하려는 d비트의 데이터 D를 가정하자. 송신자와 수신자는 먼저 r+1비트 길이의 패턴 G를 합의해야 하며, 이를 generator이라고 부른다. CRC 코드의 핵심적인 아이디어는 figure 5에 잘 나타나 있다. 주어진 데이터 D에 대해, 송신자는 r개의 추가 비트 R을 선택하여 D 뒤에 덧붙인다. 이렇게 만들어진 d+r 비트의 패턴이 generator G로 나누어 떨어지도록(즉, 나머지가 0이 되도록) R을 선택해야 한다. 이를 바탕으로 한 CRC를 이용한 오류 검사의 과정은 단순하다. 수신 노드는 수신된 d+r 비트를 G로 나누면 되며, 나머지가 0이 아니면 오류가 발생했다는 것이다. 나머지가 0일 경우는 데이터가 올바르게 전송되었다는 것이다.

이때, 이 연산은 모듈로-2(mod 2)이며, carry, borrow라는 개념이 존재하지 않는다. 이러한 특성 때문에 덧셈, 뺄셈, XOR 연산이 구분되지 않는다. 예를 들면, 아래와 같다:

 101  101  101
+110 -110 ^110 
____ ____ ____
 011  011  011

또한 곱셈과 나눗셈은 이진수의 기본 산술과 동일하지만, 필요한 덧셈과 뺄셈 연산은 carry/borrow 없이 수행된다. 일반적인 2진수 산술처럼, 2^k를 곱하는 것은 비트 패턴을 왼쪽으로 k비트만큼 쉬프트하는 것이다. 이때 송신 노드에게 중요한 것은 R 값을 계산하는 것이며, 아래와 같은 형태로 계산한다:

D $\cdot$ 2r XOR R = n $\cdot$ G

즉, D $\cdot$ 2r XOR R이 G로 나누어 떨어지도록 R을 선택하고 싶은 것이다. 이때 양변에 R을 XOR 하면:

D $\cdot$ 2r = n $\cdot$ G XOR R

이는 D $\cdot$ 2r를 G로 나눈 나머지가 R이라는 것을 말해준다. 이에 따라 아래와 같이 R을 계산할 수 있다.

R = remainder(D $\cdot$ 2r / G)

Figure 6는 다음의 경우에 대해 R값을 계산하는 예시를 보여준다:

Figure 6. A sample CRC calculation

• D = 101110 (d = 6),
• G = 1001,
• r = 3

이 경우 전송되는 9비트는 101110011이며, 이에 따라 직접 계산하면:

D · 2^r = 101110000  
그리고 이것을 G = 1001로 나눈 나머지가 R = 011  

임을 확인할 수 있다.

Multiple Access Protocols

자세한 내용은 Multiple Access Protocols 문서를 참조하십시오.

Switched Local Area Networks

자세한 내용은 Switched Local Area Networks 문서를 참조하십시오.

Link Virtualization: MPLS

MPLS(Multiprotocol Label Switching)는 1990년대 중후반부터 개발된 기술로, 고정 길이 라벨(fixed-length label)이라는 가상 회선 네트워크(Virtual Circuit Network)의 핵심 개념을 도입하여, IP 라우터의 전달 속도를 향상시키는 것을 목표로 한다. 기본적인 아이디어는 가변 길이(prefix)를 사용하는 IP 주소 기반의 longest prefix matching과는 다르게, 고정된 길이의 식별자(레이블)을 사용하여 forwarding 속도를 빠르게 하는 것이다.

Figure 7. MPLS header: Located between link- and network-layer headers

MPLS를 처리할 수 있는 라우터에서 사용되는 프레임의 구조를 보자. Figure 7은 MPLS 지원 장비들 사이에서 전송되는 프레임에 추가적인 MPLS 헤더 필드가 이더넷 헤더와 IP 헤더 사이에 추가되는 것을 보여준다. MPLS 헤더에는 다음과 같은 필드들이 포함된다:

• 라벨(label)
• 3비트 실험용 필드(reserved for experimental use)
• S 비트 1개: MPLS 헤더가 스택(stack) 형태일 경우, 마지막 헤더인지 표시
• TTL(Time-to-Live) 필드

따라서 MPLS 프레임은 MPLS를 처리할 수 있는 라우터 사이에서만 전송될 수 있다. 이때 MPLS를 지원하는 라우터는 종종 라벨 스위칭 라우터(Label-Switched Router)라고 불린다. 이들은 MPLS 프레임의 라벨을 조회하여, 해당 프레임을 즉시 적절한 출력 인터페이스로 전달한다. 즉, 이 라우터는 IP 목적지 주소를 추출하거나, 포워딩 테이블에서 가장 긴 접두사 매칭(longest prefix match)을 수행할 필요가 없다. 하지만 다음과 같은 문제가 발생한다:

1. 라우터는 어떻게 이웃 라우터가 MPLS를 지원하는지 알 수 있을까?
2. 또, 라우터는 어떤 목적지 IP에 어떤 라벨을 부여해야 하는지 어떻게 알까?

Figure 8. MPLS-enhanced forwarding

이 질문에 답하기 위해선, 여러 MPLS 라우터들 간의 상호작용을 살펴보아야 한다. Figure 8에서 라우터 R1 ~ R4는 MPLS를 지원하고, R5와 R6는 일반 IP 라우터이다. 이 상황에서 R1은 R2와 R3에게 다음을 광고(advertise)한다:

“목적지 A로 라우팅할 수 있으며, 라벨 6을 받은 프레임은 A로 전달함”

R3는 R4에게 다음을 광고한다:

“A, D 목적지로 라우팅할 수 있고, 각각 라벨 10, 12를 받은 프레임은 해당 목적지로 전달함”

R2는 R4에게 다음을 광고한다:

“나는 A로 갈 수 있으며, 라벨 8을 받은 프레임을 A로 보냄”

이로 인해서 R4는 목적지 A에 도달할 수 있는 두 가지 MPLS 경로를 가지게 된다. 하나는 라벨 10을 이용해서 인터페이스 0으로 forwarding하는 경로이고, 다른 하나는 라벨 8을 이용해서 인터페이스 1로 forwarding하는 경로이다. 이처럼 R5, R6, A, D와 같은 IP 장비들이 MPLS 인프라(R1~R4)를 통해 연결될 수 있다.

MPLS의 주요한 목적은 IP 주소를 보지 않고, 라벨만으로 포워딩하여 스위칭의 속도를 향상 시키는 것이다. 하지만 MPLS의 진정한 강점은 스위칭 속도 향상이 아니라, 트래픽 제어 기능이다. 예를 들어 앞에서 본 R4는 목적지 A로 가는 두 개의 MPLS 경로를 갖고 있는데, IP 주소를 통한 forwarding에서는 단 하나의 최소 비용 경로만을 선택할 것ㅇ다. 하지만 MPLS는 일반 IP 라우팅으로는 불가능한 경로로도 패킷 전달을 가능하게 하며, 이와 같은 기능을 통해서 운영자는 동일한 목적지로 가는 트래픽을 두 개의 다른 경로로 분산시킬 수 있다. 또한 이러한 특성은 빠른 복구(fast restoration)에도 응용되어, MPLS 경로에 장애가 발생할 경우 사전 계산된 우회 경로(failover path)로 트래픽을 즉시 우회시킬 수 있다.