Multiple Access Protocols 문서 원본 보기

상위 문서: [[Data Link Layer]]

==개요==
네트워크 링크는 point-to-point 링크와 브로드캐스트(broadcast) 링크로 구분된다. Point-to-point 링크는 링크의 양쪽 끝에 각각 하나의 노드가 존재하는 구성이다. 많은 PPP(Point-to-Point Protocol)와 HDLC(High-Level Data Link Control)와 같은 여러 link layer의 프로토콜이 이 point-to-point 링크를 기준으로 설계되어 있다. 브로드캐스트 링크는 다수의 노드들이 하나의 공유 브로드캐스트 채널에 연결될 수 있는 링크이다. 이때 "브로드캐스트"는 하나의 노드가 프레임을 전송하면 채널이 그 프레임을 모든 노드에게 방송(broadcast)하여, 다른 모든 노드들이 그 복사본을 수신하게 됨을 의미한다. 이때 이더넷(Ethernet)과 무선 LAN(wireless LAN)과 같이 여러 기술들이 브로드캐스트 링크를 위해서 설계되어 있다.

==Multiple access problem==
브로드캐스트 링크에서 가장 중요한 문제 중 하나는, 여러 노드가 공유되는 브로드캐스트 채널은 어떻게 함께 사용할지에 대해 조율하는 문제, 즉, 다중 접근 문제(multiple access problem)이다. 모든 노드가 프레임을 전송할 수 있기 때문에, 두 개 이상의 노드가 동시에 하나의 브로드캐스트 채널을 통해 프레임을 전송할 수 있다. 이런 경우, 모든 노드들은 동시에 여러 프레임을 수신하게 되고, 전송된 프레임들이 충돌(collision)하게 된다. 일반적으로는 충돌이 발생하면 해당 프레임을 수신한 노드는 어떤 프레임도 제대로 해석할 수 없게 된다. 이렇게 되면 충돌에 관련된 모든 프레임은 무의미해지고, 충돌이 발생한 동안 브로드캐스트 채널은 낭비된다. 따라서 여러 노드들이 동시에 활성화되어 있을 때, 브로드캐스트 채널에 대한 이들의 전송을 조율하는 방법이 필요하며, 이는 다중 접근 프로토콜(multiple access protocol)을 통해서 구현된다. 이상적인 다중 접근 프로토콜은 다음과 같은 특징을 만족해야 한다:
# 오직 하나의 노드만 데이터 전송이 필요할 경우, 그 노드는 채널의 최대 성능인 R bps의 처리량을 얻는다.
# M개의 노드가 데이터 전송을 원할 경우, 각각의 노드는 채널의 대역폭을 공평하게 공유하여 평균적으로 R/M bps의 처리량을 갖는다.
#* 이는 항상 순간적으로 R/M을 유지해야 한다는 뜻은 아니며, 일정 시간 구간에 걸친 평균 전송률이 R/M이 되어야 한다는 뜻이다.
# 프로토콜은 분산형(decentralized)이어야 하며, 해당 프로토콜을 위해 특별한 노드가 존재해서는 안된다. 또한 clock 동기화나, slotting과 같은 전역적인 제어 메커니즘이 없어야 한다.<ref>TDMA(Time Division Multiple Access)는 이 조건을 충족하지 못한다.</ref>
# 프로토콜은 단순해야 하며, 구현 비용이 저렴해야 한다.
또한 MAC(Medium Access Control) 프로토콜은 아래와 같이 3가지의 분류로 나뉜다:
* Channel Partitioning: 채널은 여러 조각으로 나누고<ref>시간 슬롯(time slots), 주파수(frequency), 코드(code) 등을 이용한다.</ref>, 각 노드에게 고정된 조각을 독점적으로 할당하는 방식이다.
** TDMA, FDMA, CDMA 등의 프로토콜이 이에 해당한다.
* Random Access: 채널을 나누지 않고, 임의로 전송한 후 충돌이 발생할 경우 다시 회복하는 메커니즘이다.
** ALOHA, CSMA 등의 프로토콜이 이에 해당한다.
* Taking Turns: 노드들이 순서대로 전송하며, 데이터가 많은 노드에게는 더 많은 기회를 주는 방식이다.
** polling, token passing 등의 프로토콜이 이에 해당한다.

==Channel Partitioning Protocols==
TDM(Time-Division Multiplexing)과 FDM(Frequency-Division Multiplexing)은 브로트캐스트 채널의 대역폭을 해당 채널을 공유하는 모든 노드들에게 분할하여 공유하는 기술이다. 

===TDMA: Time Division Multiple Access===
[[파일:Figure 1. Four node TDM example.png|섬네일|Figure 1. Four node TDM example]]
TDMA(Time Division Multiple Access)는 주어진 채널을 타임 슬롯(time slot) 단위로 나누어 각 노드에게 일정한 대역폭을 제공하는 기술이다. 예를 들어, 채널이 N개의 노드를 지원하고, 전송 속도가 R bps라고 가정하자. TDM은 시간을 타임 프레임(time frame) 으로 나눈 다음, 각 프레임을 다시 N개의 타임 슬롯(time slot) 으로 나눈다. 각 슬롯은 N개의 노드에 각각 할당된다. 노드가 패킷을 보낼 준비가 되면, 자신에게 할당된 타임 슬롯 동안 패킷의 비트를 전송한다.<ref>보통 슬롯의 크기는 하나의 패킷을 전송할 수 있을 정도로 설정된다.</ref> Figure 1은 4개의 노드를 관리하는 간단한 TDMA의 예시를 보여준다.

TDM의 장점은 충돌(colision)이 발생하지 않고, 공정하다는 점이다. 또한 각 노드는 타임 프레임 동안 R/N bps의 전송률을 보장받는다. 하지만 TDMA 프로토콜은 하나의 노드만 해당 채널을 사용하고자 할 떄에도, 최대의 전송률은 R/N bps로 제한된다는 단점을 가진다. 이는 다른 노드가 휴식 중이어서 다른 타임 슬롯이 비어있는 상태라고 할지라도, 각각의 노드는 자신의 타임 슬롯의 차례가 될 때까지 기다려야 하기 떄문이다. 또한 TDMA 프로토콜은 모든 노드들이 동기화되어 있어야 정확하게 각 노드가 자신의 타임 슬롯 동안 패킷을 전송할 수 있어야 하는데, 이 동기화 과정이 쉽지 않다는 단점이 있다. 또한 각 노드의 스케줄을 관리해야 하므로, 동기화 과정을 담당할 중앙 제어 장치를 필요로 한다. 즉, decentralized되어 있지 않다는 단점이 있다.

TDM의 이러한 단점을 보완하기 위해서, 사용되지 않는 타임 슬롯을 활성화된 노드에게 할당하여 효율성을 높이는 방식도 개발되었다. 이러한 방식은 효율성과 공정성을 적절하게 챙긴다는 점에서 더욱 발전되었다고 볼 수 있다. 하지만 TDMA의 본질적인 단점인 동기화가 요구된다는 점과, decentralized되어 있지 않다는 점에서는 여전히 자유롭지 않다.

===FDMA: Frequency Division Multiple Access===
[[파일:Four node FDM example.png|대체글=Figure 2. Four node FDM example|섬네일|200x200픽셀|Figure 2. Four node FDM example]]
FDMA 프로토콜은 TDMA 프로토콜이 시간을 기준으로 하나의 채널을 분할하는 반면, 주파수(frequency)를 기준으로 분할한다. 즉, R bps의 대역폭을 가지는 채널을 R/N bps의 대역폭을 가지는 서로 다른 주파수들로 분할하고, 이를 N개의 노드에 각각 할당한다. Figure 2는 이를 보여준다. FDM은 TDM과 장점과 단점을 공유한다. 충돌을 방지하고, N개의 노드 간에 공정하게 대역폭을 나눈다. 하지만 단점도 동일하게 노드의 대역폭을 항상 R/N bps로 제한한다는 것이다.

===CDMA: Code Division Multiple Access===
TDMA 프로토콜이 시간을, FDMA 프로토콜이 주파수를 할당하는 방식인 것과 달리, CDMA(Code Division Multiple Access)는 각 노드에게 고유한 코드(code)를 할당한다. 각 노드는 자신의 고유한 코드로 데이터 비트를 인코딩하여 전송한다. 이는 여러 노드가 동시에 전송하더라도, 수신 노드가 해당 송신 노드의 코드를 이용해 데이터를 복호화하여 데이터 비트를 수신할 수 있도록 한다. 이때 CDMA의 코드는 TDMA의 타임 슬롯이나 FDM의 주파수 처럼, 다중 접속 사용자에게 할당되는 자원이다.

==Random Access Protocols==
Random access 프로토콜의 가장 큰 특징은 송신 노드가 항상 채널의 전체 속도인 R bps로 전송한다는 것이다. 이 경우 충돌이 발생할 수 있으며, 해당 충돌에 연루된 각 노드는 패킷이 충돌없이 전송될 때까지 반복하여 이를 재전송한다.

==각주==
[[분류:컴퓨터 네트워크]]