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)을 통해서 구현된다. 이상적인 다중 접근 프로토콜은 다음과 같은 특징을 만족해야 한다:

1. 오직 하나의 노드만 데이터 전송이 필요할 경우, 그 노드는 채널의 최대 성능인 R bps의 처리량을 얻는다.
2. M개의 노드가 데이터 전송을 원할 경우, 각각의 노드는 채널의 대역폭을 공평하게 공유하여 평균적으로 R/M bps의 처리량을 갖는다.
   • 이는 항상 순간적으로 R/M을 유지해야 한다는 뜻은 아니며, 일정 시간 구간에 걸친 평균 전송률이 R/M이 되어야 한다는 뜻이다.
3. 프로토콜은 분산형(decentralized)이어야 하며, 해당 프로토콜을 위해 특별한 노드가 존재해서는 안된다. 또한 clock 동기화나, slotting과 같은 전역적인 제어 메커니즘이 없어야 한다.
4. 프로토콜은 단순해야 하며, 구현 비용이 저렴해야 한다.

또한 MAC(Medium Access Control) 프로토콜은 아래와 같이 3가지의 분류로 나뉜다:

• Channel Partitioning: 채널은 여러 조각으로 나누고, 각 노드에게 고정된 조각을 독점적으로 할당하는 방식이다.
  • 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

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

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

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

FDMA: Frequency Division Multiple Access

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로 전송한다는 것이다. 이 경우 충돌이 발생할 수 있으며, 해당 충돌에 연루된 각 노드는 패킷이 충돌없이 전송될 때까지 반복하여 이를 재전송한다. 하지만 충돌을 경험한 노드가 즉시 재전송하는 것은 아니며, 패킷을 재전송하기 전에 독립적으로 무작위 지연(random delay)을 기다린다. 이에 따라 random access MAC 프로토콜은 어떻게 충돌을 찾아낼지를, 그리고 충돌이 발생했을 때 이로부터 회복할지를 정의한다. 일반적으로 사용되는 random access MAC 프로토콜에는 slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA 방식이 있다.

Slotted ALOHA

Slotted ALOHA 프로토콜은 아래와 같은 가정을 기반으로 한다.

• 모든 프레임(패킷)은 정확히 L 비트로 구성되어 있다.
• 시간은 슬롯(slot) 단위로 분할되며, 각 슬롯의 크기는 L/R 초이다.
• 노드들이 프레임을 전송하기 시작하는 시점은 각 슬롯이 시작하는 시점이다.
• 노드들은 동기화되어 있어, 동일한 슬롯을 공유한다.
• 두 개 이상의 프레임이 하나의 슬롯에서 충돌할 경우, 이와 연루된 모든 노드는 해당 슬롯이 끝나기 전에 충돌을 감지한다.

Figure 3. Sloted ALOHA example

이러한 상황이 가정되어 있을 때, p를 0과 1사이의 확률이라고 하자. 이때 Sloted ALOHA는 아래와 같이 작동한다:

1. 노드가 새로운 프레임을 보낼 준비가 되면, 다음 슬롯이 시작할 때 프레임 전체를 슬롯에 전송한다.
2. 충돌이 없다면, 프레임 전송은 성공한 것이고, 재전송할 필요가 없다.
3. 충돌이 발생했다면, 노드는 슬롯이 끝나기 전에 충돌을 감지한다. 이후 각 노드는 성공할 때까지 각 슬롯마다 확률 p에 따라 프레임을 재전송한다.

이는 figure 3가 잘 보여준다. Figure 3에서 C는 충돌이 감지된 슬롯, E는 어떤 노드도 이용하지 않은 슬롯, S는 충돌이 일어나지 않고 패킷 전송이 성공한 슬롯을 의미한다. Sloted ALOHA의 장점은 어떤 채널에 대해 활성화된 노드가 유일하다고 할때, 해당 노드는 R bps 전체를 사용하여 연속적으로 패킷을 전송할 수 있다는 것이다. 또한 각 노드는 독립적으로 충돌을 감지하고, 재전송 시점도 독립적으로 결정하므로 동기화되어야 한다는 점만을 제외하면 매우 분산적으로 구성되어 있다고 볼 수 있다. 또한 프로토콜 구조가 매우 간단하다는 장점이 있다. 하지만 충돌이 일어날 경우, 슬롯을 낭비한다는 점, 확률적으로 사용되지 않는(idle) 슬롯이 존재할 수 있다는 점, 노드 사이의 동기화가 요구된다는 단점이 있다.

Sloted ALOHA의 효율을 간단하게 계산하기 위하여 프로토콜을 다음과 같이 조금 수정하자:

• 각 노드는 항상 전송할 프레임을 가지고 있다.
• 새로운 프레임이든 충돌된 프레임이든, 각 노드는 각 슬롯마다 확률 p로 전송을 시도한다.

노드의 수를 N이라고 할 때, 한 슬롯이 성공적일 확률은 하나의 노드가 전송하고, 나머지 N-1 개의 노드는 모두 전송하지 않을 확률이고 이는 아래와 같이 계산된다.

하나의 노드가 전송할 확률: p
나머지 N-1 개의 노드가 전송하지 않을 확률: (1-p)N-1
특정 노드의 송신이 성공할 확률: p * (1-p)N-1
N개의 노드 중 어느 하나가 성공할 전체 확률: N * p * (1-p)N-1

즉, sloted ALOHA의 최대 효율은 N * p * (1-p)N-1이다. 이를 최대화하기 위해서는 p에 대해 최적화해야 한다. 또한 활성 노드의 수 N이 매우 클 때의 효율을 구하기 위해서는 N $\to \mathrm{\infty }$일 때의 N * p * (1-p)N-1 극한을 구해야 한다. 이를 계산하면, sloted I/O의 최대 효율은 아래와 같다:

1/e ≈ 0.37

즉, 많은 노드가 다량의 프레임을 전송하려는 경우, 슬롯의 최대 37%만이 실제로 유용한 전송에 사용된다. 따라서 채널의 유효 전송 속도는 R bps가 아니라 0.37R bps에 불과하다.

Pure ALOHA

최초의 ALOHA 프로토콜은 sloted ALOHA과 달리 동기화를 요구하지 않고 완전히 decentralized된 프로토콜이다. Pure ALOHA에서는 프레임이 처음 도착하였을 때(송신 노드에서 데이터 그램이 link layer에 내려왔을 때), 노드는 즉시 해당 프레임 전체를 브로드캐스트 채널로 전송한다. 만약 프레임을 전송한 노드가 충돌을 경험한다면, 노드는 해당 프레임의 전송을 마친 후, 아래와 같이 작동한다:

• 확률 p에 따라 전송한다.
• 확률 1-p에 해당된 경우, 프레임 전송 시간만큼 다시 대기한다. 대기가 끝난 후에는 다시 확률 p에 따라 재전송을 시도한다.

Pure ALOHA의 최대 효율을 계산하기 위해서는 개별 노드 하나의 동작을 분석해야 한다. 이때 상황 가정은 sloted ALOHA와 동일한 과정을 사용하며, 프레임 전송 시간을 시간 단위로 사용한다. 임의의 시간에, 노드가 프레임을 전송할 확률은 p라고 하고, 어떤 프레임이 시간 t₀일 때 전송을 시작한다고 하자. 이 프레임이 성공적으로 전송되기 위해서는, 다음의 조건이 만족되어야 한다:

Figure 4. Collision probability increases in pure ALOHA

1. 다른 어떤 노드도 [t₀ – 1, t₀] 구간에서 전송을 시작하면 안 된다.
   • 다른 모든 노드가 이 구간 동안 전송을 시작하지 않을 확률은 (1 – p)^{(N – 1)} 이다.
2. [t₀, t₀ + 1] 구간에도 다른 노드가 전송을 시작하면 안 된다.
   • 다른 모든 노드가 이 구간 동안 전송을 시작하지 않을 확률은 (1 – p)^{(N – 1)} 이다.

따라서 특정 노드가 성공적으로 전송할 확률은 N * p * (1 – p)2(N – 1)이다. 슬롯 ALOHA와 마찬가지로 극한을 취하는 방식으로 분석을 진행하면, 순수 ALOHA 프로토콜의 최대 효율은:

1/2e ≈ 0.18

즉, sloted ALOHA의 효율(1/e ≈ 0.37)의 정확히 절반이다.

CSMA

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

Taking-Turns Protocols

이상적인 다중 접속 프로토콜은 아래의 두 속성을 만족시켜야 한다:

• 오직 하나의 노드만 활성 상태일 때, 그 노드는 채널의 대역폭인 R bps를 모두 사용할 수 있어야 한다.
• M개의 노드가 활성 상태일 경우, 각 활성 노드는 거의 R/M bps의 처리량을 가져야 한다.

ALOHA와 CSMA 프로토콜은 첫 번째 속성은 만족하지만, 두 번째 속성은 만족하지 못한다. Taking-turns 프로토콜은 ALOHA와 CSMA의 이러한 특성을 극복하기 위해서 구현되었다. Taking-turns 프로토콜들 중, 가장 대표적인 프로토콜 두가지는 polling 프로토콜과 Token-Passing 프로토콜이다.

Polling Protocol

Figure 5. Polling protocol

Polling 프로토콜에서는, 하나의 노드가 마스터(master) 노드로 지정되며, 마스터 노드가 아닌 노드는 슬레이브(slave) 노드가 된다. 마스터 노드는 round-robin 방식으로 다른 노드들을 polling한다. 이는 차례대록 노드에게 전송할 차례가 되었음을 알려주는 것이다. 이는 아래와 같이 동작한다:

1. 마스터 노드는 먼저 노드 1에게 메시지를 보낸다. "최대 N개의 프레임까지 전송 가능"
2. 노드 1이 전송을 마치면, 마스터는 노드 2에게 같은 방식으로 알린다.
3. 마스터 노드는 채널에서 신호가 사라지면, 해당 노드가 전송을 끝마쳤다고 판단한다.
4. 이 절차는 모든 노드들을 순환하면서 반복한다.

해당 프로토콜 방식은 충돌과 empty slot이 모두 없으므로, random access 프로토콜보다 더 높은 효율을 보장한다. 하지만 polling 지연이 발생한다는 단점이 있다. 이는 각 슬레이브 노드에게 차례를 알려주는데 시간이 걸리기 때문이다. 이는 하나의 채널은 한 노드가 독점적으로 사용할 때에도 발생하며, 이에 따라 실제 전송률은 R bps보다 낮아진다. 또한 마스터 노드에 문제가 생길 경우, 전체에 문제가 생긴다는 단점도 있다.

Token-Passing Protocol

Figure 6. Token-passing protocol

Token-passing protocol에는 마스터 노드가 존재하지 않는다. 대신 토큰(token)이라고 불리는 작고 특수한 기능을 하는 프레임이 정해진 순서대로 노드 사이에서 전달된다, 이는 라애와 같이 작동한다:

• 예를 들어, 노드 1 → 노드 2 → 노드 3 ... → 노드 N → 다시 노드 1 식의 순서로 토큰을 전달한다.
• 토큰을 받은 노드는
  • 전송할 프레임이 있다면, 허용된 만큼 최대한 프레임을 전송한 후, 토큰을 다음 노드에 전달한다.
  • 전송할 프레임이 없다면, 즉시 토큰을 다음 노드에 전달한다.

따라서, 해당 프로토콜은 decentralized되어 있으며, 매우 효율적이라는 장점이 있다. 하지만 하나의 노드라도 고장날 경우, 전체의 네트워크가 멈출 수 있다. 또한 어떤 노드가 토큰을 잃어버리거나 전달을 빼먹는 경우, 이를 복구하기 위한 절차를 필요호 한다.