Perhaps a per node hash of known recent routes to avoid flooding every single time and using flooding as a backup.