Campus Coder

목차 Dijkstra's algorithm (다익스트라 알고리즘) Example Oscillation problem (진동 문제) 1. Dijkstra’s algorithm 인접한 노드들 중 최적 경로인 노드를 계속 선택하여 최적 경로 Tree를 만드는 알고리즘 Link status algorithm은 Dijkstra’s algorithm을 기반으로 만들어짐 특징 모든 노드에 대한 비용을 알고 있을 때 사용 가능 각 라우터들이 link state broadcast 하기 때문에 사용 가능 모든 노드가 동일한 정보를 가짐 하나의 노드(source)에서 모든 노드로의 최소 비용 경로 계산 해당 노드에 대한 포워딩 테이블 주어짐 반복적인 작업을 수행한 후 최소 비용 경로를 파악 2. Example c(x,y):..

목차 라우팅 프로토콜 Link status algorithm vs. Distance vector algorithm 1. 라우팅 프로토콜 라우팅 프로토콜 목표: 라우터 네트워크를 통해 송신 호스트에서 수신 호스토로의 최적의 경로를 결정 네트워크의 그래프 추상화 그래프: G = (N,E) N = 라우터 집합 -> {u, v, w, x, y, z } E = 링크 집합 -> { (u,v), (u,x), (v,x), (v,w), (x,y), (w,y), (w,z), (y,z) } c(x,x') = 링크 비용(x,x') -> 예를 들어, c(w,z) = 5 -> 비용은 대역폭, u 또는 혼잡과 역으로 관련될 수 있음 경로 비용(x1, x2, x3,..., xp) -> c(x1,x2) + c(x2,x3) + ... ..