Link Layer

2023. 02.06 13:00 복습

Link Layer

링크 계층은 물리적으로 인접한 노드를 연결시키는 역할을 한다.

즉 링크로 연결된 노드를 연결하는 것이다. 전기적 신호를 처리하며 네트워크 카드 (NIC)를 사용한다.

링크 계층의 기능

• 프레임화: 거의 모든 링크 계층 프로토콜은 네트워크 계층 데이터그램을 링크상으로 전송하기 전에 링크 계층 프레임에 캡슐화한다.
  네트워크 계층 데이터그램이 들어있는 데이터 필드와 여러 개의 헤더 필드로 구성된다. 프레임 구조는 링크 계층 프로토콜에 의해 명시된다.
• 링크 접속: 매체 제어 접속 (medium access control, MAC) 프로토콜은 링크상으로 프레임을 전송하는 규칙에 대해 명시한다.
  점대점 링크의 경우 MAC 프로토콜은 단순하다. 이 경우 송신자가 링크가 사용되지 않을 때마다 프레임을 전송한다.
  하나의 브로드캐스트 링크를 여러 노드가 공유하는 경우, MAC 프로토콜은 여러 노드로부터의 프레임 전송을 조정한다.
• 신뢰적 전달: 링크 계층 프로토콜이 신뢰적 전달 서비스를 제공하는 경우 네트워크 계층 데이터그램은 링크상에서 오류 없이 전달된다. 링크 계층의 신뢰적 전달 서비스도 확인 응답과 재전송을 통해 가능해진다.
  링크 계층의 신뢰적 전달 서비스는 무선 링크처럼 오류율이 높은 링크에서 주로 사용한다.
  transport 계층의 신뢰적 전달인 재전송 서비스와는 다르게 링크 계층 프로토콜은 오류가 발생한 링크에서 오류를 정정한다.
  그러나 낮은 오류율을 가진 유선 링크에서는 불필요한 오버헤드가 될 수 있으므로 신뢰적 전달 서비스를 제공하지 않는다.
• 오류 검출과 정정 

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

이더넷

• 이더넷은 유선 랜 시장을 상당히 많이 점유하고 있다. 큰 이유는 싸고 단순하기 때문이다.
• 이더넷의 구현 방식은 먼저 BUS 형식이 있다. coaxible cable를 사용하는 경우다.
• 현재는 STAR 형식인 Switch를 사용하는 경우다. 스위치를 중심으로 이더넷이 구성된다.
• 이더넷은 비연결적이고 신뢰성이 낮은 특징을 가지고 있다. 즉 재전송이 없는 것이다.

이더넷의 프레임 구조

이더넷 프레임 구조

 

• 프리앰블: 이더넷 프레임은 8바이트의 프리앰블 필드로 시작한다. 프리앰블의 첫 7바이트는 10101010 값을 가진다. 마지막 바이트는 10101011 값을 가진다. 프리앰블의 첫 7바이트는 수신 어댑터를 "깨우고", 수신자의 클록을 송신자의 클록에 동기화시키는 역할을 한다.
• 출발지 주소: 이 필드는 프레임을 랜으로 전송하는 어댑터의 MAC 주소를 포함한다.
• 목적지 주소: 이 필드는 목적지 어댑터의 MAC 주소를 포함한다.
• 타입 필드: 타입 필드는 이더넷으로 하여금 네트워크 계층 프로토콜을 다중화하도록 허용한다.
• 데이터 필드: 이 필드는 IP 데이터그램을 운반한다. 이더넷의 최대 전송 단위는 1500바이트다. (MTU)
• CRC: 순환중복검사인 이 CRC 필드의 목적은 수신 어댑터인 어댑터 B로 하여금 프레임에 오류가 생겼는지 검출할 수 있게 하는 것이다.

에러 검출 방법

에러 검출 방법으로는 패리티 검사와 CRC에 대해 잠깐 언급하겠다. 

패리티 검사

• 먼저 패리티 검사다. 전송되는 D가 d 비트를 갖고 있다고 가정하자.
• 짝수 패리티 기법은 사용자가 단순히 한 비트를 추가하고 그 비트 값을 d+1 개의 비트들에서 1의 총 개수가 짝수가 되도록 선택한다.
• 홀수 패리티 기법은 패리티 비트 값을 1이 홀수 개가 되도록 선택한다.
• 만약 짝수 패리티 기법에서 1의 값을 가진 비트가 홀수 개라면, 수신자는 최소한 하나의 비트 오류가 발생했음을 알 수 있다.
• 그러나 짝수 개의 비트 오류가 발생하면 곤란해진다. 에러를 검출하지 못하는 오류가 생길 수 있다.
• 그래서 단일 비트 패리티 기법을 차원 패리티 기법으로 확장해서 비트의 오류를 검출한다.

CRC

다음은 더 강력한 CRC 에러 검출 방법이다. 모든 CRC는 덧셈의 올림이나 뺄셈의 빌림이 없는 모듈로-2 연산을 사용한다.

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

CRC 비트는 다음과 같이 동작한다.

 

• d 비트로 이루어진 데이터 D를 송신 노드가 수신 노드로 전송하고자 한다고 가정하자.
• 먼저 송신자와 수신자는 G로 표기되는 생성자로 알려진 r + 1 비트 패턴에 합의한다. G의 최상위 비트는 1이어야 한다. 주
• 어진 데이터 D에 대해 송신자는 r개의 추가 비트 R을 선택해서 D 뒤에 덧붙이며, 이 d+r 비트 패턴은 모듈로 -2 연산을 이용하여 G로 정확히 나누어진다.
• CRC를 이용한 오류 검사 절차는 단순하다. 수신자 d+r개의 수신 비트를 G로 나눈다.
• 만일 나머지가 0이 아니면 오류가 발생한 것으로 그렇지 않으면 데이터가 정확한 것으로 판정할 수 있다.
• 공식은 R=D*2^r/G의 나머지다.

Link Type

• 두 개의 링크 타입이 존재하는데 하나는 점대점 링크 타입이다.
• 즉 링크의 한쪽 끝에 한 송신자와 링크의 다른 쪽 끝에 한 송신자가 있다.
• 대다수의 링크 계층 프로토콜은 점대점 링크용으로 설계되었다.
• 다른 종류의 링크는 브로드캐스트 링크다. 동일한 하나의 공유된 브로드캐스트 채널에 다수의 송신 노드 및 수신 노드들이 연결된다.

컴퓨터 네트워크에서도 공유되는 브로드캐스트 채널로 보내는 노드들의 전송을 조정하기위 한 다중 접속 프로토콜이 존재한다.

모든 노드들이 프레임을 전송할 수 있으므로, 2개 이상의 노드가 동시에 프레임을 전송할 수 있다.

이런 일이 발생하면, 모든 노드는 동시에 여러 개의 프레임을 받게 된다. 즉, 전송된 프레임들이 각 수신자에서 충돌한다.

일반적으로 충돌이 발생하면 어떤 수신 노드도 전송된 프레임의 의미를 파악할 수 없게 된다.

따라서 충돌이 많을수록 브로드캐스트 채널의 대역폭이 많이 낭비된다.

다수의 노드가 활성화되어 있을 때 브로드캐스트 채널이 제대로 동작하도록 보장하기 위해서는 활성 노드들의 전송을 어떤 식으로든 조정할 필요가 있다. 이러한 조정작업은 다중 접속 프로토콜의 책임이다.

다중 접속 프로토콜

다중 접속 프로토콜로는 3가지 종류가 있다. 채널 분할 프로토콜, 랜덤 접속 프로토콜, 순번 프로토콜이 있다.

이에 대해 각각 살펴보겠다.

그전에 초당 R 비트의 전송률을 갖는 브로드캐스트 체널에 대한 다중 접속 프로토콜은 다음과 같은 특성을 지니는 것이 바람직하다.

 

1. 단 하나의 노드가 전송할 데이터가 있을 때는 그 노드가 R bps의 처리율을 가진다.
2. M개의 노드가 전송할 데이터가 있을 때는 각 노드가 R/M bps의 처리율을 갖는다. 이것은 M개의 노드 각각이 순간적인 R/M 전송률을 항상 가짐을 의미한는 것은 아니며, 단지 각 노드가 적당히 정의된 시간 동안 R/M의 평균 처리율을 가짐을 의미한다.
3. 이 프로토콜은 분산되어 있다. 즉, 고장으로 인해 전체 시스템을 정지시킬 수 있는 마스터 노드가 없다.
4. 이 프로토콜은 단순해서 구현하는 데 비용이 적게 든다.

채널 분할 프로토콜

먼저 채널 분할 프로토콜이다. 시분할 다중화인 TDM, 주파수분할 다중화인 FDM이 존재한다.

 

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

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

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

 

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

따라서 FDM은 하나의 큰 R bps 채널로부터 N개의 R/N bps의 작은 채널을 만든다.

 

그러나 이 두 가지는 단점이 존재하는데 전송할 패킷을 가진 노드가 단 하나일지라도 노드는 R/N 대역폭으로 제한된다.

또한 낭비가 존재한다. TDM은 자신의 차례를 기다려야 한다는 단점도 존재한다.

CDMA인 코드 분할 다중 접속도 존재하는데 여기서는 TDM에서의 시간 슬롯이나 FDM에서의 주파수처럼 CDMA 코드가 다중 접속 채널 사용자에게 할당될 수 있다는 정도만 알아두자.

랜덤 접속 프로토콜

이번에는 랜덤 접속 프로토콜이다. 먼저 2가지가 존재하는데 슬롯 알로하와 순수한 알로하다.

랜덤 접속 프로토콜에서 전송 노드는 항상 채널의 최대 전송률인 R bps로 전송한다.

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

그러나 충돌했을 때 노드는 해당 프레임을 즉시 재전송할 필요가 없다. 대신 그 프레임을 재전송하기 전에 랜덤 지연 시간 동안 기다린다.

슬롯 알로하

• 먼저 슬롯알로하는 각 노드는 언제 슬롯이 시작하는지 알 수 있게 끔 동기화되어 있다. 즉 싱크가 맞다는 것이다. 굉장히 구현하기 어려운 조건이다. 모든 프레임은 사이즈가 같아야만 한다(L비트로 같다). 시간은 L/R초의 슬롯들로 모두 똑같이 나뉜다. 노드는 슬롯의 시작점에서만 프레임을 전송하기 시작한다.
• 한 슬롯에서 2개 이상의 프레임이 충돌하면, 모든 노드는 그 슬롯이 끝나기 전에 충돌 발생을 알 수 있다.
• 슬롯 알로하는 활성 노드가 하나일 때 잘 동작한다. 채널 분할과 달리 슬로하는 하나의 활성 노드로 하여금 전속력 R로 계속해서 프레임을 전송할 수 있도록 허용한다. 또한 슬롯 알로하는 각 노드가 충돌을 감지하고 언제 재전송할지 각자 결정하므로 상당히 분산적이다. 그러나 여러 노드가 활성 상태면 고려할 요소가 생긴다.
• 첫째 활성 노드가 많이 있으면 일부 슬롯이 충돌로 인해 결과적으로 낭비된다는 것이다.
• 둘째는 모든 활성 노드들이 확률적인 전송 정책으로 인해 전송을 억제하는 경우 일부 슬롯이 빈다는 것이다. 정확히 한 노드만 전송하는 슬롯을 성공한 슬롯이라 한다. 슬롯 다중 접속 프로토콜의 효율성은 항상 전송할 프레임이 많은 활성 노드가 많은 경우의 장시간에 걸친 성공적인 슬롯들의 부분으로 정의된다.
• 알로하의 최대 효율은 0.37로 많은 노드가 전송할 프레임이 많을 때 37%의 슬롯만 낭비되지 않는다.
  이와 유사한 분석에 의하면 슬롯의 37%는 빈 채로 전송되며 슬롯의 26%는 충돌을 겪는다.
• 순수한 알로하는 동기화는 필요없다. 즉 싱크가 맞지 않아도 된다.
• 순수 알로하 프로토콜의 최대 효율은 슬롯 알로하의 절반이다.
• 순수 알로하는 슬롯이 없고 완전히 분산된 프로토콜이다. 동기화를 하지 않았으므로 실행 조건은 간단하지만 효율은 나쁘다.

CSMA

랜덤 접속 프로토콜의 마지막 방식인 CSMA다. Carrier Sense Multiple Access의 약어다.

앞의 2가지 경우는 다른 노드의 전송 여부에는 관심이 없다. 이번 방식은 좀 더 다른 노드의 행동을 주시하며 예의 바른 대화? 와 비슷하다.

먼저 말하기 전에 듣는다. 즉 캐리어 감지라고 하는데, 만일 다른 노드가 프레임을 채널로 전송하고 있으면, 노드는 임의의 짧은 시간 동안 전송 중단을 감지하면 프레임을 전송하기 시작한다.

다음은 다른 사람이 동시에 말하기 시작하면 말을 중단한다. 네트워크에서는 이것을 충돌 검출이라 한다.

만일 다른 노드가 방해 프레임을 전송하고 있음을 검출하면, 자신의 전송을 중단한다.

이후 랜덤 시간 동안 유휴 시 감지 및 전송 과정을 반복한다. 이들 두 규칙은 CSMA와 CSMA/Cd 프로토콜에 포함한다.

 

먼저 CSMA에 대해 알아보자.

 

• 먼저 CSMA는 만일 모든 노드들이 매체 감지를 하면 어떻게 충돌이 발생할 수 있는가?에 대한 질문을 해보자.
• 이 경우에 모든 노드는 다른 노드가 전송하고 있는 것을 감지할 때마다 자신의 전송을 억제한다.
• 전송하기 전에 다른 노드들로부터 귀를 기울이는 것이다. 브로드캐스트 채널의 종단간의 채널 전파 지연이 CSMA 성능을 결정하는 데 중요한 역할을 한다.
• 이러한 전파 지연이 길수록 네트워크의 다른 노드에서 이미 시작된 전송을 캐리어 감지 노드가 감지할 수 없는 경우가 증가한다. 아래 이미지와 같은 경우다.

 

전송이 충돌하는 두 CSMA 노드의 공간 시간 도표

 

CSMA/CD는 다중 접속 프로토콜에 충돌 검출을 추가해 쓸모없는 손상된 프레임을 모두 전송하지 않아도 되므로 프로토콜의 성능을 향상했다.

CSMA/CD는 다음과 같이 동작한다.

 

1. 어댑터는 네트워크 계층으로부터 데이터그램을 받아서 링크 계층 프레임을 만든 후에 그 프레임을 어댑터의 버퍼에 저장한다.
2. 어댑터는 채널이 유휴한 것을 감지하면 프레임 전송을 시작한다. 만일 어댑터가 채널이 바쁜 것을 감지하면, 어떤 신호가 감지되지 않을 때까지 더 기다렸다가 프레임을 전송하기 시작한다.
3. 전송하는 동안 어댑터는 브로드캐스트 채널을 사용하는 다른 어댑터로부터의 신호 에너지가 있는지 감시한다.
4. 프레임 전체를 전송하는 동안 다른 어댑터로부터의 신호 에너지가 감지되지 않으면, 프레임 전송을 완료한다. 그러나 전송 도중에 다른 어댑터로부터의 신호 에너지를 감지하면, 자신의 프레임 전송을 취소한다.
5. 어댑터는 전송을 취소한 후 임의의 랜덤 시간만큼 기다린 후 단계 2로 돌아간다.

 

랜덤 시간동안 기다리는 이유는 명백하다.

만일 두 노드가 동시에 프레임을 전송하고 동일한 고정 시간 동안 기다리면 계속해서 충돌하게 된다.

그렇다면 랜덤 백오프 시간을 정하는 데 사용되는 시간 간격은 어떻게 정하는 것이 좋을까?

만일 시간 간격이 크고 충돌한 노드 수가 적으면, 유휴 시 감지 및 전송 단계를 반복하기 전에 기다리는 시간이 커질 가능성이 높다.

 

반면, 시간 간격이 작고 충돌 노드가 많으면, 선택된 랜덤 값이 같을 가능성이 높아서 전송하는 노드들이 다시 충돌할 수 있다.

따라서 충돌하는 노드가 적을 때는 시간 간격을 작게 하고, 충돌하는 노드가 많을 때는 시간 간격을 크게 할 필요가 있다.

이진 지수적 백오프 알고리즘은 이 문제를 효율적으로 해결한다.

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

따라서 프레임이 충돌을 더 많이 경험할수록 K를 선택할 간격을 크게 한다.

순번 프로토콜

우리는 폴링 프로토콜과 토큰 전달 프로토콜에 대해서 간략하게 알아보겠다.

폴링 프로토콜

• 폴링 프로토콜은 노드 중 하나를 마스터 노드로 정한다.
• 마스터 노드는 각 노드를 라운도 로빈 방식으로 폴링한다. 특히, 마스터 노드는 먼저 노드 1에게 노드 1이 최대로 보낼 수 있는 프레임수에 대한 정보를 지닌 메시지를 전송한다.
• 노드 1이 프레임을 보낸 다음에 마스터 노드는 노드 2에게 노드 2가 최대로 보낼 수 있는 프레임 수를 알려 준다.
• 마스터 노드는 채널에 신호가 없는 것을 봄으로써 노드가 프레임 전송을 끝마쳤음을 결정할 수 있다.
• 마스트 노드는 순환적으로 각 노드를 폴링 하는 방식으로 이 과정을 계속한다.
• 폴링 프로토콜은 충돌뿐만 아니라 랜덤 접속 프로토콜의 단점인 빈 슬롯을 제거함으로써 훨씬 높은 효율을 제공한다. 그러나 단점도 가지고 있다.
• 폴링 지연과 마스터 노드가 고장날 시에 어쩔 도리가 없다는 것이 문제다.

토큰 전달 프로토콜

• 다음은 토큰 전달 프로토콜이다. 쉽게 말해 토큰을 가지고 있어야 프레임을 전송할 수 있다.
• 노드가 토큰을 수신하면, 전달할 프레임이 있을 때만 토큰을 붙잡는다. 그렇지 않으면 토큰을 다음 노드에게 전달한다.
• 분산 방식으로 효율이 매우 높지만 토큰 전달에 실패하면 큰 문제가 발생할 수 있다. 

MAC 주소

• 링크 계층 주소는 MAC 주소, 랜 주소, 물리 주소로 알려져 있다. MAC 주소는 네트워크 카드에 있다.
• IP와 같은 클래스가 없으며 IP가 집주소라면 MAC 주소는 주민번호 같은 느낌이다.
• 대부분의 MAC 주소는 6바이트며, 랜안에서는 모두 유니크한 MAC 주소를 가진다.
• ARP 프로토콜은 IP와 맥주소를 변환해준다.
• 각 호스트와 라우터는 자신의 메모리에 ARP 테이블을 가지고 있다.
• 이 ARP 테이블은 IP 주소와 MAC 주소 간의 매핑 정보를 포함한다.
• 라우터는 IP 주소로 포워딩하고 스위치는 보통 MAC 주소로 포워딩한다. 
• IP에서는 NEXT hop을 정하며 스위치는 자가학습 기능을 가지고 있다.

2023. 02.06 15:10 복습 및 정리

 

참고자료

컴퓨터 네트워킹 하향식 접근 제 7판