ClubNet Spring 2004

ClubNet Main Page
ClubNet Winter 2003/4
ClubNet Spring 2003
ClubNet Winter 2002/3
ClubNet 2001/2
ClubNet 1999
ClubNet 1997/8

Polygonal Broadcast, Secret Maturity and the Firing Sensors
Prof. Shlomi Dolev
Dept. of Computer Science, Ben-Gurion University of the Negev

This work considers communication among sensors that are spread in a geographic region. Each sensor is a computing device with severe resources limitations, low power, slow processing and small memory. The devices are distributed (uniformly) in the geographic region. Broadcast, flooding and sense of direction procedures that fit the special characteristics of the system will be presented. The procedures use imaginary tiling of the plane.

The broadcast procedures are used by a sensor for distributing secrets that activate the sensors simultaneously at a particular time without revealing the nature of the upcoming activity.

Joint work with Ted Herman and Limor Lahiani.

Presentation

How Fair Is Your Queue
Prof. Hanoch Levy
School of Computer Science, Tel-Aviv University

How should customers be served in a queue in order to grant them fair service? Most ordinary persons may consider the First-in-First-Out (FIFO) as the most fair policy and Last-in-First-Out (LIFO) as the most unfair policy. In contrast, some recent queueing studies suggest exactly the opposite, namely that LIFO (preemptive) is "always fair" and FIFO is "always unfair". Such queueing scheduling issues and many others show up in a large variety of applications in computer systems, Web servers and public or private facilities.

Recent studies show that fairness in queues is very important to humans, perhaps not less than the waiting itself. Further, many common queue disciplines (e.g. a special queue for short jobs in a supermarket) are being justified under the "cause of fairness". In fact, perhaps the most important cause for using a queue at all, is "fairness" among the queue users.

Nonetheless, Queueing Theory that has been developed for several decades, has hardly dealt with this issue, and an agreed upon measure of queueing fairness does not exist. The objective of this work is to understand queue fairness and develop a fairness measure that can be used by theorists and practitioners to evaluate the fairness level (and thus quality) of their system.

We propose a Resource Allocation Queueing Fairness Measure (RAQFM) which is unique in accounting for the intricate relations between jobs within the queue. RAQFM is sensitive to both seniority and service requirements. RAQFM also yields itself to analysis via common queueing-theory machinery. Lastly, RAQFM can bridge the major conceptual gap presented above, between the beliefs of ordinary people (FIFO more fair than LIFO) and recent queueing theory results (LIFO more fair than FIFO). We analyze RAQFM and demonstrate its properties.

* Background in Queueing Theory is not required. Practical Experience (e.g. in supermarkets) is welcome.

Joint work with Benjamin Avi-Itzhak and David Raz.

Presentation

A General Approach to Online Network Optimization Problems
Prof. Seffi Naor
Dept. of Computer Science, Technion

We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem, we have a communication network known to an on-line algorithm in advance. What is not known in advance are the bandwidth or connectivity demands between nodes in the network. The demands (or requests) are given to the online algorithm one by one.

We consider several classical network design problems in this framework, among them: the set cover problem, non-metric facility location problem, the multicast tree problem, and the group Steiner problem. Our algorithms are based on a unified framework for designing online algorithms for problems involving connectivity and cuts. We first present a general $O(\log m)$-deterministic algorithm for generating a fractional solution that satisfies the online connectivity or cut demands, where $m$ is the number of edges in the network. This may be of independent interest for solving fractional online bandwidth allocation problems, and is applicable to node versions as well. The integral solutions are obtained by an online rounding of the fractional solution, and we obtain randomized polylogarithmic competitive factors for the problems we consider. This part of the framework is problem dependent, and applies various tools including results on the approximate max-flow min-cut for multicommodity flow, the HST method and its extensions, certain rounding techniques for dependent variables, and Raecke's new hierarchical decomposition of graphs.

Joint work with: Noga Alon, Baruch Awerbuch, Yossi Azar, and Niv Buchbinder.

Presentation

Packet Delay in Optical Circuit-Switched Networks
Prof. Zvi Rosberg
Dept. of Communication Systems Engineering, Ben Gurion University

A general framework is provided for the evaluation of packet delay distribution in an optical circuit-switched network allowing for an arbitrary quality of service (QoS) provisioning and adaptive routing and wavelength assignment (RWA) algorithm with two-way reservation. The framework consists of a fluid model, packet queueing in edge routers, and circuit-switched transmission between edge routers. Packets are assigned to different logical buffers at the edge routers based on their QoS classes and destinations. Circuit holding times could be fixed or queue-length dependent. Slack variables are introduced in the analysis to decouple between the edge buffers so that each queue length evolution remains consistent with its evolution in the network. While exact delay distribution results are obtained for a single decoupled buffer, approximations are provided for a network. The latter is done by finding a fixed point solution to a set of equations that relate the slack variables to the specific RWA algorithm. An analysis of a randomized threshold algorithm, which allocates circuits as a function of the buffer sizes, threshold values and randomized factors, is given as an illustrative example. The analytical results are confirmed by simulations and are shown to be in good agreement with the simulation model.

Joint work with Andrew Zalesky and Moshe Zukerman.

Presentation Paper

A Generic Quantitative Approach to the Scheduling of Synchronous Packets in a Shared Medium Wireless Access Network
Prof. Reuven Cohen
Dept. of Computer Science, Technion

We present a scheme for allocating unsolicited grants to the end hosts of synchronous applications of a wireless access network, in accordance with the condition of the channel, the importance of each packet and the specific loss recovery mechanism employed in the channel. The proposed scheme is generic in the sense that it maximizes the effectiveness of the channel under various conditions and it can be used along with every FEC-based or retransmission-based error recovery strategy.

Joint work with Liran Katzir.

Paper

Compact Routing and Locality in Peer-to-Peer Systems
Ittai Abraham
The Institute of Computer Science, The Hebrew University of Jerusalem

Distributed hash tables are peer-to-peer systems that provide efficient routing and location services for shared objects. We study constructions that are locality aware. Our aim is to minimize stretch, the ratio between the cost of locating an object and its distance. The underlying problem that arises is one of name independent compact routing.

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a $\widetilde{O} (\sqrt{n})$ space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long at the shortest paths. This is optimal in a very strong sense. It is known that no compact routing using $o(n)$ space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires $\Omega(\sqrt{n})$ space per node.

The second result is for a special class of metric spaces that are growth bounded. For this realistic class of metrics, we propose the first peer-to-peer network and lookup algorithm with arbitrarily low stretch $1 + \varepsilon$ for any $\varepsilon > 0$. The construction uses an expected logarithmic number of links for each node.

The first result is a joint work with Gavoille, Malkhi, Nisan, and Thorup. The second result is joint work with Malkhi and Dobzinski.

Paper Paper

QoS Provisioning in Wireless Networks
Hwee Pink Tan
Dept. of Electrical Engineering, Technion

Wireless scheduling plays an important role in the design of next generation wireless networks as it determines the QoS provisioning over the wireless link. Compared to its wired counterpart, the design of wireless schedulers is a harder and more challenging problem due to the unique characteristics of the wireless channel. While recent work focused on the design of wireless schedulers to meet specific performance objectives, our research aims to characterize the QoS performance of a generic wireless scheduler in a downlink centralized scheduling scenario, assuming a Markov-based wireless channel. We present our approach to achieve the above objective, and illustrate the trade-off amongst QoS metrics, wireless scheduler and receiver design in various scheduling scenarios using numerical results.

Presentation

Protection On-Demand: Ensuring Resource Availability
Dr. Dan Touitou
Cisco

While a number of different tools and technologies exist that claim to protect enterprise networks from flooding attacks, such as distributed denial-of-service (DDoS) attacks, none of these solutions deliver the comprehensive protection that organizations need to ensure uninterrupted business continuity and resource availability. The reason: these solutions either focus on detection (such as intrusion detection systems), or they employ primitive, indiscriminate filtering techniques that block good traffic as well as bad, effectively completing the hacker’s job. A true DDoS protection solution must provide both detection and mitigation services that preserve business integrity. This talk introduces an attack mitigation technology that ensures continued service availability even while under DDoS attacks by combining unique on-demand attack traffic “diversion” techniques with a mechanism that filters “bad” (illegitimate) packets while forwarding “good” (legitimate) packets to the intended server. This method minimizes demand on router resources and does not introduce additional elements onto the normal data path, minimizing the impact on normal network operation or performance. This unique method cleans DDoS traffic at both the ISP and data center levels as well as at the entrance to large enterprises. Various configurations and scenarios for DDoS protection will be presented and discussed.

Dr. Philip M. Merlin Memorial Lecture - Internet Security Technologies
Marius Nacht
Senior Vice President and Founder, Check Point Software Technologies Ltd.

InfiniBand and Opportunities for Storage Solutions
Michael Kagan
Vice President of Architecture, Mellanox Technologies

Presentation

Ensuring End-to-End QoS in the DiffServ Model - Feasibility and Efficiency
Dr. Danny Raz
Dept. of Computer Science, Technion

Differentiated Services (or just DiffServ) is a very scalable architecture for delivering QoS in the Internet. This scalability is achieved by maintaining a per-class (and not a per-flow) state at the core routers. However, this exact property also makes ensuring end-to-end QoS very difficult, since one has to verify that the local resources allocated to each class are sufficient to support the requirements of all the flows in that class. This is particularly challenging when considering accumulative requirements such as delay or loss. This talk addresses two aspects of this problem.

First we address the translation of the end-to-end delay requirements of flows to a specific resource allocation at the different routers. The required end-to-end QoS level is usually specified in a Service Level Agreement (SLA). The problem is thus to find a way that maximizes the number of flows for which the delay specified in the SLA is satisfied in congested conditions. The work evaluates the importance of both local algorithms that guarantee a constant ratio between local waiting times of packets belonging to different service classes, and global probing techniques that allow classifying the packets into the different service classes according to their SLA defined delay, in maximizing the number of flows for which the delay constraint is satisfied.

Then we concentrate on the probing mechanism, trying to minimize the amount of overhead needed. We propose a new probing technique called, Adaptive Probing, in which the routers along the flow path are responsible to discover and notify a centralized entity when a violation of the SLA occurs (or soon to occur). We study the performance of this new algorithm through theoretical analysis and extensive simulations. Our results indicate that in addition to dramatically reducing the load from the centralized entity, the amount of network traffic needed is relatively small, and this new monitoring scheme scales well both with the number of hops and the network load.

This talk is based on joint works with Alex Dvorkin, Constantine Elster, and Ran Wolff.

Presentation

An Efficient Short Messages transmission in Cellular Networks
Dr. Zohar Naor
University of Haifa

A method for efficient short messages transmission in cellular networks is presented in this talk. The number of Short Message Service (SMS) messages is growing very rapidly, and existing cellular networks have to support a large number of SMS and signaling messages. The rate of SMS messages has already exceeded the rate of E-mail messages transmitted through the Internet, and their number keeps growing. SMS messages are characterized by a burst of a short, single packet message. Unfortunately, the protocols currently used by existing cellular networks cannot support this type of traffic efficiently. For this reason, SMS messages are currently transmitted through the signaling channel. Clearly, this usage of the signaling channel is far from being optimal, in terms of network resources utilization. Under certain conditions, it may even block the signaling channel. This study proposes to use a Load-Adaptive Multiple Access with Congestion Avoidance ($LAMA/CA$) for efficient short messages transmission in cellular networks. The $LAMA/CA$ protocol is more stable, and much more efficient for transmitting SMS messages and signaling messages, than the existing method currently used in cellular networks. Moreover, the proposed method is superior to a collision-free protocol that uses a Request To Send ($RTS$) and Clear To Send ($CTS$) mechanism, over the range of packet lengths used for SMS messages and signaling messages.

Presentation

Research at Intel - A Glimpse to the Future
Yossi Levy
Israel Research Sector Director, Intel

Intel Israel is celebrating its 30th birthday. A short overview of Intel operations in Israel will precede the main topic of Research at Intel. Intel's research efforts are expanding the boundaries of computing and communications technology. Our world class research in silicon and advanced process technology and manufacturing has helped us to achieve and maintain our industry leadership position. Our microprocessor research continues to advance the state of the art and extend Moore's law. Our recent explorations into disruptive technology are driving toward a future of proactive computing, in which billions of embedded devices throughout the environment will anticipate our needs and, sometimes, take action on our behalf. The presentation will open a window into some of this research work.