네트워크 링크는 두 종류로 나뉜다:

point-to-point link

• 링크 양끝에 오직 한 노드만 있는 경우
• 이 종류의 링크를 위한 프로토콜로는 대표적으로 point-to-point protocol(PPP)과 high-level data link control(HDLC)

broadcast link

• 이 종류의 링크는 링크 양쪽 끝에 여러 개의 노드가 있는 경우로, 여러 노드가 동일한 하나의 broadcast channel을 공유하는 경우이다.
• 이 링크를 사용하는 노드들은 한 노드가 보낸 frame을 다른 모든 노드들이 똑같이 받기 때문에 broadcast link이다.
• 주로 LAN이나 한 건물/캠퍼스/회사 등 지리적으로 가까운 네트워크에서 사용된다

Multiple access protocol

broadcast link는 여러 노드가 공유해서 사용하고 있기 때문에 multiple access problem이 발생한다. 이는 여러 개의 노드가 동시에 프레임을 전송해 수신자 측에서 데이터 충돌이 발생하고, 전송된 프레임이 소실되는 상황을 일컫는다. Multiple access problem을 해결하기 위해 노드의 전송을 조정하는 것이 필요한데, 이것이 바로 multiple access protocol이다.

Multiple access protocol은 다음과 같은 특징을 갖고 있다.

• throughput
  • broadcast link가 R bps를 가지고 있다고 할 때,
  • 한 노드만 데이터를 보낼 경우: throughput = R bps
  • M개의 노드들이 데이터를 보낼 경우: 각 노드의 throughput = R/M bps
    - 이때, 모든 노드가 항상 바로 R/M bps의 throughput을 가진다는 것은 아니다. 평균적으로 시간에 걸쳐 측정했을 때 그 수치가 나온다는 것이다
• protocol is decentralized
  • 특정 노드가 실패해도, 다른 노드들을 영향끼치지 않는다
• protocol is simple, inexpensive to implement

지금까지 다양한 multiple access protocol이 개발되었지만, 크게 세 카테고리로 구분할 수 있다. 바로 channel partitioning protocols, random access protocols, 그리고 taking-turns protocols이다. 지금부터 각 카테고리를 설명해보도록 하겠다.

6.3.1 Channel Partitioning Protocols

이 종류의 프로토콜들은 여러 개의 노드들이 충돌없이 frame을 보낼 수 있도록 하기 위해서 채널을 나누는 방법이다. 크게 세 가지가 있다.

1. time-division multiple access (TDMA)
이 방식은 시간을 time frame으로 나누고, 각 time frame을 노드 개수인 N개의 time slot으로 나누는 경우이다.

• 장점
  • 충돌 없음
  • 모든 노드에게 공평하게 나눔. 모든 노드는 매 frame time 마다 R/N bps의 전송속도를 보장받을 수 있다
• 단점
  • 노드는 자기 차례를 무조건 기다려야 한다. 전송하는 노드가 한 개밖에 없더라도 자기 차례를 기다려야 함
  • 전송속도는 R/N bps로 고정되어 있다. 전송하는 노드가 한 개밖에 없더라도 전송속도를 조절할 수 없음

2. frequency-division multiple access (FDMA)
이 방식은 해당 채널에 할당된 frequency를 노드 개수만큼 나누는 경우이다. 각 frequency는 R/N bandwidth를 가지며 한 노드에 할당된다. FDMA의 장단점은 TDMA의 장단점과 동일하다

3. code division multiple access (CDMA)
CDMA는 각 노드에게 다른 코드를 할당한다. 각 노드는 유니크한 코드로 데이터를 인코딩하여 전송하는데, 수신자는 그 코드를 전달받아 알맞게 디코딩해서 데이터를 읽는다. 이때, 코드를 잘 선택 및 배정하기만 하면 여러 노드가 동시에 데이터를 충돌없이 전송할 수 있다는 장점이 있다. 그래서 군대나 핸드폰에 자주 사용된다.

6.3.2 Random Access Protocols

이 종류는 말 그대로 랜덤하게 데이터를 전송하는 프로토콜들이다. Random access protocol에서는 전송하는 노드는 항상 채널의 전체 속도, 즉 R bps로 전송한다. 만약 충돌이 발생할 시, 충돌에 연관된 노드들은 전송하고자 하는 데이터가 도착할 때까지 반복적으로 재전송한다. 이때, 바로 재전송하는 것이 아니라 랜덤한 딜레이를 두고 보내게 되는데, 딜레이가 랜덤이기에 언젠가 프레임이 충돌없이 잘 도착하게 한다.

Random access protocol 중에서 자주 사용되는 프로토콜은 ALOHA protocol과 carrier
sense multiple access (CSMA) protocol이다.

1. Slotted ALOHA
이 방식은 다음과 같은 특징을 가지고 있다.

• 모든 프레임이 L bits일 때, 시간은 L/R 초의 slot으로 나눠진다. 즉 한 slot은 딱 한 개의 프레임을 다 보낼 수 있는 시간으로 설정된다.
• 노드는 무조건 slot이 시작할 때 프레임을 전송한다.
• 만약 충돌이 말생하면, 모든 노드는 slot이 끝나기 전에 충돌이 일어났음을 인지한다
• 노드가 전송할 프레임이 생기면, 다음 slot이 시작할 때까지 기다렸다가 다음 slot이 시작되면 전송한다.
• 충돌이 일어나지 않으면 프레임은 성공적으로 도착하고, 노드는 다음으로 전송할 프레임을 준비한다.
• 충돌이 일어났으면, slot이 끝나기 전에 충돌을 인지한다. 이후 노드는 충돌이 일어나지 않을 때까지 그 프레임을 다음 slot에 재전송하려고 하는데, 이때 재전송 확률은 p이다.
• 재전송 확률이 p라는 것은 동전을 던지는 것처럼 heads가 나오면 재전송, tails가 나오면 그 다음 slot을 기다리며, heads가 나올 확률이 p라는 것이다.

장점

• 만약 한 개의 노드만 전송할 데이터가 있다면, 이 방식은 그 노드가 전체 속도인 R로 지속적으로 전송할 수 있도록 한다.
• highly decentralized. 왜냐하면 각 노드는 충돌을 감지하고 독립적으로 재전송할지 결정하기 때문이다.
• 매우 간단한 프로토콜임

효율성

• 확률적으로 계산했을 때, throughput은 링크 throughput의 37%밖에 안됨

2. ALOHA
ALOHA는 slotted ALOHA와 달리 노드가 전송할 프레임이 생기면 즉시 보낸다. 충돌이 일어나면 그 즉시 p의 확률로 재전송하고, 그렇지 않으면 프레임 전송 시간만큼 기다려 다시 반복한다.

효율성

• 확률적으로 계산했을 때, throughput은 Slotted ALOHA 효율성의 절반임

3. Carrier Sense Multiple Access (CSMA)
이 방식은 노드가 전송하기 전에 채널의 상태를 확인한다. 만약 현재 채널에서 무엇이 보내지고 있다면, 노드는 채널이 어느 정도 시간 동안 안 보낼 때까지 기다리고 프레임을 전송한다. 이런 방식을 택해도 충돌이 일어나는 이유는 propagation delay 때문이다.

4. CSMA with collision detection (CSMA/CD)
이 방식은 노드가 전송하기 전에 채널의 상태를 확인하면서도 노드가 전송하는 도중에 채널의 상태를 확인한다. 만약 한 노드가 전송하고 있는 와중에 다른 노드도 전송하려고 한다는 것을 알게 되면, 전송을 그만하고 랜덤 시간동안 기다려 sense-and-transmit-when-idle cycle을 반복한다.

6.3.3 Taking-Turns Protocols

1. polling protocol
이 프로토콜은 한 노드를 마스터 노드로 지정한다. 마스터 노드는 round-robin 방식으로 다른 노드들에게 메세지(poll)을 보낸다. 가령, 마스터 노드는 노드 1한테 몇 개의 frame을 보낼 수 있음을 알리고, 노드 1이 다 보내면 노드 2한테 몇 개의 frame을 보낼 수 있음을 알리는 방식인 것이다.

장점

• 충돌 제거
• empty slot 제거(random access protocol들의 문제점)
• 효율성 극대화

단점

• polling delay

2. token-passing protocol
이 방식에는 마스터 노드가 없고, Token이라는 작고 특정 목표를 가진 프레임이 노드 사이에서 특정 순서로 교환된다. 노드가 token을 받으면, 보낼 프레임이 있을 경우 붙잡고 있다. 보낼 것이 없으면 그 즉시 다음 노드에게 token을 전달한다. 이때, token을 가지고 있는 노드는 특정 수의 프레임까지만 보낼 수 있다.