In one example, a server executes a virtual router configured to receive an inner packet output by a virtual machine associated with a virtual network. The virtual router is further configured to offload, to a physical network interface card of the server that executes the virtual router, segmentation of the inner packet into a plurality of outbound tunnel packets each having a tunnel header for output by the physical network interface card to a physical network underlying the virtual network.