CS
-
[Data Structure] TrieCS/Data Structure 2021. 12. 29. 18:28
Binary Trie 특징 이진 탐색 트리 형태의 불균형 트리 자료구조이다. 완전 매칭과 부분 매칭에 효율적인 자료구조이다. 해시의 대체로 사용된다. 두 타입의 노드를 가진다. - Branch(link, interior, non-leaf) Node: 데이터 없이 자식 노드의 포인터만 저장 - Element(data, leaf) Node: 데이터 저장 시간복잡도: O(k), k=키의 최대 비트 수 Search(탐색) 탐색할 데이터를 K라고 할 때 i번째 레벨에서 K의 i번째 비트 = 0 → 왼쪽 서브 트리 이동 K의 i번째 비트 = 1 → 오른쪽 서브트리 이동 리프 노드에 저장된 데이터과 탐색할 데이터를 비교한다. Insertion(삽입) Insert 00001 Insert 10011 Insert 0010..
-
[Data Structure] T TreeCS/Data Structure 2021. 12. 28. 16:08
T Tree T 트리는 AVL 트리의 이진 탐색 특성 및 높이 균형과 B 트리의 업데이트와 저장 효율 장점을 모두 취한 MMDB(Main-Memory Database) 최적화 트리이다. Background AVL 트리의 공간 낭비와 잦은 회전 연산을 개선하기 위해 만들어짐 AVL 트리가 하나의 노드에 데이터 한 개만을 가지는 대신 T 트리는 하나의 노드가 n개의 데이터를 가질 수 있도록 개선한 구조임 장점 B 트리의 엔트리가 해당 레코드를 포함하는 데이터 페이지를 가리키고 있는데 반해 T 트리의 각각의 엔트리가 해당 레코드의 메모리 주소를 직접 포인팅하고 있기 때문에 T 트리 인덱스는 논리적 주소를 물리적 주소로 변환하는 작업 없이 원하는 레코드를 빠르게 접근할 수 있음. T 트리는 인덱스 노드에 키 값..
-
[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..