The prominence of wireless, mobile devices on the Internet today has motivated numerous protocols and architectures, such as the MobilityFirst Future Internet Architecture project. In this work, we present a robust, local-scale, storage-aware routing approach, called GSTAR, for use in Mobility-First networks. GSTAR unifies techniques from MANET and DTN routing protocols. This unification with in-network storage enables it to overcome mobility-related challenges such as link quality variation, node disconnection, and network partitioning. Through NS3-based simulation, we show that GSTAR outperforms traditional link-state protocols for both wireless and hybrid wired-wireless network environments.