2.3.3 최단 경로 탐색 알고리즘과 링크 상태(Link State) 관리

버전 알림: 본 문서는 Zenoh 1.0.0 (및 1.0.0-rc 분기) 코어 아키텍처 규격을 기준으로 작성되었다.

인터넷(Internet) 규모의 방대한 디바이스들이 서로 얽혀 P2P 메쉬(Mesh)와 트리(Tree) 토폴로지를 혼합 구축할 때, 데이터 패킷이 목적지까지 도달하는 수많은 갈래 길 중 ’가장 빠르고 부하가 적은 최적의 경로’를 산출해 내는 능력은 네트워크 미들웨어의 존폐를 가르는 핵심 엔진이다. 중앙의 지휘자(Name Server)가 존재하지 않는 분산 환경에서, 각 라우터(Router)와 피어(Peer) 노드들은 오직 지엽적인 주변의 정보 편린들만을 조합하여 전체 네트워크의 광역 지도를 완성해 내야만 한다.

본 절에서는 과거 OSPF(Open Shortest Path First) 방식의 IP 통신망 라우팅 알고리즘 철학을 데이터 중심(Data-Centric) 네이밍 아키텍처 위로 끌어올린 Zenoh(제노)의 고차원 링크 상태(Link State) 관리 기법과 방향성 최단 경로 탐색(Shortest Path Routing) 루틴의 은밀한 작동 원리를 해부한다.

1. 링크 상태(Link State)의 분산 추적과 코스트(Cost) 메트릭(Metric)의 산정

로컬에 위치한 로봇 1호기(Peer A)가 저 멀리 떨어진 클라우드 관제 센터(Router C)와 결속하기 위해, 그 사이에 매개체로 버티고 선 포그(Fog) 라우터 B1, B2, B3 중 어느 라우터를 징검다리 경로(Hop)로 택할 것인가를 결정하려면 물리적 링크 상태(Link State)의 실시간 품질 감사가 선행되어야 한다.

Zenoh 피어 아키텍트는 세션이 한 번 수립되었다고 그 터널의 영원성을 맹신하지 않는다. 이들은 백그라운드 스레드에서 끊임없이 하트비트(Heartbeat Keep-Alive)와 지터(Jitter) 패킷을 서로 주고받으며 현재 소켓의 지연 시간(Latency), 패킷 손실률(Packet Loss), 그리고 가용 대역폭 임계치를 동적으로 계측한다. 이 품질 데이터는 해당 노드 간 커넥션이 지닌 고유의 ‘경로 비용(Routing Cost Metric)’ 점수로 즉각 환산된다. 만일 B1 라우터 쪽의 와이파이(Wi-Fi) 전파 간섭이 심해 패킷 지연이 치솟는다면, A와 B1 사이의 링크 코스트 점수는 즉시 수직으로 폭등하여 라우팅 선호도에서 후순위로 추락하게 된다.

이러한 국소적인 1:1 링크 품질 평가 팩트들은 자신의 포워딩 인포메이션 베이스(FIB, Forwarding Information Base) 메모리에 새겨지는 데서 끝나지 않고, 네트워크 전체에 서서히 확산(Flooding or Gossiping)되며 모든 글로벌 노드들이 서로 동일하게 공유하는 하나의 거대한 ’지형 비용 지도(Global Cost Map)’로 동기화 수렴(Convergence)되는 기염을 토한다.

2. 네임스페이스 트레이서 기반의 다익스트라(Dijkstra) 유사 회피 경로 탐색 알고리즘

전역 라우터들이 링크 비용 지도를 머릿속에 완벽히 복제하고 나면, 이제 쏟아지는 트래픽 토픽 이름(예: /factory/agv/sensor)에 맞춰 어느 포트로 패킷을 밀어내야 할지를 결정하는 알고리즘 엔진이 점화된다. 기존 IP 통신망에서 OSPF나 IS-IS가 사용하던 다익스트라 최단 경로 탐색 알고리즘(Dijkstra’s Shortest Path First Algorithm) 패러다임이 여기서 데이터 중심 라우팅에 맞게 변조되어 구동된다.

특정 “센서 온도 데이터를 구독하겠다“는 서브스크립션 프레임(Subscription Declaration)이 목적지 클라이언트에서 역방향으로 출발해 네트워크 교차로 라우터들을 뚫고 다가올 때마다, 이 엔진은 해당 경로를 지나온 누적 코스트(Accumulated Link Cost)를 계산하여 기록해둔다. 만일 여러 갈래의 우회 경로를 타고 동일한 구독 선언서가 중복해서 도착한다면, 라우터 내부 연산 산술기(ALU)는 누적 스코어가 가장 낮고 빠른 최적의 메인 라우팅 포트(Primary Port) 단 하나만을 정방향 포워딩(Forwarding) 출구로 우대(Favoring) 마킹(Marking)해버린다.

데이터 생산자(Publisher)가 트래픽을 토해내기 시작할 때 데이터 패킷은 계산된 코스트가 가장 낮은 1번 메인 경로 터널로 맹렬하게 빨려 들어가며, 0.1ms의 하드 리얼타임(Hard Real-time) 목표를 달성한다. 이 지능형 거리 적응 엔진은 코더가 경로를 지정해주는 원시적 노가다 런북을 파괴하는 분산망의 꽃이다.

3. 백업 우회로(Fallback Routing) 즉시 개통을 통한 타임아웃(Timeout) 절연

최적 경로 알고리즘의 진정한 방패막이는 시스템 평시가 아닌, 1번 메인 파이프의 갑작스러운 물리적 절단이나 스위치 셧다운 같은 극단적 패닉 상황에서 그 진가를 뿜어낸다.

전술 트래픽이 평화롭게 B1 라우터 징검다리를 타고 고속 회전하던 도중, B1 라우터의 전원이 날아가는 크래시(Crash) 팩트가 감지되는 그 찰나(Session Drop Event), 일반적인 L3 인터넷 장비는 멍청하게 B1이 다시 반응할 때까지 패킷을 재전송하며 패킷 드롭(Packet Drop) 타임아웃의 늪에 빠져든다. 하지만 Zenoh 아키텍처의 FIB에는 최단 경로 1위 B1에 가려져 있던 2순위, 3순위의 우회 대기망 경로 코스트(Fallback Alternative Ports)가 이미 다익스트라 트리 상에 계산되어 잠복 중인 상태이다.

B1 통신 소켓의 하트비트가 끊어짐과 동시에, 라우팅 엔진은 B1으로 가던 포워딩 스위치 기어를 즉각 차단(Block)하고, 지연 시간은 B1보다 5 밀리초 정도 더 느리지만 단단히 온존해 있던 2위 코스트 B2 라우터 대기 터널로 엔진 트래픽 밸브를 자동 스위칭(Auto Metamorphosis Rerouting) 해버린다. 상위 단의 어플리케이션은 라우터가 사망했다는 오류 예외(Exception) 코드 하나 받지 못하는 깊디깊은 장애 추상화(Failure Abstraction) 아래 온전하게 보호받는다. 최단 경로 계산이 단일선택으로 끝나는 것이 아니라 무한대 이중화 예비 다중경로(Multipath Redundancy)의 생명줄 연산으로 맞물려 돌아가는 이 공학, 이것이 바로 미들웨어 기술의 마스터피스다.