The Forward Feedback Protocol

Synopsis

The Forward Feedback Protocol (FFP) is a simple generic mechanism for improving the robustness of routing protocols. The routed messages are followed by feedback messages on their routes. The feedback is initiated by the source and signals either success or failure of message delivery (the semantics of failure and success are application definable).

Each router on the routing path learns whether it did a good job routing or not based on the feedback messages. Each router locally uses the feedback information to optimize its routing decisions. Collectively the whole network selects the routing paths that are likely to lead to successful packet delivery to their destinations.

The problems FFP solves

We have tested FFP's performance in two very different settings: overlays (like Chord) and MANETs. The problems that FFP can solve are:

• message dropping - when some nodes are dropping packets (maliciously or otherwise) it causes a rise in negative feedback and the routers start routing around the dropping nodes
• message delaying - when messages are forwarded they are delayed at both the nodes and the links between them, for some nodes or links the forwarding delay might be large, e.g. because of overload. If it takes too long to deliver the message to its destination some applications might consider it to be a failure and signal this with negative feedback. The FFP mechanism can then be used to route around the slow nodes and links.
• route discovery - FFP is capable of cold-starting, i.e. the routing tables can initially be empty and FFP will make random routing decisions gradually learning via feedback which next hops perform well for which destinations

FFP variants

• multi-path mode - we developed a variant of FFP for MANETs in which instead of sending a message along a single path, it is sent along several paths simultaneously. The path that succeeds first is reinforced with positive feedback. This significantly speeds up the process of route discovery.
• BFP - another variant of FFP is the Backward Feedback Protocol in which the feedback messages are sent from the destination back to the source on the reverse path of the original message. We are building a secure routing protocol for MANETs based on BFP. The early results are very promising, BFP is tolerant to a wide battery of attacks and can also quickly find alternative routes when the existing ones fail due to node mobility.

Open problems

• feedback security - in FFP, the feedback messages affect routing, an adversary could maliciously modify the feedback messages or spoof them to disrupt the routes. We are currently investigating the different techniques for making the feedback messages tamper-resistant and spoofing-proof and working out the different ways of managing the in-network state. We've discovered a number of interesting performance-security tradeoffs.
• routing optimality - the routers need to constantly maintain a performance model of their next hop neighbors. The model is used to make the routing decisions and updated whenever new feedback arrives. There are many ways to do this, ranging from keeping simple per-neighbor statistics to fully-blown learning methods borrowed from AI. It is not clear which of these solutions is optimal. We are currently building a theoretical framework that will hopefully provide us with some insight into the problem.

Publications

Bandwidth-efficient delay- and fault-tolerant overlay routing
W. Galuba, K. Aberer, Z. Despotovic, W. Kellerer, ICNP 2008
PDF, Poster

Authentication-free Fault-tolerant Peer-to-peer Service Provisioning
W. Galuba, K. Aberer, Z. Despotovic, W. Kellerer, DBISP2P 2007
PDF, BibTex, Slides