Nowadays, a majority of the Internet service providers are either piloting or migrating to software-defined networking (SDN) in their networks. In an SDN architecture a central network controller has ...a top-down view of the network and can directly configure each of their physical switches. It opens up several fundamental unsolved challenges, such as deploying efficient multipath routing that can provide disjoint end-to-end paths, each one satisfying specific operational goals (e.g., shortest possible), without overwhelming the data plane with a prohibitive amount of forwarding state. In this paper, we study the problem of finding a pair of shortest (node- or edge-) disjoint paths that can be represented by only two forwarding table entries per destination. Building on prior work on minimum length redundant trees, we show that the complexity of the underlying mathematical problem is NP-complete and we present fast heuristic algorithms. By extensive simulations, we find that it is possible to very closely attain the absolute optimal path length with our algorithms (the gap is just 1%-5%), eventually opening the door for wide-scale multipath routing deployments. Finally, we show that even if a primary tree is already given it remains NP-complete to find a minimum length secondary tree concerning this primary tree.
In fair division problems, we are given a set S of m items and a set N of n agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds ...the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting.
In particular, we present a polynomial time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we give a pseudo-polynomial time algorithm that always finds an EFX allocation of chores. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are {0,+1}-valued functions, and negative Boolean utilities that are {0,−1}-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.
Generalized diversity coding is a promising proactive recovery scheme against single edge failures for unicast connections in transport networks. At the source node, the user data is split into two ...parts, and their bitwise XOR is computed as a third redundancy sub-flow. In order to guarantee instantaneous failure recovery without costly node upgrades, the network must ensure that any two of the three sub-flows reach the destination node in case of a single edge failure only by allowing flow duplication or merging identical flows, and avoiding any coding operation in the core network. In this paper, we investigate the corresponding routing problem to calculate capacity-efficient routes for these sub-flows. We propose a polynomial-time algorithm for topologies without capacity constraints on the links and without capability limitations of the nodes. We show that with node limitations the presented algorithm (as well as a minimum cost disjoint path-pair) provides a 4/3-approximation for the routing problem. Furthermore, we formulate an integer linear program to provide a minimum cost solution with arbitrary constraints in general graphs and we propose a polynomial-time algorithm in directed acyclic graphs. Our simulation results suggest that with upgrading only a small set of core network nodes with flow duplication and merging capabilities most of the benefits of generalized diversity coding can be achieved.
In this paper, we propose a new proactive recovery scheme against single edge failures for unicast connections in transport networks. The new scheme is a generalization of diversity coding where the ...source data AB are split into two parts A and B and three data flows A, B, and their exclusive OR (XOR) A⊕B are sent along the network between the source and the destination node of the connection. By ensuring that two data flows out of the three always operate even if a single edge fails, the source data can be instantaneously recovered at the destination node. In contrast with diversity coding, we do not require the three data flows to be routed along three disjoint paths; however, in our scheme, a data flow is allowed to split into two parallel segments and later merge back. Thus, our generalized diversity coding (GDC) scheme can be used in sparse but still two-connected network topologies. Our proof improves an earlier result of network coding, by using purely graph theoretical tool set instead of algebraic argument. In particular, we show that when the source data are divided into two parts, robust intra-session network coding against single edge failures is always possible without any in-network algebraic operation. We present linear-time robust code construction algorithms for this practical special case in minimal coding graphs. We further characterize this question, and show that by increasing the number of edge failures and source data parts, we lose these desired properties.
P4 is a widely used Domain-specific Language for Programmable Data Planes. A critical step in P4 compilation is finding a feasible and efficient mapping of the high-level P4 source code constructs to ...the physical resources exposed by the underlying hardware, while meeting data and control flow dependencies in the program. In this paper, we take a new look at the algorithmic aspects of this problem, with the motivation to understand the fundamental theoretical limits and obtain better P4 pipeline embeddings, and to speed up practical P4 compilation times for RMT and dRMT target architectures. We report mixed results: we find that P4 compilation is computationally hard even in a severely relaxed formulation, and there is no polynomial-time approximation of arbitrary precision (unless =), while the good news is that, despite its inherent complexity, P4 compilation is approximable in linear time with a small constant bound even for the most complex, nearly real-life models.
The current best practice in survivable routing is to compute link or node disjoint paths in the network topology graph. It can protect single-point failures; however, several failure events may ...cause the interruption of multiple network elements. The set of network elements subject to potential failure events is called Shared Risk Link Group (SRLG), identified during network planning. Unfortunately, for any given list of SRLGs, finding two paths that can survive a single SRLG failure is NP-Complete. In this paper, we provide a polynomial-time SRLG-disjoint routing algorithm for planar network topologies and a large set of SRLGs. Namely, we focus on regional failures, where the failed network elements must not be far from each other. We use a flexible definition of regional failure, where the only restrictions are that i) the topology is a planar graph, ii) each SRLG forms a set of connected edges in the dual of the planar graph, and iii) for each node <inline-formula> <tex-math notation="LaTeX">v</tex-math> </inline-formula>, the links incident to <inline-formula> <tex-math notation="LaTeX">v</tex-math> </inline-formula> are part of an SRLG. The proposed algorithm is based on a max-min theorem. Through extensive simulations, we show that the algorithm scales well with the network size, and one of the paths returned by the algorithm is only <inline-formula> <tex-math notation="LaTeX">4</tex-math> </inline-formula>% longer than the shortest path on average.
The Clar number of a (hydro)carbon molecule, introduced by Clar (The aromatic sextet,
1972
), is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number ...can be formulated as an optimization problem on 2-connected plane graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson (Linear Algebra Appl 420(2):441–448,
2007
) that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is
NP
-hard. We also prove
NP
-hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an exact algorithm that determines the Clar number of a given 2-connected plane graph. The algorithm has a polynomial running time if the length of the shortest odd join in the planar dual graph is fixed, which gives an efficient algorithm for some fullerene classes, such as carbon nanotubes.
Many recent studies shed light on the vulnerability of networks against large-scale natural disasters. The corresponding network failures, called regional failures, are manifested at failing multiple ...network elements that are physically close to each other. The recovery mechanisms of current backbone networks protect failures listed as Shared Risk Link Groups (SRLGs). We aim to design an algorithm for the routing engines, which can generate a reasonable list of SRLGs based on the limited geometric information available. As a first step towards this direction, in this paper, we propose a limited geographic information failure model for the network topology that enables efficient algorithms to compute the set of links that are expected to be close to each other. More precisely, we work with (1) relative node positions without knowing the real distances, (2) an area in the map defines the route of each physical cable, and (3) a regional failure is a circular disk with <inline-formula> <tex-math notation="LaTeX">k=0,1, {\dots } </tex-math></inline-formula> nodes in its interior. We describe an efficient algorithm for listing SRLGs based on our limited geographic information failure model and show that under realistic assumptions, the obtained list of SRLGs is short, having approximately <inline-formula> <tex-math notation="LaTeX">1.2 n </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">2.2n </tex-math></inline-formula> elements for <inline-formula> <tex-math notation="LaTeX">k=0 </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">k=1 </tex-math></inline-formula>, respectively, where <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> is the number of nodes of the network.
Directed hypergraphs and Horn minimization Bérczi, Kristóf; Bérczi-Kovács, Erika R.
Information processing letters,
December 2017, 2017-12-00, Volume:
128
Journal Article
Peer reviewed
A Boolean function given in a conjunctive normal form is Horn if every clause contains at most one positive literal, and it is pure Horn if every clause contains exactly one positive literal. Due to ...their computational tractability, Horn functions are studied extensively in many areas of computer science and mathematics such as combinatorics, artificial intelligence, database theory, algebra and logic.
The present paper considers the problem of finding minimal representations of pure Horn functions. We give a new proof for a recent min–max result of Boros et al. regarding body-minimal representations. The proof is algorithmic and finds the so called Guigues–Duquenne basis. We also describe a new construction that combines two existing representations into a third one.
•Graph algorithm for determining a body-minimal representation of a Horn function.•The algorithm finds the Guigues–Duquenne basis of the Horn function.•Horn formulas are represented by directed hypergraphs.
PDF
