[Computer Network] 6.1~6.3

6. 링크 계층: 링크, 접속망, 랜

6.1 링크 계층 소개

노드(node)

• 호스트, 라우터, 스위치, WiFi AP

 

링크(link)

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

 

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

 

무선 호스트와 서버 간 6개의 링크 계층 홉

 

---

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

링크 계층의 기본 서비스

단일 통신 링크상으로 데이터그램을 한 노드에서 인접 노드로 "이동"시키는 것

 

✖️ 그 외의 서비스

• 프레임화
  • 거의 모든 링크 계층 프로토콜은 네트워크 계층 데이터그램을 링크 상으로 전송하기 전에 링크 계층 프레임에 캡슐화한다.
• 링크 접속
  • 매체 접속 제어 프로토콜은 링크상으로 프레임을 전송하는 규칙에 대해서 명시한다.
• 신뢰적 전달
  • 링크 계층 프로토콜이 신뢰적 전달 서비스를 제공하는 경우 네트워크 계층 데이터그램은 링크상에서 오류 없이 전달된다.
• 오류 검출과 정정
  • 오류가 있는 데이터그램은 전달할 필요가 없으며, 다라서 대부분의 ㄹ이크 계층 프로토콜은 오류를 검출하는 방법을 제공한다.

 

---

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

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

 

✅ 링크 계층

• 하드웨어와 소프트웨어의 조합이며, 프로토콜 스택상에서 소프트웨어와 하드웨어가 만나는 부분이라고 할 수 있다.

 

---

6.2 오류 검출 및 정정 기술

비트 수준 오류 검출과 정정은 데이터 링크 계층에서 제공하는 대표적인 두 가지 서비스이다.

✋ 하지만, 오류 검출 비트를 사용하더라도 여전히 미검출된 비트 오류가 있을 수 있다.

일반적으로, 더 향상된 오류 검출 및 정정 기술은 더 많은 오버헤드를 필요로 한다.

 

전송되는 데이터의 오류를 검출하기 위한 세 가지 기술은 다음과 같다.

• 패리티 검사
• 체크섬
• 순환 중복검사

 

6.2.1 패리티 검사

가장 단순한 형태의 오류 검출

 

• 전송되는 정보 D가 d 비트를 가지고 있다고 가정하면
  • 짝수 패리티 기법은 사용자가 단순히 한 비트를 추가하고 그 비트값을 d+1개의 비트들에서 1의 총개수가 짝수가 되도록 선택한다.
  • 짝수 패리티 기법에서 1의 값을 가진 비트가 홀수 개라면, 수신자는 최소한 하나의 비트 오류가 있음을 알게 된다.
• 2차원 패리티 기법에서는 반전된 비트를 포함하는 열과 행에 대한 패리티에 오류가 생긴다.
  • 따라서 수신자는 단일 비트 오류의 발생을 검출할 수 있을 뿐만 아니라, 패리티 오류가 있는 열과 행의 인덱스값을 사용해 잘못된 비트를 실제로 식별해서 오류를 정정할 수도 있다.

• 오류를 검출 및 정정하는 수신자의 능력을 순방향 오류 정정(forward error cor-rection, FEC)이라고 한다.

 

---

6.2.2 체크섬 방법

TCP, UDP에서 사용된다.

방법

• 데이터의 바이트를 16비트 정수 단위로 취해서 더한다.
• 더한 값의 1의 보수가 인터넷 체크섬이 되며, 이것을 세그먼트 헤더에 넣어준다.
• 수신자는 수신데이터 합의 1의 보수를 취한 후, 그 결과가 모두 1인 비트로 구성되어 있는지 계산함으로써 체크섬을 검사한다. 즉 한 비트라도 0이면 오류가 발생한 것이다.

장점

• 체크섬 방법은 상대적으로 패킷 오버헤드가 적다.
• 예를 들어, TCP와 UDP의 체크섬은 16비트만 사용한다.

 

단점

• CRC와 비교하면 오류 면에서 상대적으로 취약하다. '

 

🤨 그렇다면 왜 트랜스포트 계층에서는 체크섬을 사용하고 링크 계층에서는 CRC을 사용하는 것일까?

• 트랜스포트 계층은 일반적으로 호스트의 운영체제의 일부로서 소프트웨어로 구현된다.
  • 체크섬처럼 간단하고 빠른 오류 검출 기법이 필요하다.
• 반면에 링크 계층에서의 오류 검출은 어댑터안의 전용 하드웨어로 구현되므로
  • 더 복잡한 CRC 연산을 빨리 수행할 수 있다.

 

---

6.2.3 순환 중복검사

오늘날 컴퓨터 네크워크에서 널리 사용되는 오류 검출 기술

 

• CRC 코드는 다항식 코드로도 알려져있다.
• 각각의 CRC 표준은 r+1 비트보다 적은 수의 버스트 오류를 검출할 수 있다.

 

😀 더 자세한 내용은 아래의 블로그를 참고하자!

https://4legs-study.tistory.com/65

[데이터링크 계층] 오류 검출 (Error Detection)

 

---

6.3 다중 접속 링크와 프로토콜

두 종류의 네트워크 링크가 있다.

 

점대점 링크(point-to-point link)

• 링크의 한쪽 끝에 한 송신자와 링크의 다른 쪽 끝에 한 수신자가 있다.
• 대다수의 링크 계층 프로토콜들은 점대점 링크용으로 설계되었으며, PPP와 HDLC가 이에 속한다.

 

브로드캐스트 링크(broadcast link)

• 동일한 하나의 공유된 브로드캐스트 채널에 다수의 송신 노드 및 수신 노드들이 연결된다.
• 이더넷과 무선 랜은 브로드캐스트 링크 기술의 대표적인 예이다.

✅ 브로드캐스트라는 용어는 임의의 한 노드가 프레임을 전송하면 채널이 그 프레임을 방송(broadcast)해서 다른 모든 노드들이 그 프레임의 복사본을 수신하기 때문에 사용된 것이다.

 

이 절에서는 데이터 링크 계층에서 가장 중요한 문제 중의 하나인 다중 접속 문제(multiple access problem)

즉 다수의 송수신 노드들이 공유되는 브로드캐스트 채널로의 접속을 조정하는 문제에 대해서 살펴보겠다.

 

✖️ TV가 브로드캐스팅 방식을 사용

 

다양한 다중 접속 채널

 

 

 

충돌로 인한 브로드캐스트 채널의 대역폭 낭비

• 모든 노드는 동시에 여러 개의 프레임을 받게 된다. 즉, 전송된 프레임들이 각 수신자에서 충돌(collide)한다.
• 만일, 다수의 노드가 빈번히 프레임을 전송하려고 한다면, 그 전송은 많이 충돌할 것이며, 따라서 브로드캐스트 채널의 대역폭이 많이 낭비된다.

 

컴퓨터네트워크에서도 공유되는 브로드캐스트 채널로 보내는 노드들의 전송을 조정하기 위한

다중 접속 프로토콜(multiple access protocol)이라는 프로토콜이 있다.

 

다중 접속 프로토콜

• 채널 분할 프로토콜
• 랜덤 접속 프로토콜
• 순번 프로토콜

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

 

• 단 하나의 노드가 전송할 데이터가 있을 때는 그 노드가 R bps의 처리율을 갖는다.
• M개의 노드가 전송할 데이터가 있을 때는 각 노드가 R/M bps의 처리율을 갖는다.
• 이 프로토콜은 분산되어 있다. 즉, 고장으로 인해 전체 시스템을 정지시킬 수 있는 마스턱 노드가 없다.
• 이 프로토콜은 단순해서 구현하는 데 비용이 적게 든다.

 

---

6.3.1 채널 분할 프로토콜

TDM 시분할 다중화

• 시간을 시간프레임으로 나누고 또한 각 시간 프레임을 N개의 시간 슬롯(time slot)으로 나눈다.
• 일반적으로 슬롯 크기는 한 캐시이 한 슬롯 시간 동안 전송될 수 있게 선택된다.
• 예) 칵테일 파티에서는 파티 참석자 한 명이 고정된 시간 동안 말할 수 있고, 그 뒤 또 다른 파티 참석자가 똑같은 시간 동안 말할 수 있다.

장점

• 충돌을 제거할 수 있고 아주 공정하므로 바람직하다.

단점

• 전송할 패킷이 있는 노드가 단 하나인 경우에도 노드 전송률이 평균 R/N으로 제한된다.
• 노드가 전송 순서상 자신의 차례를 항상 기다려야 한다.

 

FDM 주파수분할 다중화

• 채널을 다른 주파수(각 R/N의 대역폭을 갖는)로 나눠서 각 주파수를 N개 노드 중 하나에게 할당한다.
• 따라서 FDM은 하나의 큰 R bps 채널로부터 N개의 R/N bps의 작은 채널을 만든다.

 

장점

• FDM은 충돌을 피하고 N개 노드에게 대역폭을 균등하게 분할한다.

 

단점

• 전송할 패킷을 가진 노드가 단 하나일지라도 노드는 R/N의 대역폭으로 한정된다.

 

 

CDMA 코드 분할 다중 접속

• 다른 코드를 각 노드에게 할당한다.
• CDMA 네트워크에서 코드들을 신중하게 선택하면 여러 노드들이 동시에 전송할 수 있고, 다른 노드들에 의해서 전송이 간섭(interfere) 되더라도 각 수신자들이 송신자의 인코딩된 데이터 비트를(수신자는 송신자의 코드를 안다고 가정함) 정확하게 수신할 수 있는 훌륭한 특성이 있다.

 

---

6.3.2 랜덤 접속 프로토콜

• 항상 채널의 최대 전송률인 R bps로 전송한다.
  • 대신 그 프레임을 재전송하기 전에 랜덤 지연 시간 동안 기다린다.
• 충돌과 관련된 각 노드는 자신만의 랜덤 지연 시간을 선택한다.
  • 충돌이 생긴 후 각 노드는 지연 시간을 스스로 결정하며, 따라서 충돌했던 노드 중 하나는 다른 노드가 선택한 지연 시간보다 충분히 작은 지연 시간을 선택함으로써 충돌 없이 자신의 프레임을 채널로 전송할 수 있다.

 

슬롯 알로하

가정

• 모든 프레임은 같은 크기 L 비트를 가진다.
• 시간은 같은 크기의 슬롯으로 분할한다. (L/R초)
• 노드는 슬롯의 시작점에서만 프레임을 전송한다.
• 각 노드는 슬롯의 시작을 알 수 있도록 동기화한다.
• 한 슬롯에서 둘 이상의 노드들이 충돌하면 다른 노드들이 충돌을 감지한다.

 

동작

• 노드는 전송할 새 프레임이 있으면 다음 슬롯에서 전송
• 충돌이 없으면 노드는 다음 슬롯에서 새로운 프레임을 전송
• 충돌이 발생하면 확률 p로 해당 프레임을 다음 슬롯에서 재전송

 

장점

• 하나의 활성 노드가 채널의 최대 속도인 R로 계속 전송
• 충돌 감지 및 재전송을 노드 각자가 결정하여 분산, 노드들은 슬롯으로 동기화 필요
• 간단함

 

단점

• 활성 노드가 많으면 충돌로 인해 슬롯 낭비
• 확률적인 전송으로 전송을 억제하는 경우 빈 슬롯 발생
• 클럭 동기화

 

각 슬롯의 상태

• S: Success 전송 성공, C: Collision 충돌 발생, E: Empty 비어 있음

 

슬롯 알로하 호율

• 최대 효율 37%
  • 많은 노드 전송 시 37%의 슬롯 만이 낭비되지 않음

 

 

알로하(ALOHA)

• 슬롯이 없어 완전히 분산된 프로토콜
• 더 간단하고 동기화 없음
• 프레임이 상위 계층에서 도착하면 바로 전송
• 충돌 확률 증가
• t0에 전송된 프레임은 [t0-1, t0+1]에서 다른 프레임과 충돌

 

알로하 효율

• 18% 슬롯 알로하보다도 더 낮은 효율

 

 

CSMA(Carrier Sense Multiple Access)

• 슬롯 알로하와 순수 알로하에서 노드가 전송 여부를 결정하는 것은 브로드캐스트 채널에 접속되어 있는 다른 노드의 활성 여부와 무관하다.
  • 다른사람이 말을 할 때 수다를 떠는 무례한 행동이라고 볼 수 있다.
• 사람들간의 예의 바른 대화에서 지켜야 할 중요한 두 가지 규칙은 다음과 같다.
  • 말하기 전에 듣는다.
    • 다른 사람이 말하고 있으면 끝날 때 까지 기다려라
    • 네트워크에서는 이것을 캐리어 감지(carrier sensing)이라고 한다.
    • 노드는 전송하기 전에 채널을 듣는다.
    • 만일 다른 노드가 프레임을 채널로 전송하고 있으면, 노드는 임의의 짧은 시간 동안 전송 중단을 감지하면 프레임을 전송하기 시작한다.
  • 다른 사람이 동시에 말하기 시작하면 말을 중단한다.
    • 네트워크에서는 이것을 충돌 검출(collision detection)이라 한다.
    • 만일 다른 노드가 방해 프레임을 전송하고 있음을 검출하면, 자신의 전송을 중단하고 랜덤 시간 동안 기다린 후 유휴 시 감지 및 전송 과정을 반복한다.

 

이들 두 규칙은 CSMA와 CSMA/CD 프로토콜에 포함된다.

 

 

✅ 브로드캐스트 채널의 종단간의 채널 전파 지연

• 신호가 채널의 한쪽 끝에서 다른 쪽 끝으로 전파되는 데 걸리는 시간이 CSAM의 성능을 결정하는 데 중요한 역할을 한다.
  • 이러한 전파 지연이 길수록 네트워크의 다른 노드에서 이미 시작된 전송을 캐리어 감지 노드가 감지할 수 없는 경우가 더 증가한다.

 

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

 

CSMA CD(Carrier Sense Multiple Access with Collision Detection)

CSMA/CD 프로토콜의 동작

1. 어댑터는 네트워크 계층으로부터 데이터그램을 받아서 링크 계층 프레임을 만든 후에 그 프레임을 어댑터의 버퍼에 저장한다.

2. 어댑터는 채널이 유휴(idle)한 것을 감지하면(쯕, 채널로부터 어댑터로 들어오는 신호 에너지가 없으면) 프레임 전송을 시작한다. 만일 어댑터가 채널이 바쁜(busy) 것을 감지하면, 어떤 시호 에너지도 감지되지 않을 때까지 더 기다렸다가 프레임을 전송하기 시작한다.

3. 전송하는 동안 어댑터는 브로드캐스트 채널을 사용하는 다른 어댑터로부터의 신호 에너지가 있는지 감시한다.

4. 프레임 전체를 전송하는 동안 다른 어댑터로부터의 신호 에너지가 감지되지 않으면, 프레임 전송을 완료한다. 그러나 전송 도중에 다른 어댑터로부터의 신호 에너지를 감지함녀, 자신의 프레임 전송을 취소한다.

5. 어댑터는 전송을 취소한 후 임의의 랜덤 시간만큼 기다린 후 단계 2로 돌아간다.

 

충돌 검출을 하는 CSMA

 

 

🤨 랜덤 시간(고정 시간이 아닌) 동안 기다리는 이유

• 만일 두 노드가 동시에 프레임을 전송하고 동일한 고정 시간 동안 기다리면 계속해서 충돌하게 된다.
• 그렇다면 랜덤 백오프(backoff) 시간을 정하는 데 사용되는 시간 간격은 어떻게 정하는 것이 좋을까?
• 충돌하는 노드가 적을 때는 시간 간격을 작게 하고 충돌하는 노드가 많을 때는 시간 간격을 크게 할 필요가 있다.

 

이진 지수적 백오프(binary exponential backoff) 알고리즘

• 충돌을 n번 경험한 프레임을 전송할 때 노드는 {0, 1, 2, ..., 2^ㅜ-1}중에서 랜덤하게 K 값을 선택한다.
  • 따라서 프레임이 충돌을 더 많이 경험할수록 K를 선택할 간격을 크게 한다.
  • 이더넷의 경우, 노드가 실제로 기다리는 시간은 K*512비트 시간이 되며 n의 최댓값은 10으로 제한된다.
• K를 선택하는 집합 크기는 충돌 횟수에 따라 지수적으로 증가한다.
  • 이런 이유로 이 알고리즘을 이진 지수적 백오프라고 한다.

 

CSMA/CD의 효율

• 오랜 시간 동안 다수의(전송할 프레임이 많은) 활성 노드들이 있을 때 충돌 없이 프레임이 채널로 전송되는 시간 비율(fraction)이다.

 

---

6.3.3 순번 프로토콜

다중 접속 프로토콜에서 요구되는 두 가지 특성

• 단 하나의 노드만이 활성이면 그 노드가 R bps의 처리율을 가지며
• M개의 노드가 활성이면 각 노드가 거의 R/M bps의 처리율을 가진다

 

알로하와 CSMA 프로토콜은 첫 번째 특성은 지니고 있으나 두 번째 특성은 없다.

이것이 다른 종류의 프로토콜, 즉 순번 프로토콜(taking-turns protocol)을 개발하게 된 동기다.

 

순번 프로토콜 중 폴링 프로토콜과 토큰 전달 프로토콜을 살펴보자.

 

폴링 프로토콜(polling protocol)

• 노드 중 하나를 마스터 노드로 지정한다.
  • 마스터 노드는 각 노드를 라운드 로빈 방식으로 폴링한다.
  • 마스터 노드는 각 노드에게 차례로 최대로 보낼 수 있는 프레임 수에 대한 정보를 지닌 메시지를 전송한다.

 

장점

• 충돌뿐만 아니라 랜덤 접속 프로토콜의 단점인 빈 슬롯을 제거함으로써 훨씬 높은 효율을 제공한다.

 

단점

• 폴링 지연(노드가 전송할 수 있음을 알리는 데 걸리는 시간)
  • 한 노드만 활성이면 활성 노드가 프레임을 최대 개수만큼 보낼 때마다 마스터 노드는 비활성 노드들을 차례로 폴링해야 하므로, 활성 노드는 Rbps 보다 작은 전송률로 전송하게 된다.
• 마스터 노드가  고장 나면 전체 채널이 동작하지 못하게 된다는 것

 

토큰 전달 프로토콜(token-passing protocol)

• 마스터 노드가 없고, 토큰(token)이라고 알려진 작은 특수 목적 프레임이 정해진 순서대로 노드 간에 전달된다.
• 노드가 토큰을 수신하면, 전송할 프레임일 있을 때만 토큰을 붙잡는다. 그렇지 않으면 토큰을 즉시 다음 노드로 전송한다.

단점

• 노드 하나가 실패하면 전체 채널이 동작하지 않는다.
• 또는 노드가 잘못해서 토큰을 놓아주지 않으면, 토큰이 다시 돌 수 있도록 하는 회복 절차가 실행되어야만 한다.

 

---

6.3.4 DOCSIS: 케이블 인터넷 접속을 위한 링크 계층 프로토콜

케이블 접속망은 채널 분할 프로토콜, 랜덤 접속 프로토콜, 순번 프로토콜의 세 종류 다중 접속 프로토콜 각각에 대한 것을 보여주기 때문에 아주 훌륭한 사례가 될 수 있다.

 

• DOCSIS는 하향 및 상향망 세그먼트들을 다수의 주파수 채널로 나누기 위해 FDM을 사용한다.
• 상향 및 하향 채널은 브로드캐스트 채널이다.
• 하향 채널은 다중 접속 문제 발생 X
  • CMTS에 의해 하향 채널로 전송된 프레임은 그 채널을 통해 수신하는 모든 케이블 모뎀에 의해 수신된다(그러나 하향 채널로 전송하는 CMTS가 한뿐이기 때문에 다중 접속 문제는 발생하지 않는다.)
• 상향 채널은 다중 접속 문제 발생 O
  • 다수의 케이블 모뎀이 CMTS로의 동일한 상향 채널(주파수)을 공유하고 따라서 충돌이 발생할 수 있다.
  • 상향 채널은 시간 간격(TDM처럼)으로 나뉘어져 있고, 각 시간 간격은 케이블 모뎀이 CMTS로 전송할 수 있는 일련의 미니 슬롯들로 구성되어 있다.
  • CMTS는 개별 케이블 모뎀이 특정 미니 슬롯에 전송할 수 있도록 허락한다.

• CMTS는 하향 채널상으로 MAP 메시지로 알려진 제어 메시지를 보냄으로써 어떤 케이블 모뎀(전송할 데이터가 있는)이 MAP 메시지에서 명시한 시간 간격 동안 어떤 미니 슬롯으로 전송할 수 있는지 알려준다.
  • 미니 슬롯이 케이블 모뎀마다 명시적으로 할당되기 때문에 CMTS는 미니 슬롯 동안은 충돌이 발생하지 않는 것을 확신할 수 있다.
• 그러면 CMTS는 어떤 케이블 모뎀이 전송할 데이터가 있는지 어떻게 알 수 있을까?
  • 케이블 모뎀이 이 용도로 할당된 특정 미니 슬롯들을 사용해서 미니 슬롯(mini-slot-request) 요청 프레임을 CMTS에게 전송함으로써 가능해진다.
  • 케이블 모뎀은 상향 채널의 사용 여부에 대한 감지나 충돌 검출을 수행하지 않는다.
  • 케이블 모뎀은 요청된 할당에 대한 응답을 다음 하향 제어 메시지에서 수신하지 못하면 미니 슬롯 요청 프레임 충도리됐다고 추정한다.

 

충돌이 발생한 것으로 추정한 케이블 모뎀은 미니 슬롯 요청 프레임의 재전송을 지연시키기 위해 이진 지수적 백오프를 사용한다.

• 상향 채널에 트래픽이 거의 없는 경우, 케이블 모뎀은 미니 슬롯 요청 프레임을 위해 할당된 슬롯에 데이터 프레임을 전송할 수도 있다.(미니 슬롯 할당을 기다리지 않아도 된다.)

 

따라서 케이블 접속망은 FDM, TDM, 랜덤 접속, 그리고 하나의 망에 시간 슬롯을 중앙에서 할당하는 것등이 모든 다중 접속 프로토콜들을 사용하는 아주 좋은 예이다.