Interplanetary Ad hoc Networks (IPANs) aim to establish a communication infrastructure in deep space, connecting planets, natural and artificial satellites, and mission elements. The communication links in IPANs have low bandwidth, high error rate, and high latency. The connectivity of the network is intermittent, affected by movement of planets out of range of each other and occlusion of a planet by another. Also, the satellites and mission stations are power constrained, which makes traditional routing protocols extremely expensive in terms of time and energy consumed. However, the determinism in the orbital patterns of planets and satellites enables predictive route-building and repair. The main contributions of this paper are (i) identification of the issues involved in routing over IPANs, (ii) graph-theoretic modeling of the interplanetary backbone network, and (iii) proposal of a routing protocol, MARVIN, for interplanetary backbone networks. The proposed routing protocol, MARVIN, for Movement-Aware Routing oVer Interplanetary Networks, makes novel use of the determinism in planetary movements. MARVIN uses the ephemeris table data for planets to precisely determine the location of planets at any instant of time, and reconfigures routes a priori, in anticipation of link-breaks. This eliminates the need for expensive topology discovery and distribution of topology information. We have simulated MARVIN over the IPAN consisting of the nine planets and the moon. It can build the routing table for any period of time given the ephemeris data tables. The graph-theoretic approach also helps in defining the stability of links of the IPAN, and can be used to choose relatively long-lasting links to reduce the number of route reconfigurations. MARVIN is studied for a variety of routing metrics such as shortest path, minimum power, and minimum end-to-end delay, and sample routing tables have been presented. © 2004 IEEE.