teawon

공부 & 개발 내용 기록 블로그

(본 글은 “컴퓨터 네트워킹 하향식 접근” 도서 및 네트워크 프로그래밍 수업 내용을 정리한 글 입니다.)

6. 링크계층

6.1.1 링크 계층 소개

노드 : 호스트와 라우터

링크 : 인접한 노드들을 연결하는 통신채널 (무선, 유선 , LASs)

  • 링크에서는 각 패킷을 프레임으로 캡슐화한다 (세그먼트 → 데이터그램 → 프레임)
    • 송신측이 데이터그램을 받으면 헤더를 붙여 프레임화
    • 수신측에서는 헤더의 내용을 보고 오류를 찾아 정정 후 문제가 없다면 데이터 그램을 추출해 네트워크 계층으로 올림

  • 링크 계층은 하나의 노드로부터 물리적으로 연결된 인접노드로 데이터를 전달해주는 책임을 가진다

  • 각 Frame은 서로다른 링크상에서 다른 링크프로토콜을 통해 전달된다
    • 각 링크 프로토콜은 서로 다른 서비스 제공
    • 노트북 A → 무선통신 (LTE 이동통신기술 사용) → 기지국 → 이더넷 기술 → …. 라우터와 라우터는 광.. (즉 채널자체도 다르고 링크 프로토콜이 각각 다름)

6.1.2 링크계층의 서비스

  • 프레임화 : 데이터그램을 받으면 헤더에 하드웨어주소(MAC주소)를 붙인다
    • 결국 이 MAC주소를 보고 자기가 받을지 버릴지 결정하는 것
  • MAC프로토콜 : 링크상에서 프레임을 전송할 때 따르는 효율적인 전송규칙의 프로토콜을 일컫는 표현
    • ex) CSMA/CD
    • 공유 링크상의 접속을 제어한다 (충돌문제도 관리)
  • 신뢰성 전달
    • TCP처럼 재전송방식을 사용하기도 하지만 대체로 오류를 해결하는 방식을 자주 사용
    • 단 유선처럼 오류가 적은곳에서는 부하를 위해쓰지 않는다
    • 오류 확률이 높은 무선링크부분에만 적용하는게 보다 효과적

  • 오류 검출

    • 신호의 약화나 잡음으로 발생
    • 오류검출비트를 추가해야 한다
    • 대체로 빠른속도를 위해 하드웨어단에서 처리
    • 재전송보다는 오류를 정정
  • 링크계층의 구현위치
    • 때체로 NIC, 하나의 칩으로 구현
    • 하드웨어와 소프트웨어 펌웨어 모두의 조합

6.2 오류검출

  • EDC : 오류 검출 및 정정 비트
  • D : 오류 체크에 의해 보호되는 데이터
  • 항상 100%오류를 검출할 수 있는건 아니다

6.2.1 패리티 검사

  • 단일 비트 패리티 : 단일 비트의 오류를 검출
    • 짝수 패리티 : 1의 개수가 짝수가 되도록 패리티 비트 설정 (반대는 홀수)
  • 이차원 비트 패리티 : 단일 비트 오류를 검출하고 정정

그러나 이 방법들은 2비트 이상의 오류를 검출할 수 없다

→ 오류가 거의 없는 유선상황에서 대체로 많이 사용

6.2.2 체크섬

  • 16비트 정수들을 다 더한 후 1의 보수를 취한 값
    • 수신자도 데이터를 받아 체크섬을 계산 후 같은지 판별하는 원리
  • CRC와 비교했을 때 비교적 간단하나 검출정도는 취약

6.2.3 CRC(순환중복검사)

  • 수학적인 나누기연산 (조금더 복잡하다)

  • 하드웨어적으로 보통 구현한다

  • 용어
    • <D,R> = D *2^R XOR R
      • D*(2^R) = 데이터에 대해 r비트만큼 시프트 연산 후 0을 채워넣는다
      • <D,R> (= D *2^R XOR R ) = 이 상태에서 0의 자리에 CRC를 넣는다
      • G = r+1

  • 순서

      1. r만큼 D에 대해 시프트 연산 (비워진만큼 0이 채워짐) → D*(2^r)
      1. D*(2^r)에 대해 G XOR수행한 나머지를 계산한다 → R계산
      1. 계산된 R과 D*(2^r)을 XOR연산한다 (비워진 0에 계산된 R넣기) → <D,R>
      1. 송신자는 <D,R>을 보낸다
      1. 수신자는 <D,R>을 G로 나눠보는데 나머지로 0이 나오는지 확인한다
  • r+1비트이상의 오류가 발생하면 검출하지 못한다 (r까지만)

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

6.3.1 두 종류의 네트워크 링크

링크 계층에서는 2가지의 채널구조가 존재할 수 있다

  • 점대점
    • 이더넷스위치와 호스트간의 점대점 링크
    • ppp, hdlc등의 프로토콜 존재
  • 브로드캐스트 링크
    • 물리적으로 다 연결되어있어서 하나에서 다른 한 곳으로 연결 가능
    • 유선과 무선 모두 가능
    • 충돌문제
      • 하나의 공유된 브로드캐스트 채널상에서 여러 노드가 동시에 프레임을 전송하면 충돌 발생
      • 충돌 시간만큼 브로드캐스트 채널은 낭비된다 (여러 노드의 신호가 다 깨짐)
      • 다중접속프로토콜 : 각 노드들이 어떻게 공유할지 결정하는 분산알고리즘이 필요하다

6.3.2 이상적인 다중 접속 프로토콜

  • 단 하나의 노드가 전송을 한다면 충돌없이 전체 전송률 bps활용 가능
  • N개의 노드가 전송을 보낸다면 평균적으로 R/N 정도의 전송률 활용가능
  • 각 노드는 완전 분산된 형태를 가진다
    • 각자의 노드가 자신의 판단으로 보냄
    • 동기화도 없다
  • 프로토콜 자체가 매우 단순

6.3.3 MAC프로토콜

  • 채널분할 프로토콜
    • 채널을 더 작은 조각으로 나누어 각 노드는 할당된 조각만을 사용함
    • 시간, 주파수, 코드
    • 트래픽이 커야 유리하다
  • 랜덤 접속 프로토콜
    • 모든 노드가 동시에 채널접속 가능
    • 충돌이 발생할 수 있다 (당연)
    • 대신 충돌을 완화하고 빠르게 복구하는 형태로 동작
    • 트래픽이 작아야 유리하다
  • 순번프로토콜
    • 위 두 프로토콜의 특징을 섞었다
    • 순번을 정해 해당 타이밍동안은 자유롭게 사용
    • 단 순번이 올때까지 오래 기다려야 한다

6.3.3.1 채널분할 MAC프로토콜

TDMA

  • 시간을 프레임 단위로 나누고 각 프레임을 Slot으로 나눈다
  • 각 노드는 Slot을 할당받아 사용한다
  • 슬롯의 크기는 고정적이며 하나의 Frame에 몇 개의 슬롯이 들어가는지는 TDMA관리자가 설계
  • 각 노드에 할당된 slot이 사용되지 않으면 낭비가 발생한다

FDMA

  • 채널 스팩트럼을 여러 주파수 대로 나눈다
  • 각 노드는 특정 주파수대를 할당받아서 사용
  • 할당받은 주파수를 사용하지 않으면 낭비

CDMA

  • 서로 다른 코드들을 노드들에게 할당
    • 이때 코드는 직교코드의 특성을 지닌다 (곱해서 0이됨)
  • 코드를 사용하여 패킷을 보내면 충돌이 발생하더라도 성공적으로 데이터를 수신할 수 있다
  • 보내려는 신호와 코드를 비트에 곱한다 (-1 * -1 = 1 )
  • 각 곱해진 신호를 더해서 수신측에 보낸다
  • 수신측에서는 받은 신호에 대해 다시 코드 연산을 수행
  • 연산된 결과를 다시 연산

6.3.3.2 랜덤 접속 프로토콜

  • 컨트롤 자체가 분산되어있다(누군가 체계적으로 관리하지 않음)
  • 전송할 패킷이 있다면 그냥 보낸다
    • 사전 조율과정이 없음
    • 해당 채널의 최대 전송률 R bps를 보낸다
  • 충돌을 감지하고 충돌에 대한 대처가 필요하다

슬롯 알로하

  • 시간을 각 슬롯으로 나눈다
  • 각 노드가 패킷을 보내기 시작하면 다음 슬랏이 시작되는 시점에 패킷을 보낸다
    • 각 노드는 슬롯에 대한 동기화 필요(슬랏이 시작되면 동시에 보내야 한다)
    • 이때 충돌이 발생하더라도 적어도 하나의 슬랏구간에 대한 손실만 발생한다 (막 보내면 2배 손실)
  • 충돌에 대한 동작
    • 적절한 확률을 계산하여 성공할 때 까지 후속슬랏에서 패킷을 계속 보낸다
      • 너무 확률을 높이면 재충돌 확률이 높아짐
      • 너무 확률을 낮추면 채널활용률이 떨어진다
      • 충돌난 노드가 많을 수록 확률을 줄여야 한다는 특징이 있다

  • 장점

    • 각 노드는 채널의 최대 전송률로 패킷 전송 가능
    • 상당히 분산된 형태(충돌이 감지되면 알아서 다시 보냄)
    • 비교적 단순

  • 단점

    • 슬롯을 사용하지 않거나 충돌 발생시 낭비
    • Clock동기화가 필요하다
    • 보내면서 충돌을 확인해야 한다
  • 효율
    • N개의 노드가 있고 각 슬롯에서 p확률로 프레임전송을 시도한다 가정
    • 임의의 노드의 프레임 전송이 성공할 확률 : p(1-p)^(N-1)
    • 특정 노드의 프레임 전송이 성공할 확률 : Np(1-p)^(N-1)
    • 최대 효율을 가지는 p의값을 찾고 계산하면 37% 즉 최대 채널 활용률은 37%
    • 순수 알로하 (slot동기화 없음)는 2배로 좋지 않은 18%

CSMA

  • 만약 채널을 누가 사용중이라고 감지(busy)했다면 프레임 전송을 미룬다.

  • CSMA/CD는 강화판
    • 충돌을 감지하면 전송하던 프레임을 멈춘다
    • 채널의 낭비가 감소된다
    • 유선의 경우 충돌감지가 더 쉽다

  • 프레임 전송이 시작되고 퍼지는 시간안에 누군가 읽게되면 충돌이 발생

    • 즉 전파지연시간과 노드간의 거리가 충돌여부에 영향을 미친다
  • 알고리즘
      1. NIC는 데이터그램 수신 후 프레임 생성
      1. 채널을 확인한다
        • idle이라면 보내고 busy라면 기다렸다가 다시 확인
      1. 프레임을 보내다가 충돌을 감지했다면 jam signal전송
        • jam signal이란 100%혼잡상황을 알릴 수 있는 신호
      1. m번째 충돌에 대한 값의 범위 0~ 2^m-1 중 랜덤하게 k값을 선택해 해당 시간을 기다렸다가 2번
        • 충돌을 겪을 수록 많은 노드가 동시에 보냈다는 것을 의미하고 지수적으로 시간을 늘린다
        • 이를 binary BackOff이라고 한다
  • 성능
    • 전파시간이 낮고 전송률이 높으면 효과적이다
    • 충돌이 많으면 비효율적이기 때문에 노드가 작을수록 효과적이다

6.3.3.2 순번 프로토콜

폴링

  • 마스터 노드가 라운드 로빈방식으로 각 노드를 폴링후 폴링된 노드가 패킷 전송
    • 순번을 누군가 컨트롤
  • 마스터 노드가 고장나면 다 죽는다
  • polling 오버헤드 존재

토큰 패싱

  • 토큰 받은 시점에서 패킷을 보낸다
  • 데이터 보낼 게 없다면 토큰을 넘긴다
  • 토큰 오버헤드가 존재
  • 노드 고장으로 토큰을 보내지 않으면 멈춘다

케이블 접속 네트워크

  • 채널분할, 랜덤접속 프로토콜 모두가 복합적으로 다 포함[FDM, TDM, random Access)
  • 다중채널로 구성되어 있다(FDM방식을 활용)
    • 다중 하향 채널 : 경쟁자가 아에 없고 헤드앤드에서 각 집으로 내려가는 방향
    • 다중 상향 채널 : 충돌이 발생할 수 있다 (다중접속상황)
  • DOCSIS
    • 각 집은 채널 분할 프로토콜의 할당받은 slot에 데이터를 보내서 보낸다 (TDML)
    • 슬롯 요청 프레임은 랜덤 접속 프로토콜 방식의 경쟁으로 보낸다

카테고리:

업데이트:

댓글남기기