The ICT industry has come under criticism as being one of the major energy consumers to exacerbate high global carbon emissions. Meanwhile, using renewable energy to power ICT infrastructure is becoming an attractive solution and is gaining its momentum due to the recent breakthroughs of converting solar and wind energies as power sources at competitive costs. Although significant amounts of fossil fuel based-energy can be saved by allowing network devices (e.g., routers and line-cards) to be set to sleep, this optimization approach comes at a price of degrading routing performance, i.e., the quality of service. This paper addresses the problem of minimizing fossil fuel consumption in large Internet Service Provider (ISP) networks, by utilizing a novel gradient-based routing protocol, which favors forwarding packets along routers powered by the highest quantity of renewable energies. Besides favoring renewable energy, the proposed routing protocol can support putting routers to sleep in order to optimize energy consumption while ensuring a minimum degradation in routing performance. Through our evaluation utilizing real meteorological data, our proposed solution has demonstrated a massive reduction of fossil fuel usage by the network (> 70%) while maintaining the routing performance to a similar level when no energy optimization is applied.