Israeli Networking Seminar 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
Participation is free.
Driving instructions: 1. see MAP, 2. Cisco is also close to Beit-Yehoshua train station, 5 minutes taxi ride.
instructions: See the map
to get to the corner of Gad Manela and
Algorithmic Aspects of Radio Access Networks Design in 4G
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,
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
Zooming in on Network-on-Chip Architectures,
Department of Electrical Engineering
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,
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,
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,
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,
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
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
Looking forward to your participation in the seminar!