Data Link Layer: Data Link Control
데이터 링크 계층(L2)의 주 역할 = 흐름 제어(flow control) + 오류 제어(error control) 를 결합해 한 노드에서 다른 노드로 데이터…
AI 네트워킹 중간범위 — 노션 강의 노트를 옵시디언용으로 정리한 노트.
데이터 링크 제어 프로토콜 개요
- 데이터 링크 계층(L2)의 주 역할 = **흐름 제어(flow control) + 오류 제어(error control)**를 결합해 한 노드에서 다른 노드로 데이터 전달.
- 오류 제어: 데이터 전송의 정확성 보장.
- 흐름 제어: 수신자의 처리 능력을 넘지 않도록 전송 제어.
- 혼잡 제어(congestion control): 네트워크 전체가 혼잡해지지 않도록 제어 → 단, L2에서는 수행하지 않음(오류·흐름 제어만).
프로토콜 분류
| 채널 | 프로토콜 |
|---|---|
| Noiseless Channel (무잡음) | 가장 단순한 프로토콜 / Stop-and-Wait |
| Noisy Channel (잡음) | Stop-and-Wait ARQ / Go-Back-N ARQ / Selective Repeat ARQ |
- 현실에 노이즈 없는 채널은 존재하지 않음 → 노이즈 채널은 흐름 제어 + 오류 제어를 모두 해야 함.
- 이때 등장하는 개념이 ARQ (Automatic Repeat reQuest, 자동 재전송 요청).
- 정의 → 데이터 전송 중 오류 발생 시, 수신측이 오류를 검출하고 송신측에 재전송을 요청하여 데이터 무결성을 보장하는 오류 제어 방식.
Stop-and-Wait ARQ
- 기본 Stop-and-Wait = 한 번에 프레임 1개만 보내고 ACK를 받을 때까지 다음 프레임을 안 보내는 방식.
- 여기에 간단한 오류 제어 메커니즘추가:
- 전송한 프레임의 복사본 유지+ 타이머. ACK가 일정 시간 안에 안 오면 재전송.
- (기존 Stop-and-Wait의 ACK는 “다음 보내도 됨” 의미 / ARQ에서는 오류 식별 용도)
- modulo-2 기반 순서 번호사용: 0 ~ 2^m − 1, 여기서는 0과 1 반복.
번호 시스템
- Sn: 다음에 보낼 프레임 번호.
- Rn: 다음에 받기를 기대하는 프레임 번호.
- modulo-2라 0과 1만 존재 (동시에 1개만 보내므로 새 프레임 vs 재전송만 구분하면 됨).
- 수신자가 Rn과 비교: 같으면 새 데이터, 다르면 재전송(중복)으로 판단.
송신자 알고리즘 (영원히 반복, 3가지 이벤트)
- Request from network layer: 보낼 데이터 생김 → 데이터 가져오기 → 프레임 생성(seq 번호 부여) → 전송 → 타이머 시작.
- Notification from physical layer (ACK 도착): ACK 확인 → 정상이면 seq 번호 이동.
- Time-out: ACK가 시간 안에 안 옴 → 이전 프레임 재전송 → 타이머 재시작.
대표 시나리오
- 정상: Frame 0 전송 → 정상 수신 → Rn=1, ACK 1 전송 → ACK 받으면 Sn=1.
- 프레임 손실: Frame 1 전송 → Lost → timeout → Frame 1 재전송 → 정상 수신 → ACK 0.
- ACK 손실: Frame 0 정상 수신·ACK 전송했으나 ACK가 손실 → timeout → Frame 0 재전송 → 수신측은 duplicate라 seq 번호를 움직이지 않고 ACK만 다시 전송.
Bandwidth-Delay Product (BDP) — 용어
- 정의: 수신자 응답을 기다리는 동안 시스템이 보낼 수 있는 비트 수의 척도.
- 공식: BDP = Bandwidth × Delay
- Bandwidth: 초당 전송량(bps), Delay: 왕복 시간 또는 전파 지연.
- 의미 → ACK 기다리는 동안 보낼 수 있는 최대 데이터 양 (제어 방식이 아니라 지표).
- 링크 이용률: Utilization = (frame size / BDP) × 100 (%)
- frame size = 헤더 + 데이터 + 트레일러 포함 한 프레임 전체 크기.
- 예시: Bandwidth=1Mbps, Delay=0.2s, Frame size=1000bits
- BDP = 1,000,000 × 0.2 = 200,000 bits
- Utilization = 1000 / 200,000 = 0.5% → 99.5% 동안 링크가 놀고 있음(Stop-and-Wait의 비효율).
파이프라이닝(Pipelining) — 용어
- 이전 작업이 끝나기 전에 다음 작업을 시작하는 방식 → 네트워크에서는 ACK를 기다리지 않고 계속 전송.
- **Stop-and-Wait ARQ에는 파이프라이닝 없음.**Go-Back-N / Selective Repeat에 적용.
- 전송 중 비트 수가 BDP에 비해 크면 파이프라이닝이 전송 효율을 향상.
- Stop-and-Wait: 항상 1개, RTT 동안 링크 IDLE → 비효율.
- Pipelining: 여러 개를 동시에 in-flight로 두어 링크를 계속 채움.
Go-Back-N ARQ
- 여러 프레임을 미리 보내고, 문제가 생기면 그 지점으로 돌아가서 이후를 모두 재전송.
- ACK 받기 전 보낼 수 있는 프레임 수: Stop-and-Wait=1개, GBN·SR = W개(Window size).
- 순서 번호: m비트, 0 ~ 2^m − 1 범위 반복.
- ACK 올 때까지 전송 프레임 복사본 유지. 프레임 손실/손상 시 송신자가 timeout 후 미결 프레임으로 돌아가 모두 재전송.
오류 처리 예 (W=4, Frame 2에서 오류)
- 수신자: Frame 0 OK, 1 OK, 2 오류→무시, 3 순서 안 맞음→무시.
- 송신자: ACK 안 옴 → timeout → Frame 2부터 다시 전송 (2,3 재전송).
- ⇒ 문제 난 지점으로 돌아가 그 이후 전부 다시 보냄.
슬라이딩 윈도우 (Sliding Window)
- 송·수신자가 관심 갖는 순서 번호의 범위를 정의하는 추상 개념.
- 송신 윈도우: 크기 = 2^m − 1, 변수 Sf, Sn, Ssize. ACK 오면 윈도우 이동(slide).
- Sf (Send First): 가장 오래된, ACK 안 받은 프레임(윈도우 시작).
- Sn (Send Next): 다음에 보낼 프레임 번호(계속 이동).
- Ssize: 동시에 보낼 수 있는 최대 개수.
- 영역 구분: [이미 ACK됨] | [보냈지만 ACK 안됨] | [보낼 수 있음] | [못 보냄].
- 수신 윈도우: 크기 1의 가상 박스, 변수 Rn 하나만. 정상 프레임 도착 시 한 칸씩 이동. 순서 안 맞는 프레임은 모두 버리고 재전송 요구.
송·수신 알고리즘
- Sender: ① Request from network → frame 생성, 윈도우 안이면 전송 ② ACK 도착 → Sf 이동(window slide), 새 프레임 전송 가능 ③ Time-out → Sf부터 다시 전송(Go-Back).
- Receiver: frame 도착 시 Rn과 일치하면 → 상위 계층 전달, Rn+1, ACK 전송. 불일치면 → 버리고 직전 ACK 재전송(중복 ACK = 못 받았다는 뜻 → 송신측 재전송 유도).
윈도우 크기 제약: window size ≤ 2^m − 1
- 이유: ACK가 손실될 때 old data를 new data로 착각하는 것을 방지.
- 2^m = 시퀀스 번호 개수. 윈도우가 2^m − 1보다 크면, ACK 손실 후 수신측이 기대하는 번호와 재전송된 옛 프레임 번호가 겹쳐 구분 불가.
기타
- 정상 흐름: Sender는 기다리지 않고 0→1→2→3 연속 전송, Receiver는 순서 맞으면 ACK.
- 손실 흐름: Frame 1 손실 → 이후 2~4는 수신측에서 drop(Rn=1 기대) → timeout 후 1부터 다시 전송.
- Stop-and-Wait ARQ = Go-Back-N ARQ의 특수 경우 (window size = 1).
- 장점: 효율 ↑(pipeline), BDP 활용 / 단점: 하나 오류 시 뒤 전부 재전송 → 불필요한 전송.
Selective Repeat ARQ
- Go-Back-N은 잡음 많은 링크에서 비효율적(에러 시 그 지점부터 전부 재전송).
- Selective Repeat: 정상 수신 프레임은 두고 손상된 프레임만 재전송→ Noisy link에서 효율적(오류율 높을수록 효과적). 단, 수신측 처리는 더 복잡.
두 개의 윈도우
- Go-Back-N은 송신 윈도우만 의미 있음(수신 윈도우=1).
- Selective Repeat은 송신 윈도우 + 수신 윈도우 둘 다 의미 있음(수신측도 여러 개 관리).
윈도우 크기: 2^(m−1)(절반)
- 송·수신 윈도우 크기가 같고, 전체 번호 공간의 절반만사용.
- 이유: 시퀀스 번호 겹침 방지 → 옛 프레임과 새 프레임을 구분.
Out-of-order 처리 & NAK
- 수신 윈도우 크기만큼은 순서와 상관없이 도착 가능, 순서가 맞춰질 때까지 버퍼에 저장(먼저 도착해도 안 버림). 상위 계층 전달은 순서대로.
- NAK (Negative AcKnowledgment, 부정 확인 응답): 타이머 만료 전에 손상 프레임을 받으면 NAK 전송 → 송신자는 해당 손상 프레임만 재전송. (timeout을 기다리지 않고 즉시 확인)
송·수신 알고리즘
- Sender: ① Request from network → frame 전송 ② ACK → 해당 프레임만 확인, 윈도우 일부 이동 / NAK → 특정 프레임만 재전송 ③ Time-out → 해당 프레임만 재전송.
- Receiver: 프레임 도착 시 → 윈도우 안이면 버퍼 저장 + ACK / 순서 맞으면 연속된 것 모두 상위 계층 전달 / 손상이면 NAK.
윈도우 크기가 2^(m−1) 이하여야 하는 이유
- 윈도우가 너무 크면 old frame과 new frame을 구분 못 함.
- 예) 번호 공간 4, 윈도우 2(절반 이하)면 0·1 ACK 손실 후 재전송 시 Rn으로 구분 가능. 윈도우 3이면 0부터 재전송 시 새 0으로 오인.
동작 예
0 → 정상
1 → 손실
2,3 → 먼저 도착 → 버퍼 저장 + NAK(1) 전송
→ 1만 재전송 → 순서 맞춰 상위 계층 전달Go-Back-N vs Selective Repeat — 무엇이 더 좋은가
- 정답: 환경에 따라 다름(에러율과 BDP로 판단).
| 상황 | 유리한 방식 | 이유 |
|---|---|---|
| 에러 거의 없음, RTT 큼(장거리), 대역폭 큼 | Go-Back-N | pipeline으로 많이 밀어넣는 게 중요, 재전송 거의 없어 높은 효율 유지 |
| 에러 자주 발생(Noisy) | Selective Repeat | 하나 틀려도 하나만 재전송 → 불필요한 재전송 제거 |