My Work On UniDirectional Link Routing

As part of my Master Degree, I worked at INRIA Soiphia Antipolis within the RODEO Team on unidirectional link routing. The subject of my master's thesis was "Dynamic Routing in networks with unidirectional links". My work was supervised by Walid Dabbous.

Why do we need unidirectional routing ?

Today connectivity to the Internet is established with bidirectional links, i.e. any two neighbours can communicate in each direction. There are some situations where we would like to set up unidirectional links only, for some cost or technical reasons. The best example is a satellite link with receive only hardware with a terrestrial backchannel connectivity to the Internet provided by the phone. A path connecting any two nodes in each direction still exists, but the reverse path is different from the outward path (asymmetry of paths).

The problem

Problems come at the level of routing since existing protocols assume that links are always bidirectional and that communication between two nodes takes the same path in both directions. The description of the problem when there exist an unidirectional link is best summarized in the UDLR web page and in our paper published in WOSBIS'97 (GZip PostScript version).

My contribution

My work first consisted in gaining an overview of the problem and the various propositions made at the Working Groupt to handle it, namely Routing Protocol Modification, and Tunneling. I took part in the discussion and helped in enhancing it.

Since the IETF only focuses on the short term, my worked then concentrated on the long term, i.e. cases where many links could be unidirectional. This led first to the study of the applicability of the current proposals and their rejection. Then, I studied the applicability of current routing techniques, Link State and Distance Vector and showed that something else is necessary, because their nature cannot be kept if adapted to unidirectional links. We need something that does not assume any bidirectionality (path, link) neither symmetry (bandwidth) and does not require hop-by-hop acknowledgements. I therefore designed a new protocol, based on the discovery of circuits . Circuits are paths that go to a particular destination and come back to the departure place. All members (nodes) of the circuit are possible destinations. Maintaining circuits ensure that I can reach destinations and I can obtain feedback. I called the protocol UDLRP , which stands for UniDirectional Link Routing Protocol .

You can download my Master's Thesis report (GZip Postscript version).

The protocol is best described in the Research Report number 3292 I wrote with my supervisor Walid Dabbous. It was submitted to INFOCOM'98 without success, unfortunately because it lacks experimentation results.

You will likely find some inconsistencies, especially if you read both the paper and the report since the description of the protocol has changed over time, between the writing of the report and the later writing of the paper. Note that this work is still under investigation.

For more details, please me.

Don't hesitate to give me your feedback, this is always very helpful.

Last modified: 20 august 1998

Thierry Ernst