An optimal, strategy-proof scheme for multi-path traffic assignment in non-cooperative networks

Multi-path routing has long been studied as an important routing strategy in networks. Many multi-path routing protocols schedule traffic among multiple paths in order to distribute traffic load. However, existing multi-path routing protocols with traffic assignment require that all nodes in the network follow the protocol, which may not always be a valid assumption when the network consists of selfish nodes. In this paper, we propose an optimal, strategy-proof scheme for multi-path traffic assignment (OSMA) in non-cooperative networks. When OSMA is used, behaving honestly is to the best interest of each selfish node regardless of any other nodes?? behavior. Furthermore, our scheme is guaranteed to compute the lowest cost traffic assignment with the existence of these selfish nodes. Our evaluations verify that our scheme is optimal and strategy-proof, and demonstrate that the scheme has very low communication and computation overhead.