OSPF(Open Shortest Path First) 동작원리

7.1 배 경

OSPF는 IETF(Internet Engineering Task Force)의 IGP(interior gateway protocol) working group에 의해 IP 네트워크에서 사용하기 위해 개발되었다.
이 워킹 그룹은 1988년에 결성되었으며, 인터넷상에서 SPF(Shortest Path First) 알고리즘에 근거한 IGP를 디자인하기 위해서였다.
OSPF는 두 가지 주요한 특성을 가지는데, 첫 번째는 프로토콜이 OPEN즉, RFC (Request For Comments) 1247에 사양이 명시되어있다는 것과 두 번째로 딕스트라(Dijkstra)의 SPF(Shortest Path First)알고리즘에 근거를 한다는 것이다.
OSPF는 같은 계층 영역(Hierarchical area) 내의 모든 라우터들에게 LSAs (Link State Advertisements) 패킷을 보내는 link-state 라우팅 프로토콜이며, 사용자에 의한 경로 지정, 가장 경제적인 경로의 지정, 복수경로의 선정 등의 기능을 제공하며, 변화의 발생에 관한 정보가 RIP에 비하여 빨리 전파된다.
라우팅정보를 인접한 라우터에 모두 전송하는 플러딩(flooding) 방식을 사용하므로 토폴로지(topology)에 관한 정보가 전체 네트웍상의 라우터에서 동일하게 유지된다. 그리고 각 라우터는 자신을 네트웍의 중심점으로 간주하여 최단 경로의 트리(tree)를 구성한다.

7.2 기본 기술

OSPF는 Interior Gateway Protocol(IGP)에 속하는 라우팅 프로토콜이다. 즉 하나의 Autonomous System(AS) 안에서만 라우팅이 이루어지는 라우팅 프로토콜이며 link-state routing algorithm을 사용한다. 여기서 link란 다른 의미로는 라우터 인터페이스(router interface)이다.
따라서 interface-state routing protocol이라고도 부른다. state라는 단어는 라우터 인터페이스나 link의 변수(parameter)로 취급한다. 이 변수는 인터페이스의 UP이나 DOWN을 나타내는 물리적인 상태, 인터페이스의 IP 어드레스, 인터페이스에 할당된 subnetmask, 인터페이스와 연결되어 있는 네트워크 그리고 라우터가 네트워크에 연결할 때 사용되는 cost 등이다.
OSPF는 다른 OSPF 라우터와 정보를 교환할 때 루트의(변화된) 상태를 교환하는 것이 아니라 link 정보를 교환한다. OSPF를 사용하는 라우터는 네트워크들끼리 도달 할 수 있는지 또는 distance 값이 얼마인지를 넘기는 것이 아니라 각각의 라우터의 네트워크 인터페이스 상태(state)와 이들 인터페이스에 연결된 네트워크와 인터페이스에서 사용되는 cost를 넘긴다.
모든 라우터들은 각기 다른 link state를 갖는다. 각 라우터의 link state는 local link state로 취급한다. 이 local link state는 OSPF 네트워크를 통하여 OSPF 라우터가 완전한 link-state database를 만들 때까지 정보를 교환(flooded)한다. 모든 라우터들은 모든 local link state를 서로 한번씩 주고받는다. 그 다음 각각의 라우터들은 그 자신을 root로 생각하며 하나의 트리(tree)를 만든다.
그리고 트리(tree)의 가지들(branchs)은 AS 안의 모든 네트워크의 루트, 최소 코스트(cost) 그리고 최단 거리에 대한 정보를 갖는다. 모든 OSPF 라우터는 이들 정보를 가지고 최단 경로(Shortest Path)를 갖는 라우팅 테이블을 만든다.
각 link의 코스트(cost)는 link 의 대역폭과 관계가 있는데, 값이 작을수록 좋은 링크로 여겨진다. 일반적인 cost 계산 방법은 다음과 같다.

cost =100000000/전송속도

예를 들면 10M 이더넷은 10 EXP8 / 10 EXP7 = 10이고, E1 라인은 10 EXP8 / 2048000 = 49이다.

네트워크가 증가하면서 link state database 크기도 증가된다, 전체적으로 네트워크의 성능에 영향을 미친다. 이런 문제점을 해결하기 위하여 OSPF는 이들 네트워크를 여러 개의 영역으로 쪼개는 생각을 하게 된 것이다. 즉, 제한된 영역에서만 link state 정보를 교환하는 방식을 채택하였다.
OSPF에서 는 이 제한된 영역을"area"라 부른다. 이 area 안에 적절하게 라우터의 수를 제한함으로써 가장 적합한 link state database를 가지게 할 수 있다. 그리고 OSPF는 다음과 같은 규칙을 정했다. OSPF는 반드시 area 0라는 backbone area를 가지고 있어야 한다는 것이다. 그리고 이 area 0 주변에는 다른 area들이 (Fig. 7-1) 과 같이 연결되어 있는 형태를 가지게 된다.



Area 안에 있는 라우터를 Internal Router(IR)라고 부르며, area 들 사이에 있는 라우터를 ABR(Area Border Router)라고 부른다. 그리고 다른 AS나 다른 네트워크 사이를 연결하는 라우터를 ASB(AS Boundary Router)라고 부른다. area 0에 있는 라우터는 Backbone 라우터라 부른다. 그리고 area 사이에 있는 Area Border 라우터는 두 개의 Link state Database를 갖게 된다. 하나는 Area 0에 대한 Database이고 또 다른 하나는 인접한 Area에 대한 Database이다.

OSPF 네트워크에서 사용하는 용어에는 다음과 같은 것들이 있다.

Router ID : 32비트로 구성되며 라우터의 고유 번호로 사용된다. 실제적으로 라우터에 부여된 가장 높은 IP 어드레스를 Router ID로 선정한다. 때로는 Loopback IP 어드레스를 Router ID로 사용하는 경우가 있다. 물론 Loopback IP 어드레스가 이 라우터에서 가장 높은 IP 어드레스임이 분명하다.

Neighboring routers : 라우터 인터페이스에 연결된 네트워크이다. multiaccess (NBMA)와 point to multipoint의 두 가지 타입이 있다. Designated Router(DR) : Broadcast 네트워크와 NBMA 네트워크에서 DR라우터는 link state 정보를 다른 네트워크에 제공한다. 일반적으로 DR라우터를 제외한 라우터끼리는 link state 정보를 주고받지 못한다. Backup Designated Router(BDR) : DR 라우터가 다운될 때 대체할 수 있는 라우터이다.

Adjacency : Broadcast 네트워크나 NBMA 네트워크에서 DR과 Non-DR사이에 이뤄지는 형태를 말한다. 모든 OSPF 라우터는 Adjacency에 의하여 Routing Update가 이루어진다.

Flooding : 라우터들끼리 link-state database를 분배하고 동기화하는 것이다.

Route Summarization : 특정 네트워크의 IP 어드레스들을 대표 IP 어드레스로 묶어서 다른 네트워크에 보내는 방법을 의미한다.

7.3. 동작 원리

OSPF는 인접한 노드를 찾는 Neighbor Discovery , Routing Update를 위해 LSA (Link State Advertisement)패킷의 작성, 배포 그리고 최적의 경로 계산 부분으로 이루어진다.

□ Link State Advertisement

Network Topology 정보를 얻기 위해 사용되는 메시지(message)로서, 상태 변화가 있는 경우에만 발생이 되며, 모든 라우터에게 전달된다. 또한 위상 DB의 동기화를 위해 매 30분마다 발생된다.

□ OSPF Metric

OSPF에서도 경로설정 시 메트릭(Metric)값을 고려하는데, 각 Interface Default Metric 값이 설정되어 있으며, 관리자가 설정하는 것도 가능하다.

□ Neighbor Discovery



□ 지원 가능한 네트워크 형태

OSPF 라우팅 프로토콜에는 세 가지 네트웍 연결 형태가 지원된다.

1) 포인트 투 포인트 형태 : 모든 라우터들이 독립적으로 수행한다.

OSPF에서 크게 고려할 사항이 없다.

2) Multiaccess 형태

LAN에서 하나의 라우터가 Designated Router(DR)가 되고, 다른 모든 라우터들은 Multicast hello를 사용해서 인접 라우터 관계를 이 DR을 통해 배운다. 인접 라우터들은 multicast OSPF Hello 패킷을 사용해 통신하는데, 라우팅 정보 교환에 따른 트래픽을 줄이고, 경로 정보 데이터베이스를 동기화 시킨다.

새로운 라우터는 multicast 주소 224.0.0.5를 모든 SPF 라우터들에게 Hello 메시지를 보냄으로 알려진다. 그리고 DB와 BDR(Backup DR)의 주소를 알게 된다. 그러면, 새로운 라우터는 224.0.0.6으로 DB와 BDR에게 LSA를 보낸다. BDR은 타이머를 설정하고 DR에 LSA를 보내기 위해 기다린다. DR은 다른 라우터에게 LSA를 224.0.0.5로 보내고, 모든 라우터의 응답을 기다린다. 만약 BDR이 타이머가 종료되기 전에 DR LSA를 전달받지 못하면, DR이 되고, BDR을 선출한다. 네트웍이 다운된 것을 DR에게 224.0.0.6으로 보내면 DR은 이것을 다른 라우터에게 224.0.0.5로 보내고, 다른 라우터들은 인접한 다른 네트웍으로 이 LSA를 보낸다.

3) Nonbroadcast Multiaccess 형태

X.25나 Frame-relay와 같은 Nonbroadcast Multiaccess 환경에서는 다른 모든 OSPF 라우터와 직접 통신할 수 없다. 이런 경우에는 인접라우터와의 관계를 일일이 수 작업으로 설정해 주어야 한다. LSA에는 2가지 종류가 있는데, 라우터LSA와 Summary LSA가 있다. 라우터 LSA는 Area를 가진 LSA에 의해 만들어진다. Summary LSA는 ABR에 의해 만들어지며, OSPF 라우팅알고리즘을 수행하지는 않는다. 축약은 OSPF 데이터베이스와 라우팅 테이블을 감소시킨다. 라우팅 테이블에는 inter-area route로 표시된다. 또한, Area에 의한 위상 변화는 백본(Backbone) Area의 변화를 야기 시키지 않는다.

□ OSPF 경로축약

경로 축약 기법을 사용하면 2가지 라우팅 정보가 네트워크를 통해 전달된다. 즉 백본(backbone)이 각 지역에 대한 정보를 얻는 Area-to-Backbone Advertisement, 각 지역에서 백본과 다른 지역에 대한 정보를 얻는Backbone-to-Area Advertisement가 그 경우이다.

1) Area-to-Backbone Advertisement

적절한 축약을 위해서는 OSPF 지역설계 시 다음과 같은 사항을 고려해야 한다.

a) OSPF경로 축약은 지역 경계 라우터에서 수행된다.

b) OSPF는 VLSM(Variable Length Subnet Mask)을 지원하므로 네트 워크/ 서브넷(subnet) 어드레스에 대한 임의의 Bit Boundary축약이 가능하다.

c) OSPF 사용 시에는 수 작업으로 축약해야 한다.

2) Backbone-to-Area Advertisement

각 지역에는 4가지 형태의 라우팅 정보가 존재한다.

a) 기본 경로: 지정된 IP 네트워크/서브 네트워크를 찾을 수 없는 경우에는 라우터가 기본경로에 지정된 목적지로 패킷을 넘긴다.

b) 역 내 경로(Intra-areaRoutes): 명확히 지정된 네트워크나 서브네트 경로는 지역 내의 모든 네트워크나 서브네트에 전송한다.

c) 지역간 경로 (Interarea Routes):각 지역은 동일한 AS의 네트워크에 대한 명확히 지정된 네트워크나 서브네트 경로를 전송한다.

d) 외부경로 (ExternalRoutes): 서로 다른 AS끼리 라우팅 정보를 교환할 때 교환되는 경로를 외부 경로라 부른다.

아래의 (Fig. 7-5)에서는 전형적인 OSPF 네트워크의 형태를 나타내 주고있다.

7.4 OSPF Configuration 예

이제부터 OSPF 라우팅 프로토콜을 이용한 네트워크를 만들고 configuration을 해보자.

(Fig.7-6)을 이용하여 라우터를 OSPF 네트워크로 구성하려고 할 경우, 단계별 구성을 살펴본다. 우선 OSPF를 적용하지 않은 각 라우터의 구성은 아래와 같다.


Current configuration
!
Version
!
hostname Router A
!
enable secret 5 $$$$$$$$
enable password cisco
!
interface Loopback 0
ip address 172.16.1.1 255.255.255.0
!
interface Loopback 1
ip address 172.16.2.1 255.255.255.0
!
interface Ethernet 0
ip address 172.16.3.1 255.255.255.0
!
no ip classless
!
line con 0
line aux 0
line vty 0 4
password cisco
login
!
end


Current configuration
!
Version
!
hostname Router B
!
enable secret 5 $$$$$$$$
enable password cisco
!
interface Loopback 0
ip address 172.16.5.1 255.255.255.0
!
interface Loopback 1
ip address 172.16.4.1 255.255.255.0
!
interface Ethernet 0
ip address 172.16.3.2 255.255.255.0
!
no ip classless
!
line con 0
line aux 0
line vty 0 4
password cisco
login
!
end

(Fig.7-6)은 Area 0의 Backbone 네트워크이다. (Fig.7-6)의 네트워크를 OSPF 라우팅 프로토콜로 설정하고자 한다. 이제 OSPF 프로세스를 동작시켜 보자.

Router A#config terminal
Router(config)#router ospf ?
<1-65535> Process ID
Router(config)#router ospf 10
Router(config-router)#^Z
RouterA#

OSPF의 프로세스 ID를 라우터에 여러 개 동작시키는 것은 권장하지 않는다. 만약에 프로세스 ID를 여러 개 동작시키면 OSPF Database를 여러 개 복사해야 하며, 여러 개의 Short Path 알고리즘을 동작시키기 때문에 라우터의 성능을 저하시킨다. 이제 OSPF 라우팅 프로세스를 동작시켰으므로 라우터 주변의 네트워크를 다른 네트워크에 통보해야 한다. 즉, RouterA는 172.16.1.0, 172.16.2.0, 172.16.3.0을 통보한다. 다른 라우팅 프로토콜에서는 다음과 같이 커맨드를 설정하여 통보하였으나, OSPF는 다음 세가지 요소를 가지고 다른 네트워크에 통보한다. 먼저 네트워크 번호, 네트워크 마스크 그리고 이 네트워크가 속한 Area이다.

OSPF 라우팅 프로토콜	network 172.16.1.0 0.0.0.255 area 0
기타 라우팅 프로토콜	network 172.16.1.0

OSPF라우팅프로토콜에서 네트워크를 표현하는 커맨드를 분석하면 다음과 같다.

network
172.16.1.0 : OSPF Wild card bits로서 netmask의 역 (reverse)으로 표현된다.
즉, 1은 0으로 바꾸고, 0은 1로 바꾸는 것이다.
Area 0 : backbone area 이다. 이 area는 십진수 또는 X.X.X.X과 같이 IP어드레스처럼 표현할 수 있다. 참고로 여기에서 Area X는 해당 네트워크의 인터페이스가 어떤 area에 속하는지에 따라서 정해진다.

이제 샘플 네트워크로 다시 돌아가서 설정해 보자.

RouterA# config terminal
RouterA(config)#router ospf 10
RouterA(config-router)#network 172.16.1.1
RouterA(config-router)#network 172.16.1.1 0.0.0.0
RouterA(config-router)#network 172.16.1.1 0.0.0.0 area 0
RouterA(config-router)#network 172.16.2.1 0.0.0.0 area 0
RouterA(config-router)#network 172.16.3.1 0.0.0.0 area 0
RouterA(config-router)#^Z

RouterA의 모든 인터페이스는 Area 0에 속한다. 따라서 모두 "area 0"로 Area를 설정했다. 그리고 172.16.1.1. 0.0.0.0 은 172.16.1.1 호스트를 표시한다. 0.0.0.0은 netmask의 역(reverse)으로 표현한 것이다.

이제 RouterB를 보자.

RouterB# config terminal
RouterB(config)#router ospf 10
RouterB(config-router)#network 172.16.3.2 0.0.0.0 area 0
RouterB(config-router)#network 172.16.4.1 0.0.0.0 area 0
RouterB(config-router)#network 172.16.5.1 0.0.0.0 area 0
RouterB(config-router)#^Z

이제 두 대의 라우터 모두 OSPF 라우팅 프로세스를 동작시키고 있다. 이들의 라우팅 테이블을 보자.

RouterA#sh ip route
172.16.0.0 is variably subnetted, 5 subnets, 2 masks
o 172.16.5.1/32 [110/11] via 172.16.3.2,00:02:50, Ethernet0
o 172.16.4.1/32 [110/11] via 172.16.3.2,00:02:50, Ethernet0
C 172.16.1.0/24 is directly connected, loopback0
C 172.16.2.0/24 is directly connected, loopback1
C 172.16.3.0/24 is directly connected, Ethernet0

RouterB#sh ip route
172.16.0.0 is variably subnetted, 5 subnets, 2 masks
C 172.16.4.0 255.255.255.0 is directly connected, loopback1
C 172.16.5.0 255.255.255.0 is directly connected, loopback0
o 172.16.1.1 255.255.255.255 [110/11] via 172.16.3.1,00:00:22, Ethernet0
o 172.16.2.1 255.255.255.255 [110/11] via 172.16.3.1,00:00:22, Ethernet0
C 172.16.3.0 255.255.255.0 is directly connected, Ethernet0

RouterA와 RouterB는 각각 3개의 직접 연결된 루트와 OSPF로부터 배운 2개의 루트가 있다. 이들 라우팅 테이블의 각각의 정보를 분석하면 다음과 같다.

루트는 무엇으로부터 배우나 : C - 라우터에 직접 연결되고, O -OSPF로부터 배운다.

[110/2]는 administrative distance (110)이고 cost(2)로 구성된다는 의미이다. 그리고 directly connected는 해당 라우터의 인터페이스에 이 네트워크가 물리 적으로 직접 연결되었음을 의미한다.

via 172.16.3.2는 OSPF를 넘겨주는 중간 네트워크(transit network)이다.

00:02:50은 해당 루트가 생성 후에 지난 시간을 의미한다. 참고로 OSPF는 주기적으로 라우팅 테이블을 Update시키지 않는다.

Ethernet0는 도착지 네트워크로 보낼 패킷이 지나가는 인터페이스.

이제 OSPF 네트워크의 네트워크 설정을 호스트가 아닌 다음과 같이 설정해 보자.

RouterA# config terminal
RouterA(config)#no router ospf 10
RouterA(config)#router ospf 10
RouterA(config-router)#network 172.16.1.0 0.0.0.255 area 0
RouterA(config-router)#network 172.16.2.0 0.0.0.255 area 0
RouterA(config-router)#network 172.16.3.0 0.0.0.255 area 0
RouterA(config-router)#^Z

RouterB# config terminal
RouterB(config)#no router ospf 10
RouterB(config)#router ospf 10
RouterB(config-router)#network 172.16.3.0 0.0.0.255 area 0
RouterB(config-router)#network 172.16.4.0 0.0.0.255 area 0
RouterB(config-router)#network 172.16.5.0 0.0.0.255 area 0
RouterB(config-router)#^Z

먼저 기존의 네트워크 설정을 지워야 한다(no router ospf 10). 그리고 다시 설정한다. 이전과 다른 것은 호스트가 아닌 네트워크라는 것이다. 이 새로운 설정 파일을 가지고 라우팅 테이블을 보면 다음과 같다.

RouterB#sh ip route
172.16.0.0 is variably subnetted, 5 subnets, 2 masks
C 172.16.4.0 255.255.255.0 is directly connected, loopback1
C 172.16.5.0 255.255.255.0 is directly connected, loopback0
o 172.16.1.1 255.255.255.255 [110/11] via 172.16.3.1,00:00:33, Ethernet0
o 172.16.2.1 255.255.255.255 [110/11] via 172.16.3.1,00:00:33, Ethernet0
C 172.16.3.0 255.255.255.0 is directly connected, Ethernet0

앞부분의 설정과 현재의 설정을 가지고 라우팅 테이블을 비교하면 결과는 똑같다. 그러면 이제 (Fig.7-6)의 대표(Major)네트워크(172.16.0.0.)를 OSPF 네트워크에 설정해 보자. 물론 RouterA와 RouterB에 동일하게 적용한다.

RouterA# config terminal
RouterA(config)#no router ospf 10
RouterA(config)#router ospf 10
RouterA(config-router)#network 172.16.0.0 0.0.255.255 area 0
RouterA(config-router)#^Z

RouterB# config terminal
RouterB(config)#no router ospf 10
RouterB(config)#router ospf 10
RouterB(config-router)#network 172.16.0.0 0.0.255.255 area 0
RouterB(config-router)#^Z

라우팅 테이블은 마찬가지이다. 172.16.0.0의 모든 subnet는 area 0에 속하는 네트워크이다. 그런데 특정 네트워크인 172.16.1.0은 area 10에 속한다고 하자. 이 네트워크를 라우터에 설정할 수 있다. 그러나 이런 방식의 네트워크 구성은 권장 하지 않는다.
실제로 "network 172.16.1.0 0.0.0.255 area 10"은 "network가 172. 17.1.0 0.0.0.255 area 10" 등의 별도의 네트워크를 구성할 것을 권장한다.

OSPF 라우팅 프로토콜은 Class Inter-Domain Routing(CIDR)과 supernetting을 지원한다. 따라서 네트워크를 설정할 때에 Class 에 구분하지 말고 임의로 subnet를 구성할 수 있다. 예를 들면 B Class 인 172.x.x.x 네트워크는 일반적으로 255.255.0.0의 subnet를 갖는다. 그러나 다음과 같이 사용해도 OSPF는 허용한다.

router ospf 10
network 172.0.0.0 0.255.255.255 area 0

위의 예를 실제 적용시켜 보자. 먼저 (Fig.7-6) 네트워크 구성 도중 RouterA에 Loopback2를 추가로 설정한다. IP 어드레스는 Loopback2 172.17.6.1 / 24로 한다.

이 새로운 네트워크를 RouterB는 인식하지 못한다. 이것은 OSPF 네트워크의 범위가 network 172.16.0.0 0.0.255.255이기 때문이다. 172.17.6.0 / 24 는 172.16.0.0 / 16 네트워크에 속하지 않기 때문에 RouterA는 172.17.6.0 / 24 네트워크 정보를 보내지 못한다.

RouterA의 OSPF 네트워크가 network 172.16.0.0 0.0.255.255 area 0인 경우에 loopback2 네트워크 정보가 RouterB에 넘어오지 않는다. 그러나 network 172.0.0.0 0.255.255.255 area 0로 RouterA를 설정하면 RouterB에 loopback2 네트워크에 대한 정보가 넘어온다.

이 경우 RouterA의 설정 순서가 반드시 다음과 같아야 한다.

router ospf 10
network 172.17.6.0 0.0.0.255 area 1
network 172.0.0.0 0.255.255.255 area 0

---

실습 및 고찰

1. 다음 명령어는 OSPF를 모니터링 하는데 사용되는 커맨드이다.

- show ip ospf

- show ip ospf neighbor

다음 명령어는 OSPF를 디버깅하는데 사용되는 명령어 이다.

- Debug ip ospf ?

<예>

다음 설정 파일을 보고 답하시오.
Router A# show running-config

Current configuration
!
Version
!
hostname Router A
!
enable secret 5 $$$$$$$$
enable password cisco
!
interface Ethernet 0
ip address 192.168.1.1 255.255.255.0
!
interface Ethernet 1
ip address 192.168.4.1 255.255.255.0
!
interface Serial 0
no ip address
shutdown
!
interface Serial 1
no ip address
shutdown
!
!
no ip classless
!
router ospf 10
network 192.168.1.0 0.0.0.255 area 1
network 192.168.4.0 0.0.0.255 area 4
area 1 virtual-link 192.168.2.1
!
line con 0
line aux 0
line vty 0 4
password cisco
login
!
end
RouterA#

1) OSPF 라우팅 update는 어느 인터페이스를 통해 이루어지는가 ?

2) OSPF 라우터의 프로세스 ID 는 ?

3) Ethernet 0 인터페이스는 Area 0(백본 area) 와 연결되어 있는가 ?

4) Ethernet 1 인터페이스는 어디와 연결되어 있는가 ?

5) OSPF는 AS number를 사용하는가 ?

6) 라우터 ID는 무엇인가 ?

출처 : http://nengjung.kit.ac.kr/~jdlee/ospf.html