1. An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a first virtual environment with a live virtual appliance having a plurality of virtual objects; and an appliance migration mechanism residing in the memory and executed by the at least one processor, wherein the appliance migration mechanism optimizes migration of the live virtual appliance from the first virtual environment to a second virtual environment to minimize temporary connections during the migration by analyzing a cost of connections for each of the virtual objects to produce from the cost of connections for each of the virtual objects an order of migration for the plurality of virtual objects.