In the power distribution domain, the increasing penetration of Distributed Generation (DG) requires reliable, real-time and cost effective communication in order to manage the grid safely and securely. To achieve this goal, a heterogeneous network (mixing the public Internet and private networks) is a promising solution due to its cost effectiveness. However, the current Internet infrastructure does not support reliable real time communication. To cope with these challenges, we propose QoS routing based on a novel overlay network protocol. Moreover, the protocol provides fault-tolerant communication for critical applications by applying multi-path routing over disjoint paths. Simulation results demonstrates that the proposed overlay network and algorithms perform well in obtaining QoS-aware overlay routing service in scalable manner as well as fault-tolerance for the critical application. © 2014 IEEE.