Compact Routing Schemes in Undirected and Directed Graphs

Routing is a fundamental task in computer networks. A routing scheme is a mechanism designed to deliver messages efficiently from a source vertex to a destination vertex within the network. In this paper, we study both undirected and directed weighted graphs, aiming to route along short paths.

More specifically, a routing scheme is composed of a preprocessing phase and a routing phase. In the preprocessing phase, the entire graph is accessible, allowing the preprocessing algorithm to compute a routing table and a label for each vertex¹¹1In this paper, we study labeled routing schemes, where the preprocessing algorithm can assign labels to the vertices. When the vertex labels are fixed and cannot be changed, the routing scheme is called an name-independent routing scheme (see, for example, [1, 16, 17, 2, 13]), which is then stored in the local storage of each vertex. In the routing phase, the routing algorithm at each vertex on the routing path can only access the local storage of the vertex. The routing algorithm gets as input a message, a destination label, and possibly a header, and decides which of the vertex neighbors is the next vertex on the routing path. The routing continues until the message reaches the destination.

A compact routing scheme is a routing scheme that uses $o(n)$ space in the local storage on average at each vertex, where $n$ is the number of vertices in the graph. Let $u$ be a source vertex and let $v$ be a destination vertex. We denote by $\widehat{d}(u,v)$ the length of the path used by the routing algorithm to route a message from $u$ to $v$. The stretch of the routing scheme is defined as ${\max }_{u,v\in V}(\frac{\widehat{d}(u,v)}{d(u,v)})$, where $d(u,v)$ is the distance from $u$ to $v$. The roundtrip stretch is defined as ${\max }_{u,v\in V}(\frac{\widehat{d}(u,v)+\widehat{d}(v,u)}{d(u,v)+d(v,u)})$.

The design of efficient compact routing schemes in undirected graphs has been a well-studied subject in the last few decades, see for example [19, 3, 4, 8, 11, 24, 22, 7]. In Table 1 we summarize the previous results.

From the Erdős girth conjecture, it follows that every routing scheme with stretch must use a total storage of $\mathrm{\Omega }(n^{1+1/k})$ bits. The approximate distance oracle data structure of Thorup and Zwick [25], which is implemented in the centralized model, where all the information is available upon a distance query to the data structure, has an optimal $(2k-1)$-stretch with $\tilde{O}(n^{1+1/k})$ total storage. In light of the gap between routing schemes and approximate distance oracles, the following problem is natural.

The $\approx 3.68k$-stretch compact routing scheme of Chechik [7], from more than a decade ago, is the current best stretch with $\tilde{O}(n^{1/k})$ worst-case local storage. In this paper, we improve the stretch to $\approx 2.64k$ by allowing an average local storage of $\tilde{O}(n^{1/k})$, as presented in the following theorem.

All the compact routing schemes mentioned so far solve the problem of sending a single message from the source to the destination, while in most real-world network applications, two parties communicate over the network for a session. A communication session is composed of two phases. In the first phase, a connection is established between the source and the destination, and in the second phase, a stream of messages is exchanged between the parties. Many real-world protocols, such as TLS, QUIC, TCP, SSH, Wi-Fi, and Bluetooth, adhere to this framework.

We consider the handshake mechanism for the establishment phase, as presented by Thorup and Zwick [24]. The handshake is composed of two messages of size $\tilde{O}(1)$, that are exchanged between the parties to establish the connection. The first message is sent from the source to the destination, and the second message is sent from the destination back to the source. Since the handshake is composed of a message sent from the source to the destination and back, the stretch of the handshake is the roundtrip stretch defined earlier.

Thorup and Zwick [24] presented a compact routing scheme that uses a handshake, in which two messages are routed along a $(4k-5)$-stretch path, to establish a connection. Then, a stream of messages is routed along an optimal $(2k-1)$-stretch path. While the compact routing scheme of Chechik [7] achieves an $\approx 3.68k$-roundtrip stretch for the handshake, there is still a significant gap from the optimal $(2k-1)$-stretch followed by the Erdős girth conjecture. Therefore, the main open problem for routing in a communication session is to reduce the stretch of the handshake phase and obtain a compact roundtrip routing scheme with improved stretch.

In this paper we solve Problem 2 by presenting an optimal $(2k-1)$-roundtrip stretch for the handshake phase, that matches the lower bound that follows from the Erdős girth conjecture, as presented in the following theorem.

Using this result with the handshake-based routing scheme of Thorup and Zwick [24], one obtains an optimal $(2k-1)$-stretch compact routing scheme for any communication session. We summarize our new results for undirected graphs and compare them to the previous work in Table 1.

Next, we turn our attention to weighted directed graphs. Since preserving the asymmetric reachability structure of directed graphs requires $\mathrm{\Omega }(n^2)$ space²²2In a bipartite graph in which all the edges are from one side to the other, there are $\mathrm{\Theta }(n^2)$ edges and removing each of them makes the destination not reachable from the source. Thus, storing reachability requires $\mathrm{\Omega }(n^2)$ space., no spanner, emulator, or compact routing scheme can exist for directed graphs. Cowen and Wagner [9] circumvented the $\mathrm{\Omega }(n^2)$ space lower bound by introducing roundtrip distances in directed graphs, defined as $d(u\leftrightarrow v)=d(u,v)+d(v,u)$.

In the last few decades, a few compact roundtrip routing schemes were presented, see for example [9, 10, 21]. The state-of-the-art result was obtained by Roditty, Thorup, and Zwick [21]. They presented a $3$-stretch compact roundtrip routing scheme that uses $\tilde{O}(n^{1/2})$ local storage and also a $(4k+\epsilon )$-stretch compact roundtrip routing scheme that uses $\tilde{O}(n^{1/k})$ local storage for every $k\ge 3$.

From the Erdős girth conjecture, it follows that every compact roundtrip routing scheme with stretch must use total storage of $\mathrm{\Omega }(n^{1+1/k})$ bits. Closing the gap between the upper and the lower bound is the main open problem regarding compact roundtrip routing schemes.

In recent years, roundtrip distances have been extensively studied but only in the context of roundtrip spanners and roundtrip emulators (see, for example [14, 6, 21, 23, 5, 18]). Despite all the recent progress, no improvements were obtained for compact roundtrip routing schemes since the $(4k+\epsilon )$-stretch roundtrip routing scheme of [21] from more than two decades ago.

In this paper, we improve upon [21] for the case that $k=3$. More specifically, using $\tilde{O}(n^{1/3})$ local storage, Roditty, Thorup, and Zwick [21] obtained a $(12+\epsilon )$-stretch roundtrip routing scheme. We present a $7$-stretch roundtrip routing scheme that uses $\tilde{O}(n^{1/3})$ local storage, as presented in the following theorem.

In addition, in the following theorem, we present an optimal³³3Assuming the Erdős conjecture, it is easy to create a graph $G$ with $\mathrm{\Omega }(n^{1+1/k})$ edges such that the girth of $G$ is $2k+2$, and the diameter of $G$ is at most $2k+1$. Given a graph with $\mathrm{\Omega }(n^{1+1/k})$ edges and $2k+2$ girth, if there is a pair of vertices $u,v\in V$ such that $d(u,v)\ge 2k+2$, we can add an edge between $u$ and $v$ to the graph without reducing the girth. By repeating this process until there are no pairs $u,v\in V$ such that $d(u,v)\ge 2k+2$, we get that the diameter is at most $2k+1$. , up to polylogarithmic factors, compact roundtrip routing scheme in graphs with $D_{hop}=\tilde{O}(k)$, where $D_{hop}$ is the hop diameter of the graph.

We summarize our new results for directed graphs and compare them to the previous work in footnote 5.

The rest of this paper is organized as follows. In Section 2 we present some necessary preliminaries. In Section 3 we present an overview of our technical contributions and our new compact routing schemes. In Section 4 we present our optimal compact roundtrip routing scheme for weighted undirected graphs. In Section 5 we extend Section 4 to directed graphs with small hop diameter. In Appendix A we present our $7$-stretch compact roundtrip routing scheme for weighted directed graphs. Finally, in Section 6 in the full version of this paper [15], we present our single message compact routing scheme for weighted undirected graphs that use average local storage.

Let $G=(V,E,w)$ be a weighted graph with $n$ vertices and $m$ edges, where $w:E\to {ℝ}^{+}$. We consider both connected undirected graphs and strongly connected directed graphs⁶⁶6If the graph is not connected (or not strongly connected), we add a dummy vertex and connect it with bi-directional edges of weight $\mathrm{\infty }$ to every vertex of the graph..

Let the distance $d_G(u,v)$ from $u$ to $v$ be the length of the shortest path from $u$ to $v$ in $G$, where the length of a path is the sum of its edge weights, and let $P_G(u,v)$ be the shortest path from $u$ to $v$, $G$ is omitted when it is clear from context. The roundtrip distance $d(u\leftrightarrow v)$ is defined as $d(u,v)+d(v,u)$. Throughout this paper, we assume that for any two vertices $u$ and $v$, there exists a unique shortest path between them. In the case of multiple shortest paths of the same length, we break ties by selecting the path with the lexicographically smallest sequence of vertex identifiers.

Let $X\subseteq V$. The distance $d(u,X)$ from $u$ to $X$ is the distance between $u$ and the closest vertex to $u$ from $X$, that is, $d(u,X)={\min }_{x\in X}(d(u,x))$. Similarly, the roundtrip distance from $u$ to $X$ is defined as $d(u\leftrightarrow X)={\min }_{x\in X}(d(u\leftrightarrow x))$. Let $p(u,X)=\arg {\min }_{x\in X}(d(u\leftrightarrow x))$ (ties are broken in favor of the vertex with a smaller identifier).

Next, following the ideas of Thorup and Zwick [25], we define bunches and clusters. Let $u\in V$ and let $X,Y\subseteq V$. The bunch of $u$ with respect to $X$ and $Y$ is defined as . The ball of $u$ with respect to $Y$ is defined as (notice that $B(u,Y)=B(u,V,Y)$). The cluster of $u$ with respect to $Y$ is defined as .

The starting point in many algorithms, distance oracles, and compact routing schemes, and in particular in Thorup and Zwick [24] routing scheme, is a hierarchy of vertex sets $A_0,A_1,\mathrm{\dots },A_k$, where $A_0=V$, $A_k=\mathrm{\varnothing }$, $A_{i+1}\subseteq A_i$ and $|A_i|=n^{1-i/k}$ for $0\le i\le k-1$.

For every $0\le i\le k-1$, the $i$-th pivot of $u$ is defined as $p_i(u)=p(u,A_i)$, and $h_i(u)$ is defined as $d(u,A_i)$. The $i$-th bunch of $u$ is defined as $B_i(u)=B(u,A_i,A_{i+1})$. The bunch of $u$ is defined as the union of its individual bunches, that is, $B(u)={\bigcup }_{i=0}^{k-1}{B}_i(u)$. The cluster of a vertex $w\in A_i\setminus A_{i+1}$ is defined as the cluster of $w$ with respect to the set $A_{i+1}$, that is, $C(w)=C(w,A_{i+1})$. We denote by $[k]$ the set $\{0,1,2,\mathrm{\dots },k-1\}$.

In the following lemma, we provide an upper bound for the size of $B(u)$, which is $O(k{n}^{1/k})$, as demonstrated by Thorup and Zwick [25].

In the following lemma, we provide an upper bound for the size of $C(u)$, which is $O(n^{1/k})$, as demonstrated by Thorup and Zwick [24].

Let $S\subseteq V$. We define $T_{out}(u,S)$ as a tree containing the directed shortest paths from $u$ to all the vertices in $S$, and $T_{in}(u,S)$ as a tree containing the directed shortest paths from all the vertices in $S$ to $u$. When $u$ is clear from context, we omit it, for example, we use $T(C(u))=T(u,C(u))$, and $T(B(u))=T(u,B(u))$. Note that it is possible for $|T_{out}(u,S)|$ to be bigger than $|S|$ in cases where the shortest path from $u$ to a vertex in $S$ passes through a vertex not in $S$. ⁷⁷7We denote with $|H|$ the number of edges in $H$, i.e. $|H|=|E(H)|$. Let $T(u,X)=T_{in}(u,X)\cup T_{out}(u,X)$, as defined in [21], when $u$ is clear from context we omit it and write $T(X)$. Notice that in undirected graphs, since $T_{in}(u,X)=T_{out}(u,X)$, we have that $T(u,X)=T_{in}(u,X)=T_{out}(u,X)$. Next, we show that if $S$ is a ball, i.e. $S=B(u,X)=B(u,V,X)$ for some set $X$, then $|T_{out}(u,S)|=|S|$ and $|T_{in}(u,S)|=|S|$, and therefore $|T(u,S)|\le 2|S|$.

In this section, we present an overview of our new compact routing schemes and their main technical contributions. Throughout the overview, let $V=A_0,\mathrm{\dots },A_k=\mathrm{\varnothing }$ be a hierarchy such that, $|A_i|=\tilde{O}(n^{1-i/k})$ and $|B(u)|=\tilde{O}(n^{1/k})$, for every $u\in V$, created using Section 2. We denote with $x\to y$ routing from $x$ to $y$ on $P(x,y)$.