A method enabling symmetric routing between a first host within a first AS and a second host within a second AS is disclosed. The method includes detecting that a first routing message was received at an edge router of the first AS from an edge router of the second AS. The first message identifies the second host as a source and the first host as a destination of a forward route. The method further includes determining that the first message further comprises an indication to implement symmetric routing between the first and second hosts and generating a second routing message for propagating to router(s) within the first AS. The second message identifies the first host as a source and the second host as a destination of a return route, and indicates that data is to be sent via the edge router of the first AS that received the first message.