[Network] 링크 계층과 다중 접속 프로토콜

네트워크 계층의 핵심은 '송신 호스트에서 수신 호스트로 패킷을 전달'을 수행한다는 것입니다.
네트워크 계층의 역할이 끝나면, 데이터그램은 일련의 유무선 통신 링크와 스위치들을 거친 뒤에 목적지 호스트에 도달하게 됩니다. 그리고 이제부터 프로토콜 스택상 네트워크 계층에서 '링크 계층'으로 내려옵니다.

링크 계층이 어떻게 동작하는지 이해하기 앞서 몇가지 용어와 링크 계층이 수행하는 역할이 무엇인지 먼저 알아보겠습니다.
링크 계층 프로토콜을 실행하는 장치들을 '노드(node)'라고 부르고 여기에는 호스트, 라우터, 스위치 등이 포함됩니다. 또한 통신 경로상의 노드들을 연결하는 통신 채널을 '링크(link)'라고 부릅니다.

링크 계층의 기본 서비스는 통신 링크를 이용해 데이터그램을 한 노드에서 인접 노드로 이동시키는 것이지만, 아래와 같은 서비스도 제공합니다.

• 프레임화 : 네트워크 계층 데이터그램을 링크상으로 전송하기 전에 링크 계층 프레임으로 캡슐화합니다.
• 링크 접속 : 여러 노드가 하나의 링크를 공유하는 경우, 전송된 프레임은 충돌할 수 있습니다. 이러한 채널에서는 프레임을 전송하는 규칙이 필요하고, 이 규칙을 MAC 프로토콜이라고 부릅니다.
• 신뢰적 전달 : 링크 계층에서의 신뢰적 전달은 오류가 발생한 링크에서 오류를 정정하는 방법을 사용합니다. 주로 무선 링크처럼 오류율이 높은 링크에서 주로 사용되며, 낮은 비트 오류율을 가진 유선 링크에서는 불필요한 오버헤드가 되기에 신뢰적 전달 서비스를 제공하지 않기도 합니다.

링크 계층이 위와같은 역할을 수행한다는 사실을 알게 되었습니다. 그러면, 링크 계층은 어디에 구현되어 있을까?에 대해 생각해봅시다.
글의 초반에 언급했지만, 링크 계층 프로토콜을 실행하는 장치인 '노드'에는 호스트, 라우터, 스위치 등이 포함됩니다.

음.. 그런데 라우터는 네트워크 계층의 역할을 수행하는 장치인데, 링크 계층 프로토콜도 실행하는 장치라니.. 혼동이 옵니다. 이는 라우터의 내부 구성요소를 열어보면 이해할 수 있는데요, 라우터는 아래의 그림과 같이 구성되어 있습니다.

라우터의 내부에는 스위치 구조가 존재합니다. 단순히 라우터 내부에는 스위치가 존재한다 라고 외우기보다는 조금 더 논리적으로 생각해봅시다.
'패킷'이라는 추상적인 메시지는 결국 물리 계층을 타고 전달될 것입니다. 그리고 경로를 설정하고 패킷을 전송하는 라우터도 근본적으로는 이 신호를 받고 보내야 하는데, 이를위해 하위 계층을 수행할 수 있는 장치가 필요할 수 밖에 없습니다. 따라서 라우터 내부에 스위치가 존재하는 것은 어쩌면 당연하다고 볼 수 있습니다.

그러면 종단 시스템에서 링크 계층은 어떻게 구현되어 있을까요? 아래의 그림을 보겠습니다.

대부분의 컴퓨터에서 링크 계층은 '네트워크 인터페이스 카드 (Network Interface Card, NIC)'로 알려진 네트워크 어댑터에 구현됩니다. 네트워크 어댑터의 중심에는 '링크 계층 제어기'가 있고, 이 제어기는 앞서 언급한 링크 계층 서비스들을 제공합니다.

여기서 주의해서 볼 것이 있는데, 바로 CPU에서도 링크 계층 프로토콜 서비스를 제공 한다는 것입니다.
이를 해석해보면, CPU에서 실행되는 소프트웨어에서도 링크 계층 기능을 제공한다는 것이고, 링크 계층이 하드웨어와 소프트웨어의 조합으로 구성된다는 사실을 알 수 있습니다. 소프트웨어로 제공하는 링크 계층 서비스는 '제어기 하드웨어 활성화', '링크 계층 주소 정보 조립' 등이 있습니다.

이제 링크 계층의 다중 접속 프로토콜에 대해 알아보겠습니다.
링크 계층 채널은 근본적으로 '브로드캐스트 채널', '점대점 통신채널' 2가지가 존재합니다.
이 중 '브로드캐스트 채널'은 다수의 노드가 공유되는 채널에 동시에 프레임을 전송할 수 있고, 모든 노드가 동시에 여러개의 프레임을 받기 때문에 프레임들이 수신자에서 '충돌'하게 됩니다. 그리고 프레임이 충돌하면 일반적으로 어떤 수신 노드도 프레임의 의미를 파악할 수 없게 됩니다. 따라서 충돌에 관련된 모든 프레임은 손실되며, 브로드캐스트 채널은 충돌 기간만큼 낭비됩니다.

이렇게 다수의 노드가 활성화된 브로드캐스트 채널이 제대로 동작하도록 보장하기 위해서는 노드의 전송을 조정할 필요가 있습니다. 그리고 이를 위해 필요한 것이 '다중 접속 프로토콜'입니다.

대표적인 다중 접속 프로토콜로는 '채널 분할 프로토콜', '랜덤 접속 프로토콜', '순번 프로토콜'이 있는데 하나씩 살펴보도록 하겠습니다.

채널 분할 프로토콜
채널 분할 프로토콜은 채널을 공유하는 모든 노드가 브로드캐스트 채널의 대역폭을 분할할 수 있게 해주는 프로토콜로, 대표적으로 3가지가 존재합니다.

1. 시분할 다중화(Time Division Multiplexing)
TDM은 시간을 '시간 프레임'으로 나누고, 각 시간 프레임을 '시간 슬롯'으로 나눕니다. 그 뒤에 각 시간 슬롯은 N개의 노드에게 각각 할당되며 노드는 전송할 패킷이 있을 때마다 TDM 프레임에서 자신에게 할당된 시간 슬롯 동안 패킷 비트들을 전송합니다. 아래의 그림은 노드가 4개인 TDM에 대한 간단한 예시를 보여주는 그림입니다.

TDM은 충돌을 제거할 수 있고 공정하다는 장점이 있지만, 2가지 단점을 가지고 있습니다.
채널이 N개의 노드를 지원하고 전송률이 R bps라고 할때,

1) 전송할 패킷이 단 하나인 경우에도 노드 전송률은 평균 R/N으로 제한됩니다.
2) 노드가 전송 순서상 자신의 차례를 항상 기다려야 합니다.

2. 주파수분할 다중화(Frequencydivision Multiplexing, FDM)
TDM은 브로드캐스트 채널을 시간으로 공유하는 반면, FDM은 채널을 주파수로 나눠서 각 주파수를 N개 노드 중 하나에게 할당합니다. 즉, 하나의 큰 R bps 채널로부터 N개의 R/N bps의 작은 채널을 만듭니다.

FDM은 TDM과 비슷한 장단점을 가집니다.
FDM은 충돌을 피하고 N개의 노드에게 대역폭을 균등하게 분할할 수 있습니다. 그러나 전송할 패킷을 가진 노드가 단 하나일지라도 노드는 R/N의 대역폭으로 한정된다는 치명적인 단점이 있습니다.

3. 코드 분할 다중화(Code Division Multiple Access, CDMA)
TDM과 FDM은 각각 시간 슬롯과 주파수를 노드에게 전달하지만, CDMA는 다른 '코드'를 각 노드에게 할당합니다.
각 노드는 이 코드를 이용해 전송하는 데이터 비트들을 인코딩합니다. 일종의 암호화를 하는 것이죠. 이 CDMA 네트워크에서 코드를 신중하게 결정하면 여러 노드들은 '동시에' 채널을 이용할 수 있고 충돌이 발생하더라도 수신자들이 인코딩된 데이터 비트를 정확히 디코딩하면 정확하게 수신할 수 있는 특징이 있습니다. CDMA는 무선 네트워크와 밀접하게 관련되어 있으므로 후에 다시 등장할 것입니다. 지금은 TDM과 FDM처럼 다중 접속 채널 사용자에게 할당될 수 있다는 정도만 알아둡시다.

랜덤 접속 프로토콜
다중 접속 프로토콜의 두번째 종류는 '랜덤 접속 프로토콜'입니다. 랜덤 접속 프로토콜의 핵심은 '전송 노드가 항상 채널의 최대 전송률인 Rbps로 전송'한다는 것입니다.

만약 충돌이 생기면 충돌과 관련된 노드는 프레임이 충돌 없이 전송될 때까지 계속 재전송합니다. 대신, 재전송하기 전에 '랜덤 지연 시간'만큼 대기하고 재전송하며 이 지연 시간은 각 노드가 스스로 선택합니다.
대표적인 랜덤 접속 프로토콜로는 4가지가 존재하는데, '알로하', '슬롯 알로하' 'CSMA', 'CSMA/CD'가 있습니다. 
비슷한 이름에서 유추할 수 있듯이 알로하-슬롯 알로하, CSMA-CSMA/CD는 서로 연관되어 있습니다. 알로하를 개선한 것이 슬롯 알로하, CSMA를 개선한 것이 CSMA/CD이기 때문에 2가지를 기준으로 살펴보겠습니다.

1. 슬롯 알로하
슬롯 알로하는 가장 단순한 랜덤 접속 프로토콜입니다. 슬롯 알로하에 대한 설명에 앞서 아래와 같은 환경을 가정하겠습니다.

• 모든 프레임은 정확히 L비트로 구성됩니다.
• 노드는 슬롯의 시작점에서만 프레임을 전송하기 시작합니다.
• 각 노드는 언제 슬롯이 시작하는지 알 수 있게끔 동기화되어 있습니다.
• 한 슬롯에서 2개 이상의 프레임이 충돌하면 모든 노드는 그 슬롯이 끝나기 전에 충돌 발생을 알게 됩니다.

각 노드느 충돌이 발생하면 확률 p로 재전송합니다. 그리고 이 확률은 모든 노드가 각자 독립적으로 계산합니다.

위의 그림은 슬롯 알로하가 동작하는 방법을 보여주는 그림입니다. 슬롯 알로하는 크게 아래와 같이 동작하는 매우 단순한 프로토콜입니다.

• 노드는 전송할 새 프레임이 있으면, 다음 슬롯이 시작할 때까지 기다렸다가 그 슬롯에 전체 프레임을 전송합니다.
• 만약 충돌하지 않으면 노드는 성공적으로 자신의 프레임을 전송할 것입니다. 따라서 프레임을 재전송할 필요가 없습니다.
• 만약 충돌하면 노드는 그 슬롯이 끝나기전 충돌을 검출합니다. 노드는 그 프레임이 충돌 없이 전송될 때까지 확률 p로 해당 프레임을 다음 슬롯들에서 재전송합니다.

슬롯 알로하는 여러 장점을 가지고 있습니다. 채널 분할과는 달리, 슬롯 알로하는 하나의 활성 노드로 하여금 채널의 전속력 R로 계속해서 프레임을 전송할 수 있도록 허용합니다. 또한 각 노드가 충돌을 감지하고 언제 재전송할지 결정하므로 상당히 분산화되어 있습니다.

하지만 효율이 떨어지는 문제를 가집니다. 위의 그림을 보면 활성 노드가 많이 있으면 슬롯의 충돌이 그만큼 많이 발생하고, 결과적으로 해당 시간 슬롯은 낭비가 되는 것을 볼 수 있습니다. 또한 모든 활성 노드들이 확률적인 전송 정책 때문에 전송을 억제하는 경우 일부 슬롯이 빈다는 문제가 발생합니다.

2. CSMA/CD
슬롯 알로하에서 노드가 전송 여부를 결정하는 것은 브로드캐스트 채널에 접속되어 있는 다른 노드의 활성 여부와 무관합니다. 쉽게말해, 노드가 전송을 시작할 때 다른 노드의 전송 여부를 주의하지 않고, 다른 노드가 자신의 전송을 간섭하는 경우에도 전송을 중지하지 않습니다.
이 두가지를 개선한다면, 충돌 시간이 줄어들 것이고 결과적으로 교환되는 데이터의 양을 증가시킬 수 있을 것이라 기대하는 프로토콜이 바로 CSMA/CD 입니다. 

CSMA/CD는 2가지 규칙이 지켜져야 하는데요, 아래와 같습니다.

• 캐리어 감지 : 노드가 데이터를 전송하기 전 채널을 확인합니다. 만약 다른 노드가 프레임을 채널로 전송하고 있으면, 노드는 충돌이 일어날 것이라고 판단하여 전송하지 않습니다.
• 충돌 검출 : 만약 다른 노드가 방해 프레임을 전송하고 있음을 검출하면 자신의 전송을 중단하고, 랜덤한 시간동안 대기합니다.

위의 그림은 CSMA/CD의 동작 방식을 보여주는 그림입니다. 만약 특정 노드가 전송하려는 시점에 다른 노드가 전송중인것을 파악하면 자신의 전송을 억제하게 됩니다. 
시간 t0에 노드 B는 다른 노드가 아무도 전송하지 않으므로 채널이 비어있다고 판단하여 전송을 시작합니다. 이때 B가 전송한 비트들은 브로드캐스트 매체를 따라 양방향으로 전파됩니다.

시간 t1에 노드 D가 전송할 프레임이 생겼다고 합니다. 노드 B가 t1 시점에 전송하고 있음에도 아직 B가 전송한 비트들이 D에 도달하지 못했고, D는 채널이 비어있다고 판단해 전송을 시작합니다. 

하지만, B와 D는 어느순간 충돌이 발생하게 됩니다. 그리고 이 두 노드는 충돌을 감지하면 서로 전송을 중단합니다. 여기서 취소하는 과정만 없으면 CSMA 프로토콜이 됩니다.

노드 B와 D의 어댑터는 충돌을 감지하면, 랜덤한 시간만큼 대기한 후 다시 재전송을 시도합니다. 이때 기다리는 시간을 '랜덤 백오프' 시간이라고 부릅니다. 대표적인 랜덤 백오프 시간은 이더넷에서 사용하는 '이진 지수적 백오프'입니다. 이 알고리즘은 충돌을 n번 경험한 프레임을 전송할 때 노드가 {0, 1, 2, ... 2^n-1} 중에서 랜덤하게 기다리는 시간을 결정하도록 구현됩니다.

순번 프로토콜 
순번 프로토콜의 종류로는 수십개가 있습니다. 이 수십개의 프로토콜을 공부하기 보다는 중요한 2가지 프로토콜을 기준으로 순번 프로토콜에 대해 알아보겠습니다.

1. 폴링 프로토콜(Polling Protocol)
폴링 프로토콜은 노드 중 하나를 마스터 노드로 지정하는 방식입니다. 마스터 노드는 각 노드를 라운드 로빈 방식으로 폴링합니다. 특히, 마스터 노드는 먼저 노드 1에게 노드 1이 최대로 보낼 수 있는 프레임 수에 대한 정보를 지닌 메시지를 전송합니다. 
노드 1이 프레임들을 보낸 다음에 마스터 노드는 노드 2에게 노드 2가 최대로 보낼 수 있는 프레임 수를 알려주며, 순환적으로 각 노드를 폴링하는 방식으로 이 과정을 계속합니다.

폴링 프로토콜은 충돌뿐만 아니라 랜덤 접속 프로토콜의 단점인 '빈 슬롯 제거'를 통해 훨씬 높은 효율을 제공할 수 있습니다.
하지만, 두가지 단점이 있는데요 첫번째는 마스터 노드가 자식 노드에게 전송할 수 있음을 알리는데 걸리는 '폴링 지연' 시간이 소요된다는 것입니다. 두번째 단점은 마스터 노드가 고장나면 전체 채널이 동작하지 못한다는 단점입니다.

2. 토큰 전달 프로토콜(Token-passing Protocol)
토큰 전달 프로토콜에는 마스터 노드가 존재하지 않습니다. 대신 '토큰'이라고 알려진 특수 목적 프레임이 정해진 순서대로 노드 간에 전달됩니다. 예를들어, 노드 1은 항상 노드 2에게 토큰을 전달하며 노드 2는 항상 노드 3에게 토큰을 전송합니다.

노드가 토큰을 수신하면, 전송할 프레임이 있을때만 토큰을 가지고 있고 그렇지 않으면 토큰을 즉시 다음 노드로 전달합니다. 
노드가 토큰을 수신했을때 전송할 프레임이 있으면 프레임을 최대 개수까지 전송한 뒤 토큰을 다음 노드로 전달합니다. 

이 방식의 문제점은 노드 하나가 실패하면 전체 채널이 동작하지 않는다는 점, 그리고 노드가 토큰을 놓아주지 않으면 토큰을 회복하는 절차가 필요하다는 점입니다. 

여기까지 링크 계층의 다중 접속 프로토콜은 무엇이 있는지 알아봤습니다. 원래는 링크 계층의 모든 내용을 담고 싶었으나 중요한 내용이 많고 글이 너무 길어져 여기서 끊게 되었습니다. 잘못된 내용이 있다면 지적 및 피드백 부탁드립니다.

Ref : 컴퓨터 네트워킹 하향식 접근 7판