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.
Gathering & Lunch, provided on site ***
Oriented, Policy-based Network Management Innovation
- New Model of Internet Topology Using k-shell Decomposition
Coffee break ***
Emulation of Output-Queued Switches
and Self-Organizing Distributed Algorithms"
Ben Gurion University
Driving instructions: 1. seeMAP,
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"
-- 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
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" -- Scott Kirkpatrick, The Hebrew University.
decomposition of a random graph provides a different and
more insightful separation of the roles of the different nodes
such a graph than does the usual analysis in terms of node
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
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
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
structure. Our k-shell analysis may also be relevant for
the function of nodes in the "scale-free" graphs
other naturally-occurring processes.
Multipath Routing --
Banner, The Technion
Current survivability schemes typically offer two degrees
of protection, namely fullprotection (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:45
Hay, The Technion
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
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
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
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
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
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
of O(log2 n) rounds.
Edward Bortnikov, The Technion.
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
forward to your participation in the seminar!