[컴퓨터망]-라우팅 알고리즘

라우팅 알고리즘을 들어가기 전에 기본 개념을 정리하겠습니다.

라우터는 들어온 패킷들을 전송하는 Forwarding 기능과, 어디로 패킷을 보낼지 결정하는 Routing 기능이 있습니다.

Forwarding을 담당하는 부분을 data plane, Routing을 담당하는 부분을 control plane이라고 합니다.

network control plane을 구조화하는 두 가지 접근 방식이 있습니다.

전통적으로는 per -router control 방식과 SDN 방식이 있습니다.

간략하게 설명하자면 

per-router control 방식은 각각의 라우터별로 라우터 별로 forwarding table을 가지고 있고, Routing 알고리즘을 수행합니다.

data plane과 control plane이 같이 묶여 있는 상태입니다.

SDN 방식은 중앙 remote controller로 부터 정보를 받아서 routing algorithm을 수행합니다.

data plane과 control plane이 분리된 상태입니다.

---

Rounting protocols

라우팅 프로토콜의 목표는 송신측에서 수신 측까지의 경로를 네트워크 라우터를 통해서 잘 결정하자!

여기서 "잘"은 상황에 따라 다르지만, 비용이 적거나, 빠르거나, 혼잡이 덜 일어나는 게 대표적인 지표일 것입니다.

 

우선 어떤 경로로 전송하는 것이 가장 효율적인지 결정하는 방법은 Link state, distance vectors가 있습니다.

더 자세하게 설명해 보겠습니다.

 

Link-state

중앙집중형 라우팅 알고리즘이라고도 합니다.

• 모든 라우터가 연결 상태와 링크 비용을 알고 있다.
  • 네트워크 전체에 대한 완전한 정보를 이용해서 출발지 -> 목적지 사이의 최소 비용 경로를 계산합니다.

 

즉 모든 라우터가 모든 링크의 비용을 알고 있기 때문에 다익스트라 알고리즘을 이용해 최적의 경로를 계산할 수 있습니다.

출발지에서 다른 도착지까지의 최적 경로를 계산해서 routing table에 저장합니다.

 

 

다익스트라 알고리즘이란?

그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단 거리를 계산하는 알고리즘입니다.

https://jja2han.tistory.com/145

[알고리즘] 다익스트라(Dijkstra)알고리즘?

간략하게 설명하자면

1. 각 정점(노드)들 간의 거리는 무한대로 초기화한 상태
2. 출발지점에서 갈 수 있는 노드들은 거리를 업데이트, 갈 수없다면 ♾️상태
3. 거리가 업데이트된 지점들 중에서 가장 가까운 지점을 방문
   1. 2번 3번을 계속 방문
4. 그렇게 해서 모든 노드를 방문하게 되면, 출발지점에서 다른 목적기까지의 최단 거리(비용)가 구해진다.

다익스트라 알고리즘은 O(n²)의 시간복잡도를 가지고, 개선을 하면 O(nlogn)이 가능하다.

 

다익스트라 알고리즘은 링크의 트래픽양(비용)에 따른다. 이는 라우터 진동(oscillcations) 문제를 야기할 수 있다.

아래의 그림이 예시이다.

• 초기상태는 왼쪽 그림과 같다.
• 트래픽 상황 비용을 갱신할 때마다 시계방향과 반시계 방향으로 경로가 진동하듯이 방황한다.

---

Distance Vector

분산형 알고리즘이다.

• 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다.(DP)
• 어떤 라우터도 모든 링크 비용에 대한 완전한 정보를 갖고 있지 않지만, 
  각 라우터는 자신에게 연결된 인접 노드에 대한 링크 비용 정보를 알고 있다.
• 따라서 벨만-포드 알고리즘을 이용해 최적의 경로를 계산할 수 있다.

벨만포드 알고리즘이란?

노드 x부터 y까지 최소 비용 경로의 비용을 d𝙭(y) = minᵥ{c(x, v) + dᵥ(y)}

v는 x에 인접한 모든 이웃을 뜻한다.

 

동작방식

• 주기적으로 각 노드는 자신의 거리 벡터 추정값을 이웃 노드에게 전송한다.
• x가 어떤 이웃으로부터 새로운 거리 벡터(DV) 추정값을 받으면, B-F 방정식을 사용하여 자신의 거리 벡터를 
  업데이트한다.

 

self-stopping

• 각 노드는 자신의 DV(거리벡터)가 변경될 때에만 이웃노드에게 알린다.
• 그리고 이웃 노드는 필요한 경우에만 자신들의 이웃에게 날린다.
• 알림을 받지 않는 경우 어떠한 조치도 취하지 않는다.

 

DV에서 링크 비용이 바뀐다면 다음과 같은 일이 벌어진다.

• 각 노드는 loacl link cost의 변경을 감지
• 자신의 routing info를 갱신하고 local DV(거리벡터)를 재계산
• 만약 local DV가 변경되었다면 이웃노드에게 알림.

이렇게 링크 비용이 바뀔 때 문제점이 있다.

count-to-infinity

링크의 속도가 빨라지는 좋은 소식은 네트워크 전역에 퍼지지만, 링크 속도가 느려지는 나쁜 소식은 매우 천천히 알려지게 된다.
이로 인해 라우팅 루프가 발생할 수 있다.

노드 사이에 변경된 정보가 전파되지 않는 한 계속해서 알고리즘이 반복되고 최소비용 경로에 대한 정보가 무한대로 수렴

 

LS VS DV

메시지 복잡성

• Ls는 O(n²) 개의 메시지가 전송되고, 링크 비용이 바뀔 때마다 모든 노드에게 변경정보를 전달
• DV는 매너 반복마다 직접 연결된 이웃 기리 메시지를 교환

수렴 속도

• LS는 O(n²)의 시간 복잡도,
• DV : 천천히 수렴하고 알고리즘이 수렴하는 동안 라우팅 루프가 발생할 우려가 이싿.

강건성

LS

• 라우터가 오작동한다면 잘못된 link cost를 전달할 수 있다.
• 라우터가 자신만의 라우팅 테이블을 계산하고, 이는 곧 비최적 경로의 선택으로 이어짐.

DV

• 라우터가 잘못된 경로 비용을 업데이트해서, 트래픽이 침입된 라우터로  전송되어 중단이나 연결 손실을 초래한다.
• 각 라우터가 이웃 라우터들과 자신의 라우팅 테이블을 공유하는데, 잘못된 비용 정보가 포함된 테이블이 공유되어서,
  비최적 경로의 선택으로 이어진다.

---

Autonnomous System

지금까지의 라우팅 알고리즘은 모든 라우터가 동일하고, 네트워크가 "flat"하다고 가정했다.
하지만 이건 현실이 아니다.

실제로는 라우터들도 다양하고, 네트워크도 flat 하지 않고, 계층적 구조를 가집니다.

이에 따라 확장성과 자율성 과리의 문제가 발생하는데
이 문제를 라우터들을 AS로 조직화하여 해결할 수 있다.

AS라는 용어는 하나의 집합 내의 라우터들의 집합을 의미한다.

 

AS에는 intra-AS와 inter-AS로 분류가 가능하다.

intra-AS

• 같은 AS 내에 라우터들의 관계를 의미한다.
• AS 내의 모든 라우터는 동일한 도메인 내 프로토콜을 실행해야 한다.
• 다른 AS의 라우터는 다른 도메인 내 라우팅 프로토콜을 실행할 수 있다.
• gateway router : AS의 경계에 위치하며, 다른 AS의 라우터와의 링크를 가지고 있다.

inter-AS

• AS와 AS 간의 관계를 의미한다.
• 게이트웨이는 AS 간 라우팅을 수행한다.(도메인 내뿐만 아니라)

forwarding table은 그림과 같이 Intra-AS , Inter-AS rounting 알고리즘으로 구성된다.

• intra-As -> 같은 AS 내의 목적지에 대한 항목을 결정
• intra-As -> 같은 내 AS에서 게이트웨이까지 움직이고, intel-As -> 게이트웨이에서 다른 AS로 옮김.

 

Intra-AS routing

RIP

• Routing Information Protocol
  동일한 AS 내에서 라우터 라우터들 간에 경로 정보를 교환하여 내부 목적지에 대한 라우팅 결정을 수행
• 30초마다 DV를 교환함.
• 더 이상 널리 사용되는 방법은 아님

EIGRP

• Enhanced interior Gateway Routing Protocol
• DV 기반이며, Cisco -> Open 소스

OSPF

• Open Shortest Path First
• link-state 기반 (정보를 교환해서 최단 경로를 계산)->다익스트라 알고리즘
• IS-IS protocol(OSPF와 동일하지만 ISP와 대규모 네트워크에서 사용된다.)

OSPF

• open -> 용어는 공개적으로 사용 가능
• link-state 알고리즘을 사용해서, 네트워크 전체의 라우터에 대한 정보를 각각 라우터들이 알고 있고, 다익스트라 알고리즘을 사용
• TCP나 UDP 등의 상위 레이어 서비스를 사용하지 않고, IP를 통해 직접 전송

 

Hierarchical OSPF

https://ddongwon.tistory.com/96

위와 같은 계층적인 구조로 OSPF를 설정하게 되면 local area, backbone으로 나뉜다

 

boundary routers

• 다른 AS와 연결되는 컨택 포인트를 담당하는 라우터

area border routers

• 각각의 area를 연결하는 라우터, 각각의 area에 포함된 라우터들의 cost만 요약해서 저장, 교환한다.

backbone routers

• 서로 다른 area를 연결하는 뼈대 역할을 하는 라우터

local routers

• 자신의 토폴로지 정보와 라우팅 정보를 관리한다.
• LS

네트워크를 로컬 영역 와 백본 영역을 분할, 관리해서 확장성을 향상한다.

로컬 영역은 작은 규모로 관리되며, 백본 영역에서는 로컬 영역 간의 라우팅 정보만을 관리해서, 네트워크의 크기에 상관없이

효율적인 라우팅이 가능해진다.

 

 

Inter-AS Routing

다른 AS들을 연결시켜 주는 라우팅 프로토콜이다.

 

대표적인 예로는 BGP(Border Gateway Protocol)이 있다.

BGP

하지만 BGP프로토콜은 서로 다른 AS들을 연결하는 것이 아닌 AS의 가장자리에 위치한 BG들 간의 프로토콜이다.

 

BGP는 다음과 같은 기능이 있다.

 

eBGP(External)

• 인접한 AS로부터 서브넷 도달 가능성 정보를 얻는다.

iBGP(internal)

• 도달 가능성 정보를 AS 내부의 모든 라우터에 전파한다.

도달 가능성 정보와 policy를 기반으로 다른 네트워크로의 좋은 경로를 결정한다.

 

 

• 파란 선은 logical iBGP, 같은 as 내부의 연결
• 빨간 선은 eBGP, as 간의 연결
• 동그라미 친 라우터들은 gateway router이다.

---

BGP의 역할

BGP의 역할은 다른 라우터들에게 A라는 라우터가 어디에 속해 있는지에 대한 정보를 광고하는 것이다.
내부는 라우팅 테이블을 통해서 AS 목적지가 정해진다. 서로 다른 AS로 가야 한다면? BGP가 필요하다.

Path attributes and BGP routes

BGP에서 광고되는 경로는 접두사(prefix)와 속성(attributes)으로 구성된다.

• prefix : 광고되는 목적지
• attribute
  • AS-PATH : prefix가 통과한 AS 목록. 어떤 AS를 거쳤는지를 나타냄.
  • NEXT-HOP : 다음 AS로의 경로에서 구체적인 내부 AS 라우터를 나타낸다.
    다음 AS로 전달할 때 사용되는 내부 AS 라우터를 지정한다..

정책 기반 라우팅

• 정책을 사용하여 특정 경로를 수락 또는 거부한다.
• 예를 들어 B동네가  A 동네를 통해서 들어오는 바나나를 받지 말아라고 정책을 수정하면
  B 동네는 A 동네에서 들어오는 바나나를 받지 못한다.
• 그리고 경 로르 다른 AS에게 광고할지 여부를 결정한다.

 

BGP는 다음과 같은 과정으로 동작된다.

 

1. AS2에 있는 2c 라우터는 AS3, 3a에서 보낸 X(eBGP)를 받았다. -> AS3, X
2. 2C는 iBGP 메시지 AS3, X를 AS2 내부 모든 라우터에게 전달한다.
3. AS2에 있는 2a는 eBGP 메시지 AS2, AS3, X 전달

보면 계속 보낸 자신을 메시지 앞에 붙인다.

이걸 역 추적하면 경로를 아주 쉽게 찾을 수 있다.

AS1과 AS2의 모든 라우터는 x의 존재와 x로 향하는 AS 경로를 알게 된다.

 

위 경우는 목적지까지 2가지 경로가 있다. 

AS3 , 3a -> As1 , 1c

As3, 3a -> As2 2c-> 내부 전파 -> As2 2a -> As1,1c

 

BGP message는 TCP 연결을 기반으로 교환된다.

• OPEN : 다른 BGP 피어와 TCP 연결을 시도
• UPDATE : 새로운 경로 정볼르 받아서 갱신
• KEEPALIVE : 연결을 수립한 상대방이 살아있는지, 또는 OPEN 요구에 대한 ACK로 사용됨.
• NOTIFICATION : 에러가 발생하였을 때 알리거나 연결을 끊을 때 사용된다.

---

Hot Potato Routing

뜨거운 감자를 만지면 빠르게 던지는 것을 비유한 방법인데 진짜 그러한 느낌인 거 같다.

Next-HOP이 짧은 link를 선택한다.

그림을 예로 설명하면

2d는 iBGP를 통해 2d->2a, 2d->2c를 통해 X로 라우팅을 할 수 있다는 것을 알고 있다.

Hot Potato Routing은 Intra-domain-cost 가 가장 적은 로컬 게이트웨이를 선택한다.

그림을 보면 2d->2a로 가는 비용이 2d->2c로 가는 비용보다 적기 때문에 2a를 선택할 것이다.

물론 이러한 선택이 나중에는 비효율적인 선택이 될 수 있지만
뜨거운 감자를 던지는 것처럼 바로바로 최소한의 내부 비용을 가지는 경로를 선택한다.

---

요약

• 라우팅 프로토콜은 송신 측에서 수신 측까지의 경로를 최소한의 비용으로 결정해 주는 프토로콜이다.
• 라우팅 프로토콜에는 크게 LS(link-state), DV(distance vector)가 있다.
• LS는 다익스트라 알고리즘, DV는 벨만포드(DP) 알고리즘을 사용한다.
  • LS는 비용이 트래픽의 변경되면 라우팅 진동, DV는 count-to-infinity 문제가 생길 수 있다.
• AS는 같은 집합 내의 라우터들의 집합을 의미한다.
• Intra-As와 Inter-AS가 있다.
  • Intra-AS는 같은 AS내의 라우터들끼리의 관계, Inter-As는 다른 AS들끼리의 관계를 의미한다.
• Intra-AS 알고리즘에는 다양한 방법이 있다(RIP, OCPF, EIGRP) -> 그중에서 OSPF는 LS를 사용한다.
• OSPF를 계층화해서 backbone과 local로 분할해서, 확장성을 향상하고, 효율적인 네트워크 관리가 가능하다.
• Inter-AS 알고리즘에는 BGP가 있다.
  • iBGP, eBGP가 있다.
  • BGP의 역할은 다른 라우터들에게 A라는 라우터가 어디에 속해 있는지에 대한 정보를 광고하는 것이다.
• Hot-potato-routing은 intra-domain-cost가 가장 적은 경로를 택한다.