=== Medium Access Control ===
1. Components of data link layer
data link layer에 두가지 큰 기능 중 하나는 data link control이다. error detection이나 재전송을 하는등의 기능을 수행한다.
오늘은 Multiple-access resolution은 매체를 여럿이 공유할때 누가 언제 매체를 통해서 전송을 할지를 결정하는 것을 이야기 한다.
What is multiple access?
• Techniques to share a common link
• point-to-point vs. shared
• In shared link, only one user should transmit at a time -> medium access control necessary
디바이스간 정보전달을 위해서는 매체가 필요하다. 회선은 여러명이 공유하는 경우가 많다.
위의 그림을 보면 point-to-point는 직접적으로 데이터를 전송한다. shared link에서 데이터 전달은 shared link로 데이터를 전송하고 데이터는 링크 전체를 돌게 된다. 그러면 다른 매체도 수신을 받을 수 있다. 하지만 이때 패킷을 까보고 자신에게 보낸것인지 확인하고 버릴지 가질지를 결정한다.
multiple access가 필요한 이유는 수신시 두개 이상의 신호가 겹치면 데이터 수신율이 떨어진다. 에러가날 가능성이 높아진다. 그래서 shared link에서 한명만 전달할 수 있도록 하는게 multiple access resolution이고 그때 사용하는것이 medium access control이라는 기술이다.
Types of multiple access protocols
Random access : 랜덤에 의존해서 데이터 전달시간을 다르게 만드는 것이다.
Controlled-access : 미리 누군가가 시간대를 결정한 것이다.
Channelization : 채널을 여러개로 나누는 것이다.
=== Random Access Protocols ===
• Collisions are avoided using “randomness”
• Similar to a group of people chatting in a room
– No one knows when a person will start talking
– If two person starts to talk at the same time, they both stop, wait for a moment, and start to talk again
랜덤에 의존해서 문제를 해결하겠다는 것. 모임을 왔는데 누가 먼저 입을 열지모른다. 그냥 랜덤이다. 그런데 갑자기 두명이 한번에 말하면 멈칫하다가 다시 시작하는 식으로 처리할 수 있다.
1. ALOHA
• Developed in 1970s at University of Hawaii
• A basic protocol in the line of random access protocols
• Summary
– If there is anything to send, send it.
– If collision occurs, wait for a certain duration of time and retransmit
가장 간단한 random access protocol이다.
만약에 어떤 device가 전송할게 있으면 일단 전송한다. 만약에 collision발생시 일정 시간을 기다렸다가 재전송한다.
Pure ALOHA
• If sender has a frame to send, send it immediately.
• When receiver receives the frame, send ACK.
• If ACK does not arrive during timeout period, sender retransmits the frame
• However, the sender does not retransmit immediately; the sender waits for a random delay and retransmits
어떤 device가 전송할 frame이 존재시 즉시 전송한다.
수신자는 만약에 frame을 받으면 ACK를 보낸다.
ACK이 올때까지 기다린다. 만약 오지 않으면 frame을 재전송한다.
알로아의 특징 : 재전송할때 즉시 보내지 않고 random delay만큼 기다린다.
• If two frames are on the link at the same time, a collision occurs
Frame 1.1을 전송해서 ACK를 받을때까지 다른 Station이 보내지 않으면 성공적인 전송이다.
그런데 station 1.2, 2.1, 3.1, 4.1은 충돌이 발생한다. 그래서 수신자가 제대로 수신 받지못한다. 그러면 여기에 있는 frame들은 모두 날아간다.
Frame 2.2, 4.2도 날아간다.
collision이 생길 가능성이 매우크다.
• What does the sender do when a frame is lost?
– Wait for some random time and retransmit
• How long should it wait?
– Choose a random number R between 0 and 2^K-1
– Wait for T x R seconds (T: time slot)
– K is incremented after each timeout
-> binary exponential backoff
frame loss가 나면 random한 시간을 기다렸다가 재전송한다고 했다. 그러면 랜덤 number R을 0 ~ 2^K-1 에서 구하게 된다.
두 device가 각각 골라서 TxR초만큼 기다렸다가 재전송을 한다.
이때의 K값은 처음에 random number가 결정된 다음부터 K를 1씩 증가시킨다. 이것을 BEB(binary exponential backoff)라고 부른다. 계속 늘려가다보면 언젠가는 충돌이 나지 않을 것이다.
K를 계속 증가시킬수는 없다. 즉 K를 계속 증가시키는데도 Kmax보다 값이 커진다면 abort 시켜버린다.
그럼 T는 무엇으로 설정해야 하는가? 보통은 Transmission time이 propagation 보다 크면 transmission으로 하고 propagation time이 더 크면 propagation을 기준으로 한다.
자꾸만 나오는데 이게 뭔 소리인지 모르겠어서 적는다.
Transmission은 송신자가 프레임을 보내는 시간이 Tfr이고
Propagation은 수신자가 프레임을 받기까지 걸린시간이 Tp이다.
Example
• 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, 2^K-1)
• If K = 1, what are the possible backoff durations?
Backoff time은 랜덤하게 기다리는 시간을 이야기 한다. TxR로 구할 수 있다.
만약 K = 1이면 어떤게 가능한가? 그러면 R = [0,1]이다. T가 20이니 [0,20]이 된다.
Vulnerable time
• Suppose a frame is transmitted on the channel. The vulnerable time is the duration of time in which a collision occurs, if another frame is transmitted.
내가 전송하는데 다른사람도 전송하면 문제가 생긴다. Vulnerable time은 내가 어느 구간까지 나에게 간섭이 없어야 내 전송이 끝까지 마칠 수 있다.
• Vulnerable time of pure ALOHA
– Assume Tp is minimal compared to Tfr
– Suppose A’s transmission starts at t and finishes at t + Tfr
– No one should transmit between t – Tfr and t + Tfr
– Vulnerable time: 2 x Tfr
어떤 frame을 전송을 하는데 그 frame의 크기는 다 동일하다고 가정하자. A가 전송되는데 A라는 frame이 전송되었을때 B와 C는 언제 전송시 문제가 생기는지를 보자
B 같은 경우 A와 겹친다. 그래서 B는 가급적 가장 왼쪽 점선보다 이전에 출발해야 문제가 생기지 않는다.
결국은 2xTfr이 Vulnerable time이라고 볼 수 있다.
Throughput
ALOHA에서 모델링으로 계산할 수 있는게 Throughput이다. 초당 데이터를 얼마나 전달할 수 있는가이다. 에러가 너무 많이 나면 Throughput이 떨어지게 된다.
ALOHA를 사용할때 모델을 사용할 수 있다.
• To calculate throughput of pure ALOHA, we compute S as follows
S = G × e^(−2G )
• S: ratio of frames that are successfully transmitted
• G: average number of frames generated in the system during Tfr
S는 성공적으로 전송이 된 frame의 비율이다. G는 Tfr이라는 시간동안 그 시스템 안에서 frame이 몇개가 생성이 되는지이다.
• If G = 1,
• S = 1 x e^-2 = 0.135
• If 1000 frames are generated per second in the system, and Tfr = 1ms, then 135 frames can be successfully sent
• e^-1 = 0.367
• e^-2 = 0.135
• e^-0.5 = 0.606
1초에 1000개의 프레임이 만들어지고 있을때 전송시간은 1ms이다. 그러면 몇개의 프레임이 전송이 되는지를 알고 싶다.
Tfr = 1ms이다. 초당 1000프레임이 생성되고 있다. 그러면 1ms에는 1frame이 생성되고 있다는 이야기 이다. 그러므로 G = 1이다. S = e^-2이다.
그러므로 1초에 1000개의 프레임이 생기면 그중 135개 프레임이 정상적으로 도착할 수 있다고 계산해볼 수 있다.
Example
• 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 (all stations together) produces
• a. 1000 frames per second
• b. 500 frames per second
• c. 250 frames per second
Tfr = 200/200k = 1ms
b. G = 0.5이다.
Solution for b.
• Tfr = 200 bits / 200 kbps = 1ms
• If the system creates 500 frames per second, it is 0.5 frames per Tfr -> G = 0.5
• S = G x e^(-2G) = 0.184
• So 500 x 0.184 = 92 frames will survive
결론적으로 1초에 92프레임이 정상적으로 도착한다고 생각할 수 있다.
Slotted ALOHA
frame 전송시간을 간혈적으로 맞추어 놨다는 것이 ALOHA와 유일한 차이점이다.
이렇게 보면 collision이 많이 줄어들었다고 볼 수 있다.
• Throughput of slotted ALOHA
• S = G x e^-G
• Suppose we send 200-bit frames at 200kbps. How many frames can be successfully sent if
– 1000 frames are generated per second
– 500 frames are generated per second
– 250 frames are generated per second
slotted ALOHA의 vulnerable time은 그냥 Tfr이다. 그냥 전송시 프레임에 딱맞추어서 전송하면 된다. 그러면 다른 프레임은 언제 전송하면 안되는가가 중요한 부분이다.
받은 구간이 중간에 생기는 경우 가장 빠른 시점에 전송하려고 한다. 만약 3.1이 그렇다면 2.1과 충돌나기에 또 한칸을 미뤄주어야 한다. 그래서 vulnerable time이 T, 1 slot이다.
2. CSMA (Carrier Sense Multiple Access)
• In ALOHA (pure/slotted), a node starts transmission even if other nodes are transmitting.
– If the node is lucky, no other node transmits in the vulnerable time period
– If the node is unlucky, a collision occurs
알로하의 특징은 다른 노드가 전송하는데도 내가 전송을 할 수 있다는 점이다.
근데 이게 충돌이 많이 일어난다. 그래서 이 충돌을 막기 위해 Carrier Sensing Hardware가 필요하다. 이 것은 medium sensing을 한다. 내가 사용하고 있는 shared medium에 어떤 데이터가 전달이 되고 있는가를 monitoring하는 것이 medium sensing이다.
• If we use hardware that can sense the medium (channel), we can further reduce collision
• CSMA: "Listen before you talk"
CSMA
• When a node has a frame to transmit
• It first senses 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
프레임을 전송전에 senseing을 한다. 채널에 signal이 없다.(idle상태) signal이 있다면(busy 상태) 그러면 나는 전송하면 안된다.
• Human analogy
– Suppose a group of people are chatting in a room
– I want to talk
– If no one is talking, I start to talk
– If someone is talking, I wait
사람으로 치면 다른 사람 말할때 나는 침묵인것이다.
• Can CSMA avoid collision completely?
그래서 collision이 완전히 해소가 되는가?
• Can CSMA avoid collision completely? No.
– If B transmits at time t1, it reaches C at t3
– At t2(t1< t2< t3), C sees channel as idle (no signal).
– If C transmits at t2 a collision occurs.
B가 전송을 했다. 그러면 shared medium을 따라 퍼지게 된다. 전송시간이 t1이고 C에 도착시점이 t3라고 하자. 그런데 여기에 도착을 해야지 C가 회선에 무언가 전송된것을 감지할 수 있다. 하지만 그 사이에 C가 전송을 했다면 collision이 발생한다.
• Vulnerable time: Tp(propagation delay)
전파시간하고 CSMA가 관련이 있다.(전송은 ALOHA와 관련) A가 t1 시점에 전송해서 가장 멀리 떨어진게 D라고 할때까지 걸리는 시간이 propagation time이자 vulnerable time이다.
즉 끝과 끝이 만날때까지의 시간이 vulnerable time이라고 볼 수 있다.
• If the channel is busy, what should the node do?
• Depending on the action, there are 3 types of CSMA.
• 1-persistent CSMA
• non-persistent CSMA
• p-persistent CSMA
CSMA에는 3가지 종류가 존재한다. 채널이 busy 상태일때 node가 어떻게 동작하느냐에 따라 갈린다.
1-persistent CSMA
• Continuously sense the channel while the channel is busy.
• As soon as the channel becomes idle, transmit
• Since multiple nodes can wait for the channel to become idle, collision probability is high.
busy가 감지되면 idle 상태가 될때까지 대기하다가 전송하다.
문제점은 서로간의 눈치게임을 보다가 한번에 들어가서 collision이 발생할 수 있다.
Non-persistent CSMA
• If the channel is busy, the node waits for some time and sense the channel again.
• If the channel is idle, transmit
• Collision probability is low, but the node can waste time waiting even after the channel becomes idle
일정 주기를 가지고 sensing을 하는 방법이다.
p-persistent CSMA
• While busy, the node continuously sense the channel until it becomes idle.
• If the channel becomes idle
– The node transmits with probability p
– The node defers transmission with probability 1-p
busy일때는 1-persistent처럼 작동, idle이 되면 각 노드는 p라는 값이 있어서 p(0...1)의 확률로 전송한다.
Three types of CSM
