14-2:Network Layer:Link Layer

Multiple access protocols

엑세스를 할 때 어떻게 처리를 할지도 링크계층에서 제공하는 중요한서비스이다

이럴 때 multiple access protocol을 이용한다.

 

링크는 두가지종류로 나눌 수 있다.

- point to point

pc와 pc가 있으면 직접 랜선으로 연결이 되어 있을 경우를 이야기한다.

직접 연결된 그런 부분들은 point to point 링크 방식을 사용한다.

 

일반적인 경우에는

- broadcast 

브로드 캐스트 방법을 사용한다.

공유하고 있는 매체를 이용해서 공유해서사용할 때 브로드캐스트 링크를 사용한다.

이더넷과 와이어리스, 위성, 4g 5g모두 브로드캐스트 링크를 사용한다.

이번에 다룰 내용은 브로드캐스트에서 공유를 하고 있는데 어떻게 동시에 여러명이 사용하는 것을 통제를 할 수 있을지 본다.

 

multiple access protocol이라고 하는데

하나의 공유하고 있는 브로드캐스트 채녈이 존재하는데 동시에 여러 노드들이 프레임을 전송하려고 할때

어떻게 처리를 할까

동시에 보내려하면 간섭이 발생을 할 것이고, 동시에만 보내려고 하면 내가 보내려는 프레임과 다른 애가 보내려는 프레임이 섞일 것이다.

받는 쪽에서는 제대로 된 것인지 확인이 불가능하다.

그래서 의미가 없는 프레임이 섞여서 전송이 되면 충돌된다.

그래서 기본적으로 간단히 생각해봤을 때 이상적인 멀티플 엑세스 프로토콜이 있다고 하자.

사용할 채널이 존재하는데 해당 채널의 밴드위스가 R bps라고 하자.

전송률이 R bps라고 하면 

하나의 노드가 전송하려고 한다면 해당 채널에서 가용한 최대 전송률을 모두 사용할 수 있어야한다.

그리고 만약에 m개의 노드가 동시에 보내려고한다면 평균적으로 봤을 때 R/m bps로 전송을 할 수 있어야 할 것이다.

이것들이 가장 이상적으로 보내는 방법일 것이다.

완전하게 분산처리가 되어야 한다.

각각 다른 노드 상황을 알필요 없이 내가 가지고 있는 정보로만 접근 여부를 결정할 수 있는 것이 이상적이다.

중간에 컨트롤하는 게 생긴다면 전체가 동작을 안하는 문제가 생길 수 있다.

그리고 심플해야한다.

 

MAC protocol

Multiple Access protocol을 줄여서 MAC이라고 한다.

그러면 기본적으로 이 프로토콜이 나눠지는 보면

channel partitioning

기본적으로는 채널을 나눠쓰는 방법이 있다.

FDM, TDM 와 비슷한 방식으로

주어져있는채널을 나눠서 사용을 하는 방법.

어떻게 나누는지만 달라지는데,

time slot으로 나눌 것인지 frequency로 나눌 것인지 code로 나뉠 것인지, 3가지 방법으로 나뉜다.

코드는 time slot과 frequency의 중간이라고 생각하면되는데,

타임 슬롯은 시간을 나누는 것이고 프리퀀시는 반대로 프리퀀시를 나눈다.

코드방법은 코딩을 해서 보내는 순서를 여기저기 나눠서 보내는 것이다. 특정시간, 특정 프리퀀시에 보내는 방법이다.

가장 기본적인 개념은 결과적으로 잘쪼갠다음에 얘를 특정 노드한테 아예할당을해주는 방식이다. 할당된 것은 그 노드만 온전히 사용할 수 있다.

 

Random access

채널을 나누지는 않는다. 말그대로 랜덤하게 접근할 수 있도록 허용하는 것이다.

이렇게 되면 출동이 생길 수 있다. 출동이 일어나는 것을 그냥 허용한다.

동시에 여러개가 들어오면 섞여서 의미없는 내용이 될 수 있는데, 이것을 검출해서 충돌이 일어남을알고, 재전송하게 한다.

 

Taking turns

순서를 기다리는 것이다.

순서를 기다렸다 내 순서가 오면 보낼 게 있으면 보내고, 없으면 보내지 않는다.

그리고 바로바로 다음 애한테 턴을 넘기는 방식이다.

 

크게 세가지 방법이 존재한다.

 

Channel partitioning MAC protocol: TDMA

채널 파티셔닝 방법에는 타임 디비젼 멀티플 엑세스 방식이 있다.

TDM과 비슷한 개념이다.

채널을 접근을 할 때 타임 슬롯과 똑같지만, '라운드'라고 하여 라운드 별로 나눈다.

각각의 노드들은 정해진 슬롯 만큼만 각 라운드에 얻게 되는 것이다.

1번은 두개를 보내야 하는데, 위 그림과 같이 정해진 시간에만 나눠 보낼 수있다.

사용하지 않는 슬롯은 그시간에 비워둔다.

만약에 6개가 동시에 링크를 공유하는 상황이라고 하면, 1,3,4만 보낸 패킷이 존재하고 2,5,6은 보낼 게 없다고 하면 2,5,6에 할당된 시간에는 낭비가 된다.

 

Channel partitioning MAC protocol: FDMA

FDM과 비슷한 방식이다.

대역폭을 나눈다.

대역폭을 나눠 아까와 같은 상황에서 1,3,4는 나한테 할당된 대역폭을 사용해서 프레임 전송을 한다.

여기서도 똑같은 문제가 발생하는데, 기본적으로 할당받은 프리퀀시 대역폭은 고정적이다. 그래서 2,5,6 프리퀀시도 낭비되고 있다.

 

코드로도 나눌 수 있는 것은 CDMA 방식이라고 한다. 이것이 와이파이 같은 곳에서 실제 사용되는 채널 파티셔닝 맥 프로토콜이다. 

 

Random access protocol

랜덤 엑세스 프로토콜에서는 한 노드가 패킷을 보내려고 할 때 기본적으로는 나눠 사용하는 것이 아닌 전체채널을 다 사용한다. 전송률이 R라고 했을 때 R을 다사용한다.

노드들끼리 서로 주고 받아서 협의를 하는 과정 자체가 없다.

무조건 최대속도로 내가 원하는 패킷을 전송을 한다.

일단 보내는데 충돌이 생길 것이다.

이것을 충동을 검출을 하고 회복을 할 것인지 정의하고 있다.

회복하는 것은 재전송이고, 얼마나 기다렸다 다시 재전송할것인지가 중요한 포인트이다.

그래서 딜레이를 굳이 하는 이유를 알아야한다.

콜리젼이 발생했는데 내가 기다리지 않고 재전송을 바로 했다면 또 한번 콜리젼이 일어날 것이고, 무한히 발생하여 아무도 링크를 사용할 수 없는 상황이 발생할 수 있다.

하나는 바로 보내고 다른 하나는 조금 기다렸다가 다시 보내는 식으로 시간적으로 차이를 가지고 보내면 출동이 일어나지 않을 것이고 이것을 위해 딜레이가 필요하다.

 

랜던 엑세스 맥프로토콜에는 몇가지 예시들이 있다.

Slotted ALOHA

슬롯이라는 개념이 추가된 알로하이다.

여기서 하고 있는 가정은 모든 프레임이 같은 사이즈라는 가정이고,

시간을 나눠 사용하는데 시간을 나눌 때 똑같은 사이즈의 슬롯으로 나눠 사용한다.

여기서 슬롯은 하나의 프레임을전송하는데 걸리는 시간이다.

그리고 노드가 어떤 프레임을 보낼 때는 슬롯이 시작할 시점에만 페킷을 전송할 수 있다는 가정이 포함되어 있고,

슬롯단위로 동작하기 때문에 슬롯이 완벽히 끝내고 보내게 하려면 노드간의 시간 동기화가 필요하다.

동시에 여러개의 노드가 똑같은 슬롯에 대해서 전송하려하면 모든 노드가 충돌상황에 대해서 알수 있다는 가정이 있다.

 

프레임을 전송할 때 충돌이 발생하지 않으면 바로 새로운 프레임을 다음 슬롯에 보내게 되고 충돌이 발생하면 재전송을 다음 슬롯에 하는데 확률을 가지고 재전송을 한다.

그래서 매번 슬롯마다 게속 시도를 해서 확률적으로 어느순간에는 재전송을 하게 된다.

 

 

 

노드 1과 2, 3이 존재한다.

동시에 프레임을 전송을 하려고 하면 충돌이 발생할 것이다.

랜던 엑세스 방식은 무조건 채널 전체를 사용하기 때문에 출동이 발생한다.

다음 슬롯은 일단 비워진다.

그 다음에 이중 어떤 애는 확률적으로 재전송을 해서 1,2 가 재전송을 하게 되나 두개가 오기때문에 다시 출동이 오고,

이번에는 2만 전송되고 2만 성공했다.

그리고 아무도 안보내서 다시 비워지고 이런식으로 반복하다보면 

성공적으로 모든 패킷을 보낼 수 있을 것이다.

이렇게 위와 같이하나의 패킷씩보냈는데도 굉장히 많은 슬롯이 발생했다.

 

이 슬롯 알로하의 장점은,

딱 하나의 노드만 전송을 할 의지가 있다고 한다면 채널 전체를 사용해서 최고 속도로 전송을 할 수 있다는 장점이 있다.

굉장히 분산화가 되어 있어서 노드들 끼리 서로 정보교환할 필요없이 보내고, 랜덤하게 보낼지말지 계산해서 보내면 되기 때문에 다른 애들과 정보를 교환할 필요 없다.

슬롯단위로 보내는 시간을 맞춰야해서 시간은 동기화 해야한다는 부분이 중요하다.

그리고 단순하다.

 

단점은

우선 출동이 발생한다.

출동이 발생하면 슬롯이 낭비가 된다.

엠티 슬롯도, 아에 아무것도 보낼 게 없어서가 아니라 다 보내지 않는 쪽에 확률로 걸려서 우연히 idle 상태가 된 것이다.보내야할 데이터가 있음에도 이렇게 idle 상태가 될 수 있다는 단점이 있다.

clock 동기화가 필요하다.

 

이런 것들이 장단점이라고 생각하면 된다.

 

그리고 이 슬롯 알로하의 효율성을 보면

그림에서 봤듯이 몇개안되는 프레임 보내려했음에도 많은 슬롯을 낭비를 했었다.

그래서 효율성을 계산을 해보면 

n개의 노드가 프레임을 보내려고 했을 때 얼마나 정상적으로 그 중에 몇개의 프레임을 전송했는지 

계산을 해보면 

max efficiency = 1/e = 0.37 정도의 효율성이 나온다.

효율이 많이 떨어진다.

 

슬롯 알로하 방식 말고 퓨어 알로하 방식이 있다.

Pure ALOHA

슬롯 단위로 나눈 개념이 없는 알로하 프로토콜

슬롯단위가 아닌 프레임이 도착을 하면 바로 전송을 하는 개념이다.

그래서 슬롯 단위 가 없기 때문에 프레임이 어느 시점에든 시작할 수 있다. 프레임이 아래 그림과 같이 겹칠 수가있다.

이렇게 겹치는 부분에서 출동이 발생할 수 있다.

이같은경우에는 효율성이 18%로 더 떨어진다.

조금만 겹쳐도 충돌이 일어나기 때문에

실제로 효율성이 더 떨어질 수밖에 없다.

그러나 장점은 시간동기화를 할 필요가 없다. 노드들이 시간을 맞출 필요가 없기 때문에 완벽 분산처리 할 수 있지만 효율은 많이 떨어진다.

 

CSMA (Carrier Sense Multiple Access)

보내려는 매체를 한번 점검을하고 보내는 방식

보내려고 하는데 해당채널이 idle 상태라면 프레임을 바로전송을하고

보내기 전에 바쁜 상태라면 조금 있다가 프레임을 전송한다.

 

다른 사람이 뭔가 하고 있으면 방해하지 않는다.

여기서 좀더 나아간 방식이 CSMA/CD 방식이다.

 

CSMA/CD

CSMA with CollisionDetection

기본적인 CSMA같은 경우 출동 발생하더라도 내가 보내던 것은 다 보낸다.

전체 프레임을 다 보내고 그 다음에 충돌여부를 판단을 한다.

그러나 이것은 콜리전이 발생하자마자 보내던 것을 취소한다.

그렇게 되면 불필요하게 보내지 않아도 되는 부분을 보내지 않아 채널 낭비를 줄일 수 있다.

유선상에서는 상대적으로 무선상에서보다 쉽다.

 

CSMA: collision

콜리전은 실제로 우리가 매체를 확인을 하고 보냄에도 불구하고 발생을 할 수 있다.

앞에서부터 A,B,C,D라고 하면

일단 B가 처음에 보내려는패킷이 있다고 하자.

전체 채널을 다써서 보내려고 한다고하자.

t0시점에 보내기 시작했는데,

결과적으로 전체 체널을 사용하려면 물리적으로 전파되는 시간이 있다. 

이를 propagation delay라고 한다

이것을 다 사용하려면 시간적으로 t0시점에 밴드위스를 다 써서 보낼 수 있는 것이 아니라 전파시간이 필요하다.

전파되는 시간에 D가 아무도 안쓴다고 판단하고 t0시점에서 보낼 수 있다. 

이렇게 됐을 때 B,D가 동시에 전송을 하는 상황이 발생할 수 있다.

결국 의미가 없는 섞인 데이터가 만들어진다.

이경우에는 기본적인 CSMA 방식에서는 우선 다 전송을 한다.

그래서 이것을 다 끝까지 보낼 때 까지 하면 시간이 낭비가 된다.

 

이에 반해서 CSMA/CD는

출동을 발견하고 바로 보내는 것을 취소한다.

그래서 낭비되는 시간을 줄일 수 있다.

 

그래서 실제로 이더넷에서는 CSMA/CD 방법을 사용한다.

NIC 이 네트워크계층으로부터 데이터그램을 받고 프레임을 만들것이다.

NIC이 전송하기 전에 채널을 체크를 해서 idle인지 바쁜 상태인지 확인한다.

아이들 상황이면 바로 전송, 아니면 기다렸다 전송한다.

 

그래서 충돌없이프레임이 잘 전송될 수 있지만,

아니라면 보내던 것을 취소하고 시그널을 보내준다.

취소하면 다시 재전송을 해야하는데 얼마나 기다렸다 할 것인지도 중요한 요소중 하나인데

여기서 사용하는게 binary (exponential) backoff 이다.

이것은 트랜스미션에 대해서는 충돌이몇번일어났는지 체크한다. 

만약에 m번째 컬리전이 발생했다면 0,1,2,...,2^m-1 중에 렌덤으로 하나 선택한다. 이중에서 만약 3이 선택된다면 3*512 bit times 까지 기다렸다가 다시 보내기 전 상태로 돌아간다.

 

512비트를 보내는데 걸리는 시간을 512 bit times 라고 한다.

충돌이 많이 발생할 수록 백오프가 얼마나 오래 물러날지가 정해질 것이고 점점더 많이 기다릴 것이다.

자동적으로 충돌 일어나느 것을 랜덤화 한다.

 

CSMA/CD의 효율성은 1로 갈수록 좋은 것

= 트랜스미션딜레이가 무한대로 갈수록 충돌이 일어나지 않고 좋은 것이다

= 프로퍼게이션 딜레이가 0으로 갈수록 좋은것

알로하보다 싸고 심플하다

 

 

Tacking turns

채널 파티셔닝

로드가 심할 때 효율적

시간으로 나누던 프리퀀시, 코드로 나누던 로드가 많은 상황에서는 효율적

하지만 로드가 낮을 경우 낭비가 심하다

랜덤 엑세스 방식에서는 로우 노드일 경우 효울적, 로드가 많아지면 출동 많아지며 오버헤드 단점 

 

위 둘의 장점 모두 같기 위한 프로토콜

그렇다고 해서 이것이 위 둘보다 좋은 것은 아니다.

이론적 성능을 좋을 수 있지만 다른 문제때문에 사용제한이 된다.

 

이같은 경우 몇가지 방법이 있다.

첫번재가 폴링방식

마스터 노드가 하나가 존재하고 슬레이브 노드들이 존재한다.

마스터가 전체적으로 트랜스미션할 수 있는 애들을 정해준다.

근데 여기서 생길 수 있는 문제는 마스터가 슬레이브가 보낼 내용이 있는지 폴링을 통해서 확인을 해야하는 작업 필요

폴링이라는 것은 무한 루프라고 생각하면된다.

 

보낼 게 있다고 바로 보낼 수 있는 것이 아나라 마스터가 결정->레이턴시 증가

 

마스터가 고장나면 아무도트랜스미션을 할 수 없다는 싱글포인트페일류어 문제가 있다.

 

token passing

토큰을 전달해주는 방식

토큰 가진 애만 프레임을 전송할 수 있다.

토큰은 정해진 순서로 순환한다.

토큰 주고받아야 하니 토큰 오버헤드 증가.

토큰 나한테 올때까지 기다려야하니 레이턴시 증가

똑같이 싱글포인트 페일류어 발생 가능성 있음

토큰 가지고 있는 애가 죽으면 받을 수가 없기 때문에 문제 발생

이러한 문제들때문에 한계존재