Link Layer
쉽게말해 노드와 노드를 연결한다.
링크계층의 커뮤니케이션 링크는 1. 유선 2. 무선 3. LANs 와 같은 종류가 있다.
링크 계층에서는 패킷을 frame(프레임)이라고 한다.
데이터그램은 서로 종류가 다른 링크로 전송될 수 있다.
(예를 들어 와이파이로 전송이 되다가 이더넷으로 전송될 수 있다.)
이떄 각 링크는 자체적으로 프로토콜을 제공한다.
<예시>
서울에서 부산으로 가는 여정을 예를 들어보자.
가는 교통수단에는 버스, 비행기, 기차가 있다.
- 이때 여행자는 데이터그램이 되고
- 가는 방법은(버스를 타고 비행기타고 간다..) 커뮤니케이션 링크가 된다.
- 버스 비행기 기차 같은 것이 링크레이어 프로토콜이 된다.
- 여행 계획을 짜는 사람은 라우팅 알고리즘이라고 할 수 있다.
링크 계층 서비스
링크 계층이 제공하는 서비스는 여러가지가 존재한다.
1. framing과 링크 접속
링크 레이어 패킷(프레임)을 만드는
프레이밍과,
한 채널에 동시에 전송요청이 있을 때 순서를 정해주는 등의 작업을 하는링크 접속두가지 서비스를 지원한다.
- IP레이어로 부터 받은 패킷을 헤더를 붙이고 캡슐화 한다.
- 헤더에는 송신지와 목적지에 대한 MAC주소를 설정한다.
2. 인접노드 사이의 reliable delivery
신뢰성 있는 전달을 서비스 하여 loss의 발생을 막는다.
유선연결에서는 loss의 발생확률이 적으므로 reliable delivery 서비스를 제공하지 않지만,무선연결에서는 충돌 및 loss가 많이 발생하므로 위 서비스가 중요하다.
3. 에러 검출
전송 중 프레임의 에러를 감지하고 drop 및 재전송을 요청한다.
- 신호의 노이즈나 충돌로 인해 잘못된 프레임을 받을 경우 오류를 검출한다.
- 하드웨어적으로 처리하여 빠르게 오류 검출이 가능. (쳌섬보다 복잡한 방식)
- 오류가 난 부분을 명확히 알 수 있는 방법이 존재한다. (무슨 비트인지)
4. 에러 정정
에러의 발생을 알아내면 에러를 고치는 서비스를 제공한다.
- 에러가 발생한 비트를 수정하여 에러를 고칠 수 있다.
(2진수이기 때문에 어느 부분이 에러인지 알 수 있으면 고칠 수 있다.)
5. half-duplex and full-duplex
half-duplex: 한번에 하나씩 전송하는 서비스
full-duplex: 한 링크에서 동시에 전송가능한 서비스
6. flow 컨트롤
인접 노드 사이의 플로우 컨트롤도 제공한다.
링크 레이어의 구현 위치 및 동작
호스트에서 대부분의 경우 링크 계층은
네트워크 인터페이스 컨트롤러(NIC)로 알려진 네트워크 어댑터에 구현된다.
이더넷은 칩의 형태로 구현되어 있지만,
와이파이같은 다른 대부분의 링크 레이어는 NIC로 구현된다.
또한, 호스트의 시스템 버스에 붙어 있으며
하드웨어와 소프트웨어, firm웨어 모두의 조합으로 구현된다.
컨트롤러(controller)
컨트롤러는 하드웨어 칩으로 구성된다.
-
송신 측 컨트롤러
호스트 메모리에 저장된 데이터그램을 링크 계층 프레임으로 캡슐화한 후 링크 접속 프로토콜에 따라 이 프레임을 통신 링크상으로 전송한다. -
수신 측 컨트롤러
프레임을 수신한 후 네트워크 계층 데이터그램을 추출한다.
CPU
- 링크 계층 주소 정보 조립, 컨트롤러 하드웨어 활성화, 컨트롤러로부터의 인터럽트, 오류 처리, 데이터그램 전달 등을 소프트웨어적으로 처리한다.
프레임을 보내고 받고 할때 추가적으로 error checking bits, reliable data transfer, flow control, 관련된 설정을 할 수 있다.
에러 검출과 정정
링크 레어어 프로토콜은 각 노드에서 패킷 송수신 시 에러를 검출하고, 문제의 비트를 특정하여 정정할 수 있다.
여러 다양한 방법들을 살펴보자.
에러 검출
에러의 detection은
EDC라는 오류 검출 및 정정 비트들을 사용하여 찾아낸다.
EDC : 오류 검출 및 정정을 위한 비트
D : 데이터를 뜻한다.(헤더 포함)
데이터를 보낼 때 원래 데이터 D에서 EDC를 계산하여 같이 보낸 다음.
비트 에러가 발생 가능한 링크를 지나 다음 노드에 도착하면,
받은 데이터 D'과 받은 EDC'를 비교하여 오류를 detection 한다.
이러한 에러 검출은 100% 정확한 것은 아니다. 하지만 높은 정확률을 보이고,
EDC의 길이가 길수록 에러를 정확히 검출할 수 있다.
Parity Checking
패리티 비트를 이용하여, 오류를 감지한다.
1의 개수가 짝수가 되도록 패리티 비트를 EDC에 설정한다.
1. 단일 패리티
패리티 비트를 단 한개만 사용하여 오류를 검출한다.
위와 같이 데이터의 1의 개수가 짝수가 되도록 하는 패리티 비트를 설정한다.
이 방법은 정확도가 높지 않다.
왜냐하면, 홀수개의 비트 오류는 검출할 수 있지만, 짝수개의 비트 오류는 검출할 수 없다.
또한 에러가 발생한 위치를 정확히 집어낼 수 없다.
➡️ 에러 정정 불가
2. 2차원 비트 패리티
데이터 D에 있는 비트들을 i개의 행과 j개의 열로 나누어,
나뉜 각각의 행과 열에 대해 하나의 패리티 값이 계산한다.
한 비트에 오류가 발생하면,
패리티가 오류인 두 부분의 교차점이 에러부분임을 알수 있다.
➡️ 에러 정정 가능!!
또한, 단일 패리티와는 달리 임의의 2개의 오류도 검출할 수 있지만,
2개 발생 시에는 정정할 수 없다.
인터넷 체크섬(Internet checksum)
데이터의 체크섬계산하여
EDC에 설정한다.
TCP/UDP에서 사용한 방법과 동일하다.
Cyclic Redundancy Check (CRC)
가장 강력한 에러 detection 방식이다.
절차
1. 비트 패턴 G : 송수신자가 모두 사전에 합의한(알고있는) r+1 비트 패턴을 설정한다.
(최상위 비트는 1이어야 함)
2. 송신자는 D에 r개의 추가 비트 R을 선택해 데이터 D 뒤에 덧붙인다.
- 연산 공식:
<D,R> = D*2^r XOR R
➡️ D를 왼쪽으로 r만큼 이동시키고 R을 덧붙인다. - 만들어진 d+r 비트 패턴은 모듈로 2 연산을 이용하면 G로 정확히 나누어진다.
3. 수신자는 <D,R> 수신 비트를 G로 나눈다.
- 만일 나머지가 0이 아니면 오류가 발생한 것이다.
모든 CRC 검사는 덧셈의 올림이나 뺄셈의 빌림이 없는 모듈로 2 연산을 사용한다.
즉, 이는 피연산자를 비트별로 XOR한 것과 같다.
위와 같은 방식으로 R을 구해 같이 보내주게 되면, 수신자는 패턴 G로 나누어 오류를 감지할 수 있다.
또한, 각각의 CRC 표준은 r개 이하의 연속적인 비트 오류를 모두 검출할 수 있다.
그리고 이더넷 wifi에서 널리 사용된다.
다중 링크 접속 프로토콜
링크의 접속은 다음의 두가지 방법이 있다.
point-to-point link
- 1-1로 연결되어 통신하는 방식
- 링크의 한쪽 끝에 한 송신자와 링크의 다른 쪽 끝에 한 수신자가 있다.
PPP(point-to-point protocol)과 HDLC(high-level data link control)이 여기에 속한다. - ex) 이더넷 스위치
브로드캐스트 링크(broadcast link)
- 하나의 채널을 여러 호스트가 공유하는 방식
- 동일한 하나의 공유된 브로드캐스트 채널에 다수의 송신 노드 및 수신 노드가 연결된다.
- 임의의 한 노드가 프레임을 전송하면 채널이 그 프레임을 브로드캐스트해서 다른 모든 노드가 그 프레임의 복사본을 수신하기 때문에 브로드캐스트라고 한다.
- ex) 무선 랜, 4G/5G, 위성
브로드캐스트방식은 동시에 신호가 들어올 때 충돌을 피하도록 설계되어야 한다.
즉, 이러한 충돌을 피하기 위한 프로토콜이 바로 Multiple access 프로토콜이다.
이상적인 Multiple access 프로토콜
R bps의 다중접속이 가능한 MAC 채널이 있다면...?
-
한명만 링크를 사용하면 R bps로 전송이 가능하다.
-
M개의 노드가 사용할 때는 각 노드가 공평히 R/M bps의 처리율을 갖는다.
-
fully decentralized
중앙 컨트롤러가 순서를 정해주는 것이 아니라 각 노드(디바이스)가 순서를 정한다.
비동기적으로 수행이 가능하다.
➡️ 분산되어 있어 하나의 고장으로 전체 시스템이 다운되지 않음. -
간단해야 한다.
모두가 이상적이진 않지만 Multiple access 프로토콜을 위한 다음의 세가지의 방식이 있다.
채널 파티셔닝
- 채널을 나누어 전송을 한다.
- idle한 채널이 있어, 낭비가 발생한다.
랜덤 억세스
- 채널을 나누지 않고 패킷을 보낸다. -> 충돌이 발생가능
➡️ 이러한 충돌을 회복하는 것이 목표
순서대로 전송
- 각 노드는 턴이 있고, 보내야할 패킷이 많을수록 더 긴 턴을 갖는다.
채널 파티셔닝 - TDMA
Time Division Multiple Access로, 1장에서 배웠던 시분할 방식이다.
(타임 slot으로 나누어 각 슬롯마다 디바이스가 채널에 순차적으로 접속한다.)
각 채널을 고정된 크기의 슬롯으로 나누어(일정한 패킷 전송시간을 기준) 번갈아 가며 전송한다.
6개의 스테이션으로 나뉜 LAN이 있을 때 1,3,4슬롯만 보낼 패킷이 있다면,
2,5,6은 보내지 않아도 항상 낭비가 된다.
채널 파티셔닝 - FDMA
Frequency Division Multiple Access로, 1장에서 배웠던 주파수분할 방식이다.
(채널의 주파수 대역을 나누어 각 대역마다 패킷을 보낼수 있다.)
이렇게 한번에 여러 패킷을 전송할 수 있지만, 안 쓰는 주파수 대역은 낭비된다.
Random access protocols
채널을 나누어 접속을 하게 되면 사용자가 1명일때 많은 낭비가 발생한다.
➡️ 채널을 나누지 않고 전송하며, 충돌을 빨리 감지하고, 회복하는 방법을 사용한다.
특징
- full 용량 사용 가능
- decentalized 방식(각자 노드에서 알아서 충돌을 감지하고 회복)
- but, 충돌가능성 존재
Random access MAC protocols의 종류
- ALOHA, slotted ALOHA
- CSMA, CSMA/CD(유선), CSMA/CA(무선)
Random access MAC protocols은 충돌이 발생가능하기 때문에
충돌을 감지하고 회복하며 충돌에 대한 피해를 최소화 하는 것이 목표이다.
Slotted ALOHA
타임슬롯을 나눈 다음 해당 타임 슬롯 전체를 사용해서 패킷을 보낸다.
충돌이 발생하면, 충돌이 발생한 프레임을 p의 확률로 다시 보낸다
가정
- 모든 프레임은 같은 사이즈
- 타임슬롯 또한 같은 사이즈(한 타임슬롯에 한 프레임만 보냄)
- 각 노드가 나뉜 slot 시간에 맞추어 패킷 전송
➡️ 때문에 시간에 대한 동기화가 필요하다 - 충돌 발생시 다른 노드들이 충돌에 대해 알 수 있다.
동작
-
충돌발생 x
➡️ 해당 노드는 성공적으로 해당 프레임을 보냈기 때문에, 다음 프레임을 보낼 수 있다. -
충돌발생
➡️ p의 확률로 보낼 수 있을 때 까지 재전송을 한다.
장점
- 한 액티브한 노드는 프레임을 보낼 때 혼자
full 채널을 사용할 수 있다. highly decentralized: 자체적으로 확률을 계산하여 보낸다.
(하지만 fully decentralized는 아님, 시간에 따라 동기화가 필요하므로)- 간단하다.
단점
- 충돌이 발생가능하고, 슬롯의 낭비가 발생한다(idle한 슬롯 가능).
- 확률적으로 동작하기 떄문에 계속해서 충돌이 발생하면
충돌시간이 매우 길어질 수 있다. - 노드들이 많아지면 그만큼 더 충돌발생가능성이 높아진다.
- clock 동기화가 필요하다.
Slotted ALOHA의 Efficiency
Efficiency : 여러개의 슬롯 중 슬롯이 패킷을 성공적으로 보내는 확률
(노드가 N개가 있을 때 하나의 슬롯이 성공적인 슬롯일 확률)
즉, 노드들 중 한 노드만 전송하고 나머지 N-1 개의 노드는 전송하지 않는 확률이다.
1. 노드가 전송할 확률이 p라하면
해당 노드가 성공할 확률 = p x (1-p)^(N-1)
2. 노드가 N개 있으므로
임의의 한 노드가 성공할 확률 = N x p x (1-p)^(N-1)
3. 최대의 효율을 구하기 위해서는 이 식을 최대화 하는 p를 구해야 한다.
4. 활성 노드가 많은 경우의 최대 효율을 구하기 위해 N이 무한대가 될 때의 극한값을 취한다.
5. 이렇게 계산하면 최대 효율은 p = 1/e = 0.37 임을 알 수있다.즉, 많은 노드가 전송할 프레임이 많을 때 기껏해야 37%의 슬롯만 낭비되지 않는다.
Pure ALOHA
노드는 프레임을 브로드캐스트 채널로 전송하고,
만약 충돌하면, 노드는 확률 p로 즉시 재전송 한다.
슬롯 알로하의 슬롯의 개념을 뺀 것이라고 보면 된다.
➡️ 시간에 따른 동기화가 필요 없다
동작
- 노드는 프레임이 도착하면 프레임의 전체를 채널로 전송한다.
- 만약 충돌이 발생하면 확률 p로 즉시 재전송
➡️ 시간에 따른 동기화가 없기 떄문에 충돌확률이 2배 증가한다.
Pure ALOHA의 Efficiency
슬롯 알로하에 비해 충돌확률이 2배 증가한다 18%
위 두 프로토콜에서는 다른 노드가 전송하고 있건 말건 일단 보낸다.
즉, 충돌이 생기고 결과적으로 효율이 떨어지게 되는데,
CSMA방식에서는 말할 사람이 손을 들고 말을 하는 것 처럼
누가 프레임을 보내고 있으면 프래임을 전송하지 않는다.
CSMA (Carrier Sense Multiple Access)
채널을 listen하고 어떤 노드가 프레임을 보내고 있으면, 패킷을 보내지 않는다.
앞의 Carrier Sense라는 것은 채널을 Sensing하여(채널 상태를 보며)
idle한 상태면 프레임을 보내고busy한 상태면 프레임을 보내지 않는다.
➡️ 이러한 방식으로 충돌발생을 막는다.
CSMA/CD 방식
위의 CSMA방식에 충돌을 감지하는 기능을 추가한다.
또한, 충돌을 감지했으면, 프레임의 전송을 취소한다.
(이더넷에서 사용하는 방식)
Q. CSMA에서는 채널이 idle한 상태일때 프레임을 보내게 되는데 왜 충돌감지가 필요할까?
➡️ 프로파게이션 타임 때문에 충돌이 발생하기 때문이다.
예를 들어 노드 1이 시간 t0에 패킷이 전송되면,
또한 t1쯤에 다른 인접 노드들이 보냈다는 사실을 알게될때,
인접노드가 아닌 다른 노드들은 1번 노드가 아직 전송했다는 신호를 못받은 상태일수 있다.
떄문에 t1시간에 패킷을 전송하게 되어 1번 노드가 보낸 패킷과 충돌이 발생 할 수 있다.
위의 상황은 충돌이 발생했음에도, 자신의 패킷을 꿋꿋히 다 보낸 상황이다.
겹치는 격자무늬의 시간 동안 충돌이 발생하고 낭비가 발생한다.
충돌 감지를 사용한 경우
충돌을 감지 할 경우 패킷의 전송을 멈춘다.
이더넷 CSMA/CD 알고리즘의 동작
-
이 NIC가 네트워크 레이어로부터 패킷을 받으면 프레임으로 캡슐화 한다.
-
NIC가 채널을 센싱하여
- IDLE : 프레임 전송
- BUSY : 프레임 전송 x
-
프레임이 충돌없이 성공적으로 보내지면 다음 프레임을 보낼수 있다.
-
충돌이 발생하면, 패킷을 취소하고,
조금 기다렸다가 다시 채널을 센싱하여 패킷을 재전송한다. (=Backoff 방식)
cf>
`NIC(네트워크 인터페이스 카드)` : 이더넷 프로토콜이 구현되어있는 인터페이스 카드바이너리 Backoff
충돌 발생시 잠깐 기다리는 시간을 정한다.
충돌을 n번 경험한 프레임을 전송할 때 노드는
{0,1,2,…,2^n - 1} 중에서 랜덤하게 K 값을 선택한 후 K x 비트 시간 만큼 기다린다.
이더넷의 경우 K x 512 비트 시간(이더넷으로 512 비트를 전송하는데 걸리는 시간 x K)가 되며 n의 최댓값을 10으로 제한한다.
만약 충돌한 두 패킷이 같은 시간을 뽑아 전송하게 되면 다시 충돌이 일어날 테지만,
충돌을 많이 경험할 수록 n값이 늘어나 랜덤한 숫자를 뽑는 범위가 늘어나게 되어
충돌발생 확률이 낮아진다.이렇게 랜덤하게 기다리는 시간을 측정하는 이유는 충돌한 두 패킷이 다시 충돌하는 것을 막기 위함이다.
CSMA/CD 효율성
-
만약 Tprop가 0이 되면, 효율성이 1이 된다
➡️ 전파지연이 없어지면 충돌이 일어나지 않기 때문 -
만약 Ttrans가 무한대가 되면, 효율성이 1이 된다
➡️ 하나의 디바이스만 채널을 사용하는 상태이므로, 충돌 발생이 없다.
알로하 방식보다 CSMA는 간단하고 싸고 decentralized된 방식이다.
하지만
1. 채널 파티셔닝 프로토콜의 경우
- 채널 효율이 좋을 떄 : 많은 액티브 노드가 존재할 때
- 채널 효율이 안 좋을 떄 : 액티브 노드가 1개일때
채널의 낭비가 주 문제이다.
2. 랜덤 억세스 프로토콜의 경우
- 채널 효율이 좋을 떄 : 액티브 노드가 적을 때 충돌발생이 적어 효율이 좋다.
- 채널 효율이 안 좋을 떄 : high load일때
채널의 충돌이 주 문제이다.
채널 낭비와 충돌문제를 보안을 하여 taking turns 라는 프로토콜이 개발되었다.
Taking Turns
채널의 낭비와 충돌의 문제를 해결하기 위해 순서대로 패킷을 전달할 수 있도록 하는 방법이다
블루투스, FDDI 에 사용되며
총 Polling 프로토콜 토큰 전달 프로토콜 두 가지 가 있다.
Polling 프로토콜
하나의 마스터 디바이스가 슬레이브 디바이스에 polling을 통해 전송 의사를 묻고, 순서대로 전송할 수 있도록 한다.
때문에 idle 한 채널이 발생하지 않고 충돌이 발생하지 않는다.
단점
- 풀링 오버헤드가 존재 (각 슬레이브에 의사를 물어야 하니 오버헤드가 발생)
만약 한 노드만 액티브해도 순서대로 inactive한 슬레이브에 polling해야한다. - 레이턴시 (지연이 발생할 수 있다.)
- 마스터 노드가 고장나면 전체가 동작 X
토큰 전달 프로토콜(token-passing protocol)
따로 마스터 디바이스를 두지 않고 토큰을 서로 전달하며, 토큰이 있는 디바이스만 패킷을 전송할 수 있다.
덕분에 polling 에서 있던 마스터 디바이스문제를 해결할 수 있다.
단점
- 토큰 오버헤드가 존재 (토큰 관리)
- 레이턴시 (토큰 전달시 지연)
- 노드 하나가 실패하면 채널이 동작하지 않는다.
- 디바이스의 고장으로 토큰을 놓아주지 않으면,
토큰이 다시 돌 수 있도록 하는 회복 절차가 수행되어야 한다.
케이블 억세스 네트워크 - DOCSIS
다운스트림과 업스트림데이터는 FDM방식으로 구분하고,
업스트림 시는 TDM 방식으로 구분하여 충돌을 막는다.
-
케이블 헤드엔드의
CMTS는
업스트림 다운스트림 데이터를FDM 주파수 분할로 나누어 처리를 한다. -
다운 스트림은
CMTS하나가각 가정에 데이터를 전송하기 때문에 충돌이 발생하지 않는다. -
업스트림은
각 가정이CMTS에 데이터를 전송하기에 충돌이 발생한다.
➡️ TDM 시분할로 타임 슬롯을 나누어 각 가정에 슬롯을 할당해 데이터를 받는다.
Q1. 그럼 각 가정이 어떤 타임슬롯에 할당되었는지는 어떻게 알려줄 수 있을까?
CMTS가 다운스트림 시
맵 프레임을 보내 각 가정의 타임 슬롯을 알려준다.
Q2. 그럼 CMTS는 어느 가정이 보낼 패킷이 있는 지 어떻게 알고 시간을 할당해서 보내주는 걸까?
맵 프레임을 보내려면 각 가정이 보낼 패킷이 있는지 부터 알아야 한다.
랜덤 억세스 프로토콜을 통해,
각 가정은 보낼 패킷이 있으면 CMTS에 알려주게 된다.
이렇게 하여 CTMS는 보낼 패킷이 있는 가정들의 정보를 알게 되고,
각 가정에 타임슬롯을 할당하여 맵 프레임을 다운스트림시 보내준다.
➡️ 즉, 케이블 억세스 네트워크는 채널 파티셔닝, 랜덤 억세스 프로토콜을 종합적으로 사용하여 서비스를 한다.
