Do Automated Cross-Platform Network Backups The Easy Way, Part 2 - page 2
BackupPC is extremely efficient, because it uses a pool system that hardlinks to identical files. So instead of storing multiple copies of the same file, it only stores one. The first three or four backups will consume the most time and space as the main pool is built; after that only changes will be recorded. Turning on compression reduces the pool size as much as 40%. Using compression uses more CPU cycles, but once the initial pool is built this won't affect performance. So it is possible that a complete backup of every host on your network will require less storage space than the aggregate total. The BackupPC manual gives an example of 240GB of raw data being reduced to 87GB. As a starting point, allow for twice your raw total.
Make sure your name resolution and DHCP are working correctly. If they aren't, neither will BackupPC.