Systems and methods for establishing routing information between software containers or other virtualized environments within a network, and providing inter-container routing between the software services operating on the network, are disclosed herein. The system utilizes an existing routing protocol such as Open Shortest Path First (OSPF) and establishes an overlay network that provides end-to-end connectivity between services of a customer operating in an Infrastructure as a Service (IaaS) network, while maintaining isolation from the traffic of other customers of the IaaS network. The system uses OSPF to learn aspects of the routes between containers in the network, and further builds a customer-specific overlay network based on IP-to-IP encapsulation of the OSPF messages.