[IT/컴퓨터 네트워크] OSPF 알고리즘 기능 이해

1. OSPF 개요 

▶ 1980년 중반 대규모 이기종 네트워크 간의 라우팅 수행 한계 도달

▶ IETF에서 최단거리 알고리즘 기반으로 대규모 네트워크에 적용 가능한 라우팅 알고리즘 개발 -> OSPF

▶ 자신을 중심으로 모든 목적지까지의 최적 경로를 계산하여 라우팅 테이블 작성 

▶ 라우팅 테이블이 안정화 되면 라우팅 정보를 주기적으로 갱신하지 않고 네트워크 변화가 있을때만 갱신함으로써 라우팅 프로토콜 트래픽이 네트워크에 미치는 영향을 최소화 가능 

▶ 네트워크 환경에 변화시 플러딩 과정을 통해서 데이터 베이스를 신속하게 갱신 

▶ RIP에 비해 라우팅 트래픽 량을 획기적으로 줄일 수 있음 

▶  OSPF는 널리 사용하는 라우팅 프로토콜이고 링크상태 알고리즘 사용 

2. 링크 상태 알고리즘 

▶ 개요

- 라우터는 이웃에 대한 연결정보를 다른 모든 라우터에 전달 

- 네트워크 전체 토폴로지에 대한 정보를 얻고 이를 바탕으로 최적의 경로 선택 

▶ 플러딩 

- 링크 상태 프로토콜을 사용하고 있는 모든 라우터에 링크 상태 정보를 전송하는 과정 

- 링크 상태 패킷을 사용하여 정보 전송 

- LSP 구성 

LSP 생성 라우터 ID

목적지 주소

비용

이웃 라우터 ID

- LSP 플러딩 과정 -> 라우터 A가 새로운 LSP를 생성했을 때 플러딩이 진행되는 과정 

▶  최단 거리 트리 - 다익스트라 알고리즘 

라우터는 자신을 루트로 하여 목적지까지의 최단 거리 트리 구성 

A를 루트로 최단경로 계산 

비용이 적은 경로 부터 확장 

현재 연결 노드애소 최소거리 값을 가지면 영구노드로 정함 

최소값을 가진 것을 영구 노드가 될 수 없는 것은 3, 5를 가진 다른 네트워크를 거치더라도 2보다는 작은 값을 가질 수 없기  때문

계속 확장해 나가고 가지의 값은 누적 값

더 이상 확장이 되지 않음녀 해당된 영구노드가 최단거리 경로가 됨

 

링크 상태 알고리즘 (Link State Algorithm)
• Dijkstra알고리즘은 라우터와 네트워크를 노드로, 그 연결을 아크(Arc, 원호, 호)로한 그래프를 이용하여 네트워크에 있는 노드간의 최단경로를 계산
• 하나의 노드를 루트로 하여 아크에 연결된 노드를 임시 노드에 두고 최소 비용을
가지는 노드를 찾는 검사를 수행하여 최단거리 트리의 영구 노드를 결정
1. 트리의 루트가 될 하나의 노드를 정한다.
2. 1의 노드를 영구노드로 결정한다.
3. 가장 최근에 영구 노드가 된 노드의 이웃 노드를 검사한다.
4. 각 노드에 누적합의 비용을 계산하고 임시 노드로 만든다
5. 임시 노드들에 대해서 가장 비용이 적은 노드를 찾아 영구 노드로 만든다.
하나이상의 경로가 존재 할 때는 누적합이 가장 작은 경로를 선택한다.
6. 3.에서 5.의 과정을 모든 노드가 영구노드가 될 때까지 반복한다.

➢ Dijkstra Algorithm(다익스트라 알고리즘)
• 1959년에 만들어진 Dijkstra 알고리즘은 오래된 알고리즘으로서 정점들간의 간선에 가중치(Weight)를 가진 그래프에서 최단 경로를 찾을 수 있게 해준다. 또한 이 알고리즘은 음수 값을 갖지 않는 간선을 가지는 가중치 유향 그래프에 사용되는데, 이때 그래프는 서로 연결되어 있어야만 한다.
• [원리]
– 시작 정점으로부터 임의의 정점 X까지의 거리가 현재 다른 정점까지 가는 것보다 작다고 가정하자. 그렇다면 다른 정점을 경유해서 갈 경우, 그냥 임의의 정점 X까지 가는 것이 무조건 더 작을 것이다. (가정에 의해, 그리고 모든 가중치는 양수이다)

– 위에 그림에서 보면, S->X는 가장 짧은 간선이다. 그러므로 S->T라는 간선은 S->X보다 클 것이다. 또한 T->X는 물론 양수이므로 결국, (S->T + T->X) >(S->X)임을 알 수 있다.
– 그러므로 2가지 경로 중 최단거리인 S->X 를 선택

▶  메세지 형식  (모든 메세지는 동일한 헤더로 시작)

➢ 동작
• 플러딩을 위해 D class IP 주소를 사용 멀티캐스팅 수행
• “hello”메시지
– 이웃 라우터에게 자신이 살아있다는 것을 알리기 위해 사용
– 일정기간 동안 “hello”메시지가 없을 때에는 이상상태가 발생했음을 감지하고 그 사실을 플러딩

➢ 수렴 속도 (Convergence)
• 네트워크 토폴로지가 변경되었을 때 신속하게 적응
– 장애를 즉시 감지
– 변경된 정보를 LSP(링크 상태 패킷)에 담아 AS내 모든 OSPF 이용 라우터에 플러딩
– LSP 수신시 즉시 데이터베이스 갱신
– 최단 경로 알고리즘을 이용하여 경로를 재 계산
• 영향을 주는 요인
– 장애 감지, 인터페이스 상태 변화
– Dead Timer : 일정 시간 내에 이웃 라우터로부터 hello 패킷이 수신되지 않을 때 확인
– 경로 계산 시간은 네트워크의 크기, 데이터베이스 내의 경로 개수에 따라 달라짐