[컴퓨터 네트워크] 링크 상태 라우팅(Link State Routing) 알고리즘

링크 상태 데이터 베이스 유지

• 각 라우터가 전체 네트워크의 구성과 링크 상태 정보를 유지
• 글로벌 라우팅(Global Rounting)

다익스트라 알고리즘(Dijkstra Algorithm)

• 각 라우터가 다익스트라 알고리즘을 수행하여 전체 k개의 목적지 라우터에 대한 최소 비용 경로와 다음 라우터를 계산한다.

라우팅 테이블 설정

• 목적지, 최소 비용 경로 상의 다음 라우터, 비용 설정

LSP(Link State Packet) 플러딩(flooding)

• 링크 상태 공유, 다익스트라 알고리즘과 별개의 라우팅 프로토콜에 의해 수행

링크 상태 데이터베이스(Link-State DB)

• LSP 플로딩 결과 모든 라우터가 동일한 LSDB 유지

각 라우터가 알려진 LSDB에 대해 수행

1. 직접 연결된 링크 중에 비용이 가장 작은 링크의 라우터를 최소 비용 경로 라우터로 선택
2. 최소 비용 경로로 선택된 라우터와 직접 연결된 라우터에 대한 경로 비용을 재계산하고, 기존 경로 비용과 비교하여 작으면 경로 비용 갱신
3. 경로 비용이 알려진 라우터들 중에 경로 비용이 가장 작은 라우터를 최소 경로 비용 라우터로 선택
4. 모든 라우터가 최소 경로 비용 라우터로 선택될 때까지 2~3을 반복

다익스트라 알고리즘 정의

• u: 출발지 라우터
• C(i, j): 라우터 i에서 라우터 j까지의 링크 비용, 라우터 i와 라우터 j가 직접 연결되지 않았으면 C(i, j) = ∞
• D(v): 출발지 라우터에서 목적지 v까지 현재의 최소 경로 비용
• p(v): 출발지 라우터에서 목적지 v까지 현재의 최소 비용 경로에서 v의 직전 라우터
• N[ ]: 출발지 라우터로부터 최소 비용 경로가 명확히 알려진 라우터들의 집합

라우터 u에서 알고리즘 실행

1. N[ ] = {u}
2. 모든 라우터 i에 대해 i가 u의 인접 라우터이면 D(i) = c(u, i), 아니라면 D(i) = ∞ → 초기화 완료
3. N[ ]에 포함되지 않은 라우터 중에 D(j)가 최소인 라우터 j를 선정하여 N 집합에 추가, 라우터 j의 직진 라우터 p(j) 기록(D(j)의 값이 동일한 경우 그중에서 임의의 라우터 선정) → u로부터 목적지 j에 대한 최소경로비용 확정
4. 라우터 j와 인접한 모든 라우터 중에 N[ ]에 포함되지 않은 라우터 k에 대해 D(k) = min{D(k), D(j) + C(j, k)}로 갱신
5. 모든 라우터가 N[ ]에 포함될 때까지 3~4를 반복

실행 결과