[네트워크] 라우팅 알고리즘 (OSI 3계층)

# Interplay between routing, forwarding

 

어떤 라우터든지, 각 라우터는 네트워크 코어에 있는shortest path를 알아야 한다.  모든 라우터 쌍에 대해서 알아야 한다. single source 에서 all destination 로 가는 대해 모든 path의 shortest paht를 알아야 한다. 중요한 것은 routing algorithm을 돌리면 end-end path가 정해지고, forwarding table이 local forwarding을 결정한다. 

요약하면, 라우팅 알고리즘은 전체 네트워크 경로를 결정하고, 포워딩 테이블은 각 라우터에서 로컬 포워딩 방식을 결정합니다.

 

# 그래프 추상화

 

 

각 vertex는 라우터이고, 연결은 엣지이다. 엣지의 cost는 bandwith와 관련된다. bandwith가 크면 cost가 낮아지는 것이고, congestion이 많이 발생하면, cost가 커지는 것이다.  알아야 하는 것은 cost가 가장 낮은 경로를 찾는 것이다. 이 경로를 찾는 것이 라우팅 알고리즘이다. 

u가 시작점이라고 z가 종료 지점이라고 생각할 때, 모든 정보를 알고 있다고 생각하는 것이 global이고, 나와 연결된 링크의 코스트만 아는 경우를 decentralized ="distance vector" 알고리즘이라 하며, 일부 정보를 가지고 shortest를 찾고 결과를 공유하는 과정에서 여러 번에 걸쳐서 정보를 얻게 된다. 

 

네트워크 라우팅 정보가 글로벌 또는 분산되어 있는지에 따라 다음과 같이 분류할 수 있습니다:

글로벌 정보:
- 모든 라우터가 완전한 토폴로지와 링크 비용 정보를 가지고 있습니다.
- "링크 상태" 알고리즘을 사용합니다.

분산 정보: 
- 라우터는 물리적으로 연결된 이웃 라우터와 이웃까지의 링크 비용만 알고 있습니다.
- 계산과 이웃 간 정보 교환의 반복적인 프로세스를 거칩니다.  
- "거리 벡터" 알고리즘을 사용합니다.

라우팅 정보가 정적인지 동적인지에 따라서는:
정적:
- 경로가 시간이 지남에 따라 천천히 변경됩니다.
동적:
- 경로가 보다 빠르게 변경됩니다.
- 주기적 업데이트
- 링크 비용 변화에 대응

 

# A Link-State Routing Algorithm

다익스트라 알고리즘 

• 네트워크 토폴로지와 링크 비용이 모든 노드에 알려져 있는 글로벌 정보 
• "링크 상태 브로드캐스트"를 통해 모든 노드가 동일한 정보를 가집니다.
• 한 노드("소스")에서 다른 모든 노드로 가는 최소 비용 경로를 계산합니다.
• 해당 노드의 포워딩 테이블을 생성합니다.
• 반복적으로 k번째 반복 후에는 k개의 목적지까지의 최소 비용 경로를 알게 됩니다.

사용되는 notation:

• c(x,y): 노드 x에서 y까지의 링크 비용. 직접 이웃이 아니면 무한대입니다.
• D(v): 소스에서 목적지 v까지의 경로 비용 현재값
• p(v): 소스에서 v까지 경로상의 predecessor 노드
• N: 최소 비용 경로가 확정적으로 알려진 노드 집합

 

결국, u에서 출발 했을 때 연결된 가장 작은 값을 선택하는 것이다. 

 

다익스트라는 u에서 시작했을 때, 다익스트라는 연결된 모든 vertex에 대해 엣지를 모두 본다. 연결된 엣지 중에서 가장 작은 엣지는 확정이다. 음수가 없기 때문이다. oscillation possible: 링크의 cost를 트래픽의 양으로 볼 때, 경로를 설정할 때, 처음에 보고 경로를 결정했을 때, 그 경로로 가려는 노드가 많을 때, 혼잡해지는 상황이다. 

알고리즘 복잡도: 
- n개의 노드가 있을 때
- 각 반복에서 N에 포함되지 않은 모든 노드 w를 검사해야 합니다.
- n(n+1)/2번의 비교가 필요합니다. 즉, O(n^2)의 시간 복잡도입니다.
- 더 효율적인 구현으로 O(nlogn)까지 가능합니다.

oscillation 가능성:
- 예를 들어, 링크 비용이 전송된 트래픽량과 같다고 가정할 때
- 이러한 비용으로 새 라우팅을 찾으면
- 새로운 비용이 발생하여 진동할 수 있습니다.

요약하면, 다익스트라 알고리즘의 시간 복잡도는 O(n^2)이며, 특정 비용 함수에서는 라우팅과 비용 간의 순환적 의존성으로 인해 진동 현상이 발생할 수 있습니다.

 

 

 

dp 를 사용할 수 있다. 분할 정복 방식이다. 일부의 정보만 사용하는 distance vector 알고리즘을 사용한다. x라는 노드가 있을 때, y로 가는 shortest path를 찾는 상황이다. x에서 y로 가는 cost에 대해서 v가 y로 가는 최단 거리를 구했을 때. 아래와 같은 식이 만족된다. 

빠르게 수렴되고 끝나는데, 중간에 나쁘게 변하는 경우가 있을 때 문제가 생긴다. 중간 과정을 최적의 값이라고 계산하는 것인데, 갑자기 중간에 값이 안 좋아지면 iter를 엄청 많이 돌아가게 된다. 

 

벨만-포드 방정식(동적 프로그래밍)에 대해 정리하면 다음과 같습니다:

dx(y) := x에서 y까지의 최소 비용 경로 비용이라고 할 때, 

dx(y) = min{c(x,v) + dv(y)}
v는 x의 이웃 노드에 대한 min

- Dx(y) = x에서 y까지의 최소 비용 경로에 대한 추정치
- x는 거리 벡터 Dx = [Dx(y): y Є N]를 유지합니다.  

- 노드 x는 
    - 각 이웃 v까지의 비용 c(x,v)를 알고 있습니다.
    - 이웃들의 거리 벡터를 유지합니다. 각 이웃 v에 대해 Dv = [Dv(y): y Є N]를 유지합니다.

주요 아이디어:
- 주기적으로 각 노드는 자신의 거리 벡터 추정치를 이웃들에게 전송합니다.
- x가 이웃으로부터 새로운 DV 추정치를 받으면 벨만-포드 방정식을 사용하여 자신의 DV를 업데이트합니다:
    Dx(y) ← minv{c(x,v) + Dv(y)} for each y Є N  
- 자연스러운 조건 하에서 Dx(y) 추정치는 실제 최소 비용 dx(y)로 수렴합니다.

 

링크 비용 변경:
❖ 노드가 로컬 링크 비용 변경을 감지함
❖ 라우팅 정보를 업데이트하고 거리 벡터를 다시 계산함
❖ 거리 벡터(DV)가 변경되면 이웃에게 알림

“좋은 소식은 빨리 퍼진다”

t0 : y가 링크 비용 변경을 감지하고, DV를 업데이트하며 이웃에게 알림.
t1 : z가 y로부터 업데이트를 받고 테이블을 업데이트하며, x로의 새로운 최소 비용을 계산하고 이웃에게 DV를 보냄.
t2 : y가 z의 업데이트를 받고 거리 테이블을 업데이트함. y의 최소 비용이 변경되지 않으므로 y는 z에게 메시지를 보내지 않음.

링크 비용 변경:
❖ 노드가 로컬 링크 비용 변경을 감지함
❖ 나쁜 소식은 천천히 퍼진다 - “무한대로 세기” 문제!
❖ 알고리즘이 안정화되기까지 44회 반복: 텍스트 참조

 

LS와 DV 알고리즘의 비교
메시지 복잡도
❖ LS: n개의 노드와 E개의 링크가 있을 때, O(nE) 메시지 전송
❖ DV: 이웃 간에만 교환
▪ 수렴 시간은 다양함

수렴 속도
❖ LS: O(n^2) 알고리즘은 O(nE) 메시지를 필요로 함
▪ 진동이 발생할 수 있음
❖ DV: 수렴 시간은 다양함
▪ 라우팅 루프가 발생할 수 있음
▪ 무한대로 세기 문제 발생 가능

견고성: 라우터가 오작동하면 어떻게 되는가?
LS:
▪ 노드는 잘못된 링크 비용을 광고할 수 있음
▪ 각 노드는 자신의 테이블만 계산함
DV:
▪ DV 노드는 잘못된 경로 비용을 광고할 수 있음
▪ 각 노드의 테이블이 다른 노드들에 의해 사용됨
• 오류가 네트워크를 통해 전파됨

=> RIP 

 

---

# hierarchcal routing 

이상적인 경우를 가정하는 것이다. 네트워크 노드가 많지 않은 상황을 가정한다.

같은 autonomous systems (AS)에 있는 경우에, 같은 라우팅 프로토콜을 돌리고 있는 상황이다. 이것을 intra-AS 라우팅 프로토콜이라 한다. 다른 AS를 이어주는 라우터를 gateway-router라고 한다. 각 AS가 어떤 네트워크 프로토콜 사용하는지 공유하고 있어야 한다. AS 안에서도 공유해야 한다.

 

inter-AS routing 알고리즘은 다른 AS 로 가기 위해서 어떤 라우터로 데이터를 보내야 하는지 파악하는 알고리즘이다. 

이를 통해 as 밖의 라우터로 향한다. 

 

AS 1이 알아야 하는 것: 1. 인접한 AS인 AS2, AS3를 통해서 어떤 네트워크로 갈 수 있는지 게이트웨이 노드까리 공유해서 알아야 한다. 2. 이 정보를 AS 1에 있는 모든 라우터에게  전파해야 한다. => 결과적으로 다 아는 것이다. 

 

1.은 eBGP 라 하고, 2번은 iBGP 라고 한다. external, internal 이라는 의미임. subnet x라는 네워크로 보내고 싶은 상황이다. 

같은 AS 안에서는 거리 벡터 알고리즘 돌아가는 것이고, 외부에 어떻게 접근할 것인가가 문제점이다. 

 

둘 다 가능한 경우 무엇을 선택할 것인가? 

1. 중간 AS 개수가 짧은데로 보내면 된다. 2 . 이것 마저도 같으면? 그러면 "내부적으로 gate-way로 빠른 길로 간다". intra에서 빠른 길로 가는 것이다. 이것이 BGP 알고리즘에서 하는 방식이다. 

 

핫 포테이토 라우팅 알고리즘은 shortest gateway로 보내버리는 것이다. 중간은 모르겠다~ 하는거임. 일종의 그리디임. 

 

# routing in the internet

intra-as routing 에서 중요한 것은 lin-state, distance vector 이 두 가지이다. 

RIP는 distance vector 알고리즘이다. subnet u로 연결된 것. 

정보가 주기적으로 와야 하는데 안 오면, 옆 노드가 죽은 것으로 안다. 그러면 그 라우터에 대한 정보는 없는 것으로 간주한다. 이 정보를 다시 이웃 노드에 알려주고 전파된다. 

 

이는 application level 과정이고, UDP를 통해서 전송된다. 

 

OSPF 는 shortest path 가 first, 우선 순위라는 의미이다. (open is open source) 

연결된 링크들에 대한 정보를 모두 받으면, 그에 대한 정보를 구성할 수 있고 다익스트라 알고리즘을 돌리면 된다. 

여기서 중요한 것은 link state 정보를 모두 수집할 수 있는 것이다. 왜? 공유하기 떄문에! 

이를 통해 토폴로지 맵을 구성하고 알고리즘을 돌린다.

 

inter-as routing: BGP

이것은 border gateway protocol 이다. 이를 통해서 AS 끼리 연결 시켜 주는 역할을 한다. eBGP는 외부의 AS와 연결된 정보들이고, iBGP는 내부에서 정보를 공유하는 것이다. 내가 여기 있다고 알리는 것이 BGP 프로토콜이다. 

 

아래와 같은 메시지를 보낸다. prefix가 목적지이다. 아래는 eBGP 메시지이다. 

AS-PATH:  BGP 메시지, 아래에서는 AS 3와 AS 131을 지나가야 나온다.

NEXT-HOP: 게이트 웨이 라우터의 주소이다. As 3에 있는 게이트웨이 라우터 주소임. 

이 정보를 공유한다. 그럼 AS 1 내부에서는 게이트 웨이가 아닌 라우터는 게이트웨이 라우터에게 intra-as 를 통해 보낸다. 

이 때 메시지는 next-hop 대신에 게이트 웨이 라우터 주소가 들어간다. 그럼 목적지로 보내려면 저 게이트 웨이로 보내고 정보를 보낸다. 

 

메시지에서 prefix가 같은 경우에:

뜨거운 감자라면 shortest path 값으로 보낸다. 

BGP 라면, 우선 AS 길이가 짧은 것을 우선적으로 선택한다. 같으면 그 때 가서: 핫 포테이트를 사용한다.