3. Data-Link Layer(데이터링크층)

이세진·2022년 4월 4일
0

Computer Science

목록 보기
66/74

생성일: 2021년 9월 12일 오후 2:20
태그: Data-Link Layer

3.1 개요

  • 인터넷
    • 라우터와 스위치와 같은 장치들을 연결하는 네트워크의 조합
    • 패킷이 호스트에서 다른 호스트로 전달되면, 이것은 이러한 네트워크들을 통과하는 경로가 필요하다
  • 데이터 링크 계층에서의 통신

노드와 링크

  • 데이터링크 계층에서의 통신은 노드-대-노드
  • LAN과 WAN은 라우터를 통해 연결
  • 라우터와 pc를 노드로 취급(LAN과 WAN 스위치는 취급 X)

  • 데이터링크 계층은 물리 계층과 네트워크 계층의 사이에 위치
  • 물리계층으로부터 네트워크 계층으로 전달받은 서비스를 제공함
  • 기능
    1. 프레임 짜기 : 네트워크 계층으로부터 받은 비트 스트림을 프레임 단위로 나눔
    2. 흐름 제어 : 수신자의 수신 데이터 전송률을 고려하여 데이터를 전송 하도록 제어
    3. 오류 제어 : 손상 또는 손실된 프레임을 발견/재전송
    4. 혼잡 제어 : 소통량을 조절하여 네트워크가 혼잡해지지 않게 조절
  • 데이터링크 계층은 단지 점-대-점 링크 또는 브로드캐스트 링크와 같은 링크 성능의 일부분을 사용함
  • 점-대-점 링크에서 링크는 서로 연결된 두개의 단말에만 전념
  • 브로드캐스트 링크의 링크는 몇 개의 기기 쌍 사이에서 공유
  • 두 하위 계층
    • 데이터 링크 제어(DLC)
    • 미디어 접속 제어(MAC)

3.2 DLC(Data-Link Control)

  • 기능
    1. 프레임 짜기
    2. 흐름 및 오류 제어

프레임 짜기(Framing)

  • 비트들을 프레임 안에 넣어 각 프레임이 다른 프레임과 구분
  • 송신자와 수신자의 주소를 넣음으로써 발신지로부터 목적지로의 메시지를 분리
  • 목적지 주소는 패킷이 가야할 곳을 규정하여 송신자는 수신자로 하여금 받았다는 것을 응답할 수 있도록 도와줌
  • 고정크기 프레임: 고정 길이 또는 가변 길이
  • 가변크기 프레임: 프레임이 끝나는 곳과 다음 프레임이 시작하는 곳 지정
    1. 문자열 중심 프로토콜

      • 전달되는 데이터는 코딩 시스템의 8비트 문자
      • 시작과 마지막에 플래그 추가
      • 문자 중심 프로토콜 프레임

    2. 비트 중심 프로토콜

      • 프레임의 데이터 부분을 전부 bit 열로 인식
      • 플래그는 "01111110"비트 패턴 사용
      • 비트 중심 프로토콜 프레임

바이트 채우기(stuffing)과 빼기(stuffing)

💡 바이트 채우기(byte stuffing)은 텍스트에 플래그나 탈출문자가 있을 때 마다 여분의 1문자를 추가하는 처리이다.

  • 비트 채워 넣기는 0뒤에 연속하는 다섯 개의 1이 있게되면 추가로 0을 채워 넣는 과정이며, 따라서 수신자가 데이터 속의 01111110을 플래그로 오인하는 것을 방지한다

에러제어

  1. 단일 비트 에러(single bit error)
    • 주어진 데이터 단위 중 오직 하나의 비트만이 변경되는 오류
  2. 폭주 오류(burst error)
    • 데이터 단위에서 2개의 이상의 연속적인 비트들이 바뀌는 오류

중복(redundancy)

  • 오류 검출과 정정의 중심 개념
  • 데이터 이외의 추가 비트들을 보내야 하는데, 이 중복 비트들은 송신자에 의해 첨가되며 수신자가 제거함
  • 중복 비트들로 인해 수신자는 오류를 찾거나 정정 할 수 있다.

검출 대 정정(detection & correction)

  • 오류 검출
    1. 오류가 생겼는지 알아냄
    2. 오류 유무만 파악
    3. 오류가 몇 개인지는 알 필요 X
  • 오류 정정
    1. 정확하게 몇 비트가 잘못 되었는지, 어디가 잘못 되었는지를 알아내는 것

코딩

  • 송신자는 중복 비트와 실제 데이터 비트들 사이에 어떤 관련을 짓게 하는 과정을 통해 중복 비트를 보냄
  • 수신자는 이 비트들 사이의 관계를 확인하여 오류 검출 및 정정
  • 코딩 방법은 블록코딩과 컨볼루션 코딩으로 나뉨

블록 코딩(block coding)

  1. 데이터워드로 불리는 k비트의 블록으로 메시지를 나눔
  2. 각 블록에 r개의 중복 비트들을 더하여 길이 n = k + r 이 되도록 함
  3. 결과로 얻는 n비트 블록은 코드워드(codeword)라고 불림

오류 검출(Error Detection)

다음 두 조건으로 수신자는 원래 코드워드가 바뀐 것을 확인한다.

  1. 수신자는 유효 코드워드들을 찾아내거나 그 리스트를 가지고 있다.
  2. 원래의 코드워드가 무효 코드워드(invalid codeword)로 바뀌었다.

💡 오류 검출 코드는 찾도록 설계된 오류만을 찾아낸다. 다른 오류는 검출하지 못한다.

해밍 거리(Hamming Distance)

  • 오류 제어를 위해 해밍 거리 이용
  • 두 개의 같은 크기의 워드간에 차기아 나는 비트의 개수
  • 두 워드에 XOR 연산을 해서 얻은 결과 값의 1의 개수

💡 두 워드 사이의 해밍 거리는 차이가 나는 해당 비트들의 개수이다.

최소 해밍 거리(minimun Hamming distance)

  • 모든 가능한 코드워드 쌍들 사이의 가장 작은 해밍 거리

💡 s개 까지의 오류가 발생해도 오류가 생긴 것을 알아내는 것을 보장하기 위해서는 블록 코드의 최소 해밍 거리는 dmin=s+1d_{min} = s+ 1 이여야 한다.

선형 블록 코드(Linear block code)

  • 두 유효한 코드워드에 대해 XOR 연산을 가해 다른 유효한 코드워드를 생성하는 코드

패리티 검사 코드

  • 선형 블록 코드
  • k비트 데이터 워드를 n = k + 1이 되도록 n비트 코드워드로 바꿈
  • 추가된 비트는 패리티 비트라고 불리며 전체 코드워드의 1의 개수가 짝수가 되도록 선정
  • 최소 해밍거리 dmin=2d_{min} = 2 이며 이는 코드가 단일 비트 오류 검출코드라는 것을 의미
  • 단순 패리티 검사 코드는 홀수 개의 오류를 검출한다(짝수개의 오류는 1의 개수의 홀짝이 바뀌지 않기 때문에 패리티 검사로 검출 불가능)

순환 코드(cyclic code)

  • 하나의 특별한 성질이 있는 선형 블록 코드
  • 코드워드를 순환시켜 다른 코드워드를 얻음
  • ex) 1011000이 코드워드이면 1개의 비트를 왼쪽을 이동시켜 얻는 0110001도 코드워드이다

순환 중복 검사(CRC)

CRC : cyclic redundancy check

LAN이나 WAN에서 널리 사용

CRC 코드 C(7,4)

  • CRC 부호화기와 복호화기

  • CRC 부호화기의 나눗셈

다항식(Polynomial)

각 항의 지수가 각 비트의 자리수를 나타냄

순환 코드의 이점

  1. 단일 비트, 두 비트, 홀수 개의 비트 및 폭주 오류 검출에 우수
  2. 쉽게 구현

두가지 DLC 프로토콜

  • 점대점과 다중점 링크 이에서 통신을 위한 비트 지향 프로토콜
  • 두 가지 전송 모드
    • 정규 응답 모드(NRM)
      1. 지극 구성이 비균형적

      2. 하나의 주국, 여러 개의 종국

      3. 주국은 명령을 보낼 수 있지만 종국은 응답만 가능

      4. 점대점, 다중점 링크에 모두 사용

        Primary : 주국, Secondary : 종국

    • 비동기 균형 모드(ARM)
      1. 균형적 구성

      2. 링크는 점대점

      3. 각 지국은 주국이자 종주국

  • HDLC 프레임 종류
    • 정보 프레임(I-프레임) : 네트워크층으로부터 사용자 데이터를 실어 나르기 위함
    • 감시 프레임(S-프레임) : 흐름제어, 오류제어를 위해 사용
    • 무번호 프레임(U-프레임) : 서로 연결된 장치들 간에 세션관리, 제어정보 교환
  • HDLC 필드 종류
    • 플래그 필드 (flag field)
    • 주소 필드 (address field)
    • 제어 필드 (control field)
    • 정보 필드 (information field)
    • FCS 필드 (frame check sequence field)

2. 점-대-점 프로토콜(PPP)

  • 점대점 접근을 위한 가장 널리 사용되는 프로토콜
  • 문자 중심 프레임 사용
  • 필드 종류
    • 플래그 필드 (flag field)

    • 주소 필드 (address field)

    • 제어 필드 (control field)

    • 프로토콜 필드 (protocol field)

    • 페이로드 필드 (payload filed)

    • FCS 필드 (frame check sequence field)

  • 다중화
    • PPP는 데이터 링크 계층 프로토콜이지만 네트워크 계층 데이터를 옮기는 등 다른 프로토콜도 사용

3.3 매체 접근 프로토콜(MAC)

  • 다중 접근 (Multiple Access) : 노드나 지국이 다중점 또는 브로드캐스트 링크라고 부르는 공유 링크를 사용할 때 링크에 접근하는 것을 조율하기 위한 다중 접근 프로토콜 필요
  • 분류

임의 접근(Random - access protocols)

  • 각 지국(station)은 다른 어느 지국에 의해 제어받지 않는 매체 접근 (media access) 권리를 가지고 있음
  • 매 순간 전송할 데이터가 있는 지국은 전송할지 말지를 결정하기 위해 프로토콜에서 정해진 절차를 따름
  • 이 결정은 매체의 상태(휴지 상태이냐 바쁘냐)에 좌우
  • 충돌(collision)을 피하기 위한 절차
    1. 언제 지국이 매체에 접속할 수 있는가?
    2. 만약 매체가 사용된다면 지국은 무엇을 할 수 있는가?
    3. 어떤 방법으로 지국은 전송의 실패와 성공을 파악할 수 있는가?
    4. 만약 매체 충돌이 발생한다면 지국은 무엇을 할 수 있는가?

ALOHA

  • 가장 오래된 임의 매체 접근 방법
  • 재국들은 매체를 공유
  • 지국이 데이터를 전송할 때 동시에 다른 지국도 같은 시도 가능
  • 두 지국으로 부터 데이터는 서로 충돌하여 망가질 수 있다. (garbled)

    순수 ALOHA (pure ALOHA)

    1. 각 지국은 지국이 전송할 프레임이 있으면 언제든지 전송

    2. 그러나 오직 하나의 채널만이 있으므로 서로 다른 지국에서 전송한 프레임 간에 충돌이 있을 수 있음

    3. 프레임 전송 후 확인응답을 기다리고 시간 내에 확인응답을 받지 못하면 프레임을 잃어버렸다고 간주하고 재전송을 시도

    • 순수 ALOHA 취약 시간 (Vulnerable time)

    • 처리량 (throughput)

      • S는 처리량, 성곡적으로 전송되는 프레임의 평균 개수
      • G는 한 프레임 전송 시간 동안에 시스템 전체에서 생성되는 프레임의 평균 개수

      Slotted ALOHA

      틈새(slotted) ALOHA에서는 시간을 TfrT_{fr}의 슬롯으로 나누어 지국은 매 시간 슬롯이 시작할 때에 전송하돌록 규제한다.

    • slotted ALOHA 프로토콜의 취약 시간

    • 처리량 (throughput)

      처리량S=GeG처리량 S = G * e^{-G}
      G=1일때최대처리량Smax=0.368G = 1 일 때 최대 처리량 S_{max} = 0.368

CSMA

반송파 감지 다중 접근 (Carrier Sense Multiple Acess)

  1. 충돌의 기회를 최소화
  2. 각 지국은 전송 전 매체의 상태를 점검
  3. "전송 이전에 감지" , "말하기 이전에 듣기" 원칙에 기반
  4. 충돌 가능성을 줄일 수는 있지만 제거는 불가( 전파 지연 때문에)
  • 시곤간 모델

  • CSMA 취약 시간

  • 지속 방식
    • 1-지속 방식

    • 비지속 방식

    • p-지속 방식

      CSMA/CD

      충돌 검출 반송파 다중 접송(CD : collision detection)

    1. 충돌을 처리하는 절차를 더함
    2. 충돌 시 재전송 요구
    3. 두번 째 충돌을 줄이기 위해 대기
    4. 지속적인 백오프 방법에서 대기시간 발생
    • 지국은 전송 후 전송이 성공적인지 매체를 관찰

    • 최소 프레임 크기
      - CSMA/CD가 동작하기 위해서는 프레임 크기에 제한을 둬야함
      - 프레임 전송 시간 TfrT_{fr}은 최소한 최대 전파 시간 TpT_{p}의 2배가 되어야 함

      Tfr=2TpT_{fr}=2 * T_p

      CSMA/CA

      충돌을 회피하는 반송파 감지 다중 접근 (CA : collision avoidance)

    1. 무선 네트워크를 위해 고안

제어 접근(Controlled Access protocols)

어느 지국이 전송 권리를 가지고 있는지 서로 상의하여 찾는다

지국은 다른 지국에 의해 권리를 인정 받기 전에는 전송 불가

  1. 예약 (Reservation)

  2. 폴링 (Polling)

  3. 토큰전달 (Token passing)

    예약(Reservation)

    • 지국은 데이터를 송신하기 전에 예약을 필요로 함
    • N개의 지국이 존재하면 N개의 미니 슬롯들이 예약 프레임 안에 존재
    • 예약을 한 지국은 데이터 프레임을 예약 프레임 뒤에 전송

    폴링(Polling)

    • 지국 중 하나가 주국(Primary station)이 되고 다른 지국들은 종국(secondary station)이 되는 접속 형태에서 동작
    • 종국으로 가는 데이터도 모두 주국을 통해 전달
    • 주국이 링크를 제어
    • 폴(poll)
      • 주국이 종국으로부터 전송을 요청하는데 사용
    • 선택(select)
      • 주국이 언제든지 송신할 것이 있을 때 사용

      • 종국의 준비 상태에 대한 확인 응답 대기

      • 주국은 전송 예정된 장치의 주소를 한 필드에 포함하고 선택 프레임을 만들어 전송

    토큰 통과(token passing)

    네트워크 안의 지국들은 지역 고리 형태로 구성된다.

    토큰을 가진 지국이 데이터 송신할 권한을 가짐


    3.4 링크 계층 주소지정

    • 발신지와 목적지 IP주소는 두 끝단을 정의하지만 패킷이 경유하는 경로에 대해서는 정의하지 못함
    • 비연결형(connectionless) 상호연결 네트워크에서는 두 노드들의 링크 계층 주소를 결정하기 위해 다른 주소지정 메커니즘이 필요
    • 데이터 그램이 네트워크층에서 데이터링크층으로 전달될 때, 데이터 그램은 프레임에 캡슐화되고 두 데이터 링크 주소는 프레임 헤더에 추가됨
    • 링크 계층 주소(link-layer address)는 링크주소(linkaddress), 물리적 주소(physical address), MAC 주소 (MAC address)라고도 불림

    ⭐작은 인터넷에서 IP 주소와 계층 주소 ⭐

    흐름을 알고 있어야 함

    세 종류의 주소

    링크 계층 프로토콜은 3종류의 주소로 정의

    1. 유니캐스트 주소
      1. 일대일 통신 의미, 링크에서 하나의 장치와 연결
    2. 멀티캐스트 주소
      1. 일대다 통신 의미, 범위는 국부 링크로 국한됨
    3. 브로드캐스트 주소
      1. 일대전체 통신 의미, 링크내 모든 장치로 전달됨

    주소 변환 프로토콜 (ARP)

    • 링크내 다른 노드로 전송하기 위해, 한 노드가 가지고 있는 IP데이터 그램은 수신노드의 IP 주소를 가지지만, 다음 노드의 IP 주소는 링크를 통과하는 프레임이 이동하는데 도움이 되지 않기 때문에 다음 노드의 링크계층 주소를 알아야함
    • ARP(Address Resolution Protocol)는 IP 주소를 지정된 링크 계층 주소에 매핑시키고, 데이터 링크층으로 전달함
profile
나중은 결코 오지 않는다.

0개의 댓글