Networking Seminar Artzi 2005

Cisco Systems, Natanya, Israel

Thursday, February 10 2005, 12:15PM - 17:00PM


You are invited to join us for a Seminar Artzi on Networking hosted by Cisco Systems at Natanya. We hope to bring together researchers and technologists in networking and communications from the Israeli Academy and High-Tech industry for a half day seminar on networking.


Participation is free.



12:15 -- 1:15

*** Gathering & Lunch, provided on site ***


 1:15  -- 1:45

The Power Challenge

Garry Epps,

Cisco Systems

 1:45  -- 2:15

Algorithmic Approaches and Challenges in QoS Routing

Ariel Orda,

The Technion

 2:15  -- 2:40

Online packet switching - competitive algorithms

Yossi Azar,

Tel-Aviv University

 2:40  -- 3:05

The Relative Queuing Delay of Parallel Packet Switches

Hagit Attiya,

The Technion

 3:05  -- 3:35

***  Coffee   break   ***



 3:35  -- 4:00

Sizing Router Buffers

Isaac Keslassy,

The Technion

 4:00  -- 4:25

Controlling Spam by Secure Internet Content Selection

Amir Herzberg,

Bar-Ilan University

 4:25  -- 4:50

DIMES, a distributed Internet measurement infrastructure: rational, architecture, and some results

Yuval Shavitt,

Tel-Aviv University


Driving instructions:  1.  see MAP,  2.  Cisco is also close to Beit-Yehoshua train station, 5 minutes taxi ride.


Parking instructions:  See the map to get to the corner of Gad Manela and HaMelacha St.  (Which is the north end of HaMelacha St.) In that corner enter (to the west) a parking floor which is under the Cisco building. Immediately after the guard turn left (*** ignore the sign "Parking for Minuyim only") and park around pillar 14 (AGAIN *** Ignore the sign "Cisco Parking" around pillar 3) Take the elevator to floor 1 (not Het-1) and enter Cisco.  (Notice, if you come from the south there is an exit from Haif-Tel-Aviv Road #2 to Shalom Aleichem St, thus you do not have to go through the IKEA/Poleg intersection (from the north you have to go through the IKEA/Poleg junction).



"The Power Challenge"  1:15  --  1:45
Garry Epps, Cisco Systems Inc.

High-end commercial routers must continue to scale and evolve to meet customer demands.  We do this with architectural innovation and application of the latest semiconductor technologies. This presentation will outline how power has become one of the biggest issues facing us, and then introduce some interesting research Cisco is participating in which might lead to a long-term solution to this.


"Algorithmic Approaches and Challenges in QoS Routing"  1:45  --  2:15
Ariel Orda, The Technion.


A major issue in the design of broadband architectures is how to provide the resources in order to meet the requirements of each connection, and, moreover, how to meet this goal in a networkwide efficient manner. QoS routing is, undoubtedly, one of the major building blocks in such architectures. However, QoS routing poses several major algorithmic challenges, such as intractability, scalability and uncertainty.  Moreover, a successful QoS routing scheme should smoothly integrate with other QoS-enabling mechanisms, most notably schedulers. These major challenges call for novel algorithmic approaches and solution schemes.

We shall overview some typical problems and solution approaches, focusing on three representative models. The first is a "basic" model, where each network element can offer a certain degree of QoS at a certain "cost". In the second, "extended" model, each network element may offer various degrees of QoS, at different "costs". Finally, in the "coupled" model, the tasks of routing and scheduling are tackled together, hence providing a more precise assessment of the actual consumption of resources. We shall focus on solution schemes that provide proven performance guarantees within efficient (polynomial) time complexity for general network topologies. We shall overview several approaches for improving scalability, with a particular focus on precomputation schemes. We shall indicate how this algorithmic framework can address problems of special practical interest, such as the need to cope with state uncertainty.

Online packet switching - competitive algorithms   2:15  --  2:40

Yossi Azzar Tel-Aviv University


The online problem of throughput maximization in packet-switching networks has been studied intensively during recent years. In such problems packets arrive online, each marked with a value, and the goal is to maximize the total value of delivered packets subject to limited buffer space. I will survey the area and discuss the following three results for switching systems. 

1. The zero-one principle for switching networks. By this principle, a comparison-based algorithm for any switching model achieves $c$-approximation if and only if it achieves $c$-approximation with respect to all 0/1 sequences.
2. A general reduction that transforms any $c$-competitive algorithm for a single queue into a $2c$-competitive algorithm for a multi-queue switch.
3. The first constant-competitive algorithm for the CIOQ (Combined Input and Output Queued) switching model, that is the most general model studied to date for approximation or competitive measure.


The talk is based on the following papers (joint work with Y. Richter):
"Management of Multi-Queue Switches In QoS Networks" (STOC03),
"The Zero-One Principle for Switching Networks" (STOC04),
"An improved algorithm for CIOQ switches" (ESA04).

The Relative Queuing Delay of Parallel Packet Switches   2:40 -- 3:05

Hagit Attiya, The Technion

Abstract: A parallel packet switch (PPS) serves as the core of many contemporary commercial switches.  This talk discusses the inherent queuing delay and delay jitter introduced by a PPS, relative to an optimal work-conserving switch.  We present (upper and lower) bounds depending on the amount of information and buffers available to the PPS demultiplexing algorithm, which is responsible for dispatching cells to the middle-stage switches.

Sizing Router Buffers    3:35  --  4:00

Isaac Keslassy, The Technion

Abstract:  All Internet routers contain buffers to hold packets during congestion.  Today, the size of the buffers is determined by the dynamics of TCP.  A widely used rule-of-thumb states that each link needs a buffer of size B = RTT X C, where RTT is the average round-trip time of a flow passing across the link, and C is the data rate of the link.  For example, a 10Gb/s router linecard needs up to 250ms X 10Gb/s = 2.5Gb of buffers.  Such large buffers are challenging for router manufacturers, who must use large, slow, off-chip DRAMs. And queueing delays can be long,  have high variance, and may destabilize the congestion control algorithms.

In this talk, I will take the (controversial) stand that this rule-of-thumb B = RTT X C is now outdated and incorrect for backbone routers because of multiplexing effects. I will show that a link with n flows
requires no more than B =(RTT X C) / sqrt{n}. The consequences on router design are enormous: A 10Gb/s link carrying 50,000 flows requires only 10Mb of buffering, or 0.4% of the widely used value.
This new value can easily be implemented using fast, on-chip SRAM.

Controlling Spam by Secure Internet Content Selection  4:00  --  4:25

Amir Herzberg, Bar-Illan University.

Abstract:  Unsolicited and undesirable e-mail (spam) is a growing problem for Internet users and service providers. We present the Secure Internet Content Selection (SICS) protocol, an efficient cryptographic mechanism for spam-control, based on allocation of responsibility (liability).  SICS may be deployed by end users and/or by mail service providers, and provides value even when deployed by one or two parties involved.  With SICS, e-mail is sent (and/or forwarded) with a content label, and a cryptographic protocol ensures labels are authentic and penalizes falsely labeled e-mail (spam). The protocol supports trusted senders/servers (penalized by loss of trust) and unknown senders/servers (penalized financially).  The recipient (or intermediary) can determine the compensation amount for falsely labeled e-mail (spam). SICS is practical, with negligible overhead, gradual adoption path, and use of existing relationships; it is also supports privacy (including encrypted e-mail) and legitimate commercial e-mail. SICS improves on other crypto-based proposals for spam controls, and complements non-cryptographic spam controls.

DIMES, a distributed Internet measurement infrastructure: rational, architecture, and some results     4:25  --  4:50

Yuval Shavitt, Tel-Aviv University


Abstract:  Due to the Internet structure and routing the only way to map its topology is by having measurement presence in almost every corner of the Internet. Managing thousands of measurement boxes is impractical, thus, we suggest instead a light software measurement agent to be downloaded by volunteers around the world. The DIMES agent can be executed on every PC (and in the future even smaller devices, like PDAs) and enable us to map the Internet and track its evolution in time in several levels of granularity from the fine router level to the coarse Autonomous System (AS) level. We can already report, after only four months of deployment, 30% new inter-AS connections that were revealed by DIMES. Our measurements can be extended to include not only connectivity and delay (like today) but also bandwidth, loss, jitter, etc. The talk will describe the motivation to DIMES, description of our initial results, and our future vision for an Internet that measure itself.


Looking forward to your participation in the seminar!


Yehuda Afek,  Tel-Aviv University,

David Belz, Cisco Systems,

Israel Cidon, The Technion