2. Data Link Layer - 데이터 프레임과 프로토콜

## 1. Data Link Layer 개요 - **링크 계층의 역할** - 해당 계층은 데이터그램을 하나의 노드에서 물리적으로 **인접한 노드**로 링크를 통해 전송하는 책임을 가짐 - 서로 다른 링크 프로토콜(e.g. 와이파이, 이더넷)을 통해 데이터그램이 전송됨 - 각 링크 프로토콜은 서로 다른 서비스를 제공함 - **서비스** 1. **framing, link access** - 데이터그램을 프레임으로 캡슐화하고, 헤더와 트레일러 추가 - 프레임 헤더에 “MAC” 주소를 사용하여 출발지와 목적지 식별 (IP 주소와 다름) 2. **신뢰할 수 있는 전송** - 인접 노드 간 신뢰할 수 있는 데이터 전송 제공 (오류율이 낮은 링크에서는 거의 사용되지 않음) - 무선 링크는 오류율이 높음 - **왜 Link 수준의 신뢰성과 end-to-end 신뢰성을 모두 제공해야 할까?** - 링크 수준 신뢰성은 인접한 두 노드 간의 데이터 전송 오류를 즉시 감지하고 수정함 - 네트워크는 여러 링크와 라우터를 거쳐 데이터를 전송함. 링크 수준 신뢰성만으로는 전체 경로의 신뢰성을 보장할 수 없음. 끝단 간 신뢰성은 출발지에서 목적지까지 전체 경로에서 데이터 전송의 무결성과 신뢰성을 보장함. 3. **flow control** - 인접 송신자와 수신자 간의 속도 조절 4. **error detection** - 신호 감쇠(attenuation), 노이즈로 인한 오류 - 수신자는 오류를 감지하고 재전송을 신호하거나 프레임을 삭제함 5. **error correction** - 수신자는 비트 오류를 식별하고 재전송 없이 수정함 6. **half-duplex and full-duplex** - **구현 위치** - 각 호스트의 **네트워크 인터페이스 카드(NIC) 또는 칩**에 구현됨 - 호스트 시스템 버스에 연결됨 - 하드웨어, 소프트웨어, 펌웨어의 조합 ### 기본 용어 **노드와 링크** ![[Data Link Layer - Figure 3.2 Nodes and Links.png|center|500]] - 일반적으로 두 엔드 호스트와 라우터는 **노드(node)**로, 그 사이의 네트워크는 **링크(link)**로 표시함 - 데이터 링크 계층에서의 통신은 **node-to-node** 통신임 - 인터넷의 한 지점의 데이터 유닛이 다른 지점에 도달하려면 많은 네트워크(LAN 및 WAN)를 통과해야 함 - 이러한 LAN 및 WAN은 라우터에 의해 연결됨 **Frame(프레임)** ![[Data Link Layer - Figure 3.4 A frame in a character-oriented protocol.png|center|600]] - 데이터 링크 계층에서는 **비트를 ==프레임(frame)==으로 패킹함** - Framing 과정을 통해 메시지를 송신지에서 수신지로 보내기 위해 필요한 정보들을 추가하여 메시지를 분리함 - 필요한 정보: 송신지 주소, 수신지 주소 등등 - 전체 메시지를 하나의 프레임에 담는 것은 일반적이지 않음 - 한 프레임이 매우 크기 때문에 흐름 제어 및 오류 제어가 매우 비효율적으로 처리됨 - 한 개의 큰 프레임에 전체 메시지가 포함되어 있을 경우, 한 비트의 오류가 전체 프레임을 다시 전송해야 할 수 있음 - **일반적으로 메시지는 작은 프레임으로 분할하여 전송**됨 - 이러한 경우 한 비트의 오류가 해당 작은 프레임에만 영향을 미치게 돼서 에러 관리가 쉬워짐 - 프레임의 사이즈는 고정 사이즈, 동적 사이즈 둘 다 가능 - 고정 크기의 프레임은 각각의 프레임이 동일한 크기를 가지기 때문에 프레임의 경계를 따로 정의할 필요가 없음 - 가변 크기의 경우에는 프레임의 크기가 다를 수 있으므로, **각 프레임의 시작과 끝을 정의하여 프레임의 경계를 명확히 해야함** **2가지 하위 계층 : DLC, MAC** ![[Data Link Layer - Figure 3.3. Dividing the data-link layer into two sublayers.png|center|450]] - 데이터 링크 계층은 매체, medium(e.g. 케이블, 무선)이 사용되는 방식을 제어함 - 전송 매체를 통해 데이터가 어떻게 전송되는지, 어떤 프레임 구조를 사용하는지 등을 제어함 - 매체의 용량을 얼만큼 사용하는가에 따라 2가지 방법으로 나뉨 - **broadcast link**: 링크의 용량 중 일부(broadcast 링크)만 사용하는 데이터 링크 계층 - **대부분 이 형태**, 다 들을 수 있으니까 신중하게 보내야 함 - 데이터 링크 계층에서 제공되는 서비스의 기능을 더 잘 이해하기 위해 두 개의 하위 계층으로 나눔 - **==데이터 링크 제어(Data Link Control, DLC)==** - **==매체 접속 제어(Media Access Control, MAC)==** - **point-to-point link**: 매체의 전체 용량을 사용하는 데이터 링크 계층 - 1:1 연결, 바로 데이터를 보내면 됨 ### 신뢰성 있는 전송을 위한 필수 요소 1. ACK, 응답 메시지 2. Timeout 3. Frame sequence number 4. ACK sequence number **1. ACK** ![[Data Link Layer - 그림 6-7 액(ACK) 사용.png|center|500]] - **문제 상황 : 프레임 전송 오류** - 송신 측이 보낸 프레임이 수신 측으로 가던 도중 사라지는 문제가 발생 - 송신 측은 처음 보낸 프레임이 사라졌다는 사실을 모른 채 두 번째 프레임을 보냄 - 수신 측 입장에서는 처음 보낸 프레임이 사라졌다는 사실을 알 수 없기 때문에, 송신 측이 두 번째로 보낸 프레임을 첫 번째 프레임이라 착각함 - 프레임 누락 발생! - **해결 방법 : 데이터 수신 시 ACK을 보냄** - 수신 측은 데이터를 수신하면 송신 측에 ACK을 보냄 - 송신자는 ACK을 수신한 후에 다음 프레임을 보냄 **2. Timeout** ![[Data Link Layer - 그림 6-8 ACK이 사라지는 경우.png|center|500]] - **문제 상황 : ACK 전송 오류** - 수신 측이 프레임을 받은 후 보낸 ACK이 전송 중 사라짐 - 송신 측은 ACK을 받아야만 다음 프레임을 보낼 수 있음 - 그러나 ACK이 사라졌기 때문에 송신 측은 다음 프레임을 보낼 수 없게 됨 - 수신 측도 ACK을 보낸 후 다음 프레임을 하염없이 기다리게 됨 - 결국 송신 측, 수신 측 모두 하염없이 기다림.. - **해결 방법 : timeout 시간 설정** - 적절한 timeout 시간을 정해두고 해당 시간이 지나면 프레임 혹은 ACK을 재전송함 **3. Frame sequence number** ![[Data Link Layer - 그림 6-9 타임아웃의 문제.png|center|500]] - **문제 상황 : timeout 후에 이전 프레임에 대한 ACK이 도착 (타임아웃 시간을 짧게 설정하는 경우)** - 송신 측이 보낸 프레임에 대해 수신 측이 ACK을 보냄 - 그러나 전송이 느려서 송신 측의 타임아웃에 걸림 - 타임아웃에 걸린 송신 측은 전송 오류가 발생했다고 판단해서 해당 프레임을 재전송하고, 그후 ACK이 도착함 - 수신 측은 재전송된 프레임에 대해 같은 프레임인지 인식 못 함 - 중복된 프레임 발생! ![[Data Link Layer - 그림 6-10 프레임 일련번호의 사용.png|center|500]] - **해결 방법 : frame에 번호를 붙여 구분** - frame에 sequence number를 붙이면 보내는 프레임이 몇 번째 프레임인지 정확하게 구분 가능함 - 따라서 프레임이 사라지거나 중복되는 경우 이를 확인할 수 있음 **4. ACK sequence number** ![[Data Link Layer - 그림 6-11 ACK 일련번호가 없는 경우의 문제.png|center|500]] - **문제 상황** - 수신 측이 보낸 ACK이 늦게 도착해서 송신 측에 타임아웃이 걸림 - 송신 측에서 0번 프레임을 재전송함 - 0번 프레임을 재전송한 후에 지연된 ACK이 도착함 - 송신 측은 재전송한 0번 프레임의 ACK이라고 생각하고 1번 프레임을 전송함 - 그러나 1번 프레임이 전송 중 사라짐 - 수신 측으로부터 재전송한 0번 프레임에 대한 ACK이 도착함 - 송신 측은 이를 1번 프레임에 대한 ACK이라고 착각하고 2번 프레임을 보냄 - 1번 프레임 실종을.. 아무도 몰랐다고 한다 ![[Data Link Layer - 그림 6-12 ACK 일련번호 사용.png|center|500]] - **해결 방법 : ACK에 번호를 붙여 구분** - ACK에도 sequence number를 붙여 구분함 - 송신 측에서 0번 ACK을 2번 받아서, 수신 측에 0번 프레임이 2번 도착했다는 사실을 알게됨 - 해당 ACK은 폐기 - 1번 프레임에 대한 ACK이 아직 안 왔으니 수신 측에 1번 프레임은 아직 도착하지 않았다는 걸 알게됨 - 1번 프레임에 대해 타임아웃이 끝날때까지 ACK이 도착하지 않으면 해당 프레임을 재전송함 > **==Piggy-backing==**: 데이터도 없이 ACK만 보내는 건 낭비니까, 메시지에 ACK을 얹어서 보내는 방식 ### Sliding Window Control ![[Data Link Layer - 그림 6-13 여러 개의 프레임을 보내고 ACK 한 번 받기.png|center|500]] **등장 배경** - 데이터를 보낸 후 멈추고(stop), ACK를 기다리는(wait) **Stop-and-Wait 방식**은 매우 느림 - 에러 없는 네트워크에서 ACK를 매번 기다리는 것은 낭비 - ACK 없이 한꺼번에 많은 양의 데이터를 보내면 전송속도가 올라감 - 이를 sliding window protocol 혹은 continues protocol 이라고 부름 **Window size** ![[Data Link Layer - 그림 6-14 슬라이딩 윈도우 프로토콜.png|center|400]] - Sliding window protocol의 보내는 쪽과 받는 쪽에서 **ACK 없이 보낼 수 있는 프레임의 개수** - 윈도우 크기가 4라는 의미는 보내는 쪽에서 ACK 없이도 4개의 프레임을 연속적으로 보낼 수 있다는 의미 - **받는 쪽에서는 마지막 4번째 프레임의 ACK만 보냄** → ACK를 받으면 다음 번 4개의 프레임을 전송 - Stop-and-Wait 방식을 window size가 1인 Stop-and-Wait ARQ 라 부름 **NAK 처리 방법에 따른 프로토콜 종류** - Sliding window protocol에서 수신B는 받지 못한 프레임에 대하여 ==**부정응답(NAK)**==을 발송함 ![[Data Link Layer - 그림 6-15 Go-Back-N ARQ.png|center|350]] - **Go-Back-N ARQ**에서 2번 NAK을 받은 경우, 2번 프레임부터 시작하여 2, 3, 4, 5의 4개의 프레임을 다시 보냄 - 작업이 단순하지만 패킷이 중복된다는 단점이 있음 ![[Data Link Layer - 그림6-16 Selective Repeat ARQ.png|center|400]] - **Selective Repeat ARQ**에서는 NAK을 받은 2번 프레임만 다시 전송함 → 2, 4, 5, 6의 4개의 프레임이 전송 - Selective Repeat ARQ를 사용하기 위해서는 수신 B가 버퍼에 프레임 3번을 저장했다가 프레임 2번을 받은 후 프레임을 순서대로 다시 조합 해야 함 - Go-Back-N ARQ에 비해 상대적으로 복잡함, 버퍼가 커야 함 ## 2. DLC sublayer의 역할 - DLC(Data Link Control)는 **두 인접 노드 간의 통신 과정**을 다룸 - 데이터 transmission type - Asynchronous transmission (비동기식 전송) : 예고 없이 데이터 보냄 - **Synchronous transmission** (동기식 전송) : 데이터를 전송 한다고 먼저 알려준 후 프레임을 보냄. 현재는 동기식 전송 사용 ### 2-1. ==Framing== **Framing 방법 1. Chracter-Oriented Framing** ![[Data Link Layer - Figure 3.4 A frame a character-oriented protocol.png|center|500]] - 데이터를 무조건 **8비트 문자(8-bit characters)** 단위로 표현하는 프레임 구성 방법 - **Header**: 출발지와 목적지 주소, 제어 정보를 담고 있음, 항상 8비트 배수임 - **Trailer**: **에러 감지**를 위한 중복 비트**(redundant bits)** 를 담고 있음, 항상 8비트 배수임 - **Flag**: **프레임 간의 구분**을 위해 시작과 끝에 8비트(1바이트)의 플래그(flag)가 추가함 - 텍스트 통신에 사용되지 않는 문자 중에서 선택됨 ![[Data Link Layer - Figure 3.5 Byte stuffing and unstuffing.png|center|600]] - **==Byte-stuffing==** - 플래그와 동일한 패턴을 가진 문자가 데이터 내에 포함되어 있는 경우, 이를 프레임의 구분자로 잘못 인식할 수 있음 - 이를 해결하기 위해 바이트-스터핑(byte-stuffing) 전략이 사용됨 - 미리 정의된 특수한 비트 패턴인 **ESC(Escape) 문자**가 데이터 섹션에 삽입되어, 이후에 오는 문자를 프레임의 데이터로 취급함 - 수신 측에서 ESC를 확인하면, ESC를 데이터 섹션에서 지우고 다음 문자를 데이터로 취급해서 프레임 구분에 영향을 미치지 않도록 함 - 만약 ESC도 데이터 내에 포함되어 있다면 그 또한 앞에 ESC를 붙여 보냄 **Framing 방법 2. Bit-Oriented Framing** ![[Data Link Layer - Figure 3.6 A frame in a bit-oriented protocol.png|center|500]] - 데이터를 **비트의 연속으로 바운더리 없이 표현**하는 프레임 구성 방법 - 각 프레임은 연속된 비트의 시퀀스로 이루어져 있음 - 프레임 간의 구분을 위해 일반적으로 **8비트의 플래그(01111110)**를 사용함 ![[Data Link Layer - Figure 3.7 Bit stuffing and unstuffing.png|center|600]] - **Bit stuffing** - 프레임 내에 플래그와 동일한 패턴이 나타나는 것을 방지하기 위해 비트 스터핑을 수행함 - 데이터 내에 0 다음에 연속적으로 1이 5개 이상 나오는 경우, **여분의 0을 삽입**하여 패턴 "01111110"이 플래그로 잘못 해석되는 것을 방지함 - 수신자는 데이터를 수신할 때 스터핑된 비트를 제거하여 원래의 데이터를 복원함 - "01111110" 뒤에 오는 추가된 0은 수신측에서 제거됨 ### 2-2. Error Control - 에러 제어는 **error detection**(문제가 있는지 감지)과 **error correction**(문제가 어디서 생긴 건지까지 알아냄)으로 나뉨 - 문제를 감지함으로써 수신자가 송신자에게 에러를 알리고 문제가 된 데이터를 다시 받을 수 있게 함 **통신 중 발생하는 에러** ![[Data Link Layer - Figure 3.8 Single-bit and burst error.png|center|500]] - 통신 시 간섭으로 인해 데이터에 예측못할 변형이 생김 - **single-bit error** - 주어진 데이터 유닛에서 1 bit만 변형된거 - 주로 유선에서 발생함 - **burst error** - 주어진 데이터 유닛에서 2개 이상의 bit 변형이 발생함 - 주로 무선에서 발생함 - 해결 과정 - Redundancy - EDC (Error Detection and Correction bits) : 에러 디텍션용 추가 비트 - EDC 필드가 클수록 오류 검출 및 수정의 신뢰성이 높아짐 - Detection 혹은 Correction - correction이 detection보다 상대적으로 어려움 - **Coding** - redundancy를 만드는 과정, 종류가 매우 다양함 **Error Control 방법 1. Block Coding(블록코딩)** ![[Data Link Layer - Figure 3.9 Process of error detection in block coding.png|center|500]] - 방법 1. **datawords**라고 불리는 블록으로 메세지를 나눔 2. r개의 redundant 비트를 더해서 **codewords** n을 만듦 (n = k+r) ![[Data Link Layer - Example 3.1.png|center|500]] - **Example 3.1** - 수신인이 011을 받았으면 유효한 codewords를 받은거임 - 111 받으면 유효한 codewords가 아니라서 버려짐 - 변형이 일어나서 000으로 바뀌었을 때 codeword에는 있어서 유효하다고 판단해버림 - 이 경우 에러 못 찾음 - codeword와 dataword의 비트 차가 작아서 발생한 문제임 - codeword가 길어질수록 detection 확률이 높아짐 **Hamming Distance 개념** - 같은 크기의 2개 words 사이의 hamming distance는 **대응되는 비트 간 몇 비트 차이나는지**를 의미함 - 두 words간 **XOR** 해서 1 결과값을 세면 쉽게 알 수 있음 - 항상 0보다 크거나 같음 ![[Data Link Layer - Example 3.2.png|center|500]] ![[Figure 3.10 Geometric concept explaining dmin in error detection.png|center|500]] - ==**minimum hamming distance**== - 모든 가능한 codeword 쌍에서 가장 작은 hamming distance를 의미함 - 만약 전송 중에 s개의 오류가 발생했다면, 수신된 코드워드와 전송된 코드워드 간의 hamming distance는 s가 된다 - 모든 경우에서 최대 s개의 오류를 감지할 수 있도록 보장하려면, 블록 코드(Block Code)의 **==최소 해밍 디스턴스는 s + 1이어야 함==** - **최소 해밍 디스턴스가 2면 1 비트 에러까지 찾을 수 있음** - **수신된 코드워드가 유효한 코드워드와 매치되지 않도록 하기 위함** - **detection 비트 수를 정하는데 사용됨** ![[Data Link Layer - Example 3.4.png|center|500]] **Linear Block Codes 개념** - 2개의 유효한 codeword의 XOR이 다른 유효한 codeword를 만들어 내면 Linear Block Code임 - 오늘날 모든 블록 코드는 선형 블록 코드라는 블록 코드의 부분집합에 속함 - 선형 블록 코드에서 최소 해밍 디스턴스는 0이 아닌 1의 개수가 가장 적은 codeword의 1의 개수임 ![[Data Link Layer - Table 3.1 A code for error detection in Example 3.1.png|center|400]] **Error Control 방법 2. Parity-Check Code** ![[Data Link Layer - Figure 3.11 Encoder and decoder for simple parity-check code.png|center|600]] - Linear Block Code의 한 종류 - k 비트의 데이터워드를 변환하여 n 비트의 코드워드를 생성함 (여기서는 n = k+1) - 데이터의 오류를 감지하기 위해 추가된 특별한 비트인 **==parity bit==**를 사용함 - single bit parity : 단일 비트 오류를 검출할 수 있음 - two-dimensional bit parity : 단일 비트 오류를 검출하고 수정할 수 있음 - parity-check code는 송신 측 인코더와 수신 측 디코더의 구성으로 작동됨 - 인코더는 데이터워드와 패리티 비트를 생성하여 코드워드를 생성하는 역할을 함 1. 인코더는 데이터워드의 복사본을 입력으로 사용하여 패리티 비트를 생성함 2. 데이터워드의 비트와 패리티 비트는 함께 5비트의 코드워드를 형성함 3. **이 코드워드 내의 1의 개수가 짝수가 되도록 패리티 비트가 선택됨** - 이때 데이터워드의 비트들은 modulo-2 연산을 수행하여 패리티 비트를 생성함 - parity bit = 데이터워트 비트 1 + ... 데이터워트 비트 4 - 디코더는 수신된 코드워드를 분석하여 오류를 감지하고 필요한 경우 수정함 1. 수신자는 송신자로부터 전송된 5비트 워드를 받음 2. 수신기의 체크기(checker)는 송신기의 생성기와 동일한 작업을 수행함 - 이때 4비트가 아니라 parity bit까지 해서 5비트에 대한 연산을 수행함 - 연산의 결과로 **==신드롬(Syndrome)==**을 얻을 수 있음 (단 하나의 비트) 3. 신드롬은 수신된 코드워드 내의 1의 개수에 따라 결정됨 - 만약 수신된 코드워드 내의 1의 개수가 짝수라면, 신드롬은 0이 됨. 이는 데이터가 송신 측에서 전송된 것과 동일하다는 것을 나타냄 - **수신된 코드워드 내의 1의 개수가 홀수라면, 신드롬은 1이 됨. 이는 데이터에 오류가 있는 것을 나타냄** - 이 경우에는 데이터가 버려짐 ![[Data Link Layer - Parity check code.png|center|500]] - **치명적 단점: 에러가 짝수개만큼 생기면 못 찾음** - 홀수 개의 에러만 감지할 수 있음 **Error Control 방법 3. ==Cyclic Redundancy Check (CRC)==** - 하나의 추가적인 property를 가진 특별한 Linear Block Code - 코드워드가 순환적으로 이동(회전)되면 다른 코드워드가 됨 = cyclic code - 예를 들어, 코드워드가 1011000일 때, 왼쪽으로 순환 이동하면 0110001이 됨 - 에러를 수정하기 위해 cyclic code를 만들 수 있음 - cyclic redundancy check(CRC)에 대해 알아보자 - 아래는 linear 하면서 cyclic한 CRC 코드 예시임 ![[Data Link Layer - Table 3.3. A CRC code with C(7,4).png|center|400]] ![[Data Link Layer - Figure 3.12 CRC encoder and decoder.png|center|600]] - **encoder** - 인코더에서는 데이터워드가 k 비트이며, 코드워드가 n 비트임 (이미지에서는 k=4, n=7) - 데이터워드의 크기를 늘리기 위해 우측에 n - k개의 0을 추가하고 이 확장된 결과 값은 제너레이터에 들어감 - 제너레이터는 크기가 n - k + 1(4bit)인 divisor를 사용하여 확장된 데이터워드(7bit)를 나눔 (modulo-2 division) - 나머지는 데이터워드에 추가되어 코드워드를 생성하며, 몫은 폐기됨 - **decoder** - 디코더는 코드워드를 수신하고 모든 n 비트의 사본을 checker에 공급함 - checker에서 생성된 나머지는 n - k 비트의 신드롬으로, 이는 Decision logic에 공급됨 - **==신드롬 비트가 모두 0이면==, 코드워드의 왼쪽 4비트가 데이터워드로 수용됩니다(오류 없음으로 해석)** - **그렇지 않으면, 4비트가 폐기됨 (오류 발생)** ![[Data Link Layer - Figure 3.13 Division in CRC encoder.png|center|500]] - n - k 만큼 0을 추가한 확장된 데이터워드를 divisior로 나누는 방법 - 나누는 숫자(1011)로 나눌 수 있는 가장 긴 부분을 찾음 - 못 나누면 0000인거임 - 몫은 버리고 나머지를 dataword 뒤에 붙여서 codeword로 사용함 ![[Data Link Layer - Figure 3.13 Division in CRC encoder2.png|center|600]] - CRC의 장점 - 싱글 에러와 홀수개의 에러는 다 detect 가능함 - 하드웨어 및 소프트웨어에서 쉽게 구현 가능 - 하드웨어로 구현할 때 특히 빠르게 동작함 > **checksum** >- 임의 길이의 메시지에 적용할 수 있는 오류 감지 비트 >- 인터넷에서는 체크섬 기법이 데이터 링크 레이어가 아닌 네트워크 및 전송 레이어에서 주로 사용됨 ## 3. DLC sublayer의 프로토콜 ### HDLC - HDLC(High-level Data Link Control) : point-to-point와 multipoint 링크 상에서 통신하기 위한 bit-oriented 프로토콜 - 두가지 전송 모드를 제공함 - 정상 응답 모드(NRM, normal response mode) - 구성이 균형적이지 않음 = 주 기지국은 명령을 보낼 수 있지만, 이차 기지국은 응답만 할 수 있음 - point-to-point와 multipoint 링크 둘 다에 사용됨 - **==비동기 균형 모드(ABM, asynchronous balanced mode)==** - 구성이 균형적임(오늘날 가장 흔함) - point-to-point 링크이고, 각 기지국은 주 기지국도 될 수 있고 이차 기지국도 될 수 있음 = 다 동등함 ![[Data Link Layer - Figure 3.17 HDLC frames.png|center|600]] - 상황에 맞게 유연성을 제공하기 위해 3가지 유형의 프레임이 있음 - 각 유형은 다른 유형의 메시지를 전송하기 위한 봉투 역할을 함 ![[Data Link Layer - Figure 3.18 Control field format for the different frame types.png|center|600]] - Control 필드는 프레임의 종류와 기능을 정의함 - **==I-frames==**: **사용자 데이터**와 사용자 데이터와 관련된 제어 정보(control information)를 전송하는 데 사용됨 - **piggybacking** 방식을 사용해서 흐름 및 오류 제어 정보를 포함할 수 있음 - 컨트롤 필드 구조 - 첫 번째 비트는 유형을 정의함 - 다음 3비트는 N(S)로, 프레임의 순서 번호를 정의함 - 3비트로 0부터 7까지의 순서 번호를 정의할 수 있음 - 마지막 3비트는 피기백이 사용될 때 확인 번호에 해당하는 N(R)임 - P/F 비트 필드는 이중 목적의 단일 비트임 - 프레임이 기본 스테이션에서 보조 스테이션으로 전송될 때 폴(Poll)을 의미함 - 프레임이 보조 스테이션에서 기본 스테이션으로 전송될 때 최종(Final)을 의미함 - **S-frames**: 제어 정보(control information)를 전송하는 데만 사용됨 - 피기백이 불가능하거나 부적절할 때 흐름 및 오류 제어에 사용됨 - information 필드가 없음 - 컨트롤 필드 구조 - 첫 2비트는 10임 - 마지막 3비트인 N(R)은 확인 번호(ACK) 또는 부정적인 확인 번호(NAK)에 해당함 - code로 불리는 2비트는 S-프레임 자체의 유형을 정의하는 데 사용됨 - 00: 수신 준비 (RR) / N(R)은 확인 번호 - 10: 수신 준비하지 않음 (RNR) / N(R)은 확인 번호 - 프레임 또는 프레임 그룹의 수신을 확인하고, 수신 측이 바쁘기 때문에 더 많은 프레임을 받을 수 없음을 알림 - 01: 거부 (REJ) - 11: 선택적 거부 (SREJ) - **U-frames**: 시스템 관리를 위해 예약되어 있음 - 일단 비워둠 - 링크 자체를 관리하기 위한 정보 ## 4. MAC sublayer의 프로토콜 ![[Data Link Layer - Figure 3.3. Dividing the data-link layer into two sublayers.png|center|450]] - **broadcast link**의 Data-link layer는 2가지 하위 계층으로 나뉨 - DLC: 데이터 전송에 관련된 작업을 처리 - MAC: 네트워크에서 물리적 매체에 접근하고 통신하기 위한 프로토콜을 다룸 - 노드 또는 스테이션이 연결되어 있고 다중 접속 또는 broadcast 링크와 같은 공통 링크를 사용하는 경우, 링크에 대한 접근을 조정하기 위해 multiple-access protocol 이 필요함 **Multiple access protocols** - **배경** - 단일 공유 브로드캐스트 채널을 사용할 때 **동시에 두 개 이상의 노드가 전송**하면 간섭 발생 - 한 노드가 두 개 이상의 신호를 동시에 수신하면 충돌(collision) 발생 - **해결 방법** - **분산 알고리즘**: 노드가 채널을 어떻게 공유할지 결정함. 즉, 노드가 언제 전송할 수 있는지 결정함 - 채널 공유에 대한 통신은 채널 자체를 사용함 - 조정을 위한 채널 외 밴드(out-of-band) 채널이 없음 - **이상적인 Multiple access protocols** - R bps 속도의 다중 접근 채널 (MAC)에서 한 노드가 전송을 원할 때, 속도 R로 전송할 수 있어야 함 - M개의 노드가 전송을 원할 때, 각각 평균 속도 R/M으로 전송할 수 있음 - fully decentralized: 전송을 조정하는 특별한 노드 없음, 클록/슬롯의 동기화 없음 - 단순함 **MAC 프로토콜 분류** 1. **채널 분할 프로토콜** - 채널을 작은 “조각”(시간 슬롯, 주파수, 코드)으로 나눔 - 높은 부하에서 채널을 효율적이고 공정하게 공유함 - 낮은 부하에서는 비효율적임: 채널 접근 지연 발생, 활성 노드가 하나일 때도 1/N 대역폭 할당 - 조각을 노드에 독점 사용을 위해 할당함 - 예시 : TDMA, FDMA 2. **랜덤 액세스 프로토콜** - 채널을 나누지 않음, 충돌 허용 - 노드가 패킷을 전송하려고 할 때 노드 간 사전 조정 없이 전송함 - 낮은 부하에서 효율적임: 단일 노드가 채널을 완전히 활용 가능 - 높은 부하에서 충돌 오버헤드 발생 - 충돌에서 “복구”함 - 충돌을 어떻게 감지할지(캐리어 센싱), 어떻게 복구할지(e.g. delayed retransmissions) 정해야 함 - 예시 : ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA/CA 3. **“taking turns”** - 노드가 교대로 사용하지만, 더 많은 데이터를 전송해야 하는 노드는 더 긴 시간을 가질 수 있음 - 앞선 방식의 장점을 취함 ### 4-1. Channel division protocol **TDMA** ![[Data Link Layer - time division multiple access.png|center|400]] - TDMA: time division multiple access - “라운드”로 채널에 접근 (채널을 시간 단위로 나누어 각 노드가 정해진 순서대로 주기적으로 접근하는 것) - 각 스테이션은 각 라운드에서 고정 길이 슬롯(패킷 전송 시간)을 가짐 - 사용되지 않는 슬롯은 비어 있음 **FDMA** ![[Data Link Layer - frequency division multiple access.png|center|400]] - FDMA: frequency division multiple access - 채널 스펙트럼을 주파수 밴드로 나눔 - 각 스테이션에 고정 주파수 밴드를 할당 - 주파수 밴드의 사용되지 않은 전송 시간은 비어 있음 ### 4-2. Random-access protocols - Random-access 방법은 **스테이션 간의 관계가 평등함** - 어떠한 스테이션이 다른 스테이션보다 우월하다거나 다른 스테이션을 제어하지 않음 - 매 순간마다 데이터를 전송할 준비가 된 스테이션은 프로토콜의 절차에 따라 전송 여부를 결정함 - **특징** - Random Access: 전송 시간이 예정되어 있지 않음 - Contention Method: 어떤 스테이션이 다음에 전송해야 하는지 규칙이 없음. 이기는 놈이 보내 - **둘 이상의 스테이션이 동시에 전송을 시도하면 collision 이 발생할 수 있음** **ALOHA** ![[Data Link Layer - Additive Links On-line Hawaii Area.png|center|400]] - ALOHA = Additive Links On-line Hawaii Area - 가장 먼저 개발된 random access 프로토콜 - radio(wireless) LAN을 위해 고안되었지만 어떤 공유 매체에서든 사용할 수 있는 메커니즘임 - ALOHA를 사용하는 경우, 한 스테이션이 데이터를 전송할 때 다른 스테이션이 동시에 데이터를 전송할 수 있음 - 스테이션들이 전송을 시도할 때 충돌이 발생할 수 있음 - 위성 시스템, 5G 기지국에서도 사용중 **ALOHA - Pure ALOHA** ![[Data Link Layer - Figure 3.24 Frames in a pure ALOHA network.png|center|500]] - 각 스테이션은 보내고 싶은 프레임이 있으면 언제든 보내버림 - **Figure 3.24** - 공유 채널에 대한 액세스를 위해 서로 경쟁하는 4개의 스테이션 - 각 방송국은 2개의 프레임을 보냄 (총 8개) - 이러한 프레임 중 일부는 공유 채널에 대해 여러 프레임이 경합 중이기 때문에 충돌함 (2개의 프레임만 생존) ![[Data Link Layer - Figure 3.25 Procedure for pure ALOHA protocol.png|center|500]] - **충돌 감지** - 스테이션은 프레임을 전송할 때 수신기가 응답(ACK)을 기다림 - 일정 시간이 경과한 후에도 응답이 도착하지 않으면 스테이션은 프레임(또는 응답)이 파괴되었다고 가정하고 프레임을 다시 전송함 - ==**Backoff**== - 두 개 이상의 스테이션이 전송하는 경우 충돌이 발생함 - 이러한 스테이션들이 모두 타임아웃 후에 프레임을 재전송하려고 하면 프레임이 다시 충돌할 수 있음 - 따라서 타임 아웃 기간이 지난 후, 각 스테이션은 프레임을 재전송하기 전에 backoff라고 불리는 랜덤 시간을 기다림 - **재전송 시도 횟수 제한** - Pure ALOHA는 프레임 재전송으로 인한 채널 혼잡을 방지하고자 했음 - 스테이션은 일정한 최대 재전송 횟수(Kmax) 이후에는 전송을 포기하고 나중에 다시 시도해야 함 - **Timeout 시간 설정** - maximum possible round-trip propagation delay과 같음 - 가장 멀리 떨어진 두 스테이션 간에 프레임을 전송하는 데 필요한 시간의 두 배 (2 × $T_p$) - **Binary exponential backoff (이진 지수 후퇴)** - backoff time $T_B$를 결정하는 방법 중 하나 - $T_B$는 일반적으로 시도 횟수(K)에 따라 결정되는 랜덤한 수임 - 각 재전송마다 R(0 ~ $2^K$ – 1)이라는 곱셈 계수가 무작위로 선택되고, 이는 $T_p$(maximum propagation time) 또는 $T_{fr}$(프레임을 전송하는 데 필요한 평균 시간)에 곱해짐 - $K_{max}$는 일반적으로 15로 선택됨 ![[Data Link Layer - Figure 3.26 Vulnerable time for pure ALOHA protocol.png|center|500]] - **Vulnerable time** - 건들면 안 되는 시간. 안전한 전송을 위해 이 시간을 보장해줘야 함 - **==Pure ALOHA의 vulnerable time은 $2*T_{fr}$==** - **Throughput** - = 성공적으로 전송된 프레임의 평균적인 수 - Normalized throughput $S$ 는 one frame transmission time 동안 성공적으로 전송된 프레임의 평균적인 수를 의미함 - $S=G*e^{-2G}$ - one frame transmission time 동안 시스템이 생성한 프레임의 평균적인 수 - $S_{max}$는 $G=1/2$ 일 때 0.184임 **ALOHA - Slotted ALOHA** - 시간을 동일한 크기의 슬롯으로 나눠서 스테이션이 슬롯 시작할 때만 보내게 함 - **충돌 없음**: 노드는 다음 슬롯에서 새로운 프레임을 전송할 수 있음 - **충돌 발생**: 노드는 성공할 때까지 각 후속 슬롯에서 확률 p로 프레임을 재전송함 - 충돌 후 모든 노드가 동시에 재전송을 시도하면 다시 충돌이 발생할 가능성이 매우 높음. 따라서, 각 노드가 무작위 확률 p 로 재전송 시간을 선택하면, 노드들이 동일한 슬롯에서 다시 전송을 시도할 확률이 줄어들어 충돌이 줄어듦 ![[Data Link Layer - Slotted ALOHA.png|center|400]] - **Vulnerable time** - 건들면 안 되는 시간. 안전한 전송을 위해 이 시간을 보장해줘야 함 - **==Slotted ALOHA의 vulnerable time은== $T_{fr}$** - $T_{fr}$ = 프레임을 전송하는 데 필요한 평균 시간, 프레임 길이 - **Throughput** - $S=G*e^{-G}$ - $G$는 트래픽이 얼마나 많이 몰렸는지를 나타냄 - $S_{max}$는 $G=1$ 일 때 0.368임 - 훨씬 좋은 성능 **CSMA** - **CSMA = Carrier Sense Mulitiple Access** - **Carrier Sense** : 데이터를 보내기 전에 남이 보내는 걸 감지함(medium 감지중) - 충돌을 최소화하고 성능을 높이기 위해 고안됨 - ALOHA는 보낼 때 신경을 안 쓰니까 throughput이 너무 낮음 - 채널이 비어 있으면 전송하고, 사용 중이면 기다림 - 충돌이 발생할 수 있으며, 충돌 시 전체 프레임 전송 시간이 낭비됨 - 캐리어 센싱을 해도 충돌이 발생할 수 있음 - 전파 지연으로 인해 두 노드가 서로의 전송 시작을 듣지 못할 수 있음 ![[Data Link Layer - Figure 3.30 Vulnerable time in CSMA.png]] ![[Data Link Layer - Figure 3.31 Behavior or three persistence methods.png]] **CSMA/CD** ![[Data Link Layer - Figure 3.33 Collision of the first bits in CSMACD.png|center|500]] ![[Data Link Layer - Figure 3.34 Collision and abortion in CSMACD.png|center|500]] - CSMA + collision detection - 충돌 감지를 통해 충돌 시 **전송을 중단하고**, 채널 낭비를 줄임 - ALOHA보다 효율적이며, 최대 전파 지연 시간과 전송 시간의 비율에 따라 효율성이 달라짐 - **Ethernet CSMA/CD 알고리즘** - NIC가 데이터그램을 수신해서 프레임을 생성함 → 채널 센싱해서 비어 있으면 전송 시작하고 사용 중이면 비어 있을 때까지 기다림 → 충돌 없이 전체 프레임을 전송하면 전송 완료 - 전송 중 다른 전송을 감지하면 전송을 중단하고 jam signal을 보낸 후, binary (exponential) backoff를 수행함 - K 값 선택 범위가 exponential 하게 증가하기 때문에 같은 숫자를 고르게 될 확률은 점점 더 떨어짐 ### 4-3. Controlled Access Protocol - 누가 언제 보낼지 잘 제어해서 충돌이 없도록 함 - 충돌이 감소하는 대신 컨트롤 오버헤드가 증가함 **Reservation** ![[Data Link Layer - Figure 3.37 Reservation access method.png|center|600]] - 시스템은 데이터를 보내려면 먼저 예약해야 함 - 시간이 쪼개짐 **Polling** ![[Data Link Layer - Figure 3.38 Select and poll functions.png|center|500]] - **마스터 노드**가 다른 노드에게 순서대로 전송을 요청함 - select and poll - 모든 데이터 교환은 primary 디바이스에 의해서만 교환됨 - 폴링 오버헤드, 지연, 마스터 노드 - single point of failure가 우려됨 **Token Passing** - **제어 토큰**이 순차적으로 한 노드에서 다음 노드로 전달됨 (토큰 메시지 사용) - 토큰 가지고 있는 애(predecessor이 successor에게 넘겨줌)만 전송해라 - 거의 쓰는 데 없음 ## 5. 데이터 링크 계층의 Addressing ![[Data Link Layer - data link layer addressing.png|center|300]] - 네트워크 계층에서는 IP 주소를 identifier로 사용함 - 근데 이것만으로는 지나갈 경로를 알 수 없음 - 그래서 데이터 링크 계층에서는 근접 노드의 주소가 필요함 **MAC address** - 로컬에서 한 인터페이스에서 물리적으로 연결된 다른 인터페이스로 프레임을 전달하는 데 사용됨 - 대부분의 LAN에서 48-bit MAC 주소 사용, NIC ROM에 저장되거나 소프트웨어로 설정 가능 - 예: 1A-2F-BB-76-09-AD - IP 주소는 네트워크 계층 주소, 인터페이스를 위한 주소. 예: 128.119.40.136 - 각 LAN 인터페이스는 고유한 48-bit MAC 주소를 가지고, 로컬에서 고유한 32-bit IP 주소를 가짐 - **MAC 주소 할당**은 IEEE에 의해 관리됨 - 제조사는 MAC 주소 공간의 일부를 구매하여 uniqueness를 보장함 - MAC flat 주소 : **인터페이스를 한 LAN에서 다른 LAN으로 이동 가능**. IP 주소는 이동 불가 (노드가 연결된 IP 서브넷에 따라 다름) **ARP: address resolution protocol** - IP 주소를 알고 있을 때, 인터페이스의 MAC 주소를 어떻게 알 수 있을까? - 각 LAN의 IP 노드(호스트, 라우터)는 **ARP 테이블**을 가짐 - 일부 LAN 노드의 IP/MAC 주소 매핑 포함 - **TTL (Time To Live)**: 주소 매핑이 잊혀지기 전의 시간 (일반적으로 20분) ![[Data Link Layer - ARP Routing to another subnet.png|center|500]] - **동작 예시** : A가 B에게 데이터그램을 보내고 싶을 때 - 내부 - B의 MAC 주소가 A의 ARP 테이블에 없으면, A는 ARP를 사용하여 B의 MAC 주소를 찾음 - B의 IP 주소를 포함한 ARP 쿼리를 브로드캐스트함 (목적지 주소 FF-FF-FF-FF-FF-FF) - LAN에 있는 모든 노드가 이 쿼리를 받음 - B가 이에 MAC 주소를 포함한 ARP response로 답함 - A가 응답을 받으면 로컬 ARP 테이블에 B 엔트리를 추가함 - 외부 : **A가 B에게 데이터그램을 보낼 때 라우터를 이용해 다른 서브넷으로 보내는 과정** - **A**는 IP 소스 A와 목적지 B로 IP 데이터그램을 생성함 - **A**는 A-to-B IP 데이터그램을 포함하는 링크 계층 프레임을 생성함 (프레임의 목적지는 R의 MAC 주소) - **A**에서 **R**로 프레임 전송 - **R**이 프레임을 수신하고, 데이터그램을 제거하여 IP 계층으로 전달함 - **R**이 출력 인터페이스를 결정하고, IP 소스 A와 목적지 B로 데이터그램을 링크 계층으로 전달함 - **R**이 A-to-B IP 데이터그램을 포함하는 링크 계층 프레임을 생성함 (프레임의 목적지 주소는 B의 MAC 주소) - **R**이 링크 계층 프레임을 전송함 - **B**가 프레임을 수신하고, IP 데이터그램을 추출하여 IP 계층으로 전달함 **MAC 주소 종류** - **유니캐스트 주소(Unicast Address)** - 특정한 하나의 호스트에게만 전달되는 주소 - 각 호스트 또는 인터페이스에는 유니캐스트 주소가 할당됨 - 두번째 숫자가 **짝수면** 유니캐스트 주소임 - **멀티캐스트 주소(Multicast Address)** - 몇몇 링크 계층 프로토콜에서는 멀티캐스트 주소를 정의함 - 멀티캐스트 주소는 하나의 송신자가 여러 수신자에게 메시지를 전송하는데 사용됨 - 즉, 한 번의 전송으로 여러 대의 호스트에게 메시지를 전달할 수 있음 - 두번째 숫자가 **홀수면** 멀티캐스트 주소임 - **브로드캐스트 주소(Broadcast Address)** - "일대전체" 주소를 의미 - 즉, 이 주소로 전송된 메시지는 네트워크 상의 모든 호스트에게 전달됨 - 네트워크 상의 모든 호스트에게 메시지를 전달할 때 사용함 - 다 1로 이루어지면 브로드캐스트 주소임 - FF:FF:FF:FF:FF:FF > 가장 일반적인 LAN인 이더넷의 링크 계층 주소는 콜론으로 구분된 12개의 16진수로 표시되는 48비트(6바이트)로 표현됨 ## 6. 스위치 ### switches **스위치의 역할** - link layer 장치 - Ethernet 프레임을 저장하고 전달함 - 수신 프레임의 MAC 주소를 검사하고, 선택적으로 프레임을 하나 이상의 출력 링크로 전달함 - 세그먼트에서 프레임을 전달할 때 CSMA/CD를 사용하여 세그먼트에 접근함 - transparent : 호스트는 스위치의 존재를 인식하지 못함 - plug-and-play, self-learning : 스위치는 설정이 필요 없음 **스위치: 다중 동시 전송** ![[Data Link Layer - switch multiple simultaneous transmissions.png|center|200]] - 호스트는 스위치에 전용 직렬 연결을 가짐 - 스위치는 패킷을 버퍼링함 - 각 수신 링크에서 Ethernet 프로토콜을 사용하여 충돌이 없음, full duplex 통신이 가능 - 각 링크는 자체 충돌 도메인을 가짐 - **스위칭**: A-to-A’와 B-to-B’는 동시에 전송 가능, 충돌 없이 통신할 수 있음 - 하지만 A-to-A’와 C-to-A’는 동시에 발생할 수 없음 = 동시에 여러 호스트로부터 수신은 불가능 **스위치 포워딩 테이블** ![[Data Link Layer - Switch self-learning.png|center|250]] - 각 스위치는 스위치 테이블에 **호스트의 MAC 주소, 호스트에 도달하기 위한 인터페이스**, 타임 스탬프 같은 정보를 저장하고 있음 (라우팅 테이블과 유사함) - 스위치 테이블은 일종의 라우팅 프로토콜처럼 작동해서 항목을 생성하고 유지함 - **self-learning** - 스위치는 어떤 호스트가 어떤 인터페이스를 통해 도달 가능한지 학습함 - 프레임이 수신되면, 스위치는 송신자의 위치(수신 LAN 세그먼트)를 “학습”함 - sender/location 쌍을 스위치 테이블에 기록함 - self-learning 스위치는 서로 연결될 수 있음 - **frame filtering/forwarding** - 프레임이 스위치에서 수신될 때 - 수신 링크와 송신 호스트의 MAC 주소를 기록함 → MAC 목적지 주소를 사용하여 스위치 테이블을 색인함 → 목적지 항목이 발견되면 목적지가 프레임이 도착한 세그먼트에 있는 경우 프레임을 폐기하고 아니면 항목에 지정된 인터페이스로 프레임을 전달함 - 목적지 항목이 발견되지 않으면 flooding 함 (도착한 인터페이스를 제외한 모든 인터페이스로 전달함) - e.g. 프레임의 목적지 A’의 위치가 알려지지 않음 - flooding - e.g. 목적지 A의 위치가 알려짐: 한 링크로만 선택적으로 전송 **스위치와 라우터의 비교** - 둘 다 store-and-forward 장치임 - **라우터**: 네트워크 계층 장치 (네트워크 계층 헤더 검사) - **스위치**: 링크 계층 장치 (링크 계층 헤더 검사) - 둘 다 포워딩 테이블을 가지고 있음 - **라우터**: 라우팅 알고리즘과 IP 주소를 사용하여 테이블 계산 - **스위치**: 플러딩과 학습을 통해 포워딩 테이블 학습, MAC 주소 사용 ### VLANs ![[Data Link Layer - Port-based VLANs.png|center|400]] - **VLAN 동기** - LAN의 확장성 문제 및 사용자 연결 지점 변경 시 발생하는 문제 해결을 위해 VLAN이 필요함 - 단일 브로드캐스트 도메인에서는 효율성, 보안, 프라이버시 문제가 발생할 수 있음 - VLAN 기능을 지원하는 스위치는 단일 물리적 LAN 인프라에서 여러 개의 **가상 LAN**을 정의하도록 구성할 수 있음 - **포트 기반 VLAN** - 스위치 포트를 그룹화하여 단일 물리적 스위치가 여러 개의 가상 스위치처럼 작동함 - **트래픽 격리**: 포트 1-8로부터의 프레임은 포트 1-8로만 전달됨 - **동적 멤버십**: 포트는 VLAN 간에 동적으로 할당될 수 있음 - VLAN 간의 트래픽, 포워딩은 라우팅을 통해 전달됨 - **여러 스위치에 걸친 VLAN** - **트렁크 포트**를 사용하여 여러 스위치 간에 VLAN 프레임을 전달함 - 802.1Q 프로토콜을 사용하여 트렁크 포트 간의 프레임에 VLAN ID 정보를 추가/제거함