In this paper, we study the problem of co-migrating a set of service replicas residing on one or more redundant virtualservers in clouds in order to satisfy a sequence of mobile batch-request demands in a cost effective way. With such a migration, we cannot only reduce the service access latency for end users but also minimize the network costs for service providers. The co-migrationcan be achieved at the cost of bulk-data transfer and increases the overall monetary costs for the service providers. To gain the benefitsof service migration while minimizing the overall costs, we propose a co-migration algorithm Migk for multiple servers, each hosting aservice replicas. Migk is a randomized algorithm with a competitive cost of O ( γ log nmin { 1κ,µλ + µ } ) to migrate κ services in a static n-nodenetwork where γ is the maximal ratio of the migration costs between any pair of neighbor nodes in the network, and where λ and µrepresent the maximum wired transmission cost and the wireless link cost respectively. For comparison, we also study this problem inits static off-line form by proposing a parallel dynamic programming (hereafter DP) based algorithm that integrates the branch&boundstrategy with sampling techniques in order to approximate the optimal DP results.