A Traffic-Adaptive Dynamic Routing Method and Its Performance Evaluation

Kimihiro YAMAMOTO  Shozo NAITO  

IEICE TRANSACTIONS on Information and Systems   Vol.E82-D   No.4   pp.870-878
Publication Date: 1999/04/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Internet Technology and Its Applications)
routing,  traffic control,  game theory,  distributed control,  emergence,  

Full Text: PDF(391.7KB)>>
Buy this Article

This paper proposes a traffic-adaptive dynamic routing method, which we have named RAG, for connectionless packet networks. Conventional traffic control methods discard the packets which cause congestion. Furthermore, conventional routing methods propagate control messages all over the network for gathering global topology information, and this causes more congestion. In contrast, RAG estimates traffic conditions all over a network without any communication between nodes and makes the best use of free links so that packets make detours to avoid congestive sites. RAG adopts distributed control based on game theory (non-communication, non-zero-sum, two-person). With RAG, nodes play a packet-forwarding game without any communication with each other, and each node controls ordering and routing of the forwarding packets based on the node's individual payoff table which is dynamically reconstructed by observation of surrounding nodes. Nodes cooperate with each other, except for punishment for disloyalty. Repetition of these local operations in nodes aims at the emergence of the gradual network-global traffic balancing. The results of experiments in comparison with the conventional shortest path first (SPF) routing method show that the throughput is about 1.58 times higher with the new method.