[CH.5] Link Layer - services, error detection/correction, multiple access protocols

 

* switching - 2계층

• 같은 네트워크(같은 LAN)에 있는 장치들 사이에서 데이터 패킷 switch
• switch는 2계층 주소 (MAX address)를 사용해 어디로 데이터 패킷을 보낼지 안다.

* routing - 3계층

• 다른 네트워크들 사이에서 패킷 route
• router는 네트워크의 목적지 IP 주소를 이용하여 패킷 보낼 곳을 안다.

 

Link layer 관련 용어들

• 호스트와 라우터들: nodes
• communication 경로 사이에서 인접한 노드들을 연결하는 communication channels: links
  • wired links
  • wireless links
  • LANs -> L(link)
    • PAN -> P(personal)
• 2계층 패킷: frame, 데이터그램 인캡슐화
• data-link layer는 데이터드램을 링크를 통해서 하나의 노드에서 물리적으로 인접한 노드로 전송하는 역할이다.

 

 

Link layer services

• framing, link access:
  • 데이터그램에 header와 trailer를 더해 frame으로 인캡슐화
  • 공유되는 매개체라면 채널 접근
  • "MAC" address는 출발지를 나타내기 위해 frame header에 사용한다.
    • IP 주소와 다름
• 인접한 노드들 사이에서 reliable delivery
  • wireless links: 에러율 높음
    • 무선은 에러가 많아서 체크를 많이 해야 함 (에러 확인하면 다시 보내는데, 다시 보내는게 많아서 유선보다 느림)
  • wire link(유선, 광케이블): 에러율 매우 작음
• flow control: 인전한 송신 노드와 수신 노드 사이의 페이싱(pacing)
• error detection
  • signal attenuation, noise로 에러 유발됨
  • 수신자는 에러 탐지 
    • 수신자의 재전송을 위해 시그널을 보내거나 frame을 버림
• error correction:
  • 수신자가 식별하고 bit error를 수정한다.
• half-duplx and full duplex
  • half-duplex: 보내고 받는거 다 가능하지만 한 번에 하나만 가능하다.
    • 즉, 두 end points가 서로 서통할 때, 둘 다 보내고 받을 수는 있지만, 둘 다 동시에 보낼 수는 없음
  • full-duplex: 보내고 받는게 동시에 가능 (반은 보내는 쪽, 반은 받는 쪽으로 사용하면 됨)
    • 무선은 한 번에 못 함

 

 

* link layer은 "adaptor"에서 구현된다. (모든 호스트에 있는)

 

 

 

sending side:

• 데이터그램을 frame으로 인캡슐화
• 에러 확인 비트, rdt, flow control 등을 추가

receiving side:

• 에러, rdt, flow control 찾음
• 데이터그램을 추출해서 상위 계층에 보냄

 

 

 

 

 

Error detection

• Parity checking
  • single bit parity: 

 

짝수 페리티 비트라면 1의 개수가 짝수가 되도록 parity bit를 설정하고,

홀수 페리티 비트라면 1의 개수가 홀수가 되도록 parity bit 설정

 

 

 

1차원 bit parity의 경우, 오류를 찾을 수는 있지만 수정은 불가

 

2차원 bit parity는 잘못된 부분 찾아서 수정도 가능

하지만 redundant한 bit가 2배가 됨

 

보통 detection만 한다. 

잘못되면 다시 보내면 되니까 ㅎㅎ

 

 

 

 

 

Checksum

• 4계층에서 사용하는 error detection -> checksum
• Cyclic redundancy check (CRC)
  • D%G=R
  • 나머지를 데이터에 붙여서 보내면 받는 쪽은 나누어 떨어짐

 

 

나머지가 없다는 것은 에러가 없다는 것을 의미

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Multiple access links, protocols

• "links"의 두 가지 타입:
  • point-to-point:
    • 전화 접속을 위한 PPP
    • Etherner switch, host 사이의 point-to-point link
  • broadcast:
    • 옛날 방식의 Ethernet
    • upstream HFC
    • cocktail party 효과 -> 옆 사람이 시끄러우면 나도 시끄럽게 말하고, 점점 시끄러워짐
      • 이를 방지하기 위한 것: medium access control (polling) <- 충동 방지
        • 한명씩 말하도록 컨트롤
        • medium = multiple
• 단일 shared broadcast channel
• 노드에서 동시에 두 개 이상이 전송: interference(간섭)
  • 만약 노드가 두 개 이상을 동시에 받는다면 collision
  • collision 발생 조건
    • shared media
    • 동시에 여러개의 시그널을 receive
    • ㄴ 이를 구분해내지 못할 때
• multiple access protocol -> collision 줄이는게 목적
  • 노드들이 어떻게 channel을 공유할지 결정하는 분산된 알고리즘
    • 예: 노드가 언제 전송할지 결정
• channel sharing에 대한 communication은 자기 자신의 channel을 사용해야만 한다.
  • 협력하는 out-of-band channel 없음

 

 

MAC protocols: taxonomy

three broad classes:

• channel partitioning
  • 채널을 작은 조각(time slots, frequency, code)로 나눔
  • 노드에게 조각을 독점적으로 할당
• random access
  • 나눠지지 않는 채널, 충돌 허용
  • 충돌로부터 복구(recover)
• taking turns
  • 노드들이 교대로 작동하지만, 보낼게 많은 노드는 오래 턴을 가질 수 있다.

 

 

Channel partitioning MAC protocols: TDMA (Time Division Multiple Access)

• 충돌 발생하지 않음 -> 자기 턴에만 보내니까
• 시간을 partitioning
• "rounds" 안에서 채널에 접근
• 각 스테이션은 각 라운드 안의 고정된 길이의 슬롯을 가진다 (길이=패킷 전송 시간)
• 노드에게 각 시간 슬롯을 각각 할당해준다.
• 노드는 전송할 새로운 패킷이 있으면 자신에게 할당된 시간 슬롯 동안 패킷 비트들을 전송한다.
• 사용하지 않는 슬롯은 낭비되는 것
  • 전송할 패킷을 가진 노드가 하나일지라도 타임슬롯 R/N 대역폭으로 한정된다
• ex: 6-station LAN, 1,3,4는 패킷 가짐, 2,5,6 슬롯은 낭비

 

 

Channel partitioning MAC protocols: FDMA (Frequency Division Multiple Access)

• TDM은 브로드캐스트 채널을 시간으로 공유하지만, FDM은 R bps의 채널을 다른 주파수로 나눠서 각 주파수를 N개 노드 중 하나에게 할당한다. (각 R/N의 대역폭을 갖는다)
• TDM과 장단점 유사

• frequency bands로 채널 스펙트럼을 나눔

• 각 스테이션은 고정된 frequency band를 할당 받음
• frequency bands에서 사용하지 않는 전송 시간은 낭비됨
• ex: 6-station LAN, 1,3,4는 패킷 가짐, 2,5,6 frequency bands는 낭비

 

 

Random access protocols

• 노드가 전송을 위한 패킷을 가지고 있을 때
  • 전체 채널 데이터 속도 R로 전송
  • 노드 간의 우선순위 없음
• 두 개 이상 노드를 전송 -> collision
• random access MAC protocol은 명시한다:
  • 어떻게 충돌을 탐지할지
  • 어떻게 충돌로부터 복구할지 (예: 지연된 재전송을 통해)
• random access MAC protocol의 예:
  • slotted ALOHA
  • ALOHA
  • CSMA, CSMA/CD, CSMA/CA

 

 

Slotted ALOHA

• 가정:
  • 모든 frame은 같은 사이즈
  • 시간을 같은 사이즈의 슬롯으로 나눈다
  • 노드는 슬롯 시작에서 전송 시작 (시작과 함께 노드 보낼 수 있음)
  • 각 노드는 언제 슬롯이 시작하는지 알 수 있게끔 동기화 되어 있다.
  • 만약 2개 이상의 노드가 슬롯에서 전송되면, 모든 노드는 충돌을 감지함
• 작동:
  • 노드가 새로운 frame을 얻으면 다음 슬롯으로 전송
    • 만약 충돌이 없다면: 노드는 다음 슬롯으로 새로운 노드를 보낼 수 있다.
    • 만약 충돌이 있다면: 노드는 성공할 때까지 각 subsequent slot에서 frame을 재전송하며, 각 전송시 성공할 확률은 P이다

 

 

 

S 구간처럼 활동하는 노드가 하나일 때만 전송 가능

충돌이 일어나면 아무도 못 쓰게 함 -> 단점

 

 

 

 

 

 

•  장점:
  • 혼자만 활동하는 노드는 계속해서 채널의 최고 속도(full rate)로 전송할 수 있다.
    • 전송할 프레임이 있는 노드를 활성 노드라고 함
  • 하나의 노드가 전체 채널을 쓸 수 있음
  • 고도로 분산된(highly decentralized): 노드에 있는 슬롯은 동기화해야한다.
  • 단순
• 단점:
  • 충돌, 기다리는 슬롯
  • 슬롯 낭비 - 활성 노드가 많으면 일부 슬롯이 충돌로 인해 낭비된다, 활성 노드가 없을 경우
  • 충돌 탐지가 느림 (?)
  • clock synchronization
• 효율성
  • : long-run fraction of successful slots (많은 노드들, 보내기 위한 많은 프레임을 갖는 모두)
  • 가정: 전송을 위한 많은 프레임을 가지는 N개의 노드가 각 슬롯에 전송할 확률 -> p
  • 주어진 노드가 슬롯에 전송 성공할 확률 = $p(1-p)^{N-1}$
  • 어떤 노드가 전송 성공할 확률 = $Np(1-p)^{N-1}$
  • 최고의 효율성: 최대 확률 $Np(1-p)^{N-1}$
  • 많은 노드에서, $Np(1-p)^{N-1}$에서 N이 무한으로 가면:
    • max efficiency = 1/e =0.37
    • ㄴ> 채널이 사용중일 확률
  • 기껏해야 37%만이 유용한 전송을 한다. (채널 이용률이 37% 이하라는 말)

 

 

Pure (unslotted) ALOHA

• 만약 위 방법에서 slot이 없다면

• 단순하고 동기화 없음

• 성능 2배로 안 좋아짐

 

 

CSMA (Carrier Sense Multiple Access)

• CSMA: 전송하기 전에 누가 보내고 있는지 들음:
  • 만약 채널이 낭비되고(아무 일도 안하고) 있다면: 전체 프레임 전송
  • 누가 말하고 있으면 쉬었다가 보냄 -> 충돌 줄임
• CSMA collisions
  • 충돌은 여전히 발생할 수 있다
    • channel propagation delay: 신호가 채널의 한쪽 끝에서 다른 쪽 끝으로 전파되는 데 걸리는 시간
    • 이러한 전파 지연이 길수록 네트워크의 다른 노드에서 이미 시작된 전송을 캐리어 감지 노드가 감지할 수 없는 경우가 더 증가한다.
  • collision: 전체 패킷 전송 시간이 낭비됨
    • 거리, 전파 지연은 충돌 확률 결정에 역할을 한다.

 

 

시간이 지나면서 거리가 늘어나는 것 -> propagation delay

 

노란색은 처음에 말하는 사람이 없어서 전송

빨간색도 처음에는 말하는 사람이 없어서(자기가 들을 수 있는 위치에) 전송

 

전송 후, 조금 있다 충돌

 

충돌이 일어나면 바로 멈춤

 

 

 

 

 

CSMA/CD (collision detection)

• CSMA/CD: carrier sending, deferral as in CSMA
  • 짧은 시간 안에 충돌 탐지
  • 충돌하면 전송을 중단시켜 채널 낭비를 줄임 -> CSMA는 전송 뒤 충돌해도 그대로 전송함
• 충돌 탐지:
  • 유선 LAN에서는 쉬움: 시그널 길이 측정, 전송 비교, 시그널 받기
  • 무선 LAN에서는 어려움: 수신 신호 세기가 로컬 전송 세기에 압도되서 신호를 못 받음 (탐지 불가)

 

 

 

Ethernet CSMA/CD 알고리즘

1. NIC는 네트워크 계층으로부터 데이터그램을 받고, frame을 만든다
2. 만약 NIC가 채널이 놀고 있다고 느끼면 프레임 전송을 시작한다. 만약 NIC가 채널이 바쁘다고 느끼면, 채널이 널널해질 때까지 기다렸다 전송한다.
3. 만약 NIC가 다른 전송을 탐지하지 않았고, 전체 프레임을 전송했다면, NIC는 프레임 전송 완료!
4. 만약 NIC가 전송하는 동안 다른 전송을 탐지했다면, 중단하고 jam 신그널을 보낸다.
5. 중단 후, NIC는 binary (exponential) backoff에 진입: (exponential random backoff)
   • m번째 충돌 이후, NIC는 {0, 1, 2, ..., $2^{M}-1$}에서 랜덤하게 K를 고른다. 그리고 NIC는 K*512bit 시간을 기다리고 step 2로 돌아간다.
   • 충돌이 많으면 backoff 간격이 커짐
   • 즉, 전송했는데 충돌 일어나면 1초 기다림. 다시 보냈더니 또 충돌 일어나면 2초 기다리고, 또 충돌 일어나면 4초... 이런식

 

"Taking turns" MAC protocols

• channel partitioning MAC protocols:
  • high load에서 효율적이고 공정하게 채널 공유
  • low load에서 비효율성: 채널 접근 지연, 한 개의 노드만 활동할 때만 1/N bandwidth 할당함
• random access MAC protocols:
  • low load에서 효율적: 하나의 노드는 완전하게 채널 유틸리티 사용 가능
  • high load: 충돌 오버헤드
• "taking turns" protocols
  • 다 사용하기는 하지만 중앙에서 처리 필요

 

 

"Taking turns" MAC protocols

• polling:
  • 마스터 노드는 전송할 차례인 slave 노드를 방문함 
    • 마스터가 자신을 선택해 줄때만 말할 기회를 얻음
  • slave 장치들은 멍청
  • 문제:
    • polling overhead
    • latency (지연 시간)
    • single point of failure (하나 망하면 다 망)
• token passing:
  • 마스터 노드 없이 토큰을 노드들 사이에서 돌리면서 토큰 받은 노드가 말하게 함
  • 문제:
    • token overhead
    • latency
      • 토큰 하나만 돌리면 너무 느리면 토큰 두 개로 늘릴 수 있음
    • single point of failure
      • 어떤 노드가 토큰 버려버리면 아무도 말 못 함

 

 

 

 

 

 

 

출처: [Computer Networking: A Top-Down Approach]