2nd Networking Seminar Artzi 2006

Cisco Systems, Natanya, Israel

Monday, April 3rd 2006, 12:30PM - 16:45PM


You are invited to join us for the 2nd 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:30 1:30

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


 1:30  -- 2:00

Service Oriented, Policy-based Network Management Innovation

Cliff Meltzer,

Cisco Systems

 2:00  -- 2:30

MEDUSA - New Model of Internet Topology Using k-shell Decomposition

Scott Kirkpatrick,

The Hebrew University

 2:30  -- 3:00

Multipath Routing

Ron Banner,

The Technion

 3:00  -- 3:15

***  Coffee   break   ***



 3:15  -- 3:45

Packet-Mode Emulation of Output-Queued Switches

David Hay,

The Technion

 3:45  -- 4:15

Self-Stabilizing and Self-Organizing Distributed Algorithms"

Shlomi Dolev,

Ben Gurion University

 4:15  -- 4:45

Nomadic Service Points

Edward Bortnikov,

The Technion


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, there is an exit from Haifa-Tel-Aviv Road #2 to Shalom Aleichem St, thus you do not have to go through the IKEA/Poleg intersection).



" Service Oriented, Policy-based Network Management Innovation"  1:30  --  2:00
Cliff Meltzer, Cisco Systems Inc.


The IT industry has wrestled with the complexity of managing networked IT systems in the context of enterprise business objectives for years. However IT managers are now faced with even higher expectations from their end customers and intense competition that requires them to look at new business models, pricing, and productivity, holistically across the entire IT networked infrastructure. Challenges faced by enterprises such as real-time response to end user requests, market demands, cost-management and technology investment protection, and compliance to corporate business policies are all factors driving an evolution in network management.

In this overview presentation, we will discuss innovative network management technology Cisco is developing to address Service Oriented Network Architectures. As the IT industry increasingly moves from static to more dynamic, on-demand resource allocations, service oriented, policy-based management technology will play an integral part in enabling business objectives and facilitating a more responsive IT environment. We will illustrate how several new management technologies will support the need for heightened, end-to- end visibility and intelligent control which will enable better integration of business and IT objectives. In turn, how these enabling technologies will reduce costs, improve productivity, and increase business growth and agility making the network a powerful platform for business optimization.


" MEDUSA - New Model of Internet Topology Using k-shell Decomposition"  2:00  --  2:30
Scott Kirkpatrick, The Hebrew University.


The k-shell decomposition of a random graph provides a different and
   more insightful separation of the roles of the different nodes in
   such a graph than does the usual analysis in terms of node degrees.
   We develop this approach in order to analyze the Internet's
   structure at a coarse level, that of the "Autonomous Systems" or
   ASes, the subnetworks out of which the Internet is assembled. We
   employ new data from DIMES, a distributed agent-based mapping effort
   which at present has attracted over 4200 volunteers running more
   than 8600 DIMES clients in over 85 countries. We combine this data
   with the AS graph information available from the RouteViews project
   at Univ. Oregon, and have obtained an Internet map with far more
   detail than any previous effort.

   The data suggests a new picture of the AS-graph structure, which
   distinguishes a relatively large, redundantly connected core of
   nearly 100 ASes and two components that flow data in and out from
   this core. One component is fractally interconnected through peer
   links; the second makes direct connections to the core only. The
   model which results has superficial similarities with and important
   differences from the "Jellyfish" structure proposed by Tauro et al.,
   so we call it a "Medusa." We plan to use this picture as a framework
   for measuring and extrapolating changes in the Internet's physical
   structure. Our k-shell analysis may also be relevant for estimating
   the function of nodes in the "scale-free" graphs extracted from
   other naturally-occurring processes.

Multipath Routing   2:30  --  3:00

Ron Banner, The Technion


Current survivability schemes typically offer two degrees of protection, namely full protection (from a single failure) or no protection at all. Full protection translates into rigid design constraints, i.e. the employment of disjoint paths. We introduce the concept of tunable survivability that bridges the gap between full and no protection. First, we establish several fundamental properties of connections with tunable survivability. With that at hand, we devise efficient polynomial (optimal) connection establishment schemes for both 1:1 and 1+1 protection architectures. Then, we show that the concept of tunable survivability gives rise to a novel hybrid protection architecture, which offers improved performance over the standard 1:1 and 1+1 architectures. Next, we investigate some related QoS extensions. Finally, we demonstrate the advantage of tunable survivability over full survivability. In particular, we show that, by just slightly alleviating the requirement of full survivability, we obtain major improvements in terms of the "feasibility" as well as the "quality" of the solution.

Packet-Mode Emulation of Output-Queued Switches   3:15 -- 3:45

David Hay, The Technion

Abstract: Most common network protocols (e.g., the Internet Protocol)
work with variable size packets, whereas contemporary switches
still operate with fixed size cells, which are easier to transmit and
buffer. This necessitates packet segmentation and reassembly modules,
resulting in significant computation and communication overhead
that might be too costly as switches become faster and bigger.

In this talk we consider an alternative mode of scheduling,
in which packets are scheduled contiguously over the switch fabric.

Specifically, we study such packet-mode scheduling for the combined
input output queued (CIOQ) switch architecture and investigates its cost.
We introduce frame-based schedulers that allow a packet-mode CIOQ
switch with small speedup to mimic an ideal output-queued switch with
bounded relative queuing delay.
The schedulers are pipelined and are based on matrix decompositions.

Self-Stabilizing and Self-Organizing Distributed Algorithms    3:45  --  4:15

Shlomi Dolev, Ben Gurion University

Abstract Self-stabilization ensures automatic recovery from an arbitrary state;
we define self-organization as a property of algorithms which
display local attributes. More precisely, we say that an algorithm is
self-organizing if (1) it converges in sublinear time and (2) reacts ``fast'' to
topology changes. If s(n) is an upper bound on the convergence time and d(n)
is an upper bound on the convergence time following a topology change, then
s(n) Îo(n) and d(n)Îo(s(n)).
The self-organization property can then be used for gaining,
in sub-linear time, global properties and reaction to
changes. We present self-stabilizing and self-organizing algorithms
for many distributed algorithms, including distributed snapshot and
leader election.

We present a new randomized self-stabilizing distributed algorithm for
cluster definition in communication graphs of
bounded degree processors. These graphs reflect sensor networks
deployment. The algorithm converges in
O(log n) expected number of rounds, handles dynamic changes locally
and is, therefore, self-organizing. Applying the clustering algorithm
to specific classes of communication graphs,
in $O(log n) levels, using an overlay network abstraction, results in a
self-stabilizing and self-organizing distributed algorithm for hierarchy

Given the obtained hierarchy definition, we present an algorithm for
hierarchical distributed snapshot. The algorithms are based on a new
basic snap-stabilizing snapshot algorithm, designed for message passing
systems in which a distributed spanning tree is defined and in which
processors communicate using bounded links capacity. The algorithm is
on-demand self-stabilizing when no such distributed spanning tree is
defined. Namely, it stabilizes regardless of the number of snapshot

The combination of the self-stabilizing and self-organizing
distributed hierarchy construction and the snapshot algorithm form an efficient
self-stabilizer transformer. Given a distributed algorithm
for a specific task, we are able to convert the algorithm into a
self-stabilizing algorithm for the same task with an expected convergence time
of O(log2 n) rounds.

Nomadic Service Points  4:15  --  4:45

Edward Bortnikov, The Technion.

Abstract:  We consider the novel problem of dynamically assigning application sessions of mobile users or user groups to service points. Such assignments must balance the tradeoff between two conflicting goals. On the one hand, we would like to connect a user to the closest server, in order to reduce network costs and service latencies. On the other hand, we would like to minimize the number of costly session migrations, or handoffs, between service points. We tackle this problem using two approaches. First, we employ algorithmic online optimization to obtain algorithms whose worst-case performance is within a factor of the optimal. Next, we extend them with opportunistic versions that achieve excellent practical average performance and scalability. We conduct case studies of two settings where such algorithms are required: wireless mesh networks with mobile users, and wide-area groupware applications with or without mobility.


Looking forward to your participation in the seminar!


Yuval Shavitt,  Tel-Aviv University,

Reuven Cohen, The Technion