An application-level routing method with transit cost reduction based on a distributed heuristic algorithm

Kazuhito Matsuda, Go Hasegawa, Masayuki Murata

Research output: Contribution to journalArticlepeer-review


Application-level routing that chooses an end-to-end traffic route that relays other end hosts can improve user-perceived performance metrics such as end-to-end latency and available bandwidth. However, selfish route selection performed by each end user can lead to a decrease in path performance due to overload by route overlaps, as well as an increase in the inter-ISP transit cost as a result of utilizing more transit links compared with native IP routing. In this paper, we first strictly define an optimization problem for selecting application-level traffic routes with the aim of maximizing end-to-end network performance under a transit cost constraint. We then propose an application-level traffic routing method based on distributed simulated annealing to obtain good solutions to the problem. We evaluate the performance of the proposed method by assuming that PlanetLab nodes utilize application-level traffic routing. We show that the proposed routing method can result in considerable improvement of network performance without increasing transit cost. In particular, when using end-to-end latency as a routing metric, the number of overloaded end-to-end paths can be reduced by about 65%, as compared with that when using non-coordinated methods. We also demonstrate that the proposed method can react to dynamic changes in traffic demand and select appropriate routes.

Original languageEnglish
Pages (from-to)1481-1491
Number of pages11
JournalIEICE Transactions on Communications
Issue number6
Publication statusPublished - 2013 Jun


  • Inter-ISP transit cost
  • Overlay network
  • Overlay routing
  • PlanetLab
  • Simulated annealing


Dive into the research topics of 'An application-level routing method with transit cost reduction based on a distributed heuristic algorithm'. Together they form a unique fingerprint.

Cite this