CS 전공자라면 누구나 한 번쯤 밤새워 구현해봤을 알고리즘, 바로 Dijkstra(다익스트라) 입니다. 1959년에 발표된 이 알고리즘은 네트워크 라우팅의 성경과도 같죠. OSPF나 IS-IS 같은 링크 상태(Link-State) 라우팅 프로토콜의 심장이기도 합니다.

그런데 최근 “Dijkstra보다 이론적으로 더 빠른 알고리즘이 발견됐다”는 소식이 들려왔습니다. 학계는 물론이고 Tech 뉴스들이 꽤 시끄러웠죠. 하지만 15년 차 엔지니어로서, 그리고 대규모 트래픽을 다뤄본 입장에서 제 첫 반응은 이랬습니다.

“그래서요? 그게 Production 환경에서 진짜 의미가 있나요?”

오늘은 최근 화제가 된 Systems Approach의 아티클과 이에 대한 Hacker News의 반응을 바탕으로, 왜 이론적 돌파구가 실무 엔지니어링에서는 계륵이 될 수 있는지 딥다이브 해보겠습니다.

1. 이론적 돌파구: 정렬(Sorting)의 장벽을 깨다

우선, 새로 나온 알고리즘이 폄하될 수준은 절대 아닙니다. ACM STOC 같은 Top-tier 컨퍼런스에서 검증된 내용이고, 이론적으로 대단한 성취인 건 맞습니다.

기존 Dijkstra 알고리즘의 시간 복잡도는 $O(m + n \log n)$입니다(피보나치 힙 사용 시). 여기서 $\log n$이 발생하는 근본적인 이유는 ‘가장 가까운 노드’를 찾기 위해 우선순위 큐(Priority Queue)를 정렬하고 추출해야 하기 때문입니다. 즉, 정렬(Sorting) 비용이 병목이었죠.

새로운 알고리즘은 이 정렬의 한계를 우회하여 $O(m \log^{2/3} n)$이라는 복잡도를 달성했다고 주장합니다. $n$이 충분히 크다면 수학적으로 Dijkstra보다 무조건 빠릅니다. 훌륭하죠. 하지만 우리는 수학자가 아니라 엔지니어잖아요? 여기서부터 현실적인 질문들을 던져봐야 합니다.

2. 라우팅 테이블의 $n$은 생각보다 작다

알고리즘의 효율성을 논할 때 가장 중요한 건 입력값 $n$(노드 수)의 크기입니다. Big-O 표기법은 $n$이 무한대로 갈 때의 거동을 설명하지만, 현실의 시스템은 유한합니다.

실제 인터넷 백본망에서 OSPF나 IS-IS가 다루는 라우터의 개수는 몇 개나 될까요? 수억 개? 아닙니다.

• OSPF/IS-IS: 하나의 라우팅 도메인(Area) 내에 있는 라우터 수는 보통 수백 대, 많아봐야 수천 대 수준입니다.
• BGP: 전 세계 인터넷 라우팅 테이블은 거대하지만, 이건 Dijkstra가 아니라 경로 벡터(Path Vector) 알고리즘을 씁니다.

원문 저자도 지적하듯, $n$이 수천 대 수준인 상황에서 $O(n \log n)$과 $O(m \log^{2/3} n)$의 차이는 미미합니다. 오히려 상수항(Constant factor)이나 구현의 복잡도 때문에 $n$이 작을 땐 새 알고리즘이 더 느릴 수도 있습니다. 마치 데이터가 10개뿐인데 퀵 정렬(Quick Sort)을 돌리는 것과 비슷한 낭비일 수 있다는 얘기죠.

3. 진짜 병목(Bottleneck)은 계산이 아니다

네트워크 엔지니어들이 라우팅 프로토콜에서 가장 신경 쓰는 지표는 Convergence Time(수렴 시간) 입니다. 장애가 발생했을 때 얼마나 빨리 우회 경로를 찾아내느냐죠.

하지만 여기서 SPF(Shortest Path First) 계산 시간은 전체 파이의 아주 작은 조각에 불과합니다. 실제 타임라인을 뜯어보면 이렇습니다:

1. Failure Detection: 링크가 죽은 걸 감지함 (수십 ms ~ 수 초)
2. Propagation: 장애 정보를 이웃 라우터에 전파 (물리적 지연)
3. Scheduling: 라우터 CPU가 정보를 받아 처리 대기
4. SPF Calculation: 경로 계산 (여기서 Dijkstra 사용)
5. FIB Update: 포워딩 테이블 업데이트 및 라인 카드로 배포

과거에는 SPF 계산이 꽤 무거웠지만, 2000년대 초반 이후 CPU 성능 향상으로 이 단계는 이미 밀리세컨드(ms) 단위로 끝납니다. 진짜 병목은 1번(장애 감지) 과 5번(하드웨어 업데이트) 에 있습니다.

그래서 업계에서는 BFD(Bidirectional Forwarding Detection) 같은 초고속 헬로 패킷 프로토콜을 도입해서 감지 속도를 올리는 데 집중했지, Dijkstra를 뜯어고치는 데 시간을 쓰진 않았습니다. 이미 충분히 빠르니까요.

4. Hacker News의 날카로운 지적들

이 주제에 대해 Hacker News의 고인물들도 흥미로운 분석을 내놓았습니다. 특히 그래프의 밀도(Density)에 대한 지적이 인상 깊었습니다.

한 유저의 코멘트를 인용하자면:

“새 알고리즘은 엣지 수($m$)에 대한 곱셈 인자가 있어서, 매우 희소한(Sparse) 그래프에서만 효율적이다. 만약 평균 차수(Degree)가 3.5를 넘어가면 오히려 Dijkstra보다 느려질 수 있다.”

실제 네트워크 토폴로지는 단순한 트리 구조가 아닙니다. 리던던시(Redundancy)를 위해 메시(Mesh) 형태로 연결된 경우가 많죠. 즉, $m$이 생각보다 큽니다. 이론적으로 더 빠른 알고리즘이 실제 토폴로지에서는 더 느려질 수 있다는, 전형적인 “Theory vs Practice”의 사례입니다.

5. KISS 원칙: 유지보수 가능한가?

Dijkstra 알고리즘의 가장 큰 장점 중 하나는 단순함 입니다. Dijkstra 본인이 말했듯, “종이와 연필 없이 설계했기 때문에 복잡함을 피할 수 있었다”는 명언이 있죠.

반면, 새로운 알고리즘(Hybrid Bellman-Ford/Dijkstra 접근법 등)은 구현 난이도가 훨씬 높습니다. 여러분이 CTO라면, 성능 차이는 거의 없는데 코드는 10배 복잡하고 디버깅도 힘든 새로운 라이브러리를 도입하시겠습니까?

“엔지니어에게 OSPF 스펙을 던져주는 게, 하이브리드 알고리즘 논문을 읽으라고 하는 것보다 훨씬 낫다”는 원문 저자의 말에 100% 공감합니다. 인프라 레벨의 코드는 화려함보다 안정성 과 가독성 이 생명입니다.

마치며: 도구의 목적을 잊지 말자

물론 이 새로운 알고리즘이 무가치하다는 뜻은 아닙니다. 수억 개의 노드를 다루는 초대형 지도 서비스나, 특정 과학적 시뮬레이션에서는 게임 체인저가 될 수도 있겠죠.

하지만 적어도 네트워크 라우팅 분야에서 Dijkstra가 은퇴할 일은 당분간 없어 보입니다. 엔지니어로서 우리가 가져야 할 태도는 신기술에 환호하는 것만큼이나, “이게 우리 문제의 진짜 병목을 해결해 주는가?” 를 냉정하게 따져보는 비판적 사고입니다.

가끔은 1959년에 나온 투박한 알고리즘이 2026년의 최신 논문보다 더 강력할 때가 있습니다. 그게 엔지니어링의 묘미 아닐까요?