[18] CH5 Link 계층 < 다중 접속 protocol >

< 다중 접속(Multiple Access) Link 및 Protocol > 

2가지 종류의 link 

 - 점 대 점 link : 전화선 PPP protocol 

 - broadcast link(공유 선로 혹은 공유 매체) : Ethernet etc

 

< 다중 접속 protocol >

 - 단일의 공유 broadcast channel

 - 두 개 이상의 node에서 동시에 전송 -> 간섭

    - 동시에 두 개 이상의 신호를 동시에 수신하면 충돌(collision) 발생.

 

 - 분산(distributed) algorithm : node들이 어떻게 channel을 공유할 것인가(즉, 언제 node가 전송할 것인가)를 결정 

 - channel 공유 방법에 관한 통신도 역시 그 channel상에서 이루어 져야함. 조정을 위한 out of band channel이 존재X

 

충돌이 일어나면 어떤 수신 노드도 전송된 프레임의 의미를 파악할 수 없다. 

 

< 이상적인 다중접속 protocol > 

속도 Rbps의 broadcast channel 

1. 한 개의 node만 전송할 때, 그 node는 속도 R로 전송 가능 

2. M개의 node가 전송하고자 한다면, 각 node는 평균속도 R/M으로 전송 가능 

3. 분산구조 : 전송을 제어하는 특별한  node가 따로 존재하지 않음

4. 단순함.

 

< MAC Protocol 종류 >

 - Channel 분할 protocol : 채널을 여러조각(time slot,frequency,code)으로 분할 , 각 조각을 node에 할당하여 그 node가 독점적으로 사용할 수 있도록 함 

 

 - Random 접속 protocol : 채널은 분할되지 않음. 충돌이 발생할 수 있다. 충돌로부터 복원 기능 있다. 

 

 - 순번(taking turns) protocol : Node들은 자기 순번을 가진다. 하지만 전송할 data가 많은 node가 더많은 시간을 소비할 수도 있다. 

 

< Channel 분할 MAC protocol : TDMA > TDMA : time division multiple access 

TDMA는 충돌을 제거할 수 있고 아주 공정하므로 바람직하다. 그러나 이방식에는 두가지 단점이 있는데 전송할 패킷이 있는 노드가 단 하나인 경우에도 노드 전송률이 평균 R/N으로 제한된다. 노드가 전송 순서상 자신의 차례를 항상 기다려야 한다. 

 

 - Channel은 반복되는 frame으로 구성된다. 각 frame은 여러 time-slot들로 분할된다. 

 - 각 station은 매 frame 내에서 고정적으로 특정 time-slot(길이 = packet전송시간)을 가진다. 

 - 시간 프레임으로 나누고 또한 각 시간 프레임을 N개의 시간 슬롯으로 나누다. 

 - 할당 받았으나 사용되지 않은 slot은 낭비된다. 

 

< Channel 분할 MAC protocol : FDMA >  FDMA : frequency division multiple access 

TDMA는 브로캐스트 채널을 시간으로 공유하지만, FDMA는 Rbps의 채널을 다른 주파수(각 R/N의 대역폭을 갖는)로 나눠서 각 주파수를 N개 노드 중 하나에게 할당한다. TDMA와 같이 충돌을 피하고 N개의 노드에게 대역폭을 균등하게 분할하지만 전송할 패킷을 가진 노드가 단 하나일지라도 노드는 R/N의 대역폭으로 제한된다. 

 

 - Channel spectrum을 여러개의 frequency band로 분할 

 - 각 station에게 특정 frequency band를 고정적으로 할당 

 - Frequency band는 사용되지 않는 시간 동안에 낭비됨 

 

< Channel 분할 MAC protocol :CDMA > CDMA : code division multiple access 

TDMA,FDMA는 각각 시간 슬롯과 주파수를 노드에게 할당하지만, CDMA는 다른 코드를 각 노드에게 할당한다. 그러면 노드는 전송하는 데이터 비트들을 자신의 유일한 코드로 인코딩한다. 

 

 - 각 station에게 특정 code를 할당함 

    - 모든 station들이 동일한 주파수를 공유하지만, 각 station들은 데이터 부호화에 사용할 자신이 소유한 칩 수열(code)를 갖고 있다. 

    - 다중 station들이 최소한의 간섭을 가지고 동시에 전송할 수 있게 한다.(code들이 직교성을 만족할 때)

 - 부호화된 신호 = 원본 데이터 X칩 수열

 - 복호화 : 부호화된 신호와 침 수열의 곱 

 

 

< Random 접속 Protocol >

 - Node가 전송할 packet을 가지고 있으면,

    - 최고 channel data 속도 R로 전송 

    - Node들 사이에 사전 조절은 없다.

 - 2개 이상의 node가 동시에 전송하면 >> 충돌(collision)발생 

 - Random access MAC protocol은 다음을 결정합니다.

    - 충돌(collision)을 어떻게 감지할 것인가?

    - 충돌 발생시 이에 어떻게 대처할 것인가?(예: 기다린 후에 재전송)

Random access MAC protocol의 예 : ALOHA etc 

 

< Slotted ALOHA >

 가정 

- 모든 frame은 동일한 크기를 가짐.

- 시간이 동일한 크기의 slot들로 분할됨( 한 개의 slot은 한 개의 frame을 전송 )

- Node들은 항상 slot의 시작위치에서만 전송을 시작 

- Node들은 동기화됨

- 2개 이상의 node가 동일한 slot에 전송하면 두 node는 모두 충돌을 감지한다. 

 

동작 

- Node가 새로운 frame을 갖게 되면, 다음 slot에 전송 

    - 충돌이 없으면 node는 다음 slot에 새로운 frame을 전송할 수 있다. 

    - 충돌이 발생하면 node는 성공할때까지 뒤이어 오는 다음 slot에서 확률p로 재전송한다. 

장점

 - 한 활성node가 계속해서 channel의 최고 속도로 전송할 수있다

 - 잘 분산화된다(단지 모든 node가 slot timing에 동기화 될 필요가 있다.

 

단점 

 - 충돌 발생, slot소비함 

 - 비어있는 slot발생 가능( 보낼 packet을 지닌 node가 있는데도 불구하고 )

 - Clock동기 필요 

 

< Slotted Aloha의 효율성 계산 >

효율성 : 장시간에 걸쳐 관찰했을때, 성공적으로 packet을 전송한 slot의 비율 

 [ 위의 사진의 경우 충돌나지 않은 slot은 3개 (총 9개) 효율성 : 33% ] 

 

node수가 많을 수록 많은 충돌, p값에 따라 효율이 달라짐 

기껏해야 유효 전송은 37% 정도 37%의 slot만이 성공적인 전송이 이루어진다. 

< Un-slotted ALOHA > 

 - un slotted Aloha : 더 간단함, 동기화 필요 없음 

 - 전송할 첫 frame이 도착하면, 즉시 전송함 

 - 충돌 확률이 증가함 

    -시각 t0 에 전송된 frame은 시간 구간 [t0-1,t0+1] 사이에 전송된 다른 frame과 충돌함

 

Slotted Aloha보다 성능이 좋지 못 함. (1/2e 약18%)

 

< CSMA(Carrier Sense Multiple Access >

CSMA : 전송하기 전에 듣는다. 

 - Channel이 비어있는 것으로 감지되면, frame 전체를 전송한다. 

 - Channel이 사용중인 것으로 감지되면, 전송을 미룬다. 

 - 비유 : 남이 이야기 중일 때 방해하지 마라!

 

< CSMA충돌 >

위 그림은 4개의 노드 A,B,C,D에 대한 공간 시간 도표가 나타나 있다. 수평축은 공간에서 각 노드의 위치를 나타내고, 수직축은 시간을 나타낸다. 시간 t0에 노드 B는 다른 노드가 아무도 전송하지 않으므로 채널이 비어 있는 것으로 감지한다. 따라서 B는 전송을 시작하며, B가 전송한 비트들이 브로드캐스트 매체를 따라 양방향으로 전파된다. 시간 t1일때 노드D가 전송할 frame이 생겼다. 노드 B가 시간 t1에 전송하고 있음에 불구하고 B에 의해 감지되는 비트들은 아직 D에 도달하지 못했고, 따라서 D는 t1일 때 채널이 사용되지 않는 것으로 감지한다. 따라서 CSMA 프로토콜에 따라 D는 자신의 프레임을 전송하기 시작한다. 약간의 시간이 경과 후, D에서 B가 전송한 것과 D의 전송이 간섭을 일으키기 시작한다. 

 

그럼에도 불구하고 충돌은 발생할 수 있다. : 전달 지연으로 인해 두개의 node가 상대의 전송을 감지하지 못할 수도 있다. 충돌 : 전체 packet전송시간이 낭비되는 결과를 초래함.

 

< CSMA/CD(Collision Detection) >

 - CSMA/CD : 신속한 충돌 감지, 충돌하고 있는 전송을 취소하여 channel에 대한 낭비를 줄인다. 

 - Collsion detection 방법 

     - 유선 LAN에서는 용이함 : 신호 세기를 측정, 전송 신호와 수신 신호를 비교 

     - 무선 LAN에서는 어려움 : 무선 신호세기는 거리에 크게 좌우되기 때문.

 

< CSMA/CD 효율 >

최대 전파 지연이 작다? > 가까이 있다 > 최대 효율 

< 순번 MAC prtocol > 

 - Channel 분할 protocol 

    - 장점 : 부하가 클 때, channel을 효과적이며 공평하게 공유함 

    - 단점 : 부하가 작을 때는 비효율적 : 혼자만 통신할 때도 전체 대역의 1/N만 할당 받음 

 

 - Random 접속 protocol 

    - 부하가 작을 때, 효과적임 : 한 개의 node가 channel 전체 대역을 사용할 수 있음 

    - 부하가 클 때 : 충돌이 심함 

 

 - 순번 protocol

    - 위의 장단점들을 고려해 개발된 protocol이다. 

 

Polling protocol

 - Master node가 slave node들이 순서대로 전송하도록 지시 

장점 : 충돌 없음 , slot이 낭비되지 않음 

단점 : Polling 제어 부하, 지연 , master node가 고장 나면 전체 channel 사용 불능 

Token passing 

 - 제어 token이 한 node에서 다른 node로 순차적으로 전달 됨 

 - 단점 : Token 제어 부하 , 지연 , 한 node가 고장 나면 전체 channel 사용 불능

 

< MAC protocol 정리 >

 - 채널 분할 : 시간,주파수,혹은 code영역에서 분할 

   - Time Division, Frequency Division, Code Division

 

 - Random 접속 

   - ALOHA

   - Carrier sensing : 유선에서는 쉽지만 무선에서 어려움 

   - CSMA/CD

 

 - 순번 protocol

   - 중앙으로부터 polling,token passing

   - Bluetooth