[컴퓨터네트워크] chapter 4-2. What's inside a router

 

국민대학교에서 "Computer Networking: A Top-Down Approach"을 이용한

이상환 교수님의 교안을 활용하여 강의 내용을 정리하였습니다.

 

(ヽ 🎀 (ヽ
꒰〃´ ˆ `〃꒱
(っ 🥛 ⊂)

 

이번 게시물에서는 router 내부에 있는 3개의 HW인 input ports, switching, output ports를 키워드로 살펴보려하며,

buffer managment와 scheduling에 대해 다루어 보려고 합니다!🩰🎀

 

 

Router architecture overview

high-level 관점에서 본 일반적인 router architecture는 아래와 같음

• routing processor는 어느 output link로 이동 시킬지 정해주는 역할을 하며 비교적 느리게 동작(millisecond)
• high-speed switching fabric은 output link로 보내주는 역할을 하므로 속도가 중요하여 엄청 빠르게 동작(nanosecond)

 

 

Input port functions

input port는 아래와 같은 구조로 이루어져 있다.

• physical layer
  • bit로 받아서 모은 후 link layer로 전달
• link layer
  • Ethernet과 같은 것을 사용하는데 이는 chapter 6에서 자세히 알아보도록 하자 🧐  
• decentralized switching (분산된 스위칭)
  • lookup: 헤더에 있는 정보를 table에 있는 정보와 비교해서 어디로 보낼지 찾는다 (match plus action: header와 내가 가진 table의 정보를 match 시키는 과정)
    ➡️ 근데 빨리하는 것이 중요하다!! (line speed)
  • forwarding: lookup을 통해 어디로 보낼 지 찾았다면 forwarding 하면된다.
    • destination-based forwarding: destination IP address만 보고 전달하는 것(하나의 field만 보고 전달하는 전통적인 방법)
    • generalized forwarding: header에 있는 여러개의 field를 보고 전달하는 것
  • queueing: datagram이 도착하는 속도가 switch fabric으로 forwarding 되는 속도보다 빠를 때 발생하는 것으로, switch fabric에 이미 처리 되고 있는 게 있다면 빌 때까지 queue에서 기다려야 한다.

 

 

Destination-based forwarding

destination의 IP address만 보고 전달하기 때문에 주소의 범위를 정하여 전달하는 방법을 사용한다.

➡️ 그런데 갑자기 범위를 쪼개서 중간의 몇 개만 다른 곳으로 보내자!!! 해버리면 table이 지저분해지고 구간이 많아지면서 lookup을 하는 시간이 오래 걸리게 된다.. 우리는 nanosecond 안에 전달을 해야하는데 말이다🥺🥺 

갑자기 저렇게 4개만 3번으로 보내자고 하면.. 처리하기 힘들어지게되.

 

 

Longest prefix matching

이럴 때 사용하는 것이 바로! longest prefix matching 이다.

📍 Longest prefix match

 destination address가 속한 범위를 forwarding table에서 찾을 때, 그 주소와 일치하는 가장 긴 주소 접두사를 찾는 것!!

이렇게 주소의 앞부분만 비교를 하는 것이다 !!

 

그런데! 한가지의 문제가 발생할 수 있다. 만약 내가 가진 destination address가 여러 개의 entry와 match가 되면 어떡하냐는 것이다.

그럴 때는 이 matching 방법의 이름을 잘 보면 된다! 바로 Longest! 가장 길게 matching 되는 것을 선택하면 된다는 것이다.

 

예를 들어보자. 내가 가진 주소가 1100/1000  0001/0111  0001/1000  1010/1010이다.

그리고 table에는 1100/1000  0001/0111 0001/1000 ********가 있고 1100/1000  0001/0111 0001/1*** ******** 가 있다.

내가 가진 주소는 방금 언급한 두 개의 entry와 모두 매칭 된다.(같은 부분을 파란색으로 표시하였다) 하지만 첫번째 entry와 더 길~~게 매칭되므로 나는 첫 번째 entry를 채택하면 되는 것이다!

 

이러한 longest prefix matching은 빠르게 수행되는 것이 중요하기 때문에 Ternary Content Addressable memories(TCAMs)라는 하드웨어를 사용하여 빠르게 수행할 수 있다!

• content addressable(콘텐츠 주소 지정 가능): TCAM에 현재 주소를 지정하면 테이블 크기에 관계없이 한 클럭 주기 내에 콘텐츠 검색이 가능.
• Cisco Catalyst: TCAM의 라우팅 테이블 엔트리 수 ~1M

 

---

 

 

Switching fabrics

• switching fabric에서는 packet을 input link에서 적절한 output link로 전달하는 역할을 한다.
  (그래서 속도가 중요하다 input port보다 빨라야한다.)
• switching rate: input에서 output으로 packet을 전송할 수 있는 속도
  • ex) 1초에 10개씩 전달할 수 있다!
  • 종종 입출력 line rate의 배수로 측정된다.
  • N개의 inputs이 있으면 switching rate는 line rate(line의 capacity)보다 N배 정도 더 많아야지 정상적으로 돌아간다.

• 세 가지의 swiching fabrics 타입이 있당
  1. memory
  2. bus
  3. interconnection network

 

 

1️⃣  Switching via memory

• 1세대 라우터
  • CPU의 직접 제어 하에 스위칭 기능이 있는 전통적인 컴퓨터(그냥 컴퓨터라고 생각하면 된다.)
  • 전송을 할 때 시스템 메모리에 packet을 복사한 후, 다시 전송한다.
  • 메모리 bandwidth에 의해 제한된 속도를 가진다. (하나의 datagram 당 2개의 bus가 필요하다 ➡️ 버스 마니 쓰네..)
    -> 여기서 메모리 bandwidth는 메모리로 얼마나 빨리 copy하고 얼마나 빨리 보내는지를 의미한다.

 

 

2️⃣  Switching via a bus

memory의 방법에서는 bus를 2번 사용해야한다는 단점이 있었다. 그래서 이를 개선한 것이 하나의 공유된 bus를 사용하는 것이다.

하지만 이 방법의 단점은 bus를 동시에 사용할 수 없기 때문에 버스 경쟁이 발생한다는 것이다.

• input port memory에서 출발한 datagramd은 공유된 bus를 통해 output port memory로 이동한다.
• bus convention: bus의 bandwidth에 의해 switching speed가 제한된다.
• 32 Gbps bus를 제공하며 , Cisco 5600라는 모델의 router가 있는데 이 기법을 사용한다고 한다.
  : access routers에서 사용하기에 충분한 속도!

 

 

3️⃣  Switching via interconnection network

위의 bus 방법은 3개의 input port에서 packet을 동시에 보낼 수 없고 한 개의 port에서만 보낼 수 있었는데, interconnection network는 3개의 input port에서 동시에 packet을 보낼 수 있도록 한 방식이다.
그러나 이 방식에서도 같은 output port로 가면 동시에 보낼 수 없다! (서로 다른 output port인 경우에만 가능)

• multistage switch: n*n을 써서 좀 더 높은 성능을 낼 수 있다.
• exploiting parallelism -> 병렬성을 활용해서 성능을 올릴 수 있다
  • 누구는 짧은 거 보내서 일찍 끝내고 기다리면 안되므로 datagram을 고정된 길이의 cell로 분할해서 보낸다.

 

---

 

Input port queueing

• 만약 fabric이 input port들의 속도보다 느릴 때를 위해 queueing이 필요하다.
  
  • input buffer의 overflow 때문에 queueing delay가 발생하고 loss까지 발생할 수도 있따.
• Head-of-the-Line(HOL) blocking: 나갈 수 있는 패킷이 있는데 앞에서 막고 있어서 나갈 수 없는 상태

좌측의 사진은 같은 output으로 전송하고자 할 때 동시 전송이 되지 않아서 발생하는 것이며, 우측의 사진은 초록색 packet은 지금 전송될 수 있지만 queue 앞에 있는 빨간색 packet이 막고 있어서 전송될 수 없는 상태이다!

 

 

output port queueing

• datagram이 output port에 도착하는 속도가 link transmission rate보다 빠를 때 buffering이 필요하다!
  그렇다면 어떤 것을 drop 시켜서 공간을 만들어내야할까?를 정의한 것이 Drop policy이다.
• Scheduling discipline는 queue 내부에서 어떠한 Packet을 내보낼 것인지 정하는 것이다.
  -> Priority scheduling: 최고의 성능을 내거나 망 중립성(network neutrality)를 고려해서 어떤 packet을 내보낼지 선택하는 것

 

• 버퍼링은 스위치 패브릭을 통해 도착하는 속도가 output line의 속도보다 빠를 때 일어난다.
• queueing delay나 loss는 output port buffer에서의 overflow 때문에 일어난다.

패브릭의 속도가 넘 빨라서 output port에 packet들이 모인다..!

 

 

How much buffering

그렇다면 얼마나 저장을 해야할까??

• RFC 3439에 따르면, 평균 버퍼링은 RTT(250 msec)에 link capacity(= C)를 곱한 것과 같다.
  ex) C = 10 Gbps라면, buffer = 250msec * 10Gbps = 2.5 Gbit 정도를 유지해야한다!
• 좀 더 최근의 방식은 N flow도 고려하는 것이다! (여기서 flow는 source IP address/Port N, destination IP address/Port N, transport layer의 type(TCP인지 UDP인지)과 같은 것을 의미한다.

flow를 고려하는 경우) flow가 많을 수록 buffer를 조금만 잡아도된다.

• 그러나 너무 많은 buffer를 사용하게 되면 delay가 증가된다..!
  • 물론 loss는 발생하지 않게된다. 하지만 Queueing delay가 길어짐에 따라 RTT도 길어지게된다.
    -> realtime apps에서는 굉장히 좋지 않음
  • delay-based congestion control: 최대한 buffer를 채우지만 넘치지 않게 해야한다.

 

 

Buffer Management

buffer management는 drop과 marking 두 가지 일을 하게 된다.

• drop: 어떤 것을 drop 시킬 것인가?
  • tail drop: queue가 꽉 차 있을 때 queue에 새롭게 도달하는 packet을 drop하는 방식
  • priority: 기존 queue안에서 우선순위가 낮은 packet을 drop하고, 빈자리에 새로운 packet을 넣는 방식
• marking: mark를 해서 보내는 것(표식을 남기는 것이라고 생각하면 될 듯)
  • 꽉 찰 때까지 기다렸다가 drop하는 것이 아니라 큐의 절반이 차면 packet이 왔을 때 ECN과 같은 비트를 바꿔서 sender에게 전달해서 속도를 늦추도록 하는 방식 

 

 

Packet Scheduling

• packet Scheduling은 다음 link에 어떤 packet을 내보낼 것인지 정하는 것이며, 아래의 4가지 방식이 있다.
  1. first come, first served
  2. priority
  3. round robin
  4. weighted fair queueing

이제 차근차근 하나씩 스케줄링 방식을 배워보도록 하자! 그림을 보고 설명을 따라가면 매우 이해하기가 쉬웠다!

 

Packet Scheduling: FCFS

• FCFS: output port에 들어온 순서대로 내보내는 방식
  • 선입선출 FIFO라고 생각하면 된다.

 

 

Scheduling policies: priority

• priority scheduling
  • 우선순위를 정해서 높은 우선순위를 가진 packet부터 전송하는 방식이다.
• 자세한 방식 
  1. packet이 들어오면 header field를 보고 우선순위 분류를 하여, high priority queue와 low priority queue에 넣는다.
  2. 그리고 highest priority queue에 담겨 있는 것들 부터 먼저 전송한다.

low priority를 전송하고 있는 도중에 high priority가 왔다고 해도 중단시키고 보내지는 않는다.

 

 

Scheduling policies: round robin

• Round Robin(RR) scheduling
  • 각각의 class에서 번갈아가면서 하나씩 전송하는 방식이다.
  • 각각의 class가 동일한 bandwidth를 사용하게 된다.
  • 담겨 있는 packet이 적으면 전송이 빠르게 완료될 수 있다.
• 자세한 방식 
  1. 헤더를 이용해서 각각의 class로 분류를 한다.
  2. 각각의 class에서 순차적으로 packet을 하나씩 꺼낸다.
     (만약 queue를 scan해서 packet이 있으면 보내면 되고, 없다면 그냥 넘어가면 된다.)

3개의 class에서 하나씩 꺼내는 방식이다.

 

 

 

Scheduling policies: weighted fair queueing

• Weighted Fair Queueing(WFQ)
  • 일반화된 RR이라고 생각하면 된다.
  • RR처럼 순차적으로 돌아가면서 전송을 하지만, weight에 따라서 보낼 수 있는 packet의 양이 달라지게 된다.
  • 그냥 RR은 매순간 하나씩 보내니까 모든 class가 동일한 bandwidth를 사용하게된다.
    하지만 WFQ는 class별로 weight를 주어서 가중치가 부여된 만큼 서비스를 받게된다. •̀.̫•́✧
    즉, weight가 클수록 더 많은 bandwidth를 사용하게 된다.
  • 최소 bandwidth를 보장해준다.
    다른 class에 packet이 엄청 많더라도 적어도 3/6, 2/6, 1/6은 사용이 가능하다는 뜻이다.
    그러나 이보다 더 많이 사용 가능하게 될 수도 있다. (다른 queue가 비면, 아직 남은 queue가 bandwidth를 독차지하여 사용 가능하기 때문에)

위에서 부터 가중치가 3, 2, 1이라고 가정할 때, 빨간색은 3/6만큼의 bandwidth를 사용할 수 있으며, 순차적으로 2/6, 1/6만큼 사용 가능하다.

 

 

Sidebar: Network Neutrality

이 부분은 망중립성과 관련된 내용이다! 사진을 보며 슉 읽어보면 될 거 같다.

 

 

ISP: telecommunications or information service?

Isp를 telecommunication service와 information service 둘 중 어떤 것으로 보느냐에 따라 적용되는 규칙이 다르다는 내용이다.