네트워크 계층 - 라우팅 알고리즘

라우팅 알고리즘

• 라우터는 forwarding table을 룩업해서 패킷의 IP주소와 매칭 되는 다음 router를 찾아 전달한다. (longest prefix matching)
• 이때, forwarding table은 특정 알고리즘에 따라 구성되는데 이 알고리즘을 라우팅 알고리즘이라고 한다.
• 라우팅 알고리즘은 네트워크를 그래프로 추상화하고 시작지점과 목적지까지의 최소 비용을 구하는 알고리즘이다.
• 라우팅 알고리즘은 크게 두 개로 구분되는데 모든 그래프 정보를 아는 상태로 계산하는 방법(global)과 인접한 노드의 정보만으로 계산하는 방법(decentralized)이 있다.

AS

• AS(astonomous systems)는 routing 알고리즘을 공유하는 router 집합을 의미한다.
• 네트워크는 AS간 연결로 구성되어있다.
• 각각의 AS는 독립된 네트워크로 내부적으로 사용되는 라우팅 알고리즘을 결정해 공유한다.
• AS 간에는 서비스를 제공받는 customer와 서비스를 제공하는 provider 관계와 동등한 관계인 peer 관계가 존재한다.
• 맺어진 관계에서만 트래픽 이동이 가능하다.

Intra-AS 알고리즘

• AS 내부에서 사용되는 알고리즘
• 대표적으로 Link State 알고리즘과 Distance vector 알고리즘이 있다.

Link State 알고리즘

• 모든 그래프 정보를 알고 있는 상태로 최소 비용을 구하는 알고리즘
• 모든 노드들이 자신과 연결되어있는 노드들의 정보를 broadcast해서 네트워크 전체 정보를 공유하고 있는 상태를 가정한다.
• 다익스트라 알고리즘을 사용한다.
• 전세계 모든 라우터들이 각 라우터의 링크 정보를 broadcast해 다익스트라 알고리즘으로 forwarding table을 구성하는 것은 불가능하다.
• 소규모의 같은 도메인을 공유하는 독립된 네트워크에서 사용할 수 있다.
• OSPF가 Link state 알고리즘을 기반으로 하는 프로토콜이다.

Distance vector 알고리즘

• 인접한 노드의 정보만으로 계산하는 알고리즘
• dx(y) = min(c(x,v) + dv(y)) => x에서 y까지 가는데 걸리는 최소값은 x에서 v까지 가는데 드는 비용과 v에서 y까지 가는데 드는 비용을 더한 최솟값
• dv(y)는 알 수 없기 때문에 v부터 recursive하게 계산해서 최솟값을 구해야한다.
• 각 노드는 인접한 노드까지 가는 cost만 계산하고 해당 결과를 다른 노드들에게 전달한다.
• 다른 노드로 부터 받을 결과로 cost를 재계산하고 min cost에 변화가 있는 경우 다시 전달한다.
• 모든 노드의 min cost가 변화가 없을 때까지 반복한다.
• count to infinity : cost가 늘어나는 경우 인접한 노드가 계산한 값이 자신에게 되돌아오는 reverse path라는 것을 모른채 최소 비용 경로를 재계산하게 되면 인접 노드와 데이터를 계속 주고받는일이 발생한다.
• poison reverse : 인접한 노드의 cost 값이 자신을 거쳐 가는 경로를 계산한 경우라면 해당 값은 무한대로 전달받아야 count to infinity 문제를 막을 수 있다.
• link state 알고리즘 처럼 전체 네트워크 정보를 받아 forwarding table을 구성하는 것은 불가능하기 때문에 소규모의 독립된 네트워크에서 사용 가능하다.
• RIP가 Distance ventor 알고리즘을 기반으로 하는 프로토콜이다.

Inter-AS 알고리즘

• 서로 다른 AS를 routing하는 데 사용하는 알고리즘이다.
• 대표적으로 BGP 프로토콜이 있다.

BGP (Border Gateway Protocol)

• Intra AS 처럼 최단 경로를 따라 움직이지 않고 각 AS간 관계에 따른 정책에 맞게 트래픽을 운반한다.
• 가장 빠르게 전달하는 것이 목적이 아닌 각 AS가 취할 수 있는 가장 큰 경제적 이득에 맞춰 경로를 선택하는 프로토콜