1. A method of operating a logical network over a network virtualization infrastructure that comprises a plurality of host machines, the method comprising: defining a logical routing element (LRE) for routing data packets between different segments of the logical network, wherein each host machine operates a set of virtual machines (VMs) and a local instance of the LRE as a managed physical routing element (MPRE) for routing packets from the set of VMs locally at the host machine, the LRE comprising a plurality of logical interfaces (LIFs), each LIF for interfacing with a different segment of the logical network, wherein a particular LIF is addressable by a plurality of different LIF addresses; assigning each LIF address of the particular LIF to a different host machine in the plurality of host machines; and advertising the plurality of LIF addresses of the particular LIF as a plurality of next-hops to an external router.