Self-Adjusting Networks (SAN) optimize their physical topology toward the demand in an online manner. Their application in data center networks is motivated by emerging hardware technologies, such as 3D MEMS Optical Circuit Switches (OCS). The Matching Model (MM) has been introduced to study the hybrid architecture of such networks. It abstracts from the electrical switches and focuses on the added (reconfigurable) optical ones. MM defines any SAN topology as a union of matchings over a set of top-of-rack (ToR) nodes, and assumes that rearranging the edges of a single matching comes at a fixed cost. In this work, we propose and study the Scalable Matching Model (SMM), a generalization of the MM, and present OpticNet, a framework that maps a set of ToRs to a set of OCSs to form a SAN topology. We prove that OpticNet uses the minimum number of switches to realize any bounded-degree topology and allows existing SAN algorithms to run on top of it, while preserving amortized performance guarantees. Our experimental results based on real workloads show that OpticNet is a flexible and efficient framework for the implementation and evaluation of SAN algorithms in reconfigurable data center environments.

51

The performance of many data-centric cloud applications critically depends on the performance of the underlying datacenter network. Reconfigurable optical technologies have recently introduced a novel opportunity to improve datacenter network performance, by allowing to dynamically adjust the network topology according to the demand. However, the vision of self-adjusting networks raises the fundamental question how such networks can be efficiently operated in a scalable and distributed manner. This article presents$DiSplayNet$, the first fully distributed self-adjusting network.$DiSplayNet$relies on algorithms that perform decentralized and concurrent topological adjustments to account for changes in the demand. We propose two natural metrics to evaluate the performance of distributed self-adjusting networks, theamortized work(the cost of routing on and adjusting the network) and themakespan(the time it takes to serve a set of communication requests). We present a rigorous formal analysis of the work and makespan of$DiSplayNet$, which can be seen as an interesting generalization of analyses known from sequential self-adjusting datastructures. We complement our theoretical contribution with an extensive trace-driven simulation study, shedding light on the opportunities and limitations of leveraging spatial and temporal locality and concurrency in self-adjusting networks.

This paper studies the design of demand-aware network topologies: networks that dynamically adapt themselves toward the demand they currently serve, in an online manner. While demand-aware networks may be significantly more efficient than demand-oblivious networks, frequent adjustments are still costly. Furthermore, a centralized controller of such networks may become a bottleneck.We present CBNet (Counting-Based self-adjusting Network), a demand-aware network that relies on a distributed control plane supporting concurrent adjustments, while significantly reducing the number of reconfigurations, compared to related work. CBNet comes with formal guarantees and is based on concepts of self-adjusting data structures. We evaluate CBNet analytically and empirically and we find that CBNet can effectively exploit locality structure in the traffic demand.

We consider the problem of designing dynamic network topologies that self-adjust to the (possibly changing) traffic pattern they serve. Such demand-aware networks currently receive much attention, especially in the context of datacenters, due to emerging technologies supporting the fast reconfiguration of the physical topology. We present the first fully distributed, provably efficient self-adjusting network. Our network called DiSptayNet relies on algorithms that perform decentralized and concurrent topological adjustments to account for changes in the demand. We present a rigorous formal analysis of the correctness and performance of DiSptayNet, which can be seen as an interesting generalization of analyses known from sequential self-adjusting datastructures. We also report on results from extensive trace-driven simulations.

SplayNets are reconfigurable networks which adjust to the communication pattern over time. We present DiSplayNets, a distributed (concurrent and decentralized) implementation of SplayNets.

In this paper we build and characterize a large-scale dataset of internet radio streams. More than 25 million snapshots of more than 75 thousand different radio stations were collected from the SHOUTcast service between December 2016 and April 2017. We characterized several attributes of the dataset, such as audience and music genre distributions among radio stations, advertisement and seasonal content dynamics, as well as bit rates and media formats of the radio streams. Finally, we analyzed to which extent these features affect audience size. We hope these and the other findings of our study may provide valuable information for content personalization and better advertisement placement in internet radio streams.

In this work, we explore the increasing demand for novel user interfaces to navigate large media collections. We implement a geometric data structure to store and retrieve item-to-item similarity information and propose a novel navigation framework that uses vector operations and real-time user feedback to direct the outcome. The framework is scalable to large media collections and is suitable for computationally constrained devices. In particular, we implement this framework in the domain of music. To evaluate the effectiveness of the navigation process, we propose an automatic evaluation framework, based on synthetic user profiles, which allows us to quickly simulate and compare navigation paths using different algorithms and datasets. Moreover, we perform a real user study. To do that, we developed and launched Mixtape , a simple web application that allows users to create playlists by providing real-time feedback through liking and skipping patterns.

Standard routing protocols for IPv6 over Low power Wireless Personal Area Networks (6LoWPAN) are mainly designed for data collection applications and work by establishing a tree-based network topology, which enables packets to be sent upwards, from the leaves to the root, adapting to dynamics of low-power communication links. The routing tables in such unidirectional networks are very simple and small since each node just needs to maintain the address of its parent in the tree, providing the best-quality route at every moment. In this work, we propose Matrix, a platform-independent routing protocol that utilizes the existing tree structure of the network to enable reliable and efficient any-to-any data traffic. Matrix uses hierarchical IPv6 address assignment in order to optimize routing table size, while preserving bidirectional routing. Moreover, it uses a local broadcast mechanism to forward messages to the right subtree when persistent node or link failures occur. We implemented Matrix on TinyOS and evaluated its performance both analytically and through simulations on TOSSIM. Our results show that the proposed protocol is superior to available protocols for 6LoWPAN, when it comes to any-to-any data communication, in terms of reliability, message efficiency, and memory footprint.

Motivated by studies of wireless ad hoc networks in obstructed environments, in this work we focus on the problem of establishing connectivity at an intersection of two roads, or streets, surrounded by obstacles. An instance of the problem is defined by four street segments meeting at an intersection point, a street width, a node density at each street segment and a transmission range of the communication nodes. The problem that we focus on consists in computing the probability that there is a communication path connecting all four intersecting street segments. We propose a simplified model that approximates the connectivity properties in this setting and compute a lower bound for the connectivity probability. We compare our result to a Euclidean Line-of-Sight (LoS) model and show that our model provides an accurate approximation, while greatly simplifying the analytical treatment.

In this paper, we address two basic questions in wireless communication. First, how long does it take to schedule an arbitrary set of communication requests? Second, given a set of communication requests, how many of them can be scheduled concurrently? Our results are derived in the signal-to-interference-plus-noise ratio (SINR) interference model with geometric path loss and consist of efficient algorithms that find a constant approximation for the second problem and a logarithmic approximation for the first problem. In addition, we show that the interference model is robust to various factors that can influence the signal attenuation. More specifically, we prove that as long as influences on the signal attenuation are constant, they affect the capacity only by a constant factor.

In this work, we analyze an alternative model for obstructed wireless networks. The model is based on a grid structure of one-dimensional street segments and two-dimensional street intersections. This structure provides a realistic representation of a variety of network scenarios with obstacles and, at the same time, allows a simple enough analysis, which is partly based on percolation theory and partly based on geometric properties. We propose three different ways of modeling the geometric part of the network and derive analytical bounds for the connectivity probability and the critical transmission range for connectivity in the network. Finally, we present extensive simulations that demonstrate that our analytical results provide good approximations, especially for high density scenarios.

Despite great effort from the research community, wireless networks still operate below full capacity. To increase the network throughput it is important to study algorithms that select communication requests that can decode their signals despite mutual interference. In this paper, we study the joint problem of data rate assignment and link scheduling in the physical interference model. The objective of the problem is to maximize the total number of bits transmitted in one time slot. By constructing an intermediate network representation through a disk graph, we prove that a constant approximation solution can be computed in polynomial time. Finally, we propose a parallel implementation of a polynomial-time approximation scheme and show through simulations that the one-slot throughput of a wireless network can be significantly improved by using variable data rates.

In this paper we study the problem of scheduling wireless links in a model where successive interference cancellation is combined with the traditional physical interference model. Successive interference cancellation is based on the observation that interfering signals should not be treated as random noise, but as well-structured signals. By exploiting this structured nature, the strongest signal can be decoded and subtracted from a collision, thus enabling the decoding of weaker simultaneous signals. The procedure can be repeated iteratively as long as the collided signals differ in strength significantly. It has been shown that the problem of scheduling wireless links with successive interference cancellation is NP-hard. In this work, we propose a polynomial-time scheduling algorithm that uses successive interference cancellation to compute short schedules for network topologies formed by nodes arbitrarily distributed in the Euclidean plane. We prove that the proposed algorithm is correct in the physical interference model and provide simulation results demonstrating the performance of the algorithm in different network topologies. We compare the results to solutions without successive interference cancellation and observe that throughput gains of up to 20% are obtained in certain scenarios.

Wireless communication technology offers multi-rate transmission capability which allows to increase the network's throughput. Nevertheless, previous algorithmic results have focused on single-rate radios. In this paper, we study the problem of scheduling multi-rate wireless requests considering the physical interference model. The objective of the problem is to select a subset of communication requests such that the sum of their data rates is maximized and no collisions occur if they are all scheduled simultaneously. We show that, under certain constraints on the input, the problem can be approximated by a graph-based model. More specifically, if network nodes live in a two-dimensional Euclidean space, where the path loss exponent is strictly larger than two, and if data rates and sender-receiver distances can only differ by a contact factor between communication requests, the problem can be modeled as a disk graph. This means that, despite the global nature of the physical interference model, conflicts between simultaneous requests can be restricted to the local neighborhood of the transmitting nodes. We show how to build the corresponding disk graph instances and prove that a weighted maximum independent set in this graph-based model provides a constant-factor approximation to the multi-rate scheduling problem in the physical interference model. Moreover, we implement a polynomial-time approximation scheme algorithm to obtain solutions that are within an arbitrarily small factor of being optimal in the disk graph model.

Connectivity properties of wireless networks in open space are typically modeled using geometric random graphs and have been analyzed in depth in different studies. Such scenarios, however, do not often represent situations encountered in practice, like urban environments or indoor spaces, which are deeply affected by obstacles. In this work, we present a model for obstructed wireless ad hoc networks consisting of a set of n nodes, deployed at random in a lattice square of size g×g, with a common transmission range r. For positioning the nodes in the field, all segments are considered as one-dimensional, but for communication purposes, we add a parameter µ to model the segments' width. Our model can be used to study the structure of obstructed networks analytically, as well as to simulate and evaluate a variety of node deployment strategies and the resulting network topologies. We derive analytical forms for the probability of existing crossing links between parallel and perpendicular segments sharing an intersection, toward a first topological characterization of our model. Moreover, we compute a lower bound for the probability of connectivity at intersections between segments, and apply percolation theory to derivate the Critical Transmission Range for connectivity in the overall network, i.e., the minimum transmission range that generates communication graphs that are connected with high probability.

In this work we study the problem of determining the throughput capacity of a wireless network. We propose a scheduling algorithm to achieve this capacity within an approximation factor. Our analysis is performed in the physical interference model, where nodes are arbitrarily distributed in Euclidean space. We consider the problem separately from the routing problem and the power control problem, i.e., all requests are single-hop, and all nodes transmit at a fixed power level. The existing solutions to this problem have either concentrated on special-case topologies, or presented optimality guarantees which become arbitrarily bad (linear in the number of nodes) depending on the network's topology. We propose the first scheduling algorithm with approximation guarantee independent of the topology of the network. The algorithm has a constant approximation guarantee for the problem of maximizing the number of links scheduled in one time-slot. Furthermore, we obtain a O(log n) approximation for the problem of minimizing the number of time slots needed to schedule a given set of requests. Simulation results indicate that our algorithm does not only have an exponentially better approximation ratio in theory, but also achieves superior performance in various practical network scenarios. Furthermore, we prove that the analysis of the algorithm is extendable to higher-dimensional Euclidean spaces, and to more realistic bounded-distortion spaces, induced by non-isotropic signal distortions. Finally, we show that it is NP-hard to approximate the scheduling problem to within n1-epsivfactor, for any constant epsiv > 0, in the non-geometric SINR model, in which path-loss is independent of the Euclidean coordinates of the nodes.

Ever larger collections of music are stored on mobile devices. The process of managing these repositories therefore becomes increasingly challenging. In this work we propose to use a map of the "world of music" as a data structure for music exploration and retrieval on mobile devices. We present Mobile Music Explorer---a mobile application, which allows users to create playlists by specifying trajectories on the map and to use similarity based search methods to navigate through their personal music collections. Our navigation methods ensure that any part of the collection can quickly be reached, even for a large set of items. Moreover, we show that the map representation is a natural approach to provide efficient and distributed operation.

Ever growing music collections ask for novel ways of organization. The traditional browsing of folder hierarchies or search by title and album tends to be insufficient to maintain an overview of a collection of orders of thousands of tracks. Methods based on song similarity offer an alternative to keyword-based search. In this work we propose to use a high-dimensional map of the "world of music" as a data structure for music retrieval and exploration of personal collections. Our approach does not require expensive analysis of audio signals and scales to hundreds of thousands of tracks. The techniques presented in this work can be used in a variety of applications, ranging from automatic DJs to file sharing on mobile devices. As a concrete example, we have developed a Web-application that allows users to visualize and navigate through their music collections and create playlists by specifying trajectories.

In this paper we study the problem of scheduling wireless links in the geometric SINR model, which explicitly uses the fact that nodes are distributed in the Euclidean plane. We present the first NP-completeness proofs in such a model. In particular, we prove two problems to be NP-complete: Scheduling and One-Shot Scheduling. The first problem consists in finding a minimum-length schedule for a given set of links. The second problem receives a weighted set of links as input and consists in finding a maximum-weight subset of links to be scheduled simultaneously in one shot. In addition to the complexity proofs, we devise an approximation algorithm for each problem.

The virtual world is comprised of data items related to each other in a variety of contexts. Often such relations can be represented as graphs that evolve over time. Examples include social networks, co-authorship graphs, and the world-wide-web. Attempts to model these graphs have introduced the notions of hierarchies and layers, which correspond to taxonomies of the underlying objects, and reasons for object relations, respectively. In this paper we explore these concepts in the process of mining such naturallygrown networks. Based on two sample graphs, we present some evidence that the current models well fit real world networks and provide concrete applications of these findings. In particular, we show how hierarchies can be used for greedy routing and how separation of layers can be used as a preprocessing step to implement a location estimation application.

Abstract In this paper, we formulate and solve the problem of how to dynamically distribute network resources in third‐generation mobile telecommunication systems, aiming to minimize the equipment maintenance and service provision costs. A mobility simulator was implemented in order to represent a hypothetical city, which was populated with different groups of users, whose mobility behavior and demand for different kinds of services was generated in order to simulate a typical 24‐h day behavior. Given the generated demand at a certain period of time, a server allocation is made in order to attend it. This is done by modeling the system as an integer‐programming problem and by, afterwards, running an optimization algorithm on it. The output from the optimization process was used to reconfigure the system by activating the selected servers and deactivating the others. The problem turned out to be NP‐hard, so a heuristic method was necessary in order to solve it. We chose the Lagrangean relaxation technique to do the task, and obtained good results in terms of the solution proximity to the optimum. The performed experiments demonstrated the model's sensitivity to different kinds of parameters, such as user mobility, demand distribution over time and space, time of day, type of area where events occur, and the relation between fixed and variable costs of the system. A significant system cost reduction was also achieved. The proposed approach allows a personalized and demand driven resource distribution. Copyright © 2006 John Wiley & Sons, Ltd.

In this paper, a new data dissemination algorithm for wireless sensor networks is presented. The key idea of the proposed solution is to combine concepts presented in trajectory-based forwarding with the information provided by the energy map of the network to determine routes in a dynamic fashion, according to the energy level of the sensor nodes. This is an important feature of an autonomic system, which must have the capacity of adapting its behavior according to its available resources. Simulation results revealed that the energy spent with the data dissemination activity can be concentrated on nodes with high-energy reserves, whereas low-energy nodes can use their energy only to perform sensing activity or to receive information addressed to them. In this manner, partitions of the network due to nodes that ran out of energy can be significantly delayed and the network lifetime extended.

Mobile computing will continue to widen as the world of computing increasingly becomes the world of access to network services and resources. We study the problem of given a network comprised of users (in our case mobile) and a set of servers that provide a service, we are interested in finding an association between users and servers that minimizes the cost to access the servers in the network. We present the mathematical formulation of this problem and a user mobility model that is used to perform some experiments. This is a initial step towards studying this problem that will be very important in a mobile setting.