Network : Multiple Access : Random Access

Data link layer의 두 가지 기능

Data Link Layer는 Data link control과 mulitiple-access resolution의 기능을 가지고 있다.

 

Data link control은 한 client가 다른 client or server와 통신을 할 때 도와주는 control이다. 또한 upper에 해당한다.

 

우리가 이번 posting에서 확인할 것은 Multiple Access이며, 매체에 data를 언제 보내야할지에 대해 control하는 부분이다. 이는 여러 client들이 통신할 때, 충돌하지 않게 도와주는 control에 대해서 배울 것이다.

 

 

multiple-access protocol의 종류

 

1. Random Access

---

Random Access은, 각 station 들은 medium에 다른 station을 고려하지 않고 보내게 되는 방법을 쓰는 것을 말한다.

만약 conflict 난다면, Frame들은 파괴되거나 손상이 갈 것이다.

 

conflict를 피하기 위해, 각 station마다 다음과 같은 과정을 따른다.

 

1. 언제 medium에 접근할까?

2. medium을 누가 쓰고있으면 어떻게 할까?

3. data를 보내는 것을 성공, 실패의 유무를 어떻게 알아낼까?

4. 만약 conflict가 일어났다면, station은 어떻게 조치를 취해야 할까?

 

 

1.1 ALOHA network

 

ALOHA

Base station이 중앙 controller로 존재한다. 이 base station은 hop로써 역할을 한다. 

 

pure ALOHA Random Access

말 그대로 Random하게 보내는데, Pure 한 ALOHA는 다른 station에서 보내던 말던, 그냥 자신의 data를 보낸다.

이렇게 하면, 위의 그림과 같이 collision이 일어난다.

 

ALOHA's Algorithm

ALOHA의 알고리즘을 살펴보면, 

1. Frame을 보내고 wait-time 을 기다린다.

2. 만약 Ack를 받았다면 성공이지만, 받지 못하였다면, K +=1을 한다.

3. K가 Kmax인 15보다 크다면, 버리지만, 작다면 0~2**k -1한 수, R를 골라서 아까 Tp만큼 기다린 시간을 곱해 더 기다린다.

4. 그 후 frame을 다시 보낸다.

 

이런 알고리즘으로 돌아간다. 횟수가 반복이 될수록 기다린 시간이 짧았다는 것을 의미,

random으로 뽑는 R의 숫자가 그만큼 커져서, 기다리는 시간의 폭이 길어진다.

물론 random한 수가 계속 0이면, conflict는 계속 나겠지만 확률적으로 매우 적음을 우리는 알 수 있다.

 

 

ALOHA의 출력량은 S = G × e −2G, Smax는 G가 0.5일 때, 나타난다. (S는 성공적으로 전송된 평균 개수, G는 1 frame을 보낼 때, 시스템에 의해 생산되는 frame의 평균 개수)

 

1.2 Slotted ALOHA

Slotted ALOHA

Pure한 ALOHA는 time을 slot으로 잡았지만, Slotted는 slot으로 나눠 Frame을 보낸다.

 

Slotted의 출력량은 S = G × e−G, Smax는 G=1 일 때, 0.368, (한 슬롯당 한개의 Frame이 들어오는)

 

정해진 시간을 맞춰 동기화를 시켜서, data를 바로바로 보내자가 이론적의미

 

 

1.3 CSMA (Carrier Sense Multiple Access)

 

원리

CSMA는 "전송하기전에 sense하자, 말하기 전에 일단 먼저 듣자!!!" -> collsion을 낮추고 performance 올리자.

 

단점

1. sensing 하는 구간에서는 충돌이 적지만, sensing을 하지 않는 구간에서는 충돌이 많이 일어난다.
2. 아무도 안 보낼때 보내면 받을수있지만, 전송되는 중인데 보내면 conflict가 일어난다. (propagation delay)

 

 

EX)

Space & Time Model of collsion in CSMA

B, C에서 Data를 양 옆으로 보내려 하는 그림이다.

가운데에 B-C 사이에 검은색 부분은 서로 Data가 충돌이 나는 지점을 말한다.

물론 B, C에서 signal이 들어오지 않으니 Data를 보낸 것은 맞지만, 전파되는데 시간이 서로 맞지 않아 신호가 없었더라도 충돌가능성이 있다.

 

1.4 Persistence methods

정의

Persistence method는 "medium이 바쁜 것을 sense하는 station을 정의"하는 과정이다.

 

• 1-persistence method : station이 line idle을 발견한다면 frame을 즉시 다시 보낸다.
• non-persistent method : frame을 보내는 station이 line을 sense 한다. line이 idle이라면 즉시 보낸다. 만약 idle이 아닐경우, random한 시간을 기다리고 다시 sense한다.
• P-persistent method : P라면 station은 frame을 보낸다. q=1-p라면 station은 wait 한다. 충돌이 많을 것 같으면, time slot을 늘린다.

 

1.5 CSMA/CD (collision detection)

원리

CSMA/CD

각 station 마다 collision을 detect 한다고 보면 된다. 

signal이 들어올 때, collision이 발견되면 signal의 진폭이 상쇄되거나 중첩되는 현상이 벌어진다.

station은 signal을 분석해서 collision이 일어남을 알 수 있다.

collision을 detect하면 jamming signal을 보내서 충돌 signal이 형성됨을 알 수 있다.

Detect 하면 frame을 버린다.

동작 과정

CSMA/CD의 detect 방법

위의 그림처럼 collision이 일어나면 energy level이 바뀌게 된다. 이로써 collision이 일어남을 detect 한다.

 

CSMA/CD는 보통 line으로 연결되어있는 network에서 빛을 발한다.

이유는 CD가 signal의 energy level을 보고 collision이 일어남을 판단하기 때문이다.

 

 

1.6 CSMA/CA (collision avoid)

CSMA/CA

목적

CSMA/CA 의 목적은 collision을 피하기 위해 만듬에 있다.

주로 energy level을 detect 하지 못하는 wireless network에서 쓴다.

 

원리

위의 그림을 보면, 가상의 line을 sense 했을 때, line이 바쁘다면, idle 구간을 찾아서 처음을 무조건 IFS (Inter-Frame Space)구간으로 남겨둔다.

여기서 바로 보내지 않는 이유는 idle이 시작됬지만, 다른 client가 data를 이미 보내고 있는 중이라면, 이 때 보내게 되면 충돌이 일어나기 때문이다. 이를 보장하기 위해 bandwidth를 낭비하더라도 IFS 만큼 기다린다.

 

IFS 란 inter-Frame space로 바로 데이터를 송출하지 않고, 일정 대기하는 접근연기(Access delay)를 말한다.

만약 정말 급한 data가 있다면, 우선순위를 높여서 IFS 구간 때 보내기도 한다.

 

IFS이후 Contention window 만큼의 slot을 나눠둔 후, 그 이후에 보낸다.

 

만약 collsion이 일어난다면, k 값을 증가시켜서 slot의 구간을 늘린다.

 

동작 과정

CSMA/CA는 channel이 바쁠경우, timer를 재시작하는 것이 아니라, timer를 멈춰두고 channel이 idle이 되기 전까지 기다린 후, timer를 다시 재시작한다.

 

CSMA/CA 알고리즘

1. idle channel이 되면, IFS 구간 만큼 기다린다.
2. idle이 지속되지 않는다면 다시 idle channel이 되기 전까지 기다린다. idle이 지속된다면 R(0~2**k -1)의 random숫자를 뽑는다.
3. R slot 구간만큼 기다린 후 frame을 보낸다.
4. ack가 온다면 성공, ack가 오지 않는다면, 충돌이 일어남을 판단. k +=1 하고 다시 idle channel이 되기 전까지 기다린다. (k 는 15를 넘기지 않는다.)