4. Resource Sharing: Multiple Access

Network Links

1. Point-to-point link

   

   • Related protocol : Point-to-point protocol (PPP)

2. Broadcast link/shared medium

   

   • Example : Ethernet, wireless local area networks (LANs)

   💡

   when anyone transmits a frame, the channel broadcasts the frame and each of the other nodes receives a copy

   Computer network broadcast channel은 송신과 수신이 동시에 가능하다. 반면 television의 경우에는 one-way broadcast이다.

하지만, broadcast link의 경우에는 공유자원인 broadcast link 를 나눠서 써야한다는 측면때문에 multiple access problem 이 발생한다.

💡

즉 각 node들이 frame을 broadcast link에 보낼 수 있는 능력이 있기 때문에 여러 frame들을 동시에 받게되는 문제가 발생하게 된다.

Multiple Access Problem

Problem definition

Receiving multiple frames at the same time : collision

→ 여러 frame이 동시에 들어와 서로 충돌하면서 하나의 혼합된 신호로 섞이게 된다. 이 과정에서 해독이 불가능해지는 것이다.

💡

이 과정에서 bandwidth가 낭비가 된다.

Assumption

1. All frames involved in a collision are lost

2. The broadcast channel is wasted during the collision interval

이러한 문제를 해결하기 위해서 multiple access protocol 이라는 protocol을 약속한다. 이를 통해 shared broadcast channel에 transmission을 하는 것을 규제하게 된다.

💡

정확하게는 각 node들은 broadcast channel에 자신들의 adapter 를 통해서 접근한다는 점을 주의해야 한다.

Multiple access protocol

Multiple Access problem을 해결하기 위해서 여러 가지 접근방법이 있으나, 다음 3가지로만 구분하려고 한다.

1. Channel partitioning protocols : TDM (2G), FDM (~1G), CDM (3G)

2. Random access protocol : ALOHA, CSMA, CSMA/CD

3. Taking-turns protocols : Token Ring

이를 하나씩 살펴보기에 앞서, 다음과 같은 desirable characterisitc을 가진다고 가정한다. (단, broadcast channel의 bandwidth(data rate)은 $R$이다.)

1. When only one node has data to send, that node has a throughput of $R$ bps

2. When $M$ nodes have data to send, each of theses nodes has a throughput of $R/M$ bps.

   💡

   항상 throughput이 $R/M$가 되는 것이 아니라 평균적인 throughput임에 주의하도록 하자.

3. The protocol is decentralized; that is, there is no master node that represents a single point of failure for the network

   → 즉, 하나의 노드가 실패하더라도 전체 시스템에 치명적인 영향을 주지 않는다는 의미이다. 비트코인과 같은 암호화폐 네트워크에서 핵심적인 기능으로 사용된다.

4. The protocol is simple, so that it is inexpensive to implement

💡

data rate와 bandwidth는 종종 혼용되어 사용되지만 기본적으로 가능한 최대 전송 속도를 설명하는 반면, throughput은 실제 전송률(즉, 성공적으로 전달된 데이터의 양)을 설명한다는 점을 주의해야 한다.

추가적으로 여러가지 network 상황들이 존재한다. (예를들어 wired, wireless network). 따라서 하나의 솔루션이 아니라 각각의 네트워크 환경과 요구사항에 맞게 최적화된 솔루션들이 달라지게 된다는 점을 주의해야 한다.

그러면 하나씩 살펴보도록 하자.

Channel Partitioning

Time-Division Multiplexing (TDM)

예를 들어 해당 channel이 $N$개의 node를 지원하고, 해당 channel의 bandwidth가 $R$ bps라고 가정하자.

💡

해당 channel에 속한 것들을 크게 하나의 node로 취급했을 때의 throughput이 $R$ bps라고 생각해주면 된다.

이 방식의 경우에는 시간을 time frame 로 나누고 해당 time frame을 $N$개의 time slot으로 나눈다. 이렇게 나눈 time slot을 $N$개의 node들 중 하나에 분배한다. 그리고 각 노드들은 할당받은 time slot에 대응되는 시간에만 channel에 transmission할 수 있다.

💡

일반적으로 time slot의 크기는 해당 시간 동안 1개의 packet이 transmitted될 수 있는 시간으로 설정된다.

Pros

1. Perfectly fair

   → 각 node들은 frame 시간동안 $R/N$ bps로 transmission할 수 있으므로

Cons

1. 다른 node들이 channel에 transmission을 시키지 않아도 $R/N$ bps로 bounded된다는 것

2. 모든 node들이 자신에게 할당된 time slot을 기다려야 한다는 점

   → 극단적으로 해당 node만 transmission시키고 싶은 상황에서도 자신 차례까지 기다려야 한다.

Frequency-division Multiplexing (FDM)

예를 들어 해당 channel이 $N$개의 node를 지원하고, 해당 channel의 bandwidth가 $R$ bps라고 가정하자.

FDM의 경우 TDM와 달리 bandwidth인 $R$ bps를 frequency 를 기준으로 노드의 수인 $N$으로 나눈다. (각각의 bandwidth는 $R/N$ bps이다.) 이후, 각 frequency를 각 node에 할당한다.

Pros

1. Perfectly fair

   → 각 node들은 frame 시간동안 $R/N$ bps로 transmission할 수 있으므로

Cons

1. 다른 node들이 channel에 transmission을 시키지 않아도 $R/N$ bps로 bounded된다는 것

💡

기본적으로 TDMA와 FDMA는 advantage와 disadvantage를 공유한다.

Code Division Multiple Access (CDMA)

각 node별로 서로 다른 code 를 할당한다. 이를 활용하여 transmit할 data bit를 encoding한다.

💡

Each user has a different, orthogonal code

Pros

1. code를 잘 선택하면 동시에 여러 노드들이 transmission 시켜도 상관없다.

   → 서로 다른 코드 사이에서 발생하는 상호 간섭으로부터 원하는 신호만 추출해내려면 해당 신호의 코드만 알면 된다. 따라서 모든 사용자가 동시에 같은 주파수 대역을 공유해서 정보를 전달할 수 있다.

💡

Used in modern wireless systems (3G, 4G, Wi-Fi, etc)

Random Access Protocols

In a random access protocol, a transmitting node always transmits at the full rate of the channel, namely, $R$ bps.

When there is a collision, each node involved in the collision repeatedly retransmits its frame until its frame gets through without a collision

💡

즉, Random Access Protocol의 경우에는 channel의 최대 bandwidth만큼 다 밀어넣고 collision이 발생하면 다시 보낸다는 것

💡

TDM, FDM의 경우 collision이 않는다는 담보를 할 수 있는 대신 전송할 수 있는 데이터의 bandwidth가 $R/N$으로 감소하였다. TDMA의 경우는 시간을 쪼개서 쓰는 것 때문에 발생한 것이고, FDMA의 경우에는 frequency를 쪼개쓰다보니까 최대 속도가 bound가 걸리게 되는 것이다.

단, 만약 collision이 발생하면 바로 다시 보내는 것이 아니라 random delay 만큼을 기다린다. 이때 random delay는 노드마다 독립적으로 선택된다.

→ with random delay probability $p$

💡

직관적으로 생각해봤을 때, 그래야 충돌이 또 발생할 확률이 줄어든다.

구체적으로 알아보기에 앞서 용어를 정리하도록 하자

Efficiency

Definition

Fraction of successful channel use

Example

• probability of one and only one node transmitting in a random access scheme

• the probability that a time slot is used in a TDM scheme

$$\text{Throughput} = \text{Efficiency}\times \text{Channel rate R}$$

💡

Efficiency는 충돌 없이 성공적으로 전송된 패킷의 비율이라고 생각하면 된다. 즉 얼마나 Channel rate를 활용하는지에 대한 정보를 담고 있는 것이다.

Slotted-ALOHA

진행하기에 앞서 몇 가지를 전제하도록 하겠다.

• All frames consist of exactly $L$ bits

• Time is divided into slots of size $L/R$ seconds (that is, a slot equals the time to transmit one frame)

• Nodes start to transmit frames only at the beginning of slots

  💡

  즉, slot이 시작할 때만 frame을 전송할 수 있다는 것이다. 이를 통해 collision을 최소화시킨다.

• The nodes are synchronized so that each node knows when the slots begin.

• If two or more frames collide in a slot, then all the nodes detect the collision event before the slot ends.

과정은 다음과 같다.

1. When the node has a fresh frame to send, it waits until the beginning of the next slot and transmits the entire frame in the slot

2. If there isn’t a collision, the node has successfully transmitted its frame and thus need not consider retransmitting the frame (The node can prepare a new frame for transmission, if it has one)

3. If there is a collision, the node detects the collision before the end of the slot. The node retransmits its frame in each subsequence slot with probability $p$ until the frame is transmitted without a collision

   💡

   즉 앞서 언급한 것처럼 바로 보내는 것이 아니라 $p$의 확률로 이후 slot에 할당해서 transmission시키는 것이다. 만약 $(1-p)$가 걸린다면 skip the slot and toss the coin again in the next slot해주면 된다. (그림에서 확인할 수 있는 것처럼 해당 time slot을 건너뛰게 된다.)

   💡

   추가적으로 이러한 collision toss는 node별로 independent 하게 진행된다.

Pros

1. Unlike channel partitioning, this allows a node to transmit continuously at the full rate, $R$, when the node is the only active node

   💡

   TDMA, FDMA의 경우에 비해서는 channel의 bandwidth를 전부 활용할 수 있다는 점에서는 장점이 있다.

2. Highly decentralized, because each node detects collisions and independently decides when to retransmit

Cons

1. Require the slots to be synchronized in the nodes

2. Certain fraction of the slots will have collisions and will therefore be wasted

   → 위 그림에서 맨 처음 시간 상황을 참고해주면 된다.

3. A certain fraction of the slots will be empty because all active nodes refrain from transmitting as a result of the probabilistic transmission policy

   → 위 그림에서 2번째 시간 상황을 참고해주면 된다.

이때 1개의 node만 transmit된 경우를 successful slot 이라고 한다.

Maximum efficiency

$N$ : number of nodes

$p$ : the probability of the transmission

We want to find $p$ which maximizes

$$Np(1-p)^{N - 1}$$

where $N$ approaches infinity

💡

우리는 어느 특정한 노드가 성공할 것인지에 관심이 없으며, 단지 어떤 노드라도 성공하면 된다. 따라서 N을 곱해주는 것이다.

$$\frac{\partial}{\partial p}Np(1-p)^{N -1} = -Np(N - 1)(1-p)^{N - 2} + N(1-p)^{N - 1} = 0 \\ \Rightarrow N(1-p)^{N - 1} = N(N - 1)p(1-p)^{N - 2} \\ \Rightarrow p^* = \frac{1}{N}$$

where $p^*$ is a optimal probability

Therefore

$$Np^*(1-p^*)^{N -1} = (1-\frac{1}{N})^{N - 1} \\ \Rightarrow \lim_{n \to \infty} Np^*(1-p^*)^{N -1} = \frac{1}{e} \\ = 0.3679$$

💡

$N$이 무한대로 가는 상황을 고려하는 이유는, 그래야 많은 수의 노드들이 있을 때의 상황을 고려할 수 있기때문이다.

ALOHA

Same principle as slotted ALOHA but not synchronized among the nodes

💡

Slotted ALOHA와 달리 노드가 데이터를 전송할 때 슬롯 또는 구분된 시간 간격 없이 언제든지 전송할 수 있다. 즉, 특정한 타이밍에 맞추어 전송하지 않아도 된다는 것이다. 이러한 측면에서 decentralized라는 것이다.

Maximum efficiency

$N$ : number of nodes

$p$ : the probability of the transmission

→ 추가적으로 1개의 frame을 보내는데 unit of time이 걸린다고 가정한다

We want to find $p$ which maximizes

$$p\times(1-p)^{(N - 1)}\times(1-p)^{(N - 1)}$$

where $N$ approaches infinity

💡

$(1-p)^{N - 1}$이 2번 곱해진 이유는 $t_0 - 1$부터 $t_0$까지 나머지 $N - 1$개의 노드가 transmission을 시작하지 않아야되는 것과, $t_0$부터 $t_0 + 1$까지 나머지 $N - 1$개의 노트가 transmission을 시작하지 않아야되는 것을 동시에 고려해주었기 때문이다.

$$p^* = \frac{1}{2e}$$

💡

유도과정이 정확히 미분으로 되지는 않는 것 같다. 실제로 미분해서 계산해보면 답이 안나온다.

💡

추가적으로 maximum efficiency가 slotted ALOHA에 비해서 절반밖에 안나온다는 점을 주의해야 한다. 이는 decentralized하게 되면서 지불하는 cost라고 이해해주면 된다.

CSMA (Carrier Sense Multiple Access) / CSMA/CD (Carrier Sense Multiple Access with Collision Detection)

앞서 살펴본 ALOHA와 Slotted ALOHA는 기본적으로 다른 노드들의 행동에 대해서 신경쓰지 않는다. 결과적으로 장점도 있기는 하지만, 이 때문에 collision이 근본적으로 발생하게 되고 이에 따라 retransmission을 진행해야한다.

잘 생각해보면 사람의 경우 이러한 상황에서 대처하는 2가지 방법이 있다.

1. Listen before speaking

2. If someone else begins talking at the same time, stop talking

즉, 말하기전에 먼저 듣고 누군가가 동시에 말하기 시작하면 그만 말하는 것이다.

💡

ALOHA와 Slotted ALOHA는 남이 말하고 있건말건 신경쓰지 않는 protocol 방식이라고 생각해주면 된다.

💡

추가적으로 CSMA/CD는 wired Ethernet Protocol에서 쓰는 방식으로 WiFi Protocol에서는 CSMA/CA를 사용한다. 왜냐하면 무선환경에서는 Collision Detection하는 것이 어렵기 때문에 Collision Avoidance로 전략을 바꾼 것이다.

이를 네트워크에 대응하면 다음과 같다

1. carrier sensing : sensing—a node listens to the channel before transmitting

   💡

   일정 시간동안 다른 node가 transmission하고 있지 않으면 transmission하는 방식이라고 이해하면 된다.

   💡

   하지만, 거의 동시에 transmission을 진행하면 carrier sensing만으로는 이를 해결할 수 없다. 이에 등장한 개념이 collision detection이다.

2. collision detection : a transmitting node listens to the channel while it is transmitting

   💡

   transmitting하고 있는 도중에 다른 node가 transmitting하고 있는 것을 감지하면 random time만큼을 기다린 후 sense와 transmit과정을 반복하게 된다. (random time을 기다리는 이후는 추가적인 collision 발생가능성을 낮추기 위함이다.)

이러한 특성때문에 pure ALOHA나 slotted ALOHA보다 더 효율적으로 처리를 진행하게 된다. 왜냐하면 위 방식은 충돌이 전체 프레임이 전송된 후에만 감지되기 때문이다.

이때, collision detection을 수행하면 CSMA/CD (Collision Sense Multiple Access with Collision)이고, 아니면 CSMA (Collision Sense Multiple Access)라고 불린다.

Example

• Horizontal axis : the position of the each node

• Vertical axis : time

위 그림에서 $t_0$에 B는 idle이기때문에 양방향으로 transmission시킨 상황이다. 이때, $t_1$상황에서는 B가 frame을 transmission시켰음에도 불구하고 해당 정보가 $D$에 도달하지 않았기 때문에 $D$ 또한 transmission을 시킨다. 이떄문에 collision이 발생한 상황이다.

💡

가로로 표기된 것은 transmission delay와 관련이 되어있고, 해당 도형에 평행한 직선은 해당 bit가 propagation되는 propagation delay와 관련이 되어있다.

💡

이러한 부분때문에 propagation delay가 클수록 carrier sensing만으로 collision을 막을 수 없는 것이다.

위 그림은 collision을 detect한 순간 transmission을 멈추는 것이다.

단, 멈추기까지 약간의 collision detection/abort time 이 요구된다. 해당 시간 이후에 바로 transmission을 멈추게 된다.

💡

단, 주의해야할 것은 이미 출발한 bit는 그대로 간다는 것이다. 따라서 collision 이후로만 transmission이 없는 것이다. 따라서 해당 선 이후로 내려오는 영역만 없는 것이다.

추가적으로 collision을 detect한 이후 네트워크상의 다른 모든 장치들에게 충돌이 발생했음을 알리기 위해 특별한 신호인 Jam signal를 전송한다. 이 신호를 받은 다른 장치들도 자신의 전송을 중단합니다.

💡

it's essentially just noise. The device continues to transmit this noise onto the shared communication medium for a certain period of time.

Because all devices on the network segment share the same communication medium, they can all hear this noise. When they detect this noise, they understand that there has been a collision on the network. (즉, packet 형태로 전송하는 것이 아니기 떄문에 MAC broadcast나 IP broadcast 방식이랑은 차이가 있다. 단지 noise를 보내고 이를 detect하는 것이다.)

만약 Collision이 발생했다면 얼마나 많은 시간을 기다리고 sense-and-transmit 과정을 진행해주어야 할까? 해당 시간이 너무 길면 비효율적이고, 너무 짧으면 collision이 날 확률이 증가하기 때문이다.

→ binary exponential backoff 를 사용하면 이를 쉽게 해결할 수 있다.

Binary exponential Backoff

$n$ : 이전까지 발생한 collision의 횟수

각 node들은 $\{0, 1, \dots, 2^n - 1\}$ 중에 1개를 선택한다. (고른 값을 $K$라고 하겠다.)

💡

즉, collision이 많이 발생했을수록 간격이 더 증가하게 된다. 그리고 그 속도도 기하급수적이다. (그래서 이름도 binary exponential backoff이다.)

왜 이름이 Binary exponential Backoff일까? 왜냐하면 충돌이 계속 발생할 경우 binary exponential하게 증가하기 때문이다. 즉, 대기 시간의 최댓값이 2배만큼 계속 커지기 때문에 binary exponential이고, backoff는 대기한다는 측면에서 유래하였다.

Ethernet의 경우에는 기다리는 시간을 $K\cdot 512$ (bit time)으로 설정하게 된다.

💡

bit time을 s 단위로 고치려면 data rate으로 나눠주어야 한다.

추가적으로 CSMA/CD (Carrier Sense Multiple Access with Collision Detection) 방식에서는 각 노드가 새로운 프레임을 전송할 준비를 할 때마다 CSMA/CD 알고리즘이 실행되며, 이때 최근에 발생했던 어떠한 충돌도 고려하지 않는다. 따라서 새로운 프레임을 가진 노드는 다른 노드들이 충돌 후 지수 백오프 상태(exponential backoff state)에 있어도 즉시 성공적인 전송을 시도할 수 있습니다. 이런 방식은 네트워크의 전체적인 효율성을 향상시키는데 기여한다.

💡

즉, binary exponential backoff는 결과적으로 collision이 발생했을 때 얼마만큼 기다려야하느냐에 대한 문제이므로 최초의 frame을 전송하려고 할 때의 상황과 무관하다.

Efficiency

$$\text{Efficiency} = \frac{1}{1 + 5\text{d}_\text{prop}/\text{d}_\text{trans}}$$

해당 efficiency 공식은 꽤나 직관적이다.

1. 앞서 언급한 것처럼 propagation delay가 0으로 간다면 efficiency는 1로 수렴한다. 왜나하면, collision을 바로 인식해서 transmission을 즉시 중단할 수 있기 때문이다.

   💡

   앞의 예시를 참고하도록 하자. 결과적으로 $t_1$ 시점에서 collision을 인식하지 못한 근본적인 이유가 propagation을 하는 과정에서 시간이 걸리기 때문이었다.

2. 추가적으로 transmission delay가 매우 커진다면 efficiency는 1로 수렴한다.

   💡

   대부분의 시간 동안 채널은 데이터를 전송하는 데 사용되고 있으므로 낭비되는 시간(즉, 아무런 데이터도 전송되지 않는 시간)이 줄어들기 때문에 efficiency가 1로 수렴한다고 이해하면 된다.

Efficiency in Random Access Protocols

Taking-Turns Protocols

앞서 언급한 multiple access의 이상적인 조건을 다시 알아보도록 하자

1. when only one node is active, the active node has a throughput of $R$ bps

   💡

   즉, 혼자 이용하고 있을 때는 모든 bandwidth를 다 쓸 수 있어야 한다는 것이다.

2. when $M$ nodes are active, then each active node has a throughput of nearly $R/M$ bps

   💡

   즉 $M$개의 node와 공유하고 있는 경우 평균적으로 throughput을 $R/M$만큼 보장해주어야 한다는 의미이다.

하지만, ALOHA와 CSAM의 경우에는 1번째 조건은 만족하지만, 2번째 조건을 만족하지 못한다.

→ 이러한 문제점을 해결하고자 등장한 protocol이 taking-turns protocols 이다.

기본적으로 여러가지 variation이 존재하지만 2가지만 살펴보도록 하겠다.

Polling protocol

1. 속한 노드들 중 하나를 master node로 지정한다.

   → master node는 round-robin형태로 돌아가면서 지정한다.

2. master node가 순서대로 노드들을 할당한다.

→ 단, master node에 문제가 생기는 경우에는 문제가 발생할 수 있고 polling delay가 발생할 수 있다는 점은 단점이다.

→ 반면 collision과 empty slot을 막을 수 있다는 점에서는 효율적이다.

💡

대표적인 예시가 Bluetooth이다

Token passing protocol

이 방식은 polling protocol와 달리 master node가 존재하지 않는다. 대신 token 이라는 것이 존재해서, 이것들을 node들끼리 정해진 순서대로 교환한다.

이때, transmit할 frame이 존재하는 경우에만 해당 token을 가지고 있고 그렇지 않은 경우에는 다음 node에게 해당 token을 넘긴다.

💡

즉 token을 가지고 있는 경우에만 transmit할 수 있는 것이다.

→ 단, 1개의 node가 고장나거나 token을 받았음에도 불구하고 release를 하지 않는다면 문제가 발생할 수 있다.

→ 반면, decentralized하고 굉장히 효율적이라는 장점이 존재한다.

💡

대표적인 예시가 FDDI(fiber distributed data interface) protocol과 token ring protocol이다

Note

The term 공유기 in the consumer market often refers to a device with Wi-Fi capabilities. Such routers typically perform three main roles:

1. Switching Function: They provide multiple Ethernet ports to enable direct communication between multiple devices on a LAN (Local Area Network).

2. Routing Function: They are responsible for the connection to the ISP (Internet Service Provider) and forwarding packets to external networks.Wi-Fi

3. Access Point Function: They allow wireless devices to connect to the LAN.

So, in this sense, you can consider a 공유기 as a type of router. However, in strict networking terminology, "router" and "switch (or network switch)" refer to devices that perform different roles.

A router forwards traffic between networks. A switch (or network switch) transfers data between devices within one Local Area Network (LAN).

💡

즉, switch는 동일한 LAN상에 위치한 host끼리 data를 direct하게 주고받을 수 있게하는 역할을 수행하는 것이고, 반면 router는 서로 다른 network (subnetwork)끼리 data를 주고받을 수 있게끔하는 역할을 수행한다.

💡

공유기는 이 2가지 기능을 동시에 하고 있다고 생각해주면 된다. 추가적으로 Ethernet port에다가 LAN선(Ethernet cable이라고도 불림)을 꽂는 것이다.