라우팅

섬네일
라우팅()은 네트워크 내에서 또는 여러 네트워크 간에 트래픽 경로를 선택하는 과정이다. 광범위하게 말하면 라우팅은 공중 교환 전화망(PSTN)과 같은 회선 교환망과 인터넷과 같은 컴퓨터 망을 포함하여 여러 유형의 네트워크에서 수행된다.

패킷 교환망에서 라우팅은 특정 패킷 포워딩 메커니즘을 통해 네트워크 패킷을 소스에서 목적지까지 중간 네트워크 노드를 거쳐 전달하는 상위 수준의 의사 결정이다. 패킷 포워딩은 네트워크 패킷이 하나의 네트워크 인터페이스에서 다른 인터페이스로 전송되는 것이다. 중간 노드는 일반적으로 라우터, 게이트웨이, 방화벽 또는 스위치와 같은 네트워크 하드웨어 장치이다. 일반 컴퓨터도 이 작업을 위한 특별히 최적화된 하드웨어는 없지만 패킷을 포워딩하고 라우팅을 수행한다.

라우팅 프로세스는 일반적으로 라우팅 테이블을 기반으로 포워딩을 지시한다. 라우팅 테이블은 다양한 네트워크 목적지로 가는 경로 기록을 유지한다. 라우팅 테이블은 관리자가 지정하거나, 네트워크 트래픽을 관찰하여 학습하거나, 라우팅 프로토콜의 도움을 받아 구축할 수 있다.

라우팅은 용어의 좁은 의미에서 종종 IP 라우팅을 의미하며 브리징과 대조된다. IP 라우팅은 네트워크 주소가 구조화되어 있으며 유사한 주소가 네트워크 내에서 근접함을 의미한다고 가정한다. 구조화된 주소는 단일 라우팅 테이블 항목이 장치 그룹으로 가는 경로를 나타낼 수 있도록 한다. 대규모 네트워크에서는 구조화된 주소 지정(좁은 의미의 라우팅)이 비구조화된 주소 지정(브리징)보다 성능이 우수하다. 라우팅은 인터넷에서 지배적인 주소 지정 형태가 되었다. 브리징은 근거리 통신망 내에서 여전히 널리 사용된다.

전송 방식

라우팅 방식은 메시지를 전달하는 방식에 따라 다르다:

유니캐스트는 인터넷에서 지배적인 메시지 전달 방식이다. 이 글은 유니캐스트 라우팅 알고리즘에 중점을 둔다.

토폴로지 분산
정적 라우팅을 사용하면 소규모 네트워크는 수동으로 구성된 라우팅 테이블을 사용할 수 있다. 대규모 네트워크는 빠르게 변경될 수 있는 복잡한 토폴로지를 가지고 있어 수동으로 라우팅 테이블을 구성하는 것이 불가능하다. 그럼에도 불구하고 대부분의 공중 교환 전화망(PSTN)은 미리 계산된 라우팅 테이블을 사용하며, 가장 직접적인 경로가 차단될 경우 대체 경로를 사용한다(PSTN의 라우팅 참조).

동적 라우팅은 라우팅 프로토콜에 의해 전달되는 정보를 기반으로 라우팅 테이블을 자동으로 구성하여 네트워크 오류 및 차단을 피하는 데 거의 자율적으로 작동할 수 있도록 하여 이 문제를 해결하려고 시도한다. 동적 라우팅은 인터넷을 지배한다. 동적 라우팅 프로토콜 및 알고리즘의 예로는 라우팅 정보 프로토콜(RIP), 최단 경로 우선 프로토콜(OSPF), EIGRP(EIGRP)가 있다.

거리 벡터 알고리즘

거리 벡터 알고리즘은 벨먼-포드 알고리즘을 사용한다. 이 접근 방식은 네트워크의 각 노드 간의 각 링크에 비용 번호를 할당한다. 노드는 노드 간 링크 비용의 합계인 가장 낮은 총 비용을 초래하는 경로를 통해 지점 A에서 지점 B로 정보를 보낸다.

노드가 처음 시작될 때, 노드는 즉각적인 이웃과 그들에게 도달하는 데 관련된 직접적인 비용만 안다. (이 정보—목적지 목록, 각 목적지까지의 총 비용, 데이터를 보내기 위한 다음 홉—는 라우팅 테이블 또는 거리 테이블을 구성한다.) 각 노드는 정기적으로 각 이웃 노드에게 자신이 알고 있는 모든 목적지에 도달하는 데 드는 총 비용에 대한 현재 평가를 보낸다. 이웃 노드는 이 정보를 검토하고 이미 알고 있는 정보와 비교한다. 이미 가지고 있는 정보에 대한 개선 사항이 있으면 자신의 테이블에 삽입한다. 시간이 지남에 따라 네트워크의 모든 노드는 모든 목적지에 대한 최적의 다음 홉과 총 비용을 발견한다.

네트워크 노드가 다운되면, 해당 노드를 다음 홉으로 사용했던 모든 노드는 해당 항목을 삭제하고 업데이트된 라우팅 정보를 모든 인접 노드에 전달하며, 인접 노드는 차례로 프로세스를 반복한다. 결국 네트워크의 모든 노드는 업데이트를 수신하고 다운된 노드를 포함하지 않는 모든 목적지에 대한 새로운 경로를 발견한다.

링크 상태 알고리즘

링크 상태 알고리즘을 적용할 때, 네트워크의 그래프 지도는 각 노드에 사용되는 기본 데이터이다. 지도를 생성하기 위해 각 노드는 연결할 수 있는 다른 노드에 대한 정보로 전체 네트워크를 플러딩한다. 그런 다음 각 노드는 이 정보를 독립적으로 지도로 조립한다. 이 지도를 사용하여 각 라우터는 데이크스트라 알고리즘과 같은 표준 최단 경로 알고리즘을 사용하여 자신부터 다른 모든 노드까지의 최소 비용 경로를 독립적으로 결정한다. 결과는 현재 노드를 루트로 하는 트리 그래프이며, 트리 내에서 루트에서 다른 노드까지의 경로는 해당 노드까지의 최소 비용 경로이다. 이 트리는 현재 노드에서 다른 노드로 가는 최적의 다음 홉을 지정하는 라우팅 테이블을 구성하는 데 사용된다.

최적화된 링크 상태 라우팅 알고리즘

모바일 애드혹 네트워크에 최적화된 링크 상태 라우팅 알고리즘은 OLSR(Optimized Link State Routing Protocol)이다.RFC 3626 OLSR은 능동적이며, Hello 및 토폴로지 제어(TC) 메시지를 사용하여 모바일 애드혹 네트워크를 통해 링크 상태 정보를 검색하고 전파한다. Hello 메시지를 사용하여 각 노드는 2-홉 이웃 정보를 검색하고 다지점 릴레이(MPR) 세트를 선택한다. MPR은 OLSR을 다른 링크 상태 라우팅 프로토콜과 구별한다.

경로 벡터 프로토콜

거리 벡터 및 링크 상태 라우팅은 모두 도메인 내 라우팅 프로토콜이다. 이들은 자율 시스템(Autonomous system) 내부에서 사용되지만 자율 시스템 간에는 사용되지 않는다. 이 두 라우팅 프로토콜은 모두 대규모 네트워크에서는 다루기 힘들며 도메인 간 라우팅에는 사용할 수 없다. 거리 벡터 라우팅은 도메인에 몇 개 이상의 홉이 있을 경우 불안정해질 수 있다. 링크 상태 라우팅은 라우팅 테이블을 계산하는 데 상당한 자원이 필요하다. 또한 플러딩으로 인해 많은 트래픽을 생성한다.

경로 벡터 라우팅은 도메인 간 라우팅에 사용된다. 이는 거리 벡터 라우팅과 유사하다. 경로 벡터 라우팅은 각 자율 시스템에 있는 하나의 노드(여러 개가 있을 수 있음)가 전체 자율 시스템을 대신하여 작동한다고 가정한다. 이 노드를 스피커 노드라고 한다. 스피커 노드는 라우팅 테이블을 생성하고 인접 자율 시스템의 인접 스피커 노드에게 광고한다. 아이디어는 거리 벡터 라우팅과 동일하지만, 각 자율 시스템의 스피커 노드만 서로 통신할 수 있다는 점이 다르다. 스피커 노드는 자체 자율 시스템 또는 다른 자율 시스템의 노드에 대한 메트릭이 아닌 경로를 광고한다.

경로 벡터 라우팅 알고리즘은 각 경계 라우터가 인접 라우터에 도달할 수 있는 목적지를 광고한다는 점에서 거리 벡터 알고리즘과 유사하다. 그러나 네트워크는 목적지와 그 목적지까지의 거리를 기준으로 광고되는 대신, 목적지 주소와 해당 목적지에 도달하기 위한 경로 설명으로 광고된다. 지금까지 통과한 도메인(또는 연합)으로 표현되는 경로는 도달 가능성 정보가 통과한 라우팅 도메인의 순서를 기록하는 특수 경로 속성에 포함된다. 경로는 목적지와 해당 목적지까지의 경로 속성 간의 쌍으로 정의된다. 따라서 경로 벡터 라우팅이라는 이름이 붙었다. 라우터는 일련의 목적지까지의 경로를 포함하는 벡터를 수신한다.

경로 선택
경로 선택은 여러 경로에 라우팅 메트릭을 적용하여 최적의 경로를 선택(또는 예측)하는 것을 포함한다. 대부분의 라우팅 알고리즘은 한 번에 하나의 네트워크 경로만 사용한다. 멀티패스 라우팅 및 특히 ECMP(equal-cost multi-path routing) 기술은 여러 대체 경로를 사용할 수 있도록 한다.

컴퓨터 네트워킹에서 메트릭은 라우팅 알고리즘에 의해 계산되며, 대역폭, 네트워크 지연, 홉 수, 경로 비용, 부하, 최대 전송 단위, 신뢰성 및 통신 비용과 같은 정보를 포함할 수 있다. 라우팅 테이블은 가장 좋은 경로만 저장하는 반면, 링크 상태 또는 토폴로지 데이터베이스는 다른 모든 정보도 저장할 수 있다.

경로가 중복되거나 동일한 경우, 알고리즘은 다음 요소를 우선순위 순서로 고려하여 라우팅 테이블에 설치할 경로를 결정한다:
 프리픽스 길이: 서브넷 마스크가 더 긴 일치하는 라우팅 테이블 항목이 대상(목적지)을 더 정확하게 지정하므로 항상 선호된다.
 메트릭: 동일한 라우팅 프로토콜을 통해 학습된 경로를 비교할 때, 메트릭이 낮은 경로가 선호된다. 다른 라우팅 프로토콜에서 학습된 경로 간에는 메트릭을 비교할 수 없다.
 관리 거리: 다른 라우팅 프로토콜 및 정적 구성과 같은 다른 소스에서 온 경로 테이블 항목을 비교할 때, 관리 거리가 낮으면 더 신뢰할 수 있는 소스이며 따라서 선호되는 경로를 나타낸다.

라우팅 메트릭은 주어진 라우팅 프로토콜에 특화되어 있으므로, 다중 프로토콜 라우터는 다른 라우팅 프로토콜에서 학습된 경로 중에서 선택하기 위해 일부 외부 휴리스틱을 사용해야 한다. 예를 들어 시스코 라우터는 각 경로에 관리 거리라는 값을 부여하는데, 관리 거리가 작을수록 더 신뢰할 수 있다고 가정되는 프로토콜에서 학습된 경로를 나타낸다.

지역 관리자는 네트워크 사용을 더 잘 제어하고, 테스트를 허용하며, 전반적인 보안을 향상시키는 호스트별 경로를 설정할 수 있다. 이는 네트워크 연결 또는 라우팅 테이블 디버깅에 유용하다.

일부 소규모 시스템에서는 단일 중앙 장치가 모든 패킷의 전체 경로를 미리 결정한다. 다른 일부 소규모 시스템에서는 네트워크에 패킷을 주입하는 엣지 장치가 해당 특정 패킷의 전체 경로를 미리 결정한다. 어느 경우든 경로 계획 장치는 네트워크에 어떤 장치가 연결되어 있고 서로 어떻게 연결되어 있는지에 대한 많은 정보를 알아야 한다. 이 정보를 얻으면 A* 알고리즘과 같은 알고리즘을 사용하여 최적의 경로를 찾을 수 있다.

고속 시스템에서는 매초 전송되는 패킷이 너무 많아서 단일 장치가 모든 패킷에 대한 전체 경로를 계산하는 것이 불가능하다. 초기 고속 시스템은 회선 교환 방식으로 이 문제를 해결했는데, 특정 소스와 특정 목적지 간의 첫 번째 패킷에 대해 경로를 한 번 설정하고, 이후 동일한 소스와 목적지 간의 패킷은 회선 해제될 때까지 재계산 없이 동일한 경로를 계속 따른다. 후기 고속 시스템은 어떤 장치도 패킷의 전체 경로를 계산하지 않고 네트워크에 패킷을 주입한다.

대규모 시스템에서는 장치 간의 연결이 너무 많고 이러한 연결이 너무 자주 변경되므로 어떤 한 장치가 모든 장치가 서로 어떻게 연결되어 있는지 아는 것조차 불가능하며, 그들을 통해 완전한 경로를 계산하는 것은 더욱 불가능하다. 이러한 시스템은 일반적으로 다음 홉 라우팅을 사용한다.

대부분의 시스템은 결정론적 동적 라우팅 알고리즘을 사용한다. 장치가 특정 최종 목적지로 가는 경로를 선택할 때, 해당 장치는 다른 경로가 더 낫다고 생각하게 만드는 정보를 수신할 때까지 항상 동일한 경로를 선택한다.

일부 라우팅 알고리즘은 패킷이 원래 소스에서 최종 목적지로 이동하는 데 최적의 링크를 찾기 위해 결정론적 알고리즘을 사용하지 않는다. 대신, 패킷 시스템에서 혼잡 핫스팟을 피하기 위해 일부 알고리즘은 무작위로 선택된 중간 목적지로 경로를 지정하고 거기에서 실제 최종 목적지로 이동하는 무작위 알고리즘인 Valiant의 패러다임을 사용한다. 많은 초기 전화 교환기에서는 다단계 스위칭 패브릭을 통한 경로의 시작을 선택하는 데 무작위화 장치가 자주 사용되었다.

경로 선택이 수행되는 응용 프로그램에 따라 다른 메트릭을 사용할 수 있다. 예를 들어, 웹 요청의 경우 웹 페이지 로드 시간을 최소화하기 위해 최소 지연 시간 경로를 사용할 수 있으며, 대용량 데이터 전송의 경우 네트워크 전체에 부하를 분산하고 처리량을 늘리기 위해 가장 적게 활용되는 경로를 선택할 수 있다. 인기 있는 경로 선택 목표는 트래픽 흐름의 평균 완료 시간과 총 네트워크 대역폭 소비를 줄이는 것이다. 최근에는 경로당 에지에서 예약된 총 바이트 수를 선택 메트릭으로 계산하는 경로 선택 메트릭이 제안되었다. 이 새로운 제안을 포함한 여러 경로 선택 메트릭에 대한 실증 분석이 제공되었다.

여러 에이전트
일부 네트워크에서는 단일 개체가 경로 선택을 책임지지 않고 여러 개체가 경로 또는 단일 경로의 일부를 선택하는 데 관여하므로 라우팅이 복잡해진다. 이러한 개체가 다른 참여자의 목표와 충돌할 수 있는 자신의 목표를 최적화하기 위해 경로를 선택하면 합병증이나 비효율성이 발생할 수 있다.

고전적인 예로는 각 운전자가 자신의 이동 시간을 최소화하는 경로를 선택하는 도로 시스템의 교통량이 있다. 이러한 라우팅에서는 균형 경로가 모든 운전자에게 최적보다 길 수 있다. 특히 브라에스의 역설은 새로운 도로를 추가하는 것이 모든 운전자의 이동 시간을 길게 할 수 있음을 보여준다.

예를 들어 터미널에서 자동 유도 차량(AGV) 라우팅에 사용되는 단일 에이전트 모델에서는 인프라의 동일한 부분을 동시에 사용하는 것을 방지하기 위해 각 차량에 대한 예약이 이루어진다. 이 접근 방식은 상황 인식 라우팅이라고도 한다. In R.R. Negenborn and Z. Lukszo and H. Hellendoorn (Eds.) Intelligent Infrastructures, Ch. 14, pp. 355–382. Springer.

인터넷은 자율 시스템(AS)(예: ISP)으로 분할되어 있으며, 각 AS는 자체 네트워크와 관련된 경로를 제어한다. 라우팅은 여러 수준에서 발생한다. 먼저, 패킷이 흐르는 AS의 시퀀스를 생성하는 BGP 프로토콜을 통해 AS 수준 경로가 선택된다. 각 AS는 인접 AS에서 제공하는 여러 경로 중에서 선택할 수 있다. 이러한 라우팅 결정은 종종 경로 품질이나 지연 시간과 관련이 없는 이러한 인접 AS와의 비즈니스 관계와 관련이 있다.Matthew Caesar and Jennifer Rexford. "BGP routing policies in ISP networks". IEEE Network Magazine, special issue on Interdomain Routing, Nov/Dec 2005. 둘째, AS 수준 경로가 선택되면 종종 여러 개의 해당 라우터 수준 경로 중에서 선택할 수 있다. 이는 부분적으로 두 ISP가 여러 연결을 통해 연결될 수 있기 때문이다. 단일 라우터 수준 경로를 선택할 때 각 ISP가 핫 포테이토 라우팅을 사용하는 것이 일반적이다. 즉, 대상까지의 총 거리를 늘리더라도 ISP 자체 네트워크를 통해 거리를 최소화하는 경로를 따라 트래픽을 전송하는 것이다.

예를 들어, 두 ISP, A와 B를 고려해보자. 각 ISP는 뉴욕에 존재하며, 지연 시간 의 빠른 링크로 연결되어 있으며, 각 ISP는 런던에 존재하며 5 ms 링크로 연결되어 있다. 두 ISP 모두 두 네트워크를 연결하는 대서양 횡단 링크를 가지고 있지만, A의 링크는 지연 시간이 100 ms이고 B의 링크는 지연 시간이 120 ms라고 가정해보자. A의 런던 네트워크에 있는 소스에서 B의 뉴욕 네트워크에 있는 목적지로 메시지를 라우팅할 때, A는 런던에서 B로 즉시 메시지를 보내기로 선택할 수 있다. 이렇게 하면 A는 값비싼 대서양 횡단 링크를 따라 메시지를 보내는 수고를 덜 수 있지만, 다른 경로가 20 ms 더 빨랐을 때 메시지가 125 ms의 지연 시간을 경험하게 된다.

또한, 유사한 라우팅 문제는 셀룰러 네트워크에서 관찰될 수 있는데, 여기서 다른 패킷은 다양한 엔드포인트로 향하고 각 링크는 다양한 스펙트럼 효율성을 나타낸다. 이 맥락에서 최적의 경로 선택은 지연 시간과 패킷 오류율을 고려해야 한다. 이를 해결하기 위해 각 기지국에 대해 여러 독립적인 엔티티가 전반적인 네트워크 성능을 최적화하기 위해 경로 선택에 중요한 역할을 한다.Shahaf Yamin and Haim H. Permuter. "Multi-agent reinforcement learning for network routing in integrated access backhaul networks". Ad Hoc Networks, Volume 153, 2024, 103347, , .

2003년 인터넷 경로 측정 연구에 따르면, 인접 ISP 쌍 간에 30% 이상의 경로가 핫 포테이토 라우팅으로 인해 지연 시간이 증가했으며, 5%의 경로가 최소 12 ms 지연되었다고 한다. AS 수준 경로 선택으로 인한 증가는 상당했지만, 주로 BGP가 지연 시간을 직접 최적화하는 메커니즘이 부족했기 때문이지 이기적인 라우팅 정책 때문은 아니라고 한다. 또한 적절한 메커니즘이 마련된다면 ISP가 핫 포테이토 라우팅 대신 지연 시간을 줄이기 위해 협력할 의사가 있을 것이라고 제안되었다.Neil Spring, Ratul Mahajan, and Thomas Anderson. "Quantifying the Causes of Path Inflation". Proc. SIGCOMM 2003. 이러한 메커니즘은 나중에 동일한 저자들이 먼저 두 ISP의 경우Ratul Mahajan, David Wetherall, and Thomas Anderson. "Negotiation-Based Routing Between Neighboring ISPs". Proc. NSDI 2005. 그리고 전 세계적인 경우Ratul Mahajan, David Wetherall, and Thomas Anderson. Mutually Controlled Routing with Independent ISPs. Proc. NSDI 2007.에 대해 발표되었다.

경로 분석
인터넷과 IP 네트워크가 미션 크리티컬 비즈니스 도구가 되면서 네트워크의 라우팅 자세를 모니터링하는 기술과 방법에 대한 관심이 증가했다. 잘못된 라우팅 또는 라우팅 문제는 바람직하지 않은 성능 저하, 경로 플래핑 또는 다운타임을 유발한다. 네트워크 라우팅 모니터링은 경로 분석 도구 및 기술을 사용하여 달성된다.

중앙 집중식 라우팅
논리적으로 중앙 집중식 제어가 포워딩 상태에서 사용 가능한 네트워크, 예를 들어 소프트웨어 정의 네트워킹을 사용하는 네트워크에서는 전역 및 네트워크 전체 성능 메트릭을 최적화하는 것을 목표로 하는 라우팅 기술을 사용할 수 있다. 이는 사설 광학 링크를 사용하여 여러 지리적 위치에 많은 데이터 센터를 운영하는 대규모 인터넷 회사에서 사용되었으며, 그 예로는 마이크로소프트의 글로벌 WAN, 페이스북의 Express Backbone, 및 구글의 B4가 있다.

최적화할 글로벌 성능 메트릭에는 네트워크 활용도 극대화, 트래픽 흐름 완료 시간 최소화, 특정 기한 전에 전달되는 트래픽 최대화, 흐름 완료 시간 단축 등이 포함된다. 사설 WAN을 통한 후자의 연구에서는 모든 큐잉을 엔드포인트로 푸싱하여 라우팅을 그래프 최적화 문제로 모델링하는 것을 논의한다. 저자는 또한 성능 손실을 무시할 수 있는 수준으로 희생하면서 문제를 효율적으로 해결하기 위한 휴리스틱을 제안한다.

 같이 보기 
 사이더 (네트워킹) (CIDR)
 비동기 전송 방식 (ATM)

 각주 

 외부 링크 

 Count-To-Infinity Problem 
 "Stability Features" are ways of avoiding the "count to infinity" problem.
 Cisco IT Case Studies about Routing and Switching


분류:인터넷 구조