Protocols for High-Speed Networks VI

With the ever increasing optical transmission rate, now exceeding 1 Tb/s on a single fiber thanks to Wavelength Division Multiplexing (WDM) technologies, electronic routing/switching is quickly becoming a performance bottleneck in high-speed backbone networks. WDM optical networking, though rooting in the physical and link layers, is by no means yet another ordinary low layer technology as it may affect the designs of the upper electronic layer. Specifically, WDM optical networks can be configured to bypass intermediate electronic components by switching/routing data in the optical domain. This will not only reduce electronic processing and I/O loads, but also provide bit-rate and coding format transparency. However, this may also lead to unexpected “shortest” and “alternate” paths in the electronic layer. In addition, primitive optical logic, and especially the lack of optical memory (buffer) are major challenges in order to realize the vision of building a bandwidth-abundant infrastructure, which is ubiquitous and yet efficient, based on WDM optical networks. In this talk, I will describe these issues and along relevant optical switching paradigms, namely wavelength-routing (as a form of optical circuit switching), optical packet switching, and optical burst switching (OBS), and discuss how the next generation Optical Internet may support QoS and provide multicast services in the WDM optical layer.

The working session is a key feature of Protocols for High-Speed Networks. The sessions for 1999 are described below.

We survey recent approaches to do fast IP lookups. We compare algorithms based on their lookup speed, scalability, memory requirement and update speed. While our main interest lies in the worst case lookup time, competitive update speeds and theoretical worst case bounds are also important. In particular we consider binary search on prefixes, binary search on prefix lengths, LC-tries, controlled prefix expansion and Lulea tries. We consider both software and hardware environments. We conclude that with these recent developments, IP lookups at gigabit speeds is a solved problem and that terabit lookup chips can be designed should the need arise.

Packet classification is the problem of matching each incoming packet at a router against a database of filters, which specify forwarding rules for the packets. The filters are a powerful and uniform way to implement new network services such as firewalls, Network Address Translation (nat), Virtual Private Networks (vpn), and per-flow or class-based Quality of Service (qos) guarantees [4]. While several schemes have been proposed recently that can perform packet classification at high speeds, none of them achieves fast worst-case time for adding or deleting filters from the database [3, 8, 9]. In this paper, we present a new scheme, based on space decomposition, whose search time is comparable to the best existing schemes, but which also offers fast worst-case filter update time. The three key ideas in this algorithm are as follows: (1) innovative data-structure based on quadtrees for a hierarchical representation of the recursively decomposed search space, (2) fractional cascading and pre-computation to improve packet classification time, and (3) prefix partitioning to improve update time. Depending on the actual requirements of the system this algorithm is deployed in, a single parameter α can be used to tradeoff search time for update time. Also, this algorithm is amenable to fast software and hardware implementation.

Coupling Internet protocol (IP) routers with wavelength-selective optical crossconnects makes it possible to support existing Internet infrastructure in a wavelength-division multiplexing optical network. Because optical wavelength routing is transparent to IP, very high throughput and low delay can be achieved when packets are made to bypass the IP forwarding process by being switched directly through the optical cross-connect. One version of this approach is called packets over wavelengths (POW). This paper presents the POW architecture in detail and discusses its salient features. Realistic simulations of the POW that use actual packet traces in a well-known Internet backbone network reveal the level of performance that can be expected from POW under various options. Specifically, the fraction of packets that are switched through the crossconnect is evaluated as a function of the number wavelengths and the degree of flow aggregation that can be achieved. The resulting analysis, conducted in the context of the very-high bandwidth network service (vBNS) Internet backbone, suggests that as few as four wavelengths combined with a high degree of traffic aggregation can carry more than 98% of IP packets in the streamlined switched mode. In cases where it is not possible to aggregate traffic, the deployment of wavelength-merging technology would increase the fraction of IP packets carried in streamlined switched mode by up to 52%.

The Nemesis operating system is designed to provide Quality of Service to applications. Nemesis also allows applications to reserve CPU time and transmit bandwidth on network interfaces. We have implemented a TCP for Nemesis that makes use of these guarantees.

We show that the Nemesis transmit scheduler rate-controls TCP traffic and thus leads to predictable traffic behavior when applications choose not to utilize non-allocated bandwidth. Applications that want to make use of the non-allocated transmit bandwidth receive the guaranteed bandwidth plus a share of the non-allocated bandwidth.

We also study the impact of the guaranteed fraction of CPU time on the throughput that networked applications achieve. We measure the amount of CPU time applications have to reserve in order to run the TCP protocol stack and send data at a particular speed. We show that these values hold even when several applications strive for CPU time and transmit bandwidth.

To be an effective platform for performance-sensitive real-time and embedded applications, off-the-shelf CORBA middleware must preserve communication layer quality of service (QoS) properties to applications end-toend. However, the standard CORBA’s GIOP/IIOP interoperability protocols are not well suited for applications that cannot tolerate the message footprint size, latency, and jitter associated with general-purpose messaging and transport protocols. It is essential, therefore, to develop standard pluggable protocols frameworks that allow custom messaging and transport protocols to be configured flexibly and used transparently by applications.

This paper provides three contributions to research on pluggable protocols frameworks for performance-sensitive communication middleware. First, we outline the key design challenges faced by pluggable protocols developers. Second, we describe how TAO, our high-performance, real-time CORBAcompliant ORB, addresses these challenges in its pluggable protocols framework. Third, we present the results of benchmarks that pinpoint the impact of TAO’s OO design on its end-to-end efficiency, predictability, and scalability.

Our results demonstrate how applying strategic optimizations to communication middleware can yield highly flexible/reusable designs and highly efficient/predictable implementations. In particular, the overall round-trip latency of a TAO two-way method invocation is ~125 μsecs using the standard CORBA inter-ORB protocol on a commercial, off-the-self Pentium II Xeon 400 MHz workstation running in loopback mode. The ORB middleware accounts for ~60 μsecs of the total round-trip latency. These results illustrate that (1) communication middleware performance is largely an implementation detail and (2) the next-generation of optimized, standards-based CORBA middleware can replace ad hoc and proprietary solutions.

Multicast transmissions naturally raise the problem of the heterogeneity of receivers in terms of networking possibilities, host performances and user desires. Several solutions have been introduced but none suits all the situations. This paper describes a scheduling algorithm that unifies some of these solutions, in particular in case of continuous data flows, and which is suited to a broad range of applications. An implementation of this algorithm is used to illustrate its behavior.

In this paper, we present a comparative study of three proposals for differentiated services — the RIO scheme, the two-bit scheme and the User-Share Differentiation (USD) scheme. We simulate the three schemes under a number of different scenarios including mismatching of bottleneck bandwidth and profiles, short duration traffic, and non-responsive sources. Our findings show that although the simpler schemes for Differentiated Services reduce the complexity in the core, they tend to perform less well when there is a mismatch between the allocated profiles and bottleneck bandwidth, and also when the traffic sources are bursty, and non-responsive.

RSVP has developed as a key component for the evolving Internet, and in particular for the Integrated Services Architecture. Therefore, RSVP performance is crucially important; yet this has been little studied up till now. In this paper, we target one of the most important aspects of RSVP: its ability to establish flows. We first identify the factors influencing the performance of the protocol by modelling the establishment mechanism. Then, we propose a Fast Establishment Mechanism (FEM) aimed at speeding up the set-up procedure in RSVP. We analyse FEM by means of simulation, and show that it offers improvements to the performance of RSVP over a range of likely circumstances.

In this paper we propose a layered framework for charging QoS-enhanced IP services with policy based configuration of its layers. As an example architecture we present our implementation — Value Added IP Charging and Accounting Service (VIPCAS). We further concentrate on VIPCAS elements for policies and data exchange. As flexible data structure for exchange of accounting information, we propose the Premium IP Network Accounting Record (PIP-NAR), which is suitable for a variety of charging schemes (e.g. charging of reserved and used resources), and which also makes provider-specific extensions possible. We specify the Tariff Formula Language (TFL) for representing tariff policies, and the Charging Information Protocol (CIP) for distributing tariff information expressed in TFL. For a fair charging of IP Multicast services, cost sharing functions should be supported at both the accounting and the charging layer. We evaluate different approaches in this area which support receiver heterogeneity with regard to the reserved QoS.

A Virtual Private Network (VPN) is a solution that provides corporate networking between geographically dispersed sites. VPN sites consist of local area networks (LANs). Their interconnection is based on a public network infrastructure. Links connecting VPN sites are allocated with a peak rate and the VPN customer pays for the reserved bandwidth. The goal of this work is to develop a control model able to manage traffic on these links. By maximizing bandwidth utilization, an optimum balance for the allocation of bandwidth on each link can be found. To respond to such needs, we propose to introduce in each LAN of the VPN a control architecture that we call The Hierarchical Bandwidth Manager. This manager is able to cope with best-effort and guaranteed flows so that bandwidth left unused by guaranteed flows is dynamically distributed among best-effort ones. It uses a tree representation of the LAN nodes and regulation of link bandwidth is done in a hierarchical and distributed manner. Each node in the tree respects either an inter-node bandwidth share protocol or an intra-host regulation protocol. The bandwidth manager relies on the implementation of both protocols in the tree node. Results of the implementation of the bandwidth manager in the ns network simulator are described in this paper.

Mobile IP represents a simple and scalable global mobility solution but lacks support for fast handoff control and real-time location tracking found in cellular networks today. In contrast, third generation cellular systems offer seamless mobility support but are built on complex and costly connection-oriented networking infrastructure that lacks the inherent flexibility, robustness and scalability found in IP networks. Future wireless networks should be capable of combining the strengths of both approaches without inheriting their weaknesses. In this paper we present analysis of Cellular IP, a new host mobility protocol which represents one such approach. Cellular IP incorporates a number of important cellular system features but remains firmly based on IP design principles. The protocol presented in this paper is implemented as extensions to the ns simulator.

This paper addresses the problems of interworking of RSVP and IP in order to support QoS in hosts within a mobile environment. Two important issues are discussed. The first regards routing of RSVP messages combined with Mobile IP (both IPv4 and IPv6) and the second concerns the impact of handover in the operation of RSVP. The problems associated with each issue are discussed for both Mobile IPv4 and IPv6 and possible solutions have been proposed.