트로둥의 일기장

용어Tree: 1개 이상의 노드들의 유한 집합Disjoint sets(부분 집합): 모든 트리는 노드 수 >= 0인 부분집합을 갖는다.노드 레벨: 루트는 레벨 1, 자식 레벨 = 부모 레벨 + 1노드의 차수(degree): 노드의 서브트리 수리프 노드(터미널 노드): 차수가 0인 노드(끝 노드)비단말 노드(논 터미널 노드): 차수가 0이 아닌 노드노드 X의 자식: 노드 X의 서브트리의 루트형제(sibling): 부모가 같은 자식들트리의 차수: max{노드의 차수}조상: 속한 모든 subtree의 루트트리의 깊이: max{노드 레벨} 트리의 리스트 표현 >>공간 낭비가 많음 왼쪽 - 자식, 오른쪽 - 형제로 하여 이진 트리로 표현

Routing protocols - link state라우팅 프로토콜의 목표는 라우터들 사이에서 가장 '좋은 경로'를 찾는 것이다. 여기서 '좋은' 경로 란 적은 비용, 속도, 그리고 낮은 혼잡도를 의미한다.  이를 찾기 위해 각각의 라우터들을 노드로 먼저 그래프 추상화를 한다. 이 중 이 글에서는 link state에서만 다룰 예정이다.link state란, 모든 라우터들이 각자의 상태(state)를 공유하여 다익스트라 알고리즘을 통해 최적의 경로를 구하는 방법이다.다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최소 경로를 계산하는 알고리즘으로 포워딩 테이블을 만드는데 사용된다.Dijkstra's link-state routing algorithm노테이션은 다음과 같다.C는 x에서 y로 가는 ..