라우팅

3. 라우팅 방식

라우팅 방식은 메시지 전달 방식에 따라 다음과 같이 분류된다.

방식	설명	그림
유니캐스트	단일 특정 노드에 메시지를 전달한다.
브로드캐스트	네트워크의 모든 노드에 메시지를 전달한다.
멀티캐스트	메시지를 수신하는 데 관심이 있는 노드 그룹으로 메시지를 전달한다.
애니캐스트	노드 그룹 중 임의의 노드로 메시지를 전달한다. (일반적으로 가장 가까운 노드)
geocast|지오캐스트영어	지리적 영역에 메시지를 전달한다.

유니캐스트는 인터넷에서 주로 사용되는 메시지 전달 방식이다.^[22]

3. 1. 유니캐스트 (Unicast)

3. 2. 브로드캐스트 (Broadcast)

3. 3. 멀티캐스트 (Multicast)

3. 4. 애니캐스트 (Anycast)

4. 라우팅 알고리즘

라우팅 알고리즘은 네트워크에서 최적의 경로를 계산하는 데 사용되는 수학적 방법이다. 라우팅 알고리즘에는 크게 거리 벡터 알고리즘(Distance Vector Algorithm, DVA)과 링크 상태 알고리즘(Link State Algorithm, LSA) 두 가지 주요 유형이 있다.

거리 벡터 알고리즘은 벨만-포드 알고리즘을 사용하여 네트워크 내 각 노드 간 링크에 '비용'을 할당하고, 최저 총 비용 경로를 통해 정보를 전송한다. 각 노드는 자신의 라우팅 테이블을 유지하며, 주기적으로 이웃 노드와 정보를 교환하여 최적 경로를 찾는다.

링크 상태 알고리즘은 각 노드가 네트워크의 그래프 맵을 사용하여 다익스트라 알고리즘과 같은 최단 경로 알고리즘으로 최저 비용 경로를 결정한다. 각 노드는 연결 가능한 노드 정보를 네트워크 전체에 알리고, 이를 바탕으로 독립적으로 최단 경로 트리를 구성하여 라우팅 테이블을 만든다.

이 외에도 도메인 간 라우팅에 사용되는 경로 벡터 프로토콜, 모바일 애드혹 네트워크에 최적화된 최적화된 링크 상태 라우팅 프로토콜(OLSR) 등이 있다.

4. 1. 거리 벡터 알고리즘 (Distance Vector Algorithm)

5. 라우티드 프로토콜과 라우팅 프로토콜

라우티드 프로토콜과 라우팅 프로토콜은 흔히 혼동되지만, 서로 다른 개념이다.^[22]

• '''라우티드 프로토콜(Routed protocols)'''은 네트워크 프로토콜 중 패킷 전송에 필요한 네트워크 계층 주소 정보를 충분히 제공하는 프로토콜을 말한다. 인터넷 프로토콜이 대표적인 예이다.
• '''라우팅 프로토콜'''은 네트워크 간에 라우팅 정보를 교환하여 라우터가 동적으로 라우팅 테이블을 생성하도록 하는 프로토콜이다.

5. 1. 라우티드 프로토콜 (Routed Protocol)

5. 2. 라우팅 프로토콜 (Routing Protocol)

• '''내부 게이트웨이 프로토콜(IGPs)''': 단일 자율 시스템(AS) 내에서 사용되는 라우팅 프로토콜이다.
• IGRP (Interior Gateway Routing Protocol)
• EIGRP (Enhanced Interior Gateway Routing Protocol)
• OSPF (Open Shortest Path First, 최단 경로 우선)
• RIP (Routing Information Protocol, 라우팅 정보 프로토콜)
• IS-IS (Intermediate System to Intermediate System, 중간 시스템 간 프로토콜)
• '''외부 게이트웨이 프로토콜(EGPs)''': 서로 다른 AS 간에 라우팅 정보를 교환하는 데 사용되는 프로토콜이다.
• EGP: 과거 인터넷 백본 연결에 사용되었던 프로토콜이다.
• BGP (Border Gateway Protocol, 경계 게이트웨이 프로토콜): 현재 인터넷에서 사용되는 표준 외부 게이트웨이 프로토콜 (BGPv4)이다. 1995년경 채택되었다.
• '''애드혹 네트워크 (Ad hoc network) 라우팅 프로토콜''': 기반 시설이 거의 없거나 아예 없는 환경에서 구성되는 네트워크를 위한 프로토콜이다.

6. 라우팅 프로토콜의 종류

라우팅 프로토콜은 네트워크 간에 라우팅 정보를 교환하여 라우터가 동적으로 라우팅 테이블을 생성할 수 있도록 하는 방법이다. 인터넷 프로토콜(IP) 기반 라우팅은 패킷을 전송할 다음 홉(hop)만을 고려하면 되므로 단순하지만, 동적 라우팅은 인터넷의 유연성을 높여 IP 네트워크 규모 확장에 기여했다.

라우팅 메트릭은 경로의 우열을 비교하는 값으로, 대역폭, 지연, 홉 수, 경로 비용, 부하, 최대 전송 단위(MTU), 신뢰성, 통신 비용 등이 사용된다. 라우팅 테이블은 최적 경로만 기록하지만, 링크 상태나 토폴로지 데이터베이스는 더 많은 정보를 가질 수 있다. 관리 거리는 여러 라우팅 프로토콜이 동일한 대상에 대해 서로 다른 최적 경로를 제안할 때, 가장 신뢰할 수 있는 프로토콜을 선택하는 데 사용되는 값이다. 일반적으로 값이 낮을수록 우선순위가 높다.

라우팅 프로토콜은 라우터의 상대적 위치에 따라 다음과 같이 분류할 수 있다.

라우티드 프로토콜은 네트워크 계층 주소에 충분한 정보를 제공하여 패킷 전송을 가능하게 하는 네트워크 프로토콜이다. 인터넷 프로토콜이 대표적이다.

6. 1. 내부 게이트웨이 프로토콜 (Interior Gateway Protocols, IGPs)

• IGRP (Interior Gateway Routing Protocol)
• EIGRP (Enhanced Interior Gateway Routing Protocol)
• OSPF (Open Shortest Path First, 최단 경로 우선)
• RIP (Routing Information Protocol, 라우팅 정보 프로토콜)
• IS-IS (Intermediate System to Intermediate System, 중간 시스템 간 프로토콜)

6. 2. 외부 게이트웨이 프로토콜 (Exterior Gateway Protocols, EGPs)

• EGP - 이전에 인터넷 백본 연결용으로 사용된 프로토콜이다.
• BGP(Border Gateway Protocol, 경계 게이트웨이 프로토콜) - 현재 버전은 BGPv4이며, 1995년경 채택되었다.

6. 3. 애드혹 네트워크 라우팅 프로토콜

7. 경로 선택 (Path Selection)

경로 선택은 여러 경로에 라우팅 메트릭을 적용하여 최적의 경로를 선택하거나 예측하는 것이다. 대부분의 라우팅 알고리즘은 한 번에 하나의 네트워크 경로만 사용하지만, 다중 경로 라우팅과 특히 동일 비용 다중 경로 라우팅 기술은 여러 대체 경로를 사용할 수 있게 한다.

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

겹치거나 동일한 경로의 경우, 알고리즘은 다음 요소를 우선순위에 따라 고려하여 라우팅 테이블에 설치할 경로를 결정한다.

# '''접두사 길이:''' 더 긴 서브넷 마스크를 가진 라우팅 테이블 항목은 대상을 더 정확하게 지정하므로 항상 우선시된다.

# '''메트릭:''' 동일한 라우팅 프로토콜을 통해 학습된 경로를 비교할 때, 더 낮은 메트릭이 우선시된다. 서로 다른 라우팅 프로토콜에서 학습된 경로 간에는 메트릭을 비교할 수 없다.

# '''관리 거리:''' 서로 다른 라우팅 프로토콜 및 정적 구성을 비롯한 서로 다른 소스의 라우팅 테이블 항목을 비교할 때, 더 낮은 관리 거리는 더 신뢰할 수 있는 소스를 나타내므로 선호되는 경로이다.

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

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

일부 소규모 시스템에서는 단일 중앙 장치나 엣지 장치가 패킷의 전체 경로를 미리 결정한다. 경로 계획 장치는 네트워크 장치 연결 정보를 알고 있어야 하며, A* 검색 알고리즘과 같은 알고리즘을 사용하여 최적의 경로를 찾을 수 있다.

고속 시스템에서는 매초 너무 많은 패킷이 전송되어 단일 장치가 각 패킷의 전체 경로를 계산하는 것이 불가능하다. 초기 고속 시스템은 회선 교환을 통해, 이후의 고속 시스템은 패킷에 대한 전체 경로를 계산하는 장치 없이 패킷을 네트워크에 주입하는 방식으로 처리했다.

대규모 시스템에서는 장치 간 연결이 너무 많고 자주 변경되어 단일 장치가 모든 연결을 파악하거나 전체 경로를 계산하기 어렵다. 이러한 시스템은 일반적으로 다음 홉 라우팅을 사용한다.

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

일부 라우팅 알고리즘은 패킷 시스템의 혼잡 핫스팟을 피하기 위해 임의 알고리즘(Valiant의 패러다임)을 사용한다.^[5][6] 많은 초기 전화 교환기에서는 다단계 스위칭 패브릭을 통한 경로의 시작을 선택하기 위해 종종 랜덤화기가 사용되었다.

경로 선택은 애플리케이션에 따라 서로 다른 메트릭을 사용할 수 있다. 예를 들어, 웹 요청은 최소 지연 시간 경로를, 대량 데이터 전송은 부하 분산을 위해 가장 덜 사용되는 경로를 선택할 수 있다. 일반적인 경로 선택 목표는 트래픽 흐름의 평균 완료 시간과 총 네트워크 대역폭 소비를 줄이는 것이다. 최근에는 경로당 엣지에서 예약된 총 바이트 수를 계산하는 경로 선택 메트릭이 제안되었다.^[7] 여러 경로 선택 메트릭에 대한 경험적 분석이 제공되었다.^[8]

8. 다중 에이전트 (Multiple agents)

일부 네트워크에서는 라우팅이 단일 주체가 아닌 여러 주체가 경로를 선택하기 때문에 복잡해진다. 이러한 주체들이 자신의 목표를 최적화하면 다른 참여자의 목표와 충돌하여 비효율성을 초래할 수 있다.

도로 시스템의 교통 흐름을 예로 들 수 있는데, 각 운전자는 이동 시간을 최소화하는 경로를 선택한다. 이러한 라우팅에서 균형 경로는 모든 운전자에게 최적 경로보다 길어질 수 있다. 브래스 역설은 새로운 도로를 추가하면 오히려 모든 운전자의 이동 시간이 늘어날 수 있음을 보여준다.

자동 유도 차량(AGV)을 라우팅하는 단일 에이전트 모델에서는 각 차량이 인프라의 동일한 부분을 동시에 사용하지 않도록 예약한다. 이 방식은 컨텍스트 인식 라우팅이라고도 한다.

인터넷은 각 네트워크를 제어하는 자율 시스템(AS) (예: 인터넷 서비스 제공업체(ISP))으로 분할된다. 라우팅은 여러 수준에서 발생한다. 먼저, BGP 프로토콜을 통해 AS 수준 경로가 선택되어 패킷이 통과하는 AS 시퀀스를 생성한다. 각 AS는 인접 AS에서 제공하는 여러 경로를 선택할 수 있다. 이러한 결정은 종종 인접 AS와의 비즈니스 관계와 관련되며, 경로 품질이나 대기 시간과는 관련이 없을 수 있다. AS 수준 경로가 선택되면 여러 개의 해당 라우터 수준 경로가 있을 수 있는데, 이는 두 ISP가 여러 연결을 통해 연결될 수 있기 때문이다. 단일 라우터 수준 경로를 선택할 때 각 ISP는 핫 포테이토 라우팅을 사용하는 것이 일반적이다. 즉, 대상까지의 총 거리가 길어지더라도 ISP 자체 네트워크를 통과하는 거리를 최소화하는 경로를 따라 트래픽을 전송한다.

예를 들어, ISP ''A''와 ''B''가 뉴욕과 런던에 각각 존재하며, 두 도시는 대기 시간이 5ms인 빠른 링크로 연결되어 있다고 가정한다. 두 ISP 모두 대서양 횡단 링크가 있지만, ''A''의 링크는 대기 시간이 100ms이고 ''B''의 링크는 120ms이다. ''A''의 런던 네트워크에서 ''B''의 뉴욕 네트워크로 메시지를 라우팅할 때, ''A''는 런던에서 ''B''로 즉시 메시지를 보낼 수 있다. 이렇게 하면 ''A''는 대서양 횡단 링크를 사용하는 노력을 덜 수 있지만, 다른 경로가 20ms 더 빠를 때 메시지는 125ms의 대기 시간을 경험하게 된다.

셀룰러 네트워크에서도 유사한 라우팅 문제가 발생하며, 서로 다른 패킷이 다양한 엔드포인트를 대상으로 하고 각 링크가 다양한 스펙트럼 효율성을 나타낸다. '최적' 경로를 선택하려면 대기 시간과 패킷 오류율을 고려해야 한다. 이를 해결하기 위해 각 기지국마다 하나씩 여러 개의 독립적인 주체가 전체 네트워크 성능을 최적화하기 위해 경로 선택에 중요한 역할을 한다.

2003년 인터넷 경로 측정 연구에 따르면, 인접한 ISP 쌍 간에 30% 이상의 경로가 핫 포테이토 라우팅으로 인해 대기 시간이 증가했으며, 5%의 경로는 최소 12ms 지연되었다. AS 수준 경로 선택으로 인한 증가는 상당했지만, 이기적인 라우팅 정책보다는 BGP에 대기 시간을 직접 최적화하는 메커니즘이 부족했기 때문이라고 한다. 또한 적절한 메커니즘이 마련되면 ISP가 핫 포테이토 라우팅 대신 대기 시간을 줄이기 위해 협력할 것이라고 제안되었다. 이러한 메커니즘은 나중에 동일한 저자에 의해 처음에는 두 ISP, 그 다음에는 글로벌 사례에 대해 발표되었다.

9. 중앙 집중식 라우팅 (Centralized routing)

소프트웨어 정의 네트워킹과 같이 논리적으로 중앙 집중화된 제어가 전달 상태에서 가능한 네트워크에서는, 전역 및 네트워크 전체의 성능 지표를 최적화하는 것을 목표로 하는 라우팅 기술을 사용할 수 있다. 이는 개인 광 링크를 사용하여 연결된 여러 지리적 위치에서 많은 데이터 센터를 운영하는 대규모 인터넷 회사에서 사용되었으며, 마이크로소프트의 글로벌 WAN,^[16] 페이스북의 익스프레스 백본,^[17] 구글의 B4^[18] 등이 그 예이다.

최적화할 전역 성능 지표에는 네트워크 활용도 극대화, 트래픽 흐름 완료 시간 최소화, 특정 마감 시간 전에 제공되는 트래픽 극대화, 흐름 완료 시간 단축 등이 포함된다.^[19] 개인 WAN에서의 후속 연구에서는 모든 대기열을 종점으로 밀어넣어 라우팅을 그래프 최적화 문제로 모델링하는 방법을 논의한다. 또한, 연구자들은 성능을 거의 희생하지 않으면서 문제를 효율적으로 해결하는 휴리스틱을 제안한다.^[20]

참조

_[1] 간행물 Tabu search algorithm for routing, modulation and spectrum allocation in elastic optical network with anycast and unicast traffic https://www.scienced[...] 2015-03-14
_[2] 문서 RFC 3626
_[3] IETF RFC 1322
_[4] citation A Survey on Routing Metrics http://rainer.bauman[...] 2007-02-10
_[5] citation The Power of Two Random Choices: A Survey of Techniques and Results http://www.eecs.harv[...]
_[6] citation The IEEE 1355 Standard: Developments, Performance and Application in High Energy Physics http://inspirehep.ne[...] 1998
_[7] 웹사이트 Poster Abstract: Minimizing Flow Completion Times using Adaptive Routing over Inter-Datacenter Wide Area Networks https://www.research[...] 2018-04
_[8] 웹사이트 Minimizing Flow Completion Times using Adaptive Routing over Inter-Datacenter Wide Area Networks https://www.research[...] 2018-04
_[9] 웹사이트 Dealing with Uncertainty in Operational Transport Planning http://www.st.ewi.tu[...] 2010
_[10] 문서 BGP routing policies in ISP networks http://www.cs.prince[...] IEEE Network Magazine 2005-11
_[11] 간행물 Multi-agent reinforcement learning for network routing in integrated access backhaul networks https://www.scienced[...] 2024
_[12] 문서 Quantifying the Causes of Path Inflation http://www.cs.washin[...] Proc. [[SIGCOMM]] 2003
_[13] 문서 Negotiation-Based Routing Between Neighboring ISPs http://research.micr[...] Proc. [[NSDI]] 2005
_[14] 문서 Mutually Controlled Routing with Independent ISPs http://research.micr[...] Proc. [[NSDI]] 2007
_[15] 서적 An Efficient Security Way of Authentication and Pair wise Key Distribution with Mobile Sinks in Wireless Sensor Networks
_[16] 웹사이트 How Microsoft builds its fast and reliable global network https://azure.micros[...] 2017-03-15
_[17] 웹사이트 Building Express Backbone: Facebook's new long-haul network https://code.fb.com/[...] 2017-05-01
_[18] 웹사이트 Inside Google's Software-Defined Network https://www.networkc[...] 2017-05-14
_[19] 간행물 Datacenter Traffic Control: Understanding Techniques and Tradeoffs 2018-07-16
_[20] 간행물 On Minimizing the Completion Times of Long Flows over Inter-Datacenter WAN https://www.research[...] 2018
_[21] 서적 Foundations of Modern Networking: SDN, NFV, QoE, IoT, and Cloud Addison-Wesley Professional 2015
_[22] 웹사이트 https://www.cisco.co[...]