10강 Data Link Control & Medium Access Control

Data link control(DLC), Medium access control(MAC) ⇒ 이건 물리 법칙이 아니라 사람들이 정하는 방식으로 프로토콜을 정의 하는 것 입니다. (표준화 된 동작이 중요)

이번주에는 기본적인 설계철학 설계 원리에 배우도록 하겠습니다.

Link Layer & IEEE 802 Project

여기서 DLC layer는 더 이상 불충분 하거나 쓸모 없어져서 MAC에 흡수되긴 했다.

다만 오늘은 설계 철학을 말하기 위해서 DLC 와 MAC을 모두 설명하도록 하겠다.

• Data link control (DLC) sublayer
• Media access control (MAC) sublayer

• 분배하는 경우는 주로 broadcast links를 말하고 주로 무선에 해당한다.

 

• 실제로는 MAC을 중심으로 흡수된 경우가 많기 때문에 MAC을 기준으로 프로토콜이 정의 되어 있다.
• MAC의 full name medium access control, multiple access control, Media access control

 

IEEE Project 802

미국 방식의 표준화

• Project 802 : 1계층과 2계층을 정의하는 표준이다. (주로 LAN)을 다룬다. (블루투스나 다른 것도 있음)
• Logical Link Control (LLC) : DLC 표준을 다룹니다.
• Media Access Control (MAC) : 시스템별로 다 다르게 정의되어있다. 가장 성공한 표준입니다.

이더넷과 WLAN(와이파이)이 크게 성공했습니다.

WPAN : 블루투스 센서등

이 세개의 표준만 기억하고 있으면 됩니다.

---

Data Link Control :

Data Link Control : Framing, Flow and error control, Retransmission

• 두개의 인접한 노드간 직접 연결되어 통신합니다.
• 가장 중요한 것은 framing and flow and error control을 말합니다.
• physical layer의 bit synchronization이 이미 맞춰져 있다고 가정합니다.
• 데이터 패킷에서 헤더(트레일러)를 붙히는 개념으로 frame으로 만듭니다.
• 프레이밍이란 : 2계층에 해당하는 패킷 포멧을 만들거나 해석합니다.

Frame Size

두가지 종류가 있다.

1. Fixed-size framing :
2. Variable-size framing

요즘은 주로 variable size로 작동을 하는데 그렇다고 fixed가 사용되지 않는 것은 아닙니다.

Character-Oriented (or byte-oriented) Framing

비트 스트림에서 어디부터 어디까지 끊어야 하는 지를 결정해야 하는데 특정 비트 패턴이 나오면 끝겠다고 정의한다. 그 특정 비트 패턴을 flag라고 부른다.

헤더는 FLAG랑 같은 비트 패턴이 발생하지 않습니다.

다만 data 같은 경우 flag와 같은 비트 패턴이 나올 수 있습니다.

프레임의 모든 단위는 한 바이트 단위로 작동합니다. : Character-Oriented

Bit-Oriented Framing

이건 캐릭터 중심이 아니라 임의의 길이로 끊어질 수 있는데 일반적으로 한바이트 단위로 끊어집니다.

따라서 어떤 oriented는 중요하지 않는데 Byte stuffing 인지 Bit Stuffing 인지는 중요합니다.\

Byte stuffing

Flag와 동일한 패턴이 나오거나 ESC와 동일한 패턴이 데이터에 나올 떄 ESC를 한번 더 붙혀줍니다.

Bit stuffing

Bit stuffing같은 경우 0111110 을 Flag 로 둡니다.

여기서 연속으로 1이 5개가 나오는 경우 뒤에 0을 붙혀주는 방식으로 flag와 구분하여 동작 시킵니다.

Flow Control

통신이 빠르고 수신이 느린 경우 천천히 보내라고 할 수 있기 때문에 그것을 flow control이라고 부릅니다.

• Balancing between production and consumption rates
• Feedback from the receiving node to the sending node to stop or slow down pushing frames.

Error Control

• Prevent the receiving node from delivering corrupted packets to its network layer

패킷에 헤더와 tailier를 붙히는데 트레일러에 CRC 값을 붙히고 수신 측에서 CRC 값을 확인해보면 그것이 깨졌는지 안 깨졌는지 확인이 가능합니다.

만약 ACK를 보내면 데이터를 보내는 식으로 동작하면 에러 컨트롤과 flow컨트롤이 동시에 되는 경우도 발생합니다.

Connectionless Protocol

이것은 둘 사이 전용 커넥션이 없기 때문에 패킷이 뒤죽박죽으로 올 수 있기 때문에 패킷넘버가 꼭 필요하다.

이더넷 같은 경우 Connectionless Protocol 이라고 합니다.

Connection-Oriented Protoco

이것은 전용 커넥션이 있어서 패킷이 순서대로 온다고 보면 됩니다.

Retransmission Protocols

에러 컨트롤에서 더 있는 프로토콜

만약 패킷이 깨졌다면 아무것도 안 하고 깨지지 않은 경우 ACK를 보내서 정상적으로 받았다는 것을 알립니다.

• ARQ (Automatic Repeat Request) protocol

송신기 측에서 일정 시간 ACK가 안 오면 패킷이 잘못 갔다고 해석합니다.

finite state machine (FSM)으로 프로토콜을 설정하면 좋습니다.

1. Simple Protocol

송신기가 있고 수신기가 있다면 프레임을 일단 보내면 수신측에서 아무것도 하지 않는 방식으로 동작합니다.

이것은 수신된 패킷이 에러가 났는지 안 났는지 확인할 수가 없습니다.!

2. Stop-and-Wait Protocol

자연스럽게 both flow and error control

• Sender sends one frame at a time and waits for an acknowledgment before sending the next one

• ACK에서 CRC를 보내는 것을 기억하자.
• 타이머가 만료되기 전에 ACK가 도달해야만 다시 Retransmision이 발생하지 않는다.
• FSM예시

• Msg sqeunce diagram

 Sequence and Acknowledgment Numbers

 Ack가 깨졌을 때 같은 패킷이 오기도 하는데 이럴 때 감지를 위해서 squence number가 있습니다.

 일반적으로 Ack는 다음에 받고 싶은 packet 번호를 보내는 경우가 많습니다.

 acknowledgment number는 the sequence number of the next frame to receive로 정의됩니다.

 이 그림은 시퀀스 넘버를 이용해서 패킷 복제 문제를 해결 할 수 있습니다.

Pipelined Retransmission Protocols

1. Go-back-N

TCP에서 동작하는 방법입니다. Retransmission

Ack를 받지 않아도 N개를 보내는 방식입니다. (외상과 비슷한 개념)

이 방식에서 N개의 사이즈를 window size라고 부릅니다.

여기서 ackNo는 가 seqNo 와 같다.

• 슬라이딩 윈도우

Go-back-N 방식 같은 경우 송신측에만 윈도우가 있고 수신측에는 윈도우가 없다.

Go Back N 은 타이머는 하나만 있으면 됩니다.

보낸것에서 가장 마지막으로 보낸 것에 대한 타이머만 가지고 있습니다.

ACK를 받기만 해도 타이머를 restart 시킵니다.

다른 시나리오.

연속적으로 쭈루룩 받은 경우만 정상적으로 받았다고 판단합니다.

즉 겹치는 ACK 를 받았기 때문에 타이머를 재가동 시키지 않습니다.

즉 뭉쳐서 네트워크 계층에 넘겨줄 필요가 없습니다.

• Receiver only sends cumulative ack

2. Selective Repeat

• Receiver sends individual ack for each packet

Selective Repeat receiver에서도 윈도우가 있다.

각각의 Packet 별로 ack를 사용합니다.

알고리즘 측면에서 복잡하지만 통신 측면에서는 효율이 좋다. (깨진 패킷만 재전송)

각각 패킷 별로 타이머가 존재합니다.

여기서 보면 회색은 이미 잘 보낸 것 입니다.

수신 측에서 upper layer 로 보내기 전에 잘 받는 것들만 저장해주고 다 받으면 위로 올려주는 방식으로 동작 합니다.

여기서는 성공한 패킷의 시퀀스 번호를 ACK로 보냅니다.

깨진 패킷만 보내면 되기 때문에 좋습니다.

Piggybacking

• Piggyback : 업다
• 양방향의 경우 데이터를 보낼 때 서로 주고 받을 데이터가 있기 때문에 Ack를 data에 같이 실어서 보냅니다.
• 무선에서는 piggyback을 안 쓰는 경우가 많습니다. (자원을 따로 할당하는 경우)

---

Medium Access Control

• Channel partitioning, Random access, Taking turns

Multiple Access Links, Protocols (MAC)

3GPP : 5G 표준, IEEE 802.11(와이파이 표준) 에서 Medium access control이라는 것으로 표현

media access control protocol or multiple access control라고도 불립니다.

• 링크에는 2가지 종류가 있다.

1. Point-to-point (직접 연결)

 일반적으로 MAC이 필요하지는 않다. 다만 framing등의 과정이 필요하기 때문에 2계층은 여전히 필요하다.

 즉 DLC는 필요하지만 MAC은 필요하다.

 다만 DLC를 MAC이 흡수한 경우가 실제로는 많아서 MAC만 살아있는 경우가 많다.

 Point-to-point link between Ethernet switch, host

1. Broadcast (shared wire or medium)

 과거 이더넷은 버스 토폴로지에 가까웠다.

 Old-fashioned Ethernet, 802.11 wireless LAN

 최신 이더넷은 point to point라고 볼 수도 있다.

 무선은 당연하게도 borad cast 속성을 가지고 있다.

 

 

Mac Protocol 특징

여러 개의 단말을 나눠줄 때 분산방식(Distributed algorithm)으로 하거나 중앙 방식(centralized algorithm)으로 할 수도 있다.

두명 이상이 동시에 자원에 접속할 때 Collision이 발생합니다.

동시에 수신을 할 때 충돌을 반드시 했다기 보다는 간섭때문에 신호가 약해지는 경우도 발생한다. (SNR이 더 중요 ) 다만 이번에는 Collision만 가지고 생각하겠다.

Collision if node receives two or more signals at the same time

채널이 사용 가능 하다는 것을 보내기 위해서 그것 만을 위한 채널 또한 있어야만 한다.

MAC Protocol의 이상

기지국이 단말에 알려주기 위해서 오버헤드가 있기 때문에 어찌보면 분산적인 방식이 가장 이상적이다.

실제 data rate가 100이고 10명이 있는 상황에서 10씩 각자 나눠가지면 이상적이지만 실제로는 8씩 나눠 가지거나 더 심하게 떨어지는 경우도 발생합니다.

• special node가 없는 것이 이상적이다.
• synchronization of clocks, slots 또한 없는 것이 이상적이다.
• 단순 해야한다.

사실 이렇게 이상적인 내용으로 없으면 좋겠는 내용은 전부 실제로 다 있어야 한다.

MAC Protocols: Taxonomy

Channel partitioning : 전용 자원을 할당해주는 방식이다.

• FDMA나 TDMA 같은 방식 같은 경우 전용으로 time Slot을 할당해주는 방식이기 때문에 비어있는 슬롯이 발생하므로, 비효율적이다.
• dedicated

TDMA: time division multiple access

TDMA : time division multiple access

• Each station gets fixed length slot
• Unused slots go idle

FDMA: frequency division multiple access

FDMA: frequency division multiple access

사실 주파수로 나누는 것만 차이가 있고 TDMA랑 거의 비슷해서 똑같이 낭비가 발생한다.

CDMA (code division multiple access), SDMA (space division multiple access) 역시 같이 낭비가 발생한다.

Random access

랜덤하게 보내고 distributed(분산) 방식이다.

오늘 배우는 방식은 full distriduted만 배웁니다.

두개 이상의 송신이 있는 경우 collision이 발생합니다.

Random access 같은 경우 어떻게 collision을 감지하냐면 순수하게 수신해야 하는 에너지 레벨보다 더 높으면 collision이 발생한 것이다. (특히 유선)

random access MAC protocols의 대표예시 :

(Pure) ALOHA,

Slotted ALOHA : 전화를 걸 때 채널을 할당해주는 것은 비효율적이니까, 처음에는 랜덤으로 찾습니다. (현재 이동통신에서 사용)

CSMA, CSMA/CD, CSMA/CA (과거 이더넷에서 사용하는 방식, 이것 때문에 MAC이 생겼다., 현재 사용하고 있는 와이파이 프로토콜이다.)

ALOHA

무선으로 보내는 프로토콜이다. (1970년에 등장)

단순한 프로토콜로 보낼 패킷이 있으면 무조건 보내고 패킷 사이즈를 한정짓는다.

첫번째 슬롯은 콜리전이 없고 두번째는 콜리전이 나는데 콜리전이 난 경우 backoff를 시도하는데 이것은 랜덤한 시간만큼 쉬는 것을 의미합니다. (그 시간이 window 크기 사이에서 뽑아낸 값이다.)

즉 이렇게 하면 송신 시점을 분산 시킬 수 있다.

만약 충돌이 날때마다 2배로 window 사이즈를 늘립니다.

이 그림에서 wait을 보면 보낼 때 propagation delay 의 최소 2배 이상이어야만 하는 이유는 보낼 때 한번 받을 떄 한번 보내기 때문이다.

해당 그림에서 왼쪽 부분이 Backoff과정이다. (Ack 가 수신되지 않은 상황)

0과 window 사이즈 사이 값으로 랜덤하게 선택해서 2의 배수로 기다립니다.

• Pure Aloha 성능 분석

 Frame이 앞이나 뒤에 살짝 겹치는 경우 에러가 발생합니다.

 즉 Frame이 앞이나 뒤에 겹치지 않게 길이를 설정해줘야만 패킷에 충돌이 발생하지 않습니다.

 이런 시간을 Vulnerable time이라고 부릅니다.

Bernoulli Process (동전 던지기)

복권, 주식 ,은행 도착시간, 서버 도달 등 ⇒ 베르누이 프로세스라고 합니다.

Poisson Process

베르누이 프로세스에 극한을 취한 것

이전의 결과가 다음 결과에 영향을 주지 않고 절대적으로 똑같이 도착하는 상황은 발생하지 않는다. 특정 순간에서는 무조건 하나만 나온다.

throughput : 한 타임 슬롯당 송신이 성공하는 패킷의 갯수

여러개의 단말중에서 보낼 패킷이 있는 단말의 비율이 arival rate라고 볼 수 있다.

• 공식 중요

Example

200-bit frames on a shared channel of 200 kbps로 보내게 되면

1프레임의 길이가 1ms가 나오고 ( 200bit / 200kbps) 꽉 채워서 보내게 되면 1초에 1000개의 프레임을 보낼 수 있다.

만약 1000개 프로레임이 발생하면 오퍼드 로드가 1

500개면 오퍼드로드가 1/2이고, 250개이면 오퍼드 로드가 1/4이다.

이 3개를 아까 위의 공식인 G* e ^-2G에 대입해주는 것입니다.

Slotted ALOHA

이건 타임 슬롯을 딱 정해놓는다.

패킷이 valunable time 이 T라는 특징이 있다.

G가 1일때 최대값을 가진다.

Carrier sense multiple access (CSMA)

이건 보낼 께 있을 때 바로 보내는 것이 아니라, 보내기 전에 네트워크에 보내고 있는게 있는지 먼저 체크를 한다.

즉 캐리어 센싱을 한다고 볼 수 있다.

보내고 싶은데 이미 에너지가 디텍션 되는 경우 보내기를 포기한다.

다만 이것도 콜리전이 존재한다.

만약 B가 보냈는데 아직 B신호가 도착하지 않았으면 충돌이 발생하기 때문에, Propagation Delay만큼 vulnerable time이 됩니다. (큰 단점)

CSMA/CD

송신 도중에 충돌이 발견되서 송신을 중간에 중지시킵니다.

초창기 이더넷에서 사용했던 방식입니다.

Carrier sense multiple access with collision avoidance (CSMA/CA)

한번 더 확인하고 보내는 방식이다. 즉 carrier sensiong을 소극적으로 피하는 방식입니다.

와이파이가 사용하는 방식입니다.

Taking turns :

Polling

Taking turns” MAC protocols 같은 경우 마스터가 보낼게 있는지 확인하는 과정을 거칩니다.

일일이 물어봐야기 때문에

 Polling overhead

 Latency

 Single point of failure (master

Token passing

• Token overhead
• Latency
• Single point of failure (token)