Link layer

• Link layer :
  실제로 인터넷에서의 link layer의 가장 중요한 기능은 host와 edge router를 one-hop(link)로 연결해주는 것임.
  router에 각 host들이 붙기는 힘드니까 여러 host들을 묶어서 router에 연결을 도와주는 기기가 switching hub일 뿐이다.
  application layer에서 packet을 message,
  transport layer에서 packet을 segment,
  network layer에서 packet을 datagram,
  link layer에서는 packet을 frame 이라고 부름.

Link layer services

• Link layer가 하는 일 :
  1. framing :
     link layer에서는 network layer에서 내려온 datagram을 link layer header를 붙여서 frame으로 만든다.
  2. link access :
     1 : 1로 붙으면 link access가 필요 없음.
     동시에 보내면 collsion이 일어나기 때문에 link access가 필요.
  3. reliable delivery between adjacent nodes :
     adjacent node 사이에 reliable data delivery를 한다.
     ➡️ 위 3가지 service를 하기 위해서 frame header에 새로운 address가 붙는다.
     왜냐면, transport에서 사용된 header가 그대로 data에 들어가기 때문에 IP address를 볼 수가 없다.
     그래서 link layer에서는 추가의 새로운 address가 필요하다.
     여기서 사용하는 address가 MAC address(HW address)이다.

Where is the link layer implemented?

• link layer는 어디에서 구현되고 있는가? :
  OS에서 service되고 있는 부분은 Transport, network layer까지였다.
  link layer는 network interface card와 함께 service된다.
  그래서 link layer는 pyhsical link를 무엇을 쓰는지와 하나의 set이다.
  LAN network interface module에 link layer까지 구성되어 있다.
  wifi를 쓸 때는 wifi modem에 wifi data-link(무선),
  모바일망은 smartphone 안에 있는 퀄컴칩에 구현되어 있다.

---

error detection, correction

• link layer에서는 checksum을 하지 않고, CRC(Cyclic Redundancy Check)를 한다.
  CRC는 HW적으로 다 구현되어 있기 때문에 자세히 알 필요 없음...

---

MAC(multiple access control) protocols : taxonomy

• Multiple access :
  다수가 같은 link를 multiple하게 사용하는 것. (Ethernet, wi-fi, satellite, human voice, ...)
  multiple access를 할 때, collision이 발생할 수 밖에 없는데
  collsion을 해결하기 위해 나온 protocol이 MAC(muliple access contorol) protocols이다.

• MAC(Multiple access protocol) protocols :
  그래서 link layer를 MAC layer라고도 표현한다.
  다른 layer들과는 달리, link layer에서만 제공하는 차별화된 service이다.
  MAC protocol에는 크게 3가지 종류가 이다.

  1. channel partitioning
  2. random access
  3. taking turns

1. channel partitioning

• channel partitioning :
  channel을 나눠서 = 주파수를 나눠서 사용하는 protocol.
  (TDMA, UDMA와 유사한데 TDMA, UDMA는 같은 resource를 나눠 쓰는 것이지 동시에 사용할 수 있는 것은 아니므로 차이가 있다.
  MAC protocol은 "동시"에 사용하길 원함.)

2. random access

• random access :
  random하게 access함.
  random하게 access하기 때문에 collision이 일어날 수 밖에 없다.
  그런데 correction(recovery)을 어떻게 하는지에 따라 또 여러 protocol로 나뉘어진다.
  만약 A와 B가 충돌이 나면,
  A의 random 함수의 결과만큼 delay.
  B의 random 함수의 결과만큼 delay.
  하고 나서 다시 보냄.
  • ALOHA
  • slotted ALOHA
  • CSMA, CSMA/CD, CSMA/CA

2.1. ALOHA

• pure ALOHA :
  data가 생기면 무조건 보냄.
  보낸 것에 대한 ACK를 받음.
  ACK를 못 받으면, collision임을 인지하고 다시 보냄.
  $[t_0, t_1]$에서 다른 host가 data를 보내면, collision이 발생하기 때문에 collision probability를 구할 수 있다.
  그런데 다른 host들이 data가 생기면 바로바로 보내기 때문에 collision이 발생할 확률이 높아진다.
  ➡️ collision probability를 줄이기 위해 나온 것이 slotted ALOHA이다.
  

2.2. slotted ALOHA

• slotted ALOHA :
  pure ALOHA protocol에서 collision probability를 줄이기 위해 나온 것이 slotted ALOHA이다.
  TDMA처럼 slot의 시작과 끝을 공유하는 것이 아니라,
  slot의 시작만 공유한다.
  slot의 시작을 공유하며 synchronization을 해야 하기 때문에
  clock synchronization을 맞춰야 한다.
  하지만 내부적으로 digital clock을 사용하기 때문에
  사실 clock drift가 누적되어 정교한 clock synchronization을 하기에는 쉽지 않다.

pure ALOHA와 slotted ALOHA는 내가 data를 보내기 전에, 누가 data를 보내고 있는지를 알 수가 없다.
이것이 가장 큰 문제이다.
이것을 개선하기 위해 나온 방식이 CSMA.

2.3. CSMA, CSMA/CD, CSMA/CA

• pure CSMA : Carrier Sense Multiple Access
  말 그대로 sensing을 하는 것이다.
  data를 보내기 전에 channel을 listen해서 carrier를 sensing한다.
  누가 data를 보내면, carrier가 sensing된다.
  누가 data를 보내고 있으면(channel이 busy하면),
  carrier sense가 clear할 때 까지(= channel이 idle할 때까지) 기다린다.
  
  그럼에도 불구하고 transmission delay 때문에 collision이 발생할 수도 있다.
  만약 2번째 host가 data를 보내기 시작한 동시에, 4번째 host가 carrier sense를 했다면
  2번째가 data를 보냈지만 transmission delay로 인해, 4번째 host는 channel이 idle하다고 판단하여 data를 보내는 상황이 생긴다.
  이때, 2번째 host와 4번째 host가 overlap되는 region에 collision이 발생한다.
  

• CSMA/CD : Carrier Sense Multiple Access/Collsion Detection
  pure CSMA에서 transmission delay로 인해 collision이 발생하는 상황을 위해
  CSMA/Collision Detection 방법을 사용한다.
  실제 우리가 사용하는 유선LAN에서 사용하고 있는 방법이다.
  
  pure CSMA처럼 carrier sensing을 하고, channel이 idle하다면 data를 보낸다.
  그런데 data를 보내면서 동시에 collision이 발생했는지도 detection한다.
  collision이 detection되면,
  data 전송을 멈추고, binary exponential backoff = {$0, 1, 2, 4, 8, ...$} 뒤에 다시 carrier sensing을 시작한다.
  만약 host A와 host B가 collision되어 동시에 멈추게 된다면 binary exponential backoff 뒤에 다시 carrier sensing을 하기 때문에
  collision 확률이 줄어들게 된다.

CSMA 방식은 중앙에 coordinator가 필요 없기 때문에
host들끼리 서로 distribute하게 collision을 detection, correction할 수 있기 때문에
자주 사용된다.

• CSMA/CA : Carrier Sense Multiple Access/Collsion Avoidance
  복잡하기 때문에 무선(Wi-fi)에서 사용한다. (skip...)

3. taking turns

• taking turns :
  • polling :
    chain으로 연결되어 교대로 사용함.
    master가 polling하여 host마다 data가 있는지 확인한다.
    이러한 polling 방식은 latency가 늘어나고,
    master가 잘못되는 경우가 생길 수도 있어서
    internet 환경에서는 적합하지 않다.TDMA랑 결합하여 Bluetooth로 많이 사용된다.
    TDMA는 slot을 나눠서 반복적으로 사용하기 때문에 collision이 일어나지 않는다.
    FDMA는 주파수를 나누니까 충돌이 발생하지 않는다.
    하지만 주파수를 나누기 때문에 Full bandwidth를 쓸 수가 없고,
    HW가 추가되어야 하기 때문에 FDMA는 잘 사용되지 않음.
  • token passing :
    예전 사내망 방식.
    사내망을 ring형으로 만들어서 token이 돈다.
    자신에게 token이 왔을 때, data를 보낼 수 있다.
    하지만 single point of failure기 때문에 사용하지 않는다.
    

---

LANs

MAC address

• MAC address :
  같은 컴퓨터여도 DHCP를 쓰면 IP address는 계속해서 바뀐다.
  그런데 MAC address는 못 바꾼다.
  MAC address는 같은게 없다.
  그래서 network layer에서는 IP address를 쓸 수 있는데,
  link layer에서는 IP address가 encapsulation이 되고, IP address가 계속해서 바뀌기 때문에 IP address를 쓸 수 없다.
  그래서 link layer에서는 link 간의 통신을 하기 위한 추가의 address인 MAC address(HW address)를 사용한다.
  
  그래서 LAN으로 연결되어 있는 device들끼리는 IP address로 통신하는게 아니라
  MAC address로 통신을 한다.
  

• MAC address 사용 예시

  1. edge router에서 host로 보내주는 packet은 IP address로만 내려오는데
     host에서 edge router로 packet을 보낼 때는 router의 HW address를 알아야 link layer로 보낼 수 있다.
  2. 또한 LAN에서는 host들끼리 data를 주고 받을 수 있다.
     이때 data를 주고 받기 위해 data를 내부망 밖으로 내보냈다가 상대방에게 전달할 것인가?
     아니다. link layer의 MAC address가 있기 때문에 내부망에서 직접 data를 주고받을 수 있다.
     
     ➡️ 그런데 문제는
     socket이나 router를 통해서 나가며 destination을 지정할 때,
     IP address를 지정하는 부분은 있었는데, MAC address를 어떻게 지정하는가?
     또한 내부망에서 host들끼리 서로의 MAC address를 어떻게 알 수 있는가? ARP protocol

ARP

• ARP (Address Resolution Protocol) :
  ARP는 LAN 내부에 연결된 host들의 IP address와 HW address를 mapping하는 protocol이다.
  그래서 host들은 해당하는 ARP table을 갖고 있게 된다.
  그런데 host들은 컴퓨터를 켰다 껐다, Ethernet cable을 뺐다 꼈다 등을 하니까
  ARP는 주기적으로 update가 된다.
  위에서는 LAN 환경이기 때문에 각각의 IP address의 subnet part 부분이 동일한 상황이다.
  우리는 Application에서 destination을 HW address가 아닌, IP address로 data를 보낸다.
  link layer에서는 그 IP address에 해당하는 MAC address가 있는지를 찾아서 해당하는 device로 보내야 한다.
  만약 137.196.7.78이 data를 137.196.7.88로 보낸다면,
  subnet part가 같아서 같은 LAN 안에 있다는 것을 금방 알 수 있다.
  그래서 link layer로 가면, 137.196.7.78은 137.196.7.88의 HW address를 알 수가 없다.
  그래서 LAN에 연결된 모든 host들과 edge router에서는 ARP table을 관리한다.
  <IP address ; MAC address : TTL(Time To Live)>
  왜 protocol인가?
  host들끼리 서로 packet을 주고 받으며 update해나가기 때문에 protocol이다.

• Routing to another LAN :
  111.111.111.111이 222.222.222.222한테 data를 보내야 한다.
  같은 subnet이 아니므로 edge router에게 data를 보내서 외부로 내보내야 한다.
  edge router로 보내기 위해 IP src, IP dest를 encapsulation하여 link layer로 router에 보내야 하는데
  이때, ARP table로 인해서 MAC dest address가 Router interface card의 MAC address(E6-E9-00-17-BB-4B)로 된다.
  이제 data가 ethernet까지 갔으니
  decapsulation을 해서 IP layer에서 routing table에 의해 routing을 한다.
  이때, destination이 정해지는게 아니라 interface card만 결정이 된다.
  이제 ethernet까지 내려오면 IP address가 다시 encapsulation이 되기 때문에 HW address로만 찾아야 하는데,
  이미 ARP table에 LAN에 연결된 host들의 IP address와 MAC address(49-BD-D2-C7-56-2A)를 알고 있기 때문에
  49-BD-D2-C7-56-2A에 해당하는 IP address인 222.222.222.222를 찾아서 link layer로 보낸다.
  이제 ethernet layer에서는 decapsulation해서 IP layer로 올리고, data를 받게 된다.