13. Link layer

본 내용은 Computer networking : a top-down approach 책을 바탕으로 정리하였습니다.

 

Index

• 1. link layer 소개
• 2. link layer services
• 3. 오류 검출 및 정정 기술
• 4. 다중 접속 링크와 프로토콜
• 5. CSMA, CSMA/CD 프로토콜

 

1. link layer 소개

 

드디어 링크 계층까지 왔다!!

앞에서는 네트워크 계층이 호스트 사이에서 통신 서비스를 제공하는 것까지 살펴보았다.

이번엔 네트워크 계층에서 내려와 링크 계층에서 개별 링크를 따라 패킷이 어떻게 전달되는지 살펴볼 것이다.

 

먼저 몇 가지 용어에 대해 정리해보자.

 

• 노드 : 호스트, 라우터, 스위치 등이 노드가 될 수 있다.
• 링크 : 인접한 노드들을 연결하는 통신 채널로 유. 무선, LAN이 있다.
• link layer의 PDU : frame

 

link layer 의 특성, 흐름

 

• 물리적으로 인접한 노드 간에 datagram을 전송한다.
• datagram을 전송하는 링크는 프로토콜마다 다양하다.
• 링크에 따라 다른 서비스를 제공한다.
• MTU : 링크 계층에서 보낼 수 있는 최대 패킷의 크기를 말한다.

 

2. link layer services

 

2.1 링크 계층이 제공하는 서비스

 

• 프레임화 : 네트워크 계층 datagram을 링크상으로 전송하기 전 링크 계층 프레임에 캡슐화한다. 이때 프레임은 datagram이 들어있는 data 필드와 여러 개의 헤더 필드로 구성된다.
• 링크 접속 : MAC(매체 접속 제어) 프로토콜은 링크상으로 프레임을 전송하는 규칙에 대해 명시한다.
• 신뢰적 전달과 오류 검출 : 앞서배운 트랜스포트 계층과 마찬가지로 링크 계층도 ack, retransmission, checksum, timeout으로 신뢰적 전달 서비스와 오류 검출을 제공한다.
• flow control : 노드 간 송신에서 overflow를 방지한다.
• 양방향 통신

 

 

2.2 링크 계층이 구현되는 위치

 

링크 계층에 대해 자세히 알아보기 전에 링크 계층이 구현되는 위치에 대해서 살펴보자.

 

 

위 그림은 일반적인 호스트 구조를 보여준다.

 

대부분의 링크 계층은 네트워크 인터페이스 카드 라고 알려진 네트워크 어댑터에 구현된다.

가운데엔 컨트롤러가 있고, 컨트롤러는 위에서 말한 링크 계층의 서비스들을 제공한다.

 

좀 더 자세히 보면, 컨트롤러와 cpu,메모리 사이엔 버스 모양이 있는데, 이를 호스트 버스라 한다.

 

2.3 adapter communicating

 

 

위 그림은 송신자와 호스트 연결을 내부에 있는 어댑터를 통해 보여준다.

 

먼저 송신자에서 datagram을 보낼 때 컨트롤러는 datagram을 캡슐화한 후, frame에 넣고, 에러를 감지하기 위한 error check bit를 넣어 보내준다.

이후 수신측은 프레임을 받고, 에러와 flow control을 체크한 후, datagram을 추출하고 상위 계층으로 보내게 된다.

물론 datagram을 보내니 다음은 network layer가 될 것이다.

 

 

3. 오류 검출 및 정정 기술

 

앞서 우린 트랜스포트 계층에서도 이와 같은 서비스가 제공되는 것을 보았다.

이번엔 링크 계층에서 오류 검출, 정정하는 데 사용할 수 있는 기술들에 대해 알아보자.

 

3.1 패리티 검사

 

가장 단순한 형태의 오류 검출인 1차원 패리티 비트의 사용을 먼저 다뤄보자.

 

1차원 패리티 검사

패리티 검사는 짝수와 홀수 패리티 기법이 있고, 사용자는 단순히 하나의 비트를 추가하여

1의 d+1개의 비트들의 1의 개수가 짝수 또는 홀수 개가 되도록 선택한다.

수신자는 이 비트를 받고, d+1개의 비트들 중 1의 개수를 계산하면 끝난다.

 

2차원 패리티 검사

2차원 패리티 검사는 d개의 비트들을 i개의 행과 j개의 열로 나눈다.

모든 행과 열에 대해 1차원 패리티 검사를 하는 기법이라고 보면 된다.

 

 

3.2 체크섬 방법

 

체크섬 기술에서는 d비트들을 일련의 k 비트의 정수처럼 다룬다.

이들 k 비트 정수들을 모두 더해 그 결괏값을 오류 검출 비트로 사용하는 것이다.

 

인터넷 체크섬

인터넷 체크섬은 위에 설명한 방식을 따른다. 송신자와 수신자의 역할을 분류해보자.

체크섬을 구하는 방법 : https://suhwanc.tistory.com/105

 

 

sender

• 데이터의 바이트를 연속된 16비트 정수로 변환한다.
• 이 체크섬을 세그먼트 헤더에 넣어준다.

 

receiver

• (체크섬을 포함한) 수신 데이터의 합의 1의 보수를 취한 후, 그 결과가 모두 1인 비트로 구성되어 있는지 계산한다.
• 만약 한 비트라도 0이면 오류가 발생한 것이다.

 

3.4 순환 중복검사

 

오늘날 네트워크에서 널리 사용되는 오류 검출 기술은 순환 중복검사(CRC) 코드를 사용한다.

CRC 코드는 다항식 코드로도 알려졌는데, 이들을 다항식 연산으로 이해하는 것이 가능하기 때문이다.

 

CRC 코드는 다음과 같이 동작한다.

d 비트로 이루어진 데이터 D를 송신 노드가 수신 노드로 전송한다 가정하자.

먼저 송신자와 수신자는 G로 표기되는 생성자로 알려진 r+1 비트 패턴에 대해서 합의한다.

G의 최상위(가장 왼쪽) 비트는 1이어야 한다.

 

주어진 데이터 D에 대해 송신자는 r개의 추가 비트 R을 선택해서 D 뒤에 덧붙이며, 이 d + r 비트 패턴은 mod 2 연산을 이용하면 G로 정확히 나누어진다. (D * 2^r XOR R = nG, n은 정수)

 

CRC를 이용한 오류 검사 절차는

수신자는 d+r개의 수신 비트를 G로 나눈다. 만약 나머지가 0이 아니면 오류가 발생한 것으로 판정할 수 있다.

 

모든 CRC 검사는 덧셈의 올림이나 뺄셈이 빌림이 없는 mod 2 연산을 사용한다.

이는 덧셈과 뺄셈이 동일함을 뜻하며 이들 모두 피연산자를 비트 별로 XOR 한 것과 같다.

 

예를 들자면

1011 XOR 0101 = 1110 -> 1011 - 0101 = 1110

1001 XOR 1101 = 0100 -> 1001 - 1101 = 0100 

처럼 되는 것이다.

 

또한 일반 이진 연산처럼 2^k를 곱하는 것은 비트 패턴을 k번 왼쪽으로 이동하는 것이 된다.

따라서 주어진 D와 R에 대해 D * 2^r XOR R을 하는 것은 d+r 비트 패턴을 만든다.

 

예시

D = 101110, d = 6, G = 1001, r=3 인 경우

 

즉, R은 D * 2^r을 G로 나눈 나머지가 된다.(D * 2^r XOR R = nG)

 

 

4. 다중 접속 링크와 프로토콜

 

네트워크 링크는 점대점 링크(point to point link), 브로드캐스트 링크(broadcast link)가 존재한다.

점대점은 링크의 끝에 송신자와 수신자가 있는 구조이고

브로드캐스트 링크는 동일한 하나의 공유된 브로드캐스트 채널에 대수의 송. 수신 노드들이 연결되는 구조이다.

ex) 이더넷

 

여기서 브로드캐스트란 임의의 한 노드가 프레임을 전송하면 채널이 그 프레임을 방송해서

다른 모든 노드들이 그 프레임의 복사본을 수신하기 때문에 사용된 것이다.

ex) 와이파이

 

다중 접속 프로토콜(MAC)은 바로 브로드캐스트를 사용한다.

 

다중 접속 프로토콜의 특징

 

• 2개 이상의 노드가 동시에 프레임을 전송할 수 있어 전송된 프레임들이 각 수신자에서 충돌 우려가 있다.
• 이런 충돌을 중재하는 역할의 노드가 없기 때문에 위험하지만, 간단하다.

 

해결책

• 1) 채널 분할 프로토콜 : TDMA, FDMA, CDMA
• 2) 랜덤 접속 프로토콜 : ALOHA
• 3) 순번 프로토콜 : taking-turn protocol

 

1-1) 채널 분할 프로토콜(time) : TDMA

 

TDMA는 시간을 "시간 프레임"으로 나누고, 각 시간 프레임을 n개의 시간 슬롯으로 나눈다.

(여기서 프레임은 PDU의 프레임과 다르다!)

 

이후 시간 슬롯은 n개의 노드에 각각 할당되고, 노드는 전송할 패킷이 있을 때마다 TDM 프레임에서 자신에게 할당된 시간 슬롯 동안 패킷 비트들을 전송한다.

 

이 방식은 아주 공정하고 바람직하지만, 전송할 패킷이 없는 노드들도 시간 슬롯이 할당되기 때문에 자신의 차례를 항상 기다려야 한다는 단점이 있다. 

 

1-2) 채널 분할 프로토콜(frequency) : FDMA

 

FDMA는 Rbps의 채널을 다른 주파수로 나눠 각 주파수를 N개의 노드 중 하나에게 할당한다.

즉 각 노드는 작은 채널을 할당받게 된다.(자기 주파수가 고정되어 있음)

하지만 전송 패킷이 많아도, 적어도 동일한 대역폭을 가진다는 단점이 있다.

 

1-3) 채널 분할 프로토콜(code) : CDMA

 

CDMA는 다른 코드를 각 노드에게 할당하는 방식이다.

노드들은 전송하는 데이터 비트들을 자신의 유일한 코드로 인코딩하고, 적절히 분배한다면

동시에 전송이 가능하다는 장점이 있다.

 

2) 랜덤 접속 프로토콜

 

랜덤 접속 프로토콜에서 각 노드들은 항상 채널의 최대 전송률인 Rbps로 전송한다.

만약 충돌이 생기면 계속해서 재전송하되, 랜덤 지연 시간 동안 기다렸다가 전송한다.

 

slotted ALOHA

랜덤 접속 프로토콜 중 하나인 슬롯 알로하이다.

알로하는 다음과 같이 가정한다.

• 모든 프레임은 같은 크기를 가진다.
• 시간은 L/R초의 슬롯들로 나뉜다.
• 각 노드는 언제 슬롯이 시작하는지 알 수 있게끔 동기화되어 있다.
• 한 슬롯에서 2개 이상의 프레임이 충돌하면, 모든 노드는 충돌 발생을 알게 된다.

 

동작

• 충돌이 발생하지 않을 경우 -> 다음 프레임을 준비한다.
• 충돌이 발생한 경우 -> 슬롯이 끝나기 전에 충돌을 검출하고, 그 프레임이 충돌 없이 전송될 때까지 일정 확률을 가진 slot 뒤에 다시 보낸다.

 

효율성

• 장점 : 각 노드들이 충돌을 감지하고, 언제 전송할지 각자 결정하므로 분산되어 있다.
• 단점 : 활성 노드가 여러 개일 때, 일부 슬롯이 충돌로 인해 낭비될 위험이 있다.

 

pure ALOHA

순수 알로하는 슬롯이 없고 완전히 분산된 프로토콜이라는 것만 알아두자.

 

 

5. CSMA, CSMA/CD 프로토콜

 

앞에서 봤던 알로하에서 노드가 전송 여부를 결정하는 것은 같이 접속되어있던 다른 노드의 활성 여부와 무관하다.

예를 들면, 강의실에서 아무 신경 안 쓰고 왕뚜껑을 먹거나.. 기숙사에서 눈치 보지 않고 남의 첵스초코를 훔쳐먹는 것처럼 말이다.

 

CSMA

이번에 볼 CSMA(carrier sense multiple access) 프로토콜은 예의 바른 송골이들(노드)을 위한 규칙이 있다.

 

• 말하기 전에 듣는다 : 만일 다른 사람이 말하고 있으면 말이 끝날 때까지 기다린다. 네트워크에서는 이것을 캐리어 감지라고 한다.

 

이런 예의 바른 CSMA 프로토콜이라도 충돌이 발생할 경우가 있다.

만약 길을 걷다가 나랑 반대방향으로 오는 사람을 피하려고 왼쪽으로 이동했는데, 그 사람도 똑같은 방향으로 이동하면

서로 두둠칫! 하면서 충돌이 일어나는 것처럼 말이다.

 

전송도 전송 딜레이 때문에 미처 다른 노드의 행동을 파악하지 못할 수 있다.

이런 전송 딜레이를 propagation delay라고 한다.

 

CSMA에서 이러한 충돌이 일어나면, 해당 패킷의 전송 시간은 버려지게 된다.

 

CSMA/CD

앞서 말한 CSMA의 문제점을 개선하기 위한 방법이다.

뒤에 붙은 CD는 collision detection을 의미한다.

 

다른 사람이 동시에 말하기 시작하면 말을 중단한다 : 네트워크에서는 이것을 충돌 검출이라 한다. 만약 다른 노드가 방해 프레임을 전송하고 있음을 검출하면, 자신의 전송을 중단하고 랜덤 시간 동안 기다린 후 재전송한다

 

CSMA/CD는 보내는 중에도 detect 하는 방식으로 이를 가능케하는 것은 media의 전위차이다.

마치 아까 길을 걷다 반대 방향 사람을 비켜주다가 엄청난 동체시력으로 안 비켜주는 것이다. 느려 느려~

 

이 방식은 충돌이 발생하면 충돌이 검출될 때까지 전송하다가 검출 직후 자신의 전송을 중단한다.

 

이때 중단 시간은 랜덤이지만, 충돌한 횟수가 많을수록 중단 시간이 늘어날 수 있다.

 

이런 방식은 앞의 ALOHA 방식보다 좋은 성능을 가지게 된다. (다른 노드 눈치를 보고 전송을 하니)

 

 

4-3) "taking turns" MAC protocols

 

taking turns protocol은 채널 분할 MAC 프로토콜과 랜덤 접근 MAC 프로토콜의 장점을 합쳤다고 보면 된다.

 

여기선 두 가지 프로토콜이 존재한다.

 

1. 폴링 프로토콜

노드 중 하나를 마스터 노드로 지정하고, 나머지는 노예로 본다.

마스터 노드는 중재자 역할로 각 노드들에게 "1급 노예 쓰세요! 2급 노예 쓰세요!"라는 식으로 말해준다.

즉, 중앙 집중형으로 만약 마스터가 죽으면 망한다는 단점이 있다.

 

2. 토큰 전달 프로토콜

이 프로토콜은 마스터 노드가 따로 없고,

토큰이라고 알려진 작은 특수 목적 프레임이 정해진 순서대로 노드 간에 전달된다.

 

토큰을 받은 노드는 data를 보낼 수 있게 된다. 또한 각 노드들은 전송할 프레임이 있을 때만 토큰을 붙잡는다.

따라서 분산 방식이며 효율이 매우 높다.

 

하지만 어떤 욕심쟁이 노드가 data를 계속 보내면 다른 노드들은 손가락 빨면서 기다려야 한다는 문제와

토큰을 가진 노드가 죽으면 망한다는 단점이 있다.