ClubNet Spring 2008
Organized by
Edward Bortnikov and
Zvika Guz
Scalable Publish-Subscribe in Very Large Distributed Systems
Dr. Gregory (Grisha) Chockler
IBM Haifa Research Lab
Publish/Subscribe (pub/sub) is a powerful communication paradigm capable of supporting diverse interaction patterns in distributed environments. Roughly, it allows users to subscribe to certain topics of interest and then be notified of every update being published on those topics. Realizing pub/sub in large distributed systems, such as enterprise data centers and compute clouds, imposes numerous scalability challenges along all of the following dimensions: number of nodes, number of topics, user subscription size, and geographical distribution. While application-level (or overlay) networks can effectively deal with a huge number of users and geographical scale, they are not readily applicable to accommodate the growth in the number of topics and subscription size. In this talk, I will discuss our recent work on constructing scalable overlay topologies to efficiently support pub/sub in very large distributed systems. I will present a new overlay construction protocol, called SpiderCast, which utilizes two fully distributed heuristics to drive the neighbor selection process so that the resulting overlay is both connected for every topic, and has a low degree.
I will then focus on the feasibility of constructing scalable pub/sub overlays under the assumption of complete knowledge of the node, interests. To this end, I will introduce a new optimization problem capturing the tradeoff between the connectivity and the average degree of the pub/sub overlays, and discuss its hardness and approximability. Time permitting, I will also touch upon a complementary approach to scalable pub/sub based on distributed topic clustering.
This is a joint work with Roie Melamed (IBM), Yoav Tock (IBM), and Roman Vitenberg (University of Oslo). It is loosely based on the papers appearing in DEBS'07 and PODC'07.
Computational Analysis and Efficient Algorithms for Micro and Macro OFDMA Scheduling
Liran Katzir
The Technion, CS Faculty
OFDMA is one of the most important modulation and access methods for the future mobile networks. Before transmitting a frame on the downlink, an OFDMA base station has to invoke an algorithm that determines which of the pending packets will be transmitted, what modulation should be used for each of them, and how to construct the complex OFDMA frame matrix as a collection of rectangles that fit into a single matrix with fixed dimensions. We propose efficient, and theoretically best possible, algorithms that solves this intricate OFDMA scheduling problem by breaking it down into two sub-problems, referred to as macro and micro scheduling. We analyze the computational complexity of these sub-problems and develop efficient algorithms for solving them.
Joint work with Prof. Reuven Cohen.
On Network Formation Dynamics with Bilateral Contracts
Prof. Shie Manor
McGill University
We consider a network formation game where a finite number of nodes wish to send traffic to each other. Nodes contract bilaterally with each other to form bidirectional communication links; once the network is formed, traffic is routed along shortest paths. Each contract is endowed with a utility transfer. Cost is incurred to a node from three sources: (1) traffic related costs; (2) maintaining links to other nodes; and (3) payments made to other nodes (from contracts). We consider two models for traffic related costs: one where cost arises from routing packets; and another where cost is related to latency or number of hops. As a solution concept, we define a network to be stable if no single node wishes to unilaterally deviate, and no pair of nodes can profitably deviate together; our definition is a variation on the notion of pairwise stability. Our starting point is the identification of the set of stable networks, showing that arbitrarily inefficient networks may be stable.
Our focus in this talk is on studying such games under myopic local best response dynamics. We consider different dynamics focusing on two desiderata: locality of information and selection of an efficient equilibrium. With these desiderata in mind we propose the following dynamics. The network evolves in discrete steps, each consisting of two stages. During the first stage, an exogenously designated node u considers all possible unilateral deviations. Then, during the second stage, it considers forming a new contract with a node v in its neighborhood. That contract can be accepted or rejected by the target node. While the designated node u chooses its actions to maximize its payoff at the end of both stages, the target node v chooses a myopic best response to maximize its payoff given the network after the first stage.
We characterize a simple set of assumptions under which these dynamics will converge to a pairwise stable network topology; as an example, our assumptions are satisfied by a contractual model motivated by bilateral Rubinstein bargaining with infinitely patient players. We study the convergence rates as well as the efficiency of the limit networks for the two models for traffic related costs.
Joint work with Esteban Aracute (Stanford), Eric Dallal (McGill) and Ramesh Johari (Stanford).
Abandoning the Ring Concept in Structured Overlay Networks
Sarunas Girdzijauskas
Ecole Polytechnique Federale de Lausanne (EPFL)
Most of the structured P2P overlay networks rely on a ring invariant as a core network connectivity element. The responsibility ranges of the participating peers and navigability principles (greedy routing) heavily depend on the ring structure. For correctness guarantees, each peer needs to eagerly maintain its immediate neighboring links - the ring invariant. However, the ring maintenance is an expensive task and reliance on the ring structure is a serious impediment for real life deployment and scalability of structured overlays. In this talk I will introduce an overlay called Fuzzynet, which does not rely on the ring invariant, yet have all the functionalities of structured overlays. I will also discuss structured overlay construction algorithms for non-uniform key spaces.
Overcoming Disruption in Wireless Radio Networks
Dr. Seth Gilbert
EPFL, Distributed Programming Laboratory
Wireless networks are particularly susceptible to malicious and
malfunctioning devices. For example, a malicious device can easily
jam the airwaves, disrupting all communication. In this talk, I will
present new techniques for overcoming network disruptions in wireless
networks, specifically in the context of multi-channel networks.
In order to provide some intuition as to the challenges posed by
malicious disruption, I will begin by demonstrating a lower bound for
oblivious gossip algorithms. (Underlying the lower bound proof lies an
interesting connection between epsilon-gossip and extremal graph
theory.) I will then present an adaptive algorithm that improves on
the lower bound, relying on a new combinatorial tool, the
multiselector (which, as a natural generalization of a selector, we
believe to be of potentially independent interest). Finally, I will
present a randomized algorithm that can tolerate even more severe
forms of malicious misbehavior.
Joint work with: Shlomi Dolev, Rachid Guerraoui, Darek Kowalski, and Calvin Newport
NAT and Firewall Traversal in Multimedia Collaboration Systems
Evgeny Hazanovich
Technion, EE Faculty
In IP networking, the process of Network Address Translation (NAT) involves re-writing the source/destination address/port of IP packets as they traverse an access router/firewall. Most systems using NAT do so in order to enable multiple hosts on a private network to access the Internet using a single public IP address. More complicated NAT implementations also involve security considerations. While the NAT technology is widespread in small office/home office (SOHO) settings, it introduces address resolution complications that may also have a performance impact. We present a complete solution for the NAT traversal problem for instant messaging (IM), voice over IP (VoIP) and video over IP collaborative applications. We have implemented a Linux-based router for all the standard NAT types, a media gateway infrastructure required for NAT traversal, and a full-fledged (Skype-like) collaborative application. The solution uses industry-standard protocols - SIP for session control and messaging and RTP for voice/video communication over the network, based on open-source software packages. Our performance measurements show that in some cases, our solution performs better than the one adopted by Skype.
Joint work with Alex Hazanovich, under the supervision of Eddie Bortnikov.
QMesh - QoS Wireless Mesh Network with Mobility Support
Tal Kol
Technion, EE Faculty
We present QMesh, a software package that allows utilizing multiple geographically scattered Windows desktops as a wireless mesh network infrastructure with seamless user mobility support. QMesh supports its users through standard protocols, and does not require any client software installation. We optimize the solution's quality of service (QoS) by providing a centralized management infrastructure, which allows an assignment of users to Internet gateways that balances between distance and load considerations. QMesh is implemented as a Windows XP driver, on top of the Mesh Connectivity Layer (MCL) toolkit from Microsoft Research that provides basic routing capabilities. To the best of our knowledge, this is the first mobile mesh solution implemented within the Win32 kernel space. The project appeared at the ACM Student Research Competition at the Mobicom 2007 conference in Montreal.
Joint work with Arkady Vaisman, under the supervision of Eddie Bortnikov.
Mobile WiMAX, a 4G Technology
Dr. Dov Andelman
Intel's Mobile Wireless Group
Mobile WiMAX, a.k.a. IEEE 802.16 is an operator provided data optimized mobile wireless access system for metro, outdoor and indoor use. This system is currently in early stages of deployment. In this talk we present a short overview of WiMAX, its evolution and how it meets the challenges of a 4G wireless system.
Challenges in Scaling to 100Gbps Packet Processing
Dr. Amir Rosen
EZchip Technologies
The never-ending demand for an ever-growing traffic bandwidth requires the industry to continue introducing solutions supporting increasing rates and aggregation. 100GE is being standardized by IEEE High Speed Study Group and the standard is about 1 or 2 years away. Demand for 100Gbps processing will become ubiquitous in only a few years.
EZchip Technologies provides high-speed and highly integrated Ethernet network processors (NPUs) that are used in building Carrier Ethernet Switches and Routers. The architecture of EZchip's NPUs allows programmable parsing, classification, modification and forwarding of high speed internet traffic. An integrated traffic manager maintains a large number queues and supports policing, hierarchical scheduling, committed and excess rate shaping, priority handling and fairness management. Real time monitoring and event generation is also accomplished as an integrated mechanism.
In this talk, we will discuss some of the challenges encountered when designing 100Gbps processing and traffic management solutions. Several aspects of EZchip novel architecture for addressing theses challenges will be introduced.
Graphs on the Semantic Web
Eran Toch
The Technion, IE Faculty
The Semantic Web extends the current World Wide Web with languages that help machines to read and understand information on the Web. These languages enable content providers to formally describe their content using graph-based data structures, which makes automatic analysis and inference easier. However, the formalization process itself inherently raises difficulties in dealing with uncertain and diverse information, which is widespread across the Web. In order to deal with these challenges, we propose methods for approximate inference on semantic Web graphs. In this talk I will give an overview of the Semantic Web, describe the challenges it is facing, and present our contribution.
Joint work with Prof. Dov Dori (Techion), Dr. Iris Reinhartz-Berger (Haifa University) and Prof. Avigdor Gal (Technion).
Brahms: Byzantine Resilient Random Membership Sampling
Prof. Idit Keidar
The Technion, EE Faculty
We present Brahms, an algorithm for sampling random nodes in a large
dynamic system prone to adversary attacks (Byzantine failures).
Brahms stores small membership views at each node, and yet overcomes
attacks by a linear portion of the system. Brahms is composed of two
components. The first is an attack-resistant gossip-based membership
protocol. The second uses a novel memory-efficient approach for
uniform sampling from a possibly biased stream of ids that traverse
the node. We evaluate Brahms using rigorous analysis, backed by
extensive simulations, which show that our theoretical model captures
the protocol's essentials. We study two representative attacks.
We show that, with high probability, an attacker cannot create a
partition between correct nodes. We further prove that each node's
sample converges to a uniform one over time.
Based on joint work with Edward Bortnikov, Maxim Gurevich, Gabriel Kliot, and Alexander Shraer
Dynamic Service Management in Infrastructure-Based Mobile Networks
Edward Bortnikov
The Technion, EE Faculty (Ph.D. seminar)
We study the paradigm of delivering real-time mobile applications through a geographically distributed cloud infrastructure, specifically the problems of dynamic assignment of mobile users and groups to service points within the cloud. In contrast with link-layer association, which is primarily driven by physical constraints, application session assignment must jointly consider network distances, congestion, and handoff costs to optimize the quality of service in the long run. The anticipated system scale and the need to adapt to changing behavior of mobile users raise novel problems and call for local and adaptive distributed optimization algorithms behind the cloud framework.
We present contribution in the following areas:
-
Nomadic Service Assignment - dynamic balancing between the needs of always assigning the user to the closest server, and reducing the number of handoffs.
-
Scalable Load-Distance Balancing - problem of assigning multiple users to servers, which jointly considers loads and distances, in a local distributed setting.
-
QMesh - mobility management framework for city-scale wireless mesh networks, which addresses all assignment factors.
Ph.D. research under the supervision of Prof. Israel Cidon and Prof. Idit Keidar.
Broadcasting in UDG Radio Networks with Unknown Topology
Erez Kantor
Weizmann Institute
We studies broadcasting in radio networks, modeled as unit disk graphs
(UDG). Such networks occur in wireless communication between sites (e.g.,
stations or sensors) situated in a terrain. Network stations are represented by
points in the Euclidean plane, where a station is connected to all stations at
distance at most 1 from it. A message transmitted by a station reaches all
its neighbors, but a station hears a message (receives the message correctly)
only if exactly one of its neighbors transmits at a given time step. Stations are
unaware of the network topology.
It turns out that broadcasting time depends on two parameters of the UDG
network, namely, its diameter D and its granularity g, which is the inverse of
the minimum distance between any two stations. We distinguish between the
arbitrary deployment setting in which stations can be placed everywhere in the
plane, and the grid deployment setting, in which stations are only allowed to
be placed on a d-spaced grid. Does the latter (more restricted) setting provides
any speedup in broadcasting time complexity?
In this talk, I'll present a linear broadcast algorithm and a linear lower
bound for the arbitrary deployment setting and a sublinear broadcasting algo-
rithm and sublinear lower bound for the grid deployment setting, thus breaking
the linear dependency on g.
This is a joint work with Yuval Emek, David Peleg (Weizmann), Leszek
G»asieniec, Chang Su (Liverpool), Andrzej Pelc (Quebec). It is based on two
papers appearing in PODC'07 and PODC'08.
Interdomain Routing and Games
Michael Schapira
The Hebrew University
We present a game-theoretic model that captures many of the intricacies of interdomain routing in today's Internet. In this model, the strategic agents are source nodes located on a network, who aim to send traffic to a unique destination node. The interaction between the agents is dynamic and complex -- asynchronous, sequential, and based on partial information. Best-reply dynamics in this model capture crucial aspects of the only interdomain routing protocol de facto, namely the Border Gateway Protocol (BGP).
We study complexity and incentive-related issues in this model. Our main results are showing that in realistic and well-studied settings, BGP is incentive-compatible. That is, not only does myopic behaviour of all players converge to a "stable" routing outcome, but no player has motivation to unilaterally deviate from the protocol. Moreover, we show that even coalitions of players of any size cannot improve their routing outcomes by collaborating. Unlike the vast majority of works in mechanism design, our results do not require any monetary transfers (to or by the agents).
This is joint work with Hagay Levin and Aviv Zohar
On Operating-Systems for Supercomputers
Edi Shmueli
IBM Haifa Research Lab
The BlueGene machines in production today run a small limited-function
kernel called CNK (Compute-Node Kernel) designed to expose bare-metal
performance to the application. The problem is that this comes at the
expense of limiting BlueGene to executing pure HPC applications, though
potentially the platform can execute any type of workload. A possible
solution would be to replace CNK with standard Linux, but in order to get
accepted, Linux must first demonstrate performance that is comparable to
CNK.
In a research conducted at the IBM T.J. Watson research center, for the
first time we booted Linux on the compute-nodes of BlueGene/L and
compared its performance to CNK. We identified two major obstacles to performance
under Linux: the well known daemon noise problem that affects application
scalability, and the high cost of TLB (Translation Lookaside Buffer)
misses that affects performance at the node-level. We then leveraged unique
hardware features in the system using proper software support in the
Linux kernel and demonstrated comparable performance to CNK over a wide set of
HPC benchmarks.
My talk has two parts. I begin with an introduction to supercomputing
where I describe the BlueGene/L software and hardware architecture, the general
structure of HPC applications, and related performance issues. I then
focus on the Linux research, where I present the experiments we performed, the
issues we encountered and the solutions we developed to address them.
Randomized Gossip Algorithms
Coby Fernandess
The Hebrew University
The dynamic behavior and scale of peer-to-peer networks in which information
and network's topology are changing continuously over time requires robust
mechanisms for keeping nodes updated with new content. Randomized gossip
protocols are mechanisms for this task. Randomized gossip-based communication
schemes are fairly simple and practical: in every time-step, each node
communicates with a partner chosen at random and exchanges information it holds
in order to provide a solution to given problems in a distributed manner. The
use of randomized gossip algorithms to propagate information has been found to
provide better reliability and scalability over traditional deterministic
approaches. We factor out the fundamental elements found at the heart of these
algorithms, hopefully, leading to a better understanding of this innovative
form of communication.
The Capacity Allocation Paradox
Asaf Baron
The Technion, EE Faculty (M.Sc. seminar)
In this talk, I will present a capacity allocation paradox which we discovered and investigated: sometimes, increasing link capacity can actually make a stable network unstable.
Such a result can obviously have significant consequences. Most often, when confronted to a network with bad performance, network designers simply assume that increasing capacity will improve it, and therefore capacity allocation is the main tool used to provide sufficient quality-of-service. The phenomenon that we discovered actually shows that this assumption is not always correct in finite-buffer networks; and even stronger, it might be that adding capacity to a stable network with sufficient quality-of-service even makes it unstable. Incidentally, note that this paradox is different from Braess's paradox, since routing is fixed and no game theory is involved.
In the talk, I will present both analysis and simulation of this capacity allocation phenomenon, and will show that it applies to networks as diverse as store-and-forward networks (as in the Internet) or wormhole networks (as in networks-on-chip, interconnection networks and SpaceWire).
M.Sc research under the supervision of Prof. Ran Ginosar and Dr. Issac Keslassy.
|
Login
