컴퓨터 네트워크 6: The Link Layer and LANs

LeemHyungJun·2023년 12월 12일
컴퓨터네트워크
0

Computer Network

목록 보기
7/8

1. Introduction

  • 용어
    • node : host & router
    • frame : 2계층에서 packet을 부르는 말
    • link : source에서 destination을 가는 동안 존재하는 경로에서 router와 host를 연결하는 것들을 말한다.
  • link layer이 제공하는 services
    • framing, link access
      • channel access : 경쟁을 통해 channel 확보하기
      • MAC 주소 : 2계층만의 고유한 주소값, 시작점과 도착지의 정보
    • flow control
    • error detection
    • error correction
    • half duplex and full duplex
  • link layer는 NIC(Network Interface Card) 에 구현되어있다.

2. Error detection, correction

  • Error detection
    • EDC : error detection과 correction을 하는 bits
  • Parity Checking
    • single bit parity
      • 짝수나 홀수 패리티 방식을 통해 1의 갯수를 측정하여 error를 찾아낸다
      • 그러나 한번에 한개의 비트가 아닌 여러개의 비트 error가 생긴 경우 문제를 해결하지 못한다.
    • two-dimensional bit parity
      • 행과 열 두개로 패리티를 구성하여 두 번의 체크를 통해 error를 찾아낸다.
  • CRC(Cyclic Redundancy Check)
    • 용어
      • D는 data bit
      • R은 CRC bit, 크기는 r bits
      • G는 bit pattern(generator), r+1 bits
    • 구조
    • 계산
      • <D,R>G\frac{<D,R>}{G} 의 결과가 나머지가 없어야 error가 없다고 판별!
      • <D,R>=D∗2r<D,R> = D*2^r XOR RR
        • 이때 D∗2rD*2^r은 r비트만큼 왼쪽으로 shift 하는 결과
      • 결론적으로 우리가 구하는 것은 R이고 D∗2rG\frac{D*2^r}{G}의 나머지가 RR이다.
    • 예시
      • D=[101110], G=[1001], r=3(G의 크기로부터 알수있음)
      • R=D∗2rGR = \frac{D*2^r}{G}의 나머지
        • D∗23=101110000D*2^3 = 101110 000
        • D∗2rG=\frac{D*2^r}{G}= 몫: 101011 나머지: 011
        • 101110 011 은 1001로 나눠떨어지게 된다.

3. Multiple access protocols

  • 2계층 프로토콜의 핵심 기능 중 하나
    • link의 두가지 타입
      • point to point : one server one receiver
      • broadcast
  • 그렇다면 하나의 공유하는 broadcast channel을 어떻게 분배할 것인가! (channel의 사용권 결정하기)
    • 이상적인 경우
      • MAC(Multiple Access Channel) of rate Rbps
      • M개의 노드가 있다면,,, R/M으로 나누기
      • 완전히 분산된 시스템이다. 동기화나 정지하는 마스터 노드가 없다. 단순하다는 장점은 있다.
  • MAC protocol의 종류
    • channel partitioning
      • 채널을 작은 조각들로 나누기
      • 안쓰는데 1/M으로 나눠진 것들은 낭비가 된다.
    • random access
      • 사용권을 경쟁을 통해 획득
      • 가장 많이 쓰는 방식
    • taking turns
      • 경쟁없이 돌아가면서 쓰는 방식
  • Channel Partitioning MAC Protocols
    • TDMA
      • 시간을 1/N으로 나누기
      • 각 frame을 고정된 길이로 나눈다.
    • FDMA
      • 대역폭을 1/N으로 나누기
  • Random Access Protocol
    • 전송 노드는 항상 최대 전송률인 Rbps로 전송
    • 만약 충돌이 발생하면 랜덤한 시간동안 기다린 후 재전송을 진행한다.
    • Slotted ALOHA
      • 전제조건
        • 모든 frame은 같은 크기
        • 충돌이 발생하면, 성공할 때 까지 p의 확률로 재전송
          • 이때 확률 p로 재전송 하는것은 확률이 매우 치우친 동전던지기를 하는 것과 같다.
      • 특징
        • 장점 : 매우 분산적이며, 간단하다.
        • 단점 : 충돌이 발생하고, slot이 낭비된다. 충돌이 발생해도 해당 slot의 전송을 끊지 않고 계속 보냄
      • 효율성
        • 임의의 한 노드가 성공적으로 보낼 확률 : Np(1−p)N−1Np(1-p)^{N-1}
        • 최대 효율은 1/e = .37 (37%)
        • 충돌이 발생하지 않으려면, 전송 시작 전 slot에서 전송하려는 데이터 이외의 데이터가 발생하지 않으면 충돌이 발생하지 않는다.
    • Pure ALOHA
      • slot을 사용하지 않는 알로하, 동기화 작업 안함 -> 충돌이 더 많아진다는 문제점이 있다.
      • pure 알로하가 충돌이 발생하지 않으려면
        1) data A가 전송하는데 걸리는 시간 T만큼 이전 기간동안 데이터가 발생하면 안된다.
        2) data A를 전송하는 시간 T 동안 다른 데이터가 발생하면 안된다.
      • 효율성
        • 최대 효율이 18%
    • CSMA(Carrier Sense multiple Access)
      • channel을 쓰고 있는지 아닌지를 확인
        • 안쓰고 있다면(idle) 바로 데이터 전송
        • 쓰고 있다면(busy) 종료될 때 까지 대기
      • 이 방식은 충돌을 피하는 것은 불가능하다.
        • propagation delay가 길어지면(node와 node 사이가 멀어지면) 충돌 발생 가능성이 더욱 높아진다. -> 그래프의 기울기가 완만해 지는 것
        • 충돌이 발생하면 다른 node들이 전송을 할 수 없어서 낭비된다.
    • CSMA/CD(CSMA with Collision Detection)
      • 이더넷에서 쓰는 방식
      • 충돌이 검출되면 전송을 끊어버림
      • 알고리즘
        1) network layer에서 datagram 가져와서 frame 만들기
        2) Idle인지 busy인지 carrier sensing 수행
        3) 전체에서 충돌 없다면 frame 보내고 종료
        4) 다른 전송을 확인한 경우 -> abort
        • abort된 경우 binary exponential backoff 수행
        • m번의 collision 발생한 경우 -> K를 0,1,2,...,2m−1{0,1,2,...,2^{m-1}}에서 K를 선택
        • NIC는 K*512 bit time을 기다린 후 2)로 돌아감
          • if) R = 100Mbps -> 1 bit time = 10−8sec10^{-8}sec
        • 많은 충돌이 발생할수록 집합의 크기가 지수적으로 커짐
      • 효율성
        • efficieny=11+5tpropttransefficieny = \frac{1}{1+5\frac{t_{prop}}{t_{trans}}}
        • propagation delay가 0일수록, transmit max-size frame 시간이 무한대에 가까울수록 효율성이 1과 가까워짐
        • 결론은 ALOHA보다 성능이 좋다
  • Taking turns
    • polling
      • 중앙집중형, 마스터 노드가 RR 방식으로 polling 수행
        -> master 노드가 다른 노드들에게 최대로 보낼 수 있는 프레임을 알려줌
      • 오버헤드, 한번에 다 고장난다는 문제점 있다.
    • token passing
      • token이라는 짧은 제어 message를 사용하는 방식
      • 즉 전송중인 노드는 token을 가지고 있는 방식
      • 그러나 token이 문제가 생길 수 있다는 단점이 있다.

4. LANs

  • IP address
    • network layer의 주소이다. 32bit, ex) 128.119.40.136
    • 3계층의 forwarding을 위해 사용
    • 위치에 따라 주소가 달라짐
  • MAC address
    • link layer의 주소이다. 48 bit, ex) 1A-2F-BB-76-09-AD
    • 물리적으로 연결된 다른 인터페이스의 frame을 가져옴
    • 어뎁터의 MAC 주소는 위치에 따라 바뀌지 않음!!

4-1. ARP (Address Resolution Protocol)

  • 정의: IP주소와 MAC주소를 변환해주는 역할
    • ARP table : IP주소, MAC 주소, TTL 순서로 작성된다.
      • TTL(time to live): 대체로 20분으로 설정, 20분 동안 address mapping이 이루어지지 않으면 table에서 지워진다.
  • ARP protocol (A와 B가 같은 subnet에 존재)
    • ARP table 비어있을 때 (A 기준)
      • 도착지 MAC 주소: FF-FF-FF-FF-FF-FF (전체에게 보낸다는 의미)
      • 만약 B가 해당 query에 응답한다면 MAC 주소를 다시 보냄
      • ARP table에 B의 IP 주소와 MAC addr, TTL을 적는다.
  • ARP protocol (A와 B가 다른 subnet에 존재)
    • R이라는 라우터를 통해 B로 이동한다.
    • A의 목적지 MAC주소는 R의 인터페이스 MAC주소이고 목적지 IP 주소는 B의 IP 주소이다.
    • 이후 subnet과 subnet 간의 이동은 link layer의 역할이 아니다.
    • 다시 R의 전송 시작 주소는 R의 MAC주소이고 도착지 주소는 B의 MAC주소가 되어 A->R->B로 전달된다. IP 주소는 그대로

4-2. Ethernet

  • 선으로 연결된 근거리 통신망, 싸고 단편하다.
  • topology
    • 이전에는 bus방식 썼지만, 충돌이 발생해서 switched 방식으로 바뀜
  • frame structure
    • preamble: 동기화, 신호의 시작 알려주기
    • address: MAC 주소의 도착지
    • type: 2->3계층으로 옮기기 위한 protocol
    • CRC: error 검출
  • 특징
    • connectionless
    • unreliable : 안정적인 전송 불가능
    • CSMA/CD 사용

4-3. Switch

  • 이더넷의 스위치는 스스로 알아서 동작함
    • transparent
    • plug and play, self learning
  • multiple simultaneous transmission
    • host들은 스위치와 전용 direct 연결로 구성
    • collision 발생 안함 -> 각 경로가 full duplex이므로
      • A->A' B->B'은 동시에 일어날 수 있고 충돌도 안생김
      • 그러나 A->A'과 B->A'이라는 전송이 동시에 이루어지면 충돌 발생
  • self learning
    • cf) IP의 forwarding table은 라우팅 프로토콜로 구성되며, 양이 매우 많다..(self learning 불가능)
    • MAC 주소는 IP에 비해 간단하므로 self learning이 가능하다.
      • 위의 그림처럼 A->A'를 지나간다면, 테이블을 채우고 다음 것을 진행하면서 테이블을 모두 채운다. (TTL : time to live 데이터의 유효기간)
      • 만약 drop time때까지 도착지에 도착을 못하면 drop 해버림
  • 스위치와 라우터의 차이점
    • 스위치
      • link layer 장치이며, store-and-forward 진행
      • flooding, learning, MAC 주소를 통해 forwarding table을 만든다.
    • 라우터
      • network layer 장치이며 store-and-forward 진행
      • 라우팅 알고리즘을 통해 table 계산, IP 주소이용

A Day in the life of a web request

profile
LeemHyungJun
이전 포스트

컴퓨터 네트워크 5: Network Layer - Control Plane

다음 포스트

컴퓨터 네트워크 7 : Wireless and Mobile Networks

0개의 댓글