네트워크 계층 - 경로 설정 프로토콜 #3. OSPF와 BGP.

앞 포스팅에서 다익스트라와 벨만 포드 알고리즘에 근거한 LS와 DV에 대해 다루었다. 그러나, 해당 알고리즘을 활용하여 전체 네트워크를 다룰 수 있을까? 답은 다룰 수 없다.

첫 번째는 확장성에 대한 문제다. 라우터의 수가 굉장히 많기 때문에 세상에 존재하는 모든 라우터와의 거리를 계산하기 위해서는 통신, 계산, 메모리에 대한 오버헤드가 걷잡을 수 없이 크다. 두 번째는 관리의 어려움이다. 각 라우터를 관리하는 관리자[ISP, Internet Service Provider]는 각자의 입맛마다 다른 알고리즘을 활용하고 싶을 것이다.

 

따라서 등장한 것이 OSPF와 BGP 프로토콜이다. 해당 프로토콜들은 각각의 라우터 하나하나를 다루는 것이 아니라 라우터를 집합으로 묶은 후, 이 집합에 대해서 경로를 설정한다. 이러한 집합을 자율 시스템[AS: Autonomous System]라 한다. 각 AS는 동일한 관리 방식으로 제어되는 라우터 그룹이다. 우리가 네트워크 공부하며 들어보았던 도메인 영역이 바로 이 AS를 뜻한다.

AS는 크게 인트라와 인터로 나누어진다. 

1. 인트라 AS 라우팅 [Intra AS]

하나의 AS 내에 존재하는 라우터들 사이에서 일어나는 라우팅을 의미한다. 각 인트라 AS 내에는 다른 AS에 존재하는 라우터와 연결된 라우터가 존재하며, 해당 라우터를 '게이트웨이'라 칭한다. 게이트웨이를 통해서 다른 AS에 존재하고 있는 라우터를 만날 수 있다. 

인트라 AS 라우팅은 보통 IGP[Interior Gateway Protol]이라고도 불린다. 해당 라우팅 방식엔 RIP[Routing Information Protocol], OSPF[Open Shortest Path First], IGRP[Interior Gateway Routing Protocol]이 존재한다.

1.2. OSPF [Open Shortest Path First]

OSPF는 링크 상태 정보를 플러딩[Flooding]하고 다익스트라 최소 비용 경로 알고리즘을 사용하는 LS 알고리즘이다. OSPF를 활용해 각 라우터는 전체 AS에 대한 토폴로지를 얻는다. AS 관리자는 각 라우터에 대한 링크를 1로 설정해서 최소 홉 라우팅을 하거나 대역폭 좁은 라우팅 사용을 억제하기 위해 대역폭과 반비례하여 링크 비용을 설정할 수 있다. 링크 비용에 대한 관리는 관리자가 설정하는 것이며 OSPF는 오직 주어진 링크 가중치에 대해 최소 비용 경로를 결정하는 방법(프로토콜)만을 제공한다. OSPF를 사용하는 라우터는 인접한 라우터 뿐만 아닌, AS 내 모든 라우터에게 라우팅 정보를 정기적으로 브로드캐스트한다. 

 

2. 인터 AS 라우팅 [Inter AS]

인트라 AS 보다 더 커다란 개념으로 각 AS들 사이에서 이루어지는 라우팅이다. 즉 게이트웨이들 끼리 이뤄지는 라우팅이다. 대표적인 프로토콜엔 BGP(Border Gateway Protocol)가 존재한다.

2.2. BGP[Border Gateway Protocol]

BGP는 인터넷 상에 존재하는 수천 개의 ISP들을 연결하는 프로토콜이기에 가장 중요하다고 말할 수 있다. BGP는 DV 같은 분산형 비동기 프로토콜이다.

BGP는 두 가지 연결이 존재한다. 하나의 AS 내에서 통신하는 iBGP[Internal BGP]와 AS 사이에서 동작하는 eBGP[External BGP]다.

 

다음과 같이 예시를 들어 BGP를 이해해보자. 해당 그림에는 세 개의 AS가 존재하며 각 AS엔 네 개의 라우터들이 존재한다. AS1 내에서 연결된 1a, 1b, 1c, 1d 라는 라우터들끼리 통신하는 것을 iBGP라 한다. 이 중 1c는 AS2의 라우터 2a와 연결되어 있다. 따라서 1c, 2a 라우터의 연결을 eBGP라 하며 각 라우터들을 '게이트웨이'라 칭한다. (cf. iBGP 연결은 물리적인 링크와 항상 일치하지는 않는다.)

 

다음 예시는 AS3에 존재하는 'X'라는 라우터에 대한 정보를 다른 AS에게 알리는 과정이다. 도달 가능성 여부를 알리기 위해서는 iBGP와 eBGP가 둘 다 활용된다.

1. 라우터 X와 연결된 AS3이 있다.

2. AS3의 게이트웨이인 3a는 다른 AS인 2c에게 "AS3 X"라는 eBGP 메시지를 보낸다.

3. 메시지를 받은 2c는 같은 AS내에 존재하는 모든 라우터들에게 iBGP를 통해 "AS3 X"를 보낸다. 

4. AS2의 또 다른 게이트웨이인 2a는 AS1에 있는 1c에게 "AS2 AS3 X"를 전송한다.

5. 메시지를 받은 1c는 같은 AS내에 존재하는 모든 라우터들에게 iBGP를 통해 "AS2 AS3 X"를 보낸다.

위와 같은 과정을 통해서 AS1과 AS2는 'X'의 존재와 그로 향하는 경로를 알 수 있다.

 

 

그러나 만약 'X'로 가는 경로가 여러가지일 때는 어떻게 경로를 정할까? 사실 이를 결정하는 알고리즘은 무수히 많으며 각각의 ISP 설정마다 다른 알고리즘을 사용하기에 깊게 다루지는 않는다.

다음 그림을 보자. 이전 그림과는 다르게 AS3에서 AS1로 바로갈 수 있는 선이 존재하며 각 AS들의 게이트웨이들은 'X'로 갈 수 있는 여러 경로를 학습하게 된다. 이 때 최적의 경로를 선택하기 위해서는 몇가지 속성을 더 살펴볼 필요가 있다. 중요한 속성 두 가지는 AS-PATH와 NEXT-HOP이다. 

AS-PATH 속성에는 알림 메시지가 통과하는 AS들의 리스트를 담는다. AS-PATH 값을 생성하기 위해서 접두부가 어떤 AS에 전달되었을 때 그 AS는 자신의 ASN을 AS-PATH에 추가한다. AS-PATH의 관점으로 위 그림을 살펴보자. AS1의 게이트웨이인 1C는 두 개의 경로를 인지한다. 하나는 AS-PATH "AS3" 이며 다른 하나는 AS-PATH "AS2 AS3"이다.

NEXT-HOP는 AS-PATH를 시작하는 라우터 인터페이스의 IP 주소다. 즉 "AS2 AS3" 이라는 AS-PATH가 있다면 NEXT-HOP에서는 2A의 왼쪽 인터페이스 링크의 IP가 된다.(1C와 2A를 연결하고 있는 링크다)

요약하자면 AS1의 각 라우터는 X로 가는 두 개의 BGP 경로를 알게 된다.

{라우터 2a의 맨 왼쪽 인터페이스의 IP 주소; AS2, AS3; x}

{라우터 3a의 맨 왼쪽 인터페이스의 IP 주소; AS3; X}

이처럼 BGP 경로는 NEXT-HOP, AS-PATH, 목적지 주소 접두부, 이렇게 세 개의 구성요소 리스트로 구성된다. (실제로는 다른 속성도 포함되지만 너무 깊어지기에 다루지 않는다.)

NEXT-HOP의 속성이 AS1에 속하지 않는 라우터의 IP 주소라는 점을 주의하자. 그러나 이 IP 주소를 포함하는 서브넷이 AS1에 직접적으로 연결된다.

 

이렇게 BGP의 경로와 속성에 대해 이해를 하였다. 이러한 정보를 기반으로 어떤 알고리즘, 어떤 방식으로 최적의 경로를 설정하는지는 다루지 않는다. 각 ISP마다 다른 알고리즘을 다루고 있으며, 그 종류는 다양하기 때문에 너무 깊어질 수 있다. 경로 선택 알고리즘으로는 그리디 방식의 뜨거운 감자 라우팅 등이 존재한다는 것만 알아두자.

 

이상으로 경로 설정을 돕는 프로토콜 정리한다.

1. RIP [Routing Information Protocol] : DV이며 벨만-포드 방식을 사용한다.

IP 통신망의 경로 설정 프로토콜의 하나로 경유하는 라우터의 대수(HOP의 수량)에 따라 최단 경로를 동적으로 결정하는 거리벡터 알고리즘을 사용한다. 버전 1은 인터넷, 인트라넷에 가장 널리 사용되고 있으며, 버전2는 CIDR에 대응될 수 있도록 기능이 확장되어 있다. 일반 기업 내에 정보 통신망(LAN)에 사용되는 경우가 많다.

2. OSPF[Open Shortest Path First] : LS이며 다익스트라 방식을 사용한다.

하나의 자율 시스템(AS)에서 동작하면서 내부 라우팅 프로토콜 그룹에 도달하는 링크 상태 라우팅 알고리즘이다. RIP의 단점을 해결하여 새로운 기능을 가지게 한 것으로, 인터넷 멀티미디어 프로토콜 표준 후보의 하나다. 인터넷망에서 이용자가 최단 경로를 선정할 수 있도록 라우팅 정보에 노드 간의 거리 정보, 링크 상태 정보를 실시간으로 조합하여 최단 경로로 라우팅을 지원하는 프로토콜이다. 대기업망에 가장 널리 쓰이는 내부 게이트웨이 프로토콜(IGP)로 간주된다.

3. BGP

외부 게이트위에 프로토콜(EGP)로 간주된다. AS의 네트워크 내에서 게이트웨이 호스트끼리 라우팅 정보를 교환하기 위한 프로토콜로, 각 호스트들은 TCP를 이용하며 통신한다. 어떤 호스트에 변경이 감지되었을 때만 갱신된 라우팅 테이블 정보를 보내는데, 오직 연관된 부분만이 보내진다.