Dynamic Programming  한국어로는 동적계획법이라 하며 Divide & Conquer와 같은 패러다임의 일종이다.예를 들어보면 다음과 같다.이 계단을 다 오르기 전 단계는 무조건 3가지 경우중 하나가 된다.얼핏보면 다음과 같이 재귀트리를 표현할 수 있다.얼핏보면 Divide & Conquer과 비슷하다.실제로 접근법 자체는 크게 다르지 않다.이후 더 깊이 재귀 절차를 보면 다음과 같다. 여기서 DP의 핵심은 반복되는 요소들이다.ways(n-2)는 2번 반복되는데 둘다 동일한 값이고 나머지 요소도 그렇다.즉,DP의 핵심은 이러한 반복되는 요소들을 저장해놓고 다시 계산하지 않고 불러서 사용하는 것 이다.중복되는 값을 저장하고 사용함으로써 선형 시간 복잡도를 갖는다.만일 저 문제를 DP로 해결하지..

이전에 배웠던 라우팅 알고리즘(Link state,Distance vector)은 모든 라우터가 동등한 입장에 있었다.하지만 현실은 모든 라우터가 같은 레벨에 존재하지 않는다.현실에서는 라우터의 수가 많이 증가했고 ISP들의 각각의 네트워크를 각자의 방식으로 관리하기에 실제로는 계층적이다.이를 자율 시스템(Autonomous Systems,AS)로서 조직화하여 해결한다.따라서 라우팅 프로토콜은 크게 2가지로 나눌 수 있다.Intra-AS 동일한 AS안에서 라우팅하는 프로토콜로 IGP(Interior Gateway Protocol)로도 불린며 동일한 AS내의 라우터는 같은 Intra-domain 라우팅 프로토콜을 사용해야 하고 서로 다른 AS는 서로 다른 Intra-domain 라우팅 프로토콜을 사용할 수..

라우터는 포워딩,라우팅 2가지 기능을 수행한다.라우팅 프로토콜(Routing Protocol)은 네트워크에서 호스트간에 좋은 경로를 찾는 것으로 이 좋은 경로의 기준은 비용,속도,혼잡도 등의 기준으로 평가할 수 있다. 라우팅 알고리즘은 그래프로 추상화 할 수 있다.각 노드를 라우터,간선들을 링크라하고 각각의 가중치를 표시하면 된다.라우팅 알고리즘의 분류는 다음과 같다. static은 일반적으로 고정된 라우터들을 의미하고 dynmaic은 자동차에 들어가는 네트워크처럼 동적인 형태를 취하는 것 들을 의미한다.하지만 중요한 2가지는 Link state,Distance vector 알고리즘이다.Link state algorithms 링크 상태 알고리즘으로 이름으로도 유추가능하듯이 이 알고리즘은 모든 라우터들이 ..

분할 정복 알고리즘을 사용한 정렬 알고리즘이다.굉장히 유명한 알고리즘으로 현재 많은 기본 언어에서의 Sort()함수는 Quick sort를 사용한다.퀵 정렬은 "in place"정렬이다.이는 삽입정렬과 동일하며 병합정렬와는 다르다.in place는 정렬하는데 있어서 추가적인 배열을 할당하지 않는다.반면 병합정렬은 combine하는데 있어서 배열을 추가적으로 할당해야한다.따라서 속도의 차이가 존재한다.이제 알고리즘을 소개하자면 다음과 같다.Divide:배열 a를 두 개의 부분 배열로 분할하는데 이는 피봇(Pivot)이라는 기준원소를 기준으로 피봇보다 작은 원소를 모아두는 배열과 큰 원소를 모아두는 배열로 나눈다.Conquer:퀵 정렬을 재귀 호출해서 두 부분의 배열을 정렬한다.Combine:부분 배열은 이..

SDN SDN(Software Define Network)는 포워딩을 일반화한 것으로 가장 큰 특징은 Control plane과 Data plane이 분리되어 있는 것이다.즉,소프트웨어적으로 이를 구현하는데 이때 각 라우터에 있는 포워딩테이블을 확장시킨 Flow table을 이용한다.따라서 Flow table에 추가적으로 기재되어있는 정보를 사용해서 포워딩을 하는 것이다.Flowtable이 수행하는 역할은 패킷의 header fields의 값과 Match하고 controller에 적당한 Action(drop,forward,modify..)를 수행하고 match가 여러개 됬을때 우선적으로 시행하는 Priority가 존재한다.그리고 트래픽의 양(패킷 수,바이트)를 측정하는 Counter가 존재한다.OpenF..

Network Address Translation(NAT) 하나의 사설 네트워크에 포함된 기기들이 그저 하나의 IP주소를 통해 인터넷과 통신하는 네트워크 라우팅 방식이다.사설 네트워크에 안에서는 포트번호로 기기를 구분한다.이를 통해 IP주소를 각각기기에 할당하지 않아도 되기에 IP주소를 효율적으로 관리할 수 있다.이 사설 네트워크에서 사용되는 IP주소는 private IP Address로 흔히 192.168.0.,10.11,172.16.로 시작하는 IP가 이에 속한다. NAT를 사용함으로써 ISP는 하나의 IP주소만 알면 사설 네트워크의 모든기기를 네트워킹할 수 있고 보안적으로도 특정기기를 외부에서 특정하기 매우 어렵다.NAT사용하는데 만일 사설 네트워크의 장비가 서버의 역할을 해야한다면 외부에서는 해당..