Routing Protocol-OSPF

Open Shortest Path First(OSPF) http://www.netmanias.com/ko/?m=view&id=blog&no=5476

- 시스코와 같은 대규모 네트워크 벤더사에서 사용되는 open standard 라우팅 프로토콜

- 큰 네트워크라면 OSPF를 사용해야하고 OSPF는 라우팅 프로토콜 간 translation service인 route redistribution(경로 재분배) 사용  

- Dijkstra algorithm을 사용하여 동작. 먼저, shortest path tree가 생성되고 최적의 경로를 가지고 routing table 만들어짐

- EIGRP만큼 빠르지는 않지만 빨리 converge(모여듦, 집중, 수렴) 함

- 동일한 목적지로 다양하고 같은 비용의 경로 지원

- EIGRP처럼 IP와 IPv6 프로토콜 제공

- OSPF 특징

1) area와 autonomous systems으로 구성

2) routing update  traffic을 최소화함

3) scalability 지원

4) VLSM/CIDR 지원

5) 제한된 hop count 가짐

6) multi-vendor deployment 지원

 

- link state routing protocol

- 계층적 구조로 설계됨 : 큰 internetwork를 area라 불리는 작은 internetwork로 분리

- 계층구조로 OSPF를 설계하는 이유

1) 라우팅 오버헤드를 줄이기 위해

2) convergence 속도를 높이기 위해

3) network instability를 single area 네트워크로 confine 하기 위해

 

OSPF 용어

link - 주어진 네트워크에 할당된 네트워크 또는 라우터 인터페이스. 하나의 인터페이스가 추가되면 OSPF에 의해 하나의 링크로 인정됨. 이 링크. 즉, 인터페이스는 하나 이상의 IP 주소뿐만 아니라 상태 정보를 가짐.

router id - 라우터를 식별하기 위해 사용되는 주소. 시스코는 모든 configured loopback interface 중 가장 높은 IP 주소를 사용함으로써 router ID를 선택. loopback interface가 주소로 configure되지 않는다면 OSPF는 active physical interface 중 가장 높은 IP 주소를 선택할 것

neighbor - point-to-point serial link 위에 연결된 두 라우터와 같이 일반 네트워크 위에 하나의 인터페이스를 가지는 두개 이상의 라우터

adjacency - 직접적인 route update 교환을 허가하는 두 OSPF routers 간의 관계. OSPF는 neighbor 간의 직접적인 경로를 공유하는 EIGRP와 달리 라우팅 정보를 공유. 대신, OSPF는 established adjacencies를 가지는 neighbor 간 경로를 직접적으로 공유. 네트워크 유형과 라우터 configuration에 따라 adjacency 관계 결정

hello protocol - OSPF hello protocol은 dynamic neighbor discovery anmaintanins neighbor 관계 제공. hello 패킷과 link state advertisements(LSAs)는 토폴로지 데이터베이스를 만들고 유지. hello 패킷은 멀티캐스트 주소 224.0.0.5로 전달됨

neighborships database - hello 패킷이 보여지는 모든 OSPF 라우터의 목록. 라우터 ID와 상태를 포함한 상세한 정보들은 neighborship database에 각 라우터 상에 관리됨.

topological database - 토폴로지 데이터베이스는 하나의 area에 대해 수신한 모든 link state advertisement 패킷의 정보를 포함. 라우터는 input으로써 토폴로지 데이터베이스로부터 모든 네트워크로의 가장 짧은 경로를 계산하는 Dijkstra algorithm으로 정보를 사용

link state advertisement - OSPF 라우터 간에 공유된 link state와 라우팅 정보를 포함하는 OSPF 데이터 패킷. OSPF 라우터는 established adjacencies를 가지는 라우터와 LSA 패킷을 교환할 것

Designated router - OSPF 라우터가 같은 multi-access network(broadcast network)에 연결될 때마다 Designated router(DR)가 선택됨.

예) 이더넷 LAN : 형성되는 adjacencies의 수를 최소화하기 위해 브로드캐스트 네트워크 또는 링크 상에 남아있는 라우터로부터 오고가는 라우팅 정보를 전송하고 받기 위해 하나의 DR이 선택됨. 토폴로지 테이블이 동기화되는 것을 보장한다. 공유된 네트워크 상 모든 라우터는 DR과 backup DR(BDR) 간 adjacencies를 만든다. 이는 가장 높은 우선순위를 가지는 라우터에 의해 결정되고 우선순위가 같다면 가장 높은 Router ID가 tiebreaker로 사용된다.

backup designated router - multi-access links(broadcast network) 위의 DR에 대한 hot standby. BDR은 OSPF adjacent router로부터 모든 라우팅 업데이트를 수신하지만 LSA 업데이트를 전송하지 않음

OSPF areas - contiguous 네트워크와 라우터의 그룹. 동일 area 내의 모든 라우터는 동일 Area ID를 공유. 라우터가 한번에 하나 이상의 area의 멤버가 될 수 있기 때문에 Area ID는 라우터 상 특정 인터페이스와 연관됨. 이는 남아있는 인터페이스가 area 0에 속하는 동안 몇 인터페이스가 area 1로 속하도록 허락함. 동일 area 안의 모든 라우터들은 동일한 토폴로지 테이블을 가짐. OSPF를 configuring할 때, area 0은 backbone area로 간주됨. Area는 계층적인 네트워크 organization(구조, 기관)을 만드는 역할. OSPF의 scalability 향상시킴.

Broadcast(multi-access) 이더넷과 같은 broadcast(multi-access)networks는 다양한 디바이스들이 하나의 패킷이 네트워크 상의 모든 노드로 전송되는 broadcast ability를 제공할 뿐만 아니라 동일 네트워크로 연결되도록 함. OSPF에서 하나의 DR과 BDR은 각 broadcast multi-access network를 위해 선정됨

Non-broadcast multi-access(NBMA) - NBMA 네트워크는 frame relay, X.25, Asynchronous Transfer Mode(ATM)과 같은 유형. 이 네트워크는 multi-access를 허락하지만 이더넷과 같은 broadcast 능력은 없음 . 그래서 NBMA 네트워크는 적절하게 기능하는 특별한 OSPF configuration을 요구하고 neighbor 관계는 정의되어야만 함

Point-to-point - 하나의 통신 경로를 제공하는 두 라우터 간의 직접적인 연결을 구성하는 네트워크 토폴로지 유형. Point-to-point 연결은 두 라우터를 직접적으로 연결하는 시리얼 케이블로써 물리적 연결이거나 Frame Relay network에 의해 수천 마일 상의 두 라우터 간에 논리적 연결일 수 있음. 이 configuration 유형은 DR이나 BDR의 필요없지만 neighbor들은 자동적으로 발견됨

Point-to-multipoint - 하나의 라우터 상의 싱글 인터페이스와 다양한 목적지 라우터 간의 연결을 구성하는 네트워크 토폴로지. Point-to-multi point 연결을 공유하는 모든 라우터 상의 모든 인터페이스는 동일 네트워크에 속함. Point-to-point와 같이 DR과 BDR이 필요 없음

 

SPF Tree Calculation

area 내에서 각 라우터는 모든 네트워크로의 가장 최적의 경로를 계산한다. 이 계산은 토폴로지 데이터베이스에서 수집된 정보에 기반하여 shortest path first(SPF)라 불리는 알고리즘을 가지고 계산한다. 이 shortest path tree는 라우팅 테이블에 OSPF 경로르 넣기 위해 사용된다.

이 tree가 동일 area 내에 존재하는 네트워크들만 포함한다. 만약 하나의 라우터가 다양한 area에서 인터페이스를 가진다면 분리된 tree들은 각 area에 구성될 것. SPF 알고리즘의 경로 선택 과정 동안 고려되는 요소는 네트워크로의 metric 또는 potential 경로 비용이다. 하지만 이 SPF 계산은 다른 area의 경로에는 적용되지 않는다.

OSPF는 cost로 언급되는 metric을 사용. cost는 SPF tree에 포함되는 모든 outgoing interface와 관련됨. 전체 경로 비용은 경로를 따라 outgoing interface의 비용의 합으로 계산. cost는 RFC 2338에 정의된 arbitrary 값이기 때문에 시스코는 각 이용가능한 OSPF 인터페이스에 대해 cost를 계산하는 방법을 가짐. 시스코는 10^8/bandwidth 식을 사용. 이 대역폭은 인터페이스를 위한 configured bandwidth. 이 규칙을 사용하여 100Mbps Fast Ethernet interface는 1이라는 default OSPF cost를 가지고 10Mbps Ethernet interface는 10이라는 cost를 가짐

 

 

OSPF 네트워크 토폴로지

 

 

그림 상에 5개의 OSPF 라우터(R1 ~ R5)가 존재하고, 라우터간 연결 링크에 대한 IP 주소와 OSPF Cost 및 각 라우터의 Loopback 주소(예. R1의 경우 10.1.0.1)가 표시되어 있습니다. 그리고 파란색 줄(링크)가 OSPF가 enable되어 있음을 표시하고 있습니다.

• OSPF에서 얘기하는 Cost란 각 링크로 패킷을 전달하는데 드는 "소요 비용"으로 OSPF는 Cost가 작은 경로를 최적의 경로(Shortest Path)로 인식합니다. 통상적으로 Link Cost는 링크 속도(bandwidth of a link)에 따라 그 값을 정의합니다. 그래서 예로 100Mbps 링크보다는 1GE 링크 Cost가 작을 것이고, 1GE 링크 보다는 10GE 링크가 Cost가 작을 것입니다. (Link Cost는 라우터의 각 Interface별로 운영자가 CLI를 통해 설정함)
• 라우터간에 OSPF 프로토콜 메시지를 주고 받기 위해서는 각 라우터를 식별할 수 있는 IP 주소(OSPF RID(Router ID))가 필요한데 이를 위해 보통 Loopback 주소를 사용합니다. Physical Link의 IP 주소를 사용해도 상관은 없지만 다음과 같은 차이로 인해 Loopback 주소를 선호하지요.

• • Physical Link IP 주소 사용의 경우: 해당 Physical Link가 down 되는 경우 그 IP 주소가 사라짐. 즉, 이 주소를 OSPF RID로 사용한 OSPF 라우터는 더 이상 OSPF neighbor(나와 연결되어 있는 라우터)와 통신이 불가함
  • Loopback IP 주소 사용의 경우: Loopback 주소는 어떤 특정 Physical Link와 바인딩되어 있지 않은 Logical한 주소이기 때문에, Physical Link가 down되더라도 Loopback 주소는 계속 살아 있음

 

각 라우터는 자신의 링크 IP 주소를 다른 라우터들로 전파

 

1. R1이 자신의 링크 정보를 다른 OSPF 라우터들로 전파

 

 

 

R1은 자신의 Link(Interface) 주소와 Loopback 주소를 Router-LSA에 실어 R2, R3로 전달합니다[t = 1]. 그리고 이를 수신한 R2, R3는 Router-LSA가 수신된 링크를 제외한 나머지 링크로 Router-LSA를 flooding 합니다. 그래서 R4와 R5는 동일한 Router-LSA를 2개씩 수신합니다[t = 2]. 이 경우, LSA 식별자에 해당하는 {LS Type, Link State ID, Advertising Router}가 동일한 경우 두번째 수신한 LSA를 폐기합니다.

• LS Type: Router-LSA (1), Network-LSA (2), External-LSA (5) 등의 타입을 구분
• Link State ID: Router-LSA인 경우 Advertising Router와 동일 값 (10.1.0.1)
• Advertising Router: Router-LSA를 생성한 라우터의 ID (OSPF RID 즉, Loopback 주소 = 10.1.0.1) 

 

R1이 보낸 Router-LSA에 포함되는 정보는 다음과 같습니다. (위 그림의 우측 상단을 보세요)

• Link Type: 링크 타입을 가리키는 값으로 그 타입에 따라 Link ID와 Link Data에 들어가는 값이 달라짐
  • Link Type = 1: Point-to-point connection(그림상에서 라우터간 연결은 모두 여기에 해당)
  • Link Type = 3: Stub network(라우터의 loopback 주소)
• Link ID: R1과 연결된 OSPF Neighbor의 Router ID(Link Type=1,  OSPF Neighbor간에 Hello 메시지를 주고 받는 과정에서 Neighbor의 RID를 알게 됨) 혹은 R1의 Loopback 주소(Link Type=3)
• Link Data: R1의 Link IP 주소(Link Type=1) 혹은 R1의 Loopback 주소에 대한 subnet mask (/32 = 255.255.255.255)
• Metric: 해당 Link의 cost(CLI로 각 링크의 cost는 설정함). Loopback 주소(stub network)인 경우 cost는 0

이와 같이 R1이 보낸 Router-LSA를 R2 ~ R5가 수신 하게 되면 각 라우터는 그 정보를 OSPF LSDB(Link State DataBase)에 저장하고 그 정보를 바탕으로 OSPF Topology를 그리게 됩니다. 현재까지의 정보로 R1 ~ R5 라우터가 알 수 있는 Topology는 다음과 같습니다.

• R1의 Loopback 주소 (10.1.0.1/32)
• R1의 Link 주소 1.1.1.1은 R2(10.1.0.2)와 연결되어 있음
• R1의 Link 주소 1.1.2.1은 R3(10.1.0.3)과 연결되어 있음

 

2. R2가 자신의 링크 정보를 다른 OSPF 라우터들로 전파

 

 

R2는 자신의 Link(Interface) 주소와 Loopback 주소를 Router-LSA에 실어 R1, R4, R5로 전달하고[t = 1], 이를 수신한 R1, R4, R5는 Router-LSA가 수신된 링크를 제외한 나머지 링크로 Router-LSA를 flooding 합니다[t = 2]. 

 

R1, R3, R4, R5는 이 정보(Router-LSA)를 LSDB에 저장하고, 이제 위 그림과 같은 "OSPF Network Topology"를 알게 됩니다.

 

3. R3가 자신의 링크 정보를 다른 OSPF 라우터들로 전파

 

 

 

R3는 자신의 Link(Interface) 주소와 Loopback 주소를 Router-LSA에 실어 R1, R4, R5로 전달하고[t = 1], 이를 수신한 R1, R4, R5는 Router-LSA가 수신된 링크를 제외한 나머지 링크로 Router-LSA를 flooding 합니다[t = 2]. 

 

R1, R2, R4, R5는 이 정보(Router-LSA)를 LSDB에 저장하고, 이제 위 그림과 같은 "OSPF Network Topology"를 알게 됩니다.

 

 

4. R4가 자신의 링크 정보를 다른 OSPF 라우터들로 전파

 

 

R4는 자신의 Link(Interface) 주소와 Loopback 주소를 Router-LSA에 실어 R2, R3로 전달하고[t = 1], 이를 수신한 R2, R3는  Router-LSA가 수신된 링크를 제외한 나머지 링크로 Router-LSA를 flooding 합니다[t = 2]. 

 

R1, R2, R3, R5는 이 정보(Router-LSA)를 LSDB에 저장하고, 이제 위 그림과 같은 "OSPF Network Topology"를 알게 됩니다.

5. R5가 자신의 링크 정보를 다른 OSPF 라우터들로 전파

 

 

 

R5는 자신의 Link(Interface) 주소와 Loopback 주소를 Router-LSA에 실어 R2, R3로 전달하고[t = 1], 이를 수신한 R2, R3는  Router-LSA가 수신된 링크를 제외한 나머지 링크로 Router-LSA를 flooding 합니다[t = 2]. 

 

R1 ~ R4는 이 정보(Router-LSA)를 LSDB에 저장하고, 이제 위 그림과 같은 "OSPF Network Topology"를 알게 됩니다.

 

 

역자 주 1: 실제로는 모든 라우터가 동시 다발적으로 자신의 Router-LSA를 OSPF neighbor들로 flooding 하지만, 본 설명에서는 이해를 돕고자 각 라우터가 순차적으로 Router-LSA를 보낸다고 하였습니다.

역자 주 2: 라우터의 링크 타입을 point-to-point로 설정(CLI)해야 Router-LSA가 나가게 되고, 그렇지 않은 경우(예. broadcast 타입) Network-LSA가 나가게 됩니다. 라우터간 링크 연결은 point-to-point가 일반적이므로 초보자님들께서는 Router-LSA만 생각하세요~*

 

각 라우터에서 OSPF Topology 그림 그리기

 

 

 

5개의 라우터들간에 Router-LSA를 주고 받게 되면, 모든 OSPF 라우터는 동일한 LSDB를 가지게 됩니다.

그리고 이 LSDB를 통해 위 그림과 같이 각 라우터는 모두 동일한 그림의 OSPF Topology Map을 완성합니다.

 

Shortest Path Tree 구성하기

 

 

 

위에서 생성한 OSPF Topology를 기반으로 각 라우터는 목적지(Destination Network)로 가는 최단 경로 즉, Shortest Path Tree를 구성합니다.

그리고 이렇게 만들어진 Shortest Path 정보가 라우터의 RIB(Routing Information Base)와 FIB(Forwarding Information Base)에 인스톨 됩니다. (참고: RIB는 OSPF와 같은 라우팅 프로토콜이 돌고 있는 Control Plane에서 관리하는 라우팅 테이블이고, FIB는 패킷을  포워딩(wire-speed packet forwarding by packet processor)하는 Data Plane에 위치한 라우팅 테이블입니다.)

 

OSPF에 대해 좀 더 자세히 알고 싶으신 분들을 위해 2권의 책을 추천드립니다.

• John T. Moy, "OSPF: Anatomy of an Internet Routing Protocol", 1998, Addison-Wesley
  • OSPF 창시자의 저서이고, 프로토콜 규격에 충실
• Jeff Doyle, "OSPF and IS-IS: Choosing an IGP for Large-Scale Networks", 2005, Addison-Wesley
  • OSPF와 IS-IS를 비교하였고, 또한 프로토콜 규격의 설명과 Cisco/Juniper 장비 설정도 함께 다루고 있음 (추천!)

 

OSPF External Network

 

 

 

■ OSPF 관점에서 External Network이란?

External Network이란 OSPF로 구성된 하나의 네트워크(AS 혹은 Routing Domain이라 부름)과 연결된 "외부 네트워크"를 말합니다. 즉, OSPF가 enable된 라우터간에는 Router-LSA(지난 시간에 설명), Network-LSA등으로 서로간에 라우팅 정보를 주고 받게 되고, OSPF가 enable되지 않은 망의 라우팅 정보는 External Network으로 분류되어 AS-External-LSA를 통해 External Network의 라우팅 정보를 OSPF 망에서 알 수 있게 됩니다. External Network의 예는 아래와 같습니다.

• BGP 망의 라우팅 정보
• IS-IS 망의 라우팅 정보
• Static route로 생성된 라우팅 엔트리 정보
• 라우터와 바로 직결된 Connected Network이지만 이 링크는 OSPF가 enable되지 않은 경우

 

이와 같이 External Network과 연결된 OSPF 라우터를 ASBR(Autonomous System Border Router)이라 부릅니다.

 

■ AS와 Routing Domain

보통 통신사업자는 망 내부 전체의 Intra-domain Routing 프로토콜로 OSPF나 IS-IS를 선택하여 운영하게 되는데, 이와 같이 동일 IGP 프로토콜로 운영되는 하나의 망을 AS 혹은 Routing Domain이라 부릅니다.

아래 내용에 따르면 AS 보다는 Routing Domain이란 표현이 더 일반적인 듯 합니다.

 

 

The IETF concept of autonomous system (AS) is, in ISO terms, a routing domain. I much prefer the second term. These days, an AS has a specific meaning in BGP networks, to differentiate one area of autonomous administrative control from another, and as entries interconnected by EBGP. Whthin a single AS, multiple IGPs can be running. In contrast, a routing domain is always the scope of a single set of routers speaking the same routing protocol to each other, unbroken by any other routing protocol

 

출처: Jeff Doyle, OSPF and IS-IS: Choosing an IGP for Large-Scale Networks, 2005, Addison-Wesley

 

OSPF Network Topology

 

 

 

그림 상에 5개의 OSPF 라우터(R1 ~ R5)가 존재하고, 라우터간 연결 링크에 대한 IP 주소와 OSPF Link Cost 및 각 라우터의 OSPF Router ID(RID)인 Loopback 주소(예. R1의 경우 10.1.0.1/32)가 표시되어 있습니다.

• 각 라우터간 파란색 링크가 OSPF가 enable되어 있음을 표시하고 있고,
• 회색 링크는 OSPF가 enable되어 있지 않음을 표시하고 있습니다.

즉, R1에 직결된(connected) 100.1.1.0/24는 External Network이고, R2에서 라우터(회색 라우터)를 거쳐 연결된(static route) 200.1.1.0/24도 External Network이 됩니다.

 

앞서 설명 드린바와 같이 External Network과 연결되는 OSPF 라우터를 "OSPF 망의 가장자리(Border)에 위치한 라우터"의 의미로 ASBR(Autonomous System Border Router)이라 부릅니다.

 

ASBR: External 라우팅 정보를 OSPF 내부 라우터들로 전파

 

1. R1이 External Network (Connected Network) 정보를 전파

 

 

 

R1의 설정(redistribute connected subnets)에 의해서 External Network 100.1.1.0/24 정보가 AS-External-LSA를 통해 R2, R3로 전파됩니다[t=1]. 그리고 이를 수신한 R2, R3는 본 AS-External-LSA가 수신된 핑크를 제외한 링크로 AS-External-LSA를 flooding 합니다. 그래서 R4, R5는 동일한 AS-External-LSA를 2개씩 수신하는데[t=2], 이 경우 LSA 식별자인 {LS Type, Link State ID, Advertising Router}가 동일한 경우 두번째 수신한 LSA를 폐기합니다.

• LS Type: Router-LSA(1), Network-LSA(2), AS-External-LSA(5) 등의 LSA 타입을 구분
• Link State ID: AS-External-LSA인 경우 External Network 주소의 Prefix (address prefix of the external route)
• Advertising Router: AS-External-LSA를 생성한 라우터의 ID (R1 OSPF RID, 즉, R1의 Loopback 주소인 10.1.0.1)

 

R1이 보낸 AS-External-LSA에 포함된 정보는 다음과 같습니다.

• Network Mask: External Network의 subnet mask (255.255.255.0)
• Metric: External Network과 OSPF Network 사이의 Link Cost (35)

 

이와 같이 R1이 보낸 AS-External-LSA를 R2 ~ R5가 수신하게 되면 각 라우터는 그 정보를 OSPF LSDB(Link State DataBase)에 저장하고 OSPF Network Topology 상에 해당 External Network으로 가기 위한 Shortest Path Tree를 구성하게 됩니다 (맨 밑에 그림 참조).

 

2. R2가 External Network (Static Route) 정보를 전파

 

 

 

R2의 설정(200.1.1.0/24로 가기 위한 static route 및 redistribute static subnets)에 의해서 External Network 200.1.1.0/24 정보가 AS-External-LSA를 통해 R1, R4, R5로 전파됩니다[t=1]. 그리고 이를 수신한 R1, R4, R5는 본 AS-External-LSA가 수신된 링크를 제외한 링크로 AS-External-LSA를 flooding 합니다. 

 

R1, R3, R4, R5는 이 정보(AS-External-LSA)를 LSDB에 저장하고, OSPF Network Topology 상에 해당 External Network으로 가기 위한 Shortest Path Tree를 구성하게 됩니다 (맨 밑에 그림 참조).

 

역자 주: External Route를 OSPF 망으로 전파할때 2가지 옵션(External Type 1 & External Type 2) 중에 하나를 선택할 수 있습니다. 위 그림의 설정은 External Type 1(CLI 상에 metric-type 1)으로 예를 든 것입니다. 이 2가지 옵션에 대해서는 다음 기회에 설명을 드리도록 하겠습니다.

 

R1 ~ R5: Shortest Path Tree 구성하기

 

 

 

위에서 설명한 2개의 External Network(100.1.1.0/24, 200.1.1.0/24)에 대해 각 라우터는 최단 경로 즉, Shortest Path Tree를 구성하고, 이렇게 만들어진 Shortest Path 정보 즉, External Network Prefix와 최단경로로 가기 위한 Next Hop 정보가 라우터의 RIB(Routing Information Base)와 FIB(Forwarding Information Base)에 인스톨 됩니다. (예. R5는 External Network 200.1.1.0/24로 가기 위한 최단경로상의 Next Hop은 R2(1.1.5.1)이고, 100.1.1.0/24로 가기 위한 최단경로상의 Next Hop도 R2(1.1.5.1)임) 

 

SPF Tree caclulation

 

광고 수익은 기부 활동에 사용됩니다

정보를 얻으신 분들은 광고 클릭 부탁드려요 :)