Fast Rerouting Against Dynamic Failures: 2-Resilience via Ear-Decomposition and Planarity

An ear decomposition $𝒫\left(G\right)$ (abbreviately, $𝒫$) of a graph $G$ is a sequence of subgraphs $G=P_0\cup P_1\cup \mathrm{\cdots }\cup P_{\kappa }$, where $P_0$ is a cycle in $G$, and for each $i\ge 0$, $P_{i+1}$ is a path whose endpoints lie in $P_0\cup P_1\cup \mathrm{\cdots }\cup P_i$, while all internal vertices of $P_{i+1}$ are disjoint from $P_0\cup P_1\cup \mathrm{\cdots }\cup P_i$. The cycle $P_0$ is called the initial ear, and each $P_{i+1}$ (for $i\ge 0$) is called an ear. If the two endpoints of $P_{i+1}$ coincide (so that $P_{i+1}$ forms a cycle), it is referred to as a closed ear; otherwise, it is an open ear [33, 19, 23, 25]. In particular, the family ${\{E(P_i)\}}_{i=0}^{\kappa }$ forms a partition of $E(G)$; that is, every edge $e\in E(G)$ lies in exactly one ear $P_i\in 𝒫$. Robbins (1939) [25, 33] showed that a graph $G$ is $2$-edge-connected if and only if it admits an ear-decomposition, in which each $P_i$ for $i\ge 1$ is either an open ear or a closed ear, and every cycle in a $2$-edge-connected graph $G$ can be the initial ear $P_0$ in some such decomposition. More specifically, one can compute an ear decomposition such that a specified vertex $v\in V$ is contained in the initial ear [28, 21, 19, 23, 26]. In the following, we assume that the destination $t\in V$ is implicitly contained in the initial ear.

Since each edge $\{u,v\}\in E$ uniquely belongs to some ear $P_i\in 𝒫$, each oriented arc of $\{u,v\}$ is uniquely contained in either $\overrightarrow{P_i}$ or $\overleftarrow{P_i}$, even if $P_i$ is closed.

By Definition 9, we define a function that maps each node to an ear to start routing.

We present the argument for right routing; the case of left routing follows analogously. By Lemma 6, every edge $e\in E$ is incident with exactly two distinct faces, say $f_i,f_j\in ℱ$.

Consider an embedding of $G$ on the Euclidean plane, and let $\{u,v\}\in E$ be an edge shared by $f_i$ and $f_j$. The infinite line by expanding $\{u,v\}$ separates the plane into two half-planes, with $f_i$ lying entirely on one side and $f_j$ entirely on the other. Now, when traversing an arc $(u,v)$ (resp., $(v,u)$), exactly one of these half-planes (and thus exactly one of the two faces) lies to the right of the traversal. Consequently, in a right routing, the directed cycles $\overrightarrow{f_i}$ and $\overrightarrow{f_j}$ cannot share the same directed arc of $\{u,v\}$. Therefore, once the routing direction is fixed, each arc $(u,v)$ of an edge $\{u,v\}\in E$ is contained in exactly one directed cycle $\overrightarrow{f_i}$, which uniquely determines the corresponding face $f_i\in ℱ$.

By definition, for any edge $\{u,v\}$ and any face $f_i\in ℱ$, if the arc $(u,v)$ belongs to $\overleftarrow{f_i}$, then the reverse arc $(v,u)$ belongs to $\overrightarrow{f_i}$. $◀$ In Definition 12, we define the rightmost and leftmost nodes on each face respectively, which serve as checkpoints to terminate face-based routing.

Lemma 13 shows that our face-based routing can visit all nodes of a face $f_i\in ℱ$, including the leftmost and rightmost nodes of $f_i$, provided there is at most one failure in $f_i$.

Our proof is carried out for the right routing $\overrightarrow{ℱ}$; the case of the left routing $\overleftarrow{ℱ}$ follows analogously. Suppose $(v,u)\in \overrightarrow{f_i}$ is failed. Starting from $u$, the outgoing link (arc) along $\overrightarrow{f_i}$ is not failed, and hence there exists a directed sub-path from $u$ to any node $t\in V(f_i)$ that is entirely contained in $\overrightarrow{f_i}\setminus \{(v,u)\}$ that is a directed path from $u$ to $v$ along $\overrightarrow{f_i}$. $◀$

In Algorithm 1, when a packet begins at an internal node in an (including the initial) ear $P_{\text{curr}}\in 𝒫$, it is first routed along the left direction $\overleftarrow{P_{\text{curr}}}$ of $P_{\text{curr}}$. Upon encountering a failure, the traversal switches to the right direction $\overrightarrow{P_{\text{curr}}}$. If each ear satisfies $|E(P_{\text{current}})\cap F|\le 1$, then one of the two routings, i.e., $\overleftarrow{P_{\text{curr}}}$ or $\overrightarrow{P_{\text{curr}}}$, always leads to an endpoint of $P_{\text{current}}$. From there, the packet proceeds into an earlier ear $P_i\in 𝒫$ with , and ultimately reaches $P_0$ to arrive at $t$. Since ear indices strictly decrease, no ear is revisited, and thus routing loops cannot occur. $◀$

By Lemma 15, if two failures $F=\{e_1,e_2\}$ are only shared by distinct faces $f_i,f_j\in ℱ$, then this scenario can be excluded from the resilient routing design, as the node, where a packet is currently staying, and destination $t$ lie in separate connected components of $G\setminus F$.

Consider the plane dual graph $G^{\ast }=(U^{\ast },X^{\ast })$ of $G=(V,E)$, where each vertex $u_i^{\ast }\in U^{\ast }$ corresponds to a face $f_i\in ℱ$ of $G$, and each edge $e\in E$ shared by two faces $f_i,f_j\in ℱ$ corresponds to an edge $\{u_i^{\ast },u_j^{\ast }\}\in X^{\ast }$. Note that $G^{\ast }$ may contain multi-edges even if $G$ is simple. Since $e_1,e_2$ are common to $f_i$ and $f_j$, their duals $e_1^{\ast },e_2^{\ast }$ are parallel edges between $u_i^{\ast }$ and $u_j^{\ast }$; thus, $\{e_1^{\ast },e_2^{\ast }\}$ forms a simple cycle of length two in $G^{\ast }$.

By the cut–cycle duality for plane graphs [12], a set $J\subseteq E$ is a minimal edge cut (bond) in $G$ iff the dual set $X^{\ast }\left(J\right):=\{e^{\ast }\in X^{\ast }:e\in J\}$ is a simple cycle in $G^{\ast }$. Applying this to $J=\{e_1,e_2\}$ shows that $\{e_1,e_2\}$ is a bond of $G$. Thus, deleting $e_1$ and $e_2$ disconnects $G$. $◀$ Now, we formally prove the correctness of the $2$-bits rewriting algorithm in Theorem 16.

By Lemma 14, we may assume that both failures $e_1,e_2\in F$ lie on the same ear $P_{\text{curr}}\in 𝒫$, and that the packet is currently located at a node $v_{\text{cursor}}$ between $e_1$ and $e_2$ on $P_{\text{curr}}$; otherwise, $t$ can be reached solely via ear-based routing.

Let $e_2=(u,v)$ be the second failure, with $(u,v)\in \overrightarrow{P_{\text{curr}}}$. By Lemma 11, there exist two distinct faces $f_i,f_j\in ℱ$ (with one possibly being the outer face), such that $(v,u)\in \overrightarrow{f_i}$ and $(v,u)\in \overleftarrow{f_j}$. By Lemma 15, at least one of $f_i,f_j$ contains only $e_2$ but not $e_1$.

We first traverse $\overrightarrow{f_i}$ starting at $u$ due to $\beta =0$. If no further failure occurs, then by Lemma 13, we reach the rightmost node $v^r(f_i)$ of $f_i$, closer to the right endpoint of $P_{\text{curr}}$ than $(u,v)$ along $\overrightarrow{P_{\text{curr}}}$. Note that the directed subpath of $\overrightarrow{P_{\text{curr}}}$ from $v^r(f_i)$ cannot include either $e_1$ or $e_2$ by Definition 12. From $v^r(f_i)$, either routing continues along $\overrightarrow{P_{\text{curr}}}$ to reach the endpoint of $P_{\text{curr}}$, or $v^r(f_i)$ is already an internal node of an ear $P_j$ with , from which $t$ is reachable by ear-based routing alone. Note that $P_{\text{curr}}$ may not be ${𝒫}_{\min }\left(f_i\right)$.

If instead traversal of $\overrightarrow{f_i}$ encounters $e_1$, switching back to ear-based routing either leads to the endpoint of $P_{\text{curr}}$ along $\overleftarrow{P_{\text{curr}}}$ or to revisiting $(u,v)$ along $\overrightarrow{P_{\text{curr}}}$. In this case, face-based routing resumes via $\overleftarrow{f_j}$ (since $\beta =1$ and $(v,u)\in \overleftarrow{f_j}$), eventually reaching the rightmost $v^r(f_j)$ of $f_j$. Although $v^r(f_j)$ may differ from $v^r(f_i)$, the directed subpath of $\overrightarrow{P_{\text{curr}}}$ from $v^r(f_j)$ onward avoids both $e_1$ and $e_2$. From $v^r(f_j)$, the above ear-based procedure applies. $◀$

It remains to consider the case where a packet gets stuck on an ear $P_{\text{curr}}\in 𝒫$ containing two failures, where first hitting $(u^1,v^1)\in \overleftarrow{P_{\text{curr}}}$ and then encountering $(u^2,v^2)\in \overrightarrow{P_{\text{curr}}}$.

Let $f_i\in ℱ$ with associated ear $P_{\mathrm{\ell }}:={𝒫}_{\text{ass}}(f_i)$ and $(v^2,u^2)\in \overrightarrow{f_i}$. Then $\overrightarrow{f_i}$ is consistent with $\overleftarrow{P_{\text{curr}}}$ (Lemma 17), while its consistency with $P_{\mathrm{\ell }}$ depends on whether $P_{\text{curr}}=P_{\mathrm{\ell }}$.

If $f_i$ contains only one failure, we will show a traversal along $\overrightarrow{f_i}$ from $u^2$ terminates at either the rightmost node $v^r(f_i)$, the leftmost node $v^l(f_i)$, or an endpoint of $P_{\mathrm{\ell }}$ (Algorithm 3, Lines 1–3;), from which ear-based routing resumes to reach $t$. By Lemma 13, all nodes of $V(f_i)$ are eventually visited. If the current node $v_{\text{cursor}}$ is an endpoint of $P_{\mathrm{\ell }}$, the traversal along $\overrightarrow{f_i}$ terminates and routing leaves $P_{\mathrm{\ell }}$ through this endpoint. We now assume $v^r(f_i)\ne v^l(f_i)$; otherwise, $v^r(f_i)=v^l(f_i)$ is itself an endpoint of $P_{\mathrm{\ell }}$ (Definition 12).

If $P_{\text{curr}}=P_{\mathrm{\ell }}$, then $\overrightarrow{f_i}$ is consistent with $\overleftarrow{P_{\mathrm{\ell }}}$. In this case, we can show the traversal must halt at the rightmost node $v^r(f_i)$ (not at $v^l(f_i)$). Let $(u,v^r(f_i))\in \overrightarrow{f_i}$ be the arc preceding $v^r(f_i)$ along $\overrightarrow{f_i}$ (we may have $u^2=v^r(f_i)$ with $v^2=u$). Suppose $\{u,v^r(f_i)\}\in E(P_{\mathrm{\ell }})$. Then, by $(u,v^r(f_i))\in \overrightarrow{f_i}$ and Lemma 17, it follows that $(u,v^r(f_i))\in \overleftarrow{P_{\mathrm{\ell }}}$. By Definition 10, this would imply $(v^r(f_i),u)\in \overrightarrow{P_{\mathrm{\ell }}}$, contradicting that $v^r(f_i)$ is the rightmost node of $f_i$. Hence, it implies $\{u,v^r(f_i)\}\notin E(P_{\mathrm{\ell }})$ and the traversal along $\overrightarrow{f_i}$ halts at $v^r(f_i)$. To show that the traversal cannot halt at $v^l(f_i)$, assume there exists an arc $(\mu ,v^l(f_i))\in \overrightarrow{f_i}$. If $(\mu ,v^l(f_i))\notin \overleftarrow{P_{\mathrm{\ell }}}$, then by Lemma 17, we have $\{\mu ,v^l(f_i)\}\notin E(P_{\mathrm{\ell }})$. By Definition 12, $v^l(f_i)$ must have a neighbor $\nu$ with $(v^l(f_i),\nu )\in \overrightarrow{f_i}$ and $(v^l(f_i),\nu )\in \overleftarrow{P_{\mathrm{\ell }}}$. This implies $\nu$ is visited after $v^l(f_i)$ along $\overleftarrow{P_{\mathrm{\ell }}}$, contradicting that $v^l(f_i)$ is the leftmost node. Hence, $(\mu ,v^l(f_i))\in \overrightarrow{f_i}$ implies $(\mu ,v^l(f_i))\in \overleftarrow{P_{\mathrm{\ell }}}$, indicating that the traversal cannot stop at $v^l(f_i)$. Consequently, from $v^r(f_i)$ the ear-based traversal along $\overrightarrow{P_{\text{curr}}}$ leaves $P_{\text{curr}}$ without further failures and finally reaches $t$.

If $P_{\text{curr}}\ne P_{\mathrm{\ell }}$, then $\overrightarrow{f_i}$ can be consistent with either $\overleftarrow{P_{\mathrm{\ell }}}$ or $\overrightarrow{P_{\mathrm{\ell }}}$. Starting at $u^2\notin V\left(P_{\mathrm{\ell }}\right)$, if $\overrightarrow{f_i}$ consistent with $\overleftarrow{P_{\mathrm{\ell }}}$ (resp., $\overrightarrow{P_{\mathrm{\ell }}}$), the traversal along $\overrightarrow{f_i}$ stops at $v^r\left(f_i\right)$ (resp., $v^l\left(f_i\right)$) since the incoming link (arc) $(w,v_{\text{cursor}})\notin \overleftarrow{P_{\mathrm{\ell }}}$ (resp., $(w,v_{\text{cursor}})\notin \overrightarrow{P_{\mathrm{\ell }}}$). As $P_{\mathrm{\ell }}$ contains no failure (), the ear-based routing from $v^r(f_i)$ (resp., $v^l(f_i)$) along $\overrightarrow{P_{\mathrm{\ell }}}$ (resp., $\overleftarrow{P_{\mathrm{\ell }}}$) always leaves $P_{\mathrm{\ell }}$ and continue traversing on the ears $P_o$ with to reach $t$.

If there are two failures on $P_{\text{curr}}$, upon hitting $(u^1,v^1)\in \overleftarrow{P_{\text{curr}}}$ (stopping at $u^1$), by Lemma 17, we know $(v^2,u^2)\in \overrightarrow{f_i}$ and $(u^1,v^1)\in \overrightarrow{f_i}$ since $\overrightarrow{f_i}$ is consistent with $\overleftarrow{P_{\text{curr}}}$. In this case there exists a face $f_j\in ℱ$ with associated ear $P_{{\mathrm{\ell }}^{\prime }}:={𝒫}_{\text{ass}}(f_j)$ such that $(v^1,u^1)\in \overrightarrow{f_j}$ (By Lemma 15, only one failure on $f_j$), because $\overrightarrow{f_j}$ is consistent with $\overrightarrow{P_{\text{curr}}}$. If $P_{\text{curr}}=P_{{\mathrm{\ell }}^{\prime }}$, then traversing $\overrightarrow{f_j}$ from $u^1$ halts at either an endpoint of $P_{{\mathrm{\ell }}^{\prime }}$ or at $v^l(f_j)$. Then, following $\overleftarrow{P_{{\mathrm{\ell }}^{\prime }}}$ from $v^l\left(f_j\right)$ (resp., the endpoint of $P_{{\mathrm{\ell }}^{\prime }}$) by ear-based routing can leave $P_{{\mathrm{\ell }}^{\prime }}$ to eventually reach $t$. However, if $P_{\text{curr}}\ne P_{{\mathrm{\ell }}^{\prime }}$, we can argue similarly as above, since no failures on $P_{{\mathrm{\ell }}^{\prime }}$. $◀$

We compute the routing rules of Algorithm 1 in a centralized model. The one- and two-bit rewriting approaches have identical time costs. For a graph $G$ with $n$ nodes and $m$ edges, a planar embedding can be computed in $O(n)$ [2, 20], an ear-decomposition in $O(n+m)$ [26], and ear-/face-based routing rules in $O(m)$. In the worst case, recomputing ear-decompositions per destination yields $O(n^2+mn)$ total time. By comparison, source-matched routing [8] needs $O(nm)$ per source–destination pair, i.e., at least $n^2$ times slower. Memory usage is reduced from $n^2$ tables (source–destination) to only $n$ (per destination). Moreover, our reliance on ear-decomposition and planar embeddings – well studied in parallel and distributed computing – underscores the practical feasibility of our routing schemes.