1. A computer-implemented method for cloud-based backup, the method comprising: receiving, at a cloud gateway (GW) device which manages backups and restores to and from cloud storage servers of two or more cloud storage providers, a first request for incremental backup from a client device over a local area network (LAN), wherein the first request includes a first file representing a difference between the incremental backup in view of a prior backup; in response to the first request, identifying by a cloud backup manager running within the cloud GW, a first base backup that has been previously backed up to a cloud storage server over a wide area network (WAN), including constructing a first descriptor having a plurality of tags to specify the first base backup, the plurality of tags including a client tag identifying the client, a file system tag identifying a file system associated with the first base backup, and a timestamp tag indicating time at which the first base backup was made; transmitting a second request to the cloud storage server over the WAN requesting the cloud storage server to copy the first base backup into a second base backup, wherein the second request includes a first backup identifier (ID) identifying the first base backup and wherein the second request is transmitted by at least transmitting a first command to the cloud storage server to select a root object of the first base backup, the first command including the first descriptor, wherein the first backup ID is represented by the first descriptor, wherein the cloud storage server selects the first base backup based on the first descriptor; and transmitting a third request to the cloud storage server over the WAN to replace a second file within the second base backup, the third request including a second backup ID identifying the second base backup, a descriptor describing which of a plurality of files of the second base backup to be replaced, and content of the file received from the client such that a backup would not have to be locked-in with a particular cloud storage provider.