According to several studies, the power consumption of the Internet accounts for up to 10% of the worldwide energy consumption and is constantly increasing. The global consciousness on this problem has also grown, and several initiatives are being put into place to reduce the power consumption of the ICT sector in general. In this paper, we face the problem of minimizing power consumption for Internet service provider (ISP) networks. In particular, we propose and assess strategies to concentrate network traffic on a minimal subset of network resources. Given a telecommunication infrastructure, our aim is to turn off network nodes and links while still guaranteeing full connectivity and maximum link utilization constraints. We first derive a simple and complete formulation, which results into an NP-hard problem that can be solved only for trivial cases. We then derive more complex formulations that can scale up to middle-sized networks. Finally, we provide efficient heuristics that can be used for large networks. We test the effectiveness of our algorithms on both real and synthetic topologies, considering the daily fluctuations of Internet traffic and different classes of users. Results show that the power savings can be significant, e.g., larger than 35%.

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.

This paper discusses merits and drawbacks of the Optical Burst Switching (OBS) paradigm, which received so much attention by the academic research community. Since the topic is hot, and given the several flavors of OBS available in the literature, we first define what we mean by OBS. Then, we carefully design a reference scenario and a set of evaluation experiments that can be used to obtain quantitative answers to interesting questions in a repeatable way. Within this framework, we motivate our skepticism towards two frequent assertions about the OBS paradigm: its ability to (i) exploit the network bandwidth more efficiently than Optical Circuit Switching (OCS) alternatives, and (ii) to efficiently solve contentions without optical buffers.

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.

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.

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.

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.

According to several studies, the power consumption of the Internet accounts for up to 10% of the worldwide energy consumption, and several initiatives are being put into place to reduce the power consumption of the ICT sector in general. To this goal, we propose a novel approach to switch off network nodes and links while still guaranteeing full connectivity and maximum link utilization. After showing that the problem falls in the class of capacitated multi-commodity flow problems, and therefore it is NP-complete, we propose some heuristic algorithms to solve it. Simulation results in a realistic scenario show that it is possible to reduce the number of links and nodes currently used by up to 30% and 50% respectively during off-peak hours, while offering the same service quality.

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.

The design of fabrics for Terabit packet switches and routers needs to consider the limitations imposed by the electronic technology; in particular, more and more attention has to be paid to information density and to power consumption and dissipation, as well as to power supply and footprint requirements. These issues make more difficult to package a packet switch in one single rack of equipment; thus, optical links start being used to interconnect the line cards with the switching fabric. In this paper, we consider optical interconnection architectures that exploit wavelength agility at line cards to control switching decisions. The actual feasibility and physical layer scalability of this approach is analyzed by considering different optical fabric alternatives to interconnect the line cards. The main contribution of the paper is the characterization of these optical fabrics in terms of their power budget, and the analysis of the port count and of the aggregate bandwidth offered by these architectures to build Terabit packet switches.

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.

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.

In this paper we consider packet networks loaded by admissible traffic patterns, i.e. by traffic patterns that, if optimally routed, do not overload network resources. In these conditions, we study the combined behavior of distributed dynamic routing and scheduling algorithms based upon link state information, with no knowledge of the average traffic pattern, and we prove that simple schemes can achieve the same network throughput as optimal centralized routing and scheduling algorithms with complete information on the traffic pattern. Our study is based on a flow-level abstract model of the network, and considers elastic traffic, i.e., we assume that flows can adapt their transmission rates to network conditions. As a result, our model captures some of the main features of Internet traffic and of quality-of-service routing approaches being currently proposed for IP networks. We show that efficient dynamic routing and scheduling algorithms can be implemented in a distributed way, and we prove that maximum throughput is achieved also in case of temporary mismatches between the actual link metrics and those used by the routing algorithm. This is a particularly relevant aspect, since any distributed implementation of a routing algorithm requires a periodic exchange of link state information among nodes, and this implies delays, and thus time periods in which the actual link state is not known.

In this correspondence, we discuss the stability of scheduling algorithms for input-queueing (IQ) and combined input/output queueing (CIOQ) packet switches. First, we show that a wide class of IQ schedulers operating on multiple traffic classes can achieve 100% throughput. Then, we address the problem of the maximum throughput achievable in a network of interconnected IQ switches and CIOQ switches loaded by multiclass traffic, and we devise some simple scheduling policies that guarantee 100% throughput. Both the Lyapunov function methodology and the fluid modeling approach are used to obtain our results.

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.

This paper presents Ring Optical Network (RingO), a wavelength-division-multiplexing (WDM), ring-based, optical packet network suitable for a high-capacity metro environment. We present three alternative architectural designs and elaborate on the effectiveness of optic with respect to electronic technologies, trying to identify an optimal mix. We present the design and prototyping of a simple but efficient access control protocol, based upon the equivalence of the proposed network architecture with input-buffering packet switches. We discuss the problem of node allocation to WDM channels, which can be viewed as a particular optical network design problem. We, finally, briefly illustrate the fault protection properties of the RingO architecture. The main contribution of this paper is the identification and experimental validation of an innovative optical network architecture, which is feasible and cost effective with technologies available today, and can be a valid alternative to more consolidated solutions in metro applications.

Instability in packet-switching networks is normally associated with overload conditions, since queueing network models show that, in simple configurations, only overload generates instability. However, some results showing that instability can happen also in underloaded queueing networks began to appear about a decade ago. Underload instabilities can be produced by: 1) customer routes that visit the same queues several times; 2) variations of the customer service times at the different queues; and 3) complex scheduling algorithms. We study, using fluid models and adversarial queueing theory, possible underload instabilities due to flow schedulers in packet networks, focusing on output queued switches with strict priority (SP) schedulers and Generalized Processor Sharing (GPS) schedulers. The considered scenarios always refer to acyclic packet routes and consider customer service times that vary only according to channel capacities, thus resembling the approaches being currently considered to provide QoS in the Internet. Our (in)stability results are rather surprising: SP schedulers appear to be more robust than GPS schedulers whenever exact information on the effective average packet flow rates is not available.

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.

Instability in packet-switching networks is normally associated with overload conditions, since queueing network models show that, in simple configurations, only overload generates instability. However, some results showing that instability can happen also in underloaded queueing networks appeared in the recent literature. Underload instabilities can be produced by complex scheduling algorithms, that bear significant resemblance to the Quality of Service (QoS) schedulers considered today for packet networks. In this paper, we study with fluid models and with adversarial queueing theory possible underload instabilities due to strict-priority schedulers and to Generalized Processor Sharing (GPS) schedulers.

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.

In this article, we develop a general methodology, mainly based upon Lyapunov functions, to derive bounds on average delays, and on averages and variances of queue lengths in complex systems of queues. We apply this methodology to cell-based switches and routers, considering first output-queued (OQ) architectures, in order to provide a simple example of our methodology, and then both input-queued (IQ), and combined input/output queued (CIOQ) architectures. These latter switching architectures require a scheduling algorithm to select at each slot a subset of input-buffered cells that can be transferred toward output ports. Although the stability properties (i.e., the limit throughput) of IQ and CIOQ cell-based switches were already studied for several classes of scheduling algorithms, very few analytical results concerning cell delays or queue lengths are available in the technical literature. We concentrate on Maximum Weight Matching (MWM) and Maximal Size Matching (mSM) scheduling algorithms; while the former was proved to maximize throughput, the latter allows simpler implementation. The derived bounds are shown to be rather tight when compared to simulation results.

In this paper, promising technologies and a network architecture are presented for future optical packet switched networks. The overall network concept is presented and the major choices are highlighted and compared with alternative solutions. Both long and shorter term approaches are considered, as well as both the wide-area network and multiple-area networks parts of the network. The results presented in this paper were developed in the frame of the research project DAVID (Data And Voice Integration over DWDM) project, funded by the European Commission through the IST-framework.

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 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.

Many studies provide an extended investigation of the maximum throughput achievable in input-queueing (IQ) or combined-input-and-output-queueing (CIOQ) packet switches. Some scheduling policies, among which are maximum weight matching algorithms, were identified as optimal, in the sense that they were proved to achieve 100% throughput under any admissible single-class traffic pattern. Most of the results in the literature, however, consider just one switch in isolation, operating on packets belonging to a single traffic class. In this paper we first generalize known results, showing that a wide class of IQ schedulers operating on multiple traffic classes can achieve 100% throughput. In addition, we address the problem of the maximum throughput achievable in a network of interconnected IQ switches loaded by multiclass traffic, and we devise some simple scheduling policies that guarantee 100% throughput when switches are interconnected in a network. Both the Lyapunov function methodology and the fluid models approach are used to obtain our results.

Wavelength routed optical networks allow to design a logical topology, comprising lightpaths and routers, which is overlayed on the physical topology, comprising optical fibers and optical cross-connects, by solving a routing and wavelength assignment (RWA) problem. In this paper we extend the concept of lightpath to the one of super-lightpath, which uses a simple bit level time division multiplexing that can be directly implemented in the optical domain, to split the wavelength bandwidth among more than one traffic flow. This allows to design logical topologies with an increased number of logical links, thus reducing the average distance among nodes, i.e., the number of electro-optic and opto-electronic conversions, and the traffic congestion on logical links. At the same time, this reduces the number of wavelengths required to solve the RWA problem. Being the super-lightpath RWA problem computationally intractable, we propose two heuristics which show that the number of wavelengths required to overlay the same logical topology on the same physical topology is reduced by more that 65% using super-lightpaths.

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.

We develop a general methodology, mainly based upon Lyapunov functions, to derive bounds on average delays, and on queue size averages and variances of complex systems of queues. We then apply this methodology to input-buffered, cell-based switch and router architectures. These architectures require a scheduling algorithm to select at each slot a subset of input-buffered cells which can be transferred towards output ports. Although the stability properties (i.e., the limit throughput) of input-buffered, cell-based switches was already studied for several classes of scheduling algorithms, no analytical results concerning cell delays or queue sizes are yet available in the technical literature. We concentrate on purely input-buffered switches that adopt a maximum weight matching scheduling algorithm, that was proved to be the scheduling algorithm providing the best performance. The derived bounds proved to be rather tight, when compared to simulation results.

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 study the bidirectional shufflenet topology, which is obtained from the well-known (unidirectional) shufflenet by considering bidirectional links. More specifically, we define a shortest path routing algorithm, and derive the diameter and the average distance of the topology. The bidirectional shufflenet is then compared, in terms of average distance, with other variations of the perfect shuffle. Bidirectional links are very common in real networks. Possible applications of bidirectional shufflenets are wormhole routing electronic networks with back-pressure flow control, and wavelength routing optical networks. The former class of networks is considered, when virtual channels are used to prevent deadlocks. We show that four virtual channels are sufficient to avoid deadlocks in the bidirectional shufflenet, regardless of the number of nodes in the topology.

We consider cell-based switch and router architectures whose internal switching matrix does not provide enough speed to avoid input buffering. These architectures require a scheduling algorithm to select at each slot a subset of input buffered cells which can be transferred toward output ports. We propose several classes of scheduling algorithms whose stability properties are studied using analytical techniques mainly based upon Lyapunov functions. Original stability conditions are also derived for scheduling algorithms that are being used today in high-performance switch and router architectures.

We consider cell-based switch architectures in which the speedup of the internal switching fabric is not large enough to avoid input buffering. These architectures require a scheduling algorithm to select at each slot a subset of input buffered cells which can be transferred towards output ports. The stability properties of maximal size matching (MSM) scheduling algorithms are studied in the paper, using analytical techniques primarily based upon Lyapunov functions. The main result of the paper is the proof that, for a wide class of MSM scheduling algorithms, stability is guaranteed by an internal switch speedup equal to two.

We consider cell-based switch architectures, whose internal switching matrix does not provide enough speed to avoid input buffering. These architectures require a scheduling algorithm to select at each slot a subset of input buffered cells which can be transferred towards output ports. The stability properties of several classes of scheduling algorithms are studied in the paper, using analytical techniques mainly based upon Lyapunov functions. Original stability conditions are derived for some scheduling algorithms that are being used today in high-performance switch architectures.

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.

We address the problem of providing transparent, reliable, and efficient network-level multicasting in wormhole LANs. We describe some alternatives for achieving deadlock-free multicasting using fast buffer reservation techniques at the host interface level. Tradeoffs involving complexity and performance of various solutions are discussed, and are illustrated using simulation results. Our results show that in most cases the straightforward approach of sending multiple unicast copies of the multicast message at the originator host turns out to be the most simple and effective approach.

In this paper we study the bidirectional shufflenet topology, which is obtained from the well-known (unidirectional) shufflenet by considering bidirectional links. More specifically, we define a shortest-path routing algorithm, and derive the diameter and the average distance of the topology. The bidirectional shufflenet is then compared, in terms of average distance, with other variations of the perfect shuffle.

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.

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.

In order to minimize latency in high-speed interconnection networks, the wormhole routing technique can be employed. With this technique, a switch transmits an incoming message as soon as it receives it, without waiting for the entire message. The problem then is that a message stretches over several links and locks network resources, thus making a contention situation possible. Two principal congestion control mechanisms cast be considered, backpressure flow control and deflection routing. The performance of these mechanisms depends both on the traffic characteristics and on the network topology. In order to compare them, we study analytically the behavior of a wormhole routing network model with random input traffic under both policies. We estimate the probability of collision between messages and express the average message transit delay as a function of the offered load. Simulation provides a good confirmation for the analytical results. This study gives us an understanding of the behavior of the system under different resource management policies.

This paper presents an approximate analytical model for the evaluation of throughput and access delays in high-speed all-optical networks with slotted multi-channel ring topology, where each channel is shared in statistical time division by all nodes transmitting to one destination using a collision- and contention-free access protocol based on a channel inspection capability. Nodes are assumed to have only one queue to store packets for all destinations; two configurations are considered: the single buffer queue and the infinite buffer queue. Simulation results are used to assess the accuracy of the approximate model.

Wormhole routing networks have become increasingly popular for low latency, high-speed interconnection of supercomputer and workstation clusters. An example is the Supercomputer SuperNet (SSN) at UCLA, which interconnects supercomputers across campus and metropolitan area distances. The SSN employs a two-level network architecture in which an optical backbone network interconnects several high-speed, wormhole-routing local area networks (Myrinets). The SSN applications such as scientific visualization and rendering require that the network support reliable delivery of traffic characterized by quality of service (QoS) parameters. Motivated by this requirement, we investigate QoS support in Myrinet-like high-speed, wormhole routing networks. Since native Myrinet protocols do not provide QoS support, we explore several novel strategies including (a) the use of a separate subnet for carrying such traffic (along with source pacing), (b) the overlay of a virtual synchronous system on the asynchronous network, and (c) the introduction of virtual channels. We discuss the tradeoffs among the different options and evaluate them via selected simulation experiments.

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.

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.>

Generalized stochastic Petri nets (GSPNs) are used to study the performances of several dynamic polling orders in symmetric multiserver multiqueue systems with one-buffer queues and Markovian interarrival, service, and walk times. Exact numerical results are obtained by means of Great-SPN, a software tool for the analysis of GSPNs, and are presented as curves of the average customer delay and waiting time. The results quantify the performance differences among the various polling orders, and show that the usual cyclic order can be the most effective, if the possibility of shorter walk times in the cyclic cases is adequately taken into account.>

Most of the medium-access control (MAC) sublayer protocols recently proposed for application in very high-speed local and metropolitan area networks (LANs and MANs) are based on a slotted transmission scheme. Slotting guarantees very good throughput efficiencies, but further gains are possible if slots can be freed after reaching their destination, thus being available for repeated use as they propagate in the network. The authors describe a simulation-based quantitative analysis of the performance gains obtained by introducing slot reuse in distributed-queue dual-bus (DQDB) and cyclic reservation multiaccess (CRMA) MANs. CRMA-II, the latest evolution of CRMA, naturally incorporates slot reuse in the MAC protocol operations and is considered in the study for comparison purposes. In the case of the standard DQDB protocol, some existing proposals are considered. In the case of CRMA, both a previous IBM proposal and a novel approach, leading to very good performances, are studied.>

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.>

The authors consider symmetric multiserver multiqueue systems in the cases of exhaustive and gated service disciplines, and present exact analytical results for the average server cycle and vacation times, as well as approximate closed-form expressions for the average customer waiting time, thus complementing the results obtained by the same authors (1990) for the one-limited service discipline. Arrival processes at each queue are assumed to be Poisson, with the same rate for all queues; service times and walk times are modeled with independent, identically distributed random variables with arbitrary distributions. The two cases in which at most one server or any number of servers can simultaneously attend a queue are considered.>

A study of multiserver multiqueue systems, i.e., queuing systems comprising a set of waiting lines where customers arrive to be served by a pool of servers, is described. Servers cyclically move from one queue to another, and provide service to at most one waiting customer per visit to a queue. Such (1-limited) multiserver polling models are analyzed. Attention is restricted to the case where the movement of the servers from queue to queue takes place in zero time. Two different server utilization policies are considered, and exact results are presented for the average customer waiting time and delay in the simpler case, while simple upper and lower bounds and a very accurate approximation are proposed for the more complex policy. In both cases systems are assumed to be symmetrical, arrivals are taken to be Poisson, and service times exponential.>

Simulation is used to estimate the performance of media access control (MAC) protocols derived from carrier-sense multiple access with collision detection (CSMA/CD), and operating in local area networks comprising several parallel broadcast channels. The influence of possible protocol and system alternatives on the network performance is discussed, based on results of the packet delay average, variance, mean square, coefficient of variation, and histogram, as well as the packet rejection probability due to lack of buffer space. The delay incurred by multipacket messages is estimated, comparing the single channel to the multichannel option. Numerical results indicate that the multichannel option provides reductions in both the packet delay average and variance, even when stations are only able to simultaneously receive from a subset of channels.>

An analysis of polling schemes with multiple servers is presented where the service discipline at each station is assumed to be of the nonexhaustive (limited) type, i.e. no more than one customer can be removed from a station per visit of a server. The times spent by servers to walk from station to station are assumed to be nonzero and are modeled by independent, identically distributed random variables. The arrival processes at each queue are assumed to be Poisson, and serving times are modeled with independent, identically distributed random variables with arbitrary PDF. The case in which at most one server and the case in which any number of servers can simultaneously attend a queue are separately considered. Under the assumption of balanced traffic (equal arrival rates at all stations), several results concerning the cycle analysis and the stability of such schemes are obtained. A simple, explicit expression that gives an approximation for the steady-state average customer waiting time is derived.>

TOPNET is a software package for the simulation of communication networks that is being developed with the aim of exploiting as much as possible the visual aspects of a simulation experiment. The communication network topology and architecture are described by drawings, the system dynamics are represented with a class of timed Petri nets, the simulation experiment is controlled through menus and buttons activated with a mouse, and results are graphically displayed on the screen. With the help of an example, the main characteristics of the user interface and the internal architecture of TOPNET are described.>