Routing algorithm of minimizing maximum link congestion on grid networks
2015
As regular topology networks, grid networks are widely adopted in network deployment. Link congestion and routing path length are two critical factors that affect the delay and throughput of a network. In this paper, we study the routing problem in grid networks concerning these two factors. The main objective of our routing algorithms is to minimize the maximum link congestion. The shortest path minimum maximum (SPMM) link congestion and non-shortest path minimum maximum (NSPMM) link congestion routing problems are studied. The two problems are first formulated as integer optimization problems. Then, corresponding routing algorithms (SPMM and NSPMM routing algorithms) are proposed. For SPMM routing algorithm, the path length is optimal, while for NSPMM routing algorithm, the path is limited in a submesh. Thus, the path length can be bounded. At last, we compare the proposed routing algorithms under different scenarios with other popular routing algorithms (RowColumn, ZigZag, Greedy, Random routing algorithms). The performances are evaluated through different metrics including link congestion, path length, path congestion, path congestion to path length ratio, delay and throughput.
Keywords:
- Computer network
- Link-state routing protocol
- Path vector protocol
- Dynamic Source Routing
- Wireless Routing Protocol
- Static routing
- Distributed computing
- Algorithm
- K shortest path routing
- Equal-cost multi-path routing
- Computer science
- Destination-Sequenced Distance Vector routing
- Hierarchical routing
- Mathematical optimization
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
42
References
2
Citations
NaN
KQI