The technology disclosed herein enables multi-path routing in virtual edge systems of a virtual network environment. In a particular embodiment, a method provides establishing a connection for a communication with a client outside of the virtual network environment through a first virtual edge system of a plurality of virtual edge systems. The method further provides generating state information about the connection that indicates properties of the connection with respect to the first virtual edge system and updating a state information base of the first virtual edge system with the state information. Also, the method provides transferring the state information to one or more other virtual edge systems of the plurality of virtual edge systems and updating respective state information bases of the one or more other virtual edge systems with the state information.