Two Heuristics for Calculating a Shared Risk Link Group Disjoint Set of Paths of Min-Sum Cost

A shared risk link group (SRLG) is a set of links which share a common risk of failure. Routing protocols in Generalized MultiProtocol Label Switching, using distributed SRLG information, can calculate paths avoiding certain SRLGs. For single SRLG failure an end-to-end SRLG-disjoint path pair can be calculated, but to ensure connection in the event of multiple SRLG failures a set with more than two end-to-end SRLG-disjoint paths should be used. Two heuristic, the Conflicting SRLG-Exclusion Min Sum (CoSE-MS) and the Iterative Modified Suurballes’s Heuristic (IMSH), for calculating node and SRLG-disjoint path pairs, which use the Modified Suurballes’s Heuristic, are reviewed and new versions (CoSE-MScd and IMSHd) are proposed, which may improve the number of obtained optimal solutions. Moreover two new heuristics are proposed: kCoSE-MScd and kIMSHd, to calculate a set of \(k\) node and SRLG-disjoint paths, seeking to minimize its total cost. To the best of our knowledge these heuristics are a first proposal for seeking a set of \(k\, (k>2)\) node and SRLG-disjoint paths of minimal additive cost. The performance of the proposed heuristics is evaluated using a real network structure, where SRLGs were randomly defined. The number of solutions found, the percentage of optimal solutions and the relative error of the sub-optimal solutions are presented. Also the CPU time for solving the problem in a path computation element is reported.     

The General Steiner Tree-Star problem

The Steiner tree problem is defined as follows—given a graph G=(V,E) and a subset X⊂V of terminals, compute a minimum cost tree that includes all nodes in X. Furthermore, it is reasonable to assume that the edge costs form a metric. This problem is NP-hard and has been the study of many heuristics and algorithms. We study a generalization of this problem, where there is a “switch” cost in addition to the cost of the edges. Switches are placed at internal nodes of the tree (essentially, we may assume that all non-leaf nodes of the Steiner tree have a switch). The cost for placing a switch may vary from node to node. A restricted version of this problem, where the terminal set X cannot be connected to each other directly but only via the Steiner nodes V?X, is referred to as the Steiner Tree-Star problem. The General Steiner Tree-Star problem does not require the terminal set and Steiner node set to be disjoint. This generalized problem can be reduced to the node weighted Steiner tree problem, for which algorithms with performance guarantees of Θ(lnn) are known. However, such approach does not make use of the fact that the edge costs form a metric. In this paper we derive approximation algorithms with small constant factors for this problem. We show two different polynomial time algorithms with approximation factors of 5.16 and 5.     

Dynamic backup routes routing protocol for mobile ad hoc networks

Mobile Ad Hoc Networks (MANETs), which provide data networking without infrastructure, represent one kind of wireless networks. A MANET is a self-organizating and adaptive wireless network formed by the dynamic gathering of mobile nodes. Due to the mobility of mobile nodes, the topology of a MANET frequently changes and thus results in the disability of originally on-the-fly data transmission routes. The dynamic properties of MANETs are therefore challenging to protocol design. To cope with the intrinsic properties of MANETs, Dynamic Backup Routes Routing Protocol (DBR²P), a backup node mechanism for quick reconnection during link failures, is proposed in this paper. DBR²P is an on-demand routing protocol and it can set up many routes to reach a destination node in a given period. Even when a link fails, those routes from the source node to the destination node can be analyzed to obtain backup routes to sustain quick reconnection. The information of backup routes can be saved in a specific on-the-route node and enables backup routes to be found immediately in situation regarding disconnection. As a result, DBR²P could more thoroughly improve the quality of routing protocol than those proposed in the past.     

Finding reliable subgraphs from large probabilistic graphs

Reliable subgraphs can be used, for example, to find and rank nontrivial links between given vertices, to concisely visualize large graphs, or to reduce the size of input for computationally demanding graph algorithms. We propose two new heuristics for solving the most reliable subgraph extraction problem on large, undirected probabilistic graphs. Such a problem is specified by a probabilistic graph G subject to random edge failures, a set of terminal vertices, and an integer K. The objective is to remove K edges from G such that the probability of connecting the terminals in the remaining subgraph is maximized. We provide some technical details and a rough analysis of the proposed algorithms. The practical performance of the methods is evaluated on real probabilistic graphs from the biological domain. The results indicate that the methods scale much better to large input graphs, both computationally and in terms of the quality of the result.     

How do we encourage an egoist to act socially in an ad hoc mobile network?

We consider a flow-based model for an ad hoc mobile network where users may need to use transit nodes in order to be able to communicate. Under the assumption that every node is willing to cooperate, we derive the set of Karush–Kuhn–Tucker equations that define the socially-optimal flows on each of the routes. We then look at the problem from an ‘egoist’ point of view, in which the user at node i cares only about maximising his/her utility under the constraint that the flows on routes which do not use node i are fixed at the socially-optimal value.This leads us to a consideration of extra constraints that could be introduced to induce the egoist user at node i to behave in a socially-optimal way. We show how to derive the parameters of such constraints, and give them interpretations in terms of schemes in which nodes’ transmission rates are constrained by the rates at which they accumulate ‘credit’.     

Approaching neighbor proximity and load balance for range query in P2P networks

We present a platform for building a range-queriable system. A distinguishing characteristic of the platform is that objects are not bound to any particular node. Rather, they can be freely moved between neighboring nodes to balance load as long as some ordering between objects in different nodes is respected. Decoupling the link between nodes and objects allows the overlay network to be constructed independently of object placement, focusing only on its own concerns, e.g. proximity and balanced load in routing. The main focus then is to present several heuristics for proximity-aware node joining to reduce communication costs in the platform. These heuristics are based on a novel process called hierarchical neighborhood search, which utilizes the overlay links to provide incoming nodes an overview of the network topology, thereby to guide them to find their neighborhood in the overlay. The experimental results show that some of the heuristics are very effective; they can reduce as much as 80% of the communication costs for neighboring nodes, and 40% overall.     

A system for the design of packet-switched communication networks with economic tradeoffs

This paper studies the problem of designing a packet-switched communication network with tradeoffs between link costs and response time to users. It consists of assigning capacities to links in the network and determining the routes used by messages for all communicating node pairs in order to minimize total link fixed and variable costs. A tradeoff between link costs and response time to users is achieved by including a constraint that sets an upper limit on the average link queueing delay in the network. The topology of the network and the end-to-end traffic requirements are given. The problem is formulated as a nonlinear integer programming model. Unlike most of previous models, where the best route for a communicating node pair is restricted to a set of prespecified candidate routes, our model considers all possible routes for every communicating node pair. An efficient heuristic based on a Lagrangean relaxation of the problem is developed to generate feasible solutions. The results of extensive computational experiments across a variety of previously used networks are reported. These results indicate that the solution procedure is effective for a wide range of traffic loads and cost structures.     

Strategies for utility maximization in social groups with preferential exploration

Social Group is group of interconnected nodes interested in obtaining common content (Scott, in Social network analysis, 2012). Social groups are observed in many networks for example, cellular network assisted Device-to-Device network (Fodor et al., in IEEE Commun Mag 50:170–177, 2012, Lei et al., in Wirel Commun 19:96–104, 2012), hybrid Peer-to-Peer content distribution (Christos Gkantsidis and Miller, in 5th International Workshop on Peer-to-Peer Systems, 2006, Vakali and Pallis, in IEEE Internet Comput 7:68–74, 2003) etc. In this paper, we consider a “Social Group” of networked nodes, seeking a “universe” of data segments for maximizing their individual utilities. Each node in social group has a subset of the universe, and access to an expensive link for downloading data. Nodes can also acquire the universe by exchanging copies of data segments among themselves, at low cost, using inter-node links. While exchanges over inter-node links ensure minimum or negligible cost, some nodes in the group try to exploit the system by indulging in collusion, identity fraud etc. We term such nodes as ‘non-reciprocating nodes’ and prohibit such behavior by proposing the “Give-and-Take” criterion, where exchange is allowed iff each participating node provides at least one segment to the node which is unavailable with the node. While complying with this criterion, each node wants to maximize its utility, which depends on the node’s segment set available with the node. Link activation between pair of nodes requires mutual consent of the participating nodes. Each node tries to find a pairing partner by preferentially exploring nodes for link formation. Unpaired nodes download data segments using the expensive link with pre-defined probability (defined as segment aggressiveness probability). We present various linear complexity decentralized algorithms based on the Stable Roommates Problem that can be used by nodes for choosing the best strategy based on available information. We present a decentralized randomized algorithm that is asymptotically optimal in the number of nodes. We define Price of Choice for benchmarking the performance of social groups consisting of non-aggressive nodes (i.e. nodes not downloading data segments from the expensive link) only. We evaluate performances of various algorithms and characterize the behavioral regime that will yield best results for nodes and social groups, spending the least on the expensive link. The proposed algorithms are compared with the optimal. We find that the Link For Sure algorithm performs nearly optimally.     

Topological network design: A survey

We consider the problem of topological optimization of communication networks subject to a number of design constraints, such as maximum network diameter, maximum node degree, k-node (link) survivability, and network fault tolerance. The primary design problem can be described as follows: Given a set of network nodes, it is required to find a topology Ψ, selected from all possible topologies, so that the cost of Ψ (measured possibly in terms of the maximum diameter, maximum node degree, etc.) is less than that of any other network topology and such that Ψ satisfies some given design constraints. Fault tolerance is concerned with the ability of the network nodes to communicate in the presence of a set of faulty links and/or nodes. The network design problem considering reliability constraints is NP-hard. We classify the research efforts presented in the literature for solving the topological optimization design problem as hierarchical, enumerative, or iterative techniques. In this paper, we provide a survey of the topological network design techniques under different design constraints. Experimental results obtained by applying a number of algorithms to a set of randomly generated networks are presented and compared.     

Heuristic methods for the identical parallel machine flowtime problem with set-up times

We consider the scheduling of N jobs divided into G families for processing on M identical parallel machines. No set-up is necessary between jobs belonging to the same family. A set-up must be scheduled when switching from the processing of family i jobs to those of another family j, i≠j, the duration of this set-up being the sequence-independent set-up time s_j for family j. We propose heuristics for this problem and computationally evaluate the performance of the heuristics relative to lower bounds and solutions obtained using an exact algorithm.Scope and purposeWe study a machine-scheduling problem within which we have identical parallel machines, jobs arranged into families, and sequence-independent set-up times between jobs of different families on these machines. Our purpose is to develop simple, effective and efficient heuristics for this problem, and we seek to maximise the use of ideas and algorithms that have appeared previously in the literature for related problems. In our computational experiments, we seek to study the behaviour of these heuristics and uncover relevant properties of the scheduling problem. Within this experiment, we compare the observed performance of the heuristics relative to lower bounds and optimal solutions.     

An Optimal Fault-Tolerant Nonredundant Broadcasting Scheme in Injured Hypercubes

We propose a nonredundant broadcasting scheme for injured hypercube multicomputers with direct-connection capability, that is, where each hypercube node has a separate router. The proposed scheme is first presented to cover faulty links only. Under the assumption that no more than n − 1 faulty links exist in an injured n-cube, the proposed scheme is optimal in the sense that it generates a spanning binomial tree from a given node whenever there exists such a tree originated from that node. The scheme is also extended to cover both node and link faults. Although the extended scheme is no longer optimal, we show that by using the extended scheme the maximum number of routing steps required from the source node s to any other node a is H(s, a) + 2, where H stands for the Hamming distance. The proposed scheme uses global network information. Evaluation studies show that the proposed scheme achieves optimal broadcasting a high percentage of times.     

iMST: A bandwidth-guaranteed topology control algorithm for TDMA-based ad hoc networks with sectorized antennas

Many topology control algorithms aim to minimize energy consumption, interference, etc. while maintaining connectivity among the nodes. Links are realized between nodes by proper adjustment of transmission power in each node. However, a link is not useful if its bandwidth is lower than what is required by the applications it supports. Therefore, topology control algorithms should also consider the minimum realizable link bandwidth when generating topologies. As the realizable bandwidth of a link depends on the amount of interference received, interference analysis must be carried out. We study the minimum realizable link bandwidth of a given network under a TDMA/TDD channel sharing mechanism. We carried out the interference analysis assuming the general multi-sectored antenna configuration, since an omni-directional antenna can be visualized as a special configuration of a sectorized antenna (i.e. with 1 sector). We then proceed to derive the transmission power to be used in each sector of all nodes in the network to maximize average channel utilization. However, a brute-force method that runs through all possible topologies takes exponential time.We thus propose an algorithm, iMST, that attempts to maximize average channel utilization by reducing interference. The iMST algorithm not only generates k-edge-connected networks, but also guarantees minimum link bandwidth. Although iMST requires global knowledge of the locations of nodes, by using a distributed MST generation method, iMST can be run in a distributed manner. The iMST scheme is evaluated and compared against a modified Fault-tolerant Cone-Based Topology Control (FCBTC) scheme, referred to as s-FCBTC, that works with sectorized antennas, on a few performance metrics: average channel utilization, network diameter, minimum link bandwidth and edge-connectedness, where edge-connectedness is a new metric defined in this paper. The iMST scheme is shown to exhibit good performance in many of these performance metrics.     

Dynamic distributed unicast routing: optimal incremental paths

Developing new mathematical frameworks such as distributed dynamic routing algorithms for constructing optimal incremental paths from a node to another node is an important challenge in data communication networks. These new algorithms can model network resources optimally and increase network performances. A bundle of single routes in a current communication path, which starts from a source node and ends to a destination node, can consist of several successive nodes and links. The Incremental term emphasizes that the number of routes (links and nodes) in a current path can change so that achieving more data rate and optimal efficiency in the network. In this paper, our problem is to add/omit some routes consisting of some nodes and links to/from the current unicast path dynamically and optimally. We call this problem the Optimal Dynamic Distributed Unicast Routing (ODDUR) problem and it is a NP-complete problem. This problem can be formulated as a new type of Linear Programming Problem (LPP) for finding a minimum cost multichannel unicast path, which this path will minimize end-to-end delay and bandwidth consumption along the routes from the source node to the destination node. In this paper, at first a new mathematical framework will be constructed and then this framework will propose the new optimal dynamic distributed unicast routing algorithm for solving our LPP problem. This algorithm will compute an optimal solution for our LPP based on the simplex method and postoptimality computations and will reduce computations and consumed time. Simulation results will show that our new algorithm is more efficient than other available algorithms in terms of utilization of bandwidths and data rate.     

Shortest Paths in Time-Dependent FIFO Networks

In this paper, we study the time-dependent shortest paths problem for two types of time-dependent FIFO networks. First, we consider networks where the availability of links, given by a set of disjoint time intervals for each link, changes over time. Here, each interval is assigned a non-negative real value which represents the travel time on the link during the corresponding interval. The resulting shortest path problem is the time-dependent shortest path problem for availability intervals ( $\mathcal{TDSP}_{\mathrm{int}}$ ), which asks to compute all shortest paths to any (or all) destination node(s) d for all possible start times at a given source node s. Second, we study time-dependent networks where the cost of using a link is given by a non-decreasing piece-wise linear function of a real-valued argument. Here, each piece-wise linear function represents the travel time on the link based on the time when the link is used. The resulting shortest paths problem is the time-dependent shortest path problem for piece-wise linear functions ( $\mathcal{TDSP}_{\mathrm{lin}}$ ) which asks to compute, for a given source node s and destination d, the shortest paths from s to d, for all possible starting times. We present an algorithm for the $\mathcal{TDSP}_{\mathrm{lin}}$ problem that runs in time O((F _d +γ)(|E|+|V|log?|V|)) where F _d is the output size (i.e., number of linear pieces needed to represent the earliest arrival time function to d) and γ is the input size (i.e., number of linear pieces needed to represent the local earliest arrival time functions for all links in the network). We then solve the $\mathcal{TDSP}_{\mathrm{int}}$ problem in O(λ(|E|+|V|log?|V|)) time by reducing it to an instance of the $\mathcal{TDSP}_{\mathrm{lin}}$ problem. Here, λ denotes the total number of availability intervals in the entire network. Both methods improve significantly on the previously known algorithms.     

Series-parallel orientations preserving the cycle-radius

Let G be an undirected 2-edge connected graph with nonnegative edge weights and a distinguished vertex z. For every node consider the shortest cycle containing this node and z in G. The cycle-radius of G is the maximum length of a cycle in this set. Let H be a directed graph obtained by directing the edges of G. The cycle-radius of H is similarly defined except that cycles are replaced by directed closed walks. We prove that there exists for every nonnegative edge weight function an orientation H of G whose cycle-radius equals that of G if and only if G is series-parallel.     

Broadbutton Node Linking — A Generalised Approach to Hyperbase Navigation

Hypertext systems operate by establishing links within information, Links are normally established by an author, although some systems — GUIDE, for example — make little distinction between author and user, permitting deliberate modification of existing connections. However, linking between nodes, whether by original author or later user, is typically an active process. Producing effective hypertext links involves knowledge both of the system and of the particular data set within it.

I suggest that efficient link building might be greatly facilitated, and existing systems given greater functionality, if two related modifications could be made. Firstly, more general or ‘broad-button’ nodal links could be created; I use the phrase ‘broad button’ linking to describe ranked connections established between areas of a hyperbase. The term is defined in detail below. Intended to be easily selectable, broad-button links would offer users the choice of a ranked list of destinations from any point within any node. Secondly, were nodes to be ranked in order of probable user choice, allowing users a degree of feedback following selection of a node would permit such ranking to be dynamically organised. Feedback of this kind also has potential in assisting automatic establishment of appropriate new links between nodes.

In this paper I describe how such modifications might be organised, and describe some experiments which are currently being planned and undertaken to evaluate the ‘broad-button linking’ process.     

Preferred link based delay-constrained least-cost routing in wide area networks

Multimedia applications involving digital audio and/or digital video transmissions require strict QoS constraints (end-to-end delay bound, bandwidth availability, packet loss rate, etc.) to be met by the network. To guarantee the real-time delivery of packets satisfying these constraints, a real-time channel (D. Ferrari and D.C. Verma, A scheme for real-time channel establishment in wide-area networks. IEEE JSAC, 8(3), 368–379, 1990) needs to be established before the transmission of packets of a connection can begin. The establishment of such channels requires the development of efficient route selection algorithms that are designed to take into account the QoS constraints.

The general problem of determining a least-cost delay-constrained route in a given communication network has been proved to be NP-hard (M.R. Garey and D.S. Johnson, Computers and Intractability: a guide to the theory of NP-completeness, W.H. Freeman, 1979). In this paper, we describe a preferred link approach to distributed delay-constrained least-cost routing in order to establish real-time channels. The approach attempts to combine the benefits of probing and backtracking based algorithms (better adaptiveness and wider search) with the advantages of distance-vector type algorithms (lower setup time). The scheme is flexible in that a variety of heuristics can be employed to order the neighbouring links of any given node. Three heuristics are proposed and their performance is studied through simulation experiments. The simulation results indicate that the proposed heuristics provide better performance than other preferred neighbour methods, in terms of increased call acceptance rate and lower average route cost. The heuristics are also shown to adapt much better to dynamic variations in network and link characteristics.     

Fault-Tolerant Permutation Routing in Hypercubes

This paper introduces a deterministic mechanism for fault-tolerant permutation routing on an n-cube with less than n processor and/or link faults, using O(n) steps and constant queue size. The basic approach is to modify an existing route of a given permutation to avoid the faulty processors and/or faulty links, yet only incurring a constant factor slowdown in communication by ensuring that, at each step of the routing, every message either stays where it is or is sent to a nonfaulty neighbor, each link has at most one message traversing it in each direction, and the routing uses constant queue size. The existing route used in this paper is Benes routes. However, our method can be applied to any routing method where, in each step, all messages use links across the same dimension. The same approach can also be applied to online routing based on Batcher′s bitonic sorting to avoid faults.     

A Generalization of the Convex Kakeya Problem

Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be seen as a generalization of Kakeya’s problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Θ(nlogn)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G.     

The structure and complexity of Nash equilibria for a selfish routing game

In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m$m$ parallel links. We assume a collection of n$n$ users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of her own traffic. In a Nash equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link.