ClubNet Winter 2007

Organized by Evgeny Bolotin and Edward Bortnikov.

ClubNet Main Page
ClubNet Spring 2006
ClubNet Winter 2006
ClubNet Spring 2005
ClubNet Winter 2004/5
ClubNet Spring 2004
ClubNet Winter 2003/4
ClubNet Spring 2003
ClubNet Winter 2002/3
ClubNet 2001/2
ClubNet 1999
ClubNet 1997/8

An IP-only Server
Dr. Oleg Goldshmidt
IBM Haifa Research Lab

Present day servers must support a variety of legacy I/O devices and protocols that are rarely used in the day to day server operation, at significant costs in board layout complexity, reliability, power consumption, heat dissipation, and ease of management. We present a design of an IP-Only Server, which has a single, unified I/O interface: IP network. All of the server's I/O is emulated and redirected over IP/Ethernet to a remote management station, except for the hard disks which are accessed via iSCSI. The emulation is done in hardware, and is available from power-on to shutdown, including the pre-OS and post-OS (crash) stages, unlike alternative solutions such as VNC which can only function when the OS is operational. The server's software stack - the BIOS, the OS, and applications - will run without any modifications. We have developed a prototype IP-Only Server, based on a COTS FPGA running our embedded I/O emulation firmware. The remote station is a commodity PC running a VNC client for video, keyboard and mouse. Initial performance evaluations with unmodified BIOS and Windows and Linux operating systems indicate negligible network overhead and acceptable user experience. This prototype is the first attempt to create a diskless and headless x86 server that runs unmodified industry standard software (BIOS, OS, and applications).

On a NIC's Operating System, Schedulers and High-Performance Networking Applications
Yaron Weinsberg
Hebrew University of Jerusalem

Two critical issues impact the overall performance of Linux clusters based on Intel servers: inter-process communication latency and data throughput. Underlying both of these performance challenges is the inefficient use of computational power and server CPU cycles to process the network protocols. Today's modern high-end Network Interface Cards (NICs) are equipped with an onboard CPU. In most cases, these CPU's are only used by the vendor and are operated by a proprietary OS, which makes them inaccessible to the HPC application developer. In this paper we present a design and implementation of a framework for building high-performance networking applications. The framework consists of an embedded NIC Operating System with a specialized scheduler. The main challenge in developing such a scheduler is the lack of a preemption mechanism in most high-end NICs. Our scheduler provides finer-grained schedules than the alternatives. We have implemented several network applications, and were able to increase their throughput while decreasing the host's CPU utilization.

Joint work with Tal Anker, Danny Dolev and Scott Kirkpatrick.

RaWMS - Random Walk based Membership Service for mobile ad hoc networks
Gabi Kliot
CS Department, Technion

In this talk I will present RaWMS - Random Walk based Membership Service for mobile ad hoc networks. The service provides each node with a partial uniformly chosen view of network nodes, while every node may set its desired view size independently of other nodes, based on its available memory. The resulting views are guaranteed to be uniformly random. RaWMS does not require multiple-hop routing and avoids flooding altogether. Its design is based on a novel reverse random walk (RW) sampling technique, specially designed and adapted for ad hoc networks. Such partial random membership service is useful, e.g., in probabilistic data dissemination algorithms, lookup and discovery services, uniform quorums constructions and peer sampling services. This talk will include a short background on random walks, a formal analysis of both the reverse RW sampling and RaWMS and results of a detailed simulation study validating the analytical analysis.

* Joint work with Ziv Bar-Yossef and Roy Friedman

Residential Communication: Market Directions and Technological Solution
Dr. Eli Fogel
Senior VP and CTO, DSP Group

Broadband connectivity penetration to the house and within the home and the proliferation of IP network solutions is transforming the residential communication industry. Until recently the BB connectivity was merely used for PC usage while now triple / quad play are becoming common with a variety of consumer electronic devices supporting those. The talk will present market trends, technical requirements and solutions for the residential communication in this new echo system. The presentation is brought from the perspective of a leading semiconductor manufacturer in this field and thus will also dive into some aspects of chip design considerations. In that context, trends in the design of consumer electronic system on chip (SOC) for this market will be presented.

Network Communication Processors
Shlomo Sinai
Product Manager, Freescale Semiconductor

The lecture will cover the following issues related to Network Communication Processors :

• Market trends
• Vendors Needs
• Supported Devices
• FSL Comprehensive Solution

Selfishness and Incentives in Networked Systems 
Dr. Michal Feldman
School of Computer Science and Engineering,
The Hebrew University of Jerusalem

The emergence of the Internet has initiated a radical shift of focus of our thinking about computational networked systems. While traditional system design assumes that all participants behave according to the intentions of the system designers, in reality, computer networks are built, operated and used by multiple users with diverse sets of interests. Hence, Internet protocols must be explicitly designed to work with interacting \emph{rational} individuals. Recently, there has been a growing interest in using tools from game theory and mechanism design to tackle incentive-related problems in these complex environments.

In the first part of the talk, I will give an overview of the field, and demonstrate its significance in computer networks through several prime examples from my own research. I will demonstrate the inherent tension between individual rationality and collective welfare in various settings ( e.g., peer-to-peer systems and network routing), and discuss several aspects of the design of incentive mechanisms that will drive the system into a desired equilibrium. In the second part of the talk, I will concentrate on the efficiency loss that is incurred due to users' selfishness in network routing and network formation. In contrast to the common measure of "price of anarchy" which quantifies the loss incurred due to both selfishness and lack of coordination, we acknowledge the ability of users to coordinate, thus propose to isolate the loss incurred due to selfishness alone. We show that coordination among selfish users can significantly improve the efficiency of the considered settings.

Efficient Contention Resolution Protocols for Selfish Agents 
Prof. Yishay Mansour
School of Computer Science, Tel Aviv University

We seek to understand behavior of selfish agents accessing a broadcast channel. In particular, we consider the natural agent utility where costs are proportional to delay. Access to the channel is modeled as a game in extensive form with simultaneous play.
Standard protocols such as Aloha are vulnerable to manipulation by selfish agents. We analyze the symmetric equilibrium strategy in such a setting and show that the appropriate transmission probabilities are $O(1/\sqrt{n})$, when $n$ agents are competing. This clearly implies exponentially long delays.
We give a very simple protocol for the agents that is in Nash equilibrium and --- other than with exponentially negligible probability --- all $n$ agents will successfully transmit within $O(n)$ steps.

This is a joint work with Amos Fiat and Uri Nadav. 

Relaxed Currency Serializability for Middle-Tier Caching and Replication 
Prof. Alan Fekete
School of Information Technologies, University of Sydney

Many applications, such as e-commerce, routinely use copies of data that are not in sync with the database due to heuristic caching strategies used to enhance performance. We study concurrency control for a transactional model that allows update transactions to read out-of-date copies. Each read operation carries a freshness constraint that specifies how fresh a copy must be in order to be read. We offer a definition of correctness for this model and present algorithms to ensure several of the most interesting freshness constraints. We outline a serializability-theoretic correctness proof and present the results of a detailed performance study.

Buffer Scalability of Wireless Networks 
Prof. Petar Momcilovic
Department of Electrical Engineering and Computer Science University of Michigan at Ann Arbor

We study the existence of protocols that can achieve the capacity limit in a large, growing wireless network with fixed buffer space in each node. The goal is to maximize the network throughput in the presence of packet losses caused by limited buffer space. We establish that the network cannot operate at its capacity limit with a finite buffer in each node. However, somewhat unexpectedly, we construct a protocol that obtains just a slightly smaller throughput even with very small buffers.

Wireless Communications for Public Transport and Road Infrastructure: Research Challenges 
Dr. Lavy Libman
National ICT Australia

There is a growing interest in the use of wireless communications for vehicular and road applications, as a result of recent advances in enabling technologies. Much of the research attention has gone into direct vehicle-to-vehicle communications (e.g. for highway safety), but practical deployment has been slow due to the need for major vehicle manufacturers to reach common agreements and standards. On the other hand, applications that do not require vehicle manufacturer involvement have seen much faster progress. In this talk, we overview two research projects in this space, involving the Networks and Pervasive Computing research group at National ICT Australia (NICTA), Sydney. Project OCEAN (On-board Communications, Entertainment and iNformation), conducted in collaboration with the University of New South Wales, studies issues in the deployment of on-board high-speed LANs in public transport vehicles, designed to offer a seamless and efficient connectivity solution to passengers without requiring them to use individual mobile network providers. A key part of this project is designing network protocols capable of utilising the repetitive, predictable nature of public transport routes and timetables to improve the network performance and quality of service. The other project, named STaR (Smart Transport and Roads) and supported by the state's Road and Traffic Authority, considers the use of static wireless mesh networks as the communications layer of traffic control systems in metropolitan areas. Such systems feature low data rates but very strict requirements of reliability and latency between the traffic control centre and roadside infrastructure, and call for specially-tailored wireless mesh protocols at the link and routing layers. This talk will review the research challenges and opportunities in both of the above projects, and present a sample of recent results and progress.

Mobile Digital TV – Architecture and Challenges  
Dr. Ilan Sutskover
Intel

Mobile Digital TV (MDTV) is an emerging trend expected to hit us all in the next 3-5 years. MDTV is about receiving TV broadcasts while on the go through handheld devices, ultra mobile devices, and laptops. The most dominant published MDTV standards include: DVB-H (and mobile DVB-T), T-DMB and ISDB-T. Qualcomm’s MediaFLO is also expected to gain its market share. In this lecture we will describe some elements in the various OSI layers and will focus more on the physical layer. The structure of the physical layer signal shall be presented and compared for few of the standards, and the communications challenges from the receivers’ point of view shall be emphasized.

Cluster Ranking with an Application to Mining Mailbox Networks  
Dr. Ziv Bar-Yossef
Google, Israel
EE Department, Technion

We initiate the study of a new clustering framework, called "cluster ranking". Rather than simply partitioning a network into clusters, a cluster ranking algorithm also orders the clusters by their strength. To this end, we introduce a novel strength measure for clusters---the "integrated cohesion"---which is applicable to arbitrary weighted networks. We then present C-Rank: a new cluster ranking algorithm. Given a network with arbitrary pairwise similarity weights, C-Rank creates a list of overlapping clusters and ranks them by their integrated cohesion. We provide extensive theoretical and empirical analysis of C-Rank and show that it is likely to have high precision and recall. A main component of C-Rank is a heuristic algorithm for finding sparse vertex separators. At the core of this algorithm is a new connection between the well known measure of vertex betweenness and multicommodity flow. Our experimental results focus on mining mailbox networks. A mailbox network is an egocentric social network, consisting of contacts with whom an individual exchanges email. Ties among contacts are represented by the frequency of their co--occurrence on message headers. C-Rank is well suited to mine such networks, since they are abundant with overlapping communities of highly variable strengths. We demonstrate the effectiveness of C-Rank on the Enron data set, consisting of 130 mailbox networks. Joint work with Ido Guy, Ronny Lempel, Yoelle Maarek, and Vova Soroka.

Hunting disease provoking genes using thousands of computers  
Mark Silberstein
CS Department, Technion

Linkage analysis is a tool used by geneticists for mapping disease-susceptibility genes in the study of Mendelian and complex diseases. However analyses of large inbred pedigrees with extensive missing data are often beyond the capabilities of a single computer. We present a distributed system called Superlink-online for computing multipoint LOD scores of large inbred pedigrees. It achieves high performance via efficient parallelization of the algorithms in Superlink, a state-of-the-art serial program for these tasks, and through utilization of thousands of resources residing in multiple opportunistic grid environments. Notably, the system is available online, which allows computationally intensive analyses to be performed with no need for either installation of software, or maintenance of a complicated distributed environment. The main algorithmic challenges have been to efficiently split large tasks for distributed execution in highly dynamic non-dedicated running environment, as well as to utilize resources in all the available grid environments, providing nearly interactive response time for shorter tasks while simultaneously serving massively parallel ones. The system is being extensively used by medical centers worldwide, achieving speedups of up to three orders of magnitude and allowing analyses which have not been feasible previously. This work has been done as a part of PhD studies in the Technion under joint supervision of Prof. Assaf Schuster and Dan Geiger. It has been published in American Journal of Human Genetics and presented at High Performance Distributed Computing conference in 2006.

Throughput Maximization in Wireless Networks via Partitioning and Randomization  
Dr. Gil Zussman
MIT

A major challenge in the design of wireless networks is the need for distributed scheduling algorithms that will efficiently share the common spectrum. Due to the distributed operation, scheduling algorithms that have been recently presented can achieve only a fraction of the maximum throughput. We present two distributed scheduling frameworks that guarantee maximum throughput. The first framework is based on deterministic algorithms and is designed for Wireless Mesh Networks (WMNs). We show that the multi-channel multi-radio capability of WMNs can enable the partitioning of the network into subnetworks in which simple deterministic distributed scheduling algorithms achieve 100% throughput. Using the recently introduced notion of Local Pooling, we characterize such subnetworks. Then, channel assignment algorithms that partition a network into such subnetworks are presented. The second framework uses randomized algorithms and is designed for general wireless networks. It is based on a combination of a distributed randomized matching algorithm and an algorithm that compares and merges successive matching solutions. The comparison can be done by a deterministic algorithm or by randomized gossip algorithms. We show that although the comparison may be inaccurate, the framework attains 100% throughput. It is shown that the complexities of our algorithms, that achieve 100% throughput, are comparable to those of algorithms that achieve 50% throughput.
The first part is joint work with A. Brzezinski and E. Modiano. The second part is joint work with E. Modiano and D. Shah.