5. 링크 계층 1

6.1 링크 계층 소개

용어 설명

• 노드: 링크 계층 프로토콜을 실행하는 장치. (호스트, 라우터, 스위치, Wifi AP)
• 링크: 통신 경로상의 인접한 노드들을 연결하는 통신 채널.
• 링크 계층 프레임: 한 링크의 노드에서 전송 받은 패킷을 링크 계층 프로토콜로 캡슐화 한 링크 계층의 데이터 단위.

 

링크 계층이 제공하는 서비스

• 프레임화: 네트워크 계층 패킷을 링크상으로 전송하기 전에 링크 계층 프레임에 캡슐화 함.
• 링크 접속: MAC(medium access control, 매체 접속 제어) 프로토콜은 링크상으로 접속하는 프레임을 전송하는 규칙에 대해서 명시함.
• 신뢰적 전달: 신뢰적 전달 서비스 제공.
• 오류 검출과 정정: 신호의 약화나 전자기 잡음으로 인한 비트 오류가 생길 수 있으며, 이러한 오류를 검출하는 방법을 제공함.

 

링크 계층이 구현되는 위치

• 링크 계층은 네트워크 인터페이스 카드(network interface card, NIC)로 알려진 네트워크 어댑터(network adapter)에 구현됨.
• 네트워크 어댑터의 중심에는 링크 계층 제어기가 있으며, 링크 계층 제어기는 링크 계층 서비스들(프레임화, 링크 접속, 오류 검출 등) 대다수가 구현되어 있는 단일의 특수 용도 칩임.
• 따라서 링크 계층 제어기의 기능 대부분은 하드웨어로 구성됨.

 

6.3 다중 접속 링크와 프로토콜

링크의 종류

• 점대점 링크point-to-point link: 링크의 한쪽 끝에 한 송신자와 다른 쪽 끝에 한 수신자가 있음.
• 브로드캐스트 링크broadcast link: 동일한 하나의 공유된 브로드캐스트 채널에 다수의 송신 노드 및 수신 노드들이 연결됨.
  • 다중 접속 문제multiple access problem 발생
    
    • 2개 이상의 노드가 동시에 프레임을 전송할 경우, 모든 노드는 동시에 여러 개의 프레임을 받게 되는 충돌collide 현상이 발생함.
    • 충돌로 인해서 수신 노드는 전송된 프레임의 의미를 파악할 수 없게 됨.
    • 충돌에 관련된 모든 프레임은 손실되며 브로드캐스트 채널은 충돌기간 만큼 낭비됨.
• 브로드캐스트 채널로 보내는 노드들의 전송을 조정하기 위한 MAC(multiple access prtocolm, 다중 접속 프로토콜)을 사용.
  
  • MAC 프로토콜의 종류
    • 채널 분할 프로토콜channel partitioning protocol
    • 랜덤 접속 프로토콜random access protocol
    • 순번 프로토콜taking-turns protocol

 

채널 분할 프로토콜

 

시간 분할 프로토콜TDM

• 각 시간 프레임을 N개의 시간 슬롯으로 나누어 N개의 노드에게 각각 할당함.
• 노드는 전송할 패킷이 있을 때마다 TDM 프레임에서 자신에게 할당된 시간 슬롯 동안 패킷 비트 전송.
  • 장점: 충돌 제거 가능, 공정함.
  • 단점: 전송할 패킷이 단 하나인 경우에도 전송률이 평균 R(채널 전송률)/Nbps임.

 

채널 분할 프로토콜FDM

• R bps의 채널을 다른 주파수로 나눠서(각 R/N의 대역폭을 갖게 됨) 각 주파수를 N개 노드 중 하나에게 할당함. 
• 모든 노드들은 항상 프레임 전송 가능.
  
  • 장점: 충돌 제거 가능, 공정함.
  • 단점: 전송할 패킷이 단 하나인 경우에도 R/N 대역폭으로 한정됨.

 

랜덤 접속 프로토콜

• 랜덤 접속 프로토콜에서 전송 노드는 항상 채널의 최대 전송률인 Rbps로 전송함.
• 충돌이 생기면 충돌과 관련된 각 노드는 프레임이 충돌 없이 전송될 때 까지 자신의 프레임을 계속해서 재전송함.
• 충돌했을 때 즉시 재전송하는 것이 아니라 그 프레임을 재전송하기 전에 랜덤 지연 시간 동안 기다림.
• 가장 일반적인 프로토콜의 종류
  
  • 알로하 프로토콜
  • CSMA 프로토콜

 

CSMA 프로토콜Carrier Sense Multiple Access

• CSMA 프로토콜의 두가지 규칙
  1. 말하기 전에 듣는다 : 만일 다른 노드가 프레임을 채널에 전송하고 있으면, 노드는 임의의 짧은 시간 동안 전송 중단을 감지하면 프레임 전송하기 시작함.
  2. 다른 사람이 동시에 말하기 시작하면 말을 중단한다 (충돌 검출, collision detection): 만일 다른 노드가 방해 프레임을 전송하고 있음을 검출하면, 자신의 전송을 중단하고 랜덤 시간 동안 기다린 후 유휴 시 감지 및 전송 과정을 반복함.

• 채널 전파 지연propagation delay으로 인한 충돌이 발생할 수 있음.
  • 위 그림에서 노드 B가 보낸 전파가 노드 D에게 전달되는 시간동안 생긴 propagation delay로 인해 충돌이 발생함.
  • propagation delay가 CSMA의 성능을 결정하는 중요한 역할을 함.

 

CSMA/CD(Carrier Sense Multiple Access with Collision Detection)

• 다른 부분은 CSMA와 동일하고, 충돌을 검출 했을 경우 두 노드가 바로 자신의 전송을 취소함.
• 전송을 취소한 후 임의의 랜덤 시간 만큼 기다린 후 유휴 시 감지 및 전송 과정을 반복함.
• 랜덤 시간은 노드가 많을 경우는 시간 간격을 크게 잡는 것이 좋고, 노드가 적을 경우는 시간 간격을 작게 잡는 것이 좋음.
• 랜덤 시간은 이진 지수적 백오프binary exponential backoff 알고리즘을 사용함.
  • 충돌을 n번 경험한 프레임을 경험한 노드는 {0, 1, 2, ... 2^n-1} 중에서 랜덤하게 K값을 선택함.
  • 충돌을 한번 경험한 경우 {0,1} 중에서 K값을 랜덤하게 선택하여 K시간만큼 기다린 후 재전송함.
  • 충돌을 두번 경험한 경우 {0,1, 2, 2^2} 중에서 K값을 랜덤하게 선택하여 K시간만큼 기다린 후 재전송함.
  • 충돌을 10번 경험한 경우 {0,1, 2, ... 2^9} 중에서 K값을 랜덤하게 선택하여 K시간만큼 기다린 후 재전송함.
  • 따라서 프레임이 충돌을 더 많이 경험할수록 K를 선택할 간격을 크게 함.

 

순번 프로토콜

폴링 프로토콜polling protocol

• 노드 중 하나를 마스터 노드로 정함.
• 마스터 노드는 각 노드를 라운드 로빈 방식으로 폴링함.
• 폴링
  • 마스터 노드는 노드 1에게 노드 1이 최대로 보낼 수는 프레임 수에 대한 정보를 지닌 메시지 전송.
  • 노드 1이 프레임을 보낸 다음에 노드 2에게 노드 2가 최대로 보낼 수는 프레임 수에 대한 정보를 지닌 메시지 전송.
  • 이러한 방식으로 순환적으로 각 노드를 폴링함.
• 장점: 랜덤 접속 프로토콜의 단점인 빈 슬롯을 제거함.
• 단점: 마스터 노드가 고장나면 전체 채널이 동작하지 못함.

 

토큰 전달 프로토콜token-passing-procotol

• 마스터 노드가 없고 토큰이라고 알려진 작은 특수 목적 프레임이 정해진 순서대로 노드 간에 전달됨.
  • 노드 1 토큰 전달  -> 노드 2 토큰 전달  -> 노드 3 토큰 전달 .. 
• 노드가 토큰을 수신하면 전송할 프레임이 있는 경우 토큰을 붙잡고 프레임을 최대 개수까지 전송한 뒤 다음 노드로 토큰 전달.
• 그렇지 않은 경우 토큰을 즉시 다음 노드로 전달.
• 장점: 분산 방식이며 효율이 높음
• 단점: 노드 하나가 토큰 전달에 실패하면 전체 채널이 동작하지 않음.