다중 접속 링크와 프로토콜

네트워크 링크의 두 종류

 

1. 점대점 링크 (point-to-point link)

: 링크의 한쪽 끝에 한 송신자와 링크의 다른 쪽 끝에 한 수신자가 있다.

ex) PPP(point-to-point protocol), HDLC(high-level data link control)

 

 

2. 브로드캐스트 링크 (broadcast link)

: 동일한 하나의 공유된 브로드캐스트 채널에 다수의 송신 노드 및 수신 노드가 연결된다,

임의의 한 노드가 프레임을 전송하면 채널이 그 프레임을 브로드캐스트해서 다른 모든 노드가 그 프레임의 복사본을 수신하기 때문에 브로드캐스트 용어가 쓰인다.

ex) 이더넷, 무선 랜

 

다중 접속 문제(multiple access problem)

: 모든 노드가 프레임을 전송할 수 있으므로 2개 이상의 노드가 브로드캐스트 채널에서 직접 통신할 수 있고, 이런 일이 발생하면 모든 노드는 동시에 여러 개의 프레임을 받게 된다.

즉, 전송된 프레임들이 각 수신자에서 충돌(collide)하게 되고 어떤 수신 노드도 전송된 프레임의 의미를 파악할 수 없게 된다.

따라서 충돌에 관련된 모든 프레임은 손실되며, 다수의 노드가 빈번히 프레임을 전송하려 한다면 많이 충돌할 것이고 따라서 브로드캐스트 채널의 대역폭이 많이 낭비된다.

ex) 

말하는 사람이 여러명이어서 듣는 사람은 무슨 말을 하는지 잘 이해를 못한다.

그래서 다중 접속 프로토콜이 이러한 문제의 해결책으로 나왔다.

 

다중 접속 프로토콜(multiple access protocol)

분류 : 채널 분할 프로토콜, 랜덤 접속 프로토콜, 순번 프로토콜

 

초당 R 비트의 전송률을 갖는 브로드캐스트 채널에 대한 다중 접속 프로토콜의 이상적인 특성

1) 단 하나의 노드가 전송할 데이터가 있을 때는 그 노드가 R bps의 처리율을 갖는다.

2) M개의 노드가 전송할 데이터가 있을 때는 각 노드가 R/M bps의 처리율을 갖는다.

항상이 아니며 각 노드가 정의된 시간 동안 R/M의 평균 처리율을 가짐을 의미한다.

3) 분산되어 있어 고장으로 인해 전체 시스템을 정지시킬 수 있는 마스터 노드가 없다.

4) 단순해서 구현하는 데 비용이 적게 든다.

 

 

6.3.1 채널 분할 프로토콜(channel partitioning protocol)

 

채널을 공유하는 모든 노드가 브로드캐스트 채널의 대역폭을 분할할 수 있게 해주는 기술

 

1) 시분할 다중화(time-division multiplexing, TDM)

채널이 N개 노드를 지원하고 채널 전송률이 R bps라고 하자.

TDM은 시간을 시간 프레임(time frame)으로 나누고 또한 각 시간 프레임을 N개의 시간 슬롯(time slot)으로 나눈다.

그 후 N개의 노드에게 시간 슬롯을 각각 할당한다.

노드는 전송할 패킷이 있을 때마다 TDM 프레임에서 자신에게 할당된 시간 슬롯 동안 패킷을 전송한다.

 

장점

충돌을 제거할 수 있다.

매우 공정하다.

 

단점

전송할 패킷이 있는 노드가 단 하나인 경우에도 노드 전송률이 R/N으로 제한된다.

노드가 전송 순서상 자신의 차례를 항상 기다려야 한다.

낭비가 발생해서 효율이 좋지 않다. 아래 그림에서 2,5,6번은 사용되지 않고 있다.

 

 

2) 주파수 분할 다중화 (frequency-division multiplexing, FDM)

R bps의 채널을 R/N의 대역폭을 갖는 다른 주파수로 나눠서 각 주파수를 N개의 노드 중 하나에게 할당한다.

즉, 하나의 큰 R bps 채널로부터 N개의 R/N bps의 작은 채널을 만든다.

TDM과 같은 장단점을 갖는다.

 

 

 

3) 코드 분할 다중 접속(code division multiple access, CDMA)

CDMA는 다른 코드를 각 노드에게 할당한다.

노드는 전송하는 데이터 비트들을 자신의 유일한 코드로 인코딩한다.

 

장점

CDMA 네트워크에서 코드들을 신중하게 선택하면 여러 노드들이 동시에 전송할 수 있다.

다른 노드들에 의해 전송이 간섭되더라도 각 수신자들이 송신자의 인코딩된 데이터 비트를 정확하게 수신할 수 있다.

 

 

6.3.2 랜덤 접속 프로토콜(random access protocol)

랜덤 접속 프로토콜에서 전송 노드는 항상 채널의 최대 전송률인 R bps로 전송한다. (채널 분할 프로토콜과는 다르게 R을 전부 사용한다)

충돌이 생기면 충돌과 관련된 각 노드는 프레임이 충돌 없이 전송될 때까지 자신의 프레임을 계속해서 재전송한다.

 

프레임이 충돌했을 때 즉시 재전송하지 않고, 랜덤 지연 시간 동안 기다린 후 재전송 한다.

즉, 출동했던 노드 중 하나는 다른 노드가 선택한 지연 시간보다 충분히 작은 지연시간을 선택함으로써 충돌 없이 자신의 프레임을 채널로 전송할 수 있다.

 

ex) 알로하, 슬롯 알로하, CSMA, CSMA/CD, CSMA/CA

 

1) 알로하(Pure ALOHA)

 

작동 과정

a) 프레임이 도착하면 노드는 즉시 프레임 전체를 브로드캐스트 채널로 전송한다.

b) 만약 충돌하면, 노드는 확률 p로 즉시 재전송 한다.

c) 즉시 재전송하지 않는 경우, 노드는 프레임 전송 시간 동안 기다린다.

d) 기다리고 나서 확률 p로 전송하거나 아니면 1-p 확률로 또 다른 프레임 시간 동안 기다린다.

 

 

2) 슬롯 알로하(Slotted ALOHA)

 

가정

a) 모든 프레임은 동일한 크기 L비트로 구성된다.

b) 시간은 L/R초의 슬롯들로 나뉜다. (즉, 한 슬롯은 한 프레임 전송에 걸리는 시간과 같다)

c) 노드는 슬롯의 시작점에서만 프레임을 전송하기 시작한다. (<-> 퓨어 알로하에서는 아무때나 시작)

d) 각 노드는 언제 슬롯이 시작하는지 알 수 있게끔 동기화되어 있다.

e) 한 슬롯에서 2개 이상의 프레임이 충돌하면, 모든 노드는 그 슬롯이 끝나기 전에 충돌 발생을 알게 된다.(detect collision)

 

작동 과정

a) 전송할 새 프레임이 있으면 다음 슬롯이 시작할 때까지 기다렸다가 그 슬롯에 전체 프레임을 전송한다.

b) 만약, 충돌하지 않으면 노드는 성공적으로 자신의 프레임을 전송한 것이다. 따라서 그 프레임을 재전송할 필요가 없다.

c) 만약 충돌하면, 노드는 그 슬롯이 끝나기 전에 충돌을 검출한다. 노드는 그 프레임이 충돌 없이 전송될 때까지 확률 p(0~1 사이)로 해당 프레임을 다음 슬롯들에서 재전송한다.

 

ex)

1번째 time slot : 1번,2번,3번 다같이 보냄 -> 충돌 => 실패

2번째 : Empty

3번째 : 1번,2번 충돌 => 실패

4번째 : 2번 => 성공

5번째 : Empty

6번째 : 1번,3번 충돌 => 실패

7번째 : Empty

8번째 : 1번 => 성공

9번째 : 3번 => 성공

 

장점

a) 하나의 활성노드로 하여금 채널의 전속력 R로 계속해서 프레임을 전송할 수 있도록 허용한다.

: 만약 1번째에서 2번,3번이 없었으면 1번이 계속 R로 전송할 수 있었다.

b) 노드가 충돌을 감지하고 언제 재전송할지 각자 결정하므로 분산되어있다.(<->중앙화)

c) 매우 단순하다.

 

단점

a) 노드는 슬롯이 언제 시작하는지 동기화되어있어야 한다.

b) 활성 노드가 많이 있으면 일부 슬롯이 충돌로 인해 결과적으로 낭비 된다.

: 위 그림 1번째에서 1번,2번,3번 충돌하여 낭비됨

c) 모든 활성 노드가 확률적인 전송 정책 때문에 전송을 억제하는 경우 일부 슬롯이 비게 된다.

 

효율성

노드가 N개가 있을 때 하나의 슬롯이 성공적인 슬롯일 확률은 노드들 중 한 노드만 전송하고 나머지 N-1 개의 노드는 전송하지 않는 확률이다. 노드가 전송할 확률 = p

해당 노드가 성공할 확률 = p x (1-p)^(N-1) 이다.

노드가 N개 있으므로 임의의 한 노드가 성공할 확률 = N x p x (1-p)^(N-1) 이다.

 

최대의 효율을 구하기 위해서는 이 식 N x p x (1-p)^(N-1) 을 최대화 하는 p를 구해야 한다.

활성 노드가 많은 경우의 최대 효율을 구하기 위해 N이 무한대가 될 때의 극한값을 취한다.

이렇게 계산하면 최대 효율은 p = 1/e = 0.37 임을 알 수있다.

 

즉, 많은 노드가 전송할 프레임이 많을 때 기껏해야 37%의 슬롯만 낭비되지 않는다.

 

 

3) CSMA(carrier sense multiple access)

위 두 프로토콜에서는 다른 노드가 전송하고 있건 말건 일단 보낸다.

즉, 충돌이 생기고 결과적으로 효율이 떨어진다.

 

이러한 충돌을 없애기 위한 CSMA의 규칙은 다음과 같다.

 

캐리어 감지(carrier sensing), 말하기 전에 듣는다.

: 만일 다른 노드가 프레임을 채널로 전송하고 있는 경우, 노드는 임의의 짧은 시간 동안 전송 중단을 감지하면 프레임을 전송하기 시작한다.

충돌 검출(collision detection)

: 만일 다른 노드가 방해 프레임을 전송하고 있음을 검출하면, 자신의 전송을 중단하고 랜덤 시간 동안 기다린 후 유휴 시 감지 및 전송과정을 반복한다. 유선에서 사용.

충돌 회피(collision avoidance)

: 충돌 검출은 유선에서는 쉽지만 무선에서는 어렵기 때문에 무선에서는 충돌을 회피하는 CA방식을 사용한다.

 

 

CSMA에서 충돌이 발생하는 경우

작동 과정

t0에서 B는 아무도 전송하고 있지 않으므로 채널이 비어 있는 것을 감지하고 전송 시작

-> B가 전송한 비트들이 양방향으로 전파됨

-> 한편 시각 t1에 노드 D가 전송할 프레임이 생겼다.

-> 노드 B가 t1에 전송하고 있음에도 불구하고, 아직 D에 도달하지 못했기 때문에 D는 채널이 사용되지 않는 것으로 감지한다.

-> D는 자신의 프레임을 전송하기 시작한다.

-> B의 전송과 D의 전송이 간섭을 일으키기 시작한다.

 

즉, 브로드캐스트 채널 종단 간의 채널 전파 지연(channel propagation delay)이 길수록 다른 노드에서 이미 시작된 전송을 캐리어 감지 노드가 감지할 수 없는 경우가 증가한다.

따라서 채널 종단 간의 채널 전파 지연(channel propagation delay) 는 CSMA의 성능을 결정하는데 중요한 역할을 한다.

 

 

4) CSMA/CD(CSMA with collision detection)

 

CSMA는 충돌 검출을 수행하지 않는 반면, CSMA/CD는 충돌 검출을 수행한 후 즉시 전송을 취소(abort)한다.

 

작동 과정

어댑터는 네트워크 계층으로부터 데이터그램을 받아서 링크 계층 프레임을 만든 후에 그 프레임을 어댑터 버퍼에 저장한다.

-> 어댑터는 채널이 유휴(idle, 채널로부터 어댑터로 들어오는 신호 에너지가 없음) 상태임을 감지하면 프레임 전송을 시작한다.

만일 어댑터가 채널이 바쁜(busy) 상태임을 감지하면, 어떤 신호 에너지도 감지되지 않을 때까지 더 기다렸다가 프레임을 전송하기 시작한다.

-> 전송하는 동안 어댑터는 브로드캐스트 채널을 사용하는 다른 어댑터로부터의 신호 에너지가 있는지 감시한다.

-> 프레임 전체를 전송하는 동안 다른 어댑터로부터의 신호 에너지가 감지되지 않으면, 프레임 전송을 완료한다. 그러나 감지되면 자신의 프레임 전송을 취소한다.

-> 전송 취소 후 임의의 랜덤 시간(backoff)만큼 기다린 후 2단계로 돌아간다.

만일 랜덤 시간이 아니라 고정 시간이라면 동시에 프레임을 전송했을 때 똑같은 시간을 기다린 후 전송을 하므로 계속해서 충돌하게 되기 때문.

 

랜덤 시간을 결정하는 알고리즘: 이진 지수적 백오프(binary exponential backoff)

충돌을 n번 경험한 프레임을 전송할 때 노드는 {0,1,2,…,2^n - 1} 중에서 랜덤하게 K 값을 선택한 후 K x 비트 시간 만큼 기다린다.

이더넷의 경우 K x 512 비트 시간(이더넷으로 512 비트를 전송하는데 걸리는 시간 x K)이 되며 n의 최댓값을 10으로 제한한다.

 

즉, 충돌을 많이 경험할수록 K의 범위가 지수적으로 커지게 된다.

새 프레임을 준비할 때는 최근 발생한 충돌을 고려하지 않고 CSMA/CD를 수행하여 충돌을 경험한 노드보다 먼저 전송될 수도 있다.

 

효율성

t(prop) = 신호 에너지가 임의의 두 어댑터 사이에서 전파되는 데 걸리는 최대 시간
t(trans) = 최대 크기의 이더넷 프레임을 전송하는데 걸리는 시간

 

t(prop)이 0이되면 효율은 1에 근접한다. 전파지연이 0이 되면 충돌한 노드는 채널을 장비하지 않고 즉시 취소하기 때문에. 

t(trans)가 아주 크면 효율은 1에 근접한다. 프레임이 채널을 한번 차지하면 아주 오랫동안 채널을 사용하기 때문에.

*효율 1 = 효율 100%

따라서 채널은 거의 모든 시간 동안 유용하게 쓰인다.

 

 

6.3.3 순번 프로토콜(taking-turns protocol)

 

채널 분할 프로토콜 : load가 클 때 유리

랜덤 접속 프로토콜 : load가 작을 때 유리

순번 프로토콜 : 모든 경우에 좋다.

 

1) 폴링 프로토콜(polling protocol)

 

노드 중 하나를 마스터 노드로 지정한다.

마스터 노드는 각 노드를 라운드 로빈 방식으로 폴링한다.

 

특히, 마스터 노드는 먼저 노드 1에게 노드 1이 최대로 보낼 수 있는 프레임 수에 대한 메시지를 전송하고, 노드 1이 프레임을 전부 보낸 다음 다음 노드도 똑같이 수행하여 순환적으로 각 노드를 폴링하는 방식으로 이 과정을 계속한다.

 

장점

빈슬롯을 제거할 수 있다.

 

단점

a) 폴링 지연이 있다.

: 한 노드만 활성이면 활성 노드가 프레임을 최대 개수만큼 보낼 때마다 마스터 노드는 비활성 노드들을 차례로 폴링해야만한다.

b) 마스터 노드가 고장나면 전체 채널이 동작하지 못한다.

 

 

2) 토큰 전달 프로토콜(token-passing protocol)

 

토큰(token) 이라고 알려진 작은 특수 목적 프레임이 정해진 순서대로 노드 간에 전달된다.

예를 들어, 노드 1은 항상 노드 2에 노드 2는 노드 3에 노드 N은 노드 1에 토큰을 전송한다.

 

노드가 토큰을 수신하면, 전송할 프레임이 있을 때만 토큰을 붙잡고, 그렇지 않으면 토큰을 전달한다.

프레임을 최대 개수까지 전송한 뒤 토큰을 다음 노드로 전달한다.

 

장점

: 분산 방식으로 효율이 매우 높다.

 

단점

a) 노드 하나가 실패하면 채널이 동작하지 않는다.

b) 노드가 토큰을 놓아주지 않으면, 토큰이 다시 돌 수 있도록 하는 회복 절차가 수행되어야 한다.

 

 

6.3.4 DOCSIS: 케이블 인터넷 접속을 위한 링크 계층 프로토콜

 

DOCSIS(Data-over-Cable Service Interface Specificaitions)는 케이블 데이터 네트워크의 구조와 프로토콜들을 정의한다.

DOCSIS는 하향 및 상향 네트워크 세그먼트들을 다수의 주파수 채널로 나누기 위해 FDM을 사용한다.

상향 및 하향 채널은 브로드캐스트 채널이다.