"Efficient Algorithm for Packet Routing Problems Using Transmission History Information"
Akinori Yoshida, Masaya Kaneko, Toshichika Aoki, Takayuki Kimura and Tohru Ikeguchi

The simplest shortest path problem in a network whose weights of edges are static can be solved easily using the well-known Dijkstra algorithm. However, in practical cases such as packet communication networks, the weights of edges are fluctuated by flowing packets or queuing packets at nodes (for example, routers). Obtaining the shortest paths of the packets from their sources to destinations in communication networks is called a packet routing problem. In the packet routing problems, both the optimum routes of packets at the current time are that at the next time cannot be guaranteed because the distributions of packets changes continually with time. We herein report the performance of routing algorithms using transmission history information for packet routing problems. Numerical experiments demonstrate that our method improves the average arrival rate of packets by approximately 50% over conventional routing methods for different topologies of communication networks.