Compact-Port Routing Models and Applications to Distance-Hereditary Graphs

In this paper we introduce a new model for compact routing called Compact-Port model. It actually corresponds to a new way of succinctly representing the shortest paths information in interconnection networks and, although we combine it with Interval Routing, it is orthogonal to the known compact routing schemes. The basic intuition behind the model is that if we want to represent all the shortest paths for each source-destination pair, at any source every destination node has a corresponding subset of output ports whose associated links belong to a shortest path to it; vice versa, each output port corresponds to a link belonging to a shortest path to a given subset of nodes. Thus, instead of representing for each output port the set of the destinations optimally reachable through the corresponding link, in the routing table each entry is associated with a subset of ports and a subset of destinations in such a way that the proper shortest paths are represented and further compression is obtained with respect to the classical methods. We first show that there are situations in which the Compact-Port model significantly outperforms the classical Interval Routing. Moreover, we give applications to an interesting family of graphs called distance-hereditary, for which no compact routing methods are still not known so far. Such a class of graphs has the interesting property that whenever any subset of node fails the distance between the nodes which are still connected remains the same. Hence, if full shortest path information is represented, that is all shortest paths between all pair of nodes, since all the neighbors of a node maintain also the same distance from the destinations, the routing can be done without affecting the routing procedure of the node. In fact, either a shortest path is routed or (in case the destination node is disconnected) a failure message can be reported at the sender, no matter of the incident link used to send the message. Finally, we introduce and discuss another compact-port method, called Intersection model, that corresponds to a different correspondence between port and destination subsets.