Computer Network Lecture.03 DLC

경희대학교 이성원 교수님의 컴퓨터 네트워크 수업을 기반으로 정리한 글입니다.

Contents

• DLC Basic
• Simple Protocol
• Stop-and-Wait Protocol
• Go-Back-N Protocol
• Selective Repeat Protocol
• DLC Example - HDLC
• DLC Example - PPP

DLC Basic

Data Link Control Layer

Concept

Data Link layer

• 2계층 하단부 - MAC Layer: physical한 medium을 여러명이 공유할 때 어떤식으로 효율적으로 공유할 것인가에 대한 방법
• 2계층 상단부 - DLC Layer: physical한 layer에서 error가 발생했을 때 어떤 방법으로 검출 및 복구할 것인가에 대한 방법으로 2계층 역할에 충실

Data Link Control(DLC)는 에러 검출 및 복구(error control)가 가장 중요한 기능이며 그 외에도 framing과 flow control을 한다.

동작 방식은 크게 두 가지로, dedicated 방식과 broadcast 방식이 있다.

 

Framing

보내고자 하는 데이터가 3계층에서 왔을 때 에러 검출 및 복구, 흐름제어를 하기 위해,

추가적으로 필요한 정보들을 집어넣고, 사이즈를 조절한다.

 

A frame in a character-oriented protocol

송신단에서 수신단으로 0과 1의 조합을 Physical Layer을 통해 Data link control Layer가 보낼 때에,

정보를 Byte 단위로 보낼 건지, Bit 단위로 보낼 건지, 크게 두 가지 방식이 있다.

 

여기서 character-oriented는 ASCII 문자로 1 byte이기에 byte 단위로 데이터를 전송한다고 이해하면 된다.

▶ A frame in a character-oriented protocol

 

physical layer가 A, B를 연결하면, 사용자가 만든 정보를 받지 않더라도 physical layer는 끊임없이 어떤 정보를 주고 받는다.

 

예를 들어, 송신단이 0볼트 0을, 5볼트 1을 보내도 손실이 발생해 수신단 입장에선 5볼트일 수 없다.

 

이때, 얼마나 손실된 것을 수신단 입장에서 5볼트로 1, 그 밑을 0으로 볼지 값을 판단하기 위한,

즉 0, 1을 판단, training 하기 위한 reference 값을 가진다.

 

이렇게 training data를 받다 DLC data의 시작을 알리는 Flag를 만나면 training을 중지하고,

이제부턴 Data Link Layer의 data임을 인식한다.

 

즉, 송신단은 DLC Layer은 3계층으로부터 받은 유의미한 데이터를 전송하고자 할 때, Flag를 쏘고.

수신단은 Flag를 받으면 training data가 아닌 Data Link Layer의 data임을 판단한다.

 

Byte stuffing and unstuffing

▶ Byte stuffing and unstuffing

• Byte stuffing: ESC 넣는 과정
• Byte unstuffing: ESC 빼는 과

사용자가 보낸 데이터가 우연히 DLC Layer가 Flag로 사용하고 있는 값과 같으면,

수신하는 DLC Layer에게 Flag가 아닌 Data임을 알려주는 stuffing 작업이 필요하다.

 

Byte stuffing은 ESC(escape sequence) 특수 코드를 넣어주는 작업이다.

 

이때 또, 사용자가 보낸 데이터가 우연히 ESC로 사용하는 값과 같으면,

앞에 ESC를 한 번 더 넣는 stuffing 작업을 함으로써 특수 코드가 아닌 Data임을 알려준다.

 

Bit stuffing and unstuffing

▶ Bit stuffing and unstuffing

 

Flag가 8비트인 01111110일 때, 송신단이 보내는 데이터가 0으로 시작해서 1이 다섯개가 나타나면,

송신단은 무조건 0을 추가하여 flag에나타나는 bit 배열이 data에 나타나지 않도록 한다. 

 

※ 과거엔 통신 링크가 매우 비쌌기에, 이를 최대한 효율적으로 사용하고자 bit 단위로 stuffing을 하였다.

Flow and Error Control

Concept

▶ Feedback

• 너무 빨리 보내지 마! (flow control)
• 지금보단 더 보내도 돼! (flow control)
• 에러 났어! (error control)

Connection

• connectionless: connection 만들지 않고 통신 (상대방 배려하지 않고 보내고 싶을 때 보냄)
• connection-oriented: connection 만들고 통신 (연결 설정 - 유지 - 해제)

flow/error control은 거의 connection-oriented이다.

connectionless는 대부분 flow/error control 하지 않는다고 볼 수 있다.

 

※ phycial layer은 physical하게 유무선 연결하며, 2계층부턴 소프트웨어적 작업으로 logical 연결한다.

Simple Protocol

Simple DLC Protocol

Simple Protocol

▶ Simple Protocol

 

flow, error control 둘 다 하지 않으며,

송신단이 보내고 싶으면 바로 전달, 수신단은 무조건 잘 받는다. (error 전혀 X -> 현실적 X)

 

※ Simple Protocol은 Stop-and-Wait Protocol, Go-Back-N Protocol, Selective Repeat Protocol, 3가지 Protocol을 설명하기 위한 가상의 방법이다.

 

FSM for the simple protocol

▶ FSM for the simple protocol (빨간 글씨: event / 검정 글씨: action / 상자: state / start: 통신 장치 시작)

• Ready: 프로그램 혹은 통신 장치의 가장 기본이 되는 최초 상태

※ FSM(Finite State Machin): 상태(state)를 기반으로 동작(오토마타)을 제어하는 방식을 구현하기 위한 state transition diagram(STD)

 

Operation of the simple protocol

▶ ladder diagram(message sequence chart, MSC) for the simple protocol

Stop-and-Wait Protocol

Stop and Wait Protocol

Concept

에러 검출 및 흐름제어 기법이다.

 

에러 발생을 확인하는 방법

• 메시지 변질: 데이터 외에 추가적인 정보로 판단 가능 (CRC)
• 송신에선 쐈으나 수신에서 못 받음: 송신단이 응답 확인 메시지 못 받은 것으로 판단 가능

▶ Stop and Wait Protocol

 

메시지 변질

CRC는 n 바이트에 해당하는 코드로, sending node의 Data-link에서 계산이 된어 Frame에 같이 붙어 전송된다.

이후, receiving node도 CRC를 계산하여 sending node의 CRC와 비교한다.

 

CRC 값이 같으면 데이터가 잘 보존되어 온 것이므로,

이 경우 receiving node의 Data-link에서 Network Layer로 데이터를 올리고 잘 받았다는 의미의 ACK를 보낸다.

 

이때 ACK 메시지 역시 CRC를 포함하기에, ACK에 대해서도 CRC를 비교하여,

sending node 입장에서 메시지가 잘 전달되었음을 알 수 있다.

 

반대로,  메시지가 변질되어 CRC가 다르면 receiving node는 ACK 메시지를 전달하지 않고 받은 데이터를 버린다.

그렇게 되면, sending node 입장에선, 일정 시간 안에 ACK가 안 왔기에 에러가 발생했음을 알 수 있다. (timer expire)

 

sending node는 타이머가 터지면 본인이 보내야 될 재전송 횟수에 도달했는지를 확인한 후, 

도달하지 않았으면 한 번 더 보낸다.

즉, Stop and Wait Protocol은 sending node가 데이터를 보낸 후,
추가적인 transimission을 stop! 그리고 receiving node로부터 ACK 메시지를 wait! 한다.

 

이러한 stop and wait로 자연스럽게 flow control도 된다.

 

송신에선 쐈으나 수신에서 못 받음

receiving node에선 데이터를 아예 못 받고, sending node의 입장에선 메시지가 변질된 경우와 똑같다.

 

FSM for the stop-and-wait protocol

▶ FSM for the stop-and-wait protocol

• save a copy: 재전송을 위해 copy 저장
• Blocking: 추가적으로 Network Layer에서 Data-link Layer로 오는 것을 막음

Flow diagram

▶ Flow diagram  for the stop-and-wait protocol (problem)

 

ACK가 없어지면 sending node는 data가 잘 갔는지 확인할 수 없어 다시 보내게 되고,

sending node 입장에서는 data가 duplicate, 즉 Network Layer에 올라가면 안 되는 data가 올라가게 된다.

▶ Flow diagram  for the stop-and-wait protocol (duplicate problem 개선)

 

Frame에 번호 달아 줌으로써 duplicate 문제를 개선했다.

 

Frame 0를 받았을 때 ACK 0이 아닌 ACK 1을 보내는 이유는

ACK 1이 (Frame 0은 잘 받았으니) 이제 Frame 1을 보내달라는 의미이기 때문이다.

 

data는 1개씩 보내기에 번호는 0, 1 두 개로 충분하다.

Piggybacking

Concept

대부분의 통신 시스템은 양방향 통신이기에 ACK를 별도로 보내는 것이 아닌, 내가 보낼 데이터에 ACK를 낑겨 보내는 방법이다.

통신에선 메시지 크기보다 개수가 더 중요하기에 메시지 개수를 줄이는 Piggybacking(돼지꼬리) 방법을 사용한다.

Go-Back-N Protocol

Go-Back-N ARQ

Stop-And-Wait는 하나를 보내고, 그 하나에 대한 응답이 올 때까지 기다린다.

때문에, 보내는 데이터가 많아짐에 따라 시간도 오래 걸리고, 효율이 떨어지는 문제가 있다.

 

Go-Back-N은 하나가 아니고, 미리 정한 숫자만큼은 ACK가 없더라도 보낼 수 있어 Stop-And-Wait 보다 효율이 좋다.

 

Send window for Go-Back-N ARQ

▶ Send window for Go-Back-N ARQ

• Sf: 가장 첫 번째 ACK 안 온애 (outstanding state, 미해결된 상태)
• Sn: 보낼 수 있는 애 중 첫 번째로 아직 안 보낸 애
• sliding window: window를 이동해 가면서 하는 것 (circular ring, 링 형태의 순환 구조)

※ window: 상대방으로부터 ACK가 없더라도 보낼 수 있는 message의 range (message들을 여러개 연결해 놓은 것)

 

Design of Go-Back-N ARQ

▶ Design of Go-Back-N ARQ

• 송신단 버퍼: stop-and-wait 보다 복잡하게 N
• 수신단 버퍼: stop-and-wait와 동일하게 1개

※ 버퍼: 데이터 패킷 저장 위한 메모리 영역 / 패킷: 네트워크를 통해 전송되는 데이터의 단위

 

Window size for Go-Back-N ARQ

window size는 왜 2^m이 아니라 2^m - 1 일까?

▶ Window size for Go-Back-N ARQ

• window size: 버퍼의 사이즈(2^m)보다 최소 1은 적어야 한다. 

※ 통신 속도가 빠를 수록 window size는 커진다. 하지만 window size가 커짐에 따라 버퍼도 커지므로 trade off, 즉 이익-손 관계를 고려해야 한다.

 

Window size < 2^m

0, 1, 2 Frame을 잘 보냈지만 ACK는 안 받은 상황에서 ACK를 못 받았으니 다시 0을 재전송하면,

receiver는 왜 3을 안 보내지? ACK가 안 보내졌나? 하면서 에러로 인한 재전송을 인식한다.

-> sender야 그냥 버려! 난 어차피 잘 받음!

 

Window size = 2^m

ACK를 못 받아 재전송한 0 Frame(Sf)을 새로운 0 Frame으로 receiver은 오해한다. (duplicate)

 

Flow diagram for Go-Back-N ARQ

▶ Flow diagram for Go-Back-N ARQ

 

ACK 3은 앞에 잘 받았으니 3번 Frame을 달라는 의미이기에 sender는 Frame 1, 2를 버퍼에서 지운다.

즉, 중간 Frame에 대한 ACK는 뒤에 있는 ACK에 의해 support되기에 큰 의미를 갖지 않는다.

▶ Flow diagram for Go-Back-N ARQ (problem)

 

sender가 여러 메시지를 보내고 그 중 일부에 대한 응답을 받지 못했을 때, 

응답받지 못한 여러개의 메시지들 중에 첫 번째 메시지부터 모든 메시지를 재전송한다.

 

이 과정에서 후속 메시지들이 이미 성공적으로 수신된 상태임에도 불구하고,

수신자의 버퍼가 하나뿐이고, 확인 수단이 ACK 하나뿐이기 때문에, 이 메시지들을 제대로 인식하지 못하여 모두 버리게 된다. 

Selective Repeat Protocol

Selective-Repeat ARQ

수신단 입장에서 잘 받은 거에 대해선 재전송하지 않는다.

즉, 선택적으로 에러가 발생한 메시지들에 대해서만 재전송한다. (효율적)

 

Send window for Selective Repeat ARQ

▶ Send window size

• Go-Back-N: 2^m - 1 이하
• Selective-Repeat: 2^(m-1) 이하

Receive window for Selective Repeat ARQ

▶ Receive window for Selective Repeat ARQ (하얀색: 에러! / 빨간색: 잘 받았음!)

• Rn: 아직 받지 못한 첫 번째 Frame

수신단 입장에서 잘 받은 것에 대해선 재전송하지 않고, 선택적으로 에러가 난 애들에 대해서만 재전송한다. (선택적 재전송)

 

Design of Selective Repeat ARQ

▶ Design of Selective Repeat ARQ

 

NAK(non acknowledgement)

• 앞에 메시지 안 왔는데 다음 메시지가 온 경우
• 에러 발생 형태로 수싱된 경우

Selective Repeat ARQ, window size

▶ Selective Repeat ARQ, window size

 

window size > 2^(m-1)

재전송인지 모르고 수신하는 문제점이 발생한다.

 

Flow diagram for Selective Repeat ARQ

▶ Flow diagram for Selective Repeat ARQ

 

Go-Back-N의 문제를 해결하기 위해 추가된 Selectiv Repeat의 대표적인 3가지 기술

• 수신버퍼의 멀티화: 각 패킷을 독립적으로 저장하고 처리할 수 있는 다수의 수신 버퍼를 사용한다. 이를 통해 패킷의 순서와 관계없이 각 패킷을 처리할 수 있게 하여 선택적 재전송을 가능하게 한다.
• NAK 메시지: 메시지가 안 왔는데 다음 메시지가 온 경우, 혹은 에러 발생 형태로 수신된 경우 NAK 메시지를 보내 잘못 받았음을 알린다. 이를 통해 필요한 패킷만을 선택적 재전송하게 한다.
• 메시지별 타이머: 각 패킷마다 개별 타이머를 설정한다. 이를 통해 각각의 패킷에 대한 타임아웃을 정확히 감지하고 해당 패킷만을 선택적 재전송할 수 있게 한다.

DLC Example - HDLC

DLC Example

HDLC

High-level Data Link Control, 여기서 High-level이란 것은 MAC 위에서 동작한다는 의미이다.

 

HDLC Frames

▶ Frame Format

• I-frame: 주로 데이터를 주고받는 용도
• S-frame: 데이터를 주고 받지 않는데 ACK만 보내야 할 땐 piggybacking이 아닌 explicit한 ACK가 나가야 하는데, 이때 쓰이는 용도
• U-frame: 제대로 동작하는지 확인하는 용도 (control이 아닌 management)

여기서 FCS는 Frame Check Sequence의 약자로, CRC(에러 검출 field)에 상응하는 것이다.

▶ HDLC Frames (Control Field의 Frame number)

• N(S): send number
• N(R): receiver number (ACK)

HDLC는 field를 잡고 비트 수를 준다.

 

Example of connection and disconnection

▶ Example of connection and disconnection (연결 설정 - 데이터 주고 받음 - 해제)

• SABM: connection request
• UA: 응답 (일종의 ACK)
• DISC: disconnection request
• UA: 응답 (일종의 ACK)

대부분의 data link control은 에러 검출 및 복구를 하기 위해 connection-oriented 기법이다.

여기서 HDLC는 connection-oriented 기법의 대표적인 예시이다.

 

Example of piggybacking with and without error

▶ Example of piggybacking with and without error (앞 쪽 파란 네모: sending frame / 뒤 쪽 파란 네모: receiving frame)

DLC Example - PPP 

DLC Example

PPP

Point-to-Point의 약자로, Point-to-Point이기에 connection-oriented 기법이며,

Data Link 계층이지만 OSI 7계층에서 얘기하는 Data Link의 목적인 에러 검출 및 복구로는 별다른 기능이 없다.

 

본인이 데이터를 주고 받는 것을 목적으로 하지 않고, 그 위 3계층 이상의 어플리케이션에 대한 것을 설정하고 유지 관리한다.

 

트리플 A: authentication(인증), authorization(허가), accounting(돈)

• 네트워크 Layer를 잘 돌아가게 한다.
• 사용자가 합법적인지, 얼마만큼 지원받으면 되는지, 암호화로 적합한지 판단해주는 등의 관리 기능을 수행한다.

PPP Frame Format

▶ PPP Frame Format

 

Transition phases

▶Transition phases

 

PPP의 3가지 상태

1. Establish 상태

• 정의: 죽어있는 Dead 상태에서 물리적 계층이 정상적으로 연결된 신호를 받았을 때 진입한다. 이 상태에서는 PPP 연결의 기초를 마련하고, 물리적 계층의 연결 확인 후 이를 유지하기 위한 프로토콜을 설정한다.
• 동작: Carrier detect 신호가 감지되면 상대방과 LCP를 사용하여 옵션을 교환하고, 연결을 설정한다. LCP는 물리적 계층이 정상적으로 작동하는지 확인하고, 필요한 링크 구성 옵션을 협상한다. 연결에 문제가 발생하면 다시 Dead 상태로 돌아 간다. 

2. Authenticate 상태

• 정의: 상호 지원되는 옵션들이 맞춰졌고, 통신 상호 작용에서 요구되는 옵션이 일치하면, 인증 단계로 넘어 간다. 이 상태는 사용자의 합법성을 검증한다.
• 동작: PAP, CHAP를 통해 인증 과정을 수행한다. 사용자가 합법적이라면 네트워크 단계로 넘어가며, 그렇지 않을 경우 연결을 끊고 다시 Dead 상태로 돌아간다. (적합 여부 판단 -> 0 or 1)

3. Network 상태

• 정의: 인증이 완료되고 사용자가 합법적으로 레이어 1과 2를 사용할 수 있다고 판단된 상태이다. 이 단계에서는 레이어 3 이상의 네트워크 구성을 설정한다.
• 동작: IPCP 등의 네트워크 제어 프로토콜을 사용하여 네트워크 레이어의 구성을 완료한다. 모든 설정이 제대로 구성되면, PPP는 open 상태가 되어 네트워크 상태로 진입하, 3계층 이상의 소프트웨어가 데이터 전송을 수행할 수 있는 상태가 된다.

Multiplexing in PPP

▶ Multiplexing in PPP

• Protocol field: 상위 계층에 있는 애들을 실어 나르는 대상이 어떤 protocol인지 명시하는 field

3계층 이상이 잘 돌아가도록 configuration 해주는 것이 목적이며, 본인은 에러 검출 및 복구는 딱히 하지 않는다.

 

LCP packet encapsulated in a frame

▶ LCP packet encapsulated in a frame

• Link Control Protocol: PPP는 상대방과 연결 요청 및 해제 과정 때 직접하지 않고 LCP를 사용

※ 01 ~ 04: 연결 요청/ 05 ~ 06: 연결 해제 / 07 ~ 0B: control 

 

PAP packets encapsulated in a PPP frame

▶ PAP packets encapsulated in a PPP frame

• ack: 승인
• nak: 미승인

PPP는 이동 통신인 경우 합법적인 사용자인가 / 아닌가, 돈 내는 사람인가 / 아닌가,

즉 사용자를 인증하여 구분하는 것이 가장 중요하다.

 

이를 위해 PAP or CHAP를 사용한다.

 

PAP은 사용자가 시스템으로 유저 아이디와 패스워드를 날리는 것이 시작이고, 

시스템 유저에게 승인/미승인 여부를 알려준다.

 

CHAP packets encapsulated in a PPP frame

▶ CHAP packets encapsulated in a PPP frame

 

CHAP는 PAP와 거의 유사한데,

CHAP는 유저가 바로 물어보지 않고 시스템 쪽, 즉 서버 쪽이 요청하라고 할 때까지 기다린다는 점에서 차이가 있다.

 

때문에 CHAP은 서버 입장에서 부하 조절이 필요할 때 사용된다.

 

Packet encapsulated in PPP frame

▶ Packet encapsulated in PPP frame (IP - 인터넷)

 

PPP Operation Example

▶ PPP Operation Example (연결 설정 - 데이터 주고 받음 - 해제)

• Establish: 직접하기 보단 LCP가 Layer 2 설정
• Authenticate: PAP, CHAP를 통해 인증 (합법성) 확인
• Network: Network를 어떤 거 쓸지에 따른 configuration -> 합법적인 애가 IP 프로토콜을 통해 통신
• Termination: LCP가 연결 해제

---

참고자료

https://www.youtube.com/watch?v=G9mP2ZgQT4U&list=PLz7S5PHCu4OlB-lUP_BqYmgiuLkvKY5aX&index=3