A novel interplanetary DTN routing protocol (IDRP) is designed to provide a general networking solution over interplanetary network scenarios. IDRP enables DTN nodes to estimate the recovery time to its neighbor nodes using the historical connection information. When two DTN nodes in the same region contact each other, they exchange their estimations to decide whether to use each other as a relay. For storage resource is constraint in deep space nodes, IDRP also takes storage consumption into consideration. Simulations based on NS2 were conducted in a Mars-to- Earth scenario. A modified epidemic routing strategy and an only-gateway-selected routing strategy are used as contrast. The simulation results show that IDRP achieves 14% higher delivery ratio and 50% less average transmission delay than the other two strategies, as well as better storage utilization.