Data center networks undergo the coexistence of latency-sensitive mice flows and bandwidth-intensive elephant flows. Jointly optimizing the performance of both traffic classes poses complex challenges. Existing flow schedulers either rely on detailed flow size information or require numerous physical priority queues (PQs) within network switches, thus facing practical challenges.In this work, we propose a novel flow scheduling algorithm, namely Multi-Path Multi-Level Feedback Queueing (MPMLFQ), to overcome these limitations. MP-MLFQ leverages the spatial diversity and regularity of DCNs to realize a scheduler with numerous logical priority levels while occupying as few as 2 physical PQs at each switch port. We designed MP-MLFQ to run atop modern programmable networks, and highlighted how to implement it without modifications at the end-hosts’ stacks. Our simulation results show that MP-MLFQ outperforms existing flow size-agnostic solutions in minimizing the flow completion time, when only two PQs are available.

Abstract In networked music performance (NMP) applications, which entail real-time audio streaming over the Internet, strict latency requirements are needed to ensure a realistic interaction between geographically dispersed musicians. Thus, NMP applications typically leverage uncompressed audio and unreliable transport protocols to avoid unnecessary processing and re-transmission delays. Given that no guarantee on packet delivery is offered, NMP applications must deal with late/lost audio packets to mitigate the impact of the resulting audio artifacts on the quality of the playback audio stream. This paper explores an audio packet loss concealment (PLC) technique based on autoregressive (AR) models. In particular, it investigates the algorithmic implementation of Burg’s method and the parameters configuration that offers the best trade-off between prediction error and computational time requirements. The purpose is to find the most suitable solution capable of running on a Raspberry Pi 4B within the real-time audio boundaries imposed by NMP applications. Additionally, we analyze the computational time required to fit the model and predict future samples by considering six implementations and various compilation flags. Results confirm that AR models can predict future audio samples more accurately than traditional PLC approaches, which consist of filling audio gaps with silence or repeating the last received audio segment. Furthermore, results demonstrate the effectiveness of the proposed solution in meeting the strict latency requirements when deployed on a Raspberry Pi 4B.

Probabilistic approaches allow designing very efficient data structures and algorithms aimed at computing the number of flows within a given observation window. The practical applications are many, ranging from security to network monitoring and control. We focus our investigation on approaches tailored for sliding windows, that enable continous-time measurements independently from the observation window. In particular, we show how to extend standard approaches, such as Probabilistic Counting with Stochastic Averaging (PCSA), to count over an observation window. The main idea is to modify the data structure to store a compact representation of the timestamp in the registers and to modify coherently the related algorithms. We propose a timestamp-augmented version of PCSA, denoted as TS-PCSA, and compare it with state-of-the-art solutions based on Hyper-LogLog (HLL) counters that evaluate the cardinality over a sliding window, but without storing the timestamps. We will show that TS-PCSA with a limited memory footprint is achieving a different tradeoff between memory and accuracy with respect to HLL-based solutions.

Due to the increasing trend in IP traffic, the placement of Data Centers (DCs) at network nodes has become a hot research topic. A proper DCs placement translates in reduced power consumption of overall network. The paper scope is to find the best placement of “k” DCs nodes out of “N” total nodes to reduce power consumption. To solve the problem, we propose two heuristics: EoDCP, based on Estimation of Distribution Algorithm (EDA), and MaxN-MinL. An exhaustive search based ESDCP algorithm is used as a lower bound to compare the performance of EoDCP and MaxN-MinL. Moreover, electronic traffic grooming technique is employed to further reduce the total network power consumption. A 20-Node Random network and a 17-Node German network are used to perform comparison of proposed heuristics. Performance of EoDCP algorithm is far better than those of MaxN-MinL, and is similar to the optimal solution obtained via ESDCP. Finally, using electronic traffic grooming improves power savings up-to 15% in the two considered topologies.

In SDN stateful data planes, switches can execute algorithms to process traffic based on local states. This approach permits to offload decisions from the controller to the switches, thus reducing the latency when reacting to network events. We consider distributed network applications that process traffic at each switch based on local replicas of network-wide states. Replicating a state across multiple switches poses many challenges, because the number of state replicas and their placement affects both the data traffic distribution and the amount of synchronization traffic among the replicas. In this paper, we formulate the optimal placement problem for replicated states, taking into account the data traffic routing, to ensure that traffic flows are properly managed by network applications, and the synchronization traffic between replicas, to ensure state coherence. Due to the high complexity required to find the optimal solution, we also propose an approximated algorithm to scale to large network instances. We numerically show that this algorithm, despite its simplicity, well approximates the optimal solution. We also show the beneficial effects of state replication with respect to the single-replica scenario, so far considered in the literature. Finally, we provide an asymptotic analysis to find the optimal number of replicas.

Recently proposed approaches to minimize the Flow Completion Time (FCT) in data centers do not require any a-priory information about the flow size, thus appear to be both practical and efficient. These solutions are based on a system of multiple priority queues (PQs) at both the servers and the switches and they may require to solve a complex algorithm to optimally split the traffic across the different PQs. However, the actual availability of priority queues at the switches is typically limited, thus restricting the applicability of these approaches. In our work we propose a novel approach, NOS2, which requires only 2 PQs at the switches while maintaining multiple PQs at the servers, and leverages a central controller that optimally coordinates the traffic split among the different priority levels. We show by simulation that NOS2 is able to achieve performance close to state-of-art solutions with significantly smaller implementation complexity. Thus, NOS2 is expected to provide a better trade- off between performance and implementation complexity.

Provisioning strategies for Translucent Elastic Optical Networks (EONs) should consider both spectrum and transponder costs. End-to-end connections that support user demands may be obtained on the one hand via transparent paths, which avoid regeneration costs but may require more spectrum slot, thus increasing the blocking probability, on the other hand via opaque paths that can reduce spectrum requirements, but at the cost of additional transponders for regeneration purposes. In this context, a wise provisioning strategy needs to consider translucent paths that can provide a good trade-off between transparent and opaque solutions. We propose a provisioning strategy that considers a multi-objective optimization problem aiming at the joint minimization of spectrum resources and regenerators. We show that the proposed strategy can significantly reduce regeneration costs while achieving low blocking probability.

Elastic Optical Networks (EONs) permit a trade-off between spectrum and regeneration use. Provisioning strategies for translucent EONs can reduce spectrum requirements at the cost of additional Bandwidth Variable Transponders (BVTs) used for regeneration. In this context, Sliceable Bandwidth Variable Transponders (SBVTs) can enable transponder sharing among multiple demands, potentially reducing regeneration costs. In this paper, we analyze the impact of SBVTs on the translucent provisioning process of EONs. In particular, we demonstrate that the use of SBVTs can improve blocking probability at almost no extra cost. We discuss simulation results for dynamic traffic over an EON when using different provisioning strategies that use SBVTs with respect to BVTs. Results reflect that the translucent strategy can significantly reduce the blocking probability even without the need of extra transponder deployment.

Recently proposed architectures for high- performance data centers advocate the adoption of a centralized control that coordinates the packet transfers within the data center network. In such architectures, centralized algorithms perform decisions regarding packet scheduling (i.e., when a packet is transferred from the server to the switches) and packet routing (i.e., the sequence of traversed switches to reach the destination server) with the aim of optimizing the overall performance. Notably, centralized control permits to reduce packet contention and to minimize the delay introduced by the data center network, but may rely on expensive mechanisms such as synchronous transmission of the packets from the servers. In our work we compare a generic synchronous architecture for the centralized control of a data center with a generic asynchronous architecture, that relaxes the strict packet-by-packet control required by the synchronous architecture and enables a simpler rate-based implementation at the servers. We show that the two architectures achieve near identical performance in terms of throughput, fairness and delays. We finally conclude that asynchronous architectures offer a better trade-off in terms of complexity and performance, with better scaling properties to very large sizes.

Data sharing and access control management is one of the issues still hindering the development of decentralized online social networks (DOSNs), which are now gaining more research attention with the recent developments in P2P computing, such as the secure public ledger–based protocols (Blockchains) for monetary systems. In a previous work, we proposed an initial audit–based model for access control in DOSNs. In this article, we focus on enhancing the audit strategies and the privacy issues emerging from records kept for audit purposes. We propose enhanced audit and collaboration strategies, for which experimental results, on a real online social network graph with simulated sharing behavior, show an improvement in the detection rate of bad behavior of more than 50% compared to the basic model. We also provide an analysis of the related privacy issues and discuss possible privacy-preserving alternatives.

The logical centralized approach in the control of SDN networks allows an unprecedented level of programmability in the network, but also implies the vulnerability in the case of misbehavior of the controller, due for example to software bugs, hardware problems or hacker attacks. In our work we propose to exploit the diversity offered by multiple controllers to manage the network switches and detect misbehaviors whenever one controller issues different OpenFlow instructions for the data plane with respect to the others. We design a behavioral checker, denoted as BeCheck, that acts as a transparent relay in the interaction between the network switches and the controllers. We propose and investigate different policies to relay the messages and to detect the controller misbehavior. We implement and validate our approach in a simple testbed, showing the possible tradeoff between detection reliability and controller reactivity perceived at the switches.

Elastic Optical Networks (EONs) can increase the efficiency of already deployed optical fibers thanks to transponders that adjust the modulation format, baud-rate and number of optical carriers to achieve the desired transmission rate, bandwidth and reach. Due to the high cost of these transponders, transparent end-to-end lightpaths are usually desired, which can require a large amount of spectrum when provisioned over long distances. In this paper, we consider the case of translucent lightpaths, which make use of flexible regeneration schemes to reduce the amount of required spectrum. We analyze the trade-off between the spectrum usage and the number of transponder devices. In particular, we propose a proactive approach to provision EONs that considers the spectrum availability. Thus, it is possible to explore the referred trade-off with a load-incremental perspective, which may be relevant for network operators. Results show how the proposed approach can increase the supported capacity in the network at the cost of additional transponder devices.

The novel “stateful” approach in Software Defined Networking (SDN) provides programmable processing capabilities within the switches to reduce the interaction with the SDN controller and thus improve the scalability and the performance of the network. In our work we consider specifically the stateful extension of OpenFlow that was recently proposed, called Open-State, that allows to program simple state machines in almost-standard OpenFlow switches. We consider a reactive traffic control application that reacts to the traffic flows which are identified in real-time by a generic traffic classification engine. We devise an architecture in which an OpenState-enabled switch sends the minimum number of packets to the traffic classifier, in order to minimize the load on the classifier and improve the scalability of the approach. We design two stateful approaches to minimize the memory occupancy in the flow tables of the switches. Finally, we validate experimentally our solutions and estimate the required memory for the flow tables.

We consider an in-line data deduplication system to backup data from many clients in a cluster of storage servers. We propose a centralized synchronous approach, denoted as GateD, that orchestrates the deduplication operations. According to GateD, the deduplication requests from multiple clients are gathered in a time window and then processed all together. This allows the centralized controller to exploit a higher space of solutions to allocate the data to the deduplication nodes in order to balance the storage occupancy across the nodes, with a beneficial effects on the final performance perceived at the clients and without sacrificing the deduplication efficiency. We investigate the performance through a detailed simulation model applied to real deduplication traces and show that GateD outperforms other state-of-art deduplication schemes.

In distributed SDN architectures, the network is controlled by a cluster of multiple controllers. This distributed approach permits to meet the scalability and reliability requirements of large operational networks. Despite that, a logical centralized view of the network state should be guaranteed, enabling the simple development of network applications. Achieving a consistent network state requires a consensus protocol, which generates control traffic among the controllers whose timely delivery is crucial for network performance. We focus on the state-of-art ONOS controller, designed to scale to large networks, based on a cluster of self-coordinating controllers. In particular, we study the inter-controller control traffic due to the adopted consistency protocols. Based on real traffic measurements and the analysis of the adopted consistency protocols, we develop some empirical models to quantify the traffic exchanged among the controllers, depending on the considered shared data structures, the current network state (e.g., topology) and the occurring network events (e.g., flow or host addition). Our models provide a formal tool to be integrated into the design and dimension the control network interconnecting the controllers. Our results are of paramount importance for the proper design of large SDN networks, in which the control plane is implemented in-band and cannot exploit dedicated network resources.

Data centers provision industry and end users with the necessary computing and communication resources to access the vast majority of services online and on a pay-as-you-go basis. In this paper, we study the problem of energy proportionality in data center networks (DCNs). Devices are energy proportional when any increase of the load corresponds to a proportional increase of energy consumption. In data centers, energy consumption is concern as it considerably impacts on the operational expenses (OPEX) of the operators. In our analysis, we investigate the impact of three different allocation policies on the energy proportionality of computing and networking equipment for different DCNs, including 2-Tier, 3-Tier, and Jupiter topologies. For evaluation, the size of the DCNs varies to accommodate up to several thousands of computing servers. Validation of the analysis is conducted through simulations. We propose new metrics with the objective to characterize in a holistic manner the energy proportionality in data centers. The experiments unveil that, when consolidation policies are in place and regardless of the type of architecture, the size of the DCN plays a key role, i.e., larger DCNs containing thousands of servers are more energy proportional than small DCNs.

Flexible-grid optical networks are the most convincing candidate for the evolution of backbone optical networks thanks to their high spectral efficiency and flexibility. We propose an original approach to the logical topology design (LTD) problem in the offline planning phase. We deal with the LTD problem using heuristic algorithms incorporating a detailed transmission layer model. Several heuristic algorithms, allocating traffic demands in different orderings, are considered for lightpath provisioning. Traffic ordering schemes are mainly based on two parameters: traffic demands capacity and lightpath physical route length. Through simulative analyses, we provide a performance comparison of different heuristics, using parameters like spectral efficiency, amount of blocked traffic and total number of transceivers. We also show the importance of integrating a detailed physical layer modeling in the network design phase.

A considerable percentage of worldwide electrical energy is consumed by information and communication technology. One significant element in this perspective are the data distribution systems via Content Delivery Networks (CDNs). We introduce a new model to compute the total energy consumption of CDNs which is based on a hierarchical Internet map and that takes into account the energy consumption needed to keep servers synchronized. The CDN is represented as a main server storing the whole data set and several surrogate servers, each caching a subset of the entire data set. Servers are located in a hierarchical three-tier network topology. We analyze the energy consumption trends as a function of the number of surrogate server. Results show that increasing the number of surrogate servers decreases the transmission delay but it does not always lead to decreasing energy consumption. Furthermore, the energy consumption profile as a function of the number of servers strongly depends on the ratio between the number of content requests and modifications. Finally, we show that the adoption of a hierarchical network model permits to highlight slightly different energy consumption trends with respect to those of standard “flat” network representation.

In distributed SDN architectures, the network is controlled by a cluster of multiple controllers. This distributed approach permits to meet the scalability and reliability requirements of large operational networks. Despite that, a logical centralized view of the network state should be guaranteed, enabling the simple development of network applications. Achieving a consistent network state requires a consensus protocol, which generates control traffic among the controllers whose timely delivery is crucial for network performance. We focus on the state-of-art ONOS controller, designed to scale to large networks, based on a cluster of self-coordinating controllers, and concentrate on the inter-controller control traffic. Based on real traffic measurements, we develop a model to quantify the traffic exchanged among the controllers, which depends on the topology of the controlled network. This model is useful to design and dimension the control network interconnecting the controllers.

Power consumption is a primary concern for cloud computing data centers. Being the network one of the non-negligible contributors to energy consumption in data centers, several architectures have been designed with the goal of improving network performance and energy-efficiency. In this paper, we provide a comparison study of data center architectures, covering both classical two- and three-tier design and state-of-art ones as Jupiter, recently disclosed by Google. Specifically, we analyze the combined effect on the overall system performance of different power consumption profiles for the IT equipment and of different resource allocation policies. Our experiments, performed in small and large scale scenarios, unveil the ability of network-aware allocation policies in loading the the data center in a energy-proportional manner and the robustness of classical two- and three-tier design under network-oblivious allocation strategies.

Scalability of Software Defined Networking (SDN) approach is one of the key issues that many network operators are willing to address and understand. Indeed, the promised programmability and flexibility of a SDN network is paid with a non-negligible control traffic exchanged between the network nodes and the SDN controllers. We consider a network controlled by a real OpenFlow-enabled controller, i.e. OpenDaylight. We evaluate analytically the number of OpenFlow messages for installing a new traffic flow, assuming the default reactive forwarding application available in OpenDaylight. We apply these results to the specific case of a large ISP network, comprising a backbone interconnecting many POPs. By evaluating exactly the amount of generated control traffic, we are able to assess the scalability of the reactive forwarding application in a practical relevant scenario for ISPs.

Energy-efficient design of flexible-grid networks is investigated. We focus on the design of the logical layer, usually disregarded when dealing with flexible-grid networks. More precisely, we evaluate the impact of introducing an energy-aware electronic traffic grooming in flexible-grid networks design. We propose two greedy heuristics for the network design, one exploiting traffic grooming, and we compare their energy efficiency. Results have been retrieved for several randomly generated networks of different size, with different connectivity, average physical link length and traffic scenarios. Significant energy savings can be achieved for low traffic loads and large network size when performing traffic grooming.

The power consumption in chips, in general, and in crossbars switching fabrics, in particular, grows with the maximum sustainable throughput. Due to the fast increasing traffic demands, the performance scalability of crossbars is severely limited by the capability of cooling the hardware devices. Hence, reducing the power consumption is an important design question to improve the crossbar switching performance. We propose to leverage Dynamic Voltage and Frequency Scaling (DVFS) hardware technique for the switching fabric. The main idea is to exploit temporary underloaded conditions to decrease the crossbar transmission rate while preserving maximum throughput. Differently from previous works, we consider a scenario in which the arrival rates are unknown in advance. Our proposed architecture is based on a power controller which runs periodically and independently of the packet scheduler, and whose decisions are based on the real time estimation of the arrival rates. We discuss the performance tradeoff in terms of throughput, delays and power, and show the relevant performance gain due to the use of DVFS in controlling the crossbar.

Software Defined Networking (SDN) is a new networking paradigm that permits to slice network infrastructures. An example of SDN is the OpenFlow framework, where the control plane runs on a separate device, called controller, that manages data forwarding switches. The OpenFlow protocol ensures communications between OpenFlow switches and the OpenFlow controller. Before widely deploying OpenFlow based networks, scalability and performance of such networks should be studied and better understood. In this paper, the scalability of NOX, one of the most popular OpenFlow controller, is analyzed through both simulation and lab measurements. We perform an Ethernet trace analysis on the controller by defining flow characteristics as would be seen by an OpenFlow controller. We study the potential trace impact on an OpenFlow controller, analyzing among others, the number of flows, flow inter arrival times, traffic volumes and flow size distribution. Our results permit to discuss the feasibility of running OpenFlow networks with a single commodity PC as the controller in a mid-size campus network.

The physical characteristics of microring resonator switching devices are thoroughly analyzed using a model based on the field coupling matrix theory. The spectral response and insertion loss properties of these switching elements are simulated using the developed model. Results show that by cascading three microring resonators it is possible to achieve flat-top passband widths ranging from 6.25 GHz to 3 THz, while having insertion losses compatible with the use in flexible-grid optical communication networks. In light of a potential use of these devices in the design of a scalable flexible wavelength selective switch, the architecture of simple optical switches with limited functionalities is discussed.

This paper shows how to use an open virtualisation architecture to analyse and improve the forwarding performance of a virtual router. In particular, the forwarding performance of the Linux kernel running inside a KVM virtual machine and the performance of some more advanced architectures based on virtual routers aggregation are analysed, showing how increasing the number of used CPU core can improve performance and how properly setting the CPU affinity of the various virtualisation activities affects virtual router throughput.

A multistage software router (MSSR) architecture is composed of several personal computers (PCs) to overcome single PC-based software router scalability issues. Although the architecture scales almost linearly with the number of internal elements, energy consumption could be a threat to its scalability features when building a core router with many internal components. Assuming a known 24 hour traffic load, this paper proposes energy efficient multistage software router design approaches, which enhance the performance of energy saving algorithms that minimize the energy consumption by tailoring the architecture to match the current input traffic demand. Simulation results show that a multistage software router architecture defined by the newly proposed design approaches saves roughly 10% of energy with respect to existing algorithms for similar cost. The energy saving may reach 20% depending on the initial admissible budget.

We consider an N × N Input-Queued (IQ) switch with a crossbar-based switching fabric implemented on a single chip. The power consumption produced by the crossbar chip, due to the data transfer, grows as NR3, where R is the maximum bit rate. Thus, at increasing bit rate, power dissipation is becoming more and more challenging, limiting the crossbar scalability for high-performance switches. We propose to exploit Dynamic Voltage and Frequency Scaling (DVFS) techniques to control packet transmissions through each crosspoint of the switching fabric. Our power control operates independently of the packet scheduler and exploits the knowledge of a traffic matrix obtained by online measurements. We propose a family of control algorithms to reduce the power consumption. The algorithms are particularly efficient in nonoverloaded conditions. The actual potential of the proposed approach is also evaluated on a real design case synthesized on a 90 nm CMOS technology.

We focus on a distributed multi-stage software router (MSSR) architecture internally composed by several personal computers (PCs) to overcome scalability and performance issues of software routers (SRs) based on a single PC. Sizing the internal architecture to sustain the peak load may lead to power inefficiency at low loads. This paper presents a power saving scheme to improve the power efficiency of the MSSR by dynamically adapting the size of its internal architecture to the offered load to reduce power needs. The off-line problem is defined as a mixed integer linear programming optimization model, shown to be NP-hard. We propose a differential on-line heuristic to solve the optimization problem when the traffic load changes. The heuristic avoids the complete MSSR reconfiguration of the optimal off-line solution that may lead to forwarding delay increase or service interruption. The performance evaluation shows that the proposed on-line algorithm, that gracefully modifies the internal MSSR configuration, preserves the load proportional power demand characteristics of the optimal offline solution.

Network-on-Chips (NoCs) have been proposed as a scalable solution to interconnect multiple components on a silicon chip. In this paper, we approach NoCs power optimization through Dynamic Voltage and Frequency Scaling (DVFS) under the hypothesis that two NoC planes are available, each with a different voltage supply and clock frequency. We show the high potential benefit of applying DVFS independently in each plane. We propose three strategies that allocate the traffic in the two planes to minimize power consumption. We evaluate them through a comparison with an ideal traffic allocation policy based on a linear programming technique. We show that load balancing in the two planes is not always the best policy. Indeed, in an unbalanced traffic scenario, concentrating the high-load flows in one plane and the remaining low-load flows in the other plane, is more power efficient.

A Network on Chip (NoC) provides the interconnection among Processing Elements (PEs) through routers, which permit hop-by-hop communications between PEs. To cope with higher traffic demands, PEs and routers are running at increasingly higher clock frequencies. Thus the chip power consumption grows rapidly and limits NoC scalability. This paper considers a Manhattan-like mesh (grid) NoC topology. We show how to leverage the traffic unbalancing within the topology to fully exploit the classical technique of Dynamic Voltage and Frequency Scaling (DVFS) to minimize the power consumption. We model the optimal NoC power control problem, and we evaluate the maximum achievable power reduction. Furthermore, we propose three different load-balancing routing schemes, simple to implement, that approximate quite accurately the optimal solution. Simulation results show that, in most of the cases, it is enough to consider only two paths among PEs to balance the traffic and to approach the minimum possible power consumption.

A multi-stage software router overcomes scalability issues related to a single, PC-based, software router by introducing parallel forwarding paths. However, since the architecture includes different internal components, energy inefficiency at low loads may arise if the multi-stage internal architecture does not adapt to currently offered traffic. This paper presents an energy-saving scheme to improve energy efficiency of the multi-stage router architecture by focusing on the back-end stage and sizing it to the offered load to reduce energy needs. The problem is defined as a mixed integer linear programming model, shown to be NP-hard. We tackle the scalability issues of the optimal problem by defining a two-step heuristic which takes advantage of existing Bin Packing algorithms. Our results shows that the two-step solution is within 10% relative error with respect to the optimal solution for different realistic scenarios.

Optical switching fabrics (OSF) are gaining interest because they promise to satisfy the higher information densities demanded by each successive generation of high-end routers and switches. Silicon microring resonators (MRR) can be employed to perform switching operations directly in the optical domain. However, similarly to other devices used to build all-optical switching fabrics, such as Arrayed Waveguide Gratings (AWG), MRR-based switching fabrics might show a limited scalability in terms of port count due to the crosstalk accumulation caused by the spatial wavelengths reuse. We consider an OSF built on a Wavelength-Routing-Matrix (WRM) based on MRRs, we highlight its scalability issues and we propose a new design as well as two different strategies to limit the wavelength spatial reuse.

Multi-stage software router architectures permit to overcome several limitations of single-stage software routers, allowing to expand the number of available interfaces and to increase the overall throughput. However, a multi-stage software router, despite being composed by several internal elements, must externally appear as a single device. A control protocol called DIST was defined to solve this problem from the control plane point of view for a previously proposed multi-stage architecture. In this paper, we tackle the same problem from the network management point of view. We define a management architecture and a manager-agent communication model to coordinate the information residing on the single elements of the multi-stage router to present a unified view to the external network management station issuing SNMP requests. We analyze the different variable types contained in the SNMP MIB and divide them into different categories depending on how the response to a SNMP request is compiled. The handling methods used to create the proper response to SNMP request for the different types of MIB variables are described. Analytical computations shows that the proposed management architectures does not affect the multi-stage software router scalability.

Array waveguide grating (AWG)-based optical switching fabrics are receiving increasing attention due to their simplicity and good performance. However, AWGs are affected by coherent crosstalk that can significantly impair system operation when the same wavelength is used simultaneously on several input ports. To permit large port counts in a N × N AWG, a possible solution is to schedule data transmissions across the AWG preventing switch configurations that generate large crosstalk. We study the properties and the existence conditions of switch configurations able to control coherent crosstalk. The presented results show that, by running a properly constrained scheduling algorithm to avoid or minimize crosstalk, it is possible to operate an AWG-based switch with large port counts without significant performance degradation.

Open source routers (OSR), i.e. routers running on commodity personal computers (PC), represent a valid alternative to proprietary hardware routers. However, they may suffer from performance impairments and software limitations. Multistage architectures, based on the interconnection of elements running on standard PCs, improve single stage OSR performance. Virtualization technologies may permit to make a further step towards performance improvement (by aggregation of multiple elements into a single logical unit), increased flexibility (e.g. scalability, maintenance, consolidation) and easier introduction of new features (e.g. energy saving mechanisms). In this paper we study a previously proposed multistage architecture and consider its implementation when using virtual machines as internal components. In our experiments we demonstrate the feasibility of the architecture, and discuss some issues related to performance and architecture control.

Optical switching fabrics are gaining interest as in multi Terabit switching devices; the advantages over their electronic equivalents are mainly their information density and power consumption. Arrayed Waveguide Gratings (AWGs) are promising optical devices proposed by the academic and industrial community to build optical switching fabrics. Because of their wavelength routing property, AWGs allow wavelength reuse over different ports introducing in-band crosstalk which strongly limits scalability of AWG-based backplanes. However, this effect can be mitigated or even completely avoided by means of proper scheduling algorithms. In this paper, we present several modified scheduling algorithms which limit the effect of coherent crosstalk in AWG-based switching fabrics and achieve good performance in terms of throughput and delay.

Input-queued (IQ) switches are one of the reference architectures for the design of high-speed packet switches. Classical results in this field refer to the scenario in which the whole switch transfers the packets in a synchronous fashion, in phase with a sequence of fixed-size timeslots, selected to transport a minimum-size packet. However, for switches with large number of ports and high bandwidth, maintaining an accurate global synchronization and transferring all the packets in a synchronous fashion is becoming more and more challenging. Furthermore, variable size packets (as in the traffic present in the Internet) require rather complex segmentation and reassembly processes and some switching capacity is lost due to partial filling of timeslots. Thus, we consider a switch able to natively transfer packets in an asynchronous fashion thanks to a simple and distributed packet scheduler. We investigate the performance of asynchronous IQ switches and show that, despite their simplicity, their performance are comparable or even better than those of synchronous switches. These partly unexpected results highlight the great potentiality of the asynchronous approach for the design of high-performance switches.

Two key elements in disaster recovery are backing up data at remote sites and reliability of services by virtualization. To support operational services and to speed up recovery process, resources should be distributed fairly and efficiently. Thus, we discuss resource allocation algorithms to support remote data storage and live virtual machines (VMs) migration. We identify two opposing forces: on the one hand, backup data should be stored as close as possible to the original site to guarantee high access speed and to minimize network load. On the other hand, upon a site failure, VM migration should minimize the impact of resuming VMs on other sites, to protect application performance and to reduce VM restoring time. We present optimal algorithms trading-off these two contrasting goals, and we compare their performance for different network topologies and resource distributions among sites.

We consider an N×N input-queued switch based on a crossbar switching fabric implemented on a single chip. The thermal power produced by the crossbar chip grows as N R3, where R is the maximum bit rate. Power dissipation is becoming more and more challenging, limiting the crossbar scalability for high performance switches. We propose to exploit Dynamic Voltage and Frequency Scaling (DVFS) techniques, quite commonly used in integrated circuit design, to control packet transmissions through each crosspoint of the switching fabric. Our thermal control operates independently of the packet scheduler and it is based on short-term traffic measurements. We propose a family of control algorithms to reduce the thermal power dissipation in non-overloaded conditions.

OpenFlow is an open standard that can be implemented in Ethernet switches, routers and wireless access points (AP). In the OpenFlow framework, packet forwarding (data plane) and routing decisions (control plane) run on different devices. OpenFlow switches are in charge of packet forwarding, whereas a controller set up switch forwarding table on a per-flow basis, to enable flow isolation and resource slicing. We focus on the data path and analyze the OpenFlow implementation in Linux based PCs. We compare OpenFlow switching, layer-2 Ethernet switching and layer-3 IP routing performance. Forwarding throughput and packet latency in underloaded and overloaded conditions are analyzed, with different traffic patterns. System scalability is analyzed using different forwarding table sizes, and fairness in resource distribution is measured.

Interconnection networks must transport an always increasing information density and connect a rising number of processing units. Electronic technologies have been able to sustain the traffic growth rate, but are getting close to their physical limits. In this context, optical interconnection networks are becoming progressively more attractive, especially because new photonic devices can be directly integrated in CMOS technology. Indeed, interest in microring resonators as switching components is rising, but their usability in full optical interconnection architectures is still limited by their physical characteristics. Indeed, differently from classical devices used for switching, switching elements based on microring resonators exhibit asymmetric power losses depending on the output ports input signals are directed to. In this paper, we study classical interconnection architectures such as crossbar, Benes and Clos networks exploiting microring resonators as building blocks. Since classical interconnection networks lack either scalability or complexity, we propose two new architectures to improve performance of microring based interconnection networks while keeping a reasonable complexity.

We consider a slotted input-queued switch with a crossbar-like switching fabric. In each time-slot, a centralized scheduler determines a switching fabric configuration to transfer packets. We consider the energy consumption needed to configure the switching fabric and we assume that the energy depends on the number of modifications in the switching configuration in two consecutive time-slots. We address the problem of scheduling a set of packets to minimize the required energy while preserving high throughput. We reduce the overall problem to the combination of two different optimization problems. We propose a family of algorithms to solve the problem and we discuss their energy-throughput performance.

AWG-based optical switching fabrics are affected by coherent crosstalk, that can significantly impair system operation when the same wavelength is used simultaneously on several input ports to forward data to output ports. To permit large port counts in a N x N AWG, the scheduling of transmissions across the AWG must therefore prevent switch configurations that generate large crosstalk. We study the properties and the existence conditions of switch configurations able to control coherent crosstalk. Our results show that it is possible to keep an AWG-based switch with large port counts in the feasible operational region without significant performance degradation, provided that a proper scheduling algorithm is used.

In this paper, Internet data collected via passive measurement are analyzed to obtain localization information on nodes by clustering (i.e., grouping together) nodes that exhibit similar network path properties. Since traditional clustering algorithms fail to correctly identify clusters of homogeneous nodes, we propose a novel framework, named "NetCluster", suited to analyze Internet measurement datasets. We show that the proposed framework correctly analyzes synthetically generated traces. Finally, we apply it to real traces collected at the access link of our campus LAN and discuss the network characteristics as seen at the vantage point.

We describe an analytical model, based on a Markov chain, suitable to study different bandwidth allocation policies for video streams over a WiMax access link. The Markov chain models an MPEG source, wireless channel conditions derived from a model compliant with WiMax specifications, and different bandwidth allocation policies. Validation with simulation results shows the correctness of the analytical model. The model permits to discuss the properties of various bandwidth allocation policies in terms of wasted slots, amount of lost data and access delays.

Passive optical networks (PONs) represent a step forward in "first mile" networks; indeed, by using optical technologies, PONs can transfer a large amount of data, and by being completely passive, they reduce management costs and failure probabilities. Access network is logically a point-to-multipoint network and the tree topology emerged as the winning solution; however, it naturally lacks protection capability and requires local traffic to be processed by the optical line terminal. In this paper, we present WONDER, a novel PON architecture based on a folded bus topology, which offers fault resilience and efficient local traffic support, and we discuss WONDER strengths and weaknesses.

Designing switching architectures for network routers and switches needs to consider limits imposed by the electronic technology, like small bandwidth x distance factors, power density constraints, energy consumption and dissipation issues. Introducing optical technologies to implement switching functions can overcome several of the current design limits. We propose a cost-effective architecture implementing an optical switch without any need for optoelectronic conversion within the switching fabric. We further propose a distributed scheduling scheme, based on an extension of the Fasnet protocol, and we compare it to classical centralized scheduling algorithms, showing that a distributed scheduler can provide performance comparable to the ones offered by more complex centralized schedulers.

Disaster recovery and business continuity issues are becoming fundamental in networks since the importance and social value of digital data is continuously increasing. On the one hand, there is an obvious need of backing up data for resilience against major failures; in many situations the process of storing backup data is also enforced by the law. On the other hand, providing services that allow the migration of applications in real-time through virtualization techniques is becoming a mandatory feature in several business situations. In this paper we analyze the problems and the challenges of off-site data replication and virtual machine migration. In particular, we discuss the issue of optimizing network planning to support disaster recovery and business continuity. ILP (IntegerLinearProgramming) formulations for the optimization problem are presented with different objective functions. Heuristics are also proposed and analyzed taking into account both network cost minimization and fault recovery efficiency.

We focus on metropolitan area networks operating in packet mode and exploiting a single-hop wavelength division multiplexing (WDM) architecture. First, we briefly describe a specific slotted WDM optical network, based on a folded bus topology. Then, we address the fairness problem arising in this architecture and propose an extension of the MetaRing protocol to a WDM scenario. Two possible strategies are defined and analyzed. Finally, we show that both fair access and high aggregate network throughput can be achieved by properly handling node access through all WDM channels.

Dealing with RTTs (round trip time) in IQ switches has been recently recognized as a challenging problem, especially if considering distributed (multi-chip) scheduler implementation which are suited to reduce the hardware complexity in very large, high-speed, switches. Traditional iterative three- or two-phase scheduling algorithms are based on a monolithic implementation, thus allowing instantaneous information exchange among input and output selectors to determine a matching. Multi-chip implementation imply that information exchange among inputs and outputs is delayed by an inter-chip latency. This delay requires non-trivial modifications to scheduling algorithms to allow a fully distributed implementation while keeping good performance. We propose a new scheduling algorithm, named SRR (synchronous round robin), which is suited to a fully distributed implementation and provides good performance if compared with more complex, non fully distributed, previously proposed scheduling algorithms.

Single-hop wavelength division multiplexing (WDM) ring networks operating in packet mode are a promising architecture for the design of innovate metropolitan area networks. They allow a cost-effective design, with a good combination of optical and electronic technologies, while supporting features like restoration and reconfiguration that are essential in any metropolitan scenario. In this article, we address the fairness problem in a slotted WDM optical network. We introduce the multi-fasnet fairness protocol, we discuss its limitations and we propose an extension, based on a dynamic strategy, that achieves high aggregate network throughput, throughput fairness, and bounded and fair access delays.

Software routers are becoming an important alternative to proprietary and expensive network devices, because they exploit the economy of scale of the PC market and open-source software. When considering maximum performance in terms of throughput, PC-based routers suffer from limitations stemming from the single PC architecture, e.g., limited bus bandwidth, and high memory access latency. To overcome these limitations, in this paper we present a multistage architecture that combines a layer-2 load-balancer front-end and a layer-3 routing back-end, interconnected by standard Ethernet switches. Both the front-end and the back-end are implemented using standard PCs and open- source software. After describing the architecture, evaluation is performed on a lab test-bed, to show its scalability. While the proposed solution allows to increase performance of PC- based routers, it also allows to distribute packet manipulation functionalities, and to automatically recover from component failures.

Efficient support of multicast traffic in storage area networks (SANs) enables applications such as remote data replication and distributed multimedia systems, in which a server must access concurrently multiple storage devices or, conversely, multiple servers must access data on a single device. In this paper we extend an innovative switching architecture, proposed in a previous paper, to support multicast traffic. We describe the most important aspects, focusing in particular on the mechanisms that permit to achieve lossless behavior. We then use simulation to analyze system performance and the impact of such mechanisms under various traffic patterns. Although the work is inspired by a specific switch architecture, results have a more general flavor and permit to highlight interesting trends in flow controlled architectures.

Optical switching fabrics (OSF) are considered to be appealing solutions for the design of high speed packet switches, due to their excellent scalability in terms of bandwidth and power consumption. Candidate technologies are MEMS, bubble switches, broadcast-and-select networks with tunable devices. All of them suffer a reconfiguration latency each time the input/output connections are changed, due to technological constraints; unfortunately, this latency is not negligible with respect to the packet transmission time, and can adversely affect performance, especially delay and throughput. When scheduling the transmission of packets across an OSF, the multi-hop approach was shown to be a promising way to control the tradeoff between delay and throughput. In this case, the OSF is configured just once in a while, on a time scale much larger than the packet transmission time, and packets may be recirculated across the ports to provide full or partial connectivity among ports. Previous works have investigated this approach when a physical ring topology is used for the interconnection. Here, we extend the multi-hop approach to multidimensional regular topologies, which offer a better tradeoff between throughput and delay. We discuss not only the scheduling problem for these topologies, but also the design of routing. We investigate performance by simple analytical models and show the design tradeoff among throughput, speedup and delays.

We focus on the identification and definition of "Web user-sessions", an aggregation of several TCP connections generated by the same source host on the basis of TCP connection opening time. The identification of a user session is non trivial; traditional approaches rely on threshold based mechanisms, which are very sensitive to the value assumed for the threshold and may be difficult to correctly set. By applying clustering techniques, we define a novel methodology to identify Web user-sessions without requiring an a priori definition of threshold values. We analyze the characteristics of user sessions extracted from real traces, studying the statistical properties of the identified sessions. From the study it emerges that Web user-sessions tend to be Poisson, but correlation may arise during periods of network/hosts anomalous functioning.

One of the most critical issues in wireless sensor networks is represented by the limited availability of energy within network nodes; thus, making good use of energy is a must to increase network lifetime. We define as network lifetime the period from the time instant when the network starts functioning till the network runs, satisfying its quality requirements, i.e., a given level of coverage in the area of interest is guaranteed. To maximize system lifetime, we exploit sensor spatial redundancy by defining sub-sets of sensors active in different time periods, to allow sensors to save energy when inactive. Two approaches are presented: the first one, based on mathematical programming techniques, must run in a centralized way; whereas the second one is based on a greedy algorithm, aimed at a distributed implementation. To assess their performance and provide guidance to network design, the two approaches are compared by varying several network parameters.

DAVID is a research project sponsored by the European Union aimed at the design of an optical packet-switched network for the transport of IP traffic. The DAVID network has a two-level hierarchical structure, with a backbone of optical packet routers interconnected in a mesh, and metropolitan areas served by sets of optical rings interconnected by passive memoryless devices called Hubs. The paper focuses on the metropolitan area network and its components: the nodes and the Huh. Access is regulated by a dynamic time-division multiple-access scheme allocating slots in sets of wavelengths that provide multichannel pipes among ring pairs. This paper proposes a new resource allocation scheme capable of transporting variable-size packets without segmentation into fixed-size data units. Resource sharing among nodes is granted by two scheduling algorithms running on different time scales: the first one is centralized at the Hub and provides coarse connectivity among ring pairs; the second one runs at nodes and provides finer node-to-node connectivity. The Hub scheduling algorithm is derived from well known algorithms in the literature; a novel heuristic scheduling algorithm running at nodes is proposed for datagram (not-guaranteed) traffic and its performance is studied by simulation.

We propose a novel framework to solve the problem of scheduling packets in high-speed input-queued switches with frame-based control. Our approach is based on the application of game theory concepts. We define a flexible scheduling policy, named SSB (slot sell and buy): the existence of a unique Nash equilibrium for the policy is proved, together with properties of convergence of these equilibria. These findings allows us to state that our SSB scheduling policy achieves 100% throughput both in isolated input-queued switches arid in networks of input-queued switches. Simulation results are used to further validate the approach and to show its flexibility in dealing with differentiated QoS guarantees.

The data and voice integration over dense wavelength-division-multiplexing (DAVID) project proposes a metro network architecture based on several wavelength-division-multiplexing (WDM) rings interconnected via a bufferless optical switch called Hub. The Hub provides a programmable interconnection among rings on the basis of the outcome of a scheduling algorithm. Nodes connected to rings groom traffic from Internet protocol routers and Ethernet switches and share ring resources. In this paper, we address the problem of designing efficient centralized scheduling algorithms for supporting multiclass traffic services in the DAVID metro network. Two traffic classes are considered: a best-effort class, and a high-priority class with bandwidth guarantees. We define the multiclass scheduling problem at the Hub considering two different node architectures: a simpler one that relies on a complete separation between transmission and reception resources (i.e., WDM channels) and a more complex one in which nodes fully share transmission and reception channels using an erasure stage to drop received packets, thereby allowing wavelength reuse. We propose both optimum and heuristic solutions, and evaluate their performance by simulation, showing that heuristic solutions exhibit a behavior very close to the optimum solution.

We focus on all-optical broadcast and select slotted WDM networks. Each network user is equipped with one tunable transmitter and one fixed receiver; full connectivity is achieved by tuning transmitters to all different wavelengths available in the optical spectrum. Tuning latencies are considered to be not negligible with respect to the slot time. A network controller allocates fixed size slots in a TDM/WDM frame according to requests issued by users via signalling procedures. User requests are accommodated in the frame incrementally, as soon as they are received by the network controller. Since we aim at an incremental solution, we impose a transparency constraint in the scheduling algorithm: new user requests may be accepted only without affecting existing allocations, otherwise they are refused. We propose a novel scheduling algorithm that may route some flows from source to destination through some intermediate nodes, following a multi-hop approach. A formal definition of an optimal transparent incremental scheduling algorithm is provided as an integer linear programming problem. The optimal incremental scheduling algorithm is NP-hard. Thus, a heuristic quasi-optimal scheduling algorithm is proposed, and its complexity is evaluated. Performance results show that significant benefits can be achieved with respect to traditional single-hop approaches and to other multi-hop approaches.

The paper studies input-queued packet switches loaded with both unicast and multicast traffic. The packet switch architecture is assumed to comprise a switching fabric with multicast (and broadcast) capabilities, operating in a synchronous slotted fashion. Fixed-size data units, called cells, are transferred from each switch input to any set of outputs in one time slot, according to the decisions of the switch scheduler, that identifies at each time slot a set of nonconflicting cells, i.e., cells neither coming from the same input, nor directed to the same output. First, multicast traffic admissibility conditions are discussed, and a simple counterexample is presented, showing intrinsic performance losses of input-queued with respect to output-queued switch architectures. Second, the optimal scheduling discipline to transfer multicast packets from inputs to outputs is defined. This discipline is rather complex, requires a queuing architecture that probably is not implementable, and does not guarantee in-sequence delivery of data. However, from the definition of the optimal multicast scheduling discipline, the formal characterization of the sustainable multicast traffic region naturally follows. Then, several theorems showing intrinsic performance losses of input-queued with respect to output-queued switch architectures are proved. In particular, we prove that, when using per multicast flow FIFO queueing architectures, the internal speedup that guarantees 100% throughput under admissible traffic grows with the number of switch ports.

The paper considers optical packet switching networks with slotted operation. A general model of network nodes is introduced, based upon a nonblocking switching fabric, and re-circulating fiber delay lines to solve contentions. Given the current large bandwidth availability in optical networks, and the projected limitations of electronic switches, a new approach to network design is proposed, aiming at balancing wavelength and buffer allocation taking the number of switch ports as a constraint. Given the problem complexity, a heuristic solution is proposed, using simple queuing theory to model network links. The effectiveness of the new network dimensioning approach is demonstrated by running a simulation program on manually dimensioned topologies, and on topologies dimensioned using the proposed approach.

We consider input-queued switch architectures dealing at their interfaces with variable-size packets, but internally operating on fixed-size cells. Packets are segmented into cells at input ports, transferred through the switching fabric, and reassembled at output ports. Cell transfers are controlled by a scheduling algorithm, which operates in packet-mode: all cells belonging to the same packet are transferred from inputs to outputs without interruption. We prove that input-queued switches using packet-mode scheduling can achieve 100% throughput, and we show by simulation that, depending on the packet size distribution, packet-mode scheduling may provide advantages over cell-mode scheduling.

We consider all-optical TDM/WDM broadcast and select networks. We assume that each network node is equipped with one fixed transmitter and one tunable receiver; tuning times are assumed to be not negligible with respect to the slot time. We discuss efficient scheduling algorithms to assign TDM/WDM slots to multicast traffic in such networks. Given the problem complexity, heuristic algorithms based on the Tabu Search methodology are proposed, and their performance is assessed using randomly created request matrices based on two types of multicast traffic patterns: a video-conference, and a server distribution traffic pattern. The considered performance index is the frame length required to schedule a given traffic request matrix.

This paper describes the network architecture and provides a performance analysis of a passive optical network named SONATA, which has been proposed and demonstrated in the European Union ACTS program. In this nationwide-all-optical network, end-terminals access a single passive routing node via PONs using a TDMA/WDMA access scheme based on slot reservations. The centralized network controller runs resource allocation algorithms to avoid conflicts among end-terminals. Since the resource allocation problem at the network controller can be shown to be in general NP-hard, we provide heuristic algorithms to solve the problem. The analysis of the algorithms is performed via both analysis and simulation.

This paper focuses on multicast support in input-queued packet switches with internal multicast capabilities. Besides providing an overview of some alternative architectures and algorithms proposed in the literature, the paper brings two original contributions. First, multicast traffic admissibility conditions are defined, and theorems showing intrinsic performance losses of input-queued with respect to output-queued switch architectures are proved. Second, the optimal scheduling discipline in transferring multicast packets from switch inputs to switch outputs is defined. From the definition of the optimal multicast scheduling discipline, the formal characterization of the sustainable multicast traffic region naturally follows. Both results aim at a correct formal definition of the considered problem, in order to identify a sound starting point for the design of heuristics that approximate the optimal solution at a complexity compatible with available technologies.

Input-queued switch architectures play a major role in the design of high performance switches and routers for packet networks. These architectures must be controlled by a scheduling algorithm, which solves contentions in the transfer of data units from inputs to outputs. Several scheduling algorithms were proposed in the literature for input-queued cell switches, operating on fixed-size data units. In this paper we consider the case of packet switches, i.e., devices operating on variable-size data units at their interfaces, but internally operating on cells, and we propose novel extensions of known scheduling algorithms. We prove that the maximum throughput achievable by input-queued packet switches is identical to that achievable with input- and output-queued cell switches. We show by simulation that, in the case of packet switches, input-queued architectures may provide performance advantages over output-queued architectures.

In this paper we discuss the throughput achievable in input-queued cell-based switches loaded with multicast traffic. The switch architecture is assumed to comprise a synchronous broadcast switching fabric, where fixed-size data units, called cells, can be transferred in one slot from one Input to any set of outputs. The switch scheduler must select the time slots for transfers of non-conflicting cells, i.e., cells neither coming from the same input nor directed to the same output. Contrary to the case of unicast traffic, for which input-queued switches were proved to yield the same throughput as output queued switches, we show by simulation experiments and analytical modeling that throughput limitations exist in input-queued switches loaded with multicast traffic.

We present an analytical approach for the joint optimization of quality of service (in terms of call blocking probability) and tariffs for a mobile telephony network. The analytical approach is based on the combination of traditional telecommunication system design techniques and econometric approaches for profit maximization.

We focus on all-optical broadcast and select slotted WDM networks. Each network user is equipped with one tunable transmitter and one fixed receiver; full connectivity is achieved by tuning transmitters to all different wavelengths available in the optical spectrum. Tuning latencies are considered to be not negligible with respect to the slot time. A centralized network controller allocates slots in a TDM/WDM frame according to requests issued by users. User requests are accommodated in the frame incrementally, as soon as they are received by the network controller. We propose a novel scheduling algorithm that may route some flows from source to destination through some intermediate nodes, following a multi-hop approach. Since we aim at an incremental solution, we impose a transparency constraint: new user requests may be accepted only without affecting existing allocations, otherwise they are refused. A heuristic quasi-optimal scheduling algorithm is proposed. Performance results show that significant benefits can be achieved with respect to traditional single-hop approaches.

This paper describes the network architecture and provides a performance analysis of a passive optical network named SONATA, which has been proposed and demonstrated in the context of the European Union ACTS Program. In this nationwide all-optical network, end terminals access a single passive routing node via PONs using a TDMA/WDMA access scheme based on reservations. The centralized network controller runs resource allocation algorithms in order to avoid conflicts among end terminals. We formally define the resource allocation problem at the network controller, and show that, in general, it is NP-hard. We also provide simple heuristic algorithms to solve the problem. The analysis of the algorithms is performed both via analysis and simulation.

This paper addresses the design of packet transmission schedules in photonic slotted wavelength-division multiplexing/time-division multiplexing broadcast-and-select networks with W wavelengths and N nodes. Nodes are equipped with one tunable-wavelength transmitter with nonnegligible tuning times and one fixed-wavelength receiver. A new scheduling algorithm that exploits multihop packet transfer to shorten the duration of scheduling periods is first proposed. A single-hop scheduling algorithm that performs slightly better than previous proposals is then described. A simulation-based analysis of the two algorithms shows that they jointly lead to significant improvements in both throughput and delay with respect to previous single-hop schedules.

This paper addresses the problem of radio resource allocation for packet switched wireless networks. The proposed approach is based on a FDMA/TDMA scheme with time slot partitioning and exploits the reuse factor concept applied to the time domain. This technique is used in combination with a specific time slot assignment in the MAC protocol, so that radio resources sharing among users within the same cell is controlled, while interference among users belonging to different cells is minimized. The scheme allows mobile users to make soft handovers while they move from one cell to contiguous ones. Adaptive time slot allocation algorithms can be envisioned to deal with hot spot traffic without requiring major frequency allocation replanning. Preliminary performance results that show that throughput benefits can be obtained are presented.

This paper presents and evaluates a quasi-optimal scheduling algorithm for input buffered cell-based switches, named reservation with preemption and acknowledgment (RPA). RPA is based on reservation rounds where the switch input ports indicate their most urgent data transfer needs, possibly overwriting less urgent requests by other input ports, and an acknowledgment round to allow input ports to determine what data they can actually transfer toward the desired switch output port. RPA must be executed during every cell time to determine which cells can be transferred during the following cell time. RPA is shown to be as simple as the simplest proposals of input queuing scheduling, efficient in the sense that no admissible traffic pattern was found under which RPA shows throughput limitations, and flexible, allowing the support of packet-mode operations and different traffic classes with either strict priority discipline or bandwidth guarantee requirements. The effectiveness of RPA is assessed with detailed simulations in uniform as well as unbalanced traffic conditions and its performance is compared with output queuing switches and the optimal maximum weighted matching (MWM) algorithm for input-buffered switches. A bound on the performance difference between the heuristic weight matching adopted in RPA and MWM is analytically computed.

This paper presents and evaluates a quasi-optimal policy for input buffered ATM switches, named RPA (reservation with preemption and acknowledgment), comprising an input queuing discipline and a cell scheduling algorithm. RPA is based on reservation rounds where the switch input ports can indicate their most urgent cell transfer needs, possibly overwriting less urgent requests by other input ports, and an acknowledgment round to allow input ports to determine what cell they can actually transfer toward the desired switch output port. RPA is shown to be simpler than previous proposals of input queuing policies, efficient and flexible, allowing the support of different traffic classes and packet-mode operations. The effectiveness of RPA is assessed with detailed simulations in uniform, as well as unbalanced, traffic conditions.

This paper considers SRR (synchronous round robin), an almost optimal collision-free access scheme for all-optical packet networks based on WDM multi-channel ring topologies providing slotted channels for transmissions to disjoint subsets of destination nodes. Only a channel inspection capability and local status information are required at nodes in order to implement the access protocol. Since SRR is not able to enforce fairness by itself, MMR (multi MetaRing), a fairness control algorithm derived from those adopted in the MetaRing high-speed metropolitan area network, is superimposed to SRR. Our analysis proves that the considered access scheme, in spite of its simplicity, allows an almost optimal exploitation of the available resources while guaranteeing a fair access to all nodes.

Different rule execution semantics may be available in the same active database system. We perform several simulation experiments to evaluate the performance trade-offs yielded by different execution semantics in various operating conditions. In particular, we evaluate the effect of executing transaction and rule statements that affect a varying number of data instances, and applications with different rule triggering breadth and depth. Since references to data changed by the database operation triggering the rules are commonly used in active rule programming, we also analyze the impact of its management on overall performance.

The paper describes SR/sup 3/ (synchronous round robin with reservations) a collision-free medium access control protocol for all-optical slotted packet networks based on WDM multi-channel ring topologies where the nodes are equipped with one fixed-wavelength receiver and one wavelength-tunable transmitter. SR/sup 3/ is derived from the SRR and MMR protocols previously proposed by the authors for the same class of all-optical networks. SRR and MMR already achieve an efficient exploitation of the available bandwidth, while guaranteeing a throughput-fair access to each node. SR/sup 3/, in addition, allows the nodes to reserve slots, thereby achieving a stronger control on access delays; it is thus well suited to meet tight delay requirements, as is the case for multimedia applications. Simulation results show that SR/sup 3/ provides very good performance to guaranteed quality traffic, but also brings significant performance improvements for best-effort traffic.

WDM rings are receiving significant attention in the field of all-optical networks because their implementation appears to be feasible with state-of-the-art components. Several MAC protocols were recently proposed in order to resolve contentions among nodes sharing the available wavelengths in WDM rings. These MAC protocols achieve high efficiency but unsatisfactory fairness, due to the asymmetric position of sources with respect to destinations. Thus, in order to improve fairness, it is necessary to adopt a fairness control scheme. We discuss the adaptation of the MetaRing fairness control scheme to the context of WDM multi-channel rings. Several alternatives are considered and compared via simulation.

The paper considers medium access control protocols for all-optical packet networks based on WDM multichannel ring topologies where nodes are equipped with one fixed-wavelength receiver and one wavelength-tunable transmitter. Such networks provide separate channels for slotted transmissions to disjoint subsets of destination nodes. Some simple access protocols based on local status information are described. Since these protocols are not able to enforce fairness by themselves, fairness control algorithms derived from those adopted in the Metaring high-speed metropolitan area network are also proposed. Analytical and simulation results are presented to assess the capacity of the proposed protocols in uniform traffic conditions, with a particular focus on the case where at each node the packet to be transmitted is randomly selected. In spite of the simplicity of the proposed access schemes, numerical results show that good performance can be achieved and the fairness problems inherent in the considered network topologies can be overcome.

Performance analysis and formal correctness verification of computer communication protocols and distributed systems have traditionally been considered as two separate fields. However, their integration can be achieved by using formal description techniques as paradigms for the development of performance models. This paper presents a novel extension of LOTOS, one of the two formal specification languages that were standardized by ISO. The extension is specifically conceived to integrate performance analysis and formal verification. The extended language syntax and semantics are formally defined, along with a mapping from extended specifications to performance models, The mapping preserves the specified observable behavior. Two simple examples, a stop-and-wait protocol and a time-sharing system, are used to concretely demonstrate the new approach and to validate it.>

Two regular meshed topologies are compared in terms of their possible use for implementing large all-optical wavelength routing communication networks or interconnection systems. It is assumed that the networks provide full connectivity among users and operate with either packet or circuit switching in a wavelength-division-multiplexing (WDM) environment, so that source-destination pairs are identified through a frequency and a physical path. The topologies considered are the K-dimensional bidirectional square lattice and the shuffle topology. The comparison is based on the maximum and average distance between nodes, and on the minimum number of identifiers (frequencies in the WDM comb) necessary to discriminate all source-destination pairs.>

Three regular meshed topologies are compared in light of their possible use for the implementation of large all-optical wavelength-routing communication networks (or interconnection systems). These systems provide all source-destination pairs with end-to-end transparent channels that are identified through a wavelength and a physical path. The considered topologies are the K-dimensional bidirectional square lattice, the twin shuffle, and the de Bruijn graph. The comparison is based on the maximum and average distance between source and destination (number of traversed nodes), on the degree of connectivity for each node (number of input and output fibers), and on the minimum number of wavelengths in the WDM comb necessary to discriminate all source-destination pairs.>