컴퓨터 네트워크를 공부하면서 정리를 한 내용들 입니다.

-참고 K-mooc 부산 대학교 유영환 교수님 : 컴퓨터 네트워크 강의

실제 collision이 발생 할 수 있는 랜덤 엑세스 기술을 알아봅니다.

Random Access Protocols

랜덤 엑세스 기술은 Channel Partitioning이나 Taking Turns와 같은

마스터의 기능이 전혀 없습니다.

각 개별 노드들이 알아서 눈치껏 치고 빠지면서

전체적으로 데이터를 전송하는 형태입니다.

그래서 여러 가지 이상적인 MAC 프로토콜이 가져야 되는 특성 중의 하나인

하나의 노드만이 전송 할 게 있다면 채널의 전체 full data rate을 보낼 수 있다는 장점과

미리 노드들이 서로 협의를 하는 것 없이 개별적으로 수행 한다는 장점이 있습니다.

단점은 알아서 치고 빠지기 때문에 collision이 발생 할 수 밖에 없으므로,

collision을 어떻게 감지 할 것이며, 어떻게 데이터를 복구하거나

collision이 발생한 데이터를 어떻게 다시 전송하거나 할 것이냐 라는 문제를 해결 해야합니다.

가장 대표적인 랜덤 엑세스 프로토콜로는 ALOHA 계열과 CSMA 계열이 있습니다.

ALOHAnet

ALOHAnet는 university of hawaii에서 개발 되어서 71년도에 처음 사용이 되었습니다.

하와이는 8개의 섬으로 이루어져 있습니다.

이 섬들을 유선으로 연결 하기 위해 바닷속으로 링크를 까는 것은 매우 어렵습니다.

그래서 무선을 통해서 네트워크를 연결해야 한다는 요구사항이 있었고

그것을 기반으로 만들어진 네트워크 입니다.

Additive Links Online Hawaii Area 이것을 줄여서 ALOHA라고 지어져습니다.

ALOHA Protocol

이 알로하 네트워크의 특징은 모든 프레임들이 같은 길이를 갖는다는 점 입니다.

무선에서 날아간다고 해서 무선에서의 전송 시간을 air time 이라고 하는데

모든 디바이스들의 전송하는 rate이 같고 데이터의 길이가 같으면

결국 air time도 다 동일하게 됩니다.

각 노드가 전송 할 프레임이 준비가 되면 바로 전송을 합니다.

collision이 발생을 하면 다시 랜덤한 시간이 흐른 뒤에,

다시 성공 할 때 까지 재전송을 통해서 collision 문제를 해결 하게 됩니다.

알로하 네트워크가 처음 나왔을 때,

여러 노드가 있고 중앙 서버에다가 전송하는 형태였습니다.

그래서 up-link 채널과 down-link 채널이 나누어져 있었고,

각 개별 노드들이 알아서 전송을 하면 서버는 그것을 받았다가

down-link 채널로 그것을 똑같이 retransmission,

에코 형태로 데이터를 보내게 됩니다.

down-link를 감지를 하고 있었다면 데이터의 도착 여부를 알 수 있습니다.

그런데 일정한 시간이 지나도록 도착 하지 않았다는 것은

collision이 발생 했다고 볼 수 있는 거고, 일정 시간 뒤에 재전송을 합니다.

For example

개별 노드 `A`, `B`, `C`, `D`, `E`, `F`가 각자가 준비 되면 전송 하는 형태이고,

예시에 파란색으로 되어 있는 것은 전송이 성공 한 경우로써,

`A`와 `B`는 전송되었고, `E`에서 전송하는 중간에 `C`가 전송을 시작 했습니다.

그러면 일부라도 겹치게 되므로 프레임은 에러가 발생 할 수 있습니다.

전송 시간이 겹침으로 인해서 수신자가 제대로 받지 못할 수 있게 됩니다.

그래서 이런 경우 재전송을 하게 됩니다.

ALOHA Efficiency

알로하 네트워크는 매우 간단하지만 효율이 매우 낮았습니다.

알로하에서는 모든 프레임의 사이즈는 다 같습니다.

그래서 한 프레임을 전송 하는 air time을 1이라고 가정을 해봅시다.

t0에 전송 시작한 노드 i의 프레임(노란색)이 정상적으로 동작하기 위해서는

초록색 프레임이나 보라색 프레임을 전송하는 노드가 없어야 됩니다.

결국 하나의 프레임 전송이 성공하기 위해서는 자신이 전송하는 시간 간격,

그 안에도 다른 노드가 전송하지 않아야 되지만,

전송 시각을 기준으로 한 프레임 이전의 시간에서도

다른 노드가 전송하지 않아야 된다 라는 규칙이 있습니다.

efficiency

위 규칙을 가지고 시스템의 efficiency를 한 번 따져 봅니다.

노드의 개수가 몇 개가 될지 모르기 때문에 노드의 개수가 많다고 가정을 합니다.

그리고 G라는 것은 하나의 노드의 시작과 끝 시간을 포함 한 프레임,

이 프레임의 타임슬롯 내에 전송을 시도하는 노드의 평균 수를 G라고 가정합니다.

그렇다면 포아송 분포에 따라서 계산 할 수가 있습니다.

푸아송 분포 : 단위 시간 안에 어떤 사건이 몇 번 발생할 것인지를 표현하는 이산 확률 분포

노란 프레임을 전송하려고 하는 t0 에서 t0 + 1 시간 안에

k개의 노드가 전송을 하려고 선택 할 확률을

포아송 분포로 나타내면 k! 분의 (G의 k승 e의 - G승)로 계산 할 수 있습니다.

그런데 t0를 기준으로 해서 t0 - 1 까지 아무도 전송을 시도하지 않아야 합니다.

그렇기 때문에 두 개의 연속적인 타임슬롯 사이에서

k개의 노드가 전송을 하는 경우의 확률을 포아송으로 계산하기 위해

G 대신에 2G가 들어가야 합니다.

전송이 성공하기 위해서는 두 타임슬롯 내에서 아무도 전송하지 않아야 되기 때문에

k를 0이라고 두게 되면 e의 -2G 승이라는 확률이 나오고, 전송을 성공 할 확률입니다.

그러면 이제 하나의 타임슬롯을 기준으로 봤을 때

프레임의 전송 성공 확률은 e의 -2G승인데 실제로 누군가 전송할 확률은 G라고 했으니

Ge의 -2G승가 슬롯 안에서 전송이 되는 확률입니다.

이 throughput의 최대값을 구하기 위해서 미분을 해줍니다.

여기서 미분 값이 0이 나오는 값은 G가 0.5일 때라는 것을 알 수 있고,

그 말은 평균적으로 타임슬롯에서 0.5대의 노드만이 전송을 해야됩니다.

Ge의 -2G승에 0.5를 대입하게 되면 0.184라는 이런 efficiency가 나오게 됩니다.

이것은 전체 채널 시간이 1이라고 보면 0.184 시간,

18.4%이 실제 데이터를 전달하는데 사용 되는 시간이고,

나머지 80% 이상은 충돌이 나거나 낭비되는 시간이 됩니다.

데이터의 개수가 많아지고, 전송하는 데이터 양도 많아지니

이런 efficiency로는 문제가 되게 되었습니다.