Brief Announcement: On the Feasibility of Local Failover Routing on Directed Graphs
摘要
Local failover mechanisms are used to achieve fast recovery from link failures in communication networks. These mechanisms are typically implemented using static routing tables at the nodes of a network, only relying on failures of outgoing links, as well as the label of the source and target node of a packet (called \(s-t\) -routing). Static failover \(s-t\) -routing on undirected graphs has been shown to be able to tolerate at most 2 failures, denoted 2-resilient, with 3-resiliency being impossible without additional rewritable bits in the packet header. In this work, we investigate local failover routing on directed graphs with n nodes and show lower and upper bounds on the number of bits required. Even 1-resilience cannot be achieved on all topologies without additional bits and we prove that 1-resilience can be obtained with \(\lceil \log (n)\rceil \) bits. For \(k>1\) failures, we show that at least \(\lceil \log (k+1)\rceil \) bits are necessary, but that \(k(\lceil \log (|E|)\rceil )\) bits are sufficient to obtain k-resiliency.