Breadth-First Search BFS는 주로 무방향 그래프에서 사용되는 그래프 탐색 알고리즘으로 넓이 우선 탐색 이라고 불린다.그래프를 순회하거나 최단경로(Shortest Path)를 구할때도 사용한다.구현할때는 Queue를 사용한다.Shortest Path Problem 최단 경로를 구하는 문제이다.  예를 들어 위의 그래프에서 s에서 b까지 가는 가장 최단거리는 이다.우선 주어진 그래프 G = (V,E)에서 BFS 알고리즘의 리턴값은 d[v](s to v 까지의 거리),pred[v](전에 지나온 노드)이다.pred[v]는 최단거리를 위해 실제로 지나온 노드를 기록하기에 경로를 찾을 수 있다.따라서 BFS가 그래프 탐색을 완료하면  이를 바탕으로 최단 경로 트리(Shortest path tree..

이전에 배웠던 Linklayer부분은 데이터통신이랑 겹치기에 따로 작성하지 않음.MAC address(Media Access Control adress) MAC 주소는 링크계층(Link layer)에서 사용하는 장치별 교유 주소이다.48bit로 이루어져있으며 LAN,물리,이더넷 주소라고도 불린다.LAN은 다음과 같은 형식으로 이루어진다. MAC 주소는 IEEE에 의해 관리되며 IP주소와는 다르게 위치기반이 아니다.장치에 기록된 주소기에 위치를 변경해도 같은 주소를 사용한다.즉,Flat한 구조를 갖고 있다.여기서 생각해봐야하는 점은 MAC주소가 꼭 필요하지 않을 수 있다는 것이다.이미 IP주소가 있기에 패킷이 목적지로 도달이 가능하다.하지만 이럼에도 MAC주소를 사용하는 이유는 만일 MAC주소가 없다면 간..

0-1 Knapsack problem 배낭문제라고 불리며 DP로 해결할 수 있는 대표적인 문제이다.DP에 대해 상기해보자면 DP 접근법은 시간은 단축시키고 공간을 늘리는 Space-time trade off 관계이다.배낭문제는 주어진 제한 조건 내에서 특정 아이템의 가치 합을 최대화하는 방법을 찾는 문제이다.파일 i에 사이즈가 w고 소요시간이 v일때 제한 W를 만족시키는 최대의 합을 찾아내는 것이라고 하고 상황이 다음과 같은 예시라고 하자.이때 0-1 Knapsack문제에서는 각 파일을 더 작게 분할할 수 없다. W = 시간은 10이 최대값이라 할때.위의 경우 i가 2,4인경우가 답이다.이는 케이스가 적어서 직관적으로 바로 풀 수 있는 쉬운 예였지만 이 i가 매우 커지면 DP를 통해 해결해야한다.그전에 ..

ICN(Information-centric networking) TCP/IP 기반의 인터넷의 한계를 나타내기 위해 제안된 네트워킹 방식으로 현재는 사용되지 않는 기술이다.TCP/IP는 End-to-end 모델을 채택하고 있었기에 IP는 지역에 기반한 식별자로 사용되었다.하지만 점점 무선통신기술이 발달하자 IP가 고정되지 않게되었다.그리고 인터넷 트래픽 트랜드를 보면 비디오 영상의 트래픽이 급성장하고 있기고 중복되는 데이터가 많아졌다.이러한 상황에서 데이터를 보다 효과적으로 전달하고 무선 기기에 대한 서비스를 개선하기 위한 움직임이 등장했다.그것이 ICN으로 구상도는 다음과 같다. TCP/IP 기반의 네트워크에서는 결국 IP가 어디에 컨텐츠가 있는지를 요청했다면 ICN에서는 컨텐츠가 무엇인지에 집중한다.즉..

Network는 네트워크 관리자(Network operator)에 의해 관리된다. 네트워크를 관리하기 위해서는 관리자는 네트워크를 모니터링해야한다.그리고 문제 발생시 조치한다.네트워크를 관리하기 위한 3가지 접근법은 다음과 같다.Command Line Interface(CLI)SNMP/MIBNETCONF/YANG첫번째 CLI같은 경우 터미널을 사용해서 직접 네트워크 기기에 명령을 내리는 것으로 이는 굉장히 비효율적이다.SNMP/MIB는 관리 프로토콜을 표준화하여 관리한다.이는 CLI는 결국 기기가 모두 다른 현실 네트워크에서 매번 적용하기 힘들기 때문이다.네트워크 기기들의 정보는 MIB(Management Information Base)라는 데이터베이스에 저장되어있고 이를 통해 NMS(SNMP Manag..

SDN은 기존의 라우터들의 Control plane에서 할 수 없었던 요소들을 만족 시켰다.즉,동적인 링크 코스트의 변화에 따른 유동적인 라우팅 알고리즘을 적용하지 못하는 점과 링크가 고장났을때의 대처를 빠르게 하는등의 이점을 챙길 수 있었다.Easier network managementTable-based forwarding allows "programmable" routersOpen implementation of control planeSDN은 하드웨어에도 영향을 미쳤다.기존의 라우터들은 모든 기능이 Monolitic하게 디자인되었지만 SDN의 등장으로 Open Interface만 준수한다는 가정하예 설계자의 니즈에 맞게 모듈별로 조합이 가능해졌다.Traffic Engineering 기존의 라우팅은..