Distance Routing on Series Parallel Networks

We consider the problem of routing messages on Series Parallel Graphs (SPGs) and we introduce a new technique called Distance Routing. This technique is based on the idea of encoding in the label of each node x some information about a shortest path from the source of the SPG to x, and from x to the terminal node of the SPG. We first compare shortest path Distance Routing and I-interval Routing Schemes on directed SPGs. We then show that Distance Routing can be used to route on bidirectional SPGs, where no general shortest path I-interval Routing Scheme can be applied. We also show the relevance of the study of the time complexity in the choice of a Compact Routing method.

In this paper we consider the problem of routing mes- sages on Series Parallel Graphs (S P Gs), and we introduce a new technique called Distance Routing. This technique is based on the idea of encoding in the label of each node x some information about a shortest path from the source of the S P G to x, and from x to the terminal node of the S P G. We first compare shortest path Distance Routing and 1-Interval Routing Schemes on directed S P Gs. We then show that Distance Routing can be used to route on bidirectional S P Gs, where no general shortest path 1-Interval Routing Scheme can be applied. We also show the relevance of the study of the time complexity in the choice of a Compact Routing method.