Federated testbeds enable collaborative research by providing access to diverse resources, including computing power, storage, and specialized hardware like GPUs, programmable switches and smart Network Interface Cards (NICs). Efficiently sharing these resources across federated institutions is challenging, particularly when resources are scarce and costly. GPUs are crucial for AI and machine learning research, but their high demand and expense make efficient management essential. Similarly, advanced experimentation on programmable data plane requires very expensive programmable switches (e.g., based on P4) and smart NICs. This paper introduces SHARY (SHaring Any Resource made easY), a dynamic reservation system that simplifies resource booking and management in federated environments. We show that SHARY can be adopted for heterogenous resources, thanks to an adaptation layer tailored for the specific resource considered. Indeed, it can be integrated with FIGO (Federated Infrastructure for GPU Orchestration), which enhances GPU availability through a demand-driven sharing model. By enabling real-time resource sharing and a flexible booking system, FIGO improves access to GPUs, reduces costs, and accelerates research progress. SHARY can be also integrated with SUP4RNET platform to reserve the access of P4 switches.

In resource-constrained cloud systems, e.g., at the network edge or in private clouds, serverless computing is increasingly adopted to deploy microservices-based applications, leveraging its promised high resource efficiency. Provisioning resources to serverless services, however, poses several challenges, due to the high cold-start latency of containers and stringent Service Level Agreement (SLA) requirements of the microservices. In response, we investigate the behavior of containers in different states (i.e., running, warm, or cold) and exploit our experimental observations to formulate an optimization problem that minimizes the energy consumption of the active servers while reducing SLA violations. In light of the problem complexity, we propose a low-complexity algorithm, named AiW, which utilizes a multi-queueing approach to balance energy consumption and system performance by reusing containers effectively and invoking cold-starts only when necessary. To further minimize the energy consumption of data centers, we introduce the two-timescale COmputing resource Management at the Edge (COME) framework, comprising an orchestrator running our proposed AiW algorithm for container provisioning and Dynamic Server Provisioner (DSP) for dynamically activating/deactivating servers in response to AiW’s decisions on request scheduling. COME addresses the mismatch in timescales for resource provisioning decisions at the container and server levels. Extensive performance evaluation through simulation shows AiW’s close match to the optimum and COME’s significant reduction in power consumption by 22–64% compared state-of-the-art alternatives.

Stateful migration has emerged as the dominant technology to support microservice mobility at the network edge while ensuring a satisfying experience to mobile end users. This work addresses two pivotal challenges, namely, the implementation and the orchestration of the migration process. We first introduce a novel framework that efficiently implements stateful migration and effectively orchestrates the migration process by fulfilling both network and application KPI targets. Through experimental validation using realistic microservices, we then show that our solution (i) greatly improves migration performance, yielding up to 77% decrease of the migration downtime with respect to the state of the art, and (ii) successfully addresses the strict user QoE requirements of critical scenarios featuring latency-sensitive microservices. Further, we consider two practical use cases, featuring, respectively, a UAV autopilot microservice and a multi-object tracking task, and demonstrate how our framework outperforms current state-of-the-art approaches in configuring the migration process and in meeting KPI targets.

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.

Stateful migration has emerged as the dominant technology to support microservice mobility at the network edge while meeting the end users' QoE requirements. In this context, our work addresses the two pivotal challenges of implementing and orchestrating the migration process. We first introduce a novel orchestration framework that efficiently realizes stateful migration and effectively orchestrates the migration process by fulfilling both network and application KPI targets. Then, through experimental validation using realistic microservices, we show that our solution improves migration performance, yielding up to 80 % decrease of the migration downtime with respect to the state of the art. Finally, we demonstrate that our framework can be exploited to successfully address critical scenarios featuring latency-sensitive microservices and strict user QoE requirements.

The practice of people counting serves as an indispensable tool for meticulously monitoring crowd dynamics, enabling informed decision-making in critical situations, and optimizing the management of urban spaces, facilities, and services. Beyond its fundamental role in safety and security, tracking people’s flows has evolved into a necessity for diverse business applications and the effective administration of both outdoor and indoor urban environments. In the ongoing exploration of the study, emphasis is placed on employing a passive counting technique. This method leverages WiFi probe request messages emitted by smart devices to assess the number of devices, providing a reliable estimate of the number of people in a specific area. However, it is crucial to acknowledge the dynamic landscape of privacy regulations and the concerted efforts by leading smart-device manufacturers to fortify user privacy, as evidenced by the adoption of MAC address randomization. In response to these considerations, an enhanced iteration of the WiFi traffic generator has been introduced. This upgraded version is designed to generate realistic datasets with ground truth, aligning with the evolving privacy landscape. Additionally, leveraging a profound understanding of probe requests and the capabilities of the designed generator, a novel crowd monitoring solution that incorporates machine learning techniques, named ARGO, has been developed. This innovative approach effectively addresses challenges posed by randomized MAC addresses, incorporating Bloom filters to ensure a formal “deniability” that complies with stringent regulations, including the European GDPR (European Parliament, Council of the European Union, Regulation (EU), 2016). The proposed solution adeptly addresses the pivotal task of people counting by harnessing WiFi probe request messages. Significantly, it prioritizes users’ privacy, aligning with the foundational principles outlined in regulations such as the European GDPR.

Stateful migration has emerged as the key solution to support latency-sensitive microservices at the edge while ensuring a satisfying experience for mobile users. In this paper, we address two relevant issues affecting stateful migration, namely, the migration of containerized microservices and that of the associated data connection. We do so by first introducing a novel network solution, based on OvS, that permits to preserve the established connection with mobile end users upon migrating a microservice. Then, using Podman and CRIU, we experimentally characterize the fundamental migration KPIs, i.e., migration duration and microservice downtime, and we devise an analytical model that, accounting for all the relevant real-world aspects of stateful migration, provides an accurate upper bound on such KPIs. We validate our model using real-world microservices, namely, MQTT Broker and Memcached, and show that it can predict KPIs values with an error that is up to 99.7% smaller than that yielded by the state of the art. Finally, we consider a UAV controller as relevant microservice use case and demonstrate how our model can be exploited to effectively configure the system parameters so that the required QoE level is met.

Everyday, as we go about our business in a city, we carry around several devices such as smartphones, tablets or even laptops, most of them with an active WiFi interface. This interface “leaks” wireless traces, or footprints, in the form of beacon or probe packets that can be used to identify the presence of people in certain areas. In particular, the analysis of device footprints allows the detection, tracking and monitoring of people in indoor and outdoor scenarios. In this paper, we focus on the probe request messages broadcast by wireless devices and we analyze the behaviour and the characteristics of these messages from different devices, coming from various vendors, with different operating systems and features, also considering the user interaction with them. In particular, we provide a detailed picture of the adoption of MAC address randomization techniques, and on the variety of fields present within the probe request messages.

Serverless edge computing allows for highly efficient resource utilization, reducing the energy footprint of edge data centers. Indeed, the containers can be dynamically created and destroyed, allowing to adapt the workload to the available resources. Creating containers upon arrivals of service requests entails, however, a high start-up latency, which may be unsuitable for time-critical services. As alternative solution, pre-started containers (“warm containers”) are used to decrease start-up latency, but incurring in higher resource costs. In this work, we minimize the energy consumption of the active servers in the data center by optimally managing the various container states while meeting the target delay of the requested services. Further, in light of the problem complexity, we investigate how a simple threshold-based algorithm performs and show that it can closely match the optimum.

To support latency sensitive microservices at the edge, stateful container migration has gathered momentum as a key solution to ensure a satisfying experience to mobile users. In this paper, we first investigate experimentally the stateful migration process, by using state-of-the-art tools, namely, Podman and CRIU. We then characterize the main migration KPIs, i.e., migration duration and downtime, and develop an analytical model that can effectively assess whether stateful migration is feasible while meeting the user's QoE requirements. Importantly, our model is validated using real-world microservices and, by accounting for all relevant real-world aspects of stateful migration, significantly outperforms state-of-the-art models.

In resource-constrained cloud systems, e.g., at the network edge or in private clouds, it is essential to deploy microservices (MSs) efficiently. Unlike most of the existing approaches, we tackle this issue by accounting for two important facts: (i) the interference that arises when MSs compete for the same resources and degrades their performance, and (ii) the MSs’ deployment time. In particular, we first present some experiments highlighting the impact of interference on the throughput of MSs co-located in the same server, as well as the benefits of MSs’ parallel deployment. Then, we formulate an optimization problem that minimizes the number of used servers while meeting the MSs’ performance requirements. In light of the problem complexity, we design a low-complexity heuristic, called iPlace, that clusters together MSs competing for resources as diverse as possible and, hence, interfering as little as possible. Importantly, clustering MSs also allows us to exploit the benefit of parallel deployment, which greatly reduces the deployment time as compared to the sequential approach applied in prior art and by default in state-of-the-art orchestrators. Our numerical results show that iPlace closely matches the optimum and uses 21-92% fewer servers compared to alternative schemes while proving to be highly scalable. Further, by deploying MSs in parallel using Kubernetes, iPlace reduces the deployment time by 69% compared to state-of-the-art solutions.

We consider a hierarchical edge-cloud architecture in which services are provided to mobile users as chains of virtual network functions. Each service has specific computation requirements and target delay performance, which require placing the corresponding chain properly and allocating a suitable amount of computing resources. Furthermore, chain migration may be necessary to meet the services’ target delay. We model and formalize the problem of finding a feasible chain placement and resource allocation, while minimizing the migration, bandwidth, and computation costs. We tackle this problem by partitioning it into a (i) CPU allocation problem, and a (ii) placement problem. For the CPU allocation problem, we find an optimal solution. For the placement problem, we show that even finding a feasible solution is NP-hard, and envision an algorithm that is guaranteed to find a feasible solution while leveraging a bounded amount of resource augmentation. Our algorithms are incorporated into a solution framework that aims to minimize both the cost and the required resource augmentation. The results, obtained through trace-driven, large-scale simulations, show that our framework can provide a close-to-optimal solution while running several orders of magnitude faster than an ILP solver.

Efficiently deploying microservices (MSs) is critical, especially in data centers at the edge of the network infrastructure where computing resources are precious. Unlike most of the existing approaches, we tackle this issue by accounting for the interference that arises when MSs compete for the same resources and degrades their performance. In particular, we first present some experiments highlighting the impact of interference on the throughput of co-located MSs. Then, we formulate an optimization problem that minimizes the number of used servers while meeting the MSs’ performance requirements. In light of the problem complexity, we design a low-complexity heuristic, called iPlace, that clusters together MSs competing for resources as diverse as possible and, hence, interfering as little as possible. Importantly, the choice of clustering MSs allows us to exploit the benefit of parallel MSs deployment, which, as shown by experimental evidence, greatly reduces the deployment time as compared to the sequential approach applied in prior art. Our numerical results show that iPlace closely matches the optimum and uses 10-63% fewer servers compared to alternative schemes, while proving to be highly scalable.

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 intrinsically inefficient service provisioning in traditional networks, Network Function Virtualization (NFV) keeps gaining attention from both industry and academia. By replacing the purpose-built, expensive, proprietary network equipment with software network functions consolidated on commodity hardware, NFV envisions a shift towards a more agile and open service provisioning paradigm. During the last few years, a large number of NFV platforms have been implemented in production environments that typically face critical challenges, including the development, deployment, and management of Virtual Network Functions (VNFs). Nonetheless, just like any complex system, such platforms commonly consist of abounding software and hardware components and usually incorporate disparate design choices based on distinct motivations or use cases. This broad collection of convoluted alternatives makes it extremely arduous for network operators to make proper choices. Although numerous efforts have been devoted to investigating different aspects of NFV, none of them specifically focused on NFV platforms or attempted to explore their design space. In this paper, we present a comprehensive survey on the NFV platform design. Our study solely targets existing NFV platform implementations. We begin with a top-down architectural view of the standard reference NFV platform and present our taxonomy of existing NFV platforms based on what features they provide in terms of a typical network function life cycle. Then we thoroughly explore the design space and elaborate on the implementation choices each platform opts for. We also envision future challenges for NFV platform design in the incoming 5G era. We believe that our study gives a detailed guideline for network operators or service providers to choose the most appropriate NFV platform based on their respective requirements. Our work also provides guidelines for implementing new NFV platforms.

Several applications for connected cars leverage the mobility information periodically broadcasted by cars through standard vehicle-to-vehicle messages. We propose an architecture in which each car generates and sends reports including the messages received from its neighbors to the access network infrastructure. The infrastructure collects and stores the received reports through multiple blockchains, each of them referring to a different geographical area. A smart contract is then executed to verify the spatial coherence among the received data. We implement a proof-of-concept of such a solution using Hyperledger Fabric, and we investigate the scalability of our solution in terms of resource consumption in a MEC system.

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.

Software switches are increasingly used in network function virtualization (NFV) to route traffic between virtualized network functions (VNFs) and physical network interface cards (NICs). Understanding of alternative switch designs remains deficient, however, in the absence of a comprehensive, comparative performance analysis. In this paper, we propose a methodology intended to be fair and use it to compare the performance of seven state-of-the-art software switches. We first explore their respective design spaces and then compare their performance under four representative test scenarios. Each scenario corresponds to a specific case of routing NFV traffic between NICs and/or VNFs. Our experimental results show that no single software switch prevails in all scenarios. It is therefore important to choose the one that is best adapted to a given use-case. The presented results and analysis bring a better understanding of design tradeoffs and identify potential bottlenecks that limit the performance of software switches.

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.

Interest in software networking has grown significantly since the introduction of Network Function Virtualization (NFV). Software switches are used in NFV to steer traffic between different virtualized network functions and physical Network Interface Cards (NICs). It is becoming more and more important to objectively evaluate and compare the performance of the multiple alternative implementations that have recently been proposed. A comprehensive performance analysis is still missing for two main reasons: (i) the amount of time required to configure and compare all such tools is enormous; (ii) it is very difficult to define a proper methodology to compare different solutions in a fair manner. In this paper we propose a methodology based on four simple yet representative test scenarios used to evaluate the performance of software switches. We apply this methodology to measure throughput and latency metrics for 6 state-of-the-art software switches namely, OVS-DPDK, snabb, BESS, FastClick, VPP and netmap VALE. Our work constitutes a first step to building a better understanding of design tradeoffs and identifying performance bottlenecks.

In the last few years, several software-based solutions have been proved to be very efficient for high-speed packet processing, traffic generation, and monitoring, and can be considered valid alternatives to expensive and non-flexible hardware-based solutions. In this paper, we first benchmark heterogeneous design choices for software-based packet monitoring systems in terms of achievable performance and required resources (i.e., the number of CPU cores). Building on this extensive analysis we design FloWatcher-DPDK, a DPDK-based high-speed software traffic monitor we provide to the community as an open source project. In a nutshell, FloWatcher-DPDK provides tunable fine-grained statistics at packet and flow levels. Experimental results demonstrate that FloWatcher-DPDK sustains per-flow statistics with 5-nines precision at high-speed (e.g., 14.88 Mpps) using a limited amount of resources. Finally, we showcase the usage of FloWatcher-DPDK by configuring it to analyze the performance of two open source prototypes for stateful flow-level end-host and in-network packet processing.

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.

The huge increase of population living in cities calls for a sustainable urban development. Mobile crowdsensing (MCS) leverages participation of active citizens to improve performance of existing sensing infrastructures. In typical MCS systems, sensing tasks are allocated and reported on individual-basis. In this paper, we investigate on collaboration among users for data delivery as it brings a number of benefits for both users and sensing campaign organizers and leads to better coordination and use of resources. By taking advantage from proximity, users can employ device-to-device (D2D) communications like Wi-Fi Direct that are more energy efficient than 3G/4G technology. In such scenario, once a group is set, one of its member is elected to be the owner and perform data forwarding to the collector. The efficiency of forming groups and electing suitable owners defines the efficiency of the whole collaborative-based system. This paper proposes three policies optimized for MCS that are compliant with current Android implementation of Wi-Fi Direct. The evaluation results, obtained using CrowdSenSim simulator, demonstrate that collaborative-based approaches outperform significantly individual-based approaches.

The unprecedented growth of the population living in urban environments calls for a rational and sustainable urban development. Smart cities can fill this gap by providing the citizens with high-quality services through efficient use of Information and Communication Technology (ICT). To this end, active citizen participation with mobile crowdsensing (MCS) techniques is a becoming common practice. As MCS systems require wide participation, the development of large scale real testbeds is often not feasible and simulations are the only alternative solution. Modeling the urban environment with high precision is a key ingredient to obtain effective results. However, currently existing tools like OpenStreetMap (OSM) fail to provide sufficient levels of details. In this paper, we apply a procedure to augment the precision (AOP) of the graph describing the street network provided by OSM. Additionally, we compare different mobility models that are synthetic and based on a realistic dataset originated from a well known MCS data collection campaign (ParticipAct). For the dataset, we propose two arrival models that determine the users' arrivals and match the experimental contact distribution. Finally, we assess the scalability of AOP for different cities, verify popular metrics for human mobility and the precision of different arrival models.

Users of device-to-device (D2D) communication need efficient content discovery mechanisms to steer their requests toward the node in their neighborhood that is most likely to satisfy them. The problem is further compounded by the lack of a central coordination entity as well as by the inherent mobility of devices, which leads to volatile topologies. In this paper, we first discuss group-based communication among non-rooted Android devices using Wi-Fi direct, a protocol recently standardized by the Wi-Fi alliance. We propose intra- and inter-group communication methodologies, which we validate through a simple testbed where content-centric routing is used. Next, we address the autonomous formation of groups with the goal of achieving efficient device resource utilization as well as full connectivity. Finally, we evaluate the performance of our group formation procedure both in simulation and in a real testbed involving Android devices in different topologies.

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.

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.

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.

In this paper we propose, implement and evaluate a bandwidth aggregation service for residential users that enhances the throughput of their Internet broadband connection through the aggregation of available capacity at neighboring broadband links. Network resources are aggregated by the residential access gateway using the 802.11 radio interface to simultaneously serve home users and to share the broadband connectivity with neighboring access gateways. Differently from previous works, our aggregation scheme is transparent both for local users, who are not required to modify their applications or device drivers, and for neighboring users, who do not experience any meaningful performance degradation. The proposed approach aims at a commercial deployment, leveraging on existing access gateways and ADSL-based access networks.

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.

The added value of Device-to-Device (D2D) communication amounts to an efficient content discovery mechanism that enables users to steer their requests toward the node most likely to satisfy them. In this paper, we address the implementation of content-centric routing in a D2D architecture for Android devices based on WiFi Direct, a protocol recently standardised by the Wi-Fi Alliance. After discussing the creation of multiple D2D groups, we introduce novel paradigms featuring intra- and inter-group bidirectional communication. We then present the primitives involved in content advertising and requesting among members of the multi-group network. Finally, we evaluate the performance of our architecture in a real testbed involving Android devices in different group configurations. We also compare the results against the ones achievable exploiting Bluetooth technologies.

In our companion WoWMoM 2015 paper [1], we propose a content-centric routing mechanism for Wi-Fi Direct networks. In that paper, we showed how to implement a Wi-Fi Direct multi-group network with unrooted Android devices that supports bidirectional communication between different groups. We devised on it a content-centric application, denoted as Multi-Group Content (MGC), that enables content request and delivery in a distributed and cooperative way. Finally, we demonstrated our application with Android devices to fully validate our approach and assess its performance. Aim of the current demonstration is to allow demo session attendees to experiment MSG and assess its behavior and performance in real time.

To assess the performance of caching systems, the definition of a proper process describing the content requests generated by users is required. Starting from the analysis of traces of YouTube video requests collected inside operational networks, we identify the characteristics of real traffic that need to be represented and those that instead can be safely neglected. Based on our observations, we introduce a simple, parsimonious traffic model, named shot noise model (SNM), that allows us to capture temporal and geographical locality of content popularity. The SNM is sufficiently simple to be effectively employed in both analytical and scalable simulative studies of caching systems. We demonstrate this by analytically characterizing the performance of the LRU caching policy under the SNM, for both a single cache and a network of caches. With respect to the standard independent reference model (IRM), some paradigmatic shifts, concerning the impact of various traffic characteristics on cache performance, clearly emerge from our results.

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.

Cooperative caching schemes allow to improve the performance of multi-hop networks based on device-to-device (D2D) communications. Indeed, each node does not only share its transmission capabilities to physically extend the network, but it also shares its storage to cache copies of contents for the sake of other nodes. It results in an increased network performance for users, since caching decreases both network load and latency to reach a content. The design of effective caching policies in a network of caches is very challenging and all the known solutions must be adapted both to the topology and to the request traffic pattern. In this paper, we consider a linear topology, representing a sequence of adjacent nodes, investigating the performances of both local and distributed cooperative caching policies. We specifically investigate where to apply the caching policy. Interestingly, we show that a simple local caching policy, that caches only the contents requested by the node itself, is not worse (or even better) than distributed policies, in which the content is eventually cached across the path from the requester node to the closest copy of the content. In some sense, we show that simplicity pays off.

We consider the problem of scheduling the transmission of packets in an input-queued switch. In order to achieve maximum throughput, scheduling algorithms usually employ the queue length as a parameter for determining the priority to serve a given queue. In this work, we propose a novel scheme to optimize the performance of a preexisting scheduler. Our main idea is to assist the scheduling decision, considering "messagesâ rather than queue lengths. Such messages are obtained by running an iterative parallel algorithm, inspired by a rigorous belief-propagation approach. We demonstrate that belief-propagation-assisted scheduling is able to boost the performance of a given scheduler, reaching almost optimal throughput, even under critical traffic scenarios.

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.

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.

Today, the permutation of circuits in the Main Distribution Frames (MDF), which connect the subscriber lines to POTS and to DSLAMs, is still operated manually. However, new market regulations, allowing subscribers to change network operator frequently, and the new schemes to concentrate active ADSL users into few DSLAMs during off-peak hours, adopted by network operators to reduce the energy consumption in the access network (and the related operational costs), require more advanced, reliable and faster mechanisms than human operations. Indeed, Automated MDFs (AMDF) have recently become available on the market to provide cheap and almost real-time circuit switching. Even if grounded on more than 50 years of research activities on architectures for circuit switching, the considered scenario is quite peculiar and offers new interesting technical challenges, since classical multistage strictly non-blocking networks are too expensive for the number of required ports (sometimes very large, exceeding 100,000), and rearrangeable multistage networks can interrupt temporarily active circuits, affecting in a indefinite way the performance of ADSL lines. For these reasons, we propose the design of AMDFs based on recently proposed non-interruptive rearrangeable (NIR) networks and show how to optimize the routing control to minimize the setup time of a circuit. Finally, our findings are relevant both for the theory of multistage interconnection networks, and for those companies producing, engineering and operating large AMDFs.

WiFi-enabled buses and stops may form the backbone of a metropolitan delay tolerant network, that exploits nearby communications, temporary storage at stops, and predictable bus mobility to deliver non-real time information. This paper studies the problem of how to route data from its source to its destination in order to maximize the delivery probability by a given deadline. We assume to know the bus schedule, but we take into account that randomness, due to road traffic conditions or passengers boarding and alighting, affects bus mobility. We propose a simple stochastic model for bus arrivals at stops, supported by a study of real-life traces collected in a large urban network. A succinct graph representation of this model allows us to devise an optimal (under our model) single-copy routing algorithm and then extend it to cases where several copies of the same data are permitted. Through an extensive simulation study, we compare the optimal routing algorithm with three other approaches: minimizing the expected traversal time over our graph, minimizing the number of hops a packet can travel, and a recently-proposed heuristic based on bus frequencies. Our optimal algorithm outperforms all of them, but most of the times it essentially reduces to minimizing the expected traversal time. For values of deadlines close to the expected delivery time, the multi-copy extension requires only 10 copies to reach almost the performance of the costly flooding approach.

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.

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.

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.

In the recent years, message-passing paradigm has emerged as a canonical algorithmic solution to solve networkwide problems by means of minimal local information exchange, across variety of disciplines. The primary purpose of this work is to understand tradeoffs offered between network performance and protocol overhead by a class of message-passing algorithms - belief propagation and its variants. Through an extensive simulation study, for prototypical network topological models, we find that such class can lead to wireless network scheduling algorithms under which each node exchanges exactly one message per time-slot and achieve reasonably high performance. This algorithm utilizes the "continuity" of network state to achieve high performance in presence of minimal information exchange.

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.

We provide the scaling laws for the transport capacity of a wide class of mobile wireless ad hoc networks. Our analysis generalizes previous results obtained under restrictive assumptions on the node mobility process and overall node density over the network area. The broader family of mobile networks that we consider is able to account for many important characteristics usually recognized in real traces of both human and vehicular mobility. In particular, we consider clustered, sparse networks of heterogeneous nodes, in which the shape of the spatial distribution of each node around one or more home-points plays a fundamental role in determining the overall transport capacity. We identify different operational regimes that arise within our general class of mobile networks, and for each regime we propose optimal scheduling and routing strategies achieving the maximum asymptotic capacity.

Input queued (IQ) switches exploiting buffered crossbars (CICQ switches) are widely considered very promising architectures that outperform IQ switches with bufferless switching fabrics both in terms of architectural scalability and performance. Indeed the problem of scheduling packets for transfer through the switching fabric is significantly simplified by the presence of internal buffers in the crossbar, which makes possible the adoption of efficient, simple and fully distributed scheduling algorithms. This paper studies the throughput performance of CICQ switches supporting multicast traffic, showing that, similarly to IQ architectures, also CICQ switches with arbitrarily large number of ports may suffer of significant throughput degradation under ldquopathologicalrdquo multicast traffic patterns. Despite the asymptotic nature of these results, the authors believe that they can contribute to a deeper understanding of the behavior of CICQ architectures supporting multicast traffic.

In this paper, we study the performance of the 2-hop routing scheme proposed for ad hoc wireless networks with mobile nodes, considering realistic node mobility patterns. First, we provide a formal definition of optimal routing maximizing the throughput of a mobile ad hoc network, in terms of a multi-commodity flow problem over the associated contact graph. Then, we relate the effectiveness of the 2-hop routing strategy to structural properties of the contact graph. We present experimental results showing that, in real networks, contact times among the nodes are largely inhomogeneous. Our results show that, in networks with inhomogeneous contact times, the 2-hop routing strategy can result strongly inefficient in terms of network throughput.

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.

We revisit the problem of characterizing the capacity of an ad hoc wireless network with n mobile nodes. Grossglauser and Tse (2001) showed that, by exploiting user mobility, it is possible to maintain a constant per-node throughput as the number of nodes grows. Their scheme allows to overcome the throughput decay (at least as 1/radicn) that affects networks with static nodes, which was first pointed out by Gupta and Kumar (2000). Subsequent works have analyzed the delay-capacity trade-off that arises in mobile networks under various mobility models. Almost invariably, however, available asymptotic results strongly rely on the assumption that nodes are identical, and move according to some ergodic process that is equally likely to visit any portion of the network area. In this paper, we relax such 'homogeneous mixing' assumption on the node mobility process, and analyze the network capacity in the more realistic case in which nodes are heterogeneous, and the motion of a node does not necessarily cover uniformly the entire space. We propose a general framework to characterize the capacity of networks with arbitrary mobility patterns, considering both the case of finite number of nodes (also with the support of experimental traces), as well as asymptotic results when the number of nodes grows to infinity.

We provide a general framework for the analysis of the capacity scaling properties in mobile ad-hoc networks with heterogeneous nodes and spatial inhomogeneities. Existing analytical studies strongly rely on the assumption that nodes are identical and uniformly visit the entire network space. Experimental data, however, have shown that the mobility pattern of individual nodes is typically restricted over the area, while the overall node density is often largely inhomogeneous, due to prevailing clustering behavior resulting from hot-spots. Such ubiquitous features of realistic mobility processes demand to reconsider the scaling laws for the per-user throughput achievable by the store-carry-forward communication paradigm which provides the foundation of many promising applications of delay tolerant networking. We show how the analysis of the asymptotic capacity of dense mobile ad-hoc networks can be transformed, under mild assumptions, into a Maximum Concurrent Flow (MCF) problem over anassociated Generalized Random Geometric Graph (GRGG). Our methodology allows to identify the scaling laws for a general class of mobile wireless networks, and to precisely determine under which conditions the mobility of nodes can indeed be exploited to increase the per-node throughput. At last we propose a simple, asymptotically optimal, scheduling and routing scheme that achieves the maximum transport capacity of the network.

Most of the current communication networks, including the Internet, are packet switched networks. One of the main reasons behind the success of packet switched networks is the possibility of performance gain due to multiplexing of network bandwidth. The multiplexing gain crucially depends on the size of the buffers available at the nodes of the network to store packets at the congested links. However, most of the previous work assumes the availability of infinite buffer-size. In this paper, we study the effect of finite buffer-size on the performance of networks of interacting queues. In particular, we study the throughput of flow-controlled loss-less networks with finite buffers. The main result of this paper is the characterization of a dynamic scheduling policy that achieves the maximal throughput with a minimal finite buffer at the internal nodes of the network under memory-less (e.g., Bernoulli IID) exogenous arrival process. However, this ideal performance policy is rather complex and, hence, difficult to implement. This leads us to the design of a simpler and possibly implementable policy. We obtain a natural trade-off between throughput and buffer-size for such implementable policy. Finally, we apply our results to packet switches with buffered crossbar architecture

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.

Input queued (IQ) switches exploiting buffered cross- bars (CICQ switches) are widely considered very promising archi- tectures that outperform IQ switches with bufferless switching fab- rics both in terms of architectural scalability and performance. In- deed the problem of scheduling packets for transfer through the switching fabric is significantly simplified by the presence of in- ternal buffers in the crossbar, which makes possible the adoption of efficient, simple and fully distributed scheduling algorithms. This paper studies the throughput performance of CICQ switches sup- porting multicast traffic, showing that, similarly to IQ architec- tures, also CICQ switches with arbitrarily large number of ports may suffer of significant throughput degradation under patho- logical multicast traffic patterns. Despite the asymptotic nature of these results, the authors believe that they can contribute to a deeper understanding of the behavior of CICQ architectures sup- porting multicast traffic. Index Terms—Buffered crossbars, multicast, packet switching, scheduling.

This paper presents an application of basic concepts of statistical physics to devise an approximate model describing the dynamics of large peer-to-peer networks, based on fluid-diffusive equations. The model we propose is quite general and highly modular, and allows to represent several effects related to resources distribution among peers, user behavior, resource localization algorithms and dynamic structure of the overlay topology. Since the complexity of the model is largely independent of the system size, it provides a viable alternative to Montecarlo approaches for the analysis of very large P2P systems.

The advent of packet networks has motivated many researchers to study the performance of networks of queues in the last decade or two. However, most of the previous work assumes the availability of infinite queue-size. Instead, in this paper, we study the maximal achievable throughput in a flow-controlled lossless network with finite-queue size. In such networks, throughput depends on the packet scheduling policy utilized. As the main of this paper, we obtain a dynamic scheduling policy that achieves the maximal throughput (equal to the maximal throughput in the presence of infinite queue-size) with a minimal finite queue-size at the internal nodes of the network. Though the performance of the policy is ideal, it is quite complex and hence difficult to implement. This leads us to a design of simpler and possibly implementable policy. We obtain a natural trade-off between throughput and queue-size for this policy. We apply our results to the packet switches with buffered crossbar architecture. We propose a simple, implementable, distributed scheduling policy which provides high throughput in the presence of minimal internal buffer. We also obtain a natural trade-off between throughput, internal speedup and buffer-size providing a switch designer with a gamut of designs. To the best of authors' knowledge, this is one of the first attempts to study the throughput for general networks with finite queue-size. We believe that our methods are general and can be useful in other contexts.

In this paper we propose a new fluid model approach in which a different description of the dynamics of traffic sources is adopted, exploiting partial differential equations. This new description of the source dynamics allows the natural representation of short-lived as well as long-lived TCP connections, with no sacrifice in the scalability of the model. In addition, the use of partial differential equations permits the description of distributions, instead of averages, thus providing better accuracy in the results. The comparison between the performance estimates obtained with fluid models and with ns-2 simulations proves the accuracy of the proposed modeling approach.

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.

Fluid models of IP networks have been recently proposed as a way to break the scalability barrier of traditional discrete state-space models, both simulative (e.g., ns-2) and analytical (e.g., queues and Markov chains). Fluid models adopt an abstract deterministic description of the average network dynamics through a set of ordinary differential equations that are then solved numerically, obtaining estimates of the time-dependent network behavior. However, an important limit of the fluid model approaches presented so far in the literature is their unnatural representation of scenarios comprising the short-lived TCP flows that dominate in today's Internet. In this paper we propose a new fluid model approach in which a different description of the dynamics of traffic sources is adopted, exploiting partial differential equations. This new description of the source dynamics allows the natural representation of short-lived as well as long-lived TCP connections, with little sacrifice in the scalability of the model. In addition, the use of partial differential equations permits the description of distributions, instead of averages, thus providing better accuracy in the results. The comparison between the performance estimates obtained with fluid models and with ns simulations proves the accuracy of the proposed modeling approach.

Although instability in packet networks has been traditionally associated with overload conditions (because queueing network models show that, in simple configurations, only overload generates instability), some results showing instability in underloaded packet networks have appeared in the recent literature. In M. Ajmone Marsan, et al. (2003) we studied, with fluid models and with adversarial queueing theory, possible underload instabilities due to complex scheduling algorithms that closely resemble quality of service (QoS) schedulers considered today for packet networks, when sources are non-adaptive. In this paper we extend the study of the underload instabilities to packet networks carrying the traffic generated by elastic (rate-adaptive) sources. In particular, we consider additive-increase, multiplicative-decrease (AIMD) sources, and we show this type of adaptivity is not sufficient to mitigate the phenomena leading to underload instabilities and to reduced network throughput.

A significant research effort has been devoted in recent years to the design of simple and efficient scheduling policies for input queued (IQ) and combined input output queued (CIOQ) packet switches. As a result, a number of switch control algorithms have been proposed. Among these, scheduling policies based on maximum weight matching (MWM) were identified as optimal, in the sense that they were proved to achieve 100% throughput under any admissible arrival process satisfying the strong law of large number. On the contrary, it has been recently shown that the usual MWM policies fail to guarantee 100% throughput in networks of interconnected IQ/CIOQ switches. Hence, new policies suited for networks of interconnected switches were proposed and proved to achieve 100% throughput. All of these new policies require coordination and cooperation among different switches. In this paper we address the open problem of the existence of local scheduling policies that guarantee 100% throughput in a network of IQ/CIOQ switches, providing a positive answer to such question. The only assumptions on the input traffic are that it satisfies the strong law of large numbers and that it does not oversubscribe any link in the network.

No abstract available.

The aggregate bandwidth of a switch is its port count multiplied by its operating line rate. We consider switches with high-aggregate bandwidths; for example, a 30-port switch operating at 40 Gb/s or a 1000-port switch operating at 1 Gb/s. Designing high-performance schedulers for such switches with input queues is a challenging problem for the following reasons: (1) high performance requires finding good matchings; (2) good matchings take time to find; and (3) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers for high-aggregate bandwidth switches: (1) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time and (2) observing arriving packets will convey useful information about the state of the switch. The above features are exploited using hardware parallelism and randomization to yield three scheduling algorithms - APSARA, LAURA, and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite close to that of the maximum weight matching, even when the traffic is correlated. We also consider the stability property of these algorithms under generic admissible traffic using the fluid-model technique. The main contribution of this paper is a suite of simple to implement, high-performance scheduling algorithms for input-queued switches. We exploit a novel operation, called MERGE, which combines the edges of two matchings to produce a heavier match, and study of the properties of this operation via simulations and theory. The stability proof of the randomized algorithms we present involves a derandomization procedure and uses methods which may have wider applicability.

A significant research effort has been devoted to the design of simple and efficient scheduling policies for input queued (IQ) and combined input-output queued (CIOQ) packet switches. As a result, a number of switch control algorithms have been proposed. Among these, scheduling policies based on maximum weight matching (MWM) were identified as optimal, in the sense that they were proved to achieve 100% throughput under any admissible arrival process satisfying the strong law of large number. On the contrary, it has been shown that the usual MWM policies fail to guarantee 100% throughput in networks of interconnected IQ/CIOQ switches. Hence, new policies suited for networks of interconnected switches were proposed and proved to achieve 100% throughput. All of these new policies require coordination and cooperation among different switches. We identify scheduling policies that require no coordination among switches (and are, thus, said to be local), and that guarantee 100% throughput in a network of IQ/CIOQ switches. The only assumptions on the input traffic pattern are that it is stationary, satisfies the strong law of large numbers and does not oversubscribe any link in the network.

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 speedup of a switch is the factor by which the switch, and hence the memory used in the switch, runs faster compared to the line rate. In high-speed switches, line rates are already touching the limits at which memory can operate. It is very important for a switch to run at as low a speedup as possible. For an input queued (IQ) switch at speedup 1, 100% throughput can be achieved for any admissible traffic (McKeown, N. et al., 1999; Dai, J. and Prabhakar, B., 2000). This gives finite average delays but does not guarantee control on packet delays. S.T. Chuang et al. (see IEEE J. Selected Areas of Commun., vol.17, no.6, p.1030-9, 1999) show that a combined input output queued (CIOQ) switch can emulate perfectly an output queued (OQ) switch at a speedup of 2 and, thus, control the packet delays. This motivates a study of the possibility of obtaining delay control at speedup less than 2. To guarantee optimal control of delays for a general class of traffic, as shown by Chuang et al., speedup 2 is necessary. Hence, to obtain control of delays at lower speedup, we need to restrict the class of arrival traffic. We study the speedup requirement for a class of admissible traffic, which we denote as (1, nF)-regulated traffic, with parameters n and F. We obtain the necessary speedup for this class of traffic. Further, we present a general class of algorithms working at the necessary speedups and thus providing bounded delays.

High-aggregate bandwidth switches are those whose port count multiplied by the operating line rate is very high; for example, a 30 port switch operating at 40 Gbps or a 1000 port switch operating at 1 Gbps. Designing high-performance schedulers for such switches is challenging for the following reasons: (i) high performance requires finding good matchings; (ii) good matchings take time to find; (iii) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers: (a) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time; (b) observing arriving packets conveys useful information about the state of the switch. These features are exploited using hardware parallelism and randomization to yield three scheduling algorithms for IQ (input-queued) switches - APSARA, LAURA and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite competitive with respect to the maximum weight matching. The stability proof involves a derandomization procedure and uses methods which may have wider applicability.

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.

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.