데이터 링크층은 세부적으로 2 부분으로 나눠진다. 첫 번째가 DLC(Data Link Control), 그리고 그다음이 MAC(Multiple Access Resolution)이다. 매체 접근 제어 (MAC)를 쓰는 이유는 다음과 같다.
Link에서 Point-to-Point, Broadcast 방식이 있는데, 두 사람이 말할 땐 상관없지만 여러 사람이 각자 말하면 목소리가 섞여 제대로 대화가 되지 않는다. 이렇게 한 Link가 2개 이상의 신호를 받는 것을 충돌 (Collision) 이라고 한다. MAC는 이 Collision을 최소화하기 위해서 노드가 채널을 어떻게 나눠서 가질지 결정하는 분산 알고리즘이다.
MAC의 주 기능 3가지
임의 접근 (Random Access)
Random Access 방식은 경쟁 방식(contention) 으로, 모든 지국은 평등한 위치에 있으며 어떤 지국도 다른 지국에 의해 제어받지 않는다. 그래서 전송할 데이터가 있는 지국은 전송할지 말지를 정해진 프로토콜(ALOHA | CSMA | CSMA/CD | CSMA/CA ) 이 지정해준 절차를 따른다. 전송하기 위해 따로 예정된 시간은 없으며 말 그대로 랜덤한 시간에 전송된다. 그래서 Collision이 자주 발생함.
그래서 이 Collision을 피하기 위한 프로토콜들의 절차는 어떤 것이 있을까? Random Access에서는 다음과 같은 조건으로 Collision을 피하고자 한다.
1. 지국이 언제 매체에 접근할 수 있는가?
2. 매체가 사용 중이면 지국은 무엇을 할 수 있는가?
3. 지국은 전송이 성공했거나 실패했는지 어떻게 알 수 있는가?
4. 접근 갈등이 있을 때 지국은 무엇을 할 수 있는가?
ALOHA
가장 오래된 Random Access 방식으로 무선 LAN을 위해 설계 되었다. 순수 ALOHA와 틈새 ALOHA로 나눠진다.
순수 ALOHA는 그냥 지국이 전송할 프레임이 있으면 그냥 보낸다. 채널이 하나 밖에 없으므로 다른 지국과 프레임을 보내는 시간이 겹치면 충돌이 난다. 오직 수신자의 응답(ACK)에만 의존하고 ACK가 시간 안에 안오면(Time Out) 충돌이 난 것으로 보고 계속 보낸다.
ACK의 수신 여부를 true/false로 받아서 참이면 통신이 성공, 실패 시 시도 횟수 K를 +1 해서 랜덤 난수 R 만큼 기다렸다가 다시 보낸다.
그렇다면 최대 취약시간은 다음과 같이 2 x T(fr) 가 된다.
최대 효율은 G = 1/2 일 때 최대다.
틈새 ALOHA는 시간을 T(fr)의 틈새로 나눠서 매 시간 틈새가 시작할 때 전송하도록 규제하는 것이다.
정해진 틈새에서만 충돌이 일어나기 때문에 기존의 순수 ALOHA 보다 2배 적은 취약 시간을 가진다.
그렇기 때문에 최대 효율 역시 G = 1 일 때 가장 좋다. 참고로 G는 프레임의 평균 갯수 이다.
Carrier Sense Multiple Access (CSMA)
CSMA는 ALOHA만으로는 한계가 있어서 충돌의 가능성을 최소화 하고 성능을 더욱 높이기 위해서 개발되었다.
지국이 매체를 사용하기 전에 매체를 감지하게 되면 충돌의 기회를 줄일 수 있다. 즉 눈치 게임을 한다는 뜻이다.
충돌의 가능성은 줄일 수 있으나 완전히 충돌을 막는 건 불가능하다. 전파 지연 때문인데, 눈치게임을 할 때 아무도 처음 1을 외치지 않아서 서로 눈치를 보다가 동시에 1을 외치는 현상이라고 보면 된다.
B가 t1의 시간에서 프레임 전파를 시작하면 A와 B 를 향해서 신호 영역이 전파된다. 시간이 계속 지나므로 B 의 t1 지점으로부터 평행사변형 모양이 되는 것이다.
CSMA의 취약시간은 다음과 같다. 프레임을 t1 에서 보내게 되면 전파 시간 만큼 취약시간이 생긴다.
지속 방식 (Persistent method)
CSMA의 핵심적인 기술인 지속 방식은 매체가 휴지(idle) 상태 이거나 사용 중(busy) 일 때 지국이 취해야 하는 방식을 정의한 것이다.
크게 3가지로 1-persistent method, Non-persistent method, p-persistent method 가 있다.
1-persistent method
1-지속 방식은 프레임 전송 전 채널을 검사한다. 검사하다가 채널이 idle 상태면 프레임을 전송하고 busy 상태면 보내지 않고 채널 감시를 계속한다. 그러다가 idle이 되면 프레임을 보낸다. 이 방식은 idle 일 때 1의 확률을 가지고 즉각 프레임을 보내기 때문에 가장 높은 충돌 위험성을 가진다.
Non-persistent method
1-지속 방식과 비슷하게 idle 상태일 때 프레임을 전송하는 건 같지만 busy 상태일 때 채널의 상태를 지속적으로 감시하지 않고 임의의 시간이 지난 후 채널을 검사한다.
P-persistent method
1-지속 방식과 비지속 방식의 장점을 합쳐서 만든 방식으로 채널이 최대 전파 지연 시간과 같거나 큰 시간 틈새를 사용하는 경우에 채택된다. 충돌의 위험은 줄이고 효율은 높이는 방식이다. 채널이 idle인 상태를 감지하면 다음의 두 단계를 거친다.
1. 확률 p를 가지고 프레임을 전송한다.
2. 확률 q = 1 -p 를 가지고 지국은 다음 틈새 시작까지 기다리다가 회선을 다시 감지한다. 이 때 만일 회선이 idle상태면 1. 단계로 돌아간다. busy 상태라면 충돌이 생긴 것으로 간주하고 다시 대기 철차에 들어간다.
반송파 감지 다중 접근/충돌 검증 ( CSMA/CD)
한국어로 쓰니까 오히려 더 어렵다. 그냥 영어로 쓰자.
Carrier sence multiple Access with Collision detection, CSMA/CD 이다 .
Collistion Detection 이기 때문에 유선에서 사용된다. 무선은 충돌을 감지할 수 없다.
충돌을 감지하고 처리하는 방식이 추가된 CSMA이다.
A가 t1 에서 프레임을 보낸다. t1~t4길이의 프레임을 보내면 t3 에서 C가 t2에서 보낸 프레임과 충돌한다.
A의 전송 시간은 t4-t1, C의 전송 시간은 t3-t2가 된다.
최소 프레임 크기
- CSMA/CD가 작동하려면 프레임 크기에 제한 필요하다. 충돌을 감지하면 전송을 멈춰야 하기 때문이다. 그래서 최소 프레임 크기가 존재하고 64바이트가 이더넷 표준의 최소 프레임 길이다.
- 최소 프레임 전송 시간 T(fr) = 2 * 최대 전파 시간 T(p)
반송파 감지 다중 접근 / 충돌 회피(CSMA/CA)
Carrier sense multiple Access with collision avoidance (CSMA/CA)는 무선 네트워크를 위해 만들어 졌다.
CSMA/CA는 Interframe space 라고 하는 IFS라 불리는 프레임 간 공간만큼 기다리는 것이 핵심이다.
IFS는 우선 채널이 idle 상태임을 알더라도 전송을 늦춰서 경쟁 구간을 피해 충돌 자체를 회피하는 기능을 구현하는데 쓰인다.
경쟁 구간 (contention window)
경쟁구간이란 시간 틈새로 나뉘어 있는 일정 시간이다. 전송할 준비가 되어 있는 지국은 임의의 수를 선택하여 그만큼 기다린다. 이 구간의 틈새 수는 2진 지수 대기 전략에 따라 달라질 수 있다. 이는 1개 틈새로 시작했다가 매번 idle 채널을 발견 하지 못할 때 마다 2배씩 틈새를 늘린다는 것을 의미한다.
채널이 사용 중인 것이 감지되면 다시 처음부터 과정을 진행하는 것이 아니라 잠시 타이머를 멈춘다.
그리고 다시 idle 상태가 감지되면 그 때 타이머를 시작한다.
그렇게 했을 때 가장 오래 기다린 지국부터 우선순위를 가진다.
프레임 교환
Controlled Access
접근 제어는 지국 간의 상의를 통해 지국의 전송 권리를 획득하는 것을 의미한다.
지국은 다른 지국에 의해 권리를 인정받을 때 까지 전송을 할 수 없다.
총 3개의 제어 접근 방식이 있다.
Reservation
지국은 데이터를 송신하기 전에 예약을 해야 한다.
N개의 지국이 있다면 총 N개의 예약 미니 틈새(mini slot)가 존재한다.
지국이 데이터를 송신하려 하면 미니 틈새에 예약을 건다.
예약한 지국은 해당 예약 프레임뒤에 자신의 데이터를 실어서 보낸다.
Polling
폴링은 주국과 종국들로 구성된 접속 형태에서 동작된다.
Select와 Poll라는 것이 존재한다.
Select : 주국이 뭔가 보낼 것이 있을 때 마다 수행, 주국은 종국의 주소가 포함된 선택(SEL)프레임을 전송하여 종국의 확인 응답을 받음
Poll : 주국이 종국들로부터 뭔가 받을게 있을 때 마다 수행, 주국이 각 장치로부터 보낼 것이 있는지 물어본다.
Token passing
링 형태의 네트워크일 때 쓴다.
Channelization
채널화란 서로 다른 지국 간에 시간/주파수/코드를 통해 링크의 사용 가능한 대역폭을 공유하는 다중 접근 방식이다.
채널화의 3가지 프로토콜은 다음과 같다.
- Frequency-Division Multiple Access (FDMA)
- Time-Division Multiple Access (TDMA)
- Code-Division Multiple Access (CDMA)
FDMA와 TDMA는 다중화 기법인 FDM 과 TDM 방식과 비슷한데, 중요한 것은 둘의 장점을 합친 CDMA이다.
CDMA(code-division multiple access)
CDMA 채널화는 하나의 채널이 모든 전송을 동시에 보낸다. 모든 지국들이 시분할 없이 동시에 데이터를 송신 할 수 있다. 즉 FDMA와 TDMA의 장점만 합친 것이다.
아이디어는 다음과 같다.
1. 각 코드를 다른 코드로 곱하면 0이 된다.
2. 각 코드를 자신의 코드에 곱하면 지국의 개수가 된다.
칩스
CDMA방식은 코드 이론에 근거하고 있다. 각 지국은 코드를 할당받으며 이 코드는 칩스라고 불리는 일련의 숫자이다.
각 순열은 N개의 요소로 되어 있으며 N은 지국의 수를 의미한다. 순열을 어떤 수로 곱하면 순열의 각 요소는 그 수로 곱해진다. (분배 법칙)
그리고 같은 순열을 곱하면 N이 나온다.
서로 다른 순열을 곱할 시 0 이 나온다.
두 순열을 더하는 것은 그냥 인덱스에 맞게 합치는 것과 같다.
이러한 원리를 가지고 칩 순열을 생성한다.
그리고 CDMA에서는 이 칩 순열을 통해 데이터를 표현한다.
데이터의 비트가 0 이면 -1, 1이면 +1, 없으면 0으로 표현해 칩 순열을 생성한다.
이 그림을 신호 준위로 바꾸면 다음과 같다.
또한 CDMA에는 Walsh 테이블이라는 것이 있다.
Walsh 테이블은 다음의 규칙으로 이뤄져 있다.
- 행과 열의 수가 동일한 2차원 표
- CDMA에서 시퀀스를 생성하기 위해 사용
- 각 행은 칩 시퀀스로 이루어짐
즉, Walsh 테이블의 순열의 개수는 $N = 2^m$이여야 한다.
약어 & 개념 정리
MAC : Multiple Access Resolution - 충돌을 최소화 하거나 막기 위한 채널 분산 기법
MAC 에는 크게 3가지의 기능 Random Access, Controlled Access, Channelization 이 있음.
Random Accesss는 ALOHA, CSMA/CD, CDMA/CA 3가지가 있음
CSMA(Carrier Sence Multiple Access) 에는 persistent method 라고 하는 지속 방식이 3개 있음 ( 1-지속 방식, 비 지속 방식, p 지속 방식)
CSMA/CD : Carrier Sence Multiple Access Collision Detection (충돌 감지, 유선에서 사용)
CSMA/CA : Carrier Sence Multiple Access Collision Avoidance (충돌 회피, 무선에서 사용)
Channelization 에는 크게 3가지의 기법으로 나눠짐
TDMA : Time-Division Multiple Access
FDMA : Frequency-Division Multiple Access
CDMA : code-Division Multiple Access
'network' 카테고리의 다른 글
| [데이터 통신] Chapter 09 데이터 링크층 개요 연습 문제 & 정답 (0) | 2023.06.13 |
|---|---|
| [데이터 통신] Chapter 08 교환 연습 문제 & 정답 (0) | 2023.06.13 |
| [데이터 통신] Chapter 11 데이터 링크 제어 DLC (0) | 2023.06.11 |
| [데이터 통신] Chapter 10 오류 검출과 오류 정정 (0) | 2023.06.11 |
| [데이터 통신] Chapter 09 데이터 링크층 개요 (0) | 2023.06.11 |
