[Computer Networks] L02 MAC

• toc {:toc}

Notice

Computer Networks 글은 경희대학교 소프트웨어융합대학 이성원 교수님의 [컴퓨터 네트워크 CSE302] 수업을 기반으로 정리한 내용입니다.

MAC(Multiple-Access Protocols) Overview

Random Access Protocols

Point

대등 관계. 내가 전송할 데이터가 있으면 다른 요소, 상황 고려하지 않고 전송!

• Station간의 우열이 존재하지 않고 조종되지 않는다.
• 전송은 medium의 상태에 따라 결정된다.
• 다른 station들의 상황을 고려하지 않기 때문에 충돌이 발생한다.

ALOHA

• 1970s 초반, 하와이에 많은 섬들끼리 날씨 정보 등 소량의 정보를 통신하기 위해 개발되었다.
• Random access protocol을 사용하기에 충돌이 필연적으로 발생한다.
• Medium은 station들끼리 공유되고, 동시에 데이터를 전송하면 충돌이 발생한다.

노란 박스가 쳐져 있는 부분은 여러 station들에서 동시에 데이터를 전송한 상태이기 때문에 데이터가 함께 붕괴되어 훼손된다.

• Procedure

1. Station이 보낼 프레임을 갖는다.
2. 프레임을 보내고 일정 시간 기다린다.
3. ACK를 받았으면 전송이 잘 완료된 것. ACK를 받지 않은 경우 일정 시간 기다렸다가 재전송
4. 만약 max 회 보냈는데도 ACK를 받지 않는 경우 전송을 중단한다.

Slotted ALOHA

• 시간을 시작지점과 끝지점을 설정한 여러 슬롯으로 나누어 슬롯 안에서만 전송할 수 있도록 한다.
• ALOHA와 동일하게 충돌이 발생할 수 있으나, 슬롯 안에서만 겹친다.
• 시간적으로 동기화가 정확히 이루어져야 하나, 동기화가 힘들다는 부분에서도 완벽히 작동되지 않는다.

CSMA(Carrier Sense Multiple Access)

• 충돌을 최소화하고 성능을 증가시키기 위해 고안되었다.
• Station이 데이터를 전송하기 전에 medium의 상태를 확인하고 전송한다.
• 기본적으로 “Sense before transmit”, “Listen before talk” 원칙을 적용한다.

• 데이터를 전송하면 이동하는 시간으로 인한 propagation time(=vulnerable time, =delay time)을 사선으로 표시했다고 생각하면 된다.

• Figure explaination

1. B가 t1에 먼저 medium이 비어있다는 것을 확인하고 전송한다.
2. C는 t2에 medium이 비어있는 것을 확인하고 데이터를 전송한다.
3. B의 데이터 전송 딜레이로 인해 C의 전송 이후 도착하면서 두 데이터가 겹치게 된다.
4. 겹친 회색 부분의 데이터는 붕괴된다.

• 데이터를 일단 전송하면 medium sensing을 하지 않기 때문에 위와 같은 경우가 발생한다.

Behavior of three persistence methods

1-persistent

• 끊입없이 sensing하다가 비어있는 상태가 되면 전송한다.
• 전력 사용이 많다.
• Delay가 발생하지 않는다.
• 바로 전송할 경우 충돌 확률이 높아진다.

Nonpersistent

• 일정 시간만큼 간격을 두고 sensing하다가 비어있는 경우 전송한다.
• 전력 소모량이 적다.
• Delay가 발생한다.

p-persistent

• p는 확률을 의미한다.
• 끊임없이 Sensing하다가 비어있는 상황에서 랜덤값 R을 추출하고 R<p인 경우 전송한다.
• R<p를 만족하지 않는 경우 다른 곳에서 보내고 있는지 확인하고 보내고 있다면(중간에 Busy 상태) 현재 보내려는 시도가 많다고 파악해 충돌이 발생하지 않아도 backoff 하여 전송하지 않는다.

CSMA/CD(Collision Detection)

• CSMA 방식은 충돌에 따른 방식을 명시하지 않았기에 충돌 탐지를 추가로 고안했다.

• Station이 medium을 전송하기 전 + 전송 후를 계속해서 sensing 한다.

• 만약 전송 중 충돌이 발생한다면 전송을 중단하고 프레임을 다시 전송한다.

• Procedure

1. Station이 보낼 프레임을 갖는다.
2. Persistent method 중 하나를 적용해 전송한다.
3. 전송 중 충돌이 발생했는지, 전송 후 전달 과정에서 충돌이 발생했는지를 확인한다. (둘 다 충돌이 없어야 완료된다.)
4. 충돌이 발생했다면 충돌이 발생했음을 알려주는 jamming 신호를 보낸다.
5. 랜덤 시간동안 기다리고 다시 프레임을 전송한다.
6. max번 시도했지만 전송되지 않는다면 전송을 중단한다.

CSMA/CA(Collision Avoidance)

• 무선 네트워크를 위해 고안되었다.
• Collision Avoidance는 Inter-frame space, Contention window, Acknowledgment 3가지 방식을 통해 구현된다.
• Collision Avoidance는 반드시 에러가 발생함을 시사한다.

• RTS(Request to send) : Sender가 데이터를 전송하겠다는 사전 신호이다.
• CTS(Clear to send) : Receiver가 데이터를 송신해도 된다고 보내는 신호이다.
  • CTS를 sender에게 보낼 때 주변 다른 station들에게도 CTS를 전송하는데, sender에게 데이터를 전송받는 동안 다른 station들에게는 데이터를 전송받지 않겠다는 의미이다.
  • 다른 station들이 CTS를 놓치는 경우 데이터를 receiver에게 전송해 에러가 발생할 수 있다.
• ACK(Acknowledgment) : 데이터를 잘 받았다는 메시지이다.

Contention Window, Inter-Frame Space

• 조금 더 충돌을 줄여보기 위해 사용한다.
• 끊임없이 sensing하다가 사용 가능할 때 일정 시간(inter-frame space) 대기하고 binary exponential 크기의 contention window에 따라 전송한다.

Hidden station problem

1. Station B와 C는 서로의 영역에 겹치는 부분이 적어 CTS를 놓치는 문제가 발생한다.
2. Station B와 C가 가려져 있는 경우 서로 통신이 잘 이루어지지 않는 문제가 발생한다.

cf) B에서의 데이터 전송이 A와 연결을 통해 C로 전달된다. 유선의 경우 줄이 중심으로 줄에 의해 통제되어 C는 A가 사용되고 있음을 인지할 수 있다. 사용되고 있다면 기다렸다가 전송하는 등의 방식을 사용할 수 있다. 하지만 무선의 경우 각 디바이스가 중심이 되고, B가 A로 데이터를 전송할 때 C의 입장에서는 A가 정보를 전달 받고 있다고 인지하지 못해 A로 정보를 전송해 데이터 간섭이 발생한다.

• Procedure

1. Station이 보낼 프레임을 갖는다.
2. 채널이 비어있는지를 확인한다.
3. Inter-frame sequence(IFS) 동안 기다린다.
4. 0부터 사이의 랜덤값 R을 고르고 R번째 슬롯을 사용한다. (Contention Window)
5. RTS(Request to send)를 보내고 타이머를 세팅한다.
6. 타이머가 다 지나기 전에 CTS(Clear to send)를 받았는지 확인한다.
7. CTS를 받았다면 IFS 동안 기다리고 프레임을 전송하고 타이머를 세팅한다.
8. 타이머가 다 지나기 전에 ACK를 받는다면 성공
9. 6번에서 CTS, 8번에서 ACK를 받지 않는다면 일정시간 대기했다가 2번으로 돌아가 재전송을 시도한다.

Controlled Access Protocols

Point

Station들이 하나의 통제를 받아 전송 권한을 갖는다. 권한이 없다면 보낼 수 없다!

Reservation

• 데이터를 보내기 전에 예약을 해야 보낼 수 있다.
• Station 개수만큼 슬롯이 나누어져 예약하고 예약된 station 순서대로 프레임을 전송한다.
• 예약이 되어 있기 때문에 충돌이 발생하지 않는다.

Polling

• Primary station이 지정되어 있고, 나머지 디바이스들은 secondary station이다.
• 모든 데이터 전송은 primary station을 반드시 지나서 전송된다.
• Primary station이 링크를 조절하고 secondary station은 명령을 따라야 한다.

• Primary station이 특정 디바이스에 전송할 때는 SEL 프레임을 전생하고 ACK를 받아 수신할 준비가 되었는지 여부를 확인 후, 데이터를 전송한다.
• Primary station이 각 디바이스에 전송할 정보가 있는지 차례로 질문하고 전송할 정보가 없다면 NAK, 있다면 데이터를 보낸다.

Token Passing

• Token passing 방법은 네트워크 station이 논리적인 ring으로 구성되어 있다.
• Station들에 대해 predecessor(선행) station, successor(후행) station이 존재한다.
• 각 station이 일정 시간 마다 토큰을 전달해주는데 토큰을 가지고 있는 경우 채널에 접근하고 데이터를 보낼 수 있는 권한이 부여된다.
• 전송할 데이터가 없다면 토근을 해제하여 다음 station으로 전달한다.

• Physical ring : 단방향 연결이기 때문에 인접한 두 station 사이의 연결이 끊어지면 전체 시스템이 영향받는다.
• Dual ring : 메인 링을 사용하다가 장애가 발생하면 보조 링을 사용한다.
• Bus ring : Station이 단일 케이블에 연결되어 있고, 후속 station의 주소를 알고 있어 토큰을 전달한다.
• Star ring : 커넥터 역할을 하는 허브가 존재해 서로 충돌하지 않고 하나가 끊어져도 다른 station들이 영향받지 않아 안정적이다.

Channelization Protocols

Point

다양한 station들 사이에서 주파수 혹은 코드를 통해 물리적 채널을 나누어 동시에 접근할 수 있도록 한다!

FDMA(Frequency-Division Multiple Access)

• 주파수 대역폭에서 이용가능한 대역폭을 각 station마다 나누어 사용한다. ex) 아날로그 TV
• 각 station은 데이터를 보내는 대역폭을 할당 받는다. 언제나 속해있어 시간에 관계없이 전송 가능
• 각 station은 bandpass filter를 사용해 전송 주파수를 제한한다.

• 동일 시간에 전송하더라도 주파수 대역폭 자체가 다르기 때문에 서로 간섭없이 데이터를 전송할 수 있다.

• 트래픽이 균일하고 일정할 때 효율적이다.

• 알고리즘이 간단하고 복잡성이 적다.

• 채널달 최대 사용량이 고정되고 작다.

TDMA(Time-Division Multiple Access)

• Station들은 동일한 주파수 대역폭을 시간 슬롯 만큼 할당 받아 데이터를 전송한다.
• 각 station은 데이터를 할당된 슬롯안에서만 전송할 수 있다.
• 전화 통화의 경우 FDMA 시에는 주파수 단위로 나누기 때문에 누군가 사용하고 있다고 하면 해당 주파수 대역을 사용할 수 없다. 하지만 통화시에 항상 말하는 것은 아니기 때문에 말하지 않는 중간 중간을 슬롯으로 할당하여 말하지 않는 경우 다른 사람이 사용 가능하도록 만든다.

• 각 사용자의 신호를 서로 다른 시간 슬롯으로 나누고 각 시간 슬롯을 서로 다른 사용자에게 할당한다.
• 채널의 데이터 전송 속도가 빨라지면서 압축된 데이터를 보내고 receiver가 압축을 해제하여 데이터를 복원한다.
• 2세대 이동통신에서 사용했다.

CDMA(Code-Division Multiple Access)

• 최근 전기 기술의 발전으로 구현 가능해졌다.
• FDMA와 다르게 오직 하나의 채널만 사용한다. 하나의 채널이 전체 대역폭을 점유한다.
• TDMA와 다르게 동시에 데이터를 보낼 수 있다. 시간을 쪼개 나누지 않는다.
• 군 암호화 목적으로 처음 개발되었지만 확대되어 3세대 이동통신에서 사용됐다.

• 4개의 노드가 데이터를 보낸다고 가정

  • c : 노드에 배정된 코드
  • d : 보내려는 데이터 (0 or 1)

• 노드별로 코드가 배정되는데 코드는 다음의 특징을 갖는다.

  • (노드의 수)

• 데이터를 보낼 때 데이터와 코드를 곱한다.

• 각 노드에서 곱한 결과물을 모두 더한 값을 채널을 통해 전송한다.

• Receiver가 데이터를 받으면 sender의 코드를 곱하고 노드의 수로 나눈다.

• 노드1 : 0 전송
• 노드2 : 0 전송
• 노드3 : Silence
• 노드4 : 1 전송

데이터와 각 코드와 내적해서 노드 수로 나누면

• 노드1 : (-1 -1 -3 +1) / 4 = -1 ⇒ 0
• 노드2 : (-1 +1 -3 -1) / 4 = -1 ⇒ 0
• 노드3 : (-1 -1 +3 -1) / 4 = 0 ⇒ Silence
• 노드4 : (-1 +1 +3 +1) / 4 = 1 ⇒ 1

참고문헌

• Textbook: Behrouz A. Forouzan, “Data Communications and Networking, 5th Edition”, McGraw-Hill Companies, Inc.

연결문서

• 다음 노트 - 2023-10-02-ComNet-L03-DLC
• 이전 노트 - 2023-10-02-ComNet-L02-Basic