Global adaptive routing is a critical component of high-radix networks in large-scale systems and is necessary to fully exploit the benefits of the path diversity of high-radix networks. However, global adaptive routing involves making a routing decision between minimal and non-minimal paths based on "approximate'' information, often based on local information. As a result, while simulations might provide high performance for a given configuration, it is not necessarily robust as network parameter changes or network size scales. Different heuristic-based adaptive routing algorithms have been proposed and in this work, we identify the limitations of previously proposed adaptive routing algorithms and their inability to properly route packets across different networks. To solve those issues, we propose to use an adaptive routing algorithm that leverages local channel utilization information based on reinforcement learning, namely $k$-armed bandit. We also propose to use packet queuing latency as feedback so that it is aware of the global condition of the network. We show that using either local or global information has its own limitations and by combining both local and global information, high routing performance can be achieved across all traffic patterns in various high-radix networks.
전역 적응형 라우팅은 대규모 시스템에서 높은 기수를 갖는 토폴로지의 중요한 구성요소로서 높은 기수를 갖는 토폴로지에서 경로 다양성의 장점을 충분히 활용하는 데 필요하다. 그러나 전역 적응형 라우팅은 때때로 지역적인 정보에 기반하기 때문에 "대략적인" 정보에만 기초하여 최단 경로와 비최단 경로 사이에 라우팅 결정을 내리는 것을 포함한다. 결과적으로, 시뮬레이션이 특정 구성에 대해서는 높은 라우팅 성능을 제공할 수 있지만, 네트워크 매개변수의 변경이나 네트워크 크기가 확장될 때 반드시 높은 라우팅 성능을 보장하지는 않는다. 이와 관련하여 경험적 접근법에 기반한 몇 가지 적응형 라우팅 알고리즘들이 제안되어 왔다. 본 연구에서는 이전에 제안된 적응형 라우팅 알고리즘들이 갖는 한계와 다양한 네트워크에서 패킷들의 최선의 경로 설정을 할 수 없는 문제를 분석한다. 그리고 이러한 한계들을 극복하기 위해 지역적 채널 이용 정보 및 패킷 지연 시간을 활용하여 네트워크의 전역 상태 정보를 추론하는 적응형 라우팅 알고리즘을 제안한다. 특히, $k$-armed bandit을 기반한 강화학습을 활용하여 지역 채널을 과도하게 사용하지 않는 선에서 충분히 활용하고, 라우팅 결정에 패킷 지연 시간 정보를 반영할 것을 제안한다. 본 논문에서는 지역 정보 또는 전역 정보만을 이용하는 것이 갖는 한계를 보이며, 지역 정보와 전역 정보를 결합함으로써 높은 기수를 갖는 다양한 네트워크와 트래픽 패턴에도 높은 라우팅 성능을 달성할 수 있음을 보인다.
