라우터 구조
라우터는 길을 찾는 장치이다.
외부에서 들어온 패킷에 대해 어디로 가면 되는지 길을 찾아주는 역할을 한다.
라우터는 공유기와 같다고 생각하면 된다.
공유기에는 네트워크 카드를 여러 개 보유하고 있는데, 보통 4개를 가지며 무선도 있다.
이러한 라우터는 컴퓨터 구조와 동일하다.
위 사진은 라우터의 구조로 high-speed switching fabric은 라우터의 특별한 하드웨어로 cpu에서의 버스와 같은 역할을 해준다. 따라서 컴퓨터의 버스는 라우터의 역할을 할 수 있는 것이다.
스마트폰에서도 라우팅 기능을 사용하고 있으며 5G, LTE 등의 인터페이스와 와이파이 인터페이스 사이의 패킷을 전달한다.
IP 라우팅과 포워딩(Routing, Forwarding)
- Routing: 길 찾기 기능
라우팅 테이블, shortest path routing algorithm.
최단거리 알고리즘으로는 다익스르라와 벨만 포드 등이 존재한다.
IP 헤더에 있는 주소를 통해 패킷을 전달한다.
프로세스의 역할은 라우팅이다.
- Forwarding: 패킷 전달 기능
포워딩 테이블, 목적지 주소 룩업(조회), 입력 큐에서 출력 큐로의 패킷 전달.
LTE, 와이파이 사이의 데터링과 동일하다. 패킷을 전달할 때 CIDR과 같이 패킷의 목적지 주소로 룩업해야 한다.
이때 포워딩은 라우터가 입력 포트에서 출력 포트로 패킷을 이동시키는 것을 말한다.
라우팅 테이블은 목적지까지의 경로를 결정하는 데 사용되며, 포워딩 테이블은 실제로 패킷을 해당 경로로 전달하는 데 사용한다.
Input port fuction
일반적으로 라우터는 공유기를 제외하면 99%가 백본으로 유선이다.
이러한 공유기는 칩이라고 할 수 있는데, 이러한 칩 안에는 마찬가지로 cpu나 메모리가 존재하여 작은 컴퓨터처럼 존재한다.
- physical layer
bit를 알아낸다.
- link layer
이더넷의 주소를 알아낸다.
- decentralized switching
link layer에서 알아낸 이더넷 주소를 통해 패킷을 왔다갔다하게 한다.
포워딩을 통해 입력을 switch fabirc로 전달하는 역할이다.
헤더 필드에 존재하는 값으로 forwarding table을 이용하여 output port를 룩업한다.
이 과정은 'line speed'로 input port를 처리하는 것을 목표한다.
input port queuing은 데이터그램이 입력으로 들어오는 속도가 switch fabric로 보내는 전달속도보다 빠른 경우에 발생한다.(입력 속도 > 처리 속도)
기본적으로는 도착지 IP 주소만을 기준으로 전달하지만 일반화하여 헤더의 필드값을 기반으로 전달한다.
포워딩 테이블
포워딩 테이블은 컴퓨터에서도 확인할 수 있으며, 보통 많아도 4-5개를 보유하고 있다.
입력으로 들어온 포워딩 값을 통해 output interface를 매핑 해 줄 수 있다.
패킷 교환(Packet Switch)망
라우터의 기본 히스토리는 교환망에서 출발하여 전화기를 연결하여 통신하는 장치로 시작하였다.
이러한 전화의 과정을 패킷으로 진화한 것이 패킷망이며, 현재 존재하는 패킷망이 TCP/IP 네트워크이다.
TCP/IP 네트워크는 데이터그램 단위의 교환망으로 라우터는 input port에서 output port로 연결하는 패킷 전달의 역할을 수행하고, IP 패킷, 즉 IP 데이터그램 단위로 전달된다.
ip는 주소만 보기 때문에 패킷 단위로 주소를 확인하고 경로를 설정하므로 같은 목적지를 향하는 패킷이라도 경로가 달라질 수 있다.
이때 IPv4 주소의 경우 43억개의 모든 주소가 기록되어 있는 것이 아니라 CIDR 포맷의 형태로 기록되어 있으며 약 90만~100만 개가 존재한다.
따라서 라우터의 역할은 패킷이 들어 왔을 때 주소를 보고 테이블을 확인하여 맞는 포트로 매핑해주는 역할을 한다.
Destination-based forwarding
앞서 포워딩 테이블에서 43억개의 모든 ip가 등록되어 있다고 하지 않았다.
포워딩 테이블은 위 사진과 같이 범위를 나누어 아이피별로 매핑해 준다.
가장 위의 주소가 최소, 마지막의 주소가 최대값이다.
이때, 위 사진은 범위가 잘 나뉘어 서로 겹칠 일이 없다.
라우팅 알고리즘에 의해 포워딩 테이블이 위와 같이 업데이트 되었다고 하자.
위 상황에서 3번 아웃풋 링크와 0번 아웃풋 링크가 겹칠 수 있는 상황이 되었다.
이 경우 어떤 링크 인터페이스로 향하는 것이 좋을까.
Longest prefix matching
Longest prefix matching이란 도착 주소로 포워딩 테이블의 항목을 찾을 때, 도착지의 주소와 가장 길게 매칭되는 항목을 고르는 것이다.
위와 같은 포워딩 테이블이 있다고 가정하자.
라우터에 도착한 패킷이 위와 같은 목적지 주소를 가질 때 포워딩 테이블에서는 1번과 2번 output 링크와 매핑된다. 이때, 1번 output 링크의 경우가 매칭되는 범위가 더 길기 때문에 1번 output 링크로 매핑해준다.
위와 같은 매칭은 일단 매칭될 ip 주소를 모두 찾은 상태에서 진행하며 하드웨어 단에서 진행된다.
IP 주소 매칭 알고리즘
ip 패킷(데이터그램)이 들어 왔을 때 라우팅 테이블에서는 어떤 알고리즘을 통해 주소를 찾을 수 있을까?
- Hash
가장 찾기 쉬운 방법은 해쉬를 사용하는 것이다. 따라서 99%의 서치는 해쉬로 해결이 가능하지만, linear의 경우 시간복잡도가 O(n)이 된다.
- Trie
Trie 구조는 위와 같은 모양을 가진다.
알파벳으로 표현되며, 위에서부터 바이너리로 탐색하여 찾을 수 있다.
평균적으로 시간복잡도는 O(nlogn)이 된다.
LC tire (Level Compressed Trie)라고 보통 이야기하며 Longest prefix matching(lpm)를 효율적으로 하기 위해 탄생한 알고리즘이다. 이러한 알고리즘은 리눅스(유닉스)에 구현이 되어 있는데, 실제로 대부분의 라우터는 리눅스 기반이다.
+) 추가
하드웨어가 빠르면 CAM(Content Address Memory)라는 방법도 사용할 수 있다.
이 CAM 방식은 인덱스를 통해 값을 찾는 것이 아닌, 값을 통해 항목을 찾을 수 있다.
Switching fabrics
라우터의 구조는 컴퓨터와 동일하지만 부가적으로 추가적인 하드웨어가 필요하다.
Switching fabrics은 라우터의 내부에서 패킷을 전달하는 역할을 하며 속도에 큰 영향을 끼친다.
- memory
가장 최초로 등장한 방식으로 운영체제에서의 인터럽트를 처리하는 방식과 비슷하다.
패킷이 도착하면 cpu는 라우터 프로세스에게 인터럽트를 주고, 라우팅 프로세서는 패킷을 메모리로 복사한 후 복사된 내용을 output 포트로 전달한다. 복사가 두 번 진행되어야 하므로 대역폭의 1/2밖에 쓰지 못한다.
- bus
버스는 데이터가 지나갈 수 있는 통로로 패킷이 라우터에 도착하면 버스로 전달하고 버스에서 어떤 링크 인터페이스로 가야 하는지 결정한 후 해당 링크 인터페이스(output 링크)로 전달된다. 모든 패킷이 버스를 거쳐야 하므로 버스의 대역폭이 커야 병목현상이 생기지 않는다.
- interconnection network
그물망 모양으로 입력과 출력이 연결되어 있어 어떤 길을 향해도 모든 곳에 도착할 수 있다.
입력 포트에서의 문제점
교차로에서 혼잡이 되는 문제는 네트워크 카드에서 발생하는 문제 때문이다.
라우터에 패킷이 들어갈 때 들어가는 속도가 라우터 내부에서 처리되는 속도보다 빠른 경우 큐에서 대기 지연 시간이 발생하게 되는데, 이는 버퍼의 오버플로우로 인해 패킷이 손실될 수도 있다.
이러한 큐 앞쪽의 패킷이 대기하는 현상을 Head-of-the-Line (HOL) blocking라고 한다.
네트워크가 느려지다가 버퍼가 풍선처럼 터지는 현상을 Bufferbloat라고 한다.
최근에는 버퍼를 너무 많이 키워 버퍼대기시간이 길어지면서 느려지는 현상이 발생한다.
출력 포트 큐
- Buffering
스위칭 속도(처리)가 빠를 때 발생한다.
- Drop policy
패킷 손실이 발생할 때의 정책이다.
- Scheduling discipline
패킷 선택 정책으로, FICO, 우선순위 큐를 사용한다.
참고 및 출처
https://velog.io/@yh_lee/%EB%9D%BC%EC%9A%B0%ED%8C%85-vs-%ED%8F%AC%EC%9B%8C%EB%94%A9
'Computer Science > 컴퓨터네트워크(ComNet)' 카테고리의 다른 글
| [컴네/CN] NAT 공유기 개요 (0) | 2023.12.06 |
|---|---|
| [컴네/CN] 인터넷 잡학 (1) | 2023.12.06 |
| [컴네/CN] Network계층의 IP (1) | 2023.12.06 |
| [컴네/CN] 혼잡제어 (1) | 2023.12.05 |
| [컴네/CN] Socket Programming (1) | 2023.12.05 |