[Network]링크 계층의 다중 접속 프로토콜이란?

1. 링크 계층

기본적으로 링크 계층의 역할은 한 노드에서 인접한 노드로 데이터그램을 직접 이동시키는 것이다.

1.1 링크 계층의 서비스

• 프레임화 : 링크 계층 프로토콜은 네트워크 계층 데이터그램을 링크상으로 전송하기 전에 링크 계층 프레임으로 캡슐화한다.
• 링크 접속 : 링크 계층의 프로토콜인 MAC(Medium Access Control, 매체 접속 제어)프로토콜은 링크상으로 프레임을 전송하는 규칙에 대하여 명시한다. 점대점의 단순한 상황에서는 송신자는 링크가 사용되지 않을 때마다 프레임을 전송할 수 있다. 만약 여러 노드가 링크를 공유하는 경우 MAC 프로토콜을 통해 여러 노드의 프레임 전송을 조정해야 한다.
• 신뢰적 전달 : 일반적으로 광섬유, 동축케이블, 꼬임쌍선을 이용하는 링크 계층에서의 오류는 잘 발생하지 않는다. 유선 상황에서는 충돌만 없다면 거의 대부분의 전송이 성공적으로 이루어지기 때문에 무선 링크와 같은 오류율이 높은 링크에서 주로 신뢰적 전달 서비스를 사용한다. 전송 계층과 마찬가지로 확인응답과 재전송을 통해 신뢰적 전달이 가능하다.
• 오류 검출과 정정 : 하드웨어로 구현한다. 오류 검출뿐만 아니라 프레임의 어느곳에서 오류가 발생했는지 정확하게 찾아낼 수 있다.

1.2 링크 계층이 구현되는 위치

라우터의 라인 카드에는 링크 계층이 구현된다. 종단 시스템의 경우 네트워크 인터페이스 카드로 알려진 네트워크 어댑터에 링크 계층이 구현된다.

네트워크 어댑터는 I/O 장치가 다른 호스트 구성요소에 접속된 것과 유사하게 호스트의 버스에 접속한다. 대부분의 링크 계층 기능이 인터페이스 카드에 구현되어 있고 일부 링크 계층 기능은 호스트 CPU에서 실행되는 소프트웨어(OS)에 구현되어 있다. (링크 계층 주소 정보 조립, 제어기 하드웨어의 활성화 등)

2. 다중 접속 링크와 프로토콜

컴퓨터 네트워크에서 수백 개에서 수천 개의 노드들이 브로드캐스드 채널을 통해 통신한다. 모든 노드들이 프레임을 전송할 수 있기 때문에 하나의 노드가 여러 개의 프레임을 받게 되면 충돌이 발생한다. 일반적으로 충돌이 발생하면 프레임의 의미를 파악할 수 없게 된다.

다중 접속 프로토콜은(multiple access protocol) 브로드캐스트 채널이 제대로 동작하도록 보장한다. 다중 접속 프로토콜은 채널 분할 프로토콜, 랜덤 접속 프로토콜, 순번 프로토콜으로 분류할 수 있다.

2.1 채널 분할 프로토콜 (channel partitioning protocol)

채널 분할 프로토콜은 시간을 분할하는 방식과 주파수를 분할하는 방식이 존재한다. (+ 무선 채널에서 사용되는 코드 분할 다중 접속도 있다.)

1. TDM

시분할 다중화(time division multiplexing, TDM)은 시간을 time frame으로 나누고 각 프레임을 N개의 time slot으로 나눈다. 분할된 time slot은 N개 노드에게 각각 할당한다. 노드는 전송할 패킷이 있을 때마다 TDM 프레임에서 자신에게 할당된 time slot 동안 패킷을 전송한다.

칵테일 파티에서 파티 참석자가 번갈아 가며 말을 한다고 하자. TDM은 참석자에게 고정된 시간 동안 말을 할 수 있는 기회를 주는 것이다. “일단” 모든 사람에게 말을 할 수 있는 기회가 주어진다.

• TDM은 충돌을 제거할 수 있다.
• 전송할 패킷이 있는 노드가 단 하나인 경우에도 전송률이 평균 R/N으로 제한된다.
• 전송을 위해 항상 자신의 차례를 기다려야 한다.

2. FDM

주파수 분할 다중화(frequency division multiplexing, FDM)은 R bps의 채널을 각 R/N의 대역폭을 갖는 주파수로 나눠 N개 노드에게 각각 할당한다.

• FDM은 충돌을 제거할 수 있다.
• 전송할 패킷이 있는 노드가 단 하나인 경우에도 대역폭이 R/N으로 제한된다.

2.2 랜덤 접속 프로토콜 (random access protocol)

랜덤 접속 프로토콜에서는 노드는 항상 채널의 최대 전송률인 R bps로 프레임을 전송한다. 만약 충돌이 발생하면 각 프레임이 충돌 없이 전송에 성공할 때까지 재전송한다. 이 때, 재전송을 즉시하는 것이 아니라 랜덤 시간 동안 기다린 후 재전송하는 것이다.

일반적으로 사용되는 랜덤 프로토콜의 종류에는 알로하 프로토콜, CSMA 프로토콜이 있다.

1. 슬롯 알로하

슬롯 알로하는 다음과 같은 특징을 갖는다.

• 모든 프레임은 정확히 L 비트로 구성된다.
• 시간을 L/R초의 슬롯들로 나눈다.
• 노드는 슬롯의 시작점에만 프레임을 전송 시작한다.
• 각 노드들은 슬롯의 시작점을 알고 충돌이 발생하면 슬롯이 끝나기전에 충돌 발생을 알게 된다.

TDM와 유사하게 시간을 분할하지만 노드들의 위치를 고정하지는 않은 방식이라 생각하면 된다. 노드들에게 정해진 순서가 없기 때문에 충돌이 발생할 수 있다. 각 노드들은 정해진 확률 p로 다음 슬롯에서 프레임을 재전송하면 된다.

슬롯 알로하에서는 채널 분할과 달리 채널의 최대 전송률인 R로 프레임을 전송할 수 있다. 또한 노드가 충돌을 감지하고 언제 재전송할 지 각자가 결정하기 때문에 분산된 구조이다. 다만 노드들이 슬롯의 시작점과 충돌 발생을 알기 위해 동기화 과정이 필요하다.

슬롯 알로하는 노드가 하나일 때는 잘 동작하지만 많은 노드들이 프레임을 전송하려고 한다면 충돌이 계속해서 발생할 것이고 충돌이 발생한 슬롯은 낭비 되어버린다. 게다가 확률적인 정책으로 인해 빈 슬롯이 발생하기도 한다.

2. 알로하

알로하 프로토콜은 처음에 슬롯이 없는 완전히 분산된 형태의 프로토콜이었다. 프레임이 준비되면 즉시 그 프레임 전체를 브로드캐스트 채널로 전송하고 충돌이 발생한다면 확률 p로 즉시 재전송한다.

3. CSMA (Carrier Sense Multiple Access)

이름에서 알 수 있듯이 CSMA는 캐리어를 감지한다. 다시 칵테일 파티의 예시를 들어보자면 다른 사람이 말을 하고 있다면, 말이 끝날 때까지 듣고 있는 것이다. 다른 사람의 말이 끝나면 내가 말을 시작한다. CSMA는 어느 정도 충돌을 회피하는 전략이다.

캐리어를 감지하고 만일 채널이 유휴 상태일 때 프레임을 전송하더라도 비슷한 시기(다른 프레임이 전송되고 있다는 것을 알아채기 전)에 프레임을 전송하는 노드와 충돌이 여전히 발생한다. CSMA에서는 충돌이 발생했음에도 불구하고 자신의 프레임 전체를 계속해서 전송한다.

4. CSMA/CD (CSMA with Collision Detection)

CSMA/CD에서는 충돌을 감지한다.

1. 네트워크 계층으로부터 데이터그램을 받아서 프레임으로 캡슐화한다. 프레임을 버퍼에 저장한다.
2. 각 노드들은 채널이 유휴한 것을 감지하면 프레임 전송을 시작한다.
3. 전송하는 동안 노드들은 브로드캐스트 채널을 사용하는 다른 노드로부터의 신호가 있는지 감시한다. (Collision Detection)
4. 신호가 감지되지 않으면 전송을 완료한다. 만약 신호가 감지되면 자신의 프레임 전송을 취소한다.
5. 전송 취소 이후 랜덤 시간만큼 기다린 후 채널이 유휴하다면 다시 프레임 전송을 시작한다.

---

여전히 문제는 남아있다. 만약 기다리는 시간의 간격이 작고 충돌하는 노드의 수가 많으면 프레임 전송이 반복해서 취소될 것이다.

이더넷 프로토콜에서는 이진 지수적 백오프 알고리즘을 통해 랜덤 시간의 최댓값을 2배로 늘리며 대기한다. 즉, 충돌을 n번 경험한 프레임은 [0,1,2,4,…,2^n-1] 중에서 고른 랜덤 시간만큼 기다린다.

2.3 순번 프로토콜 (taking-turns protocol)

순번 프로토콜에는 폴링 프로토콜과 토큰 전달 프로토콜이 있다.

 

폴링 프로토콜은 마스터 노드가 라운드 로빈 방식으로 각 노드들에게 순서를 정해주는 방식이다. 만약 마스터 노드가 고장나면 전체 채널이 동작하지 못한다. 동시에 자신의 순서가 되었음을 알려주는 시간이 생기기 때문에 지연이 발생한다.

 

토큰 전달 프로토콜은 토큰을 가진 노드가 프레임을 전송하고 다른 노드에게 토큰을 전달한다. 이 방식에서도 노드 하나가 고장나면 이후의 전체 채널이 동작하지 못하게 된다.