12. Multiple Access

dain·2022년 12월 19일

네트워크

Multiple Acces

Data link layer

데이터 링크 계층은 기능에 따라 두 개의 하위 계층으로 분리된다.

Upper Layer
- Data Link layer (DLC): 데이터링크 컨트롤 담당
Lower Layer
- Multiple-access resolution (MAC): 공유 매체에 대한 접근 해결 담당

다중 접근 프로토콜

여러 노드나 스테이션이 하나의 공통된 링크 (= multipoint = broadcast link)에 연결되어 있을 때, 링크에 대한 접근을 조정하는 프로토콜

목표
- 노드 사이의 충돌 방지
- 만약 충돌이 발생했다면, 충돌 제어

분류 체계

Radom Access

임의 접근 프로토콜

다중 접근 프로토콜에서 충돌을 해결하는 방법 중 하나
전송이 지국 사이에서 임의로 벌어지기 때문에 (정해진 시간표 X) 임의 접근 프로토콜이라 한다.
지국 간의 전송에 대한 규칙이 없고 지국들이 매체에 접근하기 위해 경쟁하기 때문에 경쟁 방식(contention)이라고도 한다.
임의 접근 방식에서 어떤 지국도 다른 지국보다 우월하지 않으며, 어떤 지국도 다른 지국에 대한 제어 권한을 할당받지 않는다. 또한 어떤 지국도 다른 지국의 전송을 허용하지도, 허용하지 않지도 않는다. (즉, 모든 노드는 통신 상황에서 평등하다)
각각의 경우에서 전송할 데이터가 있는 지국은 프로토콜에 의해 정의된 절차를 사용하여 전송 여부를 결정한다.

임의 접근 프로토콜에서의 충돌

하나 이상의 스테이션이 전송을 시도할 때, 충돌(Collision)이 발생하고 프레임은 파괴되거나 수정된다.

접근 충돌을 피하기 위해 각 지국이 답하는 질문
- 지국은 언제 매체에 접근할 수 있는가?
- 매체가 바쁠 때 지국은 무엇을 할 수 있는가?
- 지국이 전송에 대한 성공과 실패를 어떻게 결정할 수 있는가?
- 접근 충돌이 있을 때 지국은 무엇을 할 수 있는가?

ALOHA 네트워크

1970년대 하와이 대학에서 개발한 최초의 임의 접근 방법
기지국은 중앙 제어 장치로서 hop 역할을 한다.
: 모든 지국은 서로 직접적으로 통신하는 것이 아니라, 기지국을 통해 통신한다.

Hop
? 컴퓨터 네트워크에서 출발지와 목적지 사이에 위치한 경로의 한 부분이다. 데이터 패킷은 브리지, 라우터, 게이트웨이를 거치면서 출발지에서 목적지로 경유한다. 패킷이 다음 네트워크 장비로 이동할 때마다 홉이 하나 발생한다.
충돌 가능성 O
모든 수신 데이터가 사용하는 주파수 대역: 407 MHz

Pure ALOHA ⭐

각 지국은 전송할 프레임이 있을 때마다 프레임을 보낸다. 그러나 공유하는 채널이 오직 하나이므로 다른 지국의 프레임 간 충돌 가능성이 있다.

지국, 프레임 전송
지국, 수신자의 응답(acknowledgment)을 최대 전파 지연 시간의 2배 2 * T(p) 동안 기다림
최대 전파 지연 시간의 2배 (타임 아웃 시간)동안 응답을 받지 못했을 경우, 프레임이 손상된 것으로 간주 (충돌이 일어나 프레임이 성공적으로 전송되지 않은 것으로 간주)
→ 전송 시도 횟수 +1
전송 시도 횟수 K가 최대 재전송 횟수 K(max) 보다 작거나 같은 경우 (일반적으로 15 이하인 경우), 각 지국은 0부터 2^k-1 사이의 랜덤 숫자 R을 뽑음

랜덤 숫자 R에 의해 결정된 임의의 시간 T(B)만큼 대기한 후, 재전송 시도
- 타임 아웃이 발생한 직후 프레임을 재전송 한다면 또 다시 충돌이 발생할 것이기 때문에 임의의 시간만큼 기다렸다가 프레임을 재전송한다.
- 랜덤 숫자의 범위는 충돌이 발생할 때마다 증가하며, 그에 따라 각 지국의 대기 시간이 다양해지므로 충돌 발생 가능성이 줄어든다.
- T(P) 최대 전파 시간 = 거리 / 전파 속도
- T(B) 대기 시간
  : 일반적인 공식은 '이진 지수 대기시간'으로 T(B) = R * T(P) 또는 T(B) = R * T(fr)
  - r : 0부터 2^k-1 사이의 랜덤 숫자
  - k : 실패한 전송 시도 횟수
- T(fr) : 프레임을 전송하는데 요구되는 평균 시간

취약 시간
- 순수 알로하 프로토콜에서 충돌이 일어날 수 있는 시간(취약 시간)은 프레임 전송 시간의 두 배이다.
- Pure ALOHA vulnerable time = 2 * T(fr)

처리율
- G
  - 한 프레임 전송 시간 동안 시스템 전체에서 생성되는 프레임의 평균 개수
- 처리율 S
  - ? 성공적인 전송의 평균 횟수 (성공적으로 전송되는 프레임의 개수)
  - S = G * e^(-2G)
- 최대 처리율 S(max)
  - G가 1/2인 경우 S(max) = 0.184

Slotted ALOHA

한 프레임의 평균 전송 시간 T(fr)을 여러 개의 슬롯으로 나누고, 지국이 타임 슬롯의 시작에서만 프레임을 전송할 수 있도록 규제하는 알로하 프로토콜
취약 시간
- 순수 알로하 프로토콜의 절반
처리율
- S = G * e^(-G)
- G = 1일 때 최대 처리율 S(max) = 0.368
순수 알로하 프로토콜에 비해 취약 시간 절반, 충돌 구간 절반, 처리율 2배

Carrier Sense Multiple Access (CSMA)

충돌 가능성을 최소화하고 성능을 향상시키기 위해 개발된 다중 접근 프로토콜
"sense before transmit"/ "listen before talk" 원리에 기반
충돌 가능성을 줄이지만, 충돌을 완전히 없애는 것은 X
전파 지연(신호가 전송되는데 걸리는 시간차)으로 인해 충돌 가능성 여전히 존재
- 지국이 프레임을 전송할 때 그 프레임의 첫 번째 비트가 모든 지국들에 도달하여 각 지국이 비트를 감지하기 까지는 시간이 걸린다. 따라서 지국이 매체가 사용되지 않는 상태라고 감지하더라도, 실제로는 다른 지국에서 보낸 첫 번째 비트가 전송 중이지만 아직 도달되지 않은 상태일 수 있다.
- CSMA에서의 충돌의 공간/시간 모델

취약 시간
- CSMA에서 취약 시간은 전파 시간 T(p)이다.
- 전파 시간은 신호가 매체의 한 끝에서 다른 끝으로 전파되는 데 소요되는 시간으로, 전파 시간 동안 각 지국은 전송된 프레임의 첫 번째 비트를 감지했을 것이고, 충돌을 방지하기 위해 프레임을 전송하지 않는다.

Persistence methods ⭐⭐

매체가 휴지 상태이거나 사용 중일 때 지국이 취해야 할 방식 정의
- 1-persistent 방식
  - 지속적으로 회선 감지
  - 지국이 회선이 휴지 상태인 것을 감지하면, 즉시 프레임 전송 (확률 1)
  - 단점 : 충돌 발생 가능성 높음
    (두 개 이상의 지국이 회선이 휴지 상태인 것을 감지할 경우, 두 지국 모두 즉각적으로 프레임을 전송하기 때문에)
- non-persistent 방식
  - 비지속적으로 회선 감지 (임의의 시간만큼 대기)
  - 지국이 회선의 휴지 상태인 것을 감지하면, 즉시 프레임 전송
  - 그러나 회선이 휴지 상태가 아닌 경우 (다른 지국에 의해 사용 중인 경우) 임의의 시간을 대기했다가 다시 감지
  - 장점 : 임의의 시간을 대기하기 때문에 두 개 이상의 지국이 동시에 전송할 확률 낮음
    → 충돌 발생 가능성 낮음
  - 단점 : 회선 효율 감소 (임의의 시간을 결정하는데 필요없는 에너지를 낭비하고, 프레임 전송마다 추가적인 시간을 기다려야 하기 때문에)
- p-persistent 방식 ⭐
  - 일단 지속적으로 회선 감지하다
  - 만약 지국이 회선이 휴지 상태인 것을 감지하면, 확률에 따라 프레임을 전송하거나 대기
    - 확률 p로 프레임 전송
    - 확률 q=1-p로, 지국은 다음 타임 슬롯의 시작까지 기다렸다가 다시 한 번 회선 감지
CSMA의 persistence method

CSMA with Collision Detection (CSMA/CD) ⭐

CSMA에 충돌 처리 절차를 더한 것
지국은 프레임을 전송한 후, 전송이 성공했는지 매체 관찰
- 만약 성공했다면, 지국은 해야 할 일을 마친 것
- 만약 충돌이 발생했다면, 프레임 재전송
CSMA/CD에서 첫 번째 비트의 충돌
- A의 전송 시간: t(4) - t(1)
- C의 전송 시간: t(3) - t(2)
CSMA/CD에서 충돌과 폐기 (abortion)
최소 프레임 크기
- CSMA/CD가 작동하려면, 프레임 크기에 제한 필요
- 프레임 전송 시간 T(fr)은 최대 전파 시간 T(p)의 적어도 두 배여야 한다.
  : 지국은 프레임의 모든 비트를 송신하고 나면, 프레임에 대한 사본을 가지지 않으며 회선을 관찰하여 충돌이 생겼는지 확인하지 않기 때문이다. 따라서 지국은 2T(p) 이후에도 계속 전송을 하고 있어야 충돌을 감지하고 프레임을 재전송할 수 있다.

플로우 다이어그램

전송, 휴지, 충돌 동안의 에너지 준위
- 충돌이 발생하면 비정상 에너지 준위 (정상 준위의 2배)

CSMA with Collision Detection (CSMA/CA) ⭐

CSMA/CA는 무선 네트워크에서 충돌을 피하기 위해 개발되었다.
CSMA/CA에서 충돌을 방지하기 위해 사용하는 세 가지 전략
- Interframe space (IFS)
  - 지국이나 프레임의 우선 순위를 정의하는 데도 사용
  - 전파 지연 시간에서의 충돌을 피하기 위해서 사용
- Contention window
  - CSMA/CA 방식을 사용하는 무선 LAN 에서, 공유 매체가 사용가능함을 알고난 후에도,
    일정시간(IFS)을 기다리고, 그때부터 임의 대기하게되는 슬롯 단위로 구분되는 시간 범위
  - 채널이 사용 중임을 감지할 때, 경쟁 윈도우의 타이머를 바로 다시 시작(초기화)하는 것이 아니라, 타이머를 멈췄다가 채널이 휴지 상태가 되면 재시작한다.
- Acknowledgments

플로우 다이어그램

⭐ CD와 CA의 차이

CD는 유선, CA는 무선

CA에서는 랜덤성이 보장된다면 충돌 확률 낮음

Controlled Access

제어 접근에서 지국들은 서로 상의하여 어떤 지국이 전송할 권리를 갖는지 찾는다. 지국은 다른 지국들에 의해 권한을 인정받지 않는다면 전송할 수 없다.

Reservation

지국은 데이터를 보내기 전에 반드시 예약해야 한다.
- 각 구간에서, 예약 프레임은 그 구간에서 전송되는 데이터 프레임의 앞에 있다.
- 만약 시스템에 N개의 지국이 있다면, 예약 프레임에 N개의 예약 minislot이 존재하고,각 minislot은 지국에 속한다.
- 지국이 데이터 프레임을 보낼 때, 지국은 자신의 미니슬롯을 예약하고, 예약 프레임 뒤에 데이터 프레임을 전송할 수 있다.
예약한 지국만 데이터를 보낼 수 있기 때문에 충돌 X
예시

Polling

폴링은 한 장치가 주 지국 (Primary Station)으로 지정되고, 다른 장치들이 부 지국 (Secondary Station)으로 지정되는 위상 체계에서 작동한다.
주 지국은 어느 지국이 어느 때에 매체를 사용할지 결정하고, 모든 데이터는 (부지국 사이의 데이터 통신일지라도) 반드시 주 지국을 통해 교환이 이루어진다.
- 주 장치: 링크 제어, 세션의 초기화
- 부 장치: 주 장치의 지시 따름
단점
: 주 지국 마비 → 전체 시스템 마비
폴링 접근 방법에서 충돌을 방지하기 위한 기능
- Poll 기능
  - 주국이 데이터를 수신하기를 원할 때, 부국들에게 전송할 데이터가 있는지 묻는 것
  - 주국이 데이터를 수신할 준비가 되었을 때 각 장치 (부국)들에게 차례대로 전송할 데이터가 있는지 물어보고 (SEL), 부국들은 전송할 데이터의 여부에 따라 부정 응답이나 데이터를 보낸다. (ACK) 주국이 부정 응답을 받을 경우 데이터를 보낼 부국을 찾을 때까지 폴을 반복하고, 긍정 응답 (데이터 프레임)을 받을 경우 프레임을 읽고, 부국에게 응답을 보내어 데이터를 받은 것을 확인해 준다.
- Selection 기능
  - 주국이 전송할 데이터가 있을 때, 그 부국에게 데이터를 수신할 준비가 되었는지 묻는 것

토큰 패싱 네트워크

토큰 패싱 네트워크에서 지국은 특별한 프레임 (토큰)을 수신할 때 데이터를 보낼 권리가 있다.
토큰 패싱 방식에서 네트워크 안의 지국들은 고리 (ring) 형태로 구성되고, 토큰은 고리를 순회하며 각 지국의 차례마다 보낼 데이터가 있는지 확인한다.
보낼 데이터가 있는 지국은 선행 지국으로부터 토큰을 받을 때까지 기다리고, 토큰을 받았지만 보낼 데이터가 없는 지국은 토큰을 후행 지국으로 바로 넘겨준다.
토큰을 받은 지국만 데이터를 전송하므로 충돌 발생 X

Channelization

채널화란 서로 다른 지국 간에 시간/주파수/코드를 통해 링크의 사용 가능한 대역폭을 공유하는 다중 접근 방식이다.

채널화의 3가지 프로토콜
- Frequency-Division Multiple Access (FDMA)
- Time-Division Multiple Access (TDMA)
- Code-Division Multiple Access (CDMA)

Multiplexing과의 차이?

Multiplexing?

두 개 이상의 장치로 연결된 매체의 대역폭이 장치들이 요구하는 대역폭보다 클 때, 하나의 링크를 여러 개의 채널로 나누어, 하나의 링크에서 여러 개의 신호가 동시에 전송될 수 있도록 하는 기술

FDMA

FDMA에서 사용 가능한 대역폭은 주파수 대역으로 나뉘고, 각 지국에는 데이터를 전송할 대역이 할당된다. 즉, 각 대역은 특정 지국을 위해 예약되어 있으며 항상 지국에 속한다.
특징
- 사용 가능한 대역폭이 모든 지국에 의해 공유됨
  (FDMA에서 공유되는 채널의 사용 가능한 대역폭은 보호 대역에 의해 분리된 대역들로 나뉘어진다.)
- FDMA는 물리 계층의 FDM을 이용하는 데이터 링크 계층의 프로토콜이다.

FDM

아날로그 신호를 결합하는 아날로그 다중화 기술

유사한 범위의 대역폭(주파수)을 사용하는 각각의 신호를 서로 다른 carrier frequency로 변조하여, 서로 다른 대역폭 범위의 신호들을 하나의 신호로 결합하고 링크를 따라 전송하는 기술

TDMA

TDMA에서 지국들은 시간에 따라 채널의 대역폭을 공유한다. 각 지국에는 데이터를 전송할 수 있는 시간 슬롯이 할당되고, 각 지국은 할당된 시간 슬롯에 있는 데이터를 전송한다.
특징
- 전체 대역폭은 하나의 채널
  (TDMA에서 대역폭은 서로 다른 지국 간에 시간을 공유하는 하나의 채널일 뿐이다.)
- 지국은 시간 내에 채널의 용량을 공유한다.

CDMA

CDMA에서는 하나의 채널이 모든 전송을 동시에 한다.
(FDMA와는 다르게 링크의 대역폭을 나누지 않고, TDMA와는 다르게 타임 슬롯이 존재하지 않는다)
CDMA에서 데이터의 표현
- 데이터 비트가 0일 때 : -1
- 데이터 비트가 1일 때 : 1
- Silence (지국이 휴지 상태일 때 = 보낼 신호가 없을 때): 0
CDAM는 코딩 이론에 기반
- 각 지국은 chips 라고 불리는 일련의 숫자인 코드를 할당받는다.
- 칩 시퀀스
- 직교 시퀀스의 특성
  - 두 개의 동일한 시퀀스의 내적
    : A⋅A = N
  - 서로 다른 시퀀스의 내적
    : A⋅B = 0
  - A⋅(-A) = -N
CDMA에서 데이터의 표현
- 데이터 비트가 0일 때 : -1
- 데이터 비트가 1일 때 : 1
- Silence (지국이 휴지 상태일 때 = 보낼 신호가 없을 때): 0

인코딩
- 인코딩
  : 각 지국에서의 생성된 디지털 신호 (데이터 비트와 코드의 내적), 하나의복합 신호로 합성
- 멀티플렉서

디코딩
- 디코딩: 하나의 복합 신호, 지국의 개별 신호로 분리
- 복합 신호 ⋅ 지국의 코드 → 내적 결과의 값을 모두 더함 → 모든 지국의 수로 나눔 → 데이터 비트로 변환
- 디멀티플렉서

Sequence Generation
- Walsh 테이블
  - 행과 열의 수가 동일한 2차원 표
  - CDMA에서 시퀀스를 생성하기 위해 사용
  - 각 행은 칩 시퀀스로 이루어짐
- 예시
- Walsh 테이블에서 시퀀스의 수 N = 2^m
  - 사용자의 수 =< 시퀀스의 수 (시퀀스는 무조건 2의 거듭제곱이니까)