| There are two parts to this problem; changing Package files, and changing packages.
The first, which people appear to be keen to optimize, is already solved by rsync. I use apt-proxy on my 28.8k link and it’s use of rsync as the backend saves me _heaps_ of package downloads.
The second is trickier. There are several problems; the packages change names, and a small change to a package can make a big binary difference.
The name change problem means rsync sees it as a different file, and hence doesn’t even attempt a delta-update. This can be fixed by using clever heuristic name matching to find a suitable old package to use as a basis.
The big binary difference problem means any delta-update doesn’t save you anything. It would help a little if packages used rsyncable gzip, but this still doesn’t take into account a one line source change can totaly change a compiled binary. Ironicly, bsd’s use of cvsup to distribute source rather than binary packages could save you bandwidth for this reason.
There is no point in solving the big binary difference problem untill you’ve solved the name change problem. The best solution of all would be for package mantainers to take more care when creating packages, so we don’t get new “fix stupid dendancy mistake” type packages every day, but this goes against the “release early” philosophy.
There are other more esoteric solutions… xdelta mentions an extended http server/proxy that stores deltas for all versions of objects, allowing clients to request a particular delta between any two versions (using an md5sum as a key to identify versions). This gives you very optimized deltas at the cost of the server keeping every single version in delta format. Once you go down this path, you can do all sorts of wierd things like having client/server negotiate deltas for uncompressed versions of compressed objects. However, you introduce a whole new client/server/protocol to the net, and all the headaches that entails.
Bottom line: all this is all very exciting, but please don’t re-invent a wheel… Instead use and contribute to what is already out there.