해당 포스팅은 한양대학교 이석복 교수님의 컴퓨터네트워크 강의를 정리한 글입니다.
http://www.kocw.net/home/search/kemView.do?kemId=1169634

1. Routing algorithm classification

• 라우팅 알고리즘은 두가지로 나누어진다.

1. "link state" algorithms - 모든 라우터를 알 수 있는 것이다. (다익스트라 알고리즘)
2. "distance vector" algortithms - 주변 라우터만을 알 수 있는 것이다. (벨만포드 알고리즘)

1) Link State Algorithm (다익스트라)

• 알고리즘은 생략. 아래 로직을 반복하면 된다.

• 자신과 모든 링크에 대한 정보를 가지고 시작하는 알고리즘이다.

  1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문)
  2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다. 

• 한가지 문제점은oscillation이라는 문제가 발생할 수 있다.
  

• 초기에는 D->A, C->B->A 의 경로를 선택,

• 이후에 link state algorithm 을 한번 더 수행하면서 처음의 결과를 토대로 B->C->D->A로 방향을 선택한다.

• 이후에 또 수행하면 이전의 결과를 토대로 반대방향으로 계속되며 진동하는 것이다.

2) Distance vector algorithm (벨만포드)

• 자신과 이웃한 링크에 대한 정보를 가지고 시작한다.
• 이웃 노드와의 정보 교환을 통해 점진적으로 최소 비용을 계산하는 방식이다. (Dynamic Programming)
• 알고리즘은 생략, 점화식은 다음과 같다.
  

a. link cost changes

• 링크 비용이 link cost가 변화함에 따른 전파속도 차이가 존재한다.

1. 감소하는 경우
   y가 처음 가진 정보는 Dy(x) = 4, Dy(z) = 1, Dz(y) = 1, Dz(x) = 5이다.
   이때, x-y의 링크가 1로 감소함을 y가 인지해서 Dy(x)=1로 수정해 이웃에 해당 정보를 전달한다.
   z는 변경된 벡터를 기반으로 Dz(x)를 5에서 2로 변경한다.
   y는 z로부터 Dz(x)의 정보를 받긴 하지만, 최소 비용의 변화는 없다.

2. 증가하는 경우
   y가 가진 정보는 1번의 경우와 마찬가지 이다,
   이때, x-y가 60으로 변화하였다면, Dy(x) = Dy(z) + Dz(x) = 1 + 5 =6 이 된다. 이때 Dz(x)는 Dx(y)에 대한 정보에 의존하는 것이지만 해당부분을 알 수 없다.
   z는 y로 부터 해당 벡터를 바독 Dz(x)를 7로 바꾼다. y는 z로부터 해당 벡터를 받아 Dy(x)를 8로 바꾼다. 이때, cost가 50(Dz(x))보다 커질때까지 계속해서 반복된다.

2. Hierarchical routing

• Routing Alogrithm은 2가지로 나뉜다 (Intra-AS Routing algorithm, Inter-AS Routing algorithm)
  -> 이때, Intra-AS Routing Algorithm은 link, vector같은 최단 거리가 중요한 알고리즘이지만, Inter-AS는 그렇지않다.

1) Customers and Providers

• AS사이에는 제공자와 소비자가 존재한다.
• 제공자는 소비자에게 서비스를 제공하며, 소비자는 제공자에게 돈을 지불해야한다.
  

2) The "Peering" Relationship

• Peer관계의 AS사이에는 제약없이 트래픽 전송이 가능하다.
• 하지만, 같은 계층이지만 peer관계가 아니라면 불가능하다. (자본주의의 차가움, 자신이 이득볼게 없어서 제공 안해줌)

그래서 어떠한 트래픽이 전달되는 많은 경로가 있지만, 우선순위는 내가 가장 손해를 덜 보는 길로 선택하게 된다. 아래의 예시로 AS1에 가려고 한다면, 3개의 AS를 거치더라고 Provider를 더 많이 거치는 경로를 선택.