A Self-optimizing Routing Algorithm using Local Information in a 3-dimensional Virtual Grid Network with Theoretical and Practical Analysis

Abstract

In this paper, we present a self-optimizing routing algorithm using only local information, in a three-dimensional (3D) virtual grid network. A virtual grid network is a well-known network model for its ease of designing algorithms and saving energy consumption. We consider a 3D virtual grid network which is obtained by virtually dividing a network into a set of unit cubes called cells. One specific node named a router is decided at each cell, and each router is connected with the routers at adjacent cells. This implies that each router can communicate with 6 routers.

We consider the maintenance of an inter-cell communication path from a source node to a destination node and propose a distributed self-optimizing routing algorithm which transforms an arbitrary given path to an optimal (shortest) one from the source node to the destination node. Our algorithm is executed at each router and uses only local information (6 hops: 3 hops each back and forward
along the given path). Our algorithm can work in asynchronous networks without any global coordination among routers.

We present that our algorithm transform any arbitrary path to a shortest path in O(|P|) synchronous rounds, where |P| is the length of the initial path, when it works in synchronous networks. Moreover, our experiments show that our algorithm converges in about |P|/2 synchronous rounds and the ratio becomes lower as |P| becomes larger.