An efficient algorithm for reconfiguration of large-scale point-to-point satellite computer networks with maximum connectivity

The authors present a region-partitioning approach for networks that uses lasers as communication links. Since the network is highly mobile and the communication links are constrained to the line of sight between satellites, the network must be reconfigured dynamically by retargeting the transceivers among satellites. The objective of the reconfiguration is to maximize high survivability and performance by optimizing the network connectivity. The approach to this reconfiguration is a divide-and-conquer method. The network is partitioned into small subnetworks by dividing the satellite orbiting space into small regions. Then links are assigned to maximize the node connectivity of the subnetwork. Finally, subnetworks are connected together to form a complete network. The authors show that this approach provides maximum connectivity for large-scale networks. The algorithm is very efficient and has O(n log n) time complexity. The algorithm is replicated to each satellite and is run simultaneously by all satellites on a periodic basis