In this paper, we are presenting improvement of packet forwarding throughput reached by Quagga software routers. Usually, software routers that operate on general purpose hardware have moderate data plane performance compared to routers using dedicated hardware. Quagga software router relies on kernel network stack for forwarding packet between ports. The kernel network stack is composed of complex code which is not optimized for high packet forwarding throughput. We integrated Quagga control plane with fast data plane which is based on the netmap platform. Redesigned data plane provides much higher packet forwarding throughput, which is increased by the order of magnitude for shortest packets.

Shortest path routing algorithms dominate the Internet, but have their limitations that degrade the network performance as the traffic load is increasing. Shortest path routing may cause congestion on certain links while other links remain underutilized. Two-phase routing algorithms can reduce congestion due to adverse traffic patterns by means of load balancing. In this paper, we present the performance of two-phase routing algorithms in real wide area network topologies, and regular topologies typical for data centers. Also, we will analyze the influence of load balancing on goodput of TCP transport protocols in datacenter networks.

Due to a continuous rise in Internet traffic and the appearance of new services, the use of IP protocol routing can lead to the congestion of the network resources. Because of this, the modern networks use the MPLS technology to enable support to a wide spectrum of services and make Internet traffic management more efficient. Multicast traffic is becoming more popular on the Internet, so the MPLS must efficiently support multicast traffic as well. This paper proposes the hardware implementation of the control protocol which should enable the exchange and updating of labels used for multicast traffic (mLDP). Advantage of the presented hardware implementation is that it could support higher scalability and more dynamic traffic compared to the standard, software solutions. We will examine performance of the implementation in terms of the resources that it consumes, as well as the possibilities for its further improvement.

The articles i nthis special issue focus on switching and routing applications for scalable and energy efficient networking.

Internet traffic is rapidly increasing, as well as the number of users. The increased link speeds result in smaller available time for the lookup and, hence, require faster lookup algorithms. There is a trade-off between complexities of the IP lookups and the IP lookup table updates. In this paper, we propose, implement and analyze lookup table updating for parallel optimized linear pipeline (POLP) lookup algorithm and balanced parallelized frugal lookup algorithm (BPFL). We compare POLP and BPFL update algorithms in terms of their execution times for real-world routing tables. In order to analyze the influence of updates on packet forwarding, we will observe the number of memory accesses when the lookup tables are updated due to the network topology changes. For both lookup algorithms, we measure the memory requirements as well. Our analysis will show that the BPFL update algorithm has the smaller memory requirements, while the POLP update algorithm is faster.

There is an increased demand for new functionalities of the network equipment. Smaller companies that develop such functionalities build their products based on the open-source solutions. Linux is currently the most popular open-source operating system and thus the majority of products are based on it. As MPLS is becoming indispensable in the network core, the need for more stable version of MPLS for Linux becomes evident. Thus, this work focuses on the improvement of MPLS implementation for Linux kernel. It presents architecture and performance of this implementation. Its performance is compared to the performance of IP packets forwarding and existing MPLS implementations.

Many scheduling algorithms were proposed to provide fair service of flows passing through a buffer before the congested link. As we will show, fairness can be provided only if packets are dropped appropriately, while the fair scheduling algorithms is applied. We propose a novel algorithm for packet dropping in which the oldest packet is dropped (OPD). It will be shown that OPD provides fair service while having the minimal complexity.

The pool of available IPv4 addresses is being depleted, comprising less than 10% of all IPv4 addresses. At the same time, the bit-rates at which packets are transmitted are increasing, and the IP lookup speed must be increased as well. Consequently, the IP lookup algorithms are in the research focus again because the existing solutions were designed for IPv4 addresses, and are not sufficiently scalable. In this paper, we compare FPGA implementations of the balanced parallelized frugal lookup (BPFL) algorithm, and the parallel optimized linear pipeline (POLP) lookup algorithm that efficiently use the memory, and achieve the highest speeds.

In this paper, a practical routing protocol that maximizes the guaranteed node traffic loads in reliable networks is designed and analyzed. The derived node traffic loads can be routed for every traffic pattern, and regardless of the possible single node or link failures. First, it is described how load balanced shortest path routing (LB-SPR) can be optimized to maximize the value of the guaranteed node loads. By assigning the node weights which are fed into the linear program for the routing optimization, different network nodes can be guaranteed different traffic loads, according to their estimated demands. Then, the throughputs of the reliable networks using LB-SPR are determined. The obtained values are compared with the throughputs of the reliable networks using the regular shortestpath routing. The analysis is performed for the real networks, and the regular network topologies, and it is shown that the use of LB-SPR can significantly increase the network throughput.

The Internet traffic is growing, and its nature changes because of new applications. Multimedia applications require bandwidth reservations that were not needed initially when the file transfers dominated the Internet. P2P applications are making traffic patterns impossible to predict, and the traffic loads generated at nodes need to be routed regardless of the traffic pattern. When the guaranteed node traffic loads are known, bandwidth reservations can be made simple as will be explained in the paper. The shortest path routing (SPR) protocols used on the Internet today do not maximize the guaranteed node traffic loads, and do not provide scalable and fast bandwidth reservations. Load balancing can improve the network throughput for arbitrary traffic pattern. In this paper we analyze and implement a routing protocol that is based on load balancing and a commonly used shortest path routing protocol, and is, consequently, termed as LB-SPR. LB-SPR is optimized for an arbitrary traffic pattern, i.e. it does not assume a particular traffic matrix. Optimization assumes only the weights assigned to the network nodes according to their estimated demands. It will be shown that the optimized routing achieves the throughputs which are significantly higher than those provided by the currently used SPR protocols, such as OSPF or RIP. Importantly, LB-SPR calculates the guaranteed traffic loads and so allows fast autonomic bandwidth reservations which are the key for the successful support of triple-play applications, including video and audio applications that require high QoS. An actual modification of the TCP/IP stack that includes LBSPR is also described. Using the signaling mechanisms of the OSPF protocol, the information needed to perform the routing optimization is automatically distributed among the network nodes whenever the network topology changes. The LB-SPR implementation is validated on a sample network using a popular virtualization tool - Xen.

The sequential greedy scheduling (SGS) algorithm is a scalable maximal matching algorithm. This algorithm was conceptually proposed and well received since it provides non-blocking in an Internet router with input buffers and a cross-bar, unlike other existing implementations. In this paper, we implent a new design of the SGS algorithm, and determine its exact behaviour, performance and QoS that it provides. We examine different design options and measure the performance of their implementations in terms of their scalability and speed. It will be shown that multiple scheduler modules of a terabit Internet router can be implemented on a low-cost field-programmable gate-array (FPGA) device, and that the processing can be performed within the desired time slot duration. Proper functioning of the implemented scheduler was confirmed through thorough software and hardware testing.

In this paper, we propose the oblivious routing scheme based on shortest-path routing and load balancing. We present the LP model that finds the optimal routing. Then we compare the performance of the proposed scheme with the performance of the shortest-path routing for some regular and real-case network topologies. We show that the proposed routing strategy allows to achieve higher guaranteed traffic from/to a node in the network, compared to the case of the classical shortest-path routing.

The size of a single-hop switching fabric is still limited by the technology and the fabrics available on the market that do not exceed the terabit capacity. A Clos fabric is an attractive solution to increase the switch capacity. In this paper, we propose the ways to transfer packets through the Clos network without blocking them. Namely, all the traffic would get through the switching fabric timely, as long as the switch outputs are not overloaded. We show that the rate and delay guarantees can be provided to the most sensitive applications.

Congestion control in ring based packet networks is challenging due to the fact that every node in the network runs both a rate adaptation algorithm, analogous to an endpoint algorithm in other network architectures, and a rate allocation algorithm, analogous to switch-based algorithms in other network architectures. This work describes a congestion control algorithm for IEEE 802.17 resilient packet rings called the enhanced conservative mode algorithm that aims to avoid congestion and achieve a fair rate allocation for fairness eligible traffic in the case of a single bottleneck. We first present analysis to show that existing approaches for RPR congestion control (aggressive and conservative mode) have deficiencies. We present simulation results showing that the proposed enhanced conservative mode congestion control algorithm is a significant improvement. In conjunction with other mechanisms specified in the IEEE 802.17 MAC, the proposed algorithm achieves high utilization on the ring with minimal starvation and oscillations, allows sources to fast start, and provides quality of service for multiple classes of service that require rate, delay and jitter guarantees.

This paper introduces a protocol for scheduling of packets in high-capacity switches, termed weighted sequential greedy scheduling (WSGS). WSGS is a simple, greedy algorithm that uses credits to reserve bandwidth for input-output pairs. By using a pipeline technique, WSGS implemented by the current technology readily supports a switching capacity exceeding 1 Tb/s. Admission control is straightforward, allowing bandwidth reservations on a submillisecond time scale. Namely, the central controller readily determines if the newly requested bandwidth can be assigned to the given input-output pair. We have shown that a newly requested bandwidth should be assigned if both the input and output have enough capacity, which requires checking of only two inequalities. Therefore, WSGS is well suited for switching in data networks where sessions might require high bit rates and last for a short time. The WSGS allows bandwidth reservations with fine granularity, e.g., bandwidth can be reserved for individual web sessions, video streams, etc.

Optical add-drop multiplexers (OADMs) may cost-effectively provide regional nodes with large bandwidths. But, each dropped or added wavelength requires a costly TDM terminal. We discuss ways to decrease the number of TDM terminals in regional access networks (RANs) with OADMs, while ensuring high network utilization and sufficiently low probability of blocking new connection requests. We propose two wavelength assignment schemes that provide full-connectivity in RANs with fixed-tuned OADMs: (1) wavelengths are assigned to nodes according to the Hadamard code, and (2) bands of contiguous wavelengths are assigned to nodes. Simulation results show that on average, the Hadamard wavelength assignment schemes approach the performance of RANs with OADMs that add-drop all wavelengths, while saving 50% of the TDM terminals. The saving of TDM terminals by using wavelength tunable OADMs vary in different cases. Tunable OADMs are advantageous for lower traffic granularity and more interactions of a RAN with the outside network.

We have previously proposed a new scalable protocol for an optical star network, termed AFAP (adaptive fixed assignment protocol). It requires a smaller amount of control information than other reservation-based protocols: C bits per control packet, where C is the number of channels. This paper provides a complete study of the AFAP. Simulation results show the performance of AFAP when (a) the network size increases and (b) the traffic is non-uniform. We propose an extension of AFAP that better handles non-uniform traffic. In the extended AFAP, the fixed receiver for data reception is replaced by a tunable receiver; however, this tunable receiver does not have to retune very fast.