MARS: A Multi-Attribute Routing and Scheduling Algorithm for DTN Interplanetary Networks

Sara El Alaoui, Byrav Ramamurthy
October 2020
Cite DOI URL

Abstract

The Interplanetary Network (IPN) or the Interplanetary Internet is a network composed of interconnected space objects, which are in turn connected to mission control stations on the surface of Earth. The IPN is our only portal to the deep space, and yet it has been relatively sparse, until recently. With the ongoing and the planned missions to the outer space, the Delay Tolerant Networking (DTN) based network infrastructure will require more scalable routing and scheduling algorithms. In this paper, we propose the first Mixed Integer Linear Programming (MILP) model for message routing and scheduling in the IPN using Multi-Attribute Decision Making (MADM) principles. Based on this model, we propose a novel MADM-based algorithm called Multi-Attribute Routing and Scheduling (MARS) algorithm. This algorithm uses a sliding window of size n to schedule the first n messages in the buffer based on multiple attributes. After finding the optimal schedule for these messages (in terms of delivery rate), they are routed using our proposed Dijkstra-based routing algorithm. We use an existing MADM technique, PROMETHEE II, and consider the four main attributes of a message: size, priority, time to live (TTL), and time in buffer (TiB). Finally, we run multiple simulation experiments in order to test the performance of the proposed MARS and show that MADM coupled with scheduling and routing in IPN delivers at least three times more messages than a previously proposed technique, the Contact Graph Routing (CGR), while significantly reducing the average end-to-end delay and overhead.

Type
Journal article
Publication
IEEE/ACM Transactions on Networking
Internet Telecommunication Network Routing Integer Programming Linear Programming Graph Theory Routing End-to-End Delay Satellite Communication Scheduling Delay Tolerant Networking Delays Interplanetary Internet IPN Outer Space Space Missions Mixed Integer Linear Programming Routing Protocols Aerospace Control Aerospace Electronics CGR Contact Graph Routing Decision Making Deep Space Delay Tolerant Networking Based Network Infrastructure Delay Tolerant Networks Dijkstra-Based Routing Algorithm Dtn Interplanetary Networks Interconnected Space Objects Internplanetary Internet Joint Scheduling and Routing MADM MADM Technique Mars Message Routing MILP Model Mission Control Stations Mixed Integer Linear Programming Model Multi-Attribute Routing and Scheduling Multiattribute Decision Making Principles Multiattribute Routing and Scheduling Algorithm Multiple Attribute Decision Making Optimal Schedule Planned Missions PROMETHEE II Scalable Routing Telecommunication Scheduling TiB Time in Buffer Time to Live TTL
Byrav Ramamurthy
Byrav Ramamurthy
Professor & PI

My research areas include optical and wireless networks, peer-to-peer networks for multimedia streaming, network security and telecommunications. My research work is supported by the U.S. National Science Foundation, U.S. Department of Energy, U.S. Department of Agriculture, NASA, AT&T Corporation, Agilent Tech., Ciena, HP and OPNET Inc.