전체 글
-
[Data Structure] 2-3 TreeCS/Data Structure 2021. 12. 28. 11:58
2-3 Tree 차수가 2 또는 3인 노드를 가지는 트리이다. 완전 균형 트리이다. 많이 쓰이진 않지만, B/B+ 트리, T 트리의 기본 구조이다. 2 Node 3 Node Search(탐색) 2 Node X = key → 탐색 종료 X key → 오른쪽 서브 트리 탐색 3 Node X = 왼쪽 key or 오른쪽 key → 탐색 종료 X 왼쪽 key and X 오른쪽 key → 오른쪽 서브 트리 탐색 Insertion(삽입) 2 Node에 삽입할 경우 2 노드는 3 노드가 되고 작은 데이터가 왼쪽 데이터, 큰 데이터가 오른쪽 데이터가 된다. 3 Node에 삽입할 ..
-
[Network] Software Defined Networking (SDN)CS/Network 2021. 12. 14. 19:47
per-router control plane per-router control plane은 각각의 라우터 안에 개별 라우팅 알고리즘 컴포넌트가 있고, 다른 라우터의 control plane과 정보를 교환해 forwarding table을 만든다. logically centralized control plane logically centralized control plane은 원격 컨트롤러가 개별 라우터 내의 로컬 control agent와 정보를 주고 받아 forwarding table을 만든다. logically centralized control plane의 장점 1. 네트워크 관리가 쉽다. 개별 라우터 설정 오류를 피할 수 있고, 트래픽 흐름의 유연성이 향상된다. 위 그림과 같이 u에서 z로 가는 ..
-
[Network] Inter AS Routing Protocol - BGPCS/Network 2021. 12. 14. 18:15
앞선 포스팅에서 Link State나 Distance Vector를 설명했다. 하지만 인터넷 네트워크는 셀 수 없을 만큼 많은 라우터가 존재하기 때문에 모든 목적지 prefix를 forwarding table에 저장하는 것은 불가능하다. 그래서 이러한 거대한 네트워크를 계층화해 라우팅한다. Intra AS / Inter AS (domain) routing Autonomous System(AS, 자율시스템) 기관이나 단체가 운영하는 독립적인 네트워크를 말한다. intra-AS routing - 같은 AS 내에 호스트, 라우터 간의 라우팅 - 라우터 간의 최단 경로를 찾는다. - AS 내에 모든 라우터는 같은 프로토콜을 사용한다. - AS별로 다른 프로토콜을 사용할 수 있다. - intra-AS routin..
-
[Network] Routing algorithms - Distance VectorCS/Network 2021. 12. 13. 23:46
이 포스팅은 앞선 Routing Protocols - link state 다음으로 이어진다. 라우팅 알고리즘의 목적 라우팅 알고리즘의 목적은 출발지 라우터에서 목적지 라우터까지 최단 비용으로 갈 수 있는 길을 찾는 것이다. 라우팅 알고리즘 종류 라우팅 알고리즘에는 두가지 종류가 있다. - Link State algorithm: 모든 라우터들의 정보를 가지고 있을 경우 - Distance Vector algorithm: 자신과 이웃한 라우터의 정보만 가지고 있을 경우 Distance Vector algorithm 기본 가정 각 라우터는 이웃한 라우터의 정보만을 가지고 있다. 어떻게 다른 라우터까지의 최소 비용 경로를 찾을 수 있을까 ❔❔ 각 라우터는 Distance Vector를 가지고 있다. 이 dist..
-
[Network] Routing algorithms - Link StateCS/Network 2021. 12. 13. 18:30
라우팅 알고리즘의 목적 라우팅 알고리즘의 목적은 출발지 라우터에서 목적지 라우터까지 최단 비용으로 갈 수 있는 길을 찾는 것이다. 라우팅 알고리즘 종류 라우팅 알고리즘에는 두가지 종류가 있다. - Link State algorithm: 모든 라우터들의 정보를 가지고 있을 경우 - Distance Vector algorithm: 자신과 이웃한 라우터의 정보만 가지고 있을 경우 Link State algorithm 기본 가정 각 라우터는 이웃한 라우터의 정보만을 가지고 있다. 그럼 어떻게 모든 라우터의 정보를 얻을 수 있을까 ❔ 각 라우터는 모든 라우터에게 이웃한 라우터의 정보를 브로드캐스트해 네트워크의 전체 그림을 얻는다. 이후 각 라우터는 독립적으로 자신으로부터 모든 라우터까지 최단 거리를 계산한다. 어..
-
[Network] Network Address Translation (NAT)CS/Network 2021. 12. 12. 18:05
Middle box는 source 호스트와 destination 호스트 사이 데이터 경로에서 라우터의 기능과 별도의 기능을 수행하는 중간 장치를 말한다. Middle box의 종류로는 NAT, 방화벽, IDS, 로드 밸런서, CDN 등 다양한 장치가 있다. History 90년대 초 급격한 인터넷의 발달로 인해 43억 정도의 IP 주소가 다 할당되었고, IPv4에서 IPv6로 진화하고 있었다. 하지만 인터넷의 모든 장비를 IPv6를 지원하도록 만드는 것은 너무 오래 걸리는 일이였고, IP 주소 고갈 문제를 해결하기 위해 장비 자체를 업그레이드하지 않고 디바이스 간에 IP 주소를 공유할 수 있는 NAT가 발달하게 되었다. Network Address Translation (NAT) NAT는 다수의 priv..
-
[Network] 라우터 내부에선 무슨 일이 일어날까?CS/Network 2021. 12. 12. 16:53
Overview 앞선 포스팅에서 말한 것과 같이 라우터는 두가지 기능을 한다. 하나는 routing algorithm을 수행하여 출발지에서 도착지까지 패킷의 route(전체 경로)를 결정하는 routing, 다른 하나는 라우터로 들어온 패킷을 적절한 아웃풋 링크로 보내는 forwarding이다. Decentralized switching: 라우터는 인풋 포트 메모리에 있는 데이터그램의 헤더 값을 확인하여 forwarding table을 사용해 아웃풋 포트를 찾는다. - destination-based forwarding: 도착지 IP 주소만을 확인해 forward함 - generalized forwarding: 도착지 주소뿐만 아니라 다른 헤더 정보를 포함해 forward함 Datagram forward..
-
[Network] IPv6과 TunnelingCS/Network 2021. 12. 11. 21:22
IPv6 IPv4는 32 bits 주소 공간을 가지고 있다. IPv4의 총 개수는 2^32=43억 정도로 전세계 사람들이 가지고 있는 PC, 모바일, IoT 등을 따져보았을 때 이미 완전히 할당된 상태이다. IPv4의 부족 문제를 해결하기 위해 IPv6 주소 체계를 도입했다. IPv6는 128 bits 주소 공간을 가지기 때문에 전세계의 원자 수보다 많다고 한다~ IPv6는 16진수로 8개의 그룹으로 이루어져 있고, 앞의 네 그룹은 subnet prefix로 고정되어 있다. Tunneling IPv4 체계에서 IPv6 체계로 전환되어야 하지만 전세계에는 너무나도 많은 네트워크 장비가 있다. 이 모든 네트워크 장비를 동시에 IPv6 주소 체계가 가능하도록 업데이트 하는 것은 불가능하다. 👉 이를 해결하기 ..