Jul 2026· IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences· 0 citations· 9 references
Computer Science
TL;DR
This paper studies local failover schemes that minimize the number of rewritable bits in the packet header on directed graphs with $k-arc failures and shows that their scheme is nearly optimal when the number of faulty arcs is approximately less than the number of nodes.
Abstract
The local failover routing is a mechanism that routes a packet from a source to a destination only using pre-calculated routing tables, even when several edges fail. In this paper, we study local failover schemes that minimize the number of rewritable bits in the packet header on directed graphs with $k$-arc failures. There are many studies of failover routing on undirected graphs, and it has been investigated whether routing is possible depending on the number of bits in the packet header, the type of failure, the graph properties, etc. In contrast, there is not much research on directed graphs. Van et al.~first showed the upper and lower bounds of rewritable bits in the packet header on directed graphs. However, their results showed a large gap between the upper and lower bounds. The main contribution of this paper is to close the gap between the upper and lower bounds. Specifically, we show that our scheme can route packets with $k$ faulty arcs if the packet header has $\min(k \log ( \frac{e(2n+k-3)}{k}, 2n \log ( \frac{e(2n+k-3)}{2n})))$ rewritable bits, where $n$ is the number of nodes. Moreover, any local failover routing scheme needs $\Omega(k\lceil\log\frac{n}{k}\rceil)$ rewritable bits when the number of faulty arcs is equal to or less than $\frac{3(n-1)}{8}$ and $\frac{n-1}{4}$ rewritable bits when the number of faulty arc is more than $\frac{3(n-1)}{8}$. This result means our scheme is nearly optimal when the number of faulty arcs is approximately less than the number of nodes.
This paper presents detailed algorithm for calculating L-LSR coefficient, and shows that L-LSR algorithm not only performs better than OSPF, but also has verySignificant performance improvement over the other LSR family of algorithms.
Routing algebras provide a formal framework for reasoning about routing problems, algorithms, and protocols. They currently underpin systems that verify the correctness of internet routing protocol configurations prior to deployment. All such protocols—from BGP to IS-IS, OSPF, and EIGRP—can be regarded as solutions to the stable routing problem, namely that of finding an equilibrium choice of forwarding neighbors at each node of a network so as to reach a common destination. To date, only partial conditions for the existence and uniqueness of stable routings have been established. In this paper, we identify an algebraic property of cycles, which we call centripetalism, that characterizes the existence of unique stable routings for all possible destinations in a network and failure scenarios. Building on this characterization, we present the Consistent-Tree algorithm, which either produces a stable routing or reports the presence of a non-centripetal cycle, in O(n2 × m) time, where n and m denote the number of nodes and links in the network, respectively.
Ricardo Santos, J. L. Sobrinho· Proceedings of the ACM SIGCO...· 0 citations
ABSTRACT We address the Positive Influence Dominating Set problem (PIDS), which involves identifying the smallest group of vertices in a given network that maximizes influence throughout the network. Formally, given a graph G = (V, E), representing the network, we look for a subset of vertices P ⊆ V such that each vertex v i ∈ V \ P has at least ρ deg G (v i ) neighbors in P, where deg G (v i ) is the degree of v i , and 0 < ρ < 1. The problem is known to be NP-hard in general graphs and remains NP-hard even when restricted to certain particular classes, such as chordal graphs. In this paper, we develop an exact algorithm based on the Branch and Bound approach for solving PIDS on chordal graphs. The effectiveness of the proposed algorithm is demonstrated through numerical experiments conducted on various randomly generated chordal graphs.
Y A Bekhti, M. Lalou, Méziane Aïder et al.· Pesquisa Operacional· 0 citations
This article examines series of families of two-dimensional circulant networks with rectangular L-shapes, optimal in diameter, as network-on-chip topologies with a minimal number of crossings between the links and a bounded length of the maximum link that does not depend on the network size. New network-on-chip routing algorithms, which use the coordinates of three adjacent zeros in the planar graph embedding to calculate the shortest paths, were investigated and simulated. A key advantage of the proposed routing algorithms is that they require minimal input data to calculate the shortest paths. Four routing algorithms were implemented in the Noxim network-on-chip simulator using the optimal graphs of the circulant network families under study: the new analytical algorithm, the traditional Dijkstra algorithm, the routing algorithm with virtual coordinates, and the clockwise routing algorithm. The above algorithms were compared under various traffic profiles across three metrics: average and maximum latencies and network throughput. The simulation results showed that, for all traffic profiles, the new routing algorithms designed for the topologies of circulant networks with rectangular L-shapes outperform other algorithms with similar metrics in terms of memory consumption.
M. Malikov, E. Monakhova, E. R. Rzaev et al.· Uchenye Zapiski Kazanskogo U...· 0 citations
We study the shortest-path problem on graphs with positive real-valued edge weights. Given a source vertex $s$ and a target vertex $t$, the goal is to calculate the length of the shortest path from $s$ to $t$. We are particularly interested in instances that can be solved in sublinear time. Recently, Haeupler, Hlad\'ik, Rozho\v{n}, Tarjan, and T\v{e}tek proved that (a version of) the bidirectional Dijkstra's algorithm is instance-optimal on positively weighted multigraphs, both directed and undirected, considering the number of vertices and edges queried by the algorithm. However, multigraphs are not the canonical setting for the shortest-path problem. The problem is typically formulated on simple graphs without loops and parallel edges. They therefore left as an open problem whether bidirectional Dijkstra remains instance-optimal on simple weighted graphs. We answer this question, but for simple graphs, the answer is more complex, depending on the setting. We show that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order. In contrast, under the order-dependent model, where incident edges have a given order, we show that bidirectional Dijkstra is not instance-optimal. For simple directed weighted graphs, we show that bidirectional Dijkstra is not instance-optimal under either the order-oblivious or the order-dependent model, being off by a factor of $\Theta(m/n)$ in both cases. We further show that no algorithm can have instance-optimality ratio $o(m/n)$ under the order-dependent model, or under the order-oblivious model when $m=O(n\sqrt{n})$. On the positive side, the above results imply that bidirectional Dijkstra is instance-optimal up to logarithmic factors on all sparse directed and undirected graphs satisfying $m/n=\log^{O(1)} n$.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 0 citations
Network coding allows intermediate nodes to encode received messages before transmission. The multiple-unicast conjecture asserts that coding has no throughput advantage over fractional routing for independent unicast sessions in any undirected network. Despite more than two decades of sustained study, this central open problem remains unresolved. The conjecture is deeply connected to computational complexity: a proof would yield long-sought lower bounds for fundamental problems. To study the conjecture, this paper develops a unified metric framework from the perspective that the basic objects behind the comparison between coding and routing are not cuts alone, but graph metrics. Using this framework, we prove the conjecture for three new classes of undirected networks: (a) networks with at most five terminal locations; (b) planar networks whose terminal locations lie on the boundaries of at most three designated faces, with each session's endpoints on one such face; and (c) networks with arbitrarily many nodes and terminal locations under a structural restriction on session endpoints. We give a new proof that the conjecture holds for networks with at most six coding nodes, without computer-aided search, and show that if the conjecture holds on $\Gamma_{3,3}$, then it holds whenever no three sessions have six distinct terminal locations.
Sirui Liu, Linfeng Que, Zongpeng Li et al.· 0 citations