라우팅 알고리즘

라우팅 테이블은 라우터가 패킷을 전달할 때 참조하는 핵심 데이터 구조이다. 이 테이블은 네트워크 상의 목적지 IP 주소 또는 네트워크 프리픽스와, 그 목적지로 패킷을 보내기 위해 사용해야 할 '다음 홉' 정보를 매핑하여 저장한다. '다음 홉'은 일반적으로 인접한 라우터의 인터페이스 주소이거나, 목적지가 직접 연결된 네트워크일 경우 해당 출구 인터페이스 자체가 된다. 라우터는 수신한 패킷의 목적지 IP 주소를 라우팅 테이블의 항목들과 비교하여 가장 구체적으로 일치하는 경로, 즉 가장 긴 프리픽스 일치(Longest Prefix Match) 규칙을 따라 전송 경로를 결정한다.

경로 결정 과정은 다음과 같다. 라우터는 패킷 헤더의 목적지 주소를 추출한 후, 라우팅 테이블을 검색하여 해당 주소를 포함할 수 있는 네트워크 대역을 찾는다. 테이블에 여러 개의 가능한 경로가 존재할 경우, 가장 좁은 범위의 네트워크(서브넷 마스크 길이가 가장 긴 항목)를 우선적으로 선택한다. 이는 더 구체적인 경로가 존재한다면 그것이 더 정확한 경로일 가능성이 높기 때문이다. 일치하는 항목을 찾으면, 패킷은 해당 항목에 지정된 '다음 홉' 주소나 출구 인터페이스를 통해 전송된다. 만약 일치하는 항목이 전혀 없으면, 패킷은 기본 게이트웨이(Default Route, 0.0.0.0/0)로 보내지거나 폐기된다.

라우팅 테이블의 항목은 다양한 출처를 통해 학습된다. 직접 연결된 네트워크, 관리자가 수동으로 설정한 정적 라우팅 경로, 그리고 동적 라우팅 프로토콜을 통해 이웃 라우터로부터 자동으로 교환 및 계산된 경로가 그 예이다. 이 테이블은 네트워크 토폴로지 변화에 따라 지속적으로 갱신되어야 하며, 이를 위해 라우팅 알고리즘이 동작한다. 효율적인 경로 결정을 위해서는 라우팅 테이블의 크기와 검색 속도가 매우 중요하다. 대규모 네트워크에서는 수십만 개의 경로를 저장해야 할 수 있으므로, 고속의 검색 알고리즘과 메모리 관리가 필수적이다.

라우팅 알고리즘이 최적 경로를 선택하기 위해 사용하는 기준을 메트릭이라고 한다. 메트릭은 경로의 비용, 거리 또는 품질을 수치화한 값이다. 라우터는 목적지까지의 여러 가능한 경로 중에서 메트릭 값이 가장 낮거나 가장 높은 경로를 최적 경로로 선정한다. 사용되는 메트릭의 종류는 알고리즘과 프로토콜에 따라 다르다.

흔히 사용되는 메트릭은 다음과 같다.

단일 메트릭만으로는 복잡한 네트워크 환경에서 최적의 경로를 결정하기 어려운 경우가 많다. 따라서 EIGRP와 같은 일부 고급 라우팅 프로토콜은 여러 메트릭을 조합한 복합 메트릭을 사용한다. 예를 들어, 대역폭과 지연을 결합하여 더 정교한 경로 선택을 한다. 반면, OSPF는 기본적으로 인터페이스의 대역폭에 기반한 비용을 메트릭으로 사용한다. 최적 경로의 선택은 결국 네트워크 관리자가 어떤 메트릭을 우선시하도록 프로토콜을 구성하느냐에 따라 달라진다.

정적 라우팅은 네트워크 관리자가 수동으로 라우팅 테이블에 경로 정보를 입력하고 구성하는 방식이다. 이 방식에서는 라우터가 네트워크 토폴로지의 변화를 자동으로 감지하거나 경로를 재계산하지 않는다. 관리자가 직접 모든 경로를 정의하기 때문에 라우터의 처리 부하가 적고, 네트워크 대역폭을 라우팅 정보 교환에 소모하지 않는다. 또한, 예측 가능한 경로를 통해 보안 정책을 엄격하게 적용할 수 있다는 장점이 있다. 그러나 네트워크 규모가 크거나 변화가 빈번한 환경에서는 모든 변경 사항을 수동으로 반영해야 하므로 관리 부담이 크고, 장애 발생 시 자동으로 우회 경로를 찾지 못하는 단점이 있다.

반면, 동적 라우팅은 라우터가 라우팅 프로토콜을 사용하여 주변 라우터와 정보를 자동으로 교환하고, 수신한 정보를 바탕으로 라우팅 테이블을 동적으로 구성 및 갱신하는 방식이다. RIP, OSPF, BGP 등이 대표적인 동적 라우팅 프로토콜이다. 이 방식은 네트워크 링크의 상태 변화(예: 장애, 추가, 제거)를 자동으로 감지하고 최적의 경로를 재계산하여 라우팅 테이블을 갱신한다. 따라서 대규모 네트워크나 구성이 자주 변경되는 환경에서 유리하며, 장애 발생 시 자동으로 대체 경로를 제공하는 내결함성을 갖춘다. 다만, 라우터가 경로 정보를 지속적으로 계산하고 교환해야 하므로 프로세싱 자원과 네트워크 대역폭을 추가로 소모하며, 구성이 정적 라우팅에 비해 복잡할 수 있다.

두 방식의 주요 차이점을 요약하면 다음과 같다.

현실의 네트워크에서는 두 방식을 혼합하여 사용하는 경우가 많다. 예를 들어, 스텁 네트워크(말단 네트워크)로 가는 경로는 정적 라우팅으로 설정하고, 복잡한 백본 네트워크 내부에서는 OSPF 같은 동적 라우팅 프로토콜을 운영하는 방식이다.

링크 상태 알고리즘과 거리 벡터 알고리즘은 동적 라우팅을 구현하는 두 가지 핵심적인 접근 방식이다. 이들은 네트워크 토폴로지 정보를 수집하고 최적 경로를 계산하는 방식에서 근본적인 차이를 보인다.

링크 상태 알고리즘은 각 라우터가 네트워크 내 모든 다른 라우터에 대해 자신의 직접 연결된 이웃과 해당 링크의 상태(비용, 가용성 등)를 알리는 링크 상태 광고 패킷을 전체 네트워크에 플러딩한다. 모든 라우터는 이 정보를 수집하여 동일한 네트워크 전체의 토폴로지 맵을 구성한다. 그런 다음 데이크스트라 알고리즘과 같은 최단 경로 알고리즘을 이 맵에 적용하여 모든 목적지까지의 최적 경로를 독립적으로 계산한다. 이 방식은 네트워크 변화에 빠르게 반응하고 루핑이 발생할 가능성이 낮지만, 라우터의 처리 부하와 메모리 사용량이 크며, 초기 수렴까지의 시간이 걸린다는 특징이 있다.

반면, 거리 벡터 알고리즘은 각 라우터가 자신의 라우팅 테이블 전체, 즉 각 목적지까지의 거리(메트릭)와 다음 홉 정보를 정기적으로 직접 연결된 이웃 라우터들에게만 알린다. 이웃 라우터는 받은 정보를 바탕으로 자신의 라우팅 테이블을 갱신하고, 이 과정이 반복되면서 경로 정보가 네트워크를 통해 점차적으로 전파된다. 이 알고리즘의 대표적인 문제는 잘못된 경로 정보가 네트워크를 순환하는 라우팅 루프가 발생할 수 있다는 점이다. 이를 완화하기 위해 무한대 계수, 포이즌 리버스, 트리거드 업데이트 등의 기법이 사용된다. 거리 벡터 방식은 구현이 간단하고 라우터의 부하가 상대적으로 적지만, 수렴 속도가 느리고 대규모 네트워크에서 확장성이 제한될 수 있다.

다음 표는 두 알고리즘의 주요 특성을 비교한 것이다.

Dijkstra 알고리즘은 에츠허르 다익스트라가 1956년 고안한 그래프 이론 기반의 알고리즘으로, 하나의 노드에서 다른 모든 노드까지의 최단 경로를 찾는 데 사용된다. 네트워크 라우팅에서는 이 알고리즘을 기반으로 한 링크 상태 알고리즘이 구현되어, OSPF와 IS-IS 같은 내부 게이트웨이 프로토콜의 핵심이 된다. 알고리즘은 네트워크를 노드(라우터)와 간선(링크)으로 구성된 가중 그래프로 모델링하여 동작한다.

알고리즘의 동작 과정은 다음과 같다. 먼저, 출발지 노드를 제외한 모든 노드의 거리를 무한대로 초기화하고, 출발지 노드의 거리는 0으로 설정한다. 이후 아직 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택하여 '방문' 상태로 표시하고, 이 노드에 연결된 이웃 노드들의 거리를 갱신한다. 이때, 현재 노드를 경유하여 가는 경로의 비용이 기존에 알려진 비용보다 작으면 거리 정보를 업데이트한다. 이 과정을 모든 노드를 방문할 때까지 반복한다.

OSPF는 이 다익스트라 알고리즘을 SPF 계산에 적용한다. 각 OSPF 라우터는 링크 상태 광고를 통해 네트워크 전체의 토폴로지 정보를 수집하여 동일한 링크 상태 데이터베이스를 구축한다. 이 데이터베이스를 바탕으로 각 라우터는 자신을 루트로 하는 SPF 트리를 독립적으로 계산하여 최단 경로 트리를 도출하고, 그 결과를 라우팅 테이블에 반영한다. 이 방식은 네트워크 변화가 발생했을 때만 계산을 다시 수행하면 되므로 효율적이며, 계산 복잡도는 O(n log n)에 가깝다.

이 알고리즘의 적용은 네트워크의 확장성에 일정 제약을 준다. 큰 규모의 영역에서는 SPF 계산에 소요되는 시간과 자원이 증가할 수 있어, OSPF는 계층적 라우팅을 위해 영역을 분할하는 방식을 채택한다. 또한, 알고리즘 자체는 루프가 형성되지 않는 최단 경로 트리를 보장하지만, 네트워크 내에서 링크 상태 정보의 동기화가 완벽하게 이루어지지 않으면 일시적인 불일치가 발생할 수 있다[1].

Bellman-Ford 알고리즘은 거리 벡터 알고리즘의 대표적인 구현체로, 라우팅 정보 프로토콜(RIP)의 핵심 원리를 제공한다. 이 알고리즘은 각 라우터가 자신의 라우팅 테이블에 인접한 이웃 라우터까지의 거리(메트릭)와 그 이웃을 통해 도달할 수 있는 네트워크 목록을 유지하는 방식으로 동작한다. 주기적으로 또는 변화가 있을 때, 각 라우터는 자신의 거리 벡터 정보를 모든 이웃 라우터에게 광고한다. 이웃 라우터는 수신한 정보를 바탕으로 자신의 경로를 업데이트하는 과정을 반복하여 전체 네트워크에 대한 경로 정보가 전파된다.

알고리즘의 핵심 연산은 완화(relaxation) 과정이다. 출발지 라우터에서 목적지까지의 최단 경로 비용은 최대 (N-1)번의 반복을 통해 계산될 수 있다. 여기서 N은 네트워크 내 노드(라우터)의 총 수이다. 각 반복마다 모든 링크를 검사하여 현재 알려진 최단 경로보다 더 좋은 경로가 발견되면 라우팅 테이블을 갱신한다. 이 과정은 더 이상 갱신이 일어나지 않을 때까지, 즉 알고리즘이 수렴할 때까지 계속된다.

RIP는 Bellman-Ford 알고리즘을 적용한 대표적인 인트라도메인 라우팅 프로토콜이다. RIP는 홉 수를 유일한 메트릭으로 사용하며, 최대 허용 홉 수는 15로 제한된다[2]. 이는 카운트 투 인피니티(Count to Infinity) 문제와 같은 라우팅 루프 발생 가능성을 내포한다. 이러한 문제를 완화하기 위해 RIP는 스플릿 호라이즌(Split Horizon), 포이즌 리버스(Poison Reverse), 홀딩 다운(Hold-down) 타이머 등의 기법을 사용한다.

Bellman-Ford 알고리즘과 RIP의 주요 특징은 다음과 같이 정리할 수 있다.

이 알고리즘은 네트워크 토폴로지 변화에 대한 반응이 상대적으로 느리지만, 계산과 유지 관리가 간단하여 소규모 네트워크 환경에서 널리 사용되었다.

경계 경로 프로토콜(Border Gateway Protocol, BGP)은 인터넷의 핵심 백본을 이루는 자율 시스템(AS) 간에 경로 정보를 교환하는 데 사용되는 외부 게이트웨이 프로토콜(EGP)이다. 인터넷 서비스 제공자(ISP)들이 서로의 네트워크를 연결하고 전 세계적인 라우팅 정보를 공유할 수 있도록 하는 사실상의 표준 프로토콜이다. BGP는 거리 벡터 알고리즘의 원리를 기반으로 하지만, 경로 자체를 벡터로 전파하는 경로 벡터 프로토콜로 분류된다.

BGP는 신뢰성 있는 TCP 연결(포트 179)을 기반으로 동작하며, 피어라고 불리는 인접 BGP 라우터 간에 세션을 형성한다. 이 세션을 통해 네트워크 도달 가능성 정보가 교환된다. BGP가 교환하는 주요 정보는 NLRI(Network Layer Reachability Information)와 함께 여러 속성(어트리뷰트)으로 구성된 경로이다. 주요 어트리뷰트로는 AS 경로(AS_PATH), 다음 홉(NEXT_HOP), 로컬 프리퍼런스(LOCAL_PREF), 멀티 엑시트 디스크리미네이터(MED) 등이 있으며, 이러한 어트리뷰트 값들을 조합하여 최적의 경로를 선택한다.

BGP의 경로 선택 과정은 복잡한 의사 결정 알고리즘을 따른다. 동일한 목적지에 대한 여러 경로가 수신되면, 미리 정의된 순서대로 어트리뷰트를 비교하여 가장 우선순위가 높은 단 하나의 최적 경로를 선출한다. 이 과정에서 가장 중요한 원칙 중 하나는 AS_PATH의 길이를 가능한 한 짧게 유지하는 것이다. BGP의 운영 모드는 주로 두 가지로 나뉜다. 서로 다른 자율 시스템 간에 사용되는 eBGP(External BGP)와, 동일한 자율 시스템 내부의 라우터 간에 내부 경로 정보를 일관되게 유지하기 위해 사용되는 iBGP(Internal BGP)이다.

BGP는 기술적인 최단 경로보다는 사업적 정책과 신뢰 관계에 크게 영향을 받는 정책 기반 라우팅 프로토콜이다. 이로 인해 수렴 속도가 상대적으로 느리고, 잘못된 설정이 전 세계적인 라우팅 문제를 일으킬 수 있다는 취약점이 있다. 이러한 문제를 완화하기 위해 Route Flap Damping이나 보안 확장(BGPsec)과 같은 기법이 연구 및 적용되고 있다.

수렴 속도는 네트워크 토폴로지 변경 후 모든 라우터의 라우팅 테이블이 새로운 최적 경로 정보로 일치되고 안정화되기까지 걸리는 시간을 의미한다. 네트워크에서 링크 장애나 새로운 경로 추가와 같은 변화가 발생하면, 이 정보는 라우팅 프로토콜에 의해 점차적으로 네트워크 전체에 전파된다. 수렴 속도가 빠를수록 네트워크는 변화에 신속히 적응하여 데이터 패킷의 손실이나 지연을 최소화할 수 있다.

거리 벡터 알고리즘을 사용하는 RIP 같은 프로토콜은 일반적으로 느린 수렴 속도로 알려져 있다. 이는 변경 사항이 이웃 라우터에게 단계적으로 전파되는 '번-by-번' 방식으로 진행되기 때문이다. 반면, 링크 상태 알고리즘을 기반으로 하는 OSPF는 네트워크 전체의 토폴로지 맵을 각 라우터가 유지하고, 변화가 발생하면 이를 모든 라우터에 신속히 광고(플러딩)함으로써 상대적으로 빠른 수렴을 달성한다.

수렴 속도는 네트워크의 안정성과 직접적으로 연관된다. 느린 수렴은 일시적으로 불일치하는 라우팅 정보를 생성하여 라우팅 루프를 유발하거나, 패킷이 블랙홀이 되어 소실되는 현상을 초래할 수 있다. 따라서 현대 라우팅 프로토콜은 수렴 속도를 개선하기 위한 다양한 기법을 도입한다. 예를 들어, EIGRP는 DUAL 알고리즘을 사용하여 수렴 중에도 루프가 발생하지 않는 안정된 경로를 유지하면서 빠른 재계산을 가능하게 한다.

라우팅 루프는 패킷이 두 개 이상의 라우터 사이를 순환하며 목적지에 도달하지 못하는 현상이다. 이는 네트워크 대역폭을 낭비하고 패킷 손실을 유발하며, 심각한 경우 네트워크 성능을 급격히 저하시킨다. 라우팅 알고리즘은 이러한 루핑을 방지하거나 최소화하는 메커니즘을 필수적으로 포함한다.

주요 루핑 방지 기법으로는 다음과 같은 것들이 있다.

• 최대 홉 수 제한: RIP 같은 거리 벡터 프로토콜은 홉 카운트에 최대값(예: RIP의 15)을 설정한다. 이 값을 초과하는 패킷은 폐기되어 무한 순환을 방지한다.

• Split Horizon: 어떤 인터페이스를 통해 경로 정보를 학습했다면, 그 동일한 인터페이스로 그 경로 정보를 다시 광고하지 않는 규칙이다. 이는 두 라우터 간의 단순한 루프를 효과적으로 차단한다.

• Route Poisoning과 Hold-down Timer: 장애가 발생한 경로를 즉시 무한대(예: RIP의 경우 홉 수 16)의 메트릭으로 표시(포이즈닝)하여 네트워크 전체에 알리고, 일정 시간(홀드다운 타이머) 동안 그 경로에 대한 새로운 업데이트를 받지 않는다. 이는 잘못된 정보가 네트워크를 퍼지는 것을 지연시켜 수렴 중 발생하는 일시적 루프를 방지한다.

• 시퀀스 번호 및 에이징: OSPF 같은 링크 상태 알고리즘은 각 링크 상태 광고에 시퀀스 번호와 나이를 부여한다. 라우터는 항상 가장 최신의 정보만을 사용하며, 오래되거나 중복된 정보는 무시함으로써 일관된 토폴로지 뷰를 유지한다.

이러한 기법들은 알고리즘마다 조합되어 적용된다. 예를 들어, 거리 벡터 알고리즘은 주로 Split Horizon과 포이즈닝을, 링크 상태 알고리즘은 시퀀스 번호와 신속한 전체 정보 플러딩을 통해 루핑 문제를 근본적으로 해결한다. 효과적인 루핑 방지는 네트워크의 안정성과 신뢰성을 보장하는 핵심 요소이다.

확장성은 네트워크 규모가 커질수록 라우팅 알고리즘이 효율적으로 동작할 수 있는 능력을 의미한다. 라우팅 프로토콜이 처리해야 하는 라우팅 테이블의 크기, 라우팅 업데이트 메시지의 빈도와 양, 그리고 이를 계산하는 데 소요되는 CPU 및 메모리 자원은 네트워크의 크기와 직접적인 연관이 있다. 따라서 확장성이 높은 알고리즘은 대규모 네트워크, 특히 인터넷과 같은 글로벌 환경에서 안정적인 운영을 보장하는 핵심 요소이다.

확장성은 주로 라우팅 정보의 관리 방식에 따라 결정된다. 예를 들어, 거리 벡터 알고리즘은 네트워크 내 모든 경로 정보를 각 라우터가 유지해야 하므로, 네트워크 규모가 증가함에 따라 라우팅 테이블의 크기와 업데이트 트래픽이 선형적으로 증가할 수 있다. 반면, 링크 상태 알고리즘은 각 라우터가 전체 네트워크 토폴로지 맵을 유지하지만, 업데이트는 변화가 발생한 링크의 상태 정보만을 전파하는 방식으로 동작한다. 이는 네트워크가 안정적일 때 업데이트 트래픽을 줄일 수 있어 일정 수준의 확장성 이점을 제공한다.

최상위 수준의 확장성을 요구하는 인터넷 백본에서는 BGP가 사용된다. BGP는 자율 시스템 간의 라우팅을 담당하며, 전체 경로 벡터 정보를 교환하지만 연결 상태가 안정적일 때는 증분 업데이트 방식으로 동작한다. 또한, 라우팅 결정에 정책을 적용하여 불필요한 경로 정보의 전파를 제한할 수 있어, 수십만 개의 경로를 관리하는 데 필수적이다. 이러한 계층적 구조와 정보 은닉 기법은 모든 라우팅 알고리즘이 대규모 네트워크에 적용되기 위해 고려해야 할 확장성 설계의 기본 원칙이다.

소프트웨어 정의 네트워킹(SDN)은 기존의 네트워크 장비에서 통합되어 있던 제어 평면과 데이터 평면을 분리하는 새로운 네트워크 아키텍처이다. 이 아키텍처에서는 중앙 집중식 SDN 컨트롤러가 네트워크 전체의 지능(제어 기능)을 담당하고, 스위치나 라우터와 같은 네트워크 장치는 패킷 전달(데이터 전송)만을 수행한다. 컨트롤러는 OpenFlow와 같은 표준화된 인터페이스를 통해 네트워크 장치의 포워딩 테이블을 프로그래밍 방식으로 제어한다.

이러한 분리는 라우팅 알고리즘의 구현과 운영 방식에 근본적인 변화를 가져왔다. 기존 분산형 알고리즘 대신, 컨트롤러가 네트워크의 전역적 토폴로지 정보를 실시간으로 수집하고 중앙에서 최적의 경로를 계산한 후, 각 장치에 흐름 규칙을 설치한다. 이는 네트워크 정책의 유연한 적용, 자동화된 관리, 그리고 트래픽 엔지니어링의 정교한 구현을 가능하게 한다.

SDN 환경에서의 라우팅은 다음과 같은 특징을 가진다.

이 접근 방식은 클라우드 컴퓨팅 데이터 센터, 광역 네트워크, 그리고 5G 및 IoT 환경에서 네트워크 자원의 효율적이고 유연한 관리에 널리 적용되고 있다.

전통적인 라우팅 알고리즘이 고정된 규칙과 메트릭에 의존하는 반면, 머신러닝 기반 라우팅은 네트워크 상태 데이터를 학습하여 더욱 적응적이고 예측적인 경로 제어를 목표로 한다. 이 방식은 네트워크 트래픽 패턴, 링크 지연, 패킷 손실률, 대역폭 사용량 등의 방대한 실시간 및 역사적 데이터를 입력으로 사용한다. 신경망, 강화 학습, 시계열 분석 같은 머신러닝 모델을 통해 복잡한 패턴과 상관관계를 발견하고, 미래의 네트워크 상태나 트래픽 부하를 예측한다. 이를 바탕으로 알고리즘은 고정된 메트릭 계산을 넘어서 상황에 최적화된 라우팅 결정을 내릴 수 있다.

머신러닝 기반 라우팅의 주요 접근 방식은 강화 학습이다. 이 모델에서 에이전트(라우터 또는 SDN 컨트롤러)는 네트워크 환경에서의 행동(경로 선택)에 대한 보상(낮은 지연, 높은 처리량, 낮은 손실률)을 통해 학습한다. 시간이 지남에 따라 에이전트는 다양한 네트워크 조건 하에서 최대의 보상을 얻는 정책, 즉 최적의 라우팅 전략을 스스로 발전시킨다. 이는 특히 트래픽이 급변하거나 예측하기 어려운 데이터 센터나 광역 네트워크에서 기존 알고리즘이 따라잡기 힘든 동적 최적화를 가능하게 한다.

머신러닝 기반 라우팅의 장점과 과제는 다음과 같이 정리할 수 있다.

이 기술은 아직 연구 및 실험 단계에 머물러 있지만, 소프트웨어 정의 네트워킹과 결합되어 중앙집중식 컨트롤 플레인에서 머신러닝 모델을 운영하는 아키텍처가 활발히 탐구되고 있다. 네트워크의 복잡성이 증가하고 서비스 요구사항이 다양해짐에 따라, 머신러닝 기반 라우팅은 더욱 지능적이고 자율적인 네트워크 관리의 핵심 요소로 발전할 전망이다.