Rethinking Boolean Network Tomography

Boolean Inference makes it possible to observe the congestion status of end-to-end paths and infer, from that, the congestion status of individual network links. In principle, this can be a powerful monitoring tool, in scenarios where we want to monitor a network without having direct access to its links. We consider one such real scenario: a Tier-1 ISP operator wants to monitor the congestion status of its peers. We show that, in this scenario, Boolean Inference cannot be solved with enough accuracy to be useful; we do not attribute this to the limitations of particular algorithms, but to the fundamental difficulty of the Inference problem. Instead, we argue that the ``right'' problem to solve, in this context, is compute the probability that each set of links is congested (as opposed to try to infer which particular links were congested when). Even though solving this problem yields less information than provided by Boolean Inference, we show that this information is more useful in practice, because it can be obtained accurately under weaker assumptions than typically required by Inference algorithms and more challenging network conditions (link correlations, non-stationary network dynamics, sparse topologies).

Shifting Network Tomography Toward A Practical Goal

Denisa Gabriela Ghita, Can Karakus, Patrick Thiran

Boolean Inference makes it possible to observe the congestion status of end-to-end paths and infer, from that, the congestion status of individual network links. In principle, this can be a powerful monitoring tool, in scenarios where we want to monitor a network without having direct access to its links. We consider one such real scenario: a Tier-1 ISP operator wants to monitor the congestion status of its peers. We show that, in this scenario, Boolean Inference cannot be solved with enough accuracy to be useful; we do not attribute this to the limitations of particular algorithms, but to the fundamental difficulty of the Inference problem. Instead, we argue that the "right" problem to solve, in this context, is compute the probability that each set of links is congested (as opposed to try to infer which particular links were congested when). Even though solving this problem yields less information than provided by Boolean Inference, we show that this information is more useful in practice, because it can be obtained accurately under weaker assumptions than typically required by Inference algorithms and more challenging network conditions (link correlations, non-stationary network dynamics, sparse topologies).

2011

A cross-layer design of wireless ad-hoc networks

We consider a cross-layer design of wireless ad-hoc networks. Traditional networking approaches optimize separately each of the three layers: physical layer, medium access and routing. This may lead to largely suboptimal network designs. In this work, we propose a jointly optimal design of the three layers, and we show a significant performance improvement over the conventional approach. In the first part of this thesis, our goal is to select appropriate performance metrics for the joint optimization problem. To that respect, we analyze several existing rate-maximization performance metrics for wireless ad-hoc networks: maximizing the sum of rates, max-min fairness and proportional fairness. We first show with several examples that it is not clear if and how max-min fairness can be defined on each one of the examples. We give a formal proof that the max-min fair rate allocation exists on a large class of sets of feasible rates, among which are the feasible-rate sets of all known ad-hoc networking examples. We also give a centralized algorithm to compute the max-min fair allocation whenever it exists. Next, we compare the three metrics for ad-hoc scenarios in terms of efficiency and fairness. We prove that, similar to wired networking,maximizing the sum of rates leads to gross unfairness and starvation of all but the flows with the best channel conditions. We also prove that, contrary to wired networking, max-min fairness yields all flows having the same rate, thus causing large inefficiencies. These findings offer theoretical explanations to the inefficiency and unfairness phenomena previously observed in the contexts of 802.11 and UWB networks. Finally, we show that proportional fairness achieves a good trade-off between efficiency and fairness and is a good candidate for a rate-based performance metric in wireless ad-hoc settings. Having shown that the proportional fairness is an appropriate optimization objective for our problem, in the second part of the thesis we consider a joint optimization of rates, transmission powers, medium access (scheduling) and routing, where the goal of the optimization is to achieve proportional fairness. We first analyze networks built on physical layers that have a rate which is a linear function of SNR at the receiver (such as UWB or low-gain CDMA systems). We find that the optimal solution is characterized by the following principles: (1)Whenever a node transmits, it has to transmit with the maximum power; otherwise it has to remain silent (0 - PMAX power control). (2) Whenever data is being sent over a link, it is optimal to have an exclusion region around the destination, in which all nodes remain silent during transmission, whereas nodes outside of this region can transmit in parallel, regardless of the interference they produce at the destination. (3) When a source transmits, it adapts its transmission rate according to the level of interference at the destination due to sources transmitting in parallel. (4) The optimal size of this exclusion region depends only on the transmission power of the source of the link, and not on the length of the link nor on positions of nodes in its vicinity. As for the routing, we restrict ourselves to a subset of routes where on each successive hop we decrease the distance toward the destination. We also show that (5) relaying along a minimum energy and loss route is better than using longer hops or sending directly, which is not obvious since we optimize rate and not power consumption. Finally (6), the design of the optimal MAC protocol is independent of the choice of the routing protocol. We present a theoretical proof of optimality of 0 - PMAX power control, and the remaining findings we show numerically on a large number of random network topologies. Next, we consider narrow-band networks, where rate function is a strictly concave function of SNR. There, previous findings do not always hold. We show that in some cases, the size of the exclusion region and the optimal routing depend on transmission powers, and that the optimal MAC design depends on the choice of routing. Nevertheless, as we show with the example of 802.11 networks, a significant improvement over the existing 802.11 MAC can be achieved even with simpler, suboptimal strategies. Although this result is shown by simulations on a simplified model, it still gives further directions on how to improve the performance of RTS/CTS based protocols.

EPFL2005

Signaling and Reciprocity

Wojciech Galuba

Complex networks exist for a number of purposes. The neural, metabolic and food networks ensure our survival, while the social, economic, transportation and communication networks allow us to prosper. Independently of the purposes and particularities of the physical embodiment of the networks, one of their fundamental functions is the delivery of information from one part of the network to another. Gossip and diseases diffuse in the social networks, electrochemical signals propagate in the neural networks and data packets travel in the Internet. Engineering networks for robust information flows is a challenging task. First, the mechanism through which the network forms and changes its topology needs to be defined. Second, within a given topology, the information must be routed to the appropriate recipients. Third, both the network formation and the routing mechanisms need to be robust against a wide spectrum of failures and adversaries. Fourth, the network formation, routing and failure recovery must operate under the resource constraints, either intrinsic or extrinsic to the network. Finally, the autonomously operating parts of the network must be incentivized to contribute their resources to facilitate the information flows. This thesis tackles the above challenges within the context of several types of networks: 1) peer-to-peer overlays – computers interconnected over the Internet to form an overlay in which participants provide various services to one another, 2) mobile ad-hoc networks – mobile nodes distributed in physical space communicating wirelessly with the goal of delivering data from one part of the network to another, 3) file-sharing networks – networks whose participants interconnect over the Internet to exchange files, 4) social networks – humans disseminating and consuming information through the network of social relationships. The thesis makes several contributions. Firstly, we propose a general algorithm, which given a set of nodes embedded in an arbitrary metric space, interconnects them into a network that efficiently routes information. We apply the algorithm to the peer-to-peer overlays and experimentally demonstrate its high performance, scalability as well as resilience to continuous peer arrivals and departures. We then shift our focus to the problem of the reliability of routing in the peer-to-peer overlays. Each overlay peer has limited resources and when they are exhausted this ultimately leads to delayed or lost overlay messages. All the solutions addressing this problem rely on message redundancy, which significantly increases the resource costs of fault-tolerance. We propose a bandwidth-efficient single-path Forward Feedback Protocol (FFP) for overlay message routing in which successfully delivered messages are followed by a feedback signal to reinforce the routing paths. Internet testbed evaluation shows that FFP uses 2-5 times less network bandwidth than the existing protocols relying on message redundancy, while achieving comparable fault-tolerance levels under a variety of failure scenarios. While the Forward Feedback Protocol is robust to message loss and delays, it is vulnerable to malicious message injection. We address this and other security problems by proposing Castor, a variant of FFP for mobile ad-hoc networks (MANETs). In Castor, we use the same general mechanism as in FFP; each time a message is routed, the routing path is either enforced or weakened by the feedback signal depending on whether the routing succeeded or not. However, unlike FFP, Castor employs cryptographic mechanisms for ensuring the integrity and authenticity of the messages. We compare Castor to four other MANET routing protocols. Despite Castor's simplicity, it achieves up to 40% higher packet delivery rates than the other protocols and recovers at least twice as fast as the other protocols in a wide range of attacks and failure scenarios. Both of our protocols, FFP and Castor, rely on simple signaling to improve the routing robustness in peer-to-peer and mobile ad-hoc networks. Given the success of the signaling mechanism in shaping the information flows in these two types of networks, we examine if signaling plays a similar crucial role in the on-line social networks. We characterize the propagation of URLs in the social network of Twitter. The data analysis uncovers several statistical regularities in the user activity, the social graph, the structure of the URL cascades as well as the communication and signaling dynamics. Based on these results, we propose a propagation model that accurately predicts which users are likely to mention which URLs. We outline a number of applications where the social network information flow modelling would be crucial: content ranking and filtering, viral marketing and spam detection. Finally, we consider the problem of freeriding in peer-to-peer file-sharing applications, when users can download data from others, but never reciprocate by uploading. To address the problem, we propose a variant of the BitTorrent system in which two peers are only allowed to connect if their owners know one another in the real world. When the users know which other users their BitTorrent client connects to, they are more likely to cooperate. The social network becomes the content distribution network and the freeriding problem is solved by leveraging the social norms and reciprocity to stabilize cooperation rather than relying on technological means. Our extensive simulation shows that the social network topology is an efficient and scalable content distribution medium, while at the same time provides robustness to freeriding.

EPFL2011

A cross-layer design of wireless ad-hoc networks

EPFL2005

Signaling and Reciprocity

Wojciech Galuba

EPFL2011