[2장] 데이터 링크 네트워크 (Data Link Networks)

데이터 링크 계층

• OSI 7계층의 1, 2계층은 무엇을 담당?
  • 하나의 링크로 연결된 노드 사이의 비트묶음 (프레임) 교환
• 하나의 링크로 연결된 두 노드
  • 점대점 연결 네트워크: 가장 간단한 네트워크
  • 일반적 네트워크 구성의 기본 block
• 노드란? 노드의 실체는?
  • 망의 끝에서 사용자가 되면 host/단말
  • 망의 일부분이 되서 연결을 도와주면 switch/라우터
  • 결국엔 컴퓨터
• 링크란? 링크의 실체는?
• 점대점 연결에서의 통신의 실체
  • 비트 교환: 신호 인코딩 / 디지털 전송
  • 비트 묶음 교환: 프레이밍 (frame)
  • 오류 검출/복구

하드웨어 구성 요소 : 노드(Nodes)

• (단말/호스트, 스위치/라우터)
• 범용 (프로그래밍 할 수 있는) 컴퓨터로 구성된다고 가정.
  • 예) PC
• 때때로 특수한 목적의 하드웨어로 대체되기도 한다.
  
  
• 유한 메모리 (제한된 버퍼공간을 의미)
• 네트워크 어댑터 (or NIC: Network Interface Card)를 통해서 네트워크에 연결
• 프로세서는 빠르고, 메모리는 느림.
• 패킷은 store때 메모리에 있음 -> 주소를 봐야함 -> 어디로 갈지 결정

링크 (Link)

• 링크의 존재의 이유는 신호를 전달하는 것
• 데이터(신호) 전달을 위한 물리적 매체, 예) 케이블, 공기
• 뭐든지 링크가 될 수 있음 (ex. 실)
• Wired vs Wireless
  
• 전송 모드 (링크를 어떻게 쓰느냐)
  • Simplex (한방향으로만 가는 것)
    
  • 반이중(Half-duplex) (양방향으로 가는것, 동시X) -> ex. 무전기
    
  • 전이중(Full-duplex) (양방향으로 가는 것, 동시O)
    
    링크를 물리적으로 생각하면 안됨
    케이블 안에 선이 나누어져 있으면 Full-duplex
    
• 링크는 논리적 통로
  • 하나의 케이블에 여러 링크: 예) ADSL (전화선을 이용한 인터넷링크)
  • (당분간은 링크는 하나의 케이블)

모듈레이션: 데이터의 신호화

• 데이터를 링크, 즉, 물리적 매체를 통해서 전달하기 위해서
• 인코딩/모듈레이션(Modulation) : 데이터 ➡️ 신호
• 수신쪽에서는 반대 작업 (Demodulation) : 신호 ➡️ 데이터
• 모뎀 (Modem)? Modulation + Demodulation
  
• 신호의 종류: 전자기파 스펙트럼
  • 주파수(Hz)(초당 얼마나 움직이느냐), 파장(wave length)
  • 주파수가 높다는 것은 wave length가 짧다는 것)
    

신호? 데이터?
음파(아날로그) : data
신호 : 통신용
➡️ 데이터와 신호를 구분해서 써야 함

전자기 스펙트럼과 매체 특성

• 저주파일수록 전송 특성이 좋다. (장애물 잘 통과)
• 저주파는 고속의 데이터 전송에 한계.
  • 통신속도 (대역폭)와 비트 폭(length) 관계 (뒤에서 다시 설명)
• 통신의 발전: 저주파 ➡️ 고주파
• 고주파가 통신 특성은 나쁜데 대량의 데이터를 보낼 때 필요
• 적외선은 구리선을 통과할 수 없다

사용 가능한 유선 링크의 종류

링크 중에 무선과 유선이 있는데 유선을 살펴보자

• 위 3개는 구리선, 아래 3개는 광케이블
• 구리선은 twisted pair(LAN선) 과 동축 케이블로 나눌 수 있음으로 나눌 수 있음
• 속도보다 중요한건 거리
  • 케이블이 짧으면 중간에 노드를 써야함 ➡️ 단점임 ➡️ 길이가 긴 것이 좋음
• 전송 특성으로 구리선이 굵은 선이 좋다.

광케이블: Optical Fiber

송신쪽에서 빛을 쏘고 수신쪽에서 빛이 감지되면 1, 안되면 0으로 나타냄
core는 얇은게 좋음
core를 얇게 만드거나 거리를 짧게 해야함

가입자 선로 (Last-Mile Links)

• 너무 멀면 케이블이 있는 쪽에서 빌려 써야 함
• 집(사용자)와 인터넷 공급자 사이를 마지막으로 연결하는 링크
• 사용자가 선택해서 사용하는 링크이므로 중요!
• 과거: 모뎀을 통한 음성 전화 링크
• xDSL(Digital Subscriber Loop): 음성과 data를 FDM(Frequency Division Multiplexing) 방식으로 동시에
  • ADSL
    
    • 업로드보다 다운로드 하는 것이 훨씬 많음
  • VDSL
    
    • 거리가 길어지면 속도를 높이는데 한계가 있음
    • 아파트 지하에 광케이블 -> 집집마다 구리선을 씀

주파수를 분리

• Cable Modem
  - 6M - 100M; asymmetric
  - shared bandwidth
  

전화는 아파트가 있으면 지하에서 집집마다 전화선이 따로 있음. (전용링크: 남이랑 공유X)
케이블 TV는 안테나에서 여러 집을 굴러다님

Digital subscriber line (DSL)

• 전화도 쓰고 인터넷도 쓰면 집집마다 깔아주는 비용이 많이 들므로 전화선 가입자 망을 디지털로도 쓰게 만드는 것 (링크를 새로 깐 것 X)
• use existing telephone line to central office DSLAM
  • data over DSL phone line goes to Internet
  • voice over DSL phone line goes to telephone net

무선 링크 (Wireless Links): 일반

• 장점: 고정된 링크가 없음 (선이 없음)
  • 이동성 지원
  • 즉시 사용 가능 (전신줄 거칠 필요 없음)
• 단점: 공중으로 퍼져나감 (섞임)
  • 고주파 vs. 저주파
  • 인접한 링크 사이에 간섭이 일어날 수 있음
    • 전파 사용에 규제가 필요 - 라이센스 제도
  • multipath problem (고주파를 쓰니 문제가 발생함)
    • 전송 경로가 여러개 되어 문제가 생김
      
      이는 라이선스로 풀릴 문제가 안됨

이동통신 (Cellular Networks)

이동통신 할려면 기지국이 있어야 함

• 기지국 ↔️ 단말기
  • 셀: 하나의 기지국이 관할하는 지역
  • 핸드오프 (hand-off) 문제
    • 셀의 범위를 벗어나면 계속 이어줘야 함 (겹치게 함)
• 기술 발전
  • AMPS(전화, 주파수 분할) ➡️ PCS(GSM/CDMA)(TDMA/CDMA) ➡️ W-CDMA ➡️ 4세대 이동통신 ➡️ 5G
  • 전화 ➡️ data
  • 저속 ➡️ 고속
  • 사용자 ⬆️

셀이 크면 기지국이 적게 필요함 -> 옛날 방식
요즘에는 작게 만듦 (멀면 빠른 속도를 못 가짐)

고정 무선통신 (Wireless Fixed links)

이동성을 위해 쓴느 것이 아님. 즉시 사용이 가능하기 때문에 사용

• 무선 고속 전용 링크
  
  • 본사와 지점이 있음. 근데 빈번히 데이터를 주고 받아야 하는데 사이에 국경선이 있음. 땅 파서 넘어가기 힘드므로 접시 안테나 큰 것을 단다.
  • 퍼져서 에러가 날 가능성이 높음 -> 유선만큼 안정적이지 않음.
• 무선 가입자망
  
  • 집집마다 링크를 뿌려줘야 하는데 집이 수십키로 떨어져 있으므로 아까움.
  • 섬에도 해줘야 함.
  • 전화국에서 무선으로 쏘자
  • 셀하고 차이점은 셀은 이동통신이므로 신호를 정방향으로 쏴야함
  • 하지만 집은 안 움직이므로 지향성으로 쏴야 함.

위성 통신 (Satellite system)

• 정지궤도 방송/전화
  • 약 36,000km 고도
  • 정지궤도는 대부분 단방향
• 정지궤도 데이터 (VSAT)
  - 양방향으로 쏘고 싶으면 접시에서 접시로 통신
  

위성 링크는 전파지연시간이 길다. -> 2번 왔다 갔다 함
이유) 위성은 쏘아올리고 고치기 어렵고 용량을 늘리기도 어려움.

• 중궤도
  - 10,000 ~ 20,000km, 단방향
  - GPS, 단방향

  정지궤도와 중궤도는 지상에서 위성으로 쏘는데 한계가 있음

• 저궤도 통신

  • 부지런히 움직여야 함 -> 엔진이 있음
  • 전화: Iridium
  • 인터넷: 스타링크
    • 540 ~ 570km 고도, 양방향
    • 4,425대 운용

단거리 무선통신 (Short Range)

• Public (license-free) band 이용
• 적외선 통신 (리모컨, 프린터)
• 무선LAN(WiFi) - IEEE 802.11
  • WAN (wide Area Networks)
  • LAN (Local Area Networks)
  • PAN (Personal Area Networks)
• Bluetooth (3~4m) (1~2mega)(전력 save 해야 함)
• ZigBee / IEEE 802.15.4
  • 원격 제어용
  • 거리는 집 하나 정도 (LAN보다 짧고 PAN보다 넓음)
  • 속도는 짧음
  • 배터리가 오래 감

인코딩(Encoding): 개요

• 신호(Signal)는 물리적 매체를 통해 전달된다.
  • 디지탈 신호
  • 아날로그 신호
• 데이터는 디지탈 데이터만을 취급.
  • 아날로그 데이터는 디지탈 데이터를 변환
• 문제: 발신지에서 목적지로 보내려는 이진 데이터를 전달될 수 있는 신호로 인코드 해야 함.
• 보다 일반적인 용어는 변조 (Modulation)
  

중계하는 방식은 아날로그/디지탈 방식이 있음
신호가 가다보면 잡음이 끼면서 줄어진다 ➡️ 앰프 사용(잡음도 증폭이 됨)
이 문제를 해결한 것이 디지탈 전송

• 신호에 있는 데이터를 뽑아서 다시 신호화 ➡️ repeater 사용

디지털 전송 (Transmission)

• 신호 중계 방법 (통신망 안에서의 전송 방법)
• 아날로그 전송
  • 신호를 단순 증폭
  • 즉, 앰프(Amplifier) 사용
• 디지털 전송
  • 신호에서 데이터를 복원하여 다시 신호화
    • 디지털 데이터를 담은 신호만 사용 가능
  • 즉, 리피터(repeater) 사용
• 거의 모든 전송 방법이 디지털 전송 사용
  • noise 제거
  • 기기 비용
  • 부가 기능 추가 가능
• 요즘에 앰프보다 리피터가 훨씬 쌈

데이터 전송 (Transmission)

옛날에 다 쓰였지만 요즘엔 통신망에서 아날로그는 포기함. ➡️ data 전송을 쓰기 시작함
신호는 analog를 써도 상관 없음(신호에 담겨있는 data가 digital 전송을 쓰려면 analog는 안됨)

PCM (Pulse Code Modulation)

• Sampling Theorem:
  Sampling rate $\approx$ 2 x Highest signal frequency (제일 고주파, 제일 자주 바뀌는 곳)
• 4 kHz voice = 8 kHz sampling rate
• Represent samples as pulses (PAM)
• Quantize the samples (PCM)
• 8k samples/sec x 8 bits/sample = 64 kbps

Pulse Code Modulation

• A2D
  • 주기적으로 sampling ➡️ 반올림
• D2A
  • 주기 간격으로 연속 변환
  • 하나의 샘플을 길게 표현하는게 좋음
  • 손실을 줄일려면 sampling을 자주 해야 함
  • 샘플링을 자주하면 data가 늘어남 ➡️ 적당한 수준을 찾아야 함

변조: Amplitude Modulation

주파수 변조: Freq. Modulation

주파수가 달라 0, 1 구분

위상 변조: Phase Modulation

PSM (Phase Shift Modulation)
0$\degree$, 180$\degree$
0$\degree$, 90$\degree$, 180$\degree$, 270$\degree$

이동통신의 속도가 2배 ⬆️

• 무선랜 속도 등 모든 통신 분야에서 마찬가지
• 어떤 방법으로? modulation 기법을 중첩

참고: 아날로그 데이터 ➡️ 아날로그 신호

예: Amplitude Modulation (AM)

옛날에는 주파수를 받으면 아날로그 데이터의 크기를 바꿔가면서 보냄
하지만 0, 1을 안담고 있어서 리피트가 불가능하고 앰프만 가능 ➡️ 음질에 한계가 있음

Digital Transmission 가능?

음성 데이터의 디지털 전송

Non-Return to Zero (NRZ)

• 노드 내부의 데이터 표현과 일치 (즉, 별도의 인코딩 필요 없음)
• 문제점: 1 또는 0이 연속되는 경우
  • Low signal(0)의 경우 수신자는 신호가 없는 것으로 오해할 수 있음
  • High sigmal(1)의 경우 전류가 계속 흐르게 되고, 기저 전압의 혼돈을 야기
  • 클럭(clock) 복구가 불가능
    • 송신자와 수신자의 클럭이 맞지 않으면 잘못된 비트 인식
    • 수신자가 송신자의 클럭에 자신의 클럭을 맞추는 작업

속도: 1Mbps 면 비트폭은 $1mega\times10^{\frac{1}{6}}$
1msec만큼은 1이면 올리고, 0이면 내리고 한다.
수신자는 자신의 clock을 기반해서 가운데에서 sampling을 진행 함 -> 0, 1인지 찾는다.
하지만 송신자와 수신자의 clock이 조금이라도 차이가 있으면 정확하게 맞출 수 없다.
컴퓨터 내부에서는 clock 문제가 생기지 않는다 ➡️ CPU, memory, adapter 내부에서 clock을 공유하기 때문에
따라서 NRZ는 통신에서 잘 안쓰고 주변기기(ex. 프린터, disk)에서 쓰임

NRZI and Manchester

• Non-return to Zero Inverted (NRZI)
  • 1을 인코드할 경우 현재의 신호로부터 중앙 지점에서 전이(mid-transition)을 하고, 0을 인코드할 경우 현재의 신호 상태를 유지함; 연속되는 1의 문제를 해결.
  • clock을 복구 가능 ➡️ 수신자 기준에서 맞출 수 있다.
  • 연속되는 0의 문제는 해결할 수 없다.
• Manchester
  - 0: up (⬆️) transition, 1: down (⬇️) transition
  - NRZ 방식으로 인코드된 데이터와 클럭을 배타적 논리합을(XOR) 시켜서 바꾼다; 50% 효율을 갖는 문제점
  - 모든 clock에서 mid-transition
  - 매 bit마다 clock recovery 가능
  
  

mid-transition의 의미는? 바꾸는 곳의 시점

Mid-trasition의 의미 (Manchester 코드 예)

• 송신 쪽에서, $M_i = Data_i ⊕ Clock^S_i$
  • 참고. X ⊕ 0 = X, X ⊕ 1 = X', X ⊕ X = 0
• 수신된 $M'_i$에서 0/1을, 즉, $Data_i$을 인식한 후,
  • 전송 중 오류는 없다, 즉, $M'_i$ == $M_i$ 가정
  • ($M'_i ⊕ Data_i$)을 하면,
  • ($M'_i ⊕ Data_i) = (Data_i ⊕ Clock_i^S) ⊕ Data_i = Clock_i^S$
  • 즉, 수신자가 송신자의 클락을 꺼낼 수 있으며, 따라서 동기화를 할 수 있다.
  • 결론: Manchester zhemsms Data에 Clock을 얹어서 동시에 보내는 것.
  • 접근 방식의 의미? (넓게 보면, in-band signaling)
• 송신자가 XOR를 해서 보냄
• 수신자는 XOR을 함
• 송신자는 data만 보내면 clock 문제가 생겨 자신의 clock을 exclusive해서 보냄.
  

양쪽이 data만 주고 받을 수 없다. -> control이 왔다 갔다 해야함
이때 data와 control을 별도의 링크로 주고 받으면 out-of-band ➡️ 요즘 대세
만약 링크 하나로 같이 보내면 in-band-signaling

4B/5B

B는 bit의 약자

• 아이디어
  • 데이터를 매 4bits마다 5-bit코드로 인코드한다, 이 5-bit의 코드는 앞에는 1개, 뒤에는 2개까지 0이 오도록 제한해서 선택된 코드이다. (따라서, 0이 4개 이상 연속되는 나올 수 없다.)
  • 5-bit 코드는 NRZI 인코딩을 이용해서 전송된다.
  • 0의 연속을 극복
  • 효율 80%를 달성.
    • $\frac{4}{5}$가 data, $\frac{1}{5}$는 0을 피하기 위해 사용

비트(신호)의 실체 정리

프레이밍 (Framing) : 개요

• 데이터를 끝없이 보낼 수는 없음. (특히, 패킷 네트워크에서는)

• 문제

  • 비트(bit)들의 연속을 하나의 묶음(프레임: frame)으로 자르는 것
  • 수신 쪽이 프레임을 인식할 수 있도록 봉투를 씌워서 묶는 것.
  • 프레임의 처음과 끝 인식
    • 기타 추가 정보 기입 (추후에)
      

• 전형적으로 네트워크 어댑터에서 구현됨

• 어댑터는, 송신 경우, 호스트 메모리로부터 (데이터 + 헤더 일부분)을 가져와서 프레임을 만든다 (encapsulation).
  

바이트 중심 프로토콜 (Byte-Oriented Protocols)

보초 방법 (Sentinel Approach)

• BISYNC
  
• IMP-IMP, PPP
• peer-to-peer interface의 시작
• SYN: frame이 시작한다는 뜻
• 문제점: 프레임의 데이터 부분에서 ETX 문자가 나올 경우
• 해결: 확장 문자 (escaping character) 사용
  • BISYNC의 경우 DLE(delete)문자를 ETX문자를 앞에 부착
  • IMP-IMP의 경우에는 DLE 문자 앞에 DLE 문자를 부착

바이트 수 방법 (Byte Counting Approach) - DDCMP

• data가 몇 byte인지 count를 넣음
• STX와 ETX(보초)가 없음. -> 데이터가 몇 byte인지 숫자를 씀
• 문제: 개수 (Count) 항이 잘못된 경우 (framing error).
• 해결: 순회중복검사(CRC)가 실패하므로 오류 검출

protocol 메시지 (Protocol Data Unit: PDU) Format
- "peer간 인터페이스"의 실체

비트 중심 프로토콜 (Bit-Oriented Protocols)

HDLC: High-Level Data Link Control (also SDLC and PPP)

• 특별한 bit-sequence를 프레임의 앞과 뒤에 붙여 프레임을 구분: (0111110) 앞뒤로 보초를 세움
  

비트 삽입 (bit stuffing)

• 송신자: 메세지의 중간에 연속되는 5개의 1이 나오면 0을 삽입함
• 수신자: 1을 연속해서 5개 받았을 때, 다음 비트를 본다:
  • 다음 비트가 0이라면: 그 비트를 삭제함
  • 다음 비트가 10이라면: 프레임의 끝
  • 다음 비트가 11이라면: 오류

오류 검출 코드 (Error Detecting Code)

• 데이터 영역 안에 오류가 있는지를 없는지를 알아내는 부가 데이터
• 예: parity
• 판단 기준
  - 크기 면에서, EDC << data; 오류가 없는 경우 단순 부하이므로 (overhead)
  - 효율 면에서, 오류 검출율이 높아야 함. (검출율 정의는 다음 페이지)
  - 비용 면에서, f() 연산에 시간이 적게 소모되어야 함.
  

오류 검출율

• 오류 검출율이 100이 될 순 없음
• EDC가 완벽하게 오류를 검출할 수 있을까?
• 검출 실패 ➡️ 시스템 integrity 상실
• 매우 높은 오류 검출율 + 중복해서 오류 검사

2차원 패리티 (Two-Dimensional Parity)

• 검출율이 높진 않음

인터넷 체크섬 알고리즘 (Internet Checksum Algorithm)

• TCP와 IP가 사용
• 보낼 데이터를 16-bit로 쪼갬, 계속 더함
• 아이디어: 메시지를 16-bit의 정수의 연속으로 간주하고, 각 정수들을 16bit 1의 보수 연산을 사용하여 모두 더한다. 그리고 그 결과의 1의 보수를 얻는다. 이 16-bit 숫자가 체크섬(checksum)이다.
• 검출율 ⬇️
• 수신자는 데이터가 오면 다 더해서 EDC랑 비교
• 덧셈을 할 때 1의 보수 연산을 수행 함
• 송신자를 sum의 보수를 사용, 수신자는 다 더해서 0이 나오는 것 확인
  

u_short
cksum(u_sort *buf, int count) {
	register u_long sum = 0;
    while (count--) {
    	sum += *buf++;
        if (sum & 0xFFFF0000) {
        	/* carry occurred, so wrap around */
            sum &= 0xFFFF;
            sum++;
        }
    }
    return ~(sum & 0xFFFF);
}

순회 중복 검사 (Cyclic Redundancy Check: CRC)

• 더하기보다 복잡한 나누기 사용: 나머지를 오류 검출코드로 전송
• 젯수로 사용될 송수신 사이에 약속된 비트 패턴: C
  EDC ⬅️ f(data, C <- 나누는 수)
• 보낼 메시지: M
• 오류 겸출을 위해 추가되는 정보: F (즉, EDC)
• 송신쪽
  • (M || F) % C = 0이 되도록 F를 생성
    • 즉, (F에 나머지를 넣어서) 전체 프레임이 C로 나누어 떨어지도록 함.
  • (M || F)를 전송
  • 예) C=1101, M=10011010이면
    • F = 101를 생성 (10011010101은 1101로 나누어 떨어짐)
    • 10011010101 전송
• 수신쪽
  • 수신된 메시지 전체를 C로 나누어서
    • 나누어 떨어지지 않으면 ➡️ 오류 발생
      • 나누어 떨어지면 ➡️ 오류가 없는 것으로 간주 (확신을 할 순 없음)

CRC의 개념적 이해

• 주의: 실제는 10진수 연산 사용하지 않음. 다항식연산 (XOR 연산)
• 예) 송수신자가 약속하는 젯수 C = 11
• 송신자가 data 331을 보내려면,
  • 331과 함께 오류 검출용 숫자를 추가해서 전송.
  • 이 경우, 331x가 11로 나누어 떨어지도록 계산해서 1을 추가.
  • 즉, 3311을 전송
  • 일반적으로, 추가되는 자릿수는 (C의 자릿수 - 1)
• 수신자는 받은 비트 전체 (프레임)를 약속된 C로 나누어 봄
  • 이 경우, 전송 중 오류가 없다면, 수신된 3311을 11로 나누어 봄
    • 나머지가 0이면, 오류가 없다고 간주
      • 나머지가 0이 아니면 (예, 3311, 또는 2311), 오류 검출
  • 오류가 발생하더라도 검출에 실패할 수 있음. (예, 2211)
• 오류 검출율은 C의 값과 관계 있음. (예, C=10으로 정한다면 ...)

CRC의 성능

• 오류 검출율
  • 비트 패턴 C의 선택이 좌우
  • 수학적 분석에 의해 잘 잡으면, (분석 과정 슬라이드 참조)
  • 32비트 코드 사용하면, 1500 byte 이상의 데이터에 대해서도 99.99...의 겸출율
• 연산 속도
  • 전송 속도보다 늦으면 CRC 계산이 끝나는 시간이 전송 시간을 결정
  • 가능하면 네트워크 어댑터 (NIC) 내에서 하드웨어로
• 빠른 연산과 분석을 위해
  • 다항식 연산 (즉, ⊕-연산)을 사용 <- 시간이 오래 걸림
• C 값에 대한 송수신 쪽 합의 ➡️ 표준화된 C 사용 ("CRC Code")
• 세부 사항은 옵션. 송신/수신 쪽에서의 CRC 동작 정리는 필수!

순회 중복 검사: 송신자 세부 사항

• n-bit의 메시지는 n-1차 다항식으로 표현
  • 예) MSG=10011010은 $M(x) = x^7 + x^4 + x^3 + x^1$에 대응됨
• (k+1) 비트 젯수 패턴 C에 해당하는 k차 다항식 C(x)를 설정
  • 예) C=1101은 $C(x) = x^3 + x^2 + 1$
• M(x)에 $x^k$을 곱한다. (F가 들어갈 자리를 포함한다.)
  • $x^{10} + x^7 + x^6 + x^4$ (10011010000)
• C(x) (1101)로 나눈다.
  
• 나머지를 추가한 P(x)를 전송한다.
  • 10011010000 - 101 = 10011010101
  • P(x)는 C(x)로 나누어 떨어진다.

Error Pattern: E(x)

• 전송하는 프레임: P(x)

• 수신된 프레임: P'(x)

• 전송 중 발생한 오류를 프레임에 대응되는 형태로 나타내면: E(x)

• 관계

• 주의:

  • E(x)의 값을 구하는 것이 목적이 아님.
  • 오류가 없었다면, E(x)=0이고, P(x)=P'(x)라는 사실.
  • 오류가 있었다면, E(x) != 0 이고, P(x) != P'(x)라는 사실이 중요
  • 결국, E(x)는 오류 패턴
    • E(x)가 0인지 아닌지를 판단할 수 있도록 C를 설계하는 것이 분석 목적

순회 중복 검사: 수신자 세부사항

• 수신자는 송신자가 보낸 P(x)에 전송 중 오류가 반영된 P'(x) = P(x)+E(x)를 받는다. E(x)=0은 오류가 없다는 의미
• 수신자는 (P(x) + E(x))를 C(x)로 나눈다.
• 나머지가 0이 아니면, 즉, (P(x) + E(x)) % C(x) != 0
  • P(x) % C(x) = 0이므로 E(x) != 0 ➡️ 오류 발생
• 나머지가 0이면, 즉, (P(x) + E(x)) % C(x) = 0
  • E(x) = 0 ➡️ 오류 없음
  • E(x) != 0 이면서 E(x) % C(x) = 0
    ➡️ 오류는 발생하였지만 오류 검출 실패
  • 두 번째 경우가 거의 일어나지 않도록 오류 패턴을 분석해서 C(x)를 선택한다.

CRC 코드

• 하드웨어에 심어져 있음
• 길면 길수록 overhead가 증가함
• 보낼 데이터가 크면 긴것을 써야 함

보통 사용되는 C(x) 다항식:

CRC의 하드웨어 구현 (참조)

• 1-bit Latch와 XOR Gate를 비트패턴 C에 따라 조합
  • 즉, (|C| - 1) 길이 shift-register의 비트 사이에 XOR 배치
  • 모든 비트 통과 후, Latch에 남아 있는 결과가 CRC 비트
• 참고: frame format에서 CRC의 위치?
  데이터 뒤에 있다.

CRC는 왜 항상 프레임 끝에 오는가?

• 예) C = 1101
  Message 예) 송신 경우, 10011010; 수신 경우, 10011010101
  
  전송과 CRC 계산이 동시에

CRC에 대해 간단히 설명하시오.

• 전송되는 데이터의 오류 여부 확인을 위해 부가되어 보내지는 오류 검출 코드
  • 송신자가 계산에서 추가, 수신자가 확인
• 오류 검출율 매우 높고, 하드웨어 구현이 가능해서 거의 모든 링크 전송에서 사용
  • 예) 이더넷/무선랜 어댑터에서 CRC-32 사용;
    99.999...% 검출율
• 자세한 설명?
  • XOR-나누기 연산 기초
  • 프레임 전체가 약속된 젯수로 나누어 떨어지도록, CRC 값을 만들어서 이를 데이터 뒤에 붙여 전송
  • 수신자는 프레임을 약속된 젯수로 나누어서 나머지가 0이 아니면 오류로 판단
  • 나머지가 0이면 오류가 아니라고 간주

신뢰성 있는 전송

• 오류에 의해 변질된 프레임의 복구
• 오류 수정 코드 (Error Correction Codes: ECC)
  • 순방향 수정 (Forward Error Correction: FEC)
  • detection하는데 4byte + 수정 -> 많이 듦 -> error가 안나면 다 버리는 것 => 유선에선 잘 안쓰임
  • 부하가 많음
  • 오류가 많이 나면서 대안이 없을 적(전화 같은 경우)에 많이 쓰임
• 자동 반복 요청 (Automatic Repeat reQuest: ARQ): 재전송
  • ACK(수신자가 오류 검출을 기반해서 보냄)와 타임아웃(비정상적인 경우 탈출) (Acknowledgements and Timeouts) : CPU에서 메모리가 함
  • 역방향 수정 (Backward Error Correction)
• 참고
  • 오류 중에는 프레임 자체가 성립이 안 되는 framing error도 있음.
    • 이 경우는 수신 쪽이 frame 수신 여부를 인식하지 못함.
    • 즉, frame loss
    • 의미는?

오류 수정 코드 (Error Correcting Codes)

• 예: 2차원 패리티에서는 모든 1비트 오류를 수정 가능
• Forward error correction (FEC)
• 재전송이 용이하지 않은 경우 유용
  • 예) 전화 같은 실시간 통신
    • 재전송을 통해 늦게 수신된 데이터는 가치가 없음

재전송을 통한 오류 복구

• 타임아웃, 재전송용 버퍼 처리 등 필요
• 어댑터에서 단독으로 처리하는데 한계
• 2계층 기능이지만, 노드 내 소프트웨어로 처리
  

ARQ: 응답 (ACK) 및 타임아웃

• ACK가 오면 잘받았구나 판단 ➡️ 전적으로 의존 X(변질되거나 끊어지거나 한참 뒤에 올 수도 있음)
  • 재전송에 대비해서 buffer에 두고 잘못되면 버려야지 하고 timeout을 걸어놓음
• 송신자는 잘못될 수 있어서 버퍼에 담아두고 timeout을 걸어둠
• 수신자는 오류가 없으면 ACK를 보냄

(b) 보낸 데이터가 오류가 생김

• 송신자: timeout을 걸어 놓고 대기, timeout으로 잘못된것을 알고 재전송함
• 수신자: 잘왔으면 ACK 안왔으면 아무것도 안함

(c) 잘 받아서 '응' 했는데 그 '응'이 에러가 남

• 송신자: 버퍼에 담아놓고 timeout 걸어두고 전송, ACK가 안오므로 재전송
• 수신자: 잘왔네 하고 ACK 보냄
  오다가 벼락 맞음
  Frame마다 번호를 붙힘 ➡️ 수신쪽에서 중복인지 아닌지 판단 가능
  ACK에도 번호를 붙
  Frame0이 다시 오면 버림. 하지만 꼭 ACK를 보내야 함

(d)Timeout을 너무 짧게 잡음
Timeout = RTT(2 $\times$ propagate) + $\alpha$

• 송신자: Frame을 보냈는데 ACK1이 빨리 오네
• 수신자: ACK를 다시 보냄, 무시

- 송수신을 모두 보는 것은 현실에서 불가능
- 상대방에서 오는 메시지로만 상대 상태를 파악

송신/수신을 별도로!
- 송신자 동작?
- 수신자 동작?

ARQ: 순서번호 (Seq. #)

• ACK의 분실 경우: 증복 data 문제 발생
  • 순서번호 (즉, frame ID) 필요
• 순서번호
  • 거의 모든 프로토콜에서 전송되는 메시지에 부착
  • 프레임과 ACK 모두에 부탁
    • ACK에서는 n 대신 (n+1) 사용하기도 함
      - 즉, n은 잘 받았고, 다음은 (n+1)
  • 헤더의 일부분으로
• 중복된 프레임 처리
  • 수신된 중복 data는 discard
  • 그러나 ACK는 반드시 전송

순서 번호 포함된 ARQ - 스스로!

Automatic Repeat Request

• ACK의 길이는 거의 1로 생각, 하지만 전파지연시간이 있음
• ACK: 잘 받았다라는 의미
• NAK: 잘못됐다는 의미
  NAK오면 재전송하면 되므로 timeout을 안 걸어도 된다? ➡️ frame 자체가 가면서 error가 생기면 판단을 못할 수도 있다., NAK도 오다가 상실될 수 있음 ➡️ NAK도 잘 안씀

Piggybacking

• 송신자는 보낼 데이터가 끝없이 많다.

Stop and Wait: Timing 분석

• 보내고 stop하고 ACK를 기다림
• 성능을 분석하고 나면 링크를 몇% 사용하고 있나?

정지대기 (Stop-and-Wait)

• 문제점:

  파이프를 꽉 채운 상태로 유지하지 못함.

• 예: 1.5Mbps link x 45ms RTT = 67.5kb (8KB). 프레임의 사이즈가 1KB인 경우, 정지대기(stop-and-wait)는 링크 용량의 1/8만을 사용한다. 송신자는 ACK를 기다리기 전에 8개의 프레임을 보낼 수 있는 것이 바람직하다.

슬라이딩 윈도우 (Sliding Window)

• 놀게 하지말고 파이프를 채워보자
• 아이디어: 송신자가 ACK를 받기 전에 여러 개의 프레임을 전송할 수 있도록 한다. 따라서, 파이프가 꽉 차게 된다.
• ACK가 왔을 때, 누가 왔고 안왔는지 모름
• ACK를 받지 않은 상태에서 보내지는 프레임(outstanding frame)이 복수로 늘어난다. 단, 그 수는 제한된다 (window size: 한도를 설정).
  • 모두 오류 제어 대상. 순서 번호 필요.
  • stop&wait는 sliding window의 window size가 1인 경우
• 각각의 프레임에 대해서는 ARQ, 즉, ACK/timeout&재전송을 수행
  • ACK #n의 의미를 일관성 있게 정의해서 사용. : 각각에 대해 ARQ 정의
• 즉, 효율 높은 오류 제어
  - 버퍼링보다 오류가 핵심
  

Sliding Window Protocol의 성능

첫번째 보낸 얘에 대해서 ACK가 옴 ➡️ Window를 하나 더 늘려서 보내도 됨

시간 진행 표시법 및 해석

• 두가지 표시법 중 어떤 것 사용?
  
• 성능 분석이 목적?
• 시간 상황이 겹치는 세부 상황 분석 필요?

Sliding Window 개념: 오류 없는 경우

(회색 부분은 더 보낼 수 있는 프레임 수인 윈도우 표시. 버퍼 표시 아님)

ACK3은 ACK를 모아서 보냄 (누적 ACK)

슬라이딩 윈도우의 오류 복구

• 복수의 outstanding frame 중 어떤 프레임에서도 오류 발생 가능
  • 따라서, 모든 프레임은 개별적으로 재전송 준비 (버퍼 + 타임아웃) 되어야 함.
• 오류 처리 정책
  • Go-Back-N: 오류 발생한 지점부터 새 출발
  • Selective-Repeat: 오류 발생한 프레임만 재전송 (buffering이 필수)
    - 장점: 효율적
    - 단점: 복잡함

Go-back-N 구현의 옵션 사항

: 우리가 배울 옵션

• 수신 1: out-of-order 프레임을 저장할 것인가?
  • discard or store (선택사항)
  • 버리면 빠름
  • 저장하면 나중에 빵꾸가 나면 일찍 탐지할 수 있음
  • 어떤 선택도 가능. Why? 송신 쪽에서 Go-back-N!
• 수신 2: out-of-order 프레임에 대해서 Ack를 보낼 것인가?
  • no Ack or 중복 (duplicate) Ack (누적 Ack 규칙을 지켜야 함)
  • 어떤 선택도 가능. Why? 송신 쪽에서 Go-back-N!
• 송신: outstanding frame을 언제 재전송?
  • 모든 outstanding을 한꺼번에 or 각자의 timeout에 재전송
  • 어떤 선택도 가능 (timeout 값에 관계없이 오류는 복구됨)
• 어떤 선택을 해도 Go-back-N
  • TCP의 Go-back-N에 기초

오류 처리 정책: Go-Back-N 재검토

• 오류 발생한 N부터 다시 출발 (N 이하를 무조건 다시 보낸다는 의미 아님)
• 핵심: ACK는 ~까지 잘 받았다"는 의미의 누적(cumulative) ACK 사용
  • 교재/강의는 "~까지 잘 받았고, 다음은 몇 번"이라는 방식 사용
  • ACK를 보내는 시점은 수신자의 선택
  • 진행을 돕기 위해서 ACK를 보낸다면, 중복 ACK만 가능
• 수신 쪽에의 버퍼링은 수신자가 독립적으로 결정
  • 버퍼링 안해도 됨.
  • 교재/강의는 버퍼 유지하면서 순서 바뀐 데이터를 수신. 단, 버퍼링이 selective repeat을 의미 하지는 않음.

오류 처리: Selective-Repeat

• 필요 조건
  • 수신 쪽은 out-of-order 프레임 수신. 버퍼링 필수.
  • 수신 쪽의 정확한 수신 상황 정보를 송신 쪽에서 알려주어야 함.
    • "~은 잘 받았다"는 개별(individual)/선택(selective) ACK 필수

Sliding Window 세부 사항

• Sliding Window는 오류제어 프로토콜
  • 각각의 outstanding frame에 대해 기본적으로 ARQ 수행
  • 복수 개의 outstanding frame 처리를 위해 buffering 추가
• (Go-Back-N, Selective-Repeat) 선택은 송신자의 결정
  • 송신자의 재전송 방법; 수신자의 적절한 응답 필요
  • 수신자의 buffering은 별도 문제
• 버퍼링
  • Sending Buffer : 필수 (재전송)
  • Receiving Buffer
    • Selective-Repeat : 필수 (out-of-order 프레임 반드시 저장)
      • Go-Back-N : 성능 향상을 위한 option
  • 수신자가 out-of-order를 저장한다고 Selective-Repeat은 아님
• 송신자가 Selective-Repeat를 하기 위해서는 수신 상황 정보가 필요
  • 수신 쪽에서 송신 쪽으로 selective/individual ACK를 보내 주어야, 송신 쪽에서 selective repeat 가능

프로토콜의 구현

• 오류제어 이전까지는 Adaptor (NIC)에서 하드웨어로 구현
• 오류 제어는 소프트웨어로 구현되는 첫 프로토콜
• 어떻게 프로그램 할 것인가? 얼마나 어려울까?
• 송수신 양쪽을 보는 것은 이론적 설명에서만.
  • 송수신 각각이 독립적으로 동작.
  • 프로토콜의 동작에 대해서 확실한 이해 필요.
  • 특히, 비정상 상황에 대해서.
• 난이도는?
  • concurrent and distributed program
  • 설계 과정이 절대적으로 필요!

Go-Back-N의 구현

• 송신/수신쪽 독립적으로 동작
• 송신쪽 동작
  • 오류 제어: 각 outstanding frame에 대해,
    • 재전송 버퍼에 저장; 타임아웃 설정
    • ACK 받으면, 타임아웃 해제, 재전송 버퍼 해제
    • 타임아웃 발생하면, 재전송
  • (버퍼 + 윈도우) 관리
• 수신쪽 동작
  • 오류 제어: (누적) ACK 전송
  • 버퍼 관리
    (out-of-order 프레임을 저장은 하고, ACK는 따로 보내지 않는 방식)

슬라이딩 윈도우(Go-Back-N) 세부 알고리즘(1)

• 송신자
  • 각 프레임에 순서번호를 할당 (SeqNum): 각 outstanding frame의 ID
  • 세 개의 상태 변수를 유지
    • 송신창 - send window size (SWS)
    • 마지막으로 받은 ACK의 프레임 번호 - last acknowledgment
    • 마지막으로 보낸 프레임 - last frame sent (LFS)
  • 다음 항등식(invariant)을 유지: LFS - LAR + 1 $\le$ SWS
  • 
  • LFS보다 작은 얘들: 보낸 얘들
  • LAR보다 큰 얘들: ACK를 아직 못 받은 얘들
  • 사이는 보냈는데 아직 ACK를 못 받은 얘들
  • 상위 계층에서 전송 요청을 받으면, 1) LFS를 증가시키고 (LFS 증가가 불가능하면 wait), 2) 타임아웃을 설정한 뒤, 3) 프레임을 전송. (누구에게?)
  • ACK를 받으면, 1) 타임아웃을 해지하고, 2) LAR을 증가시키며, 3) 이에 따라 새로 창이 열리며 전송이 가능.
  • 타임아웃이 걸리면, 1) 타임아웃을 설정한 뒤, 2) 프레임을 재전송
  • SWS만큼의 프레임은 버퍼에 유지 -- 재전송에 필요

슬라이딩 윈도우(Go-Back-N) 세부 알고리즘(2)

• 수신자

  • Out-of-order 프레임을 저장하는 Go-Back-N 알고리즘

  • 세 개의 상태 변수를 유지

    • 수신창 - receive window size (RWS)
    • 받아들일 수 있는 마지막 프레임 - last frame acceptable (LFA)
    • 수신 예상 프레임 - next frame expected (NFE)

  • 항등식 (invariant)을 유지: LFA - NFE + 1 $\le$ RWS
    

  • SeqNum의 프레임이 도착하면

    • If NFE $\le$ SeqNum $\le$ LFA ➡️ 받아들임 (accept);
      - 중간에 빈 곳 없는 연속되는 데이터는 상위 계층으로 deliver
    • If (SeqNum $\lt$ NFE) or (SeqNum $\gt$ LFA) ➡️ 버림 (discarded)
      - SeqNum $\lt$ NFE는 ACK 전송 필요
    • 누적 ACK(cumulative ACK)를 보낸다. (NFE 값으로)

순서 번호 공간 (Sequence Number Space)

• 순서번호는 오류제어에서 필수
• 순서번호는 data와 함께 header로 들어감
• 프레임 헤더의 필드는 한정된 공간 (많이 사용하면 overhead 증가)
  • 결국, 순서 번호는 순환되며 사용
• 순서번호 공간: 가능한 순서번호 구간
  • 예) 4-bit 필드 ➡️ [0..15] (순환)
• 0, 1, ..., 15까지 갔다 0으로 왔는데 아직 이전 0의 ACK가 안왔으면 위험함
• 문제: 순서번호 필드를 얼마로 잡아야 안전하겠는가?
  • Window size (N) ↔️ 순서번호공간 (|seq #|)
  • 반대로, 주어진 순서번호 공간에서 최대 outstanding 프레임, 즉, 송신자 기준 WindowSize는 얼마까지 늘릴 수 있나?
• 순서번호 공간은 현재 전송 중인 프레임의 수보다 커야 한다.
  • 어떤 프레임이 오류 및 재전송의 대상이 될지 모르므로, outstanding Frame 각각은 서로 다른 SeqNum를 갖고 있어야 한다.
• outstanding 프레임의 최대 수 = SendingWindowSize (SWS)
• 따라서, 순서번호공간 크기 > SendingWindowSize(SWS) ⬅️ 충분?

순서 번호 공간 (2)

• "SWS $\le$ 순서번호공간 크기"는 불충분.
  • 불충분한 예) 다음 장 그림 참조
  • 3-bit SeqNum 필드를 가정(0..7)
  • SWS=RWS=7
  • 송신자는 프레임 0..6을 보냄
  • 성공적으로 도착했지만, ACKs를 잃어버림
  • 송신자는 0..6을 재전송 (retransmit)
  • 수신자는 7, 0..5를 기대하지만, 재전송된 0..5를 받게 됨
• 결론 : SWS < 순서번호공간 크기의 반
  • 즉, WindowSize, 즉, 최대로 보낼 수 있는 outstanding 프레임의 수는 순서번호공간의 반보다 작아야 안전하다.
  • 구체적으로, SWS < (MaxSeqNum + 1)/2 이 정확한 규칙.
• 직관적으로 설명하면, SeqNum는 순서 번호 공간의 1/2 사이를 오고 감.

Out-of-order Receiving: dilemma

Example:

• seq #'s: 0, 1, 2, 3
• window size=3
• receiver sees no difference in two scenarios!
• incorrectly passes duplicate data as new in (a)

Q: what relationship between seq # size and window size?

(a) 셋 다 오다가 벼락을 맞음 -> timeout 걸려서 0이 재전송
(b) packet 0은 잘 갔는데 packet 3을 잘 못 감

• 수신자가 구분할 근거가 없음

Sliding Window Protocol 평가

• 복잡!
• 왜? "all-in-one" protocol (한 프로토콜로 3가지 해결)
  • 오류 복구
  • 복수의 프레임 전송 + 버퍼 관리
  • 프레임 순서 유지
• Separate concerns!
  • 각 문제를 따로 푼다면?

동시 논리 채널 (Concurrent Logical Channels)

• 하나의 점대점(point-to-point)링크를 통해 여러 개의 논리적 채널을 동시/다중 송신함.
• 각각의 논리적 채널은 정지 대기(stop-and-wait)방식으로 운영됨
• thread를 생각하면 됨.
• 신뢰성 문제: stop-and-wait
• 효율: parallel 논리 채널 운영 - 복수 프레임으로 파이프 채움
• 프레임 순서: 수신쪽에서 버퍼링
• Go-back-N or selective-repeat?
  • 오류 나서 복구할 때 stop-and-wait로 처리
• 실제는 거의 sliding window 사용. Why?
  • link level에선 low level ➡️ parallel 지원이 안 될 수도 있음
  • 통신에서는 기준이 있음 (sliding window가 이미 자리를 잡고 있음)

Sliding Window 구현

• 목적
  • 통신 프로토콜이 어떻게 구현되는가에 대한 궁금증 해결
    • 계층 구조는 어떻게 구현되는가?
  • 슬라이딩 윈도우 알고리즘 구현을 통한 확실한 이해
• 어디서, 즉, 시스템의 어느 단계에서, 동작하는 프로그램인가?
  • 프레임 하나 하나의 송수신은 NIC(Network Interface Card)이 담당
  • 하위 계층에 CRC => NIC에서 구현
  • 슬라이딩 윈도우는 바로 그 위에서 동작
    ➡️ 디바이스 드라이버와 연동하는 시스템 소프트웨어
  • 계층 구조의 실체는? OSI 모델을 기준으로 한다면?
• 프로토콜 내부 동작의 실체는?
  • 계층 구조에 따라, 헤더 정보를 써넣고, 읽고 처리하는 것이 기본
  • 담당 기능에 따라 세부 동작이 정해짐 (슬라이딩 윈도우 - 오류제어)
• 지금까지 배운 것을 종합적으로 보여주는 예