20180506 16 : Link Layer

링크레이어 개요

우리가 알고 있는 호스트와 호스트간의 통신, 클라이언트와 서버사이의 통신들을 프로토콜 스택으로 이해하고 있다. 그리고 애플리케이션 데이터가 프로토콜 스택을 쭉 타고 내려가면서 트랜스포트 레이어, 네트워크 레이어, 링크 레이어를 통과한다.

패킷이 목적지까지 도달하기 위해서 패킷을 어디에 보내야 하는가? 네트워크 환경에 들어가면 기본 게이트웨이 라우터가 있다. 무조건 패킷은 게이트웨이 라우터로 전달해주어야 한다. 여기서 패킷이 게이트웨이 라우터에게 보내는 것이 사실, 개념화 되어있지만 그 과정에서 링크 레이어를 알아야 한다.

내가 게이트웨이 라우터에게 하고자 하는 이야기가 모든 사람들에게 들린다. 이러한 상황에서 두 명 이상이 동시에 이야기를 한다면 혼선이 발생한다. 그리고 이것을 collision 이라고 부르며 신호가 섞이게 되고 해독하지 못하는 시그널이 들어와 채널이 낭비되는 현상이 발생한다. 결국 핵심은 많은 사람들이 공유하는 매체를 통해서 메세지를 전달하기 때문에 충돌이 발생하지 않아야 메세지가 도달함을 알 수 있다.

링크레이어 역할

따라서 링크 레이어에서 하는 가장 중요한 일은 collision 이 발생하지 않도록 혹은 충돌이 발생하더라도 해결할 수 있도록 하는 것이 링크 레이어가 하는 역할이다.

소개

링크레이어는 하나의 홉에 대한 이야기이다. 여기서 홉(hop)은 네트워크의 용어로서, 출발지와 목적지 사이에 위차한 경로의 한 부분이다. 데이터 패킷은 브리지, 라우터, 게이트웨이를 거치면서 출발지에서 목적지로 경유한다. 패킷이 다음 네트워크 장비로 이동할 때마다 홉이 하나 발생한다. 홉 카운트(hop Count)는 데이터가 출발지와 목적지 사이에서 통과해야 하는 중간 장치들의 개수를 가리킨다.

하나의 홉이 다른 홉으로 넘어갈 때 충돌하지 않고 어떻게 넘어갈 것인가는 링크 레이어의 이야기이다. 그리고 우리가 엔드 유저의 관점에서 첫 홉, 링크 레이어의 기술들은 유선 이더넷 케이블인 경우가 있고, 와이파이가 있을 것이며 결국 무선이든 유선이든 와이파이든 LTE든 브로드캐스트 미디엄이다. 공유하는 매체이고 어떻게 충돌하지 않고 사용할 것인가에 대한 이야기이다. 

링크 레이어는 어디에 구현되어 있는가?

트랜스포트 레이어와 네트워크 레이어는 OS 에 구현되어 있다. 소프트웨어로 (코드) 로 구현되어 있고 링크 레이어는 Network Interface Card로 구현되어 있다. 네트워크 레이어에서 내려온 IP 패킷이 네트워크 인터페이스 카드로 전달이 되고, 네트워크 인터페이스 카드에서 외부로 나가는데 데이터 전송 단위인 프레임에 IP 패킷이 들어가서 전달된다.

호스트와 호스트 사이의 링크가 전용선이었다면 데이터를 보내는 것에 충돌을 신경쓰지 않아도 된다. 하지만 전용선이 있는 경우가 매우 드물며, 많은 사람들이 공유하는 채널을 가진 링크를 많은 사람들이 사용한다. 따라서 어느 한 사람이 패킷을 보내면 해당 시그널이 전체 링크로 브로드캐스트되어 collision 이 발생하는 것이다. 다 퍼지기 때문에 해당 매체를 "broadcast medium" 이라고 부른다. 

따라서 여러 명이 말하면 혼선이 발생되서 Medium 이라는 것, 매체에 접근할 때 Medium Acess 조절해서, 충돌을 해결하고자 하는 것을 Medium Access Control 이라 부르며 이를 앞글자만 따서 말한 것이 MAC 이다. 링크레이어에서 이야기 하는 MAC Address 는 모두 이 Medium Access Control 을 이야기 하는 것이고, 어떻게 하면 Medium Access 에 대한 컨트롤을 잘해서 충돌을 할 것인가에 대한 이야기인 것이다. 따라서 MAC 이라고 한다면 충돌에 대한 해결책이라고 보면 된다.

Wifi 는 MAC Protocol 인 것이다. Wifi 를 통해서 같은 매체를 공유하지만 충돌을 잘 해결하기 때문에 아무런 혼선 없이 데이터를 송수신할 수 있는 것이다. 

MAC Protocol

이상적으로 원하는 MAC 프로토콜은 어떤 것인지 생각해보자.

만약의 링크의 채널 대역폭(bandwidth)이 R bps 인 경우, 

(1) 하나의 노드가 데이터를 전송하고자 할 때, R을 전체 사용하여야 한다.

(2) m 개의 노드가 데이터를 전송하고자 할 때, R/m 으로 해당 대역폭을 사용할 수 있어야 한다.

(3) (1)과 (2)가 가능하되, 분산처리가 되었으면 좋겠으며 프로토콜 자체가 단순하였으면 좋겠다.

이러한 이상적인 프로토콜을 만족시키기 위해서 많은 맥 프로토콜이 제안되어왔다. 그리고 이런 맥 프로토콜들은 세 개의 방식으로 나뉘어 설명할 수 있다.

• channel partitioning
  

• random access : CSMA/CD

• taking turns

Channel Partitioning
TDMA 방식 (Time division multiple access), 시간을 쪼개서 많은 사람들이 액세스할 수 있도록 하는 것이다. 예를 들면 유저1은 번째 슬롯에서만 전송이 가능하다. (자기 차례가 왔을 때만 전송할 수 있도록 : 시간적 배분) 하지만 자원이 낭비되는 문제가 발생한다. 예를 들어 유저 1만 있는 경우 나머지는 낭비된다. 

FDMA 방식 (Frequency division multiple access), 각자 자기 자신의 데이터를 보낼 수 있는 주파수가 정해져 있어서 해당 주파수를 통해서 보내며 TDMA와 같은 장단점이 존재한다.

Random Access Protocols

자기가 보내고 싶을 때 보내자. 

TDMA와 FDMA 방식은 아무때나 액세스할 수 있지 않기 때문에 비효율적이라는 판단, 랜덤 액세스 방식은 보내고자 하는 데이터가 생기는 경우 보내겠다라는 방식이며 이러한 방식을 이용하면 충돌이 발생한다. 결국 랜덤 액세스 방식은 충돌이 발생했을 때 어떻게 해결하고 그것을 미연에 어떻게 알아차릴 수 있는가 문제가 제기된다.

ALOHA 라는 방식은 Random Access Protocols 방식에 가장 최초에 나온 프로토콜이다. 그리고 알로하라는 프로토콜은 단점이 많이 발생해서 이를 개선한 것이 CSMA 이다.

CSMA(Carrier Sense Multiple Access)
매체에 보내기 이전에 Listen을 하고 보낸다. listen before transmit 이다. 여기서 아무리 listen before transmit 을 하더라도 이후에 다시 충돌이 발생할 수 있다. (이야기를 다 듣기 전까지 기다리고 있다가 이야기가 끝난 뒤 다시 두 곳에서 동시에 말을 한 경우 혼선이 발생한다) 충돌은 항상 발생한다. 

다시 이야기 하자.

아날로그한 시간으로 따지고 들어가면 동시라는 개념보다 상대적으로 누군가는 더 빨랐을 것이다. 충돌이 발생한 이유는 빛의 속도라고 하더라도 propagation delay 가 발생하기 때문에 충돌이 발생하는 것이다. 결국 propagation delay 를 zero 로 만들면 충돌이 발생하지 않을 것이다. 하지만 propagation delay 는 zero 로 만들 수 없고, 충돌이 나는 것은 불가피하다. 아무리 listen before transmit 이라고 하더라도 말이다. 결국 충돌은 불가피하다. 충돌이 나도 프레임 전송을 해버린 상황이다. 현실 세계로 넘어가면 두 사람이 동시에 이야기를 멈추고 상대방에게 이야기할 시간을 준다. "먼저 이야기 하라는 둥의 ~ " 왜냐하면 충돌나버리면 모든 프레임이 노이즈가 되어버리고, 매체가 낭비되기 때문에 멈추고 새로운 transmission 을 하는 것이 좋다. 그리고 이를 개선한 것이 CSMA/CD 이다.

CSMA/CD (collision detection)

listen before transmit 을 실시하는데, 충돌이 나면 충돌을 감지하고 바로 전송을 멈추는 것이다. 내가 이야기하는데, 다른 사람이 이야기 한다면 충돌을 감지하고 이야기를 멈추어 버린다. 일반적인 CSMA 는 충돌을 감지하더라도 계속 프레임을 전송하는 것에 반해서 CSMA/CD 는 충돌을 감지하면 전송을 멈춘다. 그 이후에 어떻게 할 것인가?

누군가 중재를 해주어야 한다. CSMA/CD 는 어떻게 행동하라고 명시해놓았다. 충돌을 감지했을 때, 멈추고 난뒤 어떻게 행동할 것인가를 말하고 있다. binary (exponential) backoff : 이야기를 하려고 했는데 충돌이 발생한 경우, 한 발 물러서서 이야기를 멈추지만 얼마만큼 물러설 것인가를 결정해야 한다. 개념적으로 이야기한다면 { 0, 1, 2, 4, ..., 2^m-1 } 시간 단위가 있다고 생각하자. n 번의 충돌이 있었다면 해당 { } 내부의 숫자중에 하나를 선택해서 기다린다는 것이고 이것이 binary exponential backff 의 핵심이다.

충돌 횟수가 늘어나면 늘어날수록 선택하는 랜덤 숫자의 범위가 늘어나며, 이것이 binary exponential backoff 의 핵심이다. 충돌이 계속 일어남에 따라서 더 오래 기다리는 확률이 더 커진다. 왜 이렇게 했는가?

충돌이 일어났다는 건 채널에 다른 프레임이 전송되었음을 알 수 있으며 처음엔 낙관적이기에 범위가 작았다면 이후에 충돌이 여러번 발생하면 범위를 늘리는 것이다. 결국 충돌이 났을 때 backoff 한다는 것은 특정 시간 만큼 backoff 한다는 것이고 이는 결국 delay 이다. backoff 가 커지면 커질수록 delay 가 커지며 비례 관계에 있다. (동일한 의미) 사람들이 많은 경우 결국, backoff 가 늘어나기 때문에 시간이 지연되고 느려지는 것이다.

Channel Partitioning vs Random Access 

Channel Partitioning 은 사람이 많을수록 유리하다. 채널을 균일하게 분배해서 사용하기 때문이다. 반면에 Random Access 는 사용자가 적은 경우 효율적이지만 사람이 많은 경우는 backoff 가 늘어나기 때문에 불리하다.

"Taking Turns" MAC Protocols

- polling

- token passing

중앙서버는 필요없지만 토큰이라는 컨트롤 메세지가 존재한다. 해당 토큰을 가지고 있는 호스트많이 데이터를 전송할 수 있는 개념. 만약 토큰을 가지더라도 전송을 데이터가 없으면 토큰을 넘기며, 전송할 데이터가 있으면 데이터를 전송한다. 이 과정을 반복한다. 하지만 토큰을 잃어버린 경우에는? 문제가 발생한다.

패킷 전송하는 방식(패킷 스위칭) 이더넷에서 CSMA/CD 방식을 이용한다. 하지만 Wifi 에서 사용하는 맥 프로토콜은 무선 채널의 특성 때문에 다른 것을 이용한다고 한다.

정리 )

• 데이터 링크 레이어의 데이터 단위는 무엇인가

• 네트워크 레이어에서 패킷이 출발지에서 목적지까지 도달하는 경우 어디로 처음 보내야 하는가?

• 기본 게이트웨이에서 프레임 혼선 문제, collision 설명하기

• 링크 레이어가 해야하는 주요 역할은 무엇인가

• 홉(hop)이란 무엇인가

• 링크 레이어는 어디에 구현되어 있는가

• Medium Access Control 은 무엇인가

• Mac Protocol 의 세가지 방식

• Channel Partitioning

• Random Access

• Taking Turns

• CSMA/CD 란 무엇인가
• binary (exponential) backoff 란 무엇인가
• backoff 와 delay 간의 상관성