Daniel H. Wagner Associates, Inc. developed new routing algorithms for satellite
communication networks.
Hundreds of satellites will soon be orbiting the earth forming
new global communication networks. Routing messages through these
networks via intersatellite links requires an efficient routing
to achieve high data throughput and low latency. The topologies
(connectivity) of these communication networks will change in
time due to the motion of the satellites and due to failures
in both the satellites and the links. These networks will require
dynamic message routing algorithms that determine routing based
on the network topology and the network load.
As part of this effort, Wagner Associates developed a simulation
using MIL3's
OPNET software to test the performance of
the routing algorithms on a model of the former Iridium constellation.
The OPNET simulation was used to determine how much traffic could
successfully be routed for each of the algorithms.
Wagner Associates performed various studies using the OPNET simulation
to compare four different routing algorithms: a Bellman-Ford
algorithm, a greedy algorithm as described in Motorola's patents
5,430,729
and 5,596,722,
and our improvement to each of these. We evaluated each method
of routing by running simulations and increasing the traffic
load to the point of network failure. Preliminary results showing
the effectiveness of our routing algorithms are given below.
These results show that our algorithms produce substantially
better routing tables than either the Bellman-Ford or our implementation
of the simple greedy algorithm described in two of Motorola's
patents.
OPNET Simulation Results
| Algorithm |
Description |
Traffic Factor at Failure
|
Improvement Over Next Best Algorithm
|
| BF |
A Bellman-Ford routing table. |
2.1
|
- |
| Greedy |
A greedy routing table from Motorola's patents. |
2.85
|
36% better than BF |
| WGreedy |
Our improvement on the greedy routing table. |
3.38
|
19% better than Greedy |
| WBF |
Our improvement on the Bellman-Ford routing. |
3.47
|
3% better than WGreedy |
For information, contact
Dr.
David P. Kierstead.
