Random access protocols

• 한 번에 한 명씩 말해라

• "randomness"를 이용해서 충돌을 피한다

• If two people start to talk at the same time, they both stop, wait for a moment, and start to talk again

ALOHA

• If there is anything to send, send it
• If collision occurs, wait for a certain duration(random) of time and retransmit

Pure ALOHA

• sender가 보낼 게 있으면, 즉시 보낸다
• receiver가 frame 받았으면, ACK 보낸다
• timeout period 내에 ACK이 오지 않으면, sender가 frame을 다시 보낸다.
• 하지만, sender does not retransmit immetiately
  : the sender waits for a random delay and retransmit

• 두 frame이 같은 겹치면, 바로 충돌이 발생한다

How long should it wait?

• 0부터 2K-1 사이의 random number R을 잡는다.
• Wait for T x R seconds (T : fixed time slot)
• K는 충돌 날 때마다 K++.
  K is incremented after each timeout.
  binary exponential backoff(기다림)
  

How long time slot?

• Transmission time vs. maximum propagation time 둘 중에 개큰걸로 한다.
  비슷하면 Tfr + Tp로 해라.

Transmission delay(Tfr) : Duration between the time the first bit leaves the source and the time the last bit leaves the source
Propagation delay(Tp) : Duration of time a bit travels from source to destination distance / speed of travel

Q. A network of nodes uses pure ALOHA as medium access protocol. Backoff time TB is calculated as follows :

• TB = T x R
• T(time slot) = 20ms
• R = rand(0, 2K-1)
  If K = 1, what are the possible backoff durations?
  A. 뭐야... 0 or 20ms... 당연한걸 물어..

Vulnerable Time

• The vulnerable time is the duration of time in which a collision occurs, if another frame is tranmitted
  (뭔 말인지 잘 모르겠는데..?...)

• Assume Tp << Tfr
• frame A의 transmission이 t에서 시작해서 t + Tfr에 끝난다고 하자
• 그럼 t - Tfr 부터 t + Tfr 사이에는 아무도 transmit할 수 없다.
• **Vulnerable time : 2 x Tfr
  

Q. A pure ALOHA network transmits 200 bit frames on a shared channel of 200kbps. What is the requirement to make this frame collision-free? (neglect propagation delay)
A. 200kbps => 1초에 20,000 bits => 1ms에 200bit => Tfr = 1ms
앞으로 1ms, 뒤로 1ms, 총 2ms 동안 아무도 건들지 마.

Throughput

• pure ALOHA의 throuhgput을 계산하기 위해서, S를 다음과 같이 계산한다
  S = G x 2-2G
• S : ratio of frames that are successfully tranmsitted
• G : average number of frames generated in the systme during Tfr
  만약 G = 1이면, S = 1 x e-2 = 0.135
  => 1000 frame이 generated per second in time, 135frame만 성공적으로 보내진다.

  e-1 = 0.367
  e-2 = 0.135
  e-0.5 = 0.606

Q. A pure ALOHA network transmits 200 bit frames on a shared channel of 200kbps. What is the number of frames that are successfully sent if the system produces
(a). 1000 frames per second
(b). 500 frames per second
(c). 250 frames per second
A. For (b),
transmission time Tfr = 200bits/200kbps = 1ms
system creates 500 frames per second, it is 0.5 frames per Tfr(1ms)
=> G = 0.5
S = G x e-2G = 0.184 => 성공률 18.4%
Hence, 500 x 0.184 = 92 frames will survive.

Slotted ALOHA

Throughput

• S = G x e-G

• 위 문제 그대로 slotted 로 풀면, 성공률 = 0.303
  => 500 x 0.303 = 151 frames will survive

---

CSMA

• ALOHA에서는, 다른 node들이 transmits하는 도중에 node가 transmsiion을 시작해버린다.
  운이 좋으면 vulerable time period에 다른 node들이 안건들고,
  운이 나쁘면 충돌이 발생한다.

• 우리가 channel을 sense하는 하드웨어를 이용한다면, 충돌을 더 줄일 수 있다.

• CSMA(Carrier Sense Multiple Access)
  : "Listen before you talk"

• Node가 frame을 전송시키려고 할 때,
  먼저 sense the channel,
• If there is no signal on the channel(idle), go ahead and transmit.
• If there is signal on the channel(busy), do not transmit

Can CSMA avoid collision completely? No.

• t1에서 B가 D에게 신호를 보낸다.
• t2때 아직 그 신호가 C를 넘기 전이라 C가 sensing했을 땐 signal이 없는 걸로 확인된다
• 그래서 t2에 C가 신호를 쏴버린다
• 충돌 빠바밤

Vulnerable Time

• Vulnerable Time = propagation time Tp
  

---

If the channel is busy, what should node do?

1-persistence CSMA

• channel이 busy하는 동안 계속 sensing한다.
• 그러다 idle해지는 순간, transmit
• 근데 여러 node들이 다 이러고 있을 거니까, 충돌 확률이 올라간다.

non-persistence CSMA

• channel이 busy하는 동안 일정 시간을 두고 sensing한다.
• idle해지면, transmit
• 충돌 확률은 낮아지겠지만, node들이 이미 channel이 idle해졌는데도 기다리고 있어서 시간 낭비가 발생한다.

p-persistence CSMA

• 두 개 섞어놨다.
• channel이 busy하는 동안 계속 sensing한다
• idle해지는 순간, 확률 p를 두고 transmit or wait

---

CSMA / CD

• CD(collision detection)
• 충돌이 발생하면, sender가 충돌을 감지하고 행동한다.
• 이더넷(유선)에서 사용한다.

Collision situation

• Node A에서 frame을 쏜다
  그게 C에 도착하기 전, C가 frame을 쏜다.
• 충돌이 발생한다.

• 충돌 발생한 것을 어떻게 알까?
• 내 frame을 전송하고 있는 동안, 다른 frame이 도착하면, 충돌이라고 감지한다.

• 충돌된 frame이 도착할 때, 내가 반드시 내 frame을 전송하고 있어야 한다.
• 이미 내 전송이 일찍 끝났다면, 나는 충돌을 감지하지 못한다.

Condition for collision detection failure

• Node A에서 frame을 쏜다. (t1)
• Node C에서 frame을 쏜다. (t2)
• collided frame이 A에 도착한다 (t4)
• 위에 했던 얘기 그대로다. t4 전에 A 전송이 끝났다면, 충돌을 감지하지 못한다.

가장 최악인 경우는 언제일까

• 위 그림상에서는 A에서 D.
  가장 멀리 있는 애한테 쐈는데, 걔가 받기 바로바로바로바로 직전에 걔가 쏜다.
• 어쨌든 충돌은 발생했고,
  A 입장에서 이 충돌을 감지하려면 D가 쏜 프레임이 A에 도착할 때까지 A는 계속 쏘고 있어야 한다.
• Tfr ≥ 2 x Tp 정도는 되어야 한다.
• 그래서 frame size를 조절해 주어야 한다. 너무 많이씩 보내면 금방 끝나자뉴

Q. A network using CSMA/CD has a bandwidth of 10Mbps. If the maimum propagation time is 25.6µs, what is the minimum size of the frame?
A. Tp = 25.6µs
=> Tfr = frame size / 10Mbps ≥ 51.2µs
=> frame size ≥ 51.2 x 10-6 x 10 x 106
=> 512 bits
=> 64 bytes

When collision is detected,

Binary exponential backoff similart to ALOHA

---

CSMA / CA

• 충돌을 감지할 수 없는 system에 사용된다
• 무선(Wifi)에 이용된다.
  switch를 해서, 말하거나 듣거나, 하나말 할 수 있다.
• The Wi-Fi interface is half-duplex, which means it cananot transmit and receive at the same time.

• 충돌 발생 전 random backoff를 한다
• wait for ACK
• ACK이 오지 않으면 충돌로 간주한다.
  충돌 발생하면 increase backoff exponentially

IFS(inter frame spacing)

• 1-persistence CSMA처럼 계속 sensing한다.
• idle이 감지되는 순간, IFS만큼 쉰다.
  (Even if channel is sensed idle, another node might just started transmission. IFS is inserted in order to aviod collision.
• IFS 이후에는 random number x time slot 만큼 더 기다린 후, send한다.

Contention window

• A range from where a node selects a random number
• Count Down을 진행한다
• 주의). channel이 idle일 때에만 count를 진행한다. 중간에 busy가 되었으면 count를 멈추고 다시 idle이 될 때까지 기다린 후, IFC 기다리고 다시 count down 진행한다.

Binary exponential backoff

• 충돌이 발생하면, the contention window size는 두 배가 된다
  (0-31 => 0-63)
• frame이 성공적으로 전송되면, contention window는 원래 range로 돌아온다.

Q. time slot = 20µs. IFS = 50µs. initial contention window = [0-31]
transmission time of a frame = 100µs
propagation time = 0 (neglected)
no ACK
Nodes A, B, C are in the same wireless LAN
A chooses 10, B chooses 15, C chooses 20 for random number.

• 0µs : A, B, C 모두 IFC만큼 기다린다 ~ 50µs
• 50µs : count down 시작 (A : 10, B : 15, C : 20)
• 250µs : A의 count가 끝났다. (10 x 20µs). A가 전송 시작하고, BC는 A의 signal 확인해서 count down 멈춘다
• 350µs : A 전송이 끝났고, BC는 IFC만큼 기다린다
• 400µs : B,C의 남은 count down을 시작한다 (B : 5, C : 10)
• 500µs : B의 count가 끝났다. (5 x 20µs). B가 전송 시작하고, C는 B signal 확인해서 count down 멈춘다
• 600µs : B 전송이 끝났고, C는 IFC만큼 기다린다
• 650µs : C가 남은 count down을 시작한다 (C : 5)
• 750µs : C의 count가 끝났다. (5 x 20µs). C가 전송 시작한다
• 850µs : C 전송 끝났다.