Chapter 11. Data-Link Layer

HEEJOON MOON·2021년 10월 10일

목록 보기

5/12

11.1 DLC services

Data link control은 2개의 인접한 노드들간의 통신 절차를 다룬다. Data link control에는 크게 framing, flow control, error control을 포함한다.

11.1.1 Framing

Physical layer는 비트 단위의 신호들을 source에서 destination까지 보낸다. 반면, data-link layer는 비트들을 프레임단위로 묶어서, 각 프레임이 구별가능하도록 해야한다. Framing은 메시지를 분리하며, sender address와 destination address를 추가한다. 메시지를 크게 한 프레임으로 만들 수 있지만, flow, error control이 힘들어진다.

프레임을 구분하기 위한 길이를 나누는 방법에는 바이트 단위의 Character oriented 방법과 비트 단위의 bit oriented 방법이 있다.

Character oriented framing

8비트 단위의 character로 framing이 된다. Header는 소스,목적지의 주소와 control정보들을 포함하며, trailer는 error detection bit를 포함한다. flag는 프레임에 시작과 끝에 덧붙여지는데, 항상 training이 일어나는 physical layer에게 DLC로부터의 유의미한 message임을 알려주는 역할을 한다. Header, trailer, flag 모두 8비트(1바이트)이다.

만약 data frame이 flag와 같은 경우가 발생시, Byte stuffing통해 해결한다. ESC(escape character)를 삽입하여서, flag가 아닌 데이터임을 알려주는 구분자 역할을 해준다. 위의 경우처럼 ESC와 같은 경우도, 앞에 ESC를 넣어주어서 구분을 해준다.

Bit oriented framing

비트 단위로 프레임에 접근할 수 있다. Flag로는 8-bit 패턴의 01111110을 사용한다. 위의 경우처럼 사용자 데이터프레임에 flag pattern이 나타나있으면, receiver에게 프레임의 종료가 아님을 알려주어야 한다. 이는 아래와 같이 bit stuffing을 통해 해결가능하다.

bit stuffing은 1이 5개 연속으로 나온는 경우, 마지막 1뒤에 0을 무조건 삽입하여, 혼돈을 막는다. 비트단위로 프레임을 구분하여 접근한 이유는 과거에는 통신이 비싸서 최대한 효율적으로 하고자 했어서다.

11.1.2 Flow and Error control

Flow control은 위의 경우처럼 recevier node가 sending node에게 피드백을 주어서, 데이터 전송 속도를 조절한다. 빠른 송신자가 느린 수신자를 압도하지 못하도록 한다.

buffer
버퍼는 sender와 reciever에서 패킷들을 보관할 수 있는 메모리 주소들의 집합이다. Receiving data-link의 버퍼가 가득차면, Sender에게 프레임 전송을 중단하도록 요청한다.

Error control은 다음과 같이 2개의 방법을 사용한다. CRRC라는 헤더 프레임이 sender에 의해 더해져, receiver에 의해 check된다.

frame이 손상되면 버려진다. 손상되지 않으면, 패킷은 네트워크 계층에 전달된다. LAN이나 Ethernet에 사용
frame이 손상되면, 버려지고, 손상되지 않으면, ack가 sender에게 보내진다.

11.1.3 Connectionless and Connection-oriented

Connectionless oriented

frame은 frame들간의 관계가 없이 보내진다. 각각이 독립적이다. 즉, 프레임들간의 연결이 없다해서 connectionless이다. LANs이 connectionless. 또한 따로 사전/사후 연결 설정 작업들이 필요하지 않고, 보내고 싶을때 보낸다. Flow-control을 거의 하지 않는다.

Connection oriented

logical한 connection이 2개의 노드간에 설정되어야 한다. 즉, 모든 프레임들은 연관이 되어있으며, 전송이 끝나면 연결이 끊어진다. 사전/사후 연결 작업이 필요하다.(연결 생성, 유지, 제거) Flow-control, error-control을 많이 한다.

11.2 DATA-LINK LAYER PROTOCOLS

11.2.1 Simple protocol

Simple protocol은 flow,error control을 하지 않는다. Recevier는 프레임을 받는 즉시 처리할 수 있어, incomming frames에 압도되지 않는다. 하지만 이것은 실제 자연계에서는 말이 안된다.

Sender는 network layer에서 받은 패킷을 프레임들로 만들어 전송한다. Receiver는 link를 통해 프레임을 수신하고, 프레임에서 패킷을 추출하고, 패킷을 Network layer에 보낸다.

FSM(상태천이도)는 위와 같다.

Message sequence chart는 위와 같다. Propagation delay를 확인할 수 있다.

11.2.2 Stop and Wait protocol

Stop and Wait protocol은 flow, error control을 모두 사용한다. 이 방식은 sender에서는 프레임을 보내고, 다음 프레임을 보내는 것을 잠시 멈추고(stop), ACK를 기다린다.(wait) Error를 탐지하기 위해서, CRC(일종의 코드값)를 각 데이터 프레임에 추가한다. 탐지 가능한 error는 다음 2개의 경우가 대표적이다.

CRC값이 다를 경우, 프레임이 변조된 것으로 판단

transmit 이후에, response가 없는 경우다. 즉 소실된 경우, Sender만이 에러가 발생했음을 알 수 있으며, 응답이 없는 경우 에러가 났다고 판단한다.

Sending node에서는 Timer를 가지고 있어서, 시간 내에 ACK가 오면 정상으로 판단하고, 시간 내 받지 못하면 error가 발생했다고 생각하고 프레임을 재전송한다. Receiving node에서는 Frame의 CRC와 받은 데이터를 통해 수신단에서 계산한 CRC와의 비교를 통해 프레임 변조를 판단한다. 같으면 정상, 다르면 변조 되었다고 판단한다. ACK역시 CRC를 가지고 있어서 송신단에서, ACK의 CRC값과 수신단서 계산한 CRC값의 비교를 통해 변조를 판단한다.

ready state(sendor): 네트워크 계층에서부터 packet을 기다리는 상태이다
Blocking state(sendor): 추가적인 프레임을 보내지 않고, 에러발생여부 확인하는 상태

Duplicate problem
마지막 경우처럼, ACK가 중간에 소실되어, 실제로는 정보가 제대로 수신되었으나 송신단이 재전송하여 똑같은 프레임이 중복되어 들어오는 문제가 발생한다. 이것은 Sequence and Acknowledgment Numbers를 사용하여 해결 가능하다. 프레임에 번호를 붙혀서, 중복되는 프레임을 수신하면 수신단은 network layer로 전달하지 않고 버린다.

11.2.3 Piggybacking

ACK를 별도의 프레임으로 보내지 않고, Reciever가 Sendor에게 보낼 메시지가 있을때, ACK를 같이 실어서 보내는 것을 piggybacking라한다. 이를 통해 효율적인 communication을 목적으로 한다.

11.2.4 Go-Back-N protocol

Stop & wait방식과 달리 한번에 미리 정해진 숫자만큼 ACK가 안와도 여러개의 패킷들을 전송이 가능하다. 보재진 패킷들은 ACK가 도착하기 전까지 보관되어야 하며, 여러개의 패킷과 ACK들이 아래와 같이 채널에 동시에 존재할 수 있다.

sequence number : m이 bits의 sequence number영역의 사이즈라 하면, 2의 m승개의 sequence number가 존재한다
Acknowledge number : ACK번호이다. In the Go-Back-N protocol, the acknowledgment number is cumulative and defines the sequence number of the next packet expected to arrive.

위의 그림은 sliding window의 send window를 나타낸 것이다.

Outstanding: sender가 패킷들이 수신됬는지 소실되었는지 찾기 위해 기다리는 상태이다. 즉, 메시지를 보냈는데, ACK가 오지 않은 상태이다.
Sf (send window, the first outstanding packet) : outstanding 프레임의 처음 위치를 나타낸다
Sn (send window, the next packet to be sent) : 다음 보내야할 프레임의 위치를 나타낸다. 즉, Network layer에서 새로운 메시지가 내려오면 Sn으로 간다
Ssize (send window, size) : window 크기를 말하며, (2^m -1)의 크기를 최대로 갖는다.

window size가 최대 2^m - 1인 이유는 위의 그림과 같이, circular queue를 사용하여 frame이 sequence number를 갖기 때문이다. 위의 그림처럼 2^m인 경우, duplicate문제가 발생하므로, 그보다 작은 값을 size로 가져야한다.

ACK를 받으면 Sf가 이동하며, window역시 sliding하는 것처럼 이동한다.

위의 그림은 ACK2가 중간에 소실된 경우인데, ACK3이 ACK2와 ACK3의 역할을 동시에 해준다.

위의 경우처럼 Packet이 중간에 소실되는 경우, Receiver는 기대했던 패킷이 아닌 경우 버려버리며, 기대하는 패킷을 달라는 ACK를 재전송한다. Sender역시 Ack의 넘버가 Sf보다 큰 것이 아닌, 같은 값이 들어왔으므로, 쓸모없이 생각하고 버려버린다. 이후 다시 Sf부터 패킷들을 재전송하게 된다. 이 때, 중간에 패킷이 소실되고, 뒤에 패킷은 제대로 수신받아도, 소실된 것 이후로 모두 다시 재전송해야 한다. 이래서 이름이 Go-Back-N이라고 함. 하지만 이는 중복하여 데이터를 보내게 되므로 비효율적인 문제가 발생한다.

11.2.5 Selective Repeat protocol

앞써 Go-Back-N은 에러가 발생시, 그이후로부터 다시 재전송해야 하는 문제가 있었다. Selective repeat protocol은 그와 달리 error가 발생한 것만 선택적으로 재전송한다는 개념이다.

Go-Back-N과 Selective Repeat의 차이점

window size는 Go-back-n의 경우 2^m-1이지만, selective는 2^(m-1)이다

receive window의 크기가 send window와 같다(buffer size의 증가). 이 이유로는 송신된 패킷이 수신될 때까지 저장될 수 있어 에러가 난 프레임을 알 수 있기 때문이다.

NAK가 추가적으로 존재한다. NAK를 받은 Sender는 해당 프레임을 다시 재전송하게 된다.

Window size of Selective Repeat

만약 위의 경우처럼 2^(m-1)보다 큰 경우는, receiver가 재전송된 0을 다음 cycle의 0으로 판단하여 accept한다.

In the Selective-Repeat protocol, an acknowledgment number defines the sequence number of the error-free packet received.

11.3 HDLC

HDLC(high-level Data Link Control)은 bit-oriented protocol로, Stop-and-Wait 방식을 사용한다.

Frames

Flag field : 0111110과 같이 동기화 패턴이 있다
Address field : secondary station address를 포함한다.
Control field : flow, error control을 위하 바이트가 저장된다.
Information field : Network layer부터의 user data나 management data를 저장한다.
FCS field : Frame check sequence는 HDLC의 에러 감지 영역이다. CRC값이 저장되어 있다.

Cotrol field for I-frame : I-frame은 network layer에서 온 user data를 전송하기 위해 고안되었다. 또한 piggybacking을 통한 flow-and-error control이 가능하다. N(s)는 프레임의 sequence number를 정의하며, N(R)은 piggybacking이 사용될때 ACK number를 의미한다. P/F는 poll, final을 의미하는데, poll은 primary가 secondary에게 프레임을 보낼때, final은 secondary가 primary에게 보낼때 사용된다.
Control field for S-frame : S-frame은 piggybacking이 불가능한 상황에서 flow and error control을 위해서 사용된다. 앞의 2개의 10bit를 통해 S-frame임을 알려주며, N(R)은 S-frame 종류에 따른 ACK/NAK의 넘버를, code는 S-frame 자체의 종류를 정의하는데 사용된다.
Control field for U-frame : U-frame은 연결된 장치들 사이의 세션 관리나 이나 통제 정보를 교환하기 위해 사용된다. info 영역이 있으며, control field code영역에 정보들이 저장되었다.

위의 그림은 연결 설정과 해제 과정에서의 U-frame 예제다.

위의 그림은 error의 유무에 따른, piggybacking을 사용한 교환의 경우를 나타낸 것이다. 에러가 발생하면 일부 프레임들이 버려진다.

11.4 POINT-TO-POINT PROTOCOL (PPP)

PPP는 주로 모바일에서 많이 사용한다. 장치들간의 프레임 포맷을 결정하며, 2개의 장치들은 링크의 설정과 데이터교환을 협상할 수 있다. 또한 인증 프로토콜을 제공한다. 하지만 flow-control은 제공하지 않으며, error control 역시 매우 간단히 구현되어 거의 신경쓰지 않는다.

11.4.2 Framing

11.4.3 Transition Phase

dead상태서 2개의 노드들간의 통신이 시작되면, establish상태가 된다. 두 장치간 options을 설정가능한데, authentication을 두면, 인증 절차를 밟게 된다. 아님 그냥 simple하게 인증 없이도 가능. open상태서 데이터 교환이 일어나며, 연결이 설정되면, 데이터 패킷들의 교환이 일어난다. 연ㄹ결이 종료되면, terminate상태가 된다.

11.4.4 Multiplexing

PPP는 다양한 데이터 영역속 프로토콜들에 있는 데이터를 전송한다.

Link Control Protocol

LCP는 links들의 estabish, maintain, config, terminate하는 역할을 담당한다. 또한 2개의 노드들 간의 option을 set하도록 할 수 있다.

모든 LCP 패킷들은 payload 영역에서 C021로 set된 PPP frame형태로 전송된다.

Authentication Protocols

PAP
Password Authentication Protocol (PAP)는 아래와 같이 2가지 절차로 이뤄진 간단한 인증이다.
1) 시스템에 접근하고하자는 user는 인증 id와 pw를 시스템에게 보낸다
2) 시스템은 검증하여 accept or deny한다.

CHAP
Challenge Handshake Authentication Protocol (CHAP)은 PAP보다는 보안성이 높으며, 3가지 단계를 거친다. 이과정에서는 PW를 직접 서버에게 보내는 일이 없다. 따라서 더 보안성이 높다. 또한 서버의 과부하를 막을 수 있다.

1) 시스템이 user에게 challenge를 보낸다
2) User는 가지고 있는 함수와 pw를 이용하여 challenge의 결과를 서버에게 보낸다.
3) 서버도 똑같이 함수를 가지고 시스템이 알고있는 user의 pw를 이용하여 결과를 도출하여 비교한다.