DataLink Layer

어플리케이션 계층에서는 소켓과 소켓 사이의 메시지 전송만을 다룬다.
전송 계층에서는 신뢰성있는 데이터 전송을 다룬다.
네트워크 계층에서는 패킷을 전송하는 경로에 대해서 다룬다.
데이터 링크 계층에서는 전송한 패킷이 어떻게 다음 게이트웨이까지 갈 것인지를 다룬다.

패킷을 생성하면 제일 먼저 게이트웨이 라우터에 전송해야한다. 이때 게이트웨이까지 가는 경로는 어떤 전용선이 있는 것이 아니라 공용선을 통해 이동한다.

또한 여러명의 사용자가 하나의 게이트웨이로 패킷을 보낼 수 있고 이때 패킷끼리의 충돌 (Collision)이 발생할 수 있다.

예를 들어서, 내가 저 멀리있는 내 친구를 부를 때, 내 목소리를 친구만 듣는 것이 아니라 내 주위에 있는 다른 사람들도 들을 수 있다. 문제는 그 사람들도 각자 얘기를 하고 있을 것이고, 내 말과 섞여서 혼잡해질 것이다. 이를 Cocktail party 효과라고 한다.

이처럼 패킷 역시 전송되는 과정에서 다른 사용자로부터의 패킷과 뒤엉켜 충돌이 발생할 수 있다.

데이터링크 계층에서는 이러한 충돌이 발생하지 않게 또는 발생했을 때 해결하는 역할을 맡는다.

전송 계층, 네트워크 계층같은 데이터링크 계층 상위 계층들은 OS 내부에 소프트웨어 즉, 코드로 구현되어있다.

데이터링크 계층은 네트워크 인터페이스 카드 즉, 하드웨어 안에 구현되어있다.

네트워크 계층에서 내려온 IP 패킷은 네트워크 인터페이스 카드로 전달된다.
이후 네트워크 인터페이스 카드에서 외부로 나갈 때 데이터링크 계층의 전송 단위인 프레임 안에 데이터 항목에 포함되서 전송된다.

Multiple access links, protocols

링크는 크게 2가지 유형이 있다.

point-to-point

데이터링크가 전용선 (Point-to-point)으로 되어있다면 데이터가 아무런 충돌 없이 전송될 수 있다. 전화 접속을 위한 PPP 또는 Ethernet switch와 host 사이의 링크가 대표적인 예시이다.

broadcast (shared wire or medium)

대부분의 데이터링크는 많은 사람들이 공유하는 채널을 가진 공용 링크를 사용한다. 따라서 어느 한 곳에서 패킷을 보내면 그 시그널이 채널 전체로 퍼지게 되는데 (Broadcast), 이러한 매체 (Medium)를 Broadcast Medium이라고 한다.

따라서 이 매체에 무언가를 싣기 위해 접근할 때 조절을 통해 충돌을 해결하는 과정을 Media Access Control이라고 하며, 앞 글자를 따서 MAC 프로토콜이라고 한다. 즉, MAC 프로토콜이란 패킷을 정확하게 원하는 곳으로 전달하도록 하는 데이터링크 계층의 프로토콜이다.

이상적인 MAC 프로토콜의 조건

구현은 힘들지만 가장 이상적인 MAC 프로토콜의 조건을 따져보자면 다음과 같다.

1. 하나의 노드가 데이터를 전송하려면 R Bandwidth를 전부 사용할 수 있어야한다.
2. M개의 노드에서 데이터를 전송하려면 각자의 노드는 R/M 씩의 Bandwidth를 사용할 수 있어야한다.
3. 중앙 컨트롤러가 있는 것이 아니라 분산 처리되서 동작할 수 있어야한다.
4. 단순해야한다.

MAC 프로토콜: taxonomy (분류)

MAC 프로토콜은 크게 3가지의 종류가 있다.

1. Channel Partitioning

• 채널을 작은 조각 (time slots, frequency, code)로 나눈다.
• 노드에게 조각을 독점적으로 할당한다.

2. Random Access

• 나눠지지 않은 채널끼리는 충돌을 허용한다.
• 충돌이 발생하면 복구한다.

3. Taking Turns

• 노드들이 교대로 동작하지만, 보낼 데이터가 많은 노드는 다른 노드보다 더 오랫동안 동작할 수 있다.

Channel partitioning MAC protocols: TDMA

TDMA : Time (Time Division Multiple Access)
시간을 쪼개서 여러 사람이 이용할 수 있도록 한다.

각 사람별로 그 사람이 접근할 수 있는 시간 (time slots)을 할당한다.
사람들은 자기만의 시간이 돌아올 때만 사용할 수 있다.

그림에서 1번 유저는 1번 slot에서만 사용할 수 있고, 3번 4번 유저도 마찬가지이다.
이렇게하면 서로 충돌을 방지할 수 있다.

하지만 사용하지 않는 time slot은 그대로 낭비된다는 단점이 있다. 그림에서도 6개의 슬롯 공간이 있지만 실제로는 1,3,4만 사용하고 2,3,5는 그대로 낭비되고있다.

Channel partitioning MAC protocols: FDMA

FDMA (Frequency Division Multiple Access)
주파수를 쪼개서 여러 사람이 이용할 수 있도록 한다.

TDMA는 시간을 쪼개서 브로드캐스트 채널을 공유하지만, FDMA는 주파수를 여러 개로 쪼개서 (frequency bands) 사용자들에게 할당한다.

사용자들은 각자 데이터를 보낼 수 있는 주파수 조각을 할당받고, 그 주파수에 한해서만 데이터를 보낼 수 있다.

이때 각 주파수는 (R / 사용자 수 N)의 대역폭을 갖는다.

FDMA역시 충돌은 발생하지 않지만 사용되지 않는 주파수 조각이 낭비된다는 단점이 있다.

Random access protocols

TDMA, FDMA는 각자 정해진 시점에서만 보낼 수 있지만 Random Access Protocol은 보내고 싶을 때 보낼 수 있다.

노드가 전송하고자하는 패킷을 가지고 있을 때, 전체 채널 데이터 속도인 R로 전송할 수 있으며 노드 간의 우선순위는 존재하지 않는다.

하지만 필연적으로 충돌 (Collision)이 발생할 수 밖에 없기 때문에 Random Access Protocol을 사용하려면 충돌 감지와 충돌 복구에 관한 방법을 명시해야한다.

CSMA (Carrier Sense Multiple Access)

데이터를 전송하기 전에 이미 매체를 사용하고 있는 노드가 있는지 확인하는 방식이다.

CSMA는 전송하기 이전에 매체에 먼저 귀를 기울일 것을 요구하고 있다.
(전송 이전에 감지, 말하기 이전에 듣기 원칙)

A, B, C 사람들 중에서 말하고있는 사람이 있으면 그 사람이 말을 끝낼 때 까지 기다렸다가 말을 하도록 한다.

따라서 채널이 사용되지 않을 때 (idle) 까지 대기하다가, 사용되지 않으면 프레임을 전송하는 방식으로 동작한다.

CSMA Collisions

하지만 CSMA는 여전히 충돌이 발생할 수 있다.

프레임이 전송 (전파)되는 시간차 (전파지연: Propagation Delay) 때문에, 매체가 idle한 것을 감지하고나서 프레임을 전송하더라도, 다른 곳에서 보낸 프레임이 뒤늦게 도착하여 두 프레임이 충돌할 수 있다.

전파지연을 아예 없애면 충돌을 해결할 수 있지만, 전파 지연은 빛의 속도와 관련된 광섬유의 문제이기 때문에 없앨 수 없다.

CSMA/CD (Collision Detection)

CSMA에서 충돌은 피할 수 없으므로 (Inevitable), 충돌이 발생하면 이를 감지하고 잠시 멈추는 방식이 바로 CSMA/CD 이다.

프레임이 목적지에 도착하는 시간 이전에 다른 프레임이 전송 중인 것을 발견하면 충돌이 일어난 것으로 판단하고 잠시 멈춘다.

잠시 멈춘 후 재전송을 할 때 Binary (Exponential) back off 라는 방법을 사용한다.

Ethernet CSMA/CD algorithm

CSMA/CD 알고리즘은 다음과 같이 동작한다.

1. NIC (네트워크 인터페이스 카드)는 네트워크 계층으로부터 데이터그램을 받고 프레임을 생성한다.
2. 만약 NIC가 채널이 idle함을 감지하면, 프레임 전송을 시작한다. 반면 채널이 혼잡함을 감지하면 idle할때까지 기다렸다가 전송한다.
3. 만약 NIC가 다른 전송을 감지하지 않은 채 모든 프레임을 전송했다면, 전송 완료다.
4. 만약 NIC가 전송 도중 다른 전송을 감지했다면, 전송을 중단하고 jam 신호를 보낸다.
5. 전송을 중단한 후, NIC는 Binary back off 상태에 들어간다.

Binary back off 상태는 다음과 같다.

• M번째 충돌 이후, NIC는 {0, 1, 2, ... 2^M-1} 중에서 랜덤으로 숫자 K를 선택한다.
• NIC는 K * 512bit 만큼의 시간 동안 기다리고 2번 단계로 되돌아간다.
• 충돌이 많으면 그만큼 더 오래 기다리게된다.
  • 충돌이 많다는 것은 그만큼 호스트가 많다는 것을 의미한다. 따라서 더 오래 기다려야 그 호스트들의 데이터가 충돌 없이 전송될 것이기 때문에, 충돌이 많을 수록 더 오래 긷라ㅣ게 된다.

따라서 CSMA/CD는 원하는 떄에 바로 데이터를 보낼 수 있는 장점이 있지만, 사람이 많아서 충돌이 많아질 경우 back off로 인해 대기 시간이 길어진다는 단점이 있다.

"Taking turns" MAC Protocols

기존의 Partitioning과 Random의 장점을 모두 융합한 방식이지만 Decentralized를 위반하기 때문에 실제로는 거의 사용되지 않는다.

하나의 마스터 노드를 두고 전송과 충돌의 중재를 담당하게 한다.
하지만 이 마스터 노드에 오류가 생길 경우 모든 전송이 멈추게된다는 치명적인 단점이 있다.

Polling

마스터 노드는 전송할 차례인 Slave 노드에 방문하여 전송할 수 있도록 한다.
이 Slave 노드들은 멍청 (dumb)하다.
하지만 이 마스터 노드가 망가지면 전체 네트워크가 멈춰버린다. (Decentralized 위반)

Token passing

Token이라는 스페셜 메시지를 사용한다. 이 토큰을 보유한 호스트만이 데이터를 전송할 수 있다. 토큰을 넘겨받았는데 보낼 데이터가 없다면 다른 노드로 넘긴다.

하지만 이 토큰 자체가 유실된다면 전체 네트워크가 멈춰버리는 치명적인 단점이 있다. 역시 Decentralized를 위반한다.