컴퓨터 네트워크 - Link 계층: MAC Protocol
K-MOOC에서 부산대학교 유영환 교수님의 “컴퓨터 네트워킹” 강의를 수강하며 적은 노트
Multiple Access Protocols
shared link(shared medium): 여러 호스트들이 채널을 공유
Multiple Access Protocol(MAC 프로토콜): 하나의 채널을 공유할 때 여러 노드가 동시에 전송을 하여 발생하는 데이터 충돌을 방지하는 프로토콜
- 요구사항
- 전체 노드들 중에서 하나만 동작 할 경우에는 그 노드가 모든 capacity를 다 사용
- M개의 노드가 전송을 할 때는 모두 R/M의 똑 같은 capacity를 사용
- 각 노드들이 서로 통신해서 순서를 정하면 오버헤드가 심하므로, 완전히 서로 분산적으로 동작
- 간단함
- channel partitioning: 전체 채널을 time slot 또는 주파수로 나눠 개별 유저에게 할당
- taking turn: 전체 채널을 나누지 않고 순서를 정함
- random access: 개별 노드들이 알아서 적당히 채널을 사용
- 위 둘보다 완전히 분산적이지만 충돌 발생
MAC Protocols without Collision
FDMA(Frequency Division Multiple Access): 주파수로 나누어 각 채널을 각각 사용
FDMA는 주파수 혼선을 막는 guard band가 있어 주파수 낭비가 있음
TDMA(Time Division Multiple Access): 시간으로 나누어 전체 bandwidth를 한 사용자가 사용
CDMA(Code Division Multiple Access): 코드를 적용해 인코딩과 디코딩으로 서로 데이터를 구별
- FDMA나 TDMA는 사용하지 않을 때는 해당 채널이나 타임 슬롯이 낭비되지만, CDMA는 전체 사용
Taking turn
- polling: 각 노드 별로 데이터를 전송할 수 있는 순서를 정해 줌
- 블루투스: 마스터 노드, 여러 개의 슬레이브 노드들
- 마스터가 각 슬레이브들에게 보낼 것이 있는지 물어보고 있다면 전송받음
- 순서를 정하기 위해 통신을 하므로 오버헤드, 지연 발생
- single point of failure: 마스터 노드에 문제가 생길 경우 전체가 통신 불가
- token ring: token을 가진 호스트만 전송
- token passing: token이 하나의 노드에서 다른 노드로 순서대로 전달
- token을 관리하는 오버헤드, 데이터가 보낼 게 없는 노드에도 토큰이 전달되었다 넘어가므로 latency 발생
- single point of failure: token을 가진 노드가 고장이 나면 통신 불가
- FDDI(Fiber Distributed Dual Interface)
- 안정성을 위해 서로 다른 방향으로 도는 두 개의 ring
- 처음 primary ring에서 돌다가, 끊어지면 다른 ring에서 돌기
MAC Protocols with Collision
랜덤 액세스
- 장점
- 하나의 노드만이 전송할 게 있다면 채널의 전체 full data rate을 보낼 수 있음
- 노드들 사이에 coordination이 필요 없이 개별적으로 알아서 수행
- 단점
- collision 발생: 감지 및 복구 문제 해결해야 함
ALOHA(Additive Links Online Hawaii Area)
- air time: 무선에서의 실제 전송 시간
- 알로하 네트워크는 모든 프레임들이 같은 길이이므로 전송 rate와 air time이 동일
- 데이터가 보내고 싶으면 그냥 보냄, collision 발생하면 랜덤 딜레이 뒤 재전송
- 여러 노드가 중앙 서버에 전송하는 형태로, up-link 채널과 down-link 채널 구분
- 서버는 데이터를 전송받고 down-link 채널로 그것을 retransmission, 에코로 잘 전송됨을 알림
- efficiency
- 한 프레임 전송 $air time = 1$ 가정
- $t0$에 $i$ 프레임이 정상 동작하기 위해서는 $t0-1$ ~ $t0+1$에서 전송 시작되는 프레임이 없어야 함
- 프레임의 타임슬롯 내에 전송을 시도하는 노드의 평균 수를 $G$로 가정
- 포아송 분포: $t0$~$t0+1$에 $k$개의 노드가 전송을 시작할 확률 = $G^ke^{-G}/k!$
- $t0-1$ ~ $t0+1$에서 전송되면 안 되므로, $2G$ 대입: $(2G)^k e^{-2G}/k!$
- 아무도 전송 안 할 확률은 $k=0$ 대입: $e^{-2G}$
- 전송 성공할 확률: $Ge^{-2G}$
- 미분: $G=0.5$일 때 최대. 대입하면 0.184, 실제 데이터를 전달 시간은 18.4%
slotted ALOHA
- 전제 조건: 모든 노드들이 시간이 synchronized되고, 전체 air time은 같은 사이즈의 하나의 프레임을 전송 가능한 타임슬롯으로 정확하게 나누어짐
- 각 노드들은 데이터를 타임슬롯의 시작 시간에 맞추어 전송
- 충돌이 발생하면 임의로 정한 확률 p에 따라 다음 슬롯에서 전송할 지 말 지 결정
- 데이터 충돌이 중간에 겹치지 않음. 즉 ALOHA에 비해 전체적으로 충돌 확률이 반으로 줄어듦 -> 약 37%
CSMA(Carrier Sense Multiple Access): 전송 전에 반송 주파수(carrier frequency)를 먼저 감지하고 다른 노드의 전송이 없을 때에 전송
- 여전히 충돌은 있음: propagation delay 때문에 전송을 감지 못하고 내가 전송하면 충돌
- CSMA/CD(Collision Detection): 충돌을 감지하는 순간 바로 전송을 중단
- jam signal: 시스템에 약속된 어떤 시그널
- jam signal을 전체 bus에 흘려 모든 노드에게 해당 데이터를 버릴 것을 알림
- 이더넷에서 사용
비교
- 전체 트래픽 로드가 높을 때는 channel partitioning이 좋지만, 낮을 때는 bandwidth 낭비
- 전체 트래픽 로드가 낮을 때는 random access가 좋지만, 높을 때는 충돌 많음
- Taking turn
- 로드가 높을 때: 다 똑같은 기회를 줘서 공정하게 데이터를 보냄
- 로드가 낮을 때: 한 노드에게만 자원 계속 줄 수 있음
- polling, token 등은 control overhead
- single point of failure: 마스터 노드, 토큰을 가진 노드가 고장나면 전체 시스템 마비
댓글남기기