ClubNet Winter 2003/4

Organized by Omer Gurewitz and Gil Zussman.

Clubnet Spring 2003 lectures
Clubnet Winter 2002/3 lectures
ClubNet 2001/2 lectures
ClubNet 1999 lectures
ClubNet 1997/8 lectures

Asymptotically Optimal Flooding and Routing in Random Sensor Networks
Dr. Gideon Stupp
Dept. of Electrical Engineering, Technion

Contemporary sensor networks are expected to survive the failure of a constant (possible small) fraction of the nodes in the network. Thus, the networks' half life (the time until more than half of the network nodes fail), is a good indicator for the lifespan of the system. This is in contrast to the time it takes until the first node fails, or the time it takes until the last node fails, both of which can be very different.

We consider the expected half life of randomly placed sensor nets executing flooding and routing communication operations. We prove that the expected half life of the network when face routing over the edges of the Delaunay triangulation is $\widetilde{\Theta}(n^{1.5})$ and that its expected half life when flooding over these edges is $\Theta(n)$. These results contrast previous works which considered Delaunay triangulations unfitting for communication purposes due to the potential existence of long edges.

The contributions of this work, we feel, are not limited to the final results. The geometrical tools we develop can be used to analyze other communication patterns and may have implications outside the field of communication. For a set of points, $P$, randomly placed in the unit disk denote by $Del(P)$ the Delaunay triangulation of $P$. We show that (1) with high probability, the longest edge in $Del(P)$ is near the boundary, and its length is $O(\sqrt[3]{\frac{\log n}{n}})$ and (2) the expected sum of squares of lengths of the edges of $Del(P)$ is $\Theta(1)$. To the best of our knowledge this is the first work that analyzes the bounded Delaunay triangulation.

Joint work with Gadi Kozma (Weizmann Institute of Science), Zvika Lotker and Micha Sharir (Tel Aviv Univ.)

Video Conference - IP Secure Connect
Danny On
VP R&D and Technical Alliances, VCON Ltd

What is SC?

• Extends the benefits of IP based communications safely beyond the edges of the managed data network
  • Remote branch offices
  • Home office workers
  • Customers and business partners
• Solves the connectivity problems associated with firewalls and NAT servers without eliminating security
• Encryption component for added security of the actual media and signaling streams
• Most firewalls allow only very specific types of inbound traffic
• When a session is initiated from "inside" the firewall, usually returned data streams to the originating IP address and port are allowed
• Many firewalls also perform Network Address Translation (NAT) or Network Address Port Translation (NAPT)

Presentation

Network on Chip
Evgeny Bolotin
Dept. of Electrical Engineering, Technion

Rapid technology scaling in VLSI leads to increased density of VLSI System on Chips (SoCs). As the capacity of a single die grows, more processing power and functional units can be accommodated on a single chip. A great diversity of different modules that were designed by different design groups and vendors are available for reuse. However, the design of such chips that make use of many different modules is extremely complicated. The main problem of the design is to connect these heterogeneous blocks together and to provide communication infrastructure between them.

This inter-block communication becomes the main bottleneck of the system. Until now the problem of inter-block communication on chip was solved by various shared-bus or other ad-hoc interconnection architectures. Shared-bus architectures do not meet the performance requirements of modern systems and become the limiting factor that degrades performance and elevates energy consumption. Other ad-hoc solutions become extremely expensive and complex. Global interconnect dominates the power and delay of modern VLSI systems and is becoming even more dominating over time as technology improves. Therefore, new generation of interconnection networks is required for constructing scalable multiprocessor systems that make good use of the available processing power.

Our research focuses on novel architectures of such interconnection networks for highly integrated systems on single chip or SoCs. We believe that today’s interconnection systems should be replaced by networked, multi-hop, packet-based communication architecture - Network on Chip (NoC). The communication protocol between modules will be completely changed and will be separated from computation tasks of the module. System modules will communicate by exchanging packets over the network. In addition global ad-hoc wires currently used for signaling will be eliminated and replaced by encoded packet carrying information over the network.

We define Quality of Service (QoS) and cost model for communications in Systems on Chip (SoCs), and derive related Quality-of-service Network on Chip (QNoC) architecture and design process. We show several design examples of our QNoC for typical SoC and compare to alternative solutions. Then we analyze the generic cost in area and power of Networks on Chip and alternative interconnect architectures. Analytical calculation quantifies the intuitive NoC scalability advantages.

We believe that Network on Chip offers a rich ground for research, it comprises many research fields, such as Computer Networks Design, VLSI Architectures, VLSI Circuit and Computer Aided Design.

The work is performed under supervision of Israel Cidon, Ran Ginosar and Avinoam Kolodny.

Presentation

Optimal Video Stream Multiplexing through Linear Programming
Dr. Ofer Hadar
Dept. of Communication Systems Engineering, Ben Gurion University

Rapid advantages in computer and telecommunication technologies have made integrated services packet-switched networks possible. It is expected that a significant portion of future networks will carry prerecorded video. Traffic in applications such as Video on Demand (VoD), will include high-fidelity audio, short multimedia clips, and full-length movies. In this talk I present different solutions for efficient multiplexing of several video streams with Variable Bit Rate (VBR), on a Constant Bit Rate (CBR) channel. The porpuse of these schemes is to maximize the number of streams transmitted simultaneously, such that the end users receive satisfactory service. I emphasis my talk on two solutions, video rate smoothing and statistical multiplexing with transcoding. An enhancement of the Piecewise Constant Rate Transmission and Transport (PCRTT) algorithm for reducing the burstiness of a video stream based on smoothing constant intervals is presented. In this talk I also present a new optimal multiplexing scheme for compressed video streams based on a piecewise linear approximation of the accumulative data curve of each stream. A linear programming algorithm is proffered, which takes into account different constraints of each client. It is shown that the algorithm succeeds in obtaining maximum bandwidth utilization with Quality of Service (QoS) guarantees. The algorithm takes into account the interaction between the multiplexed streams and the individual streams, and simultaneously finds the optimum total multiplexed schedule and individual stream schedules that minimizes the peak transmission rate. In addition, the algorithm, due to the linear programming formulation, is bounded in polynomial time. The simulation results show a significant reduction in peak rate and rate variability of the aggregated stream, compared to the non-smoothing case. Therefore the proposed scheme allows an increase in the number of simultaneously served video streams.

* This work is a joint research with Prof. Helman Stern from the Industrial Engineering Department at BGU.

Presentation

Decision Nodes in the Definition of Communication Components
Avigdor Willenz
Founder, Galileo Technologies

Network Architecture
Michael Laor
Director, Engineering, Cisco

Networks architecture is expected to undergo changes in the coming years while requirements for networks scalability and services is likely to continue to grow. Some of the drivers for those changes are the increased pressure on service providers to improve operation efficiency and revenue combined with the accelerated penetration of last mile broad band technologies (e.g. DSL, CABLE, FTTx).

Some of the more obvious examples are:

• Network architectures are consolidating around IP or MPLS for the delivering of both native L3 (data, voice and video) as well as for carrying and connecting exiting L2 media services. This for both wireless and wire line.
• VPN technologies, Both L2 and L3, are becoming increasingly popular in particular as broad band access penetration increases. This is an area of a significant growth. This growth however does not come without requirements for better security and better QoS.
• Technologies such as PsuedoWire over IP enable new service paradigms over the PSN infrastructure.

This talk will attempt to provide an overview of those trends as well as to describe in some more details few of the involved technologies mentioned (VPNs, PW) and discuss the scalability challenges they represent. Some of those challenges may require re-thinking of today's "common wisdom".

Building and Validating Intrusion-Tolerant Distributed Systems
Dr. Adnan Agbaria
Coordinated Science Laboratory, University of Illinois at Urbana-Champaign

This talk provides an infrastructure for building intrusion-tolerant and dependable distributed systems and a methodology for validating the survivability of the infrastructure using probabilistic modeling. The architecture described provides intrusion-tolerant and dependable services through security domains, replication, and diversity, where the type and degree of replication is managed dynamically, depending on the needs of applications. The architecture uses middleware to provide fault- and intrusion-tolerance mechanisms and group communication services to distributed applications transparently as directed by an application. The architecture thus raises the level of abstraction at which a programmer thinks about impairments to service higher, allowing an application programmer high-level control over the type of attacks and faults that should be tolerated and the level of survivability desired from a remote object or processes. The validation is done using a set of stochastic activity network models and the Mobius Modeling tool. The talk argues that intrusion tolerance is an effective way to build survivable and secure systems, and that probabilistic modeling is an effective means to quantifying their survivability.

Exposing and Eliminating Vulnerabilities to Denial of Service Attacks in Secure Gossip-Based Multicast
Gal Badishi
Dept. of Electrical Engineering, Technion

We propose a framework and methodology for quantifying the effect of denial of service (DoS) attacks on a distributed system. We present a systematic study of the resistance of gossip-based multicast protocols to DoS attacks. We show that even distributed and randomized gossip-based protocols, which eliminate single points of failure, do not necessarily eliminate vulnerabilities to DoS attacks.

We propose Drum - a secure gossip-based multicast protocol that eliminates such vulnerabilities. Drum was implemented in Java and tested on a large cluster. We show, using closed-form mathematical analysis, simulations, and empirical tests, that Drum survives severe DoS attacks, while traditional gossip-based protocols collapse even under mild attacks.

Joint work with Amir Sasson and Idit Keidar.

On the Expected Payment of Mechanisms for Task Allocation
Dr. Amir Ronen
Dept. of Industrial Engineering and Management, Technion

We study a representative task allocation problem called shortest paths: Given is a graph in which the edges are owned by self interested agents and a distribution on the edge costs. The goal is to design a mechanism (protocol) which acquires a cheap $s-t$ path. We first observe that the class of generalized VCG mechanisms has desired monotonicity properties. We exploit this observation to obtain, under an independence assumption, expected payments which are significantly lower than the worst case bounds of \cite{AT02,ess03}. We then investigate whether these payments can be improved when there is competition among paths. Surprisingly, we give evidence to the fact that typically such competition hardly helps incentive compatible mechanisms. In particular, we show this for the celebrated VCG mechanism. We then construct a novel general protocol combining the advantages of incentive compatible and non-incentive compatible mechanisms. Under reasonable assumptions on the agents we show that the overpayment of our mechanism is very small.

Presentation

Paper

Building a Good Startup - Is There a Recipe?
Aharon Aharon
Chairman of the Board, Discretix Technologies

Aharon will review his experience in IBM, Zoran, Seabridge, Discretix and the VC industry and will put together his perspective on the ingredients needed for building a successful startup. In particular Aharon will address the Team, Technology and Market, as well as issues which are specific to Israel and the opportunities (or threats) we face.

Presentation