링크 계층(1) _ MAC, CSMA, CSMA/CD

 Link layer 

• application layer
  • 소켓과 소켓 사이의 메시지 전송
  • 사용자 프로그램
• transport layer
  • 신뢰성있는 데이터 전송
  • 운영체제 내부 소프트웨어(코드)로 구현
• network layer
  • 패킷 전송 경로
  • 운영체제 내부 소프트웨어(코드)로 구현
• link layer
  • 전송한 패킷을 어떻게 다음 라우터까지 잘 전달 할까
  • 네트워크 인터페이스 카드 그리고 일부 운영체제에 구현, 팜웨어로 구현
• 패킷을 첫 홉(게이트웨이 라우터)에 전달 할 때 충돌(collison)을 발생시키지 않거나 혹은 충돌이 발생했을 때 그것을 해결하는 일을 하는 곳이 Link layer이다.

패킷을 보내면 전자기파로 나가게 되고, 전자기파끼리 만나게 되면 noise가 된다. 한 순간에 한 개 이상의 패킷이 만나게 될 경우 충돌이 발생하게 되고, noise가 되는 것이다. 대화할 때 옆 사람도 대화를 하게 되면 음성이 겹치게 되어 잘 안들리는 것과 상황이 같다. 게이트웨이 라우터 입장에서는 noise를 듣게 되는 것이다. 따라서 신호를 전달하는 매체 Medium에서는 하나 이상의 송신자가 발신하는 경우 collision이 발생하기 때문에 이것을 제어하는 기술이 필요하다.

---

 Multiple access links, protocols 

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

1️⃣ point-to-point

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

2️⃣ broadcast (shared wire or medium)

• 대부분의 데이터 링크는 많은 사람들이 공유하는 채널을 가진 공용 링크를 사용한다.
• 어느 한 곳에서 패킷을 보내면 그 시그널이 채널 전체로 퍼지게 되는데(broadcast), 이러한 매체(medium)을 Broadcast Medium이라고 한다.
• 따라서 이 매체에 무언가를 싣기 위해 접근할 때 조절을 통해 충돌을 해결하는 과정을 Media Access Control이라고 하며, MAC 프로토콜이라고도 한다.
• 즉, MAC 프로토콜이란 패킷을 정확하게 원하는 곳으로 전달하도록 하는 데이터 링크 계층의 프로토콜이다.

---

 An ideal multiple access protocol 

• 한 노드가 데이터를 전송하고 싶을 때는 R Bandwidth를 온전히 사용할 수 있어야 한다.
• M개의 노드가 데이터를 전송하고 싶을 때 R/M 씩의 Bandwidth를 사용할 수 있어야 한다.
• 중앙 컨트롤러가 있는 것이 아니라 분산 처리되어서 동작할 수 있어야한다.
• 단순해야한다.

이 이상적인 조건을 목표로 MAC 프로토콜들을 동작하게끔 한다. ( 이상을 향해~! )

---

 MAC protocols: taxonomy 

 channel partitioning 

1️⃣ TDMA

• time division multiple access
• 각 노드별로 자기 자신이 전송할 수 있는 시간(time slots)을 할당하여 자신의 time slots가 돌아왔을 때만 사용할 수 있게 한다.
• 공유 자원을 시간적으로 분배하여 충돌을 나지않게 하는 것
• 자원 낭비의 문제점이 있다.
  • 연결되어 있으나 전송을 하지 않는 노드가 있을 경우
  • 연결된 노드가 1개만 있을 경우

 

2️⃣ FDMA

• frequency division multiple access
• 각 노드마다 주파수를 나눠서 해당 주파수로만 데이터를 보내도록 한다.
• TDMA와 같은 자원 낭비의 문제점이 있다.

⇒ 시간 혹은 주파수를 통해 Access 권한을 나눠가진다.

⇒ 자원이 낭비 될 수도 있다는 단점이 있다.

---

 random access 

• TDMA, FDMA는 각자 정해진 시점에서만 데이터를 보낼 수 있어 비효율적이게 되는데 random access protocol은 보내고 싶을 때 보낼 수 있다.
• 노드가 전송하고자 하는 패킷을 가지고 있을 때, 전체 채널 데이터 속도인 R로 전송할 수 있으며 노드 간의 우선순위는 존재하지 않는다.
• 그러나 필연적으로 충돌(Collision)이 발생할 수 밖에 없기 때문에 random access protocol을 사용할려면 충돌 감지와 충돌 복구에 관한 방법을 명시해야한다.

 

1️⃣ CSMA

• carrier sense multiple access
• listen before transmit
• 말하기 전에 이미 매체를 사용하고 있는 노드가 있는지 확인하는 방식이다.
• 누군가 얘기하고 있다면 listen하고 끝날 때까지 기다렸다가 조용해지만 말한다.

 

⚠️ 충돌 발생 원인 : Propagation Delay

• Propagation Delay(전파 지연)때문에 CSMA는 여전히 충돌 가능성을 가지고 있다.
• 프레임이 전송(전파)되는 시간차 때문에 매체가 조용한 것을 감지하고 나서 프레임을 전송하더라도(t0), 다른 곳에서 보낸 프레임이 뒤늦게 도착하여(t1) 두 프레임이 충돌하는 것이다.
• 전파지연을 아예 없애면 충돌 지연을 해결할 수 있지만, 전파지연은 빛의 속도와 관련된 광섬유의 문제이기 때문에 해결하기 어렵다.

 

2️⃣ CSMA/CD (Collision Detection)

• CSMA에서 충돌은 피할 수 없으므로 충돌이 발생하면 이를 감지하고 잠시 멈추는 방식이다.
• 잠시 멈춘 후 재전송 할 때 Binary back off 방법을 사용한다.

✨ Ethernet CSMA/CD algorithm

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

✨ Binary Back off

• M번째 충돌 이후, NIC는 {0, 1, 2, ... 2^M-1} 중에서 랜덤으로 숫자 K를 선택한다.
• NIC는 K * 512bit 만큼의 시간 동안 기다리고 2번 단계로 되돌아간다.

❓왜 충돌이 처음(혹은 적게) 발생하면 얼마 안기다리고 많이 발생하면 오래 기다려야할까?

❗충돌이 났다는 것은 지금 나 말고도 프레임을 전송한 사람이 있다는 것은 확신할 수 있으나 지금 얘기하는 사람이 몇 명인지 모른다. 충돌이 적게 일어났다면 말하는 사람이 적다는 것이므로 오래 기다릴 필요가 없다. 그러나 충돌이 많이 났다는 것은 말하는 사람이 많다는 것이다. 랜덤 숫자의 범위를 작게해버리면 또 충돌이 날 수 있기 때문에 랜덤 숫자의 범위를 넓혀서 충돌 없이 데이터가 전송되게 한다. 따라서 충돌이 많으면 오래 기다릴 수 있는 것이다.

---

 taking turns 

• 파티셔닝과 랜덤 액세스는 각자의 장점이 있다. 파티셔닝은 사용자가 많은 경우 충돌 제어를 할 필요가 없으며, 랜덤 액세스는 사용자가 적은 경우 bandwidth를 가용할 만큼 사용할 수 있다.
• 이 두 장점을 섞은 방식이 turns 방식이다.
• 이론적인 방법이고 현실적으로는 사용하지 않는다.

• centeralize 방식으로 마스터를 두어 특정 노드에게 발언 기회를 주는 방식이 있다.
• 마스터 노드 없이 토큰이라는 특정 발언권을 이용하여 발언을 제어하는 방식도 있다.
• 위 두 가지 방식은 특정 single node에서 문제가 생기면 (마스터 노드 또는 토큰 소유 송신자) 시스템 에러가 나므로 지양되고 있다.

---

✨ 이더넷과 와이파이는 압도적으로 random access를 사용하며 channel partitioning은 라디오/LTE 등의 이동통신에서 사용된다.

 

---

데이터 링크 계층 1

데이터 링크 계층 1