You keep track of a few folks at different distances from yourself, and route packets to the folks one knows which are closest to the ultimate destination (or ask them whom they know closest to that destination).

So rather than asking everyone you know, who ask everyone they know, who ask everyone they know, you're asking a subset, who ask a subset, who ask a subset.