Search

We study two problems where k autonomous mobile agents are initially located on distinct nodes of a weighted graph with n nodes and m edges. Each agent has a predefined velocity and can only move along the edges of the graph. The first problem is to deliver one package from a source node to a destination node. The second is to simultaneously deliver two packages, each from its source node to its destination node. These deliveries are achieved by the collective effort of the agents, which can carry and exchange a package among them. For one package, we propose an O ( k n log ⁡ n + k m ) time algorithm for computing a delivery schedule that minimizes the delivery time. For two packages, we show that the problem of minimizing the maximum or the sum of the delivery times is NP-hard for arbitrary agent velocities, but polynomial-time solvable for agents with equal velocity.

Although cloud computing greatly utilises virtualised environments for applications to be executed efficiently in low-cost hosting, it has turned energy wasting and overconsumption issues into major concerns. Cloud infrastructure is built on a great amount of server equipment, including high performance computing (HPC), and the servers are naturally prone to failures.In this paper, we report on an energy optimisation approach for scheduling HPC applications, applied to decentralised clouds system, that takes dataset transmission energy into account. The optimisation supports combining two conflicting objectives: minimising energy consumption in conjunction with the avoidance of application deadline violations caused by resource failures. Furthermore, we propose two decision strategies for weighing these conflicting objectives dynamically to account for their significance towards producing an ideal energy efficiency and resource utilisation. Through our developed simulation and experimental analysis using real parallel workloads from large-scale systems, the results illustrate that our approach provides promising energy savings with acceptable level of resource reliability.

Wireless Mesh Networks (WMNs) are gaining popularity due to the features provided, especially the low cost and self-configuration ability. In WMNs, the data traffic is transmitted through intermediate nodes and a number of packets are dropped during the transmission due to various reasons. One significant reason is the limitation of network resources such as bandwidth and buffer size. Because of these limitations, the network becomes congested under high traffic volumes. Therefore, a large number of packets will be dropped due to buffer overflow in the Interface Queue (IFQ). Hence, controlling the congestion at the IFQ is essential for achieving high throughput. In this paper, we address the node congestion level in multi-channel WMNs and reduce the dropped packets at IFQ by adjusting the traffic rate based on the solution of a linear program (LP). The benefits of these traffic rate adjustments are demonstrated in chain networks using the Network Simulator (NS2). In addition, for complex networks we show that such traffic rate adjustments alone are not sufficient and propose a simple forwarding delay scheme for the Ad Hoc On-Demand Distance Vector protocol with Forwarding delay (AODV-F) that reduces node congestion and improves throughput, which is again demonstrated in simulations with NS2.

We investigate the problem of computing the types of the relationships between Internet Autonomous Systems. We refer to the model introduced by Gao [IEEE/ACM TRANSACTIONS ON NETWORKING, 9(6):733–645, 2001] and Subramanian et al. (IEEE Infocom, 2002) that bases the discovery of such relationships on the analysis of the AS paths extracted from the BGP routing tables. We characterize the time complexity of the above problem, showing both NP-completeness results and efficient algorithms for solving specific cases. Motivated by the hardness of the general problem, we propose approximation algorithms and heuristics based on a novel paradigm and show their effectiveness against publicly available data sets. The experiments provide evidence that our algorithms perform significantly better than state-of-the-art heuristics.

Harmful Internet hijacking incidents put in evidence how fragile the Border Gateway Protocol (BGP) is, which is used to exchange routing information between Autonomous Systems (ASes). As proved by recent research contributions, even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E.g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception., Comment: 17 pages with 6 figures

Wireless mesh networks have emerged as a viable means of communicating between points that are not within wireless range of each other. There are still, however, a number of challenges involved in designing and implementing such wireless multi-hop networks, particularly with respect to optimising the user throughput. This paper presents some preliminary measurements from an experimental multi-hop wireless networking testbed that has been set up using nodes which utilise Chirp Spread Spectrum (CSS) technology. Multi-hop networks with linear topologies and a maximum of 5 static nodes have been considered. Numerous experiments, mostly indoors, have been performed in which parameters such as the network chain length, the packet size, the logical transmit channel and the transmit power of each node have been varied. The performance of a system with two parallel multi-hop chains was also investigated in which the chains operate simultaneously on either the same or different channels. The end-to-end throughput is observed to fall with increasing chain lengths, typically stabilising for longer chains at values approximately equal to 5---15 % of the single-hop throughput. As the size of the payload is increased, a corresponding linear increase in the throughput is observed. The user throughput also increases with increasing transmit powers at each of the nodes in the chain. However, a trade-off must be made if power and throughput are to be optimised simultaneously.

With the features provided by wireless mesh networks (WMN) and the increasing number of users, the Quality of Service (QoS) has become essential to support multimedia applications. In addition, employing the multichannel approach has led to the improvement of the network performance. However, selecting a path with the maximum available bandwidth to transmit data from the source to the destination is a critical issue because of intraflow interference and inter-flow interference. In this paper, we propose a routing metric Delay and Interference Aware Metric (DIAM), which selects a path with high data rate and low signal interference to achieve high performance. The DIAM metric estimates the intra-flow interference, inter-flow interference and delay of a link for multi-channel WMNs. We have implemented DIAM in the AODV routing protocol using the Network Simulator (NS2). The performance of our metric is measured by conducting simulation experiments in static and mobile networks.

The increased computational needs in many sectors place huge demands on cloud computing. Power consumption and resource pool capacity are two of the challenges faced by the next generation of high performance computing (HPC). This paper aims at minimising the computing-energy consumption in decentralised multi-cloud systems using Dynamic Voltage and Frequency Scaling (DVFS) when scheduling dependent HPC tasks under deadline constraints. We propose an energy-aware scheduling algorithm EAGS. To demonstrate the efficiency of our algorithm EAGS, we compare it with the Cloud min-min Scheduling (CMMS) algorithm in different experiments. The simulation results show that our algorithm can produce energy consumption lower than CMMS by an average of 63.9%.

Data collection is one of the predominant operations in wireless sensor networks. This paper focuses on the problem of efficient data collection in a setting where some nodes may not possess data each time data is collected. In that case, idle listening slots may occur, which lead to a waste of energy and an increase in latency. To alleviate these problems, successive-slot schedules were proposed by Zhao and Tang (Infocom 2011). In this paper, we introduce a so-called extra-bit technique to reduce idle listening further. Each packet includes an extra bit that informs the receiver whether further data packets will follow or not. The extra-bit technique leads to significantly reduced idle listening and improved latency in many cases. We prove that every successive-slot schedule is also an extra-bit schedule. We then consider the special case of linear networks and prove that the optimal length of a successive-slot schedule (or extra-bit schedule) is 4N -- 6 time slots, where N a#x2265; 3 is the number of nodes excluding the sink. Then the proposed extra-bit technique is compared with the successive-slot technique with respect to the expected amount of idle listening, and it is shown that the extra-bit technique reduces idle listening substantially.

Compliance with the Gao-Rexford conditions [1] is perhaps the most realistic explanation of Internet routing stability, although BGP is renowned to be prone to oscillations. Informally, the Gao-Rexford conditions assume that (i) the business relationships between Internet Service Providers (ISPs) yield a hierarchy, (ii) each ISP behaves in a rational way, i.e., it does not offer transit to other ISPs for free, and (iii) each ISP ranks routes through customers better than routes through providers and peers.

The use of multi-channel MAC protocols improves the capacity of wireless networks. Efficient multi-channel MAC protocols aim to utilize multiple channels effectively. Our proposed multi-channel MAC protocol called LCV-MMAC effectively utilizes the multiple channels by handling the control channel saturation. LCV-MMAC demonstrates significantly better throughput and fairness compared to DCA, MMAC, and AMCP in different network scenarios.

Due to limited battery life and fault tolerance issues posed by Wireless Sensor Networks (WSNs), efficient methods which ensure reliable coverage are highly desirable. One solution is to use disjoint set covers to cover the targets. We formulate a problem called MDC which addresses the maximum coverage by using disjoint set covers S 1 and S 2. We prove that MDC is \(\mathcal{NP}\)-complete and propose a \(\sqrt{n}\)-approximation algorithm for the MDC problem to cover n targets.

This paper proposes a simple scheme to optimise the end-to-end user throughput of small, multi-hop wireless networks. The scheme which involves the introduction of small delays between successive packet transmissions at the source node has been tested on an indoor wireless mesh testbed for uni-directional flows of data traffic with nodes that use Chirp Spread Spectrum technology. Results from a series of novel experiments confirm the effectiveness of the technique to significantly improve the throughput of multi-hop wireless networks.

This paper presents preliminary results from a simulation-based study of static, wireless multi-hop networks with linear chain topologies supporting the uni-directional flow of data. Chain lengths of up to 10 nodes have been examined. The effects of varying parameters such as the number of nodes, the MAC data rate, the offered load and the packet size have been investigated. In addition, the influence of RTS/CTS handshaking on the throughput performance of such networks has been analysed.

In recent years, wireless mesh networks have emerged as a viable means of communications, not least because of their ease of deployment and cost-effectiveness. There are still, however, a number of challenges involved in designing and implementing such wireless multi-hop networks. This paper describes some of the preliminary work carried out for the development of an experimental mesh testbed employing wireless nodes that utilise chirped spread spectrum technology.

Broadcasting is a fundamental operation underlying different routing, multicasting and address resolution protocols. Broadcasting in a network requires that all the nodes in the network receive the broadcast packet. Mobility in the network induces link failures which cause some nodes to lose the broadcast packets. Objective of all broadcasting protocols is to achieve high reachability while keeping the broadcast redundancy as low as possible. In this paper we propose a cross layer protocol, called cross layer mobility adaptive broadcasting (CMAB) to handle the mobility in mobile ad hoc networks (MANETs). CMAB uses two Disjoint Sets of Broadcast Relay Gateways (BRGs1 and BRG2) to ensure high reliability in case of high mobility. Our approach minimizes broadcast redundancy by activating the second set of BRG2s only in highly mobile scenarios. A further reduction in broadcast redundancy is achieved by forcing the second Disjoint BRG2 to rebroadcast only if it is covering a maximum number of 2-hop neighbors of upstream sender or source to be covered by BRG1. The proposed protocol balances the retransmission redundancy avoiding the broadcast storm problem and increasing reachability in highly mobile and denser network scenarios. Simulation results show that CMAB provides high delivery ratio, low forwarding ratio and low end-to-end delay in highly mobile and denser network scenarios.

If a set K of nodes in a wireless network want to set up a routing structure that allows them to communicate with each other, one possible approach is to use a Steiner tree that spans all the nodes in K. However, a tree can be disconnected by the failure of a single link, and so it is desirable to employ other routing structures that are fault-tolerant. Furthermore, many real-world wireless networks are heterogeneous, meaning that the suitability of nodes for inclusion in the routing structure varies significantly. Therefore, it is meaningful to assign weights to the nodes and aim to compute a fault-tolerant routing structure of minimum total weight. In this paper, we model this problem as the problem of computing a minimum-weight 2-edge-connected Steiner subgraph spanning a given set of terminals, and we propose a constant-factor approximation algorithm for this problem in wireless networks that are modelled as unit disk graphs or quasi unit disk graphs.

The problem of scheduling wireless transmissions under signal to interference-plus-noise ratio (SINR) constraints has received increasing attention recently. While previous work has considered the unicast case where each transmission has one sender and one receiver, we consider the setting of multicast requests where each transmission has one sender and a set of receivers. A set of multicast transmissions can be scheduled in the same round if the SINR at all receivers is above a certain threshold. The goal is to minimise the number of rounds. Building on the relationship between SINR scheduling and unit disk graph colouring established by Halldorsson (ESA 2009), we present an O(log Γ)-approximation algorithm for multicast scheduling in the SINR model, where Γ is the ratio of the longest to the shortest link length, considering only the longest link of each multicast request. The algorithm uses uniform power assignment and can be implemented online. We also compare the model of atomic multicasts (where all receivers of a multicast must receive the transmission in the same round) to the model of splittable multicasts (where a multicast sender can transmit in several rounds, each time serving a subset of its receivers). Furthermore, we consider the throughput maximisation problem and obtain an O(log Γ)-competitive randomised online algorithm and show that every deterministic algorithm, even for unicast links and using arbitrary power assignments, has competitive ratio Ω(log Γ).

Flooding is an obligatory technique to broadcast messages within mobile ad hoc networks (MANETs). Simple flooding mechanisms cause the broadcast storm problem and swamp the network with a high number of unnecessary retransmissions, thus resulting in increased packet collisions and contention. This degrades the network performance enormously. There are several broadcasting schemes that adapt to different network conditions of node density, congestion and mobility.

This paper addresses the problem of exploring the fault tolerance potential of the routing primitive called path splicing. This routing mechanism has been recently introduced in order to improve the reliability level of networks. The idea is to provide for each destination node in a network several different routing trees, called slices, by running different routing protocols simultaneously. The possibility for the traffic to switch between different slices at any hop on the way to the destination makes it possible to achieve a level of reliability that is close to the ideal level achieved by the underlying network. In this work we show that there is a method for computing just two slices that achieves fault tolerance against all single-link failures that do not disconnect the underlying network. We present an experimental evaluation of our approach, showing that for a number of realistic topologies our method of computing the slices achieves the same level of fault tolerance that is achieved by a much larger number of slices using the previously proposed method.

Multicast communication in a wireless ad-hoc network can be established using a tree that spans the multicast sender and receivers as well as other intermediate nodes. If the network is modelled as a graph, the multicast tree is a Steiner tree, the multicast sender and receivers correspond to terminals, and other nodes participating in the tree are Steiner nodes. As Steiner nodes are nodes that participate in the multicast tree by forwarding packets but do not benefit from the multicast, it is a natural objective to compute a tree that minimizes the total cost of the Steiner nodes. We therefore consider the problem of computing, for a given node-weighted graph and a set of terminals, a Steiner tree with Steiner nodes of minimum total weight. For graph classes that admit spanning trees of maximum degree at most d, we obtain a 0.775d-approximation algorithm. We show that this result implies a 3.875-approximation algorithm for unit disk graphs, an O(1/α2)-approximation algorithm for α-unit disk graphs, and an O(λ)-approximation algorithm for (λ + 1)-claw-free graphs.

A virtual private network (VPN) provides private network connections over a publicly accessible shared network. Bandwidth provisioning for VPNs leads to challenging optimization problems. In the hose model proposed by Duffield et al., each VPN endpoint specifies bounds on the total amount of traffic that it will send or receive at any time. The network provider must provision the VPN so that there is sufficient bandwidth for any traffic matrix that is consistent with these bounds. While previous work has considered tree routing and single-path routing between the VPN endpoints, we demonstrate that the use of multipath routing offers significant advantages. On the one band, we present an optimal polynomial-time algorithm that computes a bandwidth reservation of minimum cost using multi-path routing. This is in contrast to tree routing and single-path routing, where the problem is computationally hard. On the other hand, we present experimental results showing that the reservation cost using multi-path routing can indeed be significantly smaller than with tree or single-path routing.

The topology of the Internet has initially been modelled as an undirected graph, where vertices correspond to so-called Autonomous Systems (ASs), and edges correspond to physical links between pairs of ASs. However, in order to capture the impact of routing policies, it has recently become apparent that one needs to classify the edges according to the existing economic relationships (customer-provider, peer-to-peer or siblings) between the ASs. This leads to a directed graph model in which traffic can be sent only along so-called valley-free paths. Four different algorithms have been proposed in the literature for inferring AS relationships using publicly available data from routing tables. We investigate the differences in the graph models produced by these algorithms, focussing on connectivity measures. To this aim, we compute the maximum number of vertex-disjoint valley-free paths between ASs as well as the size of a minimum cut separating a pair of ASs. Although these problems are solvable in polynomial time for ordinary graphs, they are NP-hard in our setting. We formulate the two problems as integer programs, and we propose a number of exact algorithms for solving them. For the problem of finding the maximum number of vertex-disjoint paths, we discuss two algorithms; the first one is a branch-and-price algorithm based on the IP formulation, and the second algorithm is a non LP based branch-and-bound algorithm. For the problem of finding minimum cuts we use a branch-and-cut algorithm, based on the IP formulation of this problem. Using these algorithms, we obtain exact solutions for both problems in reasonable time. It turns out that there is a large gap in terms of the connectivity measures between the undirected and directed models. This nding supports our conclusion that economic relationships need to be taken into account when building a topology of the Internet.

A common approach for establishing connection requests in an optical ring network that uses wavelength-division multiplexing is to first find a routing of the requests that minimizes the congestion and then deal with the wavelength allocation. The congestion of a routing, however, does not reflect its wavelength requirements. Indeed, we observe that for certain instances such an approach can result in considerable waste of network resources. To overcome this, we propose a new routing objective, namely to minimize the maximum clique of the routing, i.e., the maximum number of connections that pairwise share a common fiber. We present optimal algorithms and heuristics for finding minimum clique routings and perform experiments to evaluate their performance.

Consider a scenario where radio base stations need to send data to users with wireless devices. Time is discrete and slotted into synchronous rounds. Transmitting a data item from a base station to a user takes one round. A user can receive the data item from any of the base stations. The positions of the base stations and users are modeled as points in Euclidean space. If base station b transmits to user u in a certain round, no other user within distance at most kb, Technical report, 462

The Internet AS (Autonomous System) topology structure is a subject of high interest as performance of Internet protocols and algorithms can depend heavily on the topology. Besides other reasons, a good model for the Internet topology may lead to a realistic generator, used for simulations. Power-law degree Internet topology generators, now state-of-the-art, result in different kinds of graphs. It has already been observed that power-law distribution creates hierarchy, although the type of hierarchy differs from model to model. Also, one should take into account the influence of BGP policies by considering them as part of the AS topology model. We looked at the real and generated Internet Topology in order to find relevant and computationally simple metrics to evaluate differences. Preliminary results using the Normalized Laplacian Spectrum, which can be calculated in polynomial time, show that it is a good candidate to differentiate classes of topologies. Some of the questions we are interested in are: – What can we conclude about topology from the normalized spectrum of the graph? Preliminary results: Observation of the difference between the multiplicities of the eigenvalue 1 in the Normalized Laplacian Spectrum of graphs created by Inet 2 (Inet Topology Generator, University of Michigan) and of corresponding AS graphs lead us to a new hierarchical representation of the AS graph. We partition the graph into 4 components: P, Q, R and I. Taking into account BGP policies, we confirmed our conclusions about the functionality of each component (roughly, the edge and

Many real-time embedded systems involve a collection of independently executing event-driven code blocks, having hard real-time constraints. Tasks in many such systems, like network processors, are either not preemptable or have restrictions on the number of preemptions allowed. All the previous work on theschedulability analysis of such systems either have exponential complexity, or allow unbounded number of preemptions and are usually based on heuristics. In this paper we present the exact necessary and sufficient conditions under EDF, for the schedulability of such a collection of code blocks in a non-preemptive environment, and give efficient algorithms for testing them. For fixed priority schedulers we give a sufficient condition. We validate our analytical results with experiments and show that the schedulability analysis problem in such systems can be exactly and efficiently solved in practice., TIK Report, 130