[네트워크] 링크 계층 (1) 서비스 / EDC / MAP 다중 접속 프로토콜

링크 계층 (Link Layer )

• 노드: 네트워크에 소속된 전송 대상이 되는 호스트, 라우터, 서버 등등
• 링크: 두 인접한 노드 사이를 연결하는 통신 채널
• 프레임: 링크 계층 패킷 단위, 네트워크 계층에서의 데이터 그램을 캡슐화한 것 혹은 물리 계층으로 부터 수신받은 프레임

- 기본 기능

• 링크를 통한 한 노드에서 다른 노드로의 데이터 그램을 전송
• 비트 오류 처리 bit error handling
• 패킷 충돌 처리 packet collision handling

링크 계층

- 링크 계층 서비스

캡슐화: Ethernet 프로토콜과 같은 전송 기술로 헤더를 앞에, 비트 오류 검사를 위한 트레일러를 뒤에 추가하여 데이터 그램을 프레임으로 캡슐화한다.

역캡슐화: MAC 주소를 조사하여 목적지 MAC 주소를 변경하거나 수신받은 프레임의 데이터 오류를 검사하고 오류가 있을 시 자체적으로 비트를 수정하는 기능을 제공한다. 

• Channel Acccess : 서로 다른 노드들이 통신 채널을 공유할 때 어떻게 순서를 정하고 누가 먼저 전송할 지 결정
• Flow Control: 노드 사이에서 전송 속도를 조절
• Error Detection: 물리적 신호 잡음에 의한 error bit 감지, 송신자에게 재전송을 요청하거나 패킷을 버림
• Error Correction:  오류를 감지했을 때 자체적으로 error bit를 수정하여 데이터 정상화

- 링크 통신

• Sender Side: 캡슐화, 오류 확인용 비트를 추가, flow control
• Receiving Side: 역캡슐화, 에러 비트를 확인, flow control

Error Detection and Correction

EDC: Error detection and correction bits (데이터 그램에 추가되는 비트)

EDC

1) 기존 데이터 비트 D에 EDC용 비트가 추가

2) 수신된 데이터 비트 D'에 EDC'를 이용하여 오류가 있는지 검사

3) 오류가 있을 시 수정을 하거나 그런 기능이 없을 시 재전송 요청/패킷 버림

 

Error Detction

- Parity Checking

• Single bit parity: data 비트 열에 에러 유무만 감지
• 전체 비트 열 중 1의 갯수를 짝수로 맞추기 위해 1 parity bit를 추가
• Two-dimensional bit parity: 오류 유무뿐만아니라 해당 비트 위치에 대한 수정이 가능
• 각 행과 열이 모두 1의 갯수에 대한 parity bit가 유효한 지 검사

- CRC Cyclic Redundancy Check

CRC

가장 많이 쓰이며 오류 감지에 효과적이나 오류 수정 기능은 없다.

• D: d bits로 이루어진 원본 데이터 비트 열
• R: r bits로 이루어져 오류 확인을 위해 기존 D 뒤에 추가된 비트
• G: r+1 bit 패턴으로 송신자와 수신자가 오류 확인을 위해 약속한 비트

- 규칙

<D, R> 비트 열을 G로 나누었을 때 정확히 나누어 떨어지도록 CRC 비트 R을 구성한다.

• -> $D*2^r XOR R = nG$
• -> $D*2^r=nG XOR R$
• -> $R = remainder[{D*2^r}/G]$
• 수신 호스트는 프레임에서 약속된 G를 이용하여 실제로 <D,R>에 대한 나머지가 0인지 검사한다.

 

Error Correction

- Forward Error Correction (FEC) or channel coding

• 노이즈가 있는 통신 환경에서 오류를 제어하는 기술

- Codeword

• Forward Error Correction를 위한 코드 블록 정의

Codeword

• k: Length of Data
• n: Length of Codeword
• Redundancy = (n-k)/k = #parity bits/#message bits
• Code Rate = k/n = 실제 데이터 비율

- Hamming code

Data block	Codeword
00	00000
01	00111
10	11001
11	11110

- 00100 패턴의 codeword를 수신하였을 때

1. hamming distance d(v1,v2)를 계산하여 가장 가까운 codeword를 올바른 것으로 선택한다.
2. d(00000, 00100) = 1, d(00111, 00100) = 2, d(11001, 00100) = 4, d(11110, 00100) = 3
3. 따라서 가장 가까운 codeword인 00000으로 수정한다.
4. Code word 패턴 쌍 사이의 거리가 충분히 길고 오류 비트가 있을 시 가장 가까운 codeword가 유일해야한다.

다중 접속 프로토콜 MAP (Multiple Access Protocol)

- Point-to-pont

• Ethernet 스위치와 호스트 사이를 연결하는 point-to-point 링크
• 하나의 통신 채널을 사용

- Broadcast via shared medium

• 여러 호스트가 통신 채널을 공유하는 경우
• old-fashioned Ethernet
• 802.11 wireless LAN
• 위성 통신
• Multiple Access 기술이 필요

- 이상적인 다중 접속 프로토콜을 위한 조건

만약 R bps로 전송이 가능한 broadcast용 채널이 있을 때,

1. 한 노드만 전송할 시 전송률은 R bps를 유지한다.
2. M 노드가 전송할 시 각 노드는 공평하게 R/M bps를 가지도록 한다.
3. 분산 작업으로 추가 동기화 작업이나 조율을 담당하는 노드가 필요 없게 한다.
4. 간단한 구조로 구현한다.

Mutliple Access Protocol 유형

• Channel partioning: 채널을 작은 조각 단위로 분리 (time slots, frequency, code), 충돌 가능성이 없다.
• Taking turns: 호스트 별로 전송 순서를 정함, 충돌 가능성 없다.
• Random access: 채널을 나누지 않고 무작위 순서로 전송, 충돌을 허용하나 충돌으로부터 복귀를 구현해야한다.

Channel Partitioning

- FDMA (Frequency Division Multiple Access)

• 주파수 대역을 분리하여 채널을 할당.

- TDMA (Time Domain Multiple Access)

• n개의 time slot으로 구성된 frame으로 나누고 각 채널을 time slot에 할당.

- CDMA (Code Division Multiple Access)

• 각 채널을 서로 다른 코드로 인코딩 되어 전송
• 수신자는 데이터 디코딩을 위해 인코딩을 위해 사용된 코드를 알고 있어야함.

Taking Turns

- Polling

• Master/Slave 호스트로 구성된 네트워크에서 Master가 Slave에 각각 전송할 순서를 부여함.

- Token Passing

• 한 노드에서 다른 노드로 전송할 권리를 갖는 토큰을 전달.

MAC protocols with Random Access Protocols

- 한 노드에서 전송할 경우

• 모든 채널이 R bps 전송률을 가질 수 있음, 노드 사이의 사전적 조율이 필요없음.

- 두 노드 이상에서 전송할 경우

• 동시 전송에 의한 충돌 가능성이 있음.

-> 어떻게 충돌을 감지 할 것 인가

-> 충돌로 부터 어떻게 복구 할 것인가 (재전송 요청 등)

ex) ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA/CA

 

- ALOHAnet

1971년에 University of Hawaii에서 개발

	Pure ALOHA	Slotted ALOHA
특징	모든 프레임은 같은 길이를 가짐 프레임이 전송 준비 완료시 즉시 전송 시작 충돌 발생시, 해당 노드는 무작위 시간 경과 후 재전송을 시도	노드는 동기화되어 timeslot의 시작지점 부터 전송을 시작할 수 있음 모든 timeslot은 같은 크기를 가짐 충돌 발생시, 다음 slot에서 p 확률로 재전송을 시도
단점	[$t_0, t_0+1$] timeslot에 전송되는 node $i$ 프레임이 인접 timeslot에 전송되는 다른 프레임에 의해 충돌가능성이 큼 최대 전송 효율: 18%	Pure ALOHA에 비해 충돌 확률이 반으로 줄음 최대 전송 효율: 37% (두 배)

 

- CSMA (Carrer Sense Multiple Access)

기존 Slotted ALOHA의 문제점

-> 각 노드들이 다른 노드가 전송 중 인 것을 신경쓰지 않는 문제로 충돌 일어날 가능성이 높다.

 

- CSMA 특징

-> 전송 전에 채널에 대한 listen을 수행

1. 채널이 유휴 상태일 경우 완전한 프레임을 전송
2. 채널이 점유 상태일 경우 전송을 연기함

하지만 충돌은 여전히 존재했는데, 장거리 통신의 경우 propagation delay에 의해 긴 지연 시간이 발생한다. 따라서 두 노드 사이에서 전송 중인 채널이 존재한다는 사실을 listen을 통해 알게될 때까지 오랜 시간이 걸린다.

 

- CSMA/CD (Collision Detection)

• 유선 LAN을 사용하는 경유 통신 채널에서 신호 세기나 전송/수신된 신호들을 분석하여 충돌 감지를 미리 할 수 있다.
• 무선 LAN은 주변 환경에 따라 신호 세기가 영향을 받아 어렵다.
• 충돌을 감지하는 순간 전송을 중단하고 모든 공유 채널을 통해 충돌 사실을 알린다.

- 이미지 출처 및 참고자료 : wiki.ucalgary.ca/page/Courses/Computer_Science/CPSC_441.W2014/Chapter_5:_Link_Layer.html