Feedback-based routing

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 the protocol's performance in two very different settings: peer-to-peer overlays and mobile ad-hoc networks (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

Feedback-based routing in MANET's

We developed a variant of FFP for MANETs in which instead of sending the feedback forward from the source to the destination it is sent backward from the destination back to the source. Such protocol is capable to quickly adapting to the changing network conditions and routing around adversarial nodes as they appear

Publications

Castor: Scalable Secure Routing for Ad-hoc Networks
W. Galuba, P. Papadimitratos, M. Poturalski K. Aberer, Z. Despotovic, W. Kellerer, INFOCOM'10
PDF, BibTex, Slides

Self-organized fault-tolerant routing in peer-to-peer overlays
W. Galuba, K. Aberer, Z. Despotovic, W. Kellerer, SASO'09
PDF, BibTex, Slides

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