12.1 Random Access

random-access 또는 contention 방법들에서는, station이 다른 station보다 우월하거나 통제권을 갖지는 않는다. 각 station마다 전송해야할 데이터가 있고, 이는 사전에 정의된 protocol에 의해서 송신할지 말지를 결정한다. 이 결정은 medium의 상태에 의해 결정된다. (idle/busy) 즉, 각 station은 medium의 상태를 테스팅하는 것을 포함하여, 사전정의된 절차에 따라 송신할 수 있다.

위 방법의 2가지 대표적인 특징이 있다. 첫번째로는, station마다 송신할 시간이 정해져 있지 않다는 점이다. 송신은 station마다 random하게 일어난다. 그래서 random access라 부른다. 두번째로는, 어떤 station이 다음에 송신해야하는 규칙이 정해져 있지 않다 station은 medium을 차지하기 위한 경쟁을 하게 되고, 이로 인해 contention이라 부른다.

random access method서는, station은 다른 station을 통제할 수 없으며, 모두 다 medium에 접속할 수 있다. 만약 1개 이상의 station이 송신을 시작하면, collision이 발생하여, 프레임들이 깨지거나 변질될 것이다. 충돌을 회피하기 위해서는 다음과 같은 질문에 답할 수 있어야 한다.

• 언제 station이 medium에 접속할 수 있는지?
• station은 medium이 바쁘면 어떤 일을 할 수 있는지?
• station은 어떻게 전송의 실패/성공을 확인하는지?
• station은 충돌시, 어떻게 하는지?

아래 내용서는 가장 간단한 random-access protocol인, multiple-access(MA)를 사용한 ALOHA에 대해서 알아본다. 이 방법의 핵심은 전송하기 전에 sensing하는 것이다(CSMA). 이 방법이 발전하여 CSMA/CD, station에게 충돌이 감지되면 어떤 일을 해야할지 알려주는 방법과 CSMA/CA, 충동을 회피하기 위해 노력하는 방법으로 발전하게 된다.

12.1.1 ALOHA

1970년대, 하와이대학서 wireless LAN을 위하여 개발될 것이며, shared medium을 사용하였다. medium을 stations이 공유하였으므로, 충돌이 발생할 것은 자명하였다.

pure ALOHA

original ALOHA protocol은 pure ALOHA라고 불린다. 이 방법은 전송할 데이터가 생기면, 바로 쏘는 방식이다. 하지만 1개의 채널을 공유하므로, 충돌이 발생하여 프레임들이 변질될 가능성이 생긴다.

위의 그림에선 충돌이 발생하여 오직 2개 프레임만이 전송에 성공. 프레임이 겹치면, 충돌이 발생하여 파괴된다. 따라서 충돌된 프레임을 다시 재전송 해줄 필요가 생긴다. 재전송시, random한 일정 시간(backoff time)동안 기다려서, 재전송을 하여 충돌을 회피하고자 한다

또한 재전송을 계속 반복하여 채널을 혼잡하게 하는 것을 방지하기 위해여, K(max) 이후에는 재전송을 하지 못하고 중단해버린다.

위의 그림은 ALOHA의 취약 시간을 나타낸 것이다. T(fr)주기로 한 같은 길이의 프레임이 전송된다고 했을때, Vulnerable time = 2 x T(fr)이다

Slotted ALOHA

pure ALOHA는 station이 언제 전송해야 하는지 규칙이 없다. 이를 개선한 것이 slotted ALOHA이다. 시간을 여러개의 T(fr)길이만큼의 slot들로 나누어서, slot의 시작점에서만 송신을 할 수있도록 하는 방법이다

Time slot의 시작점에서만 전송이 가능하므로, 다음 시간 slot을 기다려야 한다. 만약 놓치면, 다음 슬롯을 기다려야 한다. 물론, 이 방법에서도, 같은 time slot에서 동시에 전송이 일어나 충돌이 발생하는 경우도 있다. 하지만, vunlerabel time은 2T(fr)에서 T(fr)로 줄어든다.

12.1.2 CSMA

충돌을 줄이고자, CSMA 방법이 개발되었다. 송신 전에 감지를 하여, 충돌의 기회를 줄이고자 하였다. CSMA는 각 station에게 송신전에 먼저 medium을 listen하라고 한다. 즉, "sense before transmit".

CSMA 방식은 충돌을 줄일 수는 있어도, 없앨수는 없다! 이는, 바로 propagation delay때문이다. 즉, station은, propagtion delay로 인해 다른 station서 보낸 bit를 감지 못한체 이상적인 상태라 판단하여 쏘는 경우가 발생할 수 있다. 위의 그림도, t2에서 B가 보낸 bit가 C에 도달하지 않은 상태므로, C는 송신을 시작하게되고, 프레임들이 겹치게 되어 파괴된다.

CSMA의 vunerlable time은 propagation time과 같다. 즉, 신호가 다른 stations들 모두에게 도착할때까지 걸리는 시간이 필요하다. propagation time만큼 기다리게 되면, 충돌 가능서이 더욱 낮아질 것이다.

persistence methods

"channel이 busy하거나 idle하면 station은 어떤 일을 해야할 것인가?"에 대한 answer.

• 1-persistent: 이 방식은 간단하며 직관적이다. idle 상태로 sensing되면, 바로 쏘는 것이다. 충돌의 가능성이 가장 높은데, 여러 stations이 idle하다고 sensing하면 동시에 쏠 수 있기 때문이다. 추후에 ethernet에서 이 방법을 사용한다.

• Non-persistent: 이 방식은 sensing을 하여, 이상적이라 판단하면 즉시 전송하지만, idle하지 않는다하면, random하게 wait한 후에 다시 sensing을 한다. 이 방법은 충돌 가능성을 줄여주는데, 2개이상의 stations들이 똑같은 time만큼 기다려서 재송신하지 않기 때문이다. 하지만, 프레임을 보낼 stations이 많은 상황에서도 medium이 idle한 상황이 발생할 수 있다는 단점도 있다.

• p-persistent: channel이 propagtion time 최대치 이상의 time-slot들로 나눠진 경우에 사용한다. 위의 2가지 방법의 장점들을 모아두었다. 충돌 가능성을 줄여주고 효율성을 개선한다. idle한 상태가 되면, 다음의 단계를 따른다. 1) p의 확률로, frame을 보낸다. 2) q=1-p의 확률로, station은 다음 slot의 시작을 기다리고, 다음을 다시 확인한다. <line이 idle하면 step1으로 다시 보내고, busy하면 충돌을 고려하여 back-off procedure를 수행한다>

1.2.3 CSMA/CD

이 방법은, station이 프레임 전송후에 성공적였는지 monitoring을 하게된다. 만약 성공적이면 종료되지만, 실패한 경우는 프레임을 재전송한다.

위의 경우처럼, t3, t4에서 충돌이 감지되면, 전송을 즉시 멈추게 된다. 또한 프레임의 마지막 비트를 보낼때까지 collision을 detect해야 한다. 프레임 전송 시간은, Propagtion time의 최소 2배는 되어야 하는데, 이는 가장 먼 station에서 프레임이 도달하기 위해서 Tp, 다시 원래 station에게 충돌 영향이 가는데 Tp가 걸리기 때문이다.

ALOHA와의 3가지 차이점

• persistence process의 추가 : 프레임을 전송하기 전, persistece process를 이용하여 sense한다.
• frame transmission : 알로하에서는 전체 프레임을 전송하고, ack를 기다리는 반면, CSMA/CD는 한번에 프레임 전체를 송신하지 않고, 전송과 충돌 감지가 연속적인 과정이다. station은 전송과 수신을 연속적으로, 동시에 진행한다. 충돌이 발생하지 않았으면, 프레임 전체의 transmission도 끝났음을 의미한다.
• Jamming sigmal : 다른 stations에게 충돌이 발생했음을 알려주는 것이다.

과거 LAN protocol에서는 CSMA/CD를 사용하여 전통적인 이더넷에서 10 Mbps의 전송을 하는데 사용하였다.

1.2.4 CSMA/CA

무선 네트워크를 위해 개발되었다. 충돌들은 3가지 전략들을 사용하여 회피하였다.

• Interframe Space (IFS) : Channel이 idle하다고 감지되어도, 멀리 있는 station에서 전송한 신호가 도달하지 못한 경우를 대비하여, interframe space(IFS) 시간동안 기다린다. IFS 시간동안 멀리서 오는 신호가 도달할 수 있도록 기다려주고, 만약 이 이후에도 idle한 상태이면, station은 conetention window만큼 다시 기다린 후에 전송을 한다. 또한 짧은 IFS는 높은 우선순위를 갖는다
• Contention window: slots들로 분해된 시간의 총합이다
  
• Ackonwlegement: Receiver가 프레임을 잘 받았다고 알려주는 메시지이다.
  

채널이 idle한 상태가 되면
1. DIFS만큼 일정 기간 기다린 후에, station은 RTS(request-to-send)라는 control frame을 보낸다.
2. RTS를 받은후 SIFS만큼 다시 기다리고, CTS(clear-to-send)라는 control frame을 보낸다. CTS에는 destination station이 데이터를 받을 준비가 되었다는 것을 알려준다.
3. SIFS만큼 기다린후, 데이터를 전송한다
4. 목적 station은 SIFS만큼 기다린후에, ACK를 보내어 데이터가 잘 수신되었다는 것을 알려준다.

Hidden-station problem
위의 그림을 보면 거리로 인해 RTS가 B에는 도달했지만, C,D에는 도달하지 못한 것을 확인할 수 있다. 하지만 B에서 나온 CTS가 C,D에도 도달하게 되어서, C와 D는 누군가 데이터를 전송한다고 생각할 것이고, 본인들의 데이터 전송을 삼갈 것이다.

CSMA/CA and Wireless Networks
무선 통신에서 많이 사용된다. 하지만 위에서 설명한 방법들은 정교하지 않아서, 무선 네트워크 문제들을 해결할 수 없을수 있다. 추후에 Chapter15에서 다루게 된다.

12.2 Controlled ACCESS

통제가 된 상황에서 송신이 일어나는 것을 말한다. station은 다른 stations의 승인을 받기 전까지는 송신하지 못한다.

12.2.1 Reservation

Reservation 방법서는 station은 데이터를 보내기 전에 예약을 해야한다. 시간이 여러 구간으로 분할되고, 각 구간에 예약 프레임들이 선점하게 된다. 만약 N개의 stations이 있다면, 최소 N개의 slot이 있어야 한다. Medium을 누가 사용할 것인지의 정보가 존재한다.

장단점

• 예약하여 사용하므로, collision이 줄어든다
• Delay가 발생한다.

12.2.2 Polling

Polling은 하나의 station이 primary station으로 지정되며, 나머지는 secondary stations으로 지정된다. 모든 데이터교환은 primary station을 거쳐야한다. Primary station은 collision을 방지하기 위해 select와 poll 함수를 사용한다.

Select

select함수는 primary가 보내고 싶은 데이터가 있을 때 사용된다. SEL frame을 통하여 secondary station이 받을 준비가 되었는지 확인한다.

Poll

poll함수는 primary가 데이터를 받을 준비가 되면, secondary에게 poll을 통해 보낼 것이 있는지 물어본다. 만약 보낼 것이 없으면 NAK를 보낸다. Primary는 그럼 다른 secondary에게 다시 물어보며, 데이터를 보낼 secondary를 찾을 때까지 반복한다. Primary가 데이터를 수신하면, ACK를 보내어 잘 수신한 것을 확인시켜준다.

장단점

• Collision이 거의 발생하지 않는다.
• Primary가 고장나면, 시스템 전체가 마비된다.
• 지연이 발생한다.

12.2.3 Token Passing

Token passing 방법은 stations들이 ring형태로 되어있다. 즉, 각 station을 predecessor와 successor로 되어있다. predecessor는 앞에 있는, successor는 뒤에 있는 것을 말한다.

이 방법에서는 token이라는 특별한 패킷이 ring을 순환한다. 토큰을 가지고 있을 때, station은 채널에 접속하여 데이터를 보낼 권한을 갖는다. 만약 station이 보낼 데이터가 있으면, predecessor로부터 토큰을 받을때가지 기다린다. 더이상 보낼 데이터가 없으면, successor에게 토큰을 넘겨준다. 토큰의 관리 역시 필수적이다. 토큰이 파괴,손실 되었는지 추적이 필요하다. 우선순위에 따른 토큰의 전달 역시 관리가 필요하다.

12.3 Channelization

Channelization은 stations의 다중 접속 방법으로, 시분할, 주파수 공유, 코드를 통해 이뤄진다.

12.3.1 FDMA

Frequency division multiple access(FDMA)방식은 가능한 주파수 대역을 분할하여, 각 station에 분배한다. 각 주파수는 reserved된 station에게 부여되여 사용된다.

이 방식의 흔적으로는, 전화 통화 시간에 따른 요금 부과 방법이 있다.(1세대 이동통신)

12.3.2 TDMA

Time division multiple access(TDMA)에서, stations은 시간동안 채널의 주파수를 공유한다.(시분할) 각 station은 time slot을 할당받아, 데이터를 전송할 수 있다. 기존의 FDMA에서 주파수는 비싸므로, 1개의 station에 할당하는 것은 낭비가 될 수 있다. 이를 보완하고자, 디지털 변환을 통해 압축하여 굉장히 빠른 채널(초고속 네트워크)에 실어보낸 후, 다시 압축을 푸는 과정을 통해 전송하는 방식을 사용한다. 하지만 압축하고 푸는 과정에서 delay가 발생할 수 있으나 사람이 인지할 정도는 아니다. 또한 data를 large area에 spread하면, propagation delay가 발생할 수 있는데, guard time을 통한sunchronization을 통해 해결할 수 있다. 주로 2세대 통신에 활용하던 방식이다.

12.3.3 CDMA

Code division multiple access(CDMA)는 군용기술이 민간으로 이전된 것이다. code를 통해 encode/decode 과정이 존재하며, 각 station의 코드를 알아야 해독이 가능하다. 이 방법은 FDMA와 달리 한 채널이 여러 주파수 대역을 사용하고, TDMA와 달리 시분할 없이 모든 stations이 동시에 데이터를 전송할 수 있다는 점이다. 이 방법은 초고속 채널(네트워크)를 필요한데, 사람이 만들기 매우 어려웠다. 3세대 이동통신에 많이 사용되었는데, 너무 많은 processing power을 필요로 하여 이후세대의 통신에는 거의 사용되지 않는다.

각 station의 데이터와 코드를 곱한 값을 더하여, Common channel을 통해 보낸다.

Channel의 데이터를 다시 station별 코드와 곱하면(위의 경우 station2 코드와의 곱) 결과를 구할 수 있다. 이 값들을 더한 후에 code-size로 나누어 scaling-down한 결과를 통해 원래 데이터(bit)를 복원할 수 있다. 이 방법을 통해 어느정도의 용량 개선이 되었다고 한다.