Israeli Networking Seminar 2007



Cisco Systems, Natanya, Israel


Thursday, March 15 2007




You are invited to join us for the 3rd Israeli Networking Seminar 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:00 – 13:00

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


 13:00  - 13:45

 Routing and Addressing issues in the Internet

 David Ward

 Cisco Fellow 

 13:45  - 14:10


Algorithmic Aspects of Radio Access Networks Design in 4G Cellular Networks

 Dudu Amzallag

 The Technion

 14:10  - 14:35

Efficient TCAM-based Classification using Gray Coding

 Danny Hendler 

 Ben Gurion University

 14:35 -  15:05


Zooming in on Network-on-Chip Architectures

 Israel Cidon

 The Technion

 15:05 -  15:25

***  Coffee   break   ***



 15:25 -  15:50


Acyclic Type of Relationships between Autonomous Systems

 Rami Cohen

 The Technion

 15:50 -  16:15


The OD Cycles Approach for Survivable Converged  Networks


 Meir Herzberg


 16:15 -  16:30


Short talk: Transmission Scheduling for Mass Transit in Data Wireless Networks


 Elisha Rosensweig

 CS Tel-Aviv University

 16:30 -  16:45


Short talk: A simulation Study of Multi-Color Marking of TCP Aggregates


 Miriam Allalouf

 EE 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 12 or so (AGAIN *** Ignore the sign "Cisco Parking" around pillar 3).  Take the elevator to floor 1 (not Het-1) and enter Cisco.






Algorithmic Aspects of Radio Access Networks Design in 4G Cellular Networks, 13:45  - 14:10
Dudu Amzallag

The Technion



The forthcoming 4G cellular systems will provide broadband wireless access to a variety of advanced data and voice services. In order to do that, these networks will have a significantly larger number of base stations and a much higher bandwidth demand from their radio access networks. This will motivate operators to replace the commonly used star based architecture, in which a Radio Network Controller (RNC) is connected to a set of base stations via direct links, with a more complex tree structure, where a base station can be connected to an RNC via other base stations.

In this work we address algorithmic aspects of this challenging design problem, in which tree-topology is used to connect base stations and RNCs. We formulate the problem as an optimization problem and prove that it is NP-hard to approximate it in the general case. For the metric case, however, we develop an O(log n)-approximation algorithm. We then study the performance of this algorithm and several other heuristics in practical scenarios. Our results indicate that a combination of a certain greedy heuristic and the proven approximation algorithm, generates a solution that produces close to optimal results in practical scenarios and can be efficiently computed for sufficiently large network sizes.

This is a joint work with Seffi Naor and Danny Raz. This work is to appear in IEEE INFOCOM 2007.


Efficient TCAM-based Classification using Gray Coding, 14:10-14:35


Danny Hendler 

Ben Gurion University



Ternary content-addressable memories (TCAMs) are increasingly used for high-speed packet classification. TCAMs compare packet headers against all rules in a classification database in parallel and thus provide high throughput unparalleled by software-based solutions.

TCAMs are not well-suited, however, for representing rules that contain range fields. Such rules have to be represented by multiple TCAM entries. The resulting range expansion can dramatically reduce TCAM utilization.

The majority of real-life database ranges are short. We present a novel algorithm called short range gray encoding (SRGE) for the efficient representation of short range rules. SRGE encodes range borders as binary reflected gray codes and then represents the resulting range by a minimal set of ternary strings. SRGE is database independent and does not use TCAM extra bits.

For the small number of ranges whose expansion is not significantly reduced by SRGE, we use dependent encoding that exploits the extra bits available on today's TCAMs. Our comparative analysis establishes that this hybrid scheme utilizes TCAM more efficiently than previously published solutions. The SRGE algorithm has worst-case expansion ratio of 2W-4, where W is the range-field length. We prove that any TCAM encoding scheme has worst-case expansion ratio W or more.

This is a joint work with Anat Bremler-Barr (IDC). This work is to be presented in IEEE INFOCOM 2007.

Zooming in on Network-on-Chip Architectures,14:35-15:05

Israel Cidon

Department of Electrical Engineering

The Technion



The aim of this presentation is to expose the networking community to the concept of Network-on-Chip (NoC)}, an emerging field of study within the VLSI realm, in which networking principles play a significant role, and new network architectures are in demand. NoC architectures pose new challenges in exploring solutions to traditional problems such as routing, quality-of-service, and reliability, in unfamiliar settings under new constraints.

In addition, a new set of problems that are specific to NoCs such as, network design process, power optimization and special functionalities will also be discussed.

Acyclic Type of Relationships between Autonomous Systems, 15:25-15:50

Rami Cohen

The Technion



The Internet connectivity in the Autonomous System (AS) level reflects the commercial relationship between ASes. A connection between two ASes could be of type customer-provider when one AS is a provider of the other AS, or of type peer-peer, if they are peering ASes. This commercial relationship induces a global hierarchical structure which is a key ingredient in the ability to understand the topological structure of the AS connectivity graph. Unfortunately, it is very difficult to collect data regarding the actual type of the relationships between

ASes, and in general this information is not part of the collected AS connectivity data. The Type of Relationship (ToR) problem attempts to address this shortcoming, by inferring the type of relationship between connected ASes based on their routing policies. However, the approaches presented so far are local in nature and do not capture the global hierarchical structure.

In this work we define a novel way to infer this type of relationship from the collected data, taking into consideration both local policies and global hierarchy constrains. We define the Acyclic Type of Relationship AToR  problem that captures this global hierarchy and present an efficient algorithm that allows determining if there is a hierarchical assignment without invalid paths. We then show that the related general optimization problem is NP-complete and present a 2/3 approximation algorithm where the objective function is to minimize the total number of local policy mismatches. We support our approach by extensive experiments and simulation results showing that our algorithms classify the type of relationship between ASes much better than all previous algorithms.

This is a joint work with Danny Raz, to be presented in IEEE INFOCOM 2007.

The OD Cycles Approach for Survivable Converged  Networks, 15:50-16:15


Meir Herzberg



The issue of network survivability is of increasing importance as each major network failure may have a greater impact when compared to the past. In this talk, I will explain the terms of survivability strategies and policies in addition to the main performance measures involved. Several major network approached developed, including p-Cycles, Fast Re-Routing (FRR, developed by Cisco) and Hop Limit, will be detailed.

The main reason for the establishment of Multi-Service Networks is to attain cost savings by implementing “converged” networks, thus, requiring a set of policies for survivability to support different grades of recovery. Developing a suitable approach for such a compound network environment is desirable. OD Cycles tries to meet that challenge. It is a novel approach that simultaneously may support the following survivability types at the end-to-end path level:

(i) 1+1 with Automatic Protection Switching (1+1 APS);

(ii) Shared Backup Path Protection (SBPP);

(iii) Pre-Cross-connected Trails (PXTs);

(iv) Split Flows.

I will detail the above mentioned terms and the OD Cycle approach. Some typical network findings based on OD Cycles will be presented.


Short talk: Transmission Scheduling for Mass Transit in Data Wireless Networks,16:15-16:30


Elisha Rosensweig

CS Tel-Aviv University



Scheduling of down-link transmission for data applications in wireless networks has been the focus of recent research. Channel-aware scheduling algorithms were shown to achieve significant performance gains by accounting for the time varying reception capacities and exploiting their independence across the mobile users.

We deviate from these studies by considering mass-transit systems, in which reception capacities of the mobile users are not independent but are rather positively correlated to each other and thus pose a potential problem due to the bursty  traffic requirements they inflict on the cells. We study the performance of these systems focusing on trains and aiming at providing a solution to this bursty traffic. We propose a down-link scheduling algorithm that maximizes the resources allocated to the mobile users residing outside the train while obeying the delay constraints of the train users. We further propose a new architecture for train wireless support systems, based on spatially separated reception train antennas. The combination of the proposed scheduling algorithm with the proposed architecture results in significant improvement of system performance.

This is a joint work with Hanoch Levy.

A Simulation Study of Multi-Color Marking of TCP Aggregates,16:30-16:45


Miriam Allalouf

School of Electrical Engineering, Tel Aviv University


Service Level Agreements (SLAs) are contracts signed between a provider and a customer which govern the amount of traffic that will be serviced.

This work pinpoints an important problem faced by the Internet service provider (ISP) which is to be able to differentiate between the services given to aggregates of multiple TCP connections. The Metro-Ethernet access network, the Differentiated Services (DiffServ) architecture and the ATM reference model are three architectural models where edge routers perform traffic metering and coloring of aggregated flows according to the SLA.

Finer color marking was suggested to improve differentiation quality. We observe that increasing the number of colors indeed provides a good differentiation between the aggregates according to the committed and the excess rates.  We show that the token bucket coloring policies, which are widely used for this purpose, prefer short packets and mark them with higher priority colors. The differentiation process is more difficult for the short TCP connections that remain in the slow start phase, than for the long connections that are usually in the congestion avoidance phase.

This is joint work with and Yuval Shavitt,


Former Seminars:

The 1st Seminar Artzi on Networking

The 2nd Seminar Artzi on Networking


Looking forward to your participation in the seminar!

Dr. Isaac Keslassy:         Technion

Dr. Anat Bremler-Barr:   Interdisciplinary Center Herzliya