12. 링크 계층

2021-11-17

2022-01-23

a. 링크

a-1. 링크 계층 소개

링크 계층(2계층) 프로토콜을 실행하는 장치를 노드라 함.

통신 경로상의 인접한 노드들을 연결하는 통신 채널은 링크

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

a-2. 링크 계층의 서비스

프레임화 : 네트워크 계층 데이터그램을 링크상으로 전송하기 전에 링크 계층 프래임에 캡슐화.
header payload trailer 형식으로 캡슐화
링크 접속 : 매체 접속 제어(MAC) 프로토콜은 링크상으로 프레임을 전송하는 규칙에 대해서 명시함
신뢰적 전달(RDT) : 링크 계층의 신뢰적 전달 서비스도 확인 응답과 재전송 방식으로 가능
*트랜스포트 계층이나 애플리케이션 계층과 달리 데이터를 재전송하는 방식과 달리
*링크 계층 프로토콜은 오류가 발생한 링크에서 오류를 정정.
왜 수송 계층과 링크 계층 모두 RDT가 필요하지? 링크 계층에서 잘 되도, IP에서 best-effort로 인한 손실이 발생가능. 그래서 수송 계층에서 RDT를 하는 것.
오류 검출과 정정 : 오류 검출은 송신 노드에서 프레임의 오류 검출 비트를 설정하고 수신 노드에서 오류 검사를 수행하게 하는 방식. 오류 정정은 프레임 안의 오류 검출, 프레임의 어느 곳에서 오류가 발생했는지를 찾아내는 것.(오류 검출과 비슷하게 구현)

a-3. 링크 계층이 구현되는 위치

링크 계층은 네트워크 인터페이스 카드로 알려진 네트워크 어댑터로 구현된다.

링크 계층 제어기로 링크 계층 서비스들의 대다수가 구현한다. 일부 링크 계층 기능은 호스트 cpu에 실행되는 소프트웨어에 구현되어 있다.

링크 계층은 하드웨어와 소프트웨어의 조합.

프로토콜 스택상에서 소프트웨어와 하드웨어가 만나는 부분에 위치.

송신 측의 제어기는 상위 계층에 의해 생성되어 호스트 메모리에 저장된 데이터그램을 링크 계층 프레임을 캡슐화한 후, 링크 접속 프로토콜에 따라 이 프레임을 통신 링크로 전송한다.

수신 측의 제어기는 프레임을 수신한 후 네트워크 계층 데이터그램을 추출한다.

b. 오류 검출 및 정정 기술

비트 오류를 방지하기 위해 송신 노드에서 데이터 D에 오류 검출 및 정정 비트들(EDC)을 첨가한다.

수신자는 자신이 수신한 D’와 EDC’만으로 원래의 D가 D’와 동일한지 결정한다.

오류 검출 비트를 사용하더라도 여진히 미검출된 비트 오류가 있을 수 있다.

b-1. 패리티 검사

b-1-1. 단일 패리티 비트

데이터 D가 d개의 비트를 가지고 있다고 할 때, 패리티 비트를 하나 추가.

이 비트들에서 1의 개수가 짝수(혹은 홀수)가 되도록 설정한다.

수신자는 받은 데이터의 1 갯수가 홀수(혹은 짝수)이면 오류가 있음을 알게 된다.

그러나 짝수 개의 비트 오류가 발생하면 오류를 검출하지 못할 수도 있다.

b-1-2. 2차원 단일 비트 패리티

데이터 D를 i개의 행과 j개의 열로 나눠서

각 가로줄과 세로줄의 1 갯수가 짝수(혹은 홀수)가 되도록 패리티를 설정한다.

이 방식은 수신자가 단일 비트 오류의 발생을 검출할 수 있을 뿐 아니라,

열과 행의 인덱스 값을 사용해 잘못된 비트를 실제로 식별해 오류를 정정할 수 있다.

b-2. 체크섬

데이터 바이트를 16비트 정수 단위로 취해서, 더한 값의 1의 보수가 인터넷 체크섭이 되며,

이를 세그먼트 헤더에 넣어준다.

오버헤드가 적지만 오류 면에서 상대적으로 취약하다.

b-3. 순환중복검사(CRC)

데이터 D가 비트 d로 이뤄져 있을 때,

G로 표현하는 생성자로 알려진 r+1 비트 패턴에 대해서 합의한다.

송신자는 r개의 추가비트 R을 선택해서 D 뒤에 덧붙이며,

d+r 비트 패턴은 모듈 -2연산(XOR 연산)을 이용하면 G로 정확히 나누어진다.

수신자는 d+r개의 수신 비트를 G로 나눈다. 나머지가 0이 아니면 오류가 존재하는 것.

예시로 해보자

일단 생성자 G를 1001로 약속하고,
101110인 데이터 D에 2^r을 곱한 것을

G로 나눈 나머지를 R로 정한다.

그 이후 D*2^R XOR R을 수신자에게 보낸다

XOR 연산은 같은 자리 같은 숫자이면 0인 연산이다.

간단히 생각하면 D뒤에 R을 그냥 덧붙인 결과라 생각하자.

예시에 따르면 101110011이 된다.

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

다수의 송수신 노드들의 공유되는 브로드캐스트 채널로의 접속을 조정하는 문제.

즉 다중 접속 문제에 의한 충돌을 해결해야 한다.

이런 전송을 조정하기 위한 것이 다중 접속 프로토콜.

#out of band channel & in band channel

out of band = control과 data가 다른 채널로 전달

in band = control 과 data가 같은 채널로 전달

무선랜은 in-band channel

c-1. 이상적인 다중 접속 프로토콜의 조건

단 하나의 노드가 전송하려 할 때, 그 노드가 R bps의 처리율을 갖는다.
M개의 노드가 전송하려 할 때, 각 노드가 R/M bps의 처리율(평균적 의미)을 갖는다.
프로토콜이 분산되어 있어, 고장으로 시스템이 정지될 수 없다.
비용이 적게 든다.

c-2. 채널 분할 프로토콜

c-2-1. 시분할 다중화(TDM)

TDM은 시간을 시간 프레임으로 나누고 또한 각 시간 프레임을 N개의 시간 슬롯으로 나눈다.

각 시간 슬롯은 N개의 노드에게 할당된다.

노드는 전송할 패킷이 있을 때마다 TDM 프레임에서 자신에게 할당된 시간 슬롯 동안 패킷 비트를 전송.

참가자들에게 고정된 시간을 주고, 말할 게 없어도 시간을 준다.

전송하고픈 노드가 하나라도 노드 전송률은 평균 R/N으로 제한.

노드가 전송 순서상 자신의 차례를 기다려야함.

c-2-2. 주파수분할 다중화(FDM)

FDM은 R bps의 채널을 다른 주파수로 나눠서 각 주파수를 N개 노드 중 하나에게 할당한다.

TDM과 비슷한 장단점을 가짐.

c-3. 랜덤 접속 프로토콜

항상 채널의 최대 전송률인 R bps로 전송한다.

충돌이 생기면 충돌과 관련된 각 노드는 프레임이 충돌없이 전송될 때까지 자신의 프레임을 계속해서 재전송.

대신 그 프레임을 재전송하기 전에 랜덤 지연 시간 동안 기다린다.

c-3-1. 슬롯 알로하

가정

모든 프레임은 정확히 L비트로 구성
시간은 L/R초의 슬롯들로 구성(즉 한 슬롯은 한 프레임 전송에 걸리는 시간과 같음)
노드는 슬롯의 시작점에서만 프레임을 전송하기 시작
각 노드는 언제 슬롯이 시작하는지 알 수 있게끔 동기화되어 있음
한 슬롯에서 2개 이상의 프레임이 충돌 시, 모든 노드는 그 슬롯이 끝나기 전에 충돌 발생을 알게 됨

작동 방식

노드는 전송할 새 프레임이 있으면 다음 슬롯까지 기다렸다가 전체 프레임을 전송
충돌이 없으면, 노드는 성공적으로 자신의 프레임을 전송한 것
따라서 보낸 프레임을 다시 보낼 필요 없음
충돌하면, 노드는 그 슬롯이 끝나기 전 충돌을 검출, 노드는 그 프레임이 충돌 없이 전송 될 때까지 확률 p로 해당 프레임을 다음 스롯들에서 재전송한다.
각 노드들은 자신의 동전을 던지며, 재전송할지 다음 슬롯에서 동전을 다시 던질지를 결정한다.

장점

활성노드가 채녈의 전속력 R로 계속해서 프레임을 전송할 수 있돌록 허용
상당히 분산(노드는 슬롯을 동기화시켜야)
매우 단순
활성 노드가 하나일 때 잘 동작

단점

여러 노드가 참여하면 충돌이 생겨 낭비가 생긴다.
모두가 전송을 자제해 슬롯이 비는 상황이 생길 수 있다.

효율성(여러개의 활성 노드가 있을 때 충돌없이 전송되는 시간 비율)

N개의 노드가 확률 p로 슬롯 알로하로 패킷을 보낼 때 임의의 노드가 성공 확률은? Np(1-p)^(N-1)

최대 효율은 효율성의 극대화인데, 이 프로토콜의 최대 효율은 0.37.(겨우 37%의 슬롯만 낭비되지 않는다…)

c-3-2. 알로하

슬롯 알로하는 모든 노드가 슬롯의 시작점에서 전송을 시작할 수 있도록 동기화되어 있기를 요구

하지만 알로하 프로토콜은 슬롯이 없고 완전히 분산된 프로토콜

전송된 프레임이 하나 이상의 다른 전송과 충돌하면, 노드는 확률 p로 즉시 프레임을 전송한다.

주어진 노드가 성공적인 전송을 할 확률은 p(1-p)^2(N-1)

순수 알로하 프로토콜의 최대 효율은 1/2e 즉 슬롯 알로하의 절반…

c-3-3. CSMA

말하기 전에 들어라 : 다른 사람이 말하고 있으면 말이 끝날 때까지 기다려라.
네트워크에서는 이를 캐리어 감지 라고 한다.
다름 사람이 동시에 말하기 시작하면 말을 중단하라 : 네트워크에서 이것을 충돌 검출이라 함
(송신 노드는 전송하면서 동시에 채널을 듣는다.)
멈춘 후 랜덤 시간 동안 기다린 후 유휴 시 감지 및 전송 과정을 반복

하지만 브로드캐스트 채널의 종단간의 채널 전파 지연이 CSMA의 성능을 결정하는 데 중요함.

전파 지연이 길 수록 네트워크의 다른 노드에서 이미 시작된 전송을 캐리어 감지 노드가 감지 할 수 없는 경우 증가.

c-3-4. CSMA/CD

다중접속 프로토콜에 충돌 검출을 추가한 것.

쓸모 없는 프레임(충돌이 발생한 프레임)을 모두 전송하지 않게 됨.

링크 계층 프레임을 만든 후에 그 프레임을 어댑터의 버퍼에 저장
채널이 유휴한 것을 감지하면(채널로부터 어댑터로 들어오는 신호 에너지가 없으면) 프레임 전송을 시작한다.
채널이 바쁜 것을 감지하면, 신호 에너지가 감지되지 않을 때까지 기다렸다가 프레임을 전송한다.
전송하는 동안 어댑터는 다른 어댑터로부터 신호가 있는지 감시한다.
전송 도중 다른 어댑터로부터 신호 에너지를 감지하면, 자신의 프레임 전송을 취소한다.
임의의 랜덤 시간(이진지수적 백오프)만큼 기다린 후 2단계로 돌아간다

#이진지수적 백오프

충돌을 n번 경험한 프레임을 전송할 때, {0,1,2…,2^n-1} 중 랜덤하게 선택한다.

새 프레임을 준비할 때 최근 발생했던 충돌을 고려하지 않는다.

효율성

prop : 신호 에너지가 임의의 두 어댑터 사이에서 전파되는 데 걸리는 최대 시간

trans : 최대 크기의 이더넷 프레임을 전송하는 데 걸리는 시간
(10Mbps 이더넷에서 대략 1.2msec)

c-4. 순번 프로토콜

다중 접속 프로토콜의 두가지 특성

단 하나의 노드만이 활성화 되면 그 노드가 R bps의 처리율을 가져야 한다

M개의 노드가 활성이면 각 노드가 거의 R/M bps의 처리율을 가진다.

알로하와 CSMA는 첫번째 특성을 가지나 두 번째 특성은 없다.

순번 프로토콜을 개발하게 된 계기이다.

채널 나누기 MAC protocol : high load 일 때 효율적 공정, low load일 때 비효율(무조건 1/N을 분배)

랜덤 access MAC protocol : low load 일 때 효율, high load일 때 비효율(충돌 overhead)

c-4-1. 폴링 프로토콜

노드 중 하나를 마스터 노드로 지정.

각 노드를 라운드 로빈 형식으로 폴링.

마스터가 노드1에게 최대로 보낼 수 있는 프레임 수에 대한 메시지를 보내준다.

노드 1이 모두 보내고 나면 노드 2에게 최대로 보낼 수 있는 프레임 수에 대한 메시지를 보내준다.

단점

폴링 지연(노드가 전송할 수 있음을 알리는데 걸리는 시간)으로 인해 활성 노드는 R bps보다 작은 전송률을 가진다.

마스터 노드가 고장 나면 전체가 작동 안하게 됨

c-4-2. 토큰 전달 프로토콜

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

토큰이 노드1->노드2->노드3 순으로 토큰을 전달한다.

노드는 토큰을 수신하면, 보낼 데이터가 있을 때만 토큰을 잡는다.

보낼 게 있으면 최대 개수 만큼 프레임을 보낸다.

노드하나가 실패하면 전체가 동작하지 않는다.

d. 스위치 근거리 네트워크

스위치 네트워크에서는 링크 계층 프레임을 전달하기 위해 IP 주소가 아닌 링크 계층 주소를 사용

d-1. 링크 계층 주소체계와 ARP

d-1-1. MAC 주소

호스트의 어댑터 혹은 라우터의 어댑터가 링크 계층 주소를 가진다.

다수의 어댑터를 가지고 있는 호스트나 라우터는 여러개의 링크 계층 주소를 가진다.

MAC 주소는 6바이트(48비트) 길이이고, 16진수 표기법으로, 각 바이트는 2개의 16진수로 표현.

어떤 어댑터도 동일한 주소를 가지지 않는다!(IEEE에서 주소 할당)

MAC 주소는 평면 구조를 가지며, 어댑터의 위치에 따라 변경되지 않음

마치 사람의 주민등록번호와 같다(ip는 위치에 따라 변하는 것처럼, 주소와 비슷하다)

d-1-2. ARP

네트워크 계층 주소(ip)와 링크 계층 주소(MAC 주소) 사이의 변환
(ARP는 링크 계층과 네트워크 계층의 경계에 있다고 봐야한다.)

ARP는 동일한 서브넷상에 있는 호스트나 라우터 인터페이스의 IP 주소만을 해결한다.

호스터와 라우터는 자신의 메모리에 ARP 테이블을 가지고 있다.

테이블엔 <IP 주소, MAC 주소, TTL>이 있다.

ARP 테이블을 보고 노드를 찾아 간다.

만약 송신 노드의 ARP 테이블에 목적지 노드에 대한 엔트리가 없다면?

먼저 송신 노드 ARP 패킷이라는 특수 패킷을 구성한다.
ip주소와 mac 주소를 포함하는 필드를 갖고 있다.
ARP 질의 패킷의 목적은 해결하려는 ip주소에 대응하는 mac 주소를 결정하기 위해
모든 호스트와 라우터에게 질의하는 것.
송신 노드는 어댑터에게 ARP 패킷을 전달하여,
브로드캐스트 주소(FF-FF-FF-FF-FF-FF)로 패킷을 전송하도록 지시
서울시 xx구 xx동 xx아파트 101호에 사는 사람 주민번호가 뭔지 아는사람?
각 노드의 어댑터는 ARP 패킷을 자신의 ARP 모듈로 전달,
모듈이 자신의 ip와 패킷 속 ip와 비교하여 일치할 경우 요구 정보를 반환.
질의를 한 호스트는 답변을 듣고, 자신의 ARP 테이블을 갱신

질의 메시지는 브로드캐스트로 전달되지만 응답 메시지는 표준 프레임으로 전송된다.

ARP의 플러그 앤 플레이, 즉 노드의 ARP 테이블이 자동으로 구축된다.

d-1-2-1. 서브넷에 없는 노드로 데이터그램 전송

라우터는 각 인터페이스 당 하나의 IP 주소를 가진다. 각 라우터 인터페이스는 ARP 모듈(라우터 안)과 어댑터를 가진다.

물론 각 인터페이스 별로 MAC 주소를 가진다.

ARP로 라우터의 MAC 주소를 알아내 원래 목적지를 담은 데이터그램을 포함한 프레임을 전달한다
라우터의 어댑터의 링크 계층 프레임이 자신을 목적지로 했는지 확인 후 라우터의 네트워크 계층으로 보낸다.
라우터는 포워딩 테이블을 참조해 정확한 인터페이스를 결정한다
데이터그램을 새 프레임에 캡슐화해 서브넷 2로 전송한다.
ARP로부터 목적지의 MAC 주소를 알아내 보낸다.

d-2. 이더넷

최초의 이더냇 랜은 노드를 연결하기 위해 동축 버스를 사용.

버스 토폴로지의 이더넷은 브로드캐스트 랜으로, 전송되는 모든 프레임은 버스에 연결된 모든 어댑터를 거치며 처리됨

이후 랜을 허브 기반의 스타 토폴로지를 사용하는 이더넷으로 대체했다.

허브는 프레임이 아닌 각각의 비트에 대한 처리를 하는 물리 계층 장치이다. 허브도 브로드캐스트 랜이므로, 여러 프레임이 수신되면 충돌이 발생해 재전송 해야한다.

허브 이후 중앙의 허브가 충돌이 없는 스위치로 대체되었다.

d-2-1. 이더넷 구조

데이터 필드(46~1500바이트) : IP 데이터그램을 운반(다른 네트워크 계층도 가능), 46보다 작으면 채워서라도 보내야 하고, 1500바이트보다 많으면 데이터그램을 단편화해야함.
목적지 주소(6바이트) : 목적지 어댑터의 MAC주소
출발지 주소(6바이트) : 전송하는 어댑터의 MAC주소
타입 필드(2바이트) : 이더넷으로 하여금 네트워크 게층 프로토콜을 다중화(연계). IP 외의 다른 네트워크 계층 프로토콜을 사용할 수 있음을 의미
순환중복검사(CRC, 4바이트)
프리앰블(8바이트) : 첫 7바이트는 10101010값을 가짐. 마지막 바이트는 10101011이다. 첫 7개의 바이트는 수신 어댑터를 깨우고, 수신자의 클록을 송신자의 클록에 동기화시키는 역할을 한다. 8번째 바이트의 마지막 두 비트(연속으로 오는 1)는 어댑터로 하여금 중요한 것이 오고 있음을 알려준다.

d-2-2. 이더넷 특징

비연결형 서비스
핸드셰이킹하지 않고 이더넷 프레임에 데이터그램을 캡슐화해서 그 프레임을 랜으로 전송
비신뢰적인 서비스
CRC를 통과해도 응답이 없고, 실패해도 응답이 없다. CRC를 실패하면 그냥 수신자가 폐기한다.
CRC를 통과했는지 알 방법이 없다.(TCP가 이 역할을 대신한다.)

d-3. 링크 계층 스위치

스위치는 그 자체가 서브넷의 호스트와 라우터들에게 투명함.

호스트/라우터는 프레임을 스위치가 아닌 다른 호스트/라우터를 목적지로 해서 랜상으로 보내며,
중간에 스위치가 프레임을 받아서 다른 노드에게 전달하는 것을 알지 못한다.

d-3-1. 스위치의 전달 및 여과

여과 : 프레임을 전달할지 혹은 폐기할 지 결정.

전달 : 전송될 인터페이스를 결정하고 해당 인터페이스로 내보내는 것.

여과와 전달은 스위치 테이블을 이용.

d-3-2. 스위치의 작동 방식

목적지 주소 DD-DD-DD-DD-DD-DD를 가진 프레임이 스위치의 인터페이스 X에 도착했다고 가정

목적지 주소에 대한 엔트리가 스위치 테이블에 없을 경우 : 인터페이스 X를 제외한 모든 인터페이스에 프레임 복사본을 보낸다.(브로드캐스트)
목적지 주소가 인터페이스 X에 대한 엔트리가 있는 경우 : 이 경우, 다른 인터페이스를 전달할 필요가 없으며, 프레임을 여과를 실행하여 제거(DD-DD-DD-DD-DD-DD로 보내려면 인터페이스 X를 사용해야 될 경우 잘못된 상황이다.)
목적지 주소가 인터페이스 Y에 대한 엔트리가 있는 경우 : Y에 접속된 랜 세그먼트로 전달

d-3-3. 스위치의 자가학습

*플러그앤플레이*

스위치 테이블을 자동으로 동적으로 자치적으로 구축하는 기능

스위치 테이블은 초기에 비어있다.
인터페이스로 수신한 각 프레임에 대해서 다음 정보를 저장한다.
a. 프레임의 출발지 주소필드에 있는 MAC 주소
b. 프레임이 도착한 인터페이스
c. 현재시간
일정시간이 지난 후에도 스위치가 해당 주소를 출발지 주소로 하는 프레임을 수신하지 못하면 테이블에서 삭제한다.

d-3-4. 스위치 vs 라우터

라우터 : 네트워크 계층 주소를 사용해서 패킷 전달, 저장 후 전달 패킷 스위치, 3계층까지 프레임 처리해야함

스위치 : MAC 주소를 사용해서 패킷 전달, 저장 후 전달 패킷 스위치, 플러그앤 플레이, 2계층까지만 패킷 처리

d-4. 가상 근거리 네트워크(VLAN)

트래픽 격리 부족, 사용자 관리, 스위치의 비효율적인 사용을 해결하기 위한 기술.

VLAN을 지원하는 스위치는 하나의 물리적 근거리 네트워크 기반 구조상에서 여러 개의 가상 근거리 네트워크들을 정의할 수 있게 한다.

d-4-1. VLAN 트렁킹

트렁크 포트를 지정해 트렁크 링크를 통해 다른 스위치로 전달해준다.

프레임이 속한 VLAN을 식별해주는 4바이트 VLAN 태그를 헤더에 덧붙여 어떤 VLAN의 요청인지를 파악한다.(802.1Q)

Computer ScienceNetwork