국민대학교에서 "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에서 기다려야 한다.
- lookup: 헤더에 있는 정보를 table에 있는 정보와 비교해서 어디로 보낼지 찾는다 (match plus action: header와 내가 가진 table의 정보를 match 시키는 과정)

Destination-based forwarding
destination의 IP address만 보고 전달하기 때문에 주소의 범위를 정하여 전달하는 방법을 사용한다.
➡️ 그런데 갑자기 범위를 쪼개서 중간의 몇 개만 다른 곳으로 보내자!!! 해버리면 table이 지저분해지고 구간이 많아지면서 lookup을 하는 시간이 오래 걸리게 된다.. 우리는 nanosecond 안에 전달을 해야하는데 말이다🥺🥺

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 타입이 있당
- memory
- bus
- 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 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 때문에 일어난다.

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인지)과 같은 것을 의미한다.

- 그러나 너무 많은 buffer를 사용하게 되면 delay가 증가된다..!
- 물론 loss는 발생하지 않게된다. 하지만 Queueing delay가 길어짐에 따라 RTT도 길어지게된다.
-> realtime apps에서는 굉장히 좋지 않음 - delay-based congestion control: 최대한 buffer를 채우지만 넘치지 않게 해야한다.
- 물론 loss는 발생하지 않게된다. 하지만 Queueing delay가 길어짐에 따라 RTT도 길어지게된다.
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가지 방식이 있다.
- first come, first served
- priority
- round robin
- weighted fair queueing
이제 차근차근 하나씩 스케줄링 방식을 배워보도록 하자! 그림을 보고 설명을 따라가면 매우 이해하기가 쉬웠다!
Packet Scheduling: FCFS
- FCFS: output port에 들어온 순서대로 내보내는 방식
- 선입선출 FIFO라고 생각하면 된다.

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

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

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를 독차지하여 사용 가능하기 때문에)


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


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

'Computer Network' 카테고리의 다른 글
| [컴퓨터네트워크] chapter 4-3. IP: the Internet Protocol (1) | 2024.05.16 |
|---|---|
| [컴퓨터네트워크] chapter 4-1. Network Layer: overview (0) | 2024.05.03 |
| [컴퓨터네트워크] chapter 1. Introduction (2) | 2024.04.25 |