링크 계층 소개

링크 계층 소개

• 노드(node)
  • 링크 계층(2계층) 프로토콜을 실행하는 장치
  • 호스트, 라우터, 스위치, 와이파이 AP(access point) 등
• 링크(link)
  • 통신 경로상의 인접한 노드들을 연결하는 통신 채널
  • 데이터그램을 출발지 호스트에서 목적지 호스트로 이동시키기 위해서는 데이터그램을 종단 간 경로의 개별 링크로 이동시켜야 함

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

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

• 프레임화(framing)
  • 거의 모든 링크 계층 프로토콜은 네트워크 계층 데이터그램을 링크상으로 전송하기 전에 링크 계층 프레임에 캡슐화 한다.
• 링크 접속(link access)
  • 매체 접속 제어(medium access control, MAC) 프로토콜은 링크상으로 프레임을 전송하는 규칙을 명시한다.
  • 단일 송신자, 단일 수신자가 있는 점대점 링크의 경우 MAC 프로토콜을 단순하다.
    • 송신자는 링크가 사용되지 않을 때마다 프레임을 전송할 수 있다.
  • 하나의 브로드 캐스트 링크를 여러 노드가 공유하는 경우
    • MAC 프로토콜은 여러 노드로부터의 프레임 전송을 조정한다.
• 신뢰적 전달
  • 링크 계층이 신뢰적 전달 서비스를 제공하는 경우 링크 계층 데이터그램은 링크상에서 오류 없이 전달된다.
  • 링크 계층의 신뢰적 전달 서비스는 확인응답과 재전송을 통해 가능해진다.
  • 무선 링크처럼 오류율이 높은 링크에서 주로 사용한다.
    • 애플리케이션, 트랜스포트 계층이 데이터를 종단 간에 재전송하는 방식을 사용하는 것과 달리 오류가 발생한 링크에서 오류를 정정한다.
  • 대다수 유선 링크 계층 프로토콜은 신뢰적 서비스를 제공하지 않음
    • 낮은 오류율을 가지고 있기 때문에, 불필요한 오버헤드가 발생할 수 있다.
• 오류 검출과 정정
  • 오류 검출은 송신 노드에서 프레임에 오류 검출 비트를 설정하게 하고 수신 노드에서 오류 검사를 수행하게 함으로써 가능해진다.
  • 링크 계층에서의 오류 검출은 일반적으로 더 복잡하며, 하드웨어로 구현된다.
  • 오류 정정은 프레임 안의 오류 검출뿐만 아니라 프레임의 어느 곳에서 오류가 발생했는지 정확하게 찾아낼수 있다.

링크 계층이 구현되는 위치

대부분의 경우 링크 계층은 네트워크 인터페이스 컨트롤러(network interface controller, NIC)로 알려진 네트워크 어댑터(network adapter)에 구현된다.

 

트워크 어댑터의 중심에는 링크 계층 컨트롤러가 있으며, 프레임화, 링크 접속, 오류 검출등의 서비스가 구현되어 있다.

송신측 컨트롤러는 데이터그램을 링크 계층 프레임으로 캡슐화 후 통신 링크 상으로 전송한다.

수신측 컨트롤러는 프레임을 수신한 후 네트워크 계층 데이터그램을 추출한다.

 

오류 검출의 경우 송신측 컨트롤러는 프레임 헤더의 오류 검출 비트를 설정하고 수신측 컨트롤러는 오류 검출을 수행한다.

 

일부 링크 계층의 기능은 호스트의 CPU에서 실행되는 소프트웨어에 구현되어 있다.

• 링크 계층 주소 정보 조립
• 컨트롤러 하드웨어의 활성화

다중 접속 링크와 프로토콜

두 종류의 네트워크 링크

• 점대점 링크(point-to-point link)
  • 링크의 한쪽 끝에 한 송신자와 링크의 다른 쪽 끝에 한 수신자가 있다.
• 브로드캐스트 링크(broadcast link)
  • 동일한 하나의 공유된 브로드캐스트 채널에 다수의 송신 노드 및 수신 노드가 연결된다.
  • 한 노드가 프레임을 전송하면 채널이 그 프레임을 브로드캐스트해서 다른 모든 노드가 그 프레임의 복사본을 수신한다.

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

 

2개 이상의 노드가 동시에 프레임을 전송하면, 모든 노드는 동시에 여러 개의 프레임을 받게 된다. 즉, 전송된 프레임들이 각 수신자에서 충돌(collide)한다.

• 수신 노드는 전송된 프레임의 의미를 파악할 수 없게 된다.
• 충돌에 관련된 모든 프레임은 손실되며, 브로드캐스트 채널은 충돌 기간만큼 낭비된다.

충돌 문제를 해결하기 위한 여러 종류의 다중 접속 프로토콜이 존재한다.

다중 접속 프로토콜의 분류

• 채널 분할 프로토콜(channel partitioning protocol)
• 랜덤 접속 프로토콜(random access protocol)
• 순번 프로토콜(taking-turns protocol)

채널 분할 프로토콜

• 시분할 다중화(time-division multiplexing, TDM)
  • 채널이 N개의 노드를 지원하고, R bps의 전송률을 가진다고 가정한다.
  • TDM은 시간을 시간 프레임(time frame)으로 나누고, 각 시간 프레임을 N개의 시간 슬롯(time slot)으로 나눈다.
  • 각각의 슬롯은 N개의 노드에게 할당된다.
  • 단점
    • 전송할 패킷이 있는 노드가 단 하나여도 R/N bps의 전송률을 가짐
    • 노드가 전송 순서상의 자신의 차례를 기다려야 한다.
• 주파수 분할 다중화(frequency-division multiplexing)
  • R bps의 채널을 다른 주파수로 나눠서 각 주파수를 N개 노드 중 하나로 할당한다.
  • 시분할 다중화와 같은 단점을 가진다.

시분할 다중화와 주파수 분할 다중화는 충돌을 피하고 N개 노드에게 대역폭을 균등하게 분할한다는 장점이 있다.

• 코드 분할 다중 접속(code division multiple access, CDMA)
  • 다른 코드를 각 노드에게 할당한다.
  • 노드는 전송하는 데이터 비트들을 자신의 유일한 코드로 인코딩한다.

랜덤 접속 프로토콜

• 전송 노드는 항상 채널의 최다 전송률인 R bps로 전송한다.
• 충돌이 생기면 충돌과 관련된 각 노드는 프레임(패킷)이 충돌 없이 전송될 때 까지 자신의 프레임을 계속해서 재전송한다.
• 프레임을 재전송하기 전에 랜덤 지연 시간 동안 기다린다.(즉시 재전송하지 않음)
  • 충돌과 관련된 각 노드는 자신만의 랜덤 지연 시간을 선택한다.

슬롯 알로하

슬롯 알로하가 다음과 같이 동작한다고 가정

• 모든 프레임의 사이즈가 같다
• 동일한 크기의 슬롯으로 시간이 분할되어 있음
• 노드는 슬롯의 시작점에서만 프레임을 전송한다.
• 각 노드는 언제 슬롯이 시작되는지 알 수 있게 동기화 되어 있다.
• 만약 2개 이상의 프레임이 충돌하면, 모든 노드는 충돌 상황을 알게 된다.

슬롯 알로하의 동작

• 노드는 전송할 새 프레임이 있다면 다음 슬롯에 프레임을 전송한다.
• 충돌이 발생하지 않으면 노드는 프레임의 전송을 성공했으므로 프레임을 재전송하지 않음
• 충돌이 발생했다면 노드는 프레임이 충돌 없이 전송될 때까지 확률 p로 해당 프레임을 다음 슬롯들에서 재전송한다.

슬롯 알로하의 장점과 단점

• 장점
  • 채널 분할과 달리 하나의 활성 노드가 채널의 최다 전송률인 R bps로 계속해서 프레임을 전송할 수 있도록 한다.
  • 각 노드가 충돌을 감지하고 언제 재전송할지 각자 결정하므로 상당히 분산되어 있다.
• 단점
  • 활성 노드가 많으면 충돌이 발생해서 슬롯이 낭비된다.
  • 모든 활성 노드가 확률적인 전송 정책 때문에 전송을 억제하는 경우 일부 슬롯이 빈다.

슬롯 알로하의 효율성

• 수식을 이용해 계산해보면 최대의 효율성은 약 0.37정도가 된다. 즉 채널의 실제 전송률은 R bps가 아닌 0.37R bps 정도가 된다.

순수 알로하

• 단순하며 동기화가 되어 있지 않음
  • 프레임이 도착하면 노드는 즉시 그 프레임 전체를 브로드캐스트 채널로 전송한다.
• 동기화 되어 있지 않기 때문에 충돌 확률이 증가함
• 순수 알로하의 효울성은 슬롯 알로하의 절반정도다.

CSMA

슬롯 알로하와 순수 알로하의 노드의 특징

• 노드의 전송 여부는 브로드캐스트 채널에 접속되어 있는 다른 노드의 활성 여부와 무관하다.
• 노드가 전송을 시작하면 다른 노드의 전송 여부는 주의하지 않을 뿐더러, 다른 노드가 자신의 전송을 간섭하는 경우에도 전송을 중지하지 않음

CSMA(carrier sense multiple access)와 CSMA/CD(CSMA with collision detection) 프로토콜에 포함되는 규칙

• 말하기 전에 듣는다
  • 노드는 전송을 하기 전에 채널을 듣는다.
    • 캐리어 감지(carrier sensing) 이라고 함
  • 다른 노드가 프레임을 채널로 전송하고 있을 때, 노드가 임의의 짧은 시간 동안 전송 중단을 감지하면 프레임을 전송하기 시작한다.
• 다른 사람이 동시에 말하기 시작하면 말을 중단한다.
  • 충돌 검출(collision detection) 이라고 한다.
  • 다른 노드가 방해 프레임을 전송하고 있음을 검출하면, 자신의 전송을 중단하고 랜덤 시간 동안 기다린 후 프레임을 전송한다

CSMA에서 충돌이 발생하는 경우

시각 t0에는 B는 다른 노드가 아무 전송도 하지 않으므로 프레임을 전송한다. t1 시점에 D는 B에 의해 전송되는 프레임을 감지하지 못했으므로 자신의 프레임을 전송한다. 약간의 시간이 경과한 후 D에서 B가 전송한 것과 D의 전송이 간섭을 일으킨다.

 

위 그림에서 알수 있듯이 채널 전파 지연(channel propagation delay, 신호가 채널의 한쪽 끝에서 다른 쪽 끝으로 전파되는데 걸리는 시간)이 CMSA의 성능을 결정하는데 중요한 역할을 하는것을 알 수 있다.

 

위 그림에서는 충돌이 발생했음에도 프레임을 계속 전송한다. 노드가 충돌 검출을 수행했을 때 충돌이 검출되면 자신의 전송을 중지한다.

CSMA/CD

CSMA의 그림과 다르게 충돌이 발생하면 바로 자신의 전송을 중단한다.

 

CSMA/CD의 동작

1. 이더넷은 네트워크 계층으로부터 데이터그램을 받고 프레임으로 만든다.
2. 만약 이더넷이 채널을 감지했을 때
   • 유휴(idle) 상태이면 프레임을 전송한다.
   • 바쁜(busy) 상태이면 채널이 유휴 상태일 때 까지 기다렸다가 프레임을 전송한다.
3. 만약 충돌없이 모든 프레임을 전송했으면 완료
4. 만약 전송중 다른 노드의 프레임 전송이 감지되면 자신의 프레임 전송을 취소한다.
5. 노드가 전송을 취소했으면 임의의 시간만큼 기다린 후 2단계로 돌아간다.

임의의 시간을 기다릴 때 이진 지수적 백오프(binary exponential backoff) 알고리즘을 사용하면 효율적이다.

이진 지수적 백오프 알고리즘

• 충돌을 n번 경험한 프레임을 전송할 때 노드는 [0,1,2,...,2^n-1] 에서 랜덤하게 K값을 선택한다.
• 이더넷의 경우 노드가 실제로 기다리는 시간은 K*512비트 시간이 되며 n의 최대값은 10으로 제한된다.

이진 지수적 백오프 알고리즘 예시

• 노드가 프레임을 전송 할 때 충돌을 감지했다.
• 어댑터는 확률 0.5로 K = 0 또는 k = 1을 선택한다.
• k = 0이면 바로 채널을 감지한다. k = 1이면 512비트 시간동안 기다린다.
• 두 번째 충돌 후, 같은 확률로 [0, 1, 2, 3] 에서 k를 선택한다.
• 세 번째 충돌 후, 같은 확률로 [0, 1, 2, 3, 4, 5, 6, 7] 에서 k를 선택한다.
• n 번째 충돌 후, [0, 1, 2, 3, ... , 2^n - 1]에서 k를 선택한다.

순번 프로토콜

• 폴링 프로토콜(polling protocol)
  • 노드중 하나를 마스터 노드로 지정한다.
  • 마스터 노드는 각 노드를 라운드 로빈 방식으로 폴링한다.
  • 작동 방식
    • 마스터 노드가 한 노드에게 최대로 보낼 수 있는 프레임 수에 대한 정보를 지닌 메시지를 전송한다.
    • 한 노드가 메시지를 모두 전송한다.
    • 마스터 노드는 다음 노드에 대해서 같은 과정을 반복한다.
  • 장단점
    • 장점
      • 충돌을 해결한다.
      • 빈 슬롯을 제거함으로써 높은 효율을 제공한다.
    • 단점
      • 폴링 지연이 발생한다. 활성 노드 뿐만 아니라 비활성 노드에도 폴링을 한다.(라운드 로빈이므로)
      • 마스터 노드가 고장나면 전체 채널이 동작하지 않음
• 토큰 전달 프로토콜(token-passing protocol)
  • 토큰(token)이라고 하는 작은 특수 목적 프레임이 정해진 순서대로 노드간에 전달된다.
  • 토큰은 노드1 -> 노드2 -> 노드N -> 노드1 이런 형태로 전달됨
  • 토큰을 전달 받았을 때 프레임이 없으면 토큰을 다음 노드로 전달한다. 프레임이 있으면 프레임을 전송한 후 토큰을 다음 노드로 전달함
  • 장단점
    • 장점
      • 분산 방식이며 효율이 높음
    • 단점
      • 노드 하나가 실패하면 전체 채널이 동작하지 않음
      • 노드가 토큰을 놓아주지 않으면 토큰이 다시 돌 수 있도록 하는 회복 절차가 실행되어야 한다.