10. 링크 계층

---

이 글은 Computer Networking: A Top-Down Approach 7th를 읽고 정리한 글입니다.

---

 

 

 

1. 링크 계층 소개

---

이전에 쓰였던 노드와 링크 개념이 여기서도 계속 쓰인다.

- 노드: 호스트, 라우터, 스위치, ...

- 링크: 인접한 노드들을 연결하는 통신 채널

 

링크 계층에서는 데이터그램을 프레임으로 캡슐화하여 링크로 전송한다.

(트랜스포트 계층 - 세그먼트, 네트워크 계층 - 데이터 그램)

---

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

- 기본 기능: 링크에서 데이터그램을 한 노드에서 인접 노드로 이동하는 것

- 프레임화: 데이터그램을 프레임으로 캡슐화

- 신뢰적 전달: 트랜스포트 계층의 신뢰적 전달처럼 ack와 retransmission을 한다.

- 흐름 제어: 수신자의 속도가 느리면 송신자의 속도를 수신자의 속도로 맞춘다.

- 링크 접속: MAC 프로토콜을 사용하여 프레임 전송을 조정한다.

- 오류 검출과 정정: checksum을 송신자가 보내서 수신자가 오류 확인을 할 수 있고 정정도 할 수 있다.

---

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

링크 계층은 네트워크 어댑터라는 부분에 있고, 링크 계층 서비스들은 대부분 하드웨어로 구현된다.

 

컨트롤러는 데이터그램을 프레임에 캡슐화하고, error checking bits, rdt, flow control과 같은 정보를 추가하여 전달한다.

수신자는 error, rdt, flow control을 확인해보고 이상이 없으면 데이터그램으로 역캡슐화를 한다.

---

 

 

 

2. 오류 검출 및 정정 기술

---

비트 오류를 방지하기 위해  송신자는 데이터 D에 오류 검출 및 정정 비트들인 EDC를 추가한다.

이후 수신자는 D'과 EDC'를 받는다.(D', EDC'인 이유는 전송 과정에서 비트가 바뀌었을 수도 있으므로)

수신자는 데이터의 오류를 검출하기 위해 패리티 검사, 체크섬, 순환중복검사를 사용하게 된다.

---

2.1 패리티 검사

패리티 검사는 패리티 비트를 추가하여 확인하는 가장 단순한 형태의 오류 검출로 짝수 패리티 비트, 홀수 패리티 비트로 나뉜다.

짝수 패리티 비트는 데이터 D가 d 비트를 가지고 있다고 하면 사용자가 비트 한 개를 추가하여 d+1개의 비트에서 1의 개수가 짝수가 되도록 만드는 것이다.

위 그림은 데이터 D에서 1의 개수가 10개이므로 패리티 비트를 0으로 하면 된다. 이 데이터는 일차원이므로 단일 패리티 검사라고 한다.

 

2차원 패리티 검사는 행과 열의 끝에 패리티 비트를 추가하는 것이다.

단일 패리티 검사와는 다르게 2차원 패리티 검사는 비트 오류의 발생을 검출뿐만 아니라 정정도 가능하다.

위 그림은 (2,2)의 값이 원래 1이지만, 0으로 바뀌어서 에러가 나타나있는데, 여기서 패리티 에러가 나오므로 행과 열의 위치로 비트를 특정할 수 있으므로 해당 비트의 값을 0에서 1로 정정할 수 있다.

---

2.2 체크섬 방법

체크섬 방법은 트랜스포트 계층에서 이미 배운 방법이다.

데이터 값 + 체크섬 + 윤회식 자리 올림을 하면 모든 비트의 값이 1로 나와야 오류가 없다는 것이다.

체크섬의 장점은 오버헤드가 적지만, 오류 검출에서는 순환중복검사보다 취약하다.

---

2.3 순환중복검사(Cyclic Redundancy Check, CRC)

트랜스포트 계층에서는 체크섬을 사용하지만, 링크 계층에서는 CRC를 사용한다.

CRC 코드는 다항식 코드라고 부르는 것처럼 비트열을 다항식으로 생각할 수 있다.

 

위 사진처럼 데이터 D는 d비트, CRC인 R은 r비트를 수신자에게 보낸다고 가정하자

1) 생성자(G)인 r+1 비트 패턴에 대해서 합의한다. 이때 G의 가장 왼쪽 비트는 1이어야 한다.

2) D 뒤에 R을 덧붙이고, d+r 비트 패턴은 mod 2 연산을 사용하면 G로 나누어져야 한다.

3) D+R을 G로 나누었을 때 나머지가 0이어야 오류가 없는 것이고, 0이면 오류이다.

 

CRC에서 수신자는 아래 식을 통해 R을 구해야 한다.

= D * 2^r XOR R = nG

이 수식은 D + R에서 D의 왼쪽 R비트는 0으로 가득차있으니 D * 2r로 하고, 000...인 부분은 XOR를 하면 XOR한 값으로 되므로 D * 2^r XOR R = nG가 될 수 있다.

 

a^b^a = b인 xor의 특성을 이용하여 양변에 XOR R을 추가한다.

D * 2^r XOR R XOR R = nG XOR R

= D * 2^r = nG XOR R 

 

마지막으로 D * 2^r XOR R = nG 은 D * 2^r XOR R이 G로 나누어 떨어진다느 것이므로 D * 2^r을 G로 나눈다면 나머지가 R이 나올 것이다.

그러면 R = (D * 2^r) / G로 R을 구할 수 있게 된다.

= R = (D * 2^r) / G

 

D = 110011, G=1001, d=6, r=3인 경우 위와 같은 과정을 통해 R = 011임을 구할 수 있다.

---

 

 

 

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

---

네트워크 링크는 브로드캐스트 링크(broadcast)와 점대점 링크(point-to-point)가 있다.

 

브로드캐스트 링크는 한 개의 브로드캐스트 채널에 다수의 송수신 노드를 연결한다. 이때 한 노드가 프레임을 전송하면 채널이 해당 프레임을 브로드캐스트하여 다른 모든 노드들이 그 프레임의 복사본을 수신한다.

(ex 이더넷, 무선랜)

 

- 다중 접속 문제: 다수의 송수신 노드가 브로드캐스트 채널로의 접속을 조정하는 문제이다.

- 다중 접속 프로토콜: 브로드캐스트 채널로 보내는 노드들의 전송을 조정하는 것

 

수천개의 노드가 한 개의 브로드캐스트 채널에서 통신할 수 있게 되면 문제가 생긴다.

모든 노드들이 프레임을 전송할 수 있어서 2개 이상의 노드가 프레임을 전송한다면, 모든 노드가 동시에 여러 개의 프레임을 받게 되는데, 이것을 충돌(collide)라고 부른다.

충돌이 일어나면 어떤 수신 노드도 여러 개의 전송받은 프레임의 의미를 알 수 없게 된다.

그래서 이런 프레임을 보내려는 활성화 노드들을 조정하는 것이 다중 접속 프로토콜의 역할이다.

 

다중 접속 프로토콜의 종류는 세 가지로 분류할 수 있다.

1) 채널 분할 프로토콜

2) 랜덤 접속 프로토콜

3) 순번 프로토콜

---

3.1 채널 분할 프로토콜

우리는 처음 공부할 때 브로드캐스트 채널의 대역폭을 분할해주는 기술인 TDM과 FDM에 대해 배운적이 있다.

https://hello70825.tistory.com/455

1. 컴퓨터 네트워크와 인터넷

1) TDMA (Time Division Multiple Access)

TDM은 일정 주기마다 한 사용자가 모든 대역폭을 얻을 수 있는 기술인데, 여기서는 순서를 정해서 각자 할당된 시간동안 패킷 비트를 전송할 수 있도록 한다.

이 방법은 아주 공정하지만 항상 자신의 차례를 기다려야하며, 보낼 데이터가 작아도 최대 전송률을 보장하면서 고정된 시간을 제공한다.

---

2) FDMA (Frequency Division Multiple Access)

 

FDM은 하나의 채널을 여러개의 작은 채널로 나누어서 노드에게 할당한다.

이것의 단점도 TDM과 비슷하게 데이터가 크든 작든 전송률이 고정되어 있다. 여기서는 데이터가 클 경우 문제가 된다.

---

3.2 랜덤 접속 프로토콜

랜덤 접속 프로토콜은 TDM과 같이 채널의 최대 전송률로 전송을 해준다.

만약 충돌이 생긴다면 재전송을 해야하는데, 이때 랜덤한 시간을 기다리고 재전송을 한다.

이때 사용하는 랜덤 접속 프로토콜은 아래 3가지로 분류된다.

1) slotted ALOHA

2) ALOHA

3) CSMA

---

1) 슬롯 알로하

1) 슬롯 알로하는 전송할 프레임이 있으면 다음 슬롯이 시작할 때 전체 프레임을 전송한다.

2) 만약 충돌하면 충돌한 노드는 충돌 없이 전송될 때까지 확률 p로 해당 프레임을 다음 슬롯들에 재전송한다.

 

위 그림에서 C가 충돌이 일어난 것인데, p의 확률로 모든 프레임이 다음 슬롯에 재전송을 하지 않는다.

p의 확률로 1과 2가 다음 슬롯에서 재전송을 하는데 충돌이 일어나고, p의 확률로 2가 바로 재전송을 하게 되어 성공한다.

이런 과정을 통해 프레임을 모두 전송할 수 있게 된다.

 

슬롯 알로하는 재전송하는 위치가 잘 분산되어 있지만, 충돌이 일어나는 슬롯은 그대로 낭비가 된다는 단점이 있다.

---

2) 알로하

순수 알로하는 슬롯 없이 프레임이 도착하면 즉시 브로드캐스트 채널로 전송한다.

이때 충돌이 일어난다면 p의 확률로 충돌된 프레임이 다 전송 될 때까지 기다리다가 전송이 됐으면 즉시 재전송한다.

순수 알로하는 슬롯 알로하보다 최대 효율이 2배 정도 좋지 않다.

---

3) CSMA (Carrier Sense Multiple Access)

알로하의 경우에는 다른 노드가 전송하고 있는지 말든지에 대해 전혀 고려하지 않고 일단 전송하게 된다.

그래서 CSMA는 눈치 좀 보고 행동하자는 것으로 두 개의 규칙을 가지고 있다.

 

1. 캐리어 감지: 다른 노드가 브로드캐스트 채널에 보내고 있으면 데이터를 보내지 않고 기다리다가 나중에 보낸다.

2. 충돌 감지: 다른 노드가 프레임을 보내려고 하면 자신은 데이터 전송을 중단하고 랜덤한 시간 이후 다시 보낸다.

 

여기서 드는 의문점은 이런 감지를 하면 어떻게 다른 노드가 개입을 할 수 있냐는 것인데, 바로 브로드캐스트하는 시간동안 다른 노드가 모든 노드가 패킷을 보내지 않는 줄 알고 자신도 전송을 하게 될 때 생긴다.

위 그림에서 두번째 컴퓨터가 데이터를 전송하면서 다른 채널들에게 브로드캐스트를 하는데, 아직 모든 노드에게 도달하기 전에 네번째 노드가 자신도 데이터를 전송하면서 다른 채널들에게 브로드캐스트를 한다.

이런 상황이 펼쳐지면 채널 전파 지연(channel propagation delay)라고 부른다.

이 상황은 프레임이 손상되므로 다시 전송해야 한다.

---

4) CSMA/CD (Carrier Sense Multiple Access with Collision Detection)

그래서 나온 것이 충돌 검출을 추가하여 충돌이 되기 전까지 전송하다가 충돌이 감지되면 잠시 전송을 중단하고 나중에 전송을 하는 방법이다.

CSMA/CD의 효율성은 ALOHA보다 성능이 좋고, 단순하고, 싸고, 분산화가 되어 있다.

---

3.3 순번 프로토콜

순번 프로토콜은 채널 분할 프로토콜의 장점과 랜덤 접근 프로토콜의 장점을 합친 프로토콜이다.

 

1) 폴링 프로토콜

노드중 하나를 마스터 노드로 지정하고, 마스터 노드는 각 노드를 라운드 로빈 방식으로 폴링한다.

예를 들어서 마스터 노드가 1번 노드에게 1번 노드가 보낼 수 있는 최대 프레임 수를 알려주고, 1번 노드가 다 보냈다면 2번 노드에게 보낼 수 있는 최대 프레임 수를 알려주는 식이다.

폴링 프로토콜은 충돌도 해결할 수 있고, 슬롯 알로하의 단점인 빈슬롯을 제거하였지만, 마스터 노드가 고장나면 끝난다.

---

2) 토큰 전달 프로토콜

이 프로토콜은 마스터 노드가 없는 대신 토큰이 정해진 순서대로 노드들에게 전달 된다.

위 그림은 반시계 방향으로 토큰을 전송하는 것으로 토큰을 받았으면 프레임을 최대 개수까지 전송하고, 다음 노드에게 토큰을 넘기는 것이다.

이 방법은 분산 방식이고 효율이 매우 높지만, 토큰을 주지 않으면 회복 작업을 해야하고, 토큰을 받은 노드가 전송을 실패하면 끝난다.

---