TIL 2021-12-02 RIPv2, OSPF

RIP 장점

대역폭, 설정, 관리시간의 측면에서 overhead가 작다.

실행하기 쉬움

 

RIP는 벨만포드나 DV 알고리즘 기반의 routing protocol이다.

 

Route Selection에 hop count 사용함

hop count가 15 넘으면 discard함

 

default로 routing update는 30초마다 broadcast하는 것

 

이 프로토콜은 가장 긴 path가 15 hop으로 제한함

 

대체 라우트와 비교할떄 fixed metrics(hop count)를 사용함

 

이것은 RIP의 약점이지 DV의 약점은 아님. (Delay, bandwith 등 고려 안하고 hop만 봄)

 

많은 DV 알고리즘은 이런 문제가 없음

 

RIPv2

 

시스템의 모든 가능한 경로에 entry가 포함된 테이블을 유지한다

 

entry에는 Destination에 대한 거리 d와 거기로 가기 위한 첫 라우터 G가 있음

 

기간마다 routing update를 모든 neighbor에게 보냄

 

만약 neighbor G로부터 routing update가 도착하면 G와 공유하는 네트워크의 코스트를 더함

 

현 routing entry와 결과 거리 D'를 비교함

만약 현재 거리보다 새 거리가 더 작다면 새 라우트를 적용함

 

G=G'면 이전꺼보다 커도 새 metric를 사용함

 

 

Next hop field

 

0.0.0.0

만약 자신이 준 RIP update를 가지고 자기의 Routing table을 업데이트할꺼면 내 라우팅 hop에 새로 계산되는 next hop 주소는 RIP를 보낸 originator가 됨

 

Appendix A에 나온 상황에서 

 

Counting to Infinity

 

Routing Update 전에 해당 라우터를 거쳐야하는데 그 라우터 경로가 맛이 간 경우에 발생함

 

B가 맛이 갔는데 C가 B를 통해서 D로 보내려했다면 B는 B->D를 무한대로 바꾼 값과 C-D의 값을 다시 계산하여 C로 다시 보낸다.

 

<TN:X metric a>가 원하는 목적지에 가고 싶으면 TN로 가면 된다, 그리고 그 값을 a라고 표현한다라고 하자.

 

C:<TN:B metric 3>이라고 보내면 B<TN, _, unreachable>인 상태이므로

 

B는 C->D의 비용이 3이라고 알고 있기에 C->D로 가는게 더 빠르다고 생각한다.

<TN:C, metric(3+1)>을 다시 C에게 보낸다.

 

하지만 C의 metric에서 C->D는 10이기 떄문에 <TN:B, metric(4+1)>을 다시 B에게 보낸다....

 

Route update가 30초에 한번 벌어지게 되어서 이런 반복적으로 패킷 이동만 하는 현상이 발생함

 

Split Horizon

 

라우터가 metric을 학습한 곳으로 update를 보내지 않아서 문제를 피하는 방법

 

routing loop를 피하기 위한 DV 라우팅 프로토콜에 사용되는 방법중 하나다.

 

문제

 

라우터 1,2,3와 Destination이 순서대로 있다고 하자

2가 2->3의 연결이 끊어졌다고 1에게 보내려고 하는데 그전에 이미 2은 1에게서 metric을 학습한 상황을 가정하자.

그러면 Split horizon에 의해 2->3이 끊어졌다는 것을 1에게 보내지 않기 때문에, 2는 계속 1에게 다른 경로가 있을 것이라고 생각하고 패킷을 보낸다.

1은 2->3이 끊어졌다는 것을 학습하지 않았기 떄문에 계속 2로 패킷을 보낸다.

이러면 루프가 생김

 

Route Posioning , Posion Reverse

 

Router B가 C에게 routing table을 forward해도 Route posioning아래서 routing 정보를 안받아드림

Holddown time이 작동하고 있기 떄문

그리고 ICMP로 10.4.0.0이 도달할 수 없다고 notify함

 

posion reverse는 무한대로 세팅해서 보냄

 

Split horizon, route posion은 2개의 라우터 상에서는 루프 방지할 수 있으나 3개가 상호작용하는 순간부터는 루프 발생 가능성이 있다.

 

primary purpose는 network convergence 속도를 향상 시켜서 loop을 방지하는 것

 

Triggered Update goal

 

-Convergence speed improvement

 

만약 라우터가 metric을 바꿨다면 거의 바로 즉시 update message를 보냄(정기 update 시간이 아니어도)

 

똑같은 G에서 왔다면 크던 작던 업데이트함

결과적으로 바뀌었다면 직접적으로 연결된 router들에게 trigger함

그리고 cascade하며 다 업데이트됨

 

Protocol Specification

 

RIP는  IPv4 기반 네트워크를 통해 라우트 계산에 필요한 정보들을 교환하게 해줌

그 정보중 제일 중요한 것은 metric이고 1~15의 값을 가짐

RIP를 구현한 라우터는 Routing table을 가진다고 여겨짐

 

각 Entry는

• 서브넷 마스크와 DST에 대한 IP 주소
• metric(라우터에서 목적지까지의 총 비용)
• DST에 가기 위해 가야하는 다음 라우터 IP 주소
• route가 최근에 바뀌었는지 표시할 flag
• outgoing 인터페이스 숫자

 

directed connected networks의 entries는 RIP에 지정되지 않은 방법으로 수집된 정보를 통해서 설정됨

 

directly connected network의 metric은 그 네트워크까지의 비용으로 설정됨

 

1이 평범한 값이다

더 복잡한 metric이 특정 네트워크의 선호를 표시하기 위해 설정될 수 도 있음

 

RIP Format

 

최대 504octets 4 +  20*25 (RIP Entry size(20octet)) + IP(20) +UDP (8) =504

 

 

OSPF

 

Link state routing protocol

 

각 OSPF 라우터는 동일한 DB를 유지함

DB로부터 가장 짧은 Path가 건설되어 routing table이 계산됨

하나의 Autonomous System에 의해 내부적으로 작동하도록 디자인됨

 

 

장점

 

topologies 변화에 빠르게 계산됨(Convergence time 적음)

추가적인 routing protection과 routing protocol traffic의 감소를 가능케 하면서 area routing capablity가 제공된다.

 

 

 

Hierarchial Routing Protocol

2-tier:

backbone area(Area 0)

Non-backbone Area

 

inter-area routing을 위한 Link state Protocol

Inter-area간의 link-state routing이 아님

 

 

Classfication of routers

 

Internel Router(normal routers)

같은 네트워크 안에 속해있는 모든 directly connected 네트워크가 있는 router

 

Area border router(ABR)

여러 area에 붙어있는 router(대체로 backbone area의 인터페이스를 가짐)

 

Backbone router

backbone에 연결되어있는 라우터

 

AS Boundary routers

다른 AS(Autonomous Systems)에 속해있는 라우터들과 정보를 교환하는 라우터

 

Network의 종류

 

Transit Network: 2개 이상 OSPF router가 연결된 네트워크

Stub network : OSPF 라우터가 딱 하나 연결된 네트워크

 

//// 혹은 이렇게도 나눌 수 있음

 

Point to point networks

 

Broadcast networks(DR/BDR 필요)

 

Non-broadcast Networks

많은 라우터가 붙어있는 네트워크지만 broadcast 능력이 없음.

두개의 모드

non-broadcast multi-access(NBMA)（DR 선출 필요)

broadcast네트워크의 OSPF 작동을 시뮬레이션함

Point to MultiPoint

point to point 링크의 모음

 

Termininology

Neighbor router

공통된 네트워크가 있는 라우터

 

Adjaceny

routing 정보 교환하기 위해 선택된 neighboring router간에 형성된 관계

 

DR이 선출되면 DR하고면 LSA를 주고받을수 있음

 

BDR은 DR하고만 연결할 수있음

 

Topology는 directed graph로 나타남

 

graph의 verticle은 Router와 network를 가지고 있다.

 

transit network는 incoming, outgoing edge를 가지는 것으로 나타난다.

stub network는 incoming edge만 있음

 

graph edge는 두 라우터가 point to point network로 연결되어 있을떄 연결됨

 

네트워크 나가는 cost는 없고 들어가는 cost는 있ㅇ므

 

OSPFv2는 2-tier hierarchial routing protocol이다

 

inter-area routing의 경우에는 topology db를 사용하고 다익스트라 같은 알고리즘을 사용하여 db로부터 SPF tree를 만듦

 

inter area와 exterior AS routing의 경우에는 topology 정보를 더함

 

<Area border GW, destination, aggregated cost>

 

 

LSA TYPE

 

1. Route LSA(TYPE1)

모든 라우터가 자신과 연결된 link 정보를 담아 만든 LSA

 

2.Network LSA(TYPE2)

DR로 선출된 라우터가 자신과 연결된 모든 link 정보를 담아 만든 LSA

 

3.Network summary LSA(TYPE3)

ABR이 Area간에 정보를 교환하면서 생성하는 LSA(다른 Area Network 정보)

->다른 Network의 topology를 구성할 필요는 없으니 Network정보만

 

4. ASBR Summary LSA(TYPE4)

ABR이 LSA TYPE5 정보를 전달하면서 생성하는 LSA(ASBR 라우터 정보)

->ASBR이 어디 있는지를 알려줌

 

5. Externel LSA(TYPE5)

ASBR이 타 라우팅 프로토콜의 Network 정보를가져오면서 생성하는 LSA(외부 네트워크 정보)

->다른 Network의 topology를 구성할 필요는 없으니 Network정보만

 

 

3은 다른 Area, 5는 외부에 정보를 주는거, 4는 외부로 나가기 위해 ASBR이 어디 있는지 알려주는거

 

Inter-area Topology

Router-LSA1.) router information

Network-LSA2).transit network information(TYPE2는 DR이 함)

 

Inter-area Reachablity Information

Summary-LSA

3,4

 

Exterior-AS Reachablity Information

AS-Externel-LSA(5)

 

 

 

1. R1가 다른 OSPF 라우터들에게 link 정보를 보냄

2.각 OSPF 라우터들은 R1에서부터 온 Router LSA를 받고 LSDB를 만듬

3.R2가 다른 OSPF 라우터들에게 link 정보를 보냄

4.각 OSPF 라우터들은 R2에서부터 온 Router LSA를 받고 LSDB를 만듬

5. R5까지 반복

6. 5번 Router LSA를 교환하면 모두 같은 LSDB를 가지고 있음

7. LSDB로 모두 같은 OSPF Topology map를 구성함

8. 만들어진 map으로 최단거리 계싼

9. 마지막으로 계산된 최단거리를 routing table에 설치함

 

Header Format

 

IP에 올림

 

IP Header 안에 OSPF Packet Header가 있음

 

Version: OSPF version number(v2니까 2)

Type: OSPF Packet TYPE( LSA TYPE 아님)

Router ID: 패킷 소스의 Router ID

Area ID: 패킷이 속해있는 area의 32bit 식별 주소

checksum

 

TYPE

 

Hello(1)

각 인터페이스마다 neighbor찾음

 

Database Description(DD) (2)

DB의 요약이 있는 Database Description

 

Link state Request(3)

LSA 헤더 보내서 LSA 요청함

 

Link State Update(4)

데이터베이스에 full LSA들 옮김

LSA 요구되거나 기간마다 flood됨

 

Link State Ack(5)

Link State Update에 의해 옮겨지는 LSA들 ACK함

 

 

Identifier : <LS TYPE, Link State ID, Advertising Router>

Age: <LS Sequence Number, LS Checksum, LS Age>

new: sequence number 크면 checksum 큼

 

Link State advertisement(LSA)

Router-LSAs(TYPE=1)

모든 라우터가 생성함

area에 수집된 router들의 인터페이스들을 말함

single area에서만 flooded함

 

Network-LSAs(TYPE=2)

DR에 의해 broadcast, NBMA에서 생성됨

네트워크에 연결된 라우터들의 목록을 가지고 있음

single area에서만 flooded함

 

Summary-LSA(3,4)

3: area border router에서 생성됨

4: ASBR boundary router에서 생성됨

 

AS-externel-LSA(5)

AS boundary router에서 생성됨

AS에서 flooded됨