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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Brief Announcement: On the Feasibility of Local Failover Routing on Directed Graphs

  • Erik van den Akker,
  • Klaus-Tycho Foerster

摘要

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.