LSR(Link state routing)

이 라우팅 방식은 라우터가 껐다 켜졌을 때 다음과 같은 순서로 진행된다.

1. Neighbor를 찾고 그들의 네트워크 주소를 학습한다.

내 주변에 있는 라우터들의 정보를 얻는 과정이다. 이를 위해 자신의 모든 인터페이스로 HELLO라는 메시지를 담은 패킷을 전송한다. 그러면 이 HELLO 패킷을 받은 라우터는 자신이 누구인지를 담아 다시 회신해준다.

2. Neighbor 각각의 delay나 cost를 측정한다.

연결된 Neighbor 라우터까지의 delay를 측정하기 위해 ECHO 패킷을 보낸다. 이걸 받은 라우터는 받자마자 바로 다시 회신을 해준다. 이렇게 되면, ECHO 패킷을 보낸 시점과 Response를 받은 시점 간의 시간 차이를 반으로 나누면 해당 인접 라우터까지 걸리는 Cost값을 알 수 있다.

예를 들어, A가 B에게 ECHO를 보내고 10초 뒤에 Response가 왔다면, A에서 B까지의 거리는 5초만큼의 값을 가지는 길이라고 할 수 있다.

근데, Packet을 사용하는 네트워크에서는 문제가 생긴다. 때에 따라 5초만에 인접 라우터까지 도달할 수도 있지만, 네트워크 상황에 따라 3초가 걸릴 수도, 8초가 걸릴 수도 있게 된다. 이런 이유로 1번만 패킷을 보냈을 때는 확실하게 알 수가 없기 때문에 여러 번 패킷을 보내어 cost의 평균치를 찾는다.

하지만, 보통은 이렇게 Dynamic하게 코스트를 설정하지 않고, 관리자가 직접 Static하게 설정한다.

3. 지금까지의 정보를 토대로 Packet을 만든다.

Link state packet이라는 것을 만든다. 이 패킷은 자신의 인접 라우터와 각 인접 라우터와의 cost값을 기반으로 만들어진다.

4. 이 패킷을 다른 모든 라우터에게 전송한다.

Link state packet을 다른 모든 라우터들에게 Broadcast 시킨다. 이를 Flooding이라고 한다. A가 Flooding을 했다고 하면, 인접 노드들 뿐만 아니라 다른 모든 노드, 즉 모든 라우터들에게 A의 link state packet이 도달하게 되고, 이 라우터들은 이제 각자의 cost matrix를 만들 수 있게 된다. 이 cost matrix가 이제 Algorithm의 입력값으로 들어가, Shortest Path를 찾을 수 있게 된다. 이때, LSP를 Flooding 하는 범위는 하나의 AS 범위이다.

Flooding
패킷을 받은 포트를 제외한 다른 모든 포트로 패킷을 Broadcast하여 모든 인접 라우터들에게 패킷을 전달하는 것

Cost matrix 예시

5. 모든 다른 라우터들로 가기 위한 Shortest path를 계산한다.

이제는 이 Cost matrix를 입력값으로 하여 Dijkstra 알고리즘을 통해 다른 모든 노드들과의 Shortest Path를 구성한다. 여기서 Bellman-Ford나 Floyd Warshall 알고리즘이 아닌 Dijkstra 알고리즘을 사용하는 이유는 뭘까?

그 이유는 간단하다. 이 Dijkstra 알고리즘이 가장 Computation time이 적게 소요되기 때문이다. 즉, 가장 빨리 끝나는 알고리즘이 Dijkstra 알고리즘이기 때문에 이 알고리즘을 사용한다.

LSR을 정리해보면 다음과 같은 순서로 동작한다.

1. Neighbor를 찾고 그들의 네트워크 주소를 학습한다.
2. Neighbor 각각의 delay나 cost를 측정한다.
3. 지금까지의 정보를 토대로 Packet을 만든다.
4. 이 패킷을 다른 모든 라우터에게 전송한다.
5. 모든 다른 라우터들로 가기 위한 Shortest path를 계산한다.

이런 식으로 동작하는 라우팅 방법을 LSR(Link state routing) 방법이라고 한다.

OSPF

앞선 포스트에서 다뤘던 라우팅 방법은 Distance vector routing algorithm(Distributed Asynchronous Bellman-Ford Algorithm)방식을 기본으로 하는 RIP이었다. 한편, RIP처럼 대표되는 프로토콜 중 LSR을 사용하는 가장 대표적인 라우팅 프로토콜은 OSPF가 있다.

OSPF는 LSR을 기반으로 하는 Intradomain routing protocol이다. 쉽게 말하자면, LSR을 기반으로 하나의 AS에서 동작하는 라우팅 프로토콜이다. 즉, Interior routing protocol이라는 말이다.

Intradomain이라는 것은 KT, SKT, LG와 같은 한 회사들이 관리하는, 그 회사 내에서 동작하는 도메인을 말한다. 이를 AS라고 하는 것이고, Intradomain routing protocol은 이 Intradomain, 하나의 AS 내에서 동작하는 프로토콜이다.
반대로 AS 간 통신에 사용되는 프로토콜은 Interdomain routing protocol로 BGP라는 프로토콜이 있다.

Types of Links

Link의 종류에는 다음과 같이 4개의 종류가 있다.

Point to Point

두 개의 라우터가 1대1로 연결된 것으로, 이 Link에서는 Network address를 할당할 필요가 없다. 주소라는 것은 특정 상대방에게 보내기 위해서 사용하는 건데, 이 경우에서는 주소가 없어도 상대 라우터가 이미 정해져있기 때문에 그냥 보내면 되기 때문이다.

Transient

하나의 이더넷과 같이 여러 라우터가 연결된 Link이다. 이 경우에는 데이터를 보내면 이 Link에 연결된 모든 라우터들이 이 정보를 받을 수 있기 때문에 라우팅이 필요해지고, 주소 역시 필요해진다. 이때, LSR에서는 Neighbor 라우터들을 가장 먼저 찾는다고 했다. 그러나, Transient 구조에서는 Neighbor가 너무 많다는 문제가 생긴다. 이를 해결하기 위해 라우터들 가운데에 논리적인 라우터를 하나 만든다.

실제 라우터는 아니지만, 논리적으로 라우터가 하나 있다고 가정해서 본다면 Transient 구조에서 Neighbor 라우터가 너무 많아지는 문제를 해결할 수 있다. 이 논리적인 라우터는 실제로 존재하는 라우터가 아닌 논리적인 개념이기 때문에, 실제 라우터 중 한 라우터가 이 역할을 대신해준다. 이 역할을 하는 라우터를 Designated router라고 한다.

그렇다면 이 Designated router를 선정하는 기준이 따로 있을까? Designated router는 Transient 구조에 연결된 라우터들 중 가장 높은 우선순위를 가지는 라우터가 하거나, Router ID가 가장 높은 라우터가 하게 된다.

Stub & Virtual

Stub 구조는 네트워크가 오직 하나의 라우터에 연결된 구조를 말한다.

Virtual은 여러 네트워크들이 하나의 가상적인 링크로 연결되어 있는 구조로, VPN이 이러한 구조를 사용한다. 이 부분은 내용이 길어지기 때문에 다루지 않는다.

AS Example

다음과 같은 구조를 생각해보자.

• P2P : (A, D), (B, E)
• Transient : (A, B, C), (D, E, F)
• Stub : C, E, F

여기에 Network address를 할당하고, 호스트들에게 Host ID를 할당한 후, 특히 Transient Link의 경우에서 Designated router를 선정해보자.

Designated Router는 가장 높은 Router ID를 가지는 라우터가 수행한다고 했다. 그렇다면 이 Router ID는 어떻게 정해지는걸까?

• 관리자가 직접 설정
• 관리자의 설정이 없으면 라우터가 가진 인터페이스들의 IP address 중 가장 높은 address값을 Router ID로 사용한다.

그래서 C 라우터의 경우를 보면, N1과 N2 모두에 연결되어 있고, C 라우터의 인터페이스 IP address 중 가장 큰 값은 N1에 연결된 2.0.0.1/8 주소가 N2에 연결된 1.0.0.1/8보다 크기 때문에 2.0.0.1이 C 라우터의 Router ID가 된다.

이렇게 되면 A, B, C가 연결된 Transient Link에서 Designated router는 Router ID가 가장 높은 A 라우터가 되는 것이다.

Types of OSPF Packets

이런 종류들이 있다. 각 패킷들은 LSR의 각 단계에 맞추어 동작된다. 이 중 Hello 패킷과 Link state update 패킷을 자세히 다뤄보자.

Hello message

Hello message는 내 옆에 어떤 라우터가 있는 지를 확인하기 위해, 즉 인접 라우터를 파악하기 위해 보내는 메시지이다. 이 경우에서는 A 라우터가 D에게 자신의 Router ID를 전달하면, D 라우터는 이 request를 받아 역시 자신의 Router ID를 담아 다시 reply해주는 상황이다.

이 Hello message 교환이 끝나면 각 라우터들은 자신의 Neighbor 라우터의 Router ID를 알 수 있게 된다.

이번에는 Transient의 경우이다. Transient에서도 똑같이 Hello 메시지를 보내는데, 이때는 Broadcast하게 보내어 이 Link에 연결된 모든 라우터들이 이 Hello 메시지를 받을 수 있도록 한다.

그 후에는 Transient는 Designated router를 선정한다. 이 Designated router가 선정되어야 Transient 구조에서는 라우터들이 자신의 Neighbor 라우터를 확정지을 수 있기 때문이다.

이 그림에서는 E의 Router ID가 가장 크기 때문에 E가 Designated router가 된다. 주의해야 할 점은 이 Designated router는 논리적으로 라우터가 하나 더 있다고 생각하는 것이라고 했다. 그렇다면 이 논리적인 Designated router에도 Router ID가 필요하다. 이것을 Link ID라고 하는데, E의 Router ID를 그대로 사용하는 것이 아니라 Designated router 위치(N3 위치)에서 E와 연결된 인터페이스 주소, 즉 3.0.0.2가 Designated router의 Link ID가 된다. 이렇게 되면 DR의 Neighbor는 D, E, F이지만, 각 라우터들의 Neighbor은 ID를 3.0.0.2로 가지고, N3 위치에 있는 Designated router만 Neighbor 라우터로 존재할 수 있게 된다.

Link state update packet

LSR에서는 라우터들 간 Hello 메시지 교환이 끝나면, 이 정보들을 모아 다른 라우터들에게 Broadcast 시킨다고 했다. 여기서 라우터가 자신의 인접 라우터와의 관계를 정의하는 것을 LSA, Link state advertisement라고 하고, 이 LSA들을 모아 다른 라우터들에게 보내는 패킷을 Link state update packet이라고 한다.

말이 좀 어렵다... 쉽게 말해보자면, D의 인접 라우터에는 E와 F가 있다. 그러면 D는 자신과 E의 관계에 대해 정의하고, 또 D와 F와의 관계에 대해서도 정의할 것이다. 이 각각의 정의를 담은 메시지를 LSA라고 하고, 이 LSA를 하나로 모아 다른 라우터들에게 보내는 하나의 패킷이 Link state update packet인 것이다.

여기서 말하는 관계를 정의한다라는 표현은 LSA의 종류별로 정의하는 것이 다르다.

LSA의 종류는 Router Link LSA와 Network Link LSA로 나뉜다.

Router Link LSA

실제 라우터의 링크를 정의하는, 즉 자신이 직접적으로 연결되어 있는 링크에 대한 정보를 만들기 위해 사용하는 것이다. Router LSA에 포함되는 내용은 다음과 같다. 이때, Link Type에 따라 들어가는 정보가 조금씩 다르니 주의해야 한다.

• Number of router link - Router link의 개수로 해당 라우터에 연결된 Link의 개수를 말한다.
• Link Types
• Link ID
• Link Data
• Metric

이 경우를 다시 살펴보자. 먼저 F가 보내는 Router Link LSA를 보자면,

• Number of router link = 2

  • Link Type = 3(stub)

  • Link ID = 4.0.0.0

  • Link Data = 255.0.0.0

  • Metric = 5

    ---

  • Link Type = 2(transient)

  • Link ID = 3.0.0.2(DR의 Link ID, 즉 DR의 IP 주소)

  • Link Data = 3.0.0.3(DR과 연결된 F의 interface 주소)

  • Metric = 9

이렇게 된다. 이번에는 D가 보내는 Router Link LSA를 보자.

• Number of router link = 2

  • Link Type = 1 (p2p)

  • Link ID = 2.0.0.3 (연결된 인접 라우터 인터페이스의 IP 주소)

  • Link Data = 1 (임의로 정한 Interface 번호)

  • Metric = 8

    ---

  • Link Type = 2(transient)

  • Link ID = 3.0.0.2(DR의 Link ID, 즉 DR의 IP 주소)

  • Link Data = 3.0.0.1(DR과 연결된 F의 interface 주소)

  • Metric = 2

헤더는 두 경우 모두에서 type = 1로 고정이다. 이 type은 LSA가 router link LSA임을 나타낸다.

E가 보내는 Router Link LSA도 생각해보자.

Network Link LSA

이번에는 Network Link LSA이다. 이 Network Link LSA는 Designated router가 보내야 할 LSA를 실제 라우터가 대신 보내주는 LSA를 말한다. Designated router는 실제 존재하는 라우터가 아닌 그저 선 위에 가상의 라우터가 있다고 생각한 것이기 때문에, 이 가상의 논리 라우터가 직접 LSA를 보낼 순 없으니 이 Designated router 역할을 대신 하던 실제 라우터가 보내는 LSA인 것이다. 즉, 내 네트워크에 실제로 어떤 라우터가 접속되어 있는가를 나타내는 것이다.

이 Network Link LSA에서는 LSA 헤더값은 type = 2와 Designated router의 IP주소가 Link state ID로 들어가고, 데이터 필드에 포함되어야 할 정보는 서브넷 마스크 값과 네트워크에 연결된 라우터들의 Router ID들을 전부 적어서 보낸다.

여기서 Network Link LSA는 Designated router 역할을 대신 하고 있던 E가 보낸다.

• Header
  • type = 2(network link)
  • Link state ID = 3.0.0.2 (DR의 IP 주소)
• Network link advertisement
  • network mask = 255.0.0.0
  • attached router ID = 3.0.0.1 / 4.0.0.1 / 5.0.0.1

이렇게 E가 보내는 Network Link LSA를 구성할 수 있다.

Another LSAs

이외에도 여러 LSA가 더 존재한다. 지금부터 소개되는 LSA들은 네트워크의 크기가 굉장히 커지면서 사용되는 LSA들이다. 예를 들어, 통신 3사들이 관리하는 네트워크의 규모는 전국을 커버하기 때문에 매우 크다. 이렇게 네트워크 규모가 커지게 되면 관리가 불편하기 때문에 관리의 용이성 등의 이유로 AS를 여러 개의 Area로 나누게 되고, 지금부터 나오는 LSA들은 그 Area 간이나 AS 간에 사용되는 LSA들이다. 간단히 언급 정도만 하겠다.

• Summary Link to Network LSA
  
  Area에서의 게이트웨이 라우터는 Border router라고 한다. 이 LSA는 Border router가 한 OSPF Area의 경로 정보를 다른 Area로 요약해서 전달하는 LSA이다. 이 LSA를 통해 Area는 외부 네트워크들에 대한 정보를 알 수 있게 되고, 다른 Area들도 해당 Area의 정보를 Flooding 받아 알게된다. 이 LSA의 Header type 값은 3이다.

• Summary Link to AS Boundary Router LSA
  
  AS의 게이트웨이 라우터는 AS boundary router라고 한다. 이 LSA는 각 Area의 Border router와 AS Boundary router 사이의 경로 cost값을 알려주기 위한 LSA이다. 이 LSA는 Header type 4번으로 가진다.

• External Link LSA
  
  AS 외부의 네트워크들에 대한 정보를 외부에서 AS 내부로 Flooding해주는 LSA이다. 이 LSA는 Header type 5번을 가진다.