We present the first spectrum symmetry-free model for the routing and spectrum assignment (RSA) problem. This model allows for the design of more efficient algorithms as it eliminates from consideration an exponential number of equivalent symmetric solutions. By sidestepping symmetry, the RSA solution space is naturally and optimally decomposed into a routing space and a connection permutation space. Building upon this property, we introduce a two-parameter, symmetry-free algorithm that is universal in that it can be used to tackle any RSA variant in a uniform manner. The algorithm is amenable to multi-threaded execution to speed up the search process and the value of the parameters can be adjusted to strike a balance between running time and solution quality. Our evaluation provides insight into the relative benefits of path diversity (which determines the size of the routing space) and connection diversity (which determines the size of the permutation space).

First-Fit (FF) is a well-known and widely deployed algorithm for spectrum assignment (SA), but until our recent study [1], investigations of the algorithm had been experimental in nature and no formal properties of the algorithm with respect to SA were known. In this work, we show that FF is a universal algorithm for the SA problem in the sense that 1) it can be used to construct solutions equivalent to, or better than, any solution obtained by any other algorithm, and 2) it can construct an optimal solution. This universality property applies to both the min-max and min-frag objectives, and to variants of the SA problem with or without guard band constraints. Consequently, the spectrum symmetry-free model of [1] extends to all known SA variants, which therefore reduce to permutation problems. Accordingly, all variants may be solved by similar, intuitive, effective and highly parallelizable algorithms. Our results unlock new algorithmic approaches for optical network design problems that encompass SA as an integral subproblem.

Recursive First Fit (RFF) is an optimal algorithm for the offline spectrum allocation (SA) problem that we developed recently [1]. To the best of our knowledge, RFF is the first algorithm for networks of general topology that is spectrum symmetry-free, i.e., it does not consider any equivalent solutions that are the result of spectrum slot permutations. The algorithm applies the first-fit (FF) heuristic to solve the SA problem, and hence it can be readily implemented. In this work, we present two strategies for parallelizing the execution of RFF, and we evaluate them experimentally using a comprehensive set of metrics. Our experiments indicate that the RFF algorithm explores a vast number of symmetry-free solutions and, for moderate-size networks, it takes mere seconds to yield solutions that are either optimal or very close to the lower bound.

Spectrum allocation (SA) is a fundamental problem in optical network design, yet existing solutions cannot cope effectively with the challenges posed by spectrum symmetry. In this work, we develop parameterized first-fit (PFF), a new heuristic for the SA problem that is not affected by spectrum symmetry and has several desirable properties: it explores a pre-defined subset of the solution space whose size is tailored to the available computational budget; it constructs this subset by sampling from diverse areas of the solution space rather than from the neighborhood of an initial solution; it finds solutions by applying the well-known FF heuristic and thus it can be deployed readily; and it is efficient in finding good quality solutions.

We present a new single-step solution approach for the routing and spectrum allocation (RSA) problem that integrates the first-fit (FF) heuristic with a new routing strategy that we refer to as “parameterized exhaustive routing.” Our approach is to explore the whole routing space for a subset of the traffic requests, e.g., those with the largest demands or those of higher priority or importance. For each of the remaining requests we employ a greedy heuristic to select one of the candidate paths jointly with spectrum allocation. Our solution represents a two-parameter family of algorithms that bridges the gap between an exhaustive search of the routing space and current two-step methodologies for the RSA problem that select paths for each traffic request in isolation. The parameter values may be used to trade off the quality of the final solution and the computational requirements. Our results indicate that exploring the joint routing space of even a few large requests leads to better solutions than purely greedy approaches.

Many network design problems encompass two tasks, routing and resource allocation, that are so intricately intertwined as to contribute significantly to the intractability of such problems. In this paper, we make two contributions to addressing general network design problems of this nature. First, we present a new decomposition method that optimally decouples resource allocation from routing, making it possible to tackle each of these aspects separately. Second, we develop a recursive branch-and-bound algorithm to search the routing space exhaustively, yet in a scalable manner. We apply our method to a well-known intractable problem in optical networks, routing and spectrum assignment (RSA). Our results indicate that the recursive algorithm is able to search efficiently the entire routing space of topologies representative of large-scale wide area networks.

Network function virtualization (NFV), with its potential to facilitate network service provisioning, has drawn growing interest from both academia and industry. One essential challenge is to allocate efficiently the bandwidth and computational resources to the service requests. In an online context, service chain requests may arrive, depart or evolve in an arbitrary fashion, adding more difficulty to the problem. Service chain reconfiguration may help improve the performance by individually rerouting a subset of the service chain requests. In this paper, we propose a new service chain reconfiguration framework to achieve load balancing in an NFV environment under varying levels of support from the underlying infrastructure. We show that our framework can achieve an approximation ratio of O(lnm/ln lnm) with high probability for the service chain request rerouting problem.

Network function virtualization (NFV), with its perceived potential to accelerate service deployment and to introduce flexibility in service provisioning, has drawn a growing interest from industry and academia alike over the past few years. One of the key challenges in realizing NFV is the service chain routing problem, whereby traffic must be routed so as to traverse the various components of a network service that have been mapped onto the underlying network. In this work, we consider the online service chain routing problem. We route the service chain with the goal of jointly minimizing the maximum network congestion and the number of hops from the source to the destination. To this end, we present a simple yet effective online algorithm in which the routing decision is irrevocably made without prior knowledge of future requests. We prove that our algorithm is O(log m)-competitive in terms of congestion minimization, where m is the number of edges of the underlying network topology, and we show that this ratio is asymptotically optimal.

Network function virtualization (NFV), with its perceived potential to accelerate service deployment and to introduce flexibility in service provisioning, has drawn a growing interest from industry and academia alike over the past few years. One of the key challenges in realizing NFV is the service chain routing problem, whereby traffic must be routed so as to traverse the various components of a network service that have been mapped onto the underlying network. In this work, we consider the online service chain routing problem with the goal of minimizing the maximum network congestion. To this end, we present a simple yet effective online algorithm in which the routing decision is irrevocably made without prior knowledge of future requests. We prove that our algorithm is O(log m)-competitive, where m is the number of edges of the underlying network topology, and we show that this ratio is asymptotically optimal.

Efficient allocation of resources is an essential yet challenging problem in a virtual network environment, especially in an online setting whereby virtual network requests may arrive, depart, or be modified in real time. Virtual network reconfiguration may help to improve network performance by remapping a subset of virtual nodes or links to better align the allocation of resources to current network conditions. In this paper, we develop a virtual network reconfiguration scheme that aims to balance the load on the substrate network by dynamically reconfiguring the embedding of both virtual nodes and links. Our solution consists of decomposing the problem into two subproblems: i) virtual node selection, for which we present a linear programming-based fully polynomial time approximation scheme to select the virtual nodes to be migrated, and ii) virtual node remapping, for which we make use of random walk on a Markov chain to select new substrate nodes for the migrated virtual nodes.

Interest in network functions virtualization (NFV) continues to grow due to its perceived benefits to both service providers and users. One of the main challenges in realizing NFV has to do with orchestration of virtual functions deployed in various locations across the network. In this work, we consider the service-concatenation routing problem, where the objective is to construct a path of minimum cost that visits a set of nodes where virtual services are to be applied to the user's traffic in a specific order. We first show that this problem can be modeled as the shortest path tour problem (SPTP) that has been studied in different contexts. We then review and implement a suite of algorithms that use a variety of solution approaches for tackling SPTP, and we also develop a new algorithm. Finally, we carry out a comprehensive experimental evaluation of all algorithms and demonstrate that our algorithm scales well to large problem instances and is suitable for real-time operation as part of the orchestration process in NFV environments.

Elastic optical networks (EONs) are considered as the most promising technology for interconnecting data centers. With the rapid growth of inter- datacenter traffic, power consumption of EONs becomes a significant challenge. In this work, we present a lightpath management algorithm that uses traffic prediction techniques to eliminate unnecessary lightpath termination and re- establishment so as to decrease switching power and enhance the energy efficiency of the network. Our algorithm builds upon the centralized control and capabilities of software defined networking (SDN) technology. Numerical results show that the proposed algorithm is effective in achieving substantial savings in power consumption while maintaining a bandwidth blocking ratio at levels comparable to those of earlier algorithms.

The routing and spectrum assignment (RSA) problem has emerged as the key design and control problem in elastic optical networks. Distance adaptive spectrum allocation exploits the tradeoff between spectrum width and reach to improve resource utilization by tailoring the modulation format to the level of impairments along the path. In this paper, we consider the distance-adaptive RSA (DA-RSA) problem with fixed alternate routing. We first show that the DA-RSA problem in networks of general topology is a special case of a well-studied multiprocessor scheduling problem. We then leverage insights from scheduling theory to (1) present new results regarding the complexity of the DA-RSA problem, and (2) build upon list scheduling concepts to develop a computationally efficient solution approach that is effective in utilizing the available spectrum resources.

In order to find out the tradeoff between recovery time and resource overhead when a link failure occurs, we propose a software-defined based fast restoration scheme for elastic optical datacenter networks, called precomputation based restoration path (P-RP). By extending the controller functionality and OpenFlow protocol in software defined networking (SDN) technology, we establish a novel elastic optical inter-datacenter network architecture which can quickly and accurately converge the network state information with a global view for failure recovery. Based on this architecture, the P-RP performs path computation and bandwidth resource selection for restoration before a failure occurs. The experimental results demonstrate that the proposed scheme can achieve fast recovery with low blocking probability while maintaining high spectrum efficiency. Compared with existing restoration schemes, average recovery time is improved by up to 28%.

Open marketplaces of path services are the next step towards realizing “routing-as-a-service.” Such marketplaces will enable users to select from a set of path services offered by multiple competing network providers so as to construct customized end-to-end paths for their applications. This is analogous to online travel marketplaces that allow users to explore travel options and book their travel. We review the requirements for path planners to assist users in stitching together available path services. We define the problem of finding multi-criteria time-constrained paths in this context, and present a dynamic programming algorithm that constructs Pareto-optimal paths.

Process schedulers are part of the core functionality of an operating system (OS), and have been enhanced over the years to account for multiple cores in the processors and to support multi-threaded applications. In this study, we investigate the impact of the Linux scheduler's load-balancing algorithm on the performance of multi-threaded OpenSIPS (an open source SIP proxy server, SPS) running on a multi-core processor system. Linux uses the “completely fair scheduler” (CFS) scheduling policy and provides parameters specifically tunable in a multi-core environment. We conducted extensive experiments and analyzed the collected data to characterize the performance of SPS as a function of the number of CPU cores, the number of server threads and the call arrival rate. Based on our analysis, we show how to configure the various scheduler parameters as a function of the number of CPU cores to achieve a significant improvement in SPS performance. We further present a capacity planning model as a tool that service providers may use to obtain a first-order approximation of the capacity of their system that yields a good match to experimental results.

Virtual request partitioning is an essential subproblem of two common problems in virtual networks, namely, virtual network embedding (VNE) and virtual machine placement (VMP). In this study, we consider a network-aware variant of the problem where the objective is to partition a virtual request so as to minimize the total amount of inter-cluster traffic. This problem is equivalent to the (k,v)-balanced partitioning problem, an NP-complete problem. To handle the inherent complexity of this problem, we develop a spectral clustering-based partitioning scheme that produces good solutions in a reasonable amount of time. Our solution consists of several components: (a) spectral clustering, (b) a constrained k-means partitioning algorithm that ensures that capacity limits for clusters are met, and for which we present a polynomial-time greedy algorithm, and (c) a greedy refinement algorithm using simulated annealing to further improve the clustering solution. Simulation results indicate that our algorithm outperforms existing partitioning schemes in terms of inter-cluster traffic minimization.

Distance adaptive spectrum allocation exploits the tradeoff between spectrum width and reach to improve resource utilization by tailoring the modulation format to the level of impairments along the path. We first show that the distance-adaptive routing and spectrum assignment (DA-RSA) problem in mesh networks is a special case of a multiprocessor scheduling problem. We then develop a suite of efficient and effective DA-RSA algorithms that build upon list scheduling concepts. Our work explores the tradeoffs involved in DA-RSA algorithm design, and opens up new research directions that may leverage the vast literature in scheduling theory.

Deployment of innovative new networking services requires support by network providers. Since economic motivation plays an important role for network providers, it is critical that a network architecture intrinsically considers economic relationships. We present the design of a protocol that associates access to network services with economic contracts. We show how this protocol can be realized in fundamentally different ways, using out-of-band signaling and in-band signaling, based on two different prototype implementations. We present results that show the effectiveness of the proposed protocol and thus demonstrate a first step toward realizing an economy plane for the Internet.

Multi-threading is a widely used program execution model, where each thread executes independently while sharing some of the process resources. Multi-threaded processes are used for a range of network application servers including web servers, mail servers and SIP proxy servers (SPS) for Voice over IP (VoIP). The process scheduler is a core part of any Operating System and the policy it uses may have a significant impact on the various applications executing on the system. In this work, we investigate the impact of the Linux scheduler on the performance of OpenSIPS, an open source SIP proxy server. The version of Linux used in our study uses a scheduling policy known as “Completely Fair Scheduler” (CFS), and the Linux kernel provides several parameters that may be used to tune the CFS policy. We have collected a large set of experimental data, in a methodical fashion, to characterize the performance of SPS as a function of the number of server threads and the call arrival rate under (1) default CFS setting and (2) with CFS parameters tuned for improved performance. By fine tuning the scheduler parameters, SPS performance is improved in all scenarios, in some cases significantly. To the best of our knowledge, this is the first study that takes into account the scheduler parameters in improving the performance of the SPS. Our results indicate that network operators may increase server capacity without additional capital expenditures, by applying insightful configuration changes to scheduler policy.

Spectrum assignment has emerged as the key design and control problem in elastic optical networks. We have shown that spectrum assignment in networks of general topology is a special case of scheduling multiprocessor tasks on dedicated processors. Based on this insight, we develop and evaluate efficient and effective algorithms for mesh and chain networks that build upon list scheduling concepts.

Hierarchical traffic grooming facilitates the control and management of multigranular WDM networks. We define the hierarchical virtual topology and traffic routing (H-VTTR) problem, the grooming-specific subproblem of traffic grooming, and we present a suite of ILP formulations to solve it. The formulations represent various tradeoffs between solution quality and running time.

The growing number of applications that use the Session Initiation Protocol (SIP) to manage media sessions over IP is placing increasing demands on the SIP proxy servers (SPS) that make up the core of the SIP network. In this work we investigate the performance of OpenSIPS, an open source SPS. We have collected a large set of experimental data to characterize the performance of the SPS under various call arrival rates and inter-arrival time distributions. Based on these measurements, we model the SPS as an M/G/1 queue. A key component of the model is a parameter that captures the cache-miss overhead, i.e., the impact of cache-misses on kernel service times.

We present a simple yet effective enhancement to the operation of the EPON multipoint control protocol (MPCP) that results in significant performance gains across the whole range of traffic loads. The enhancement, inspired by our earlier work in a related but different context, allows the OLT to perform look-ahead scheduling on the upstream channel. The look-ahead operation is fully compatible with the existing standard, and may be implemented via software updates to the OLT without affecting the operation of ONUs. In addition to improvements in delay and throughput performance, look-ahead enhanced MPCP also opens up new opportunities for the design of sophisticated DBA algorithms to support advanced quality of service (QoS) capabilities.

We present a scalable formulation for the traffic grooming problem in WDM ring networks. Specifically, we modify the ILP formulation to replace the constraints related to routing and wavelength assignment (RWA), typically based on a link approach, with a new set of constraints based on the maximal independent set decomposition (MISD) that we recently developed to solve optimally the RWA problem in ring networks. Our experimental study indicates that the new formulation results in an improvement of up to two orders of magnitude in running time. Consequently, it is now possible to solve the traffic grooming problem to optimality for 16-node rings in a few seconds using commodity hardware.

We consider the virtual topology and traffic routing (VTTR) problem, a subproblem of traffic grooming that arises as a fundamental network design problem in optical networks. The objective of VTTR is to determine the minimum number of light-paths so as to satisfy a set of traffic demands, and does not take into account physical layer constraints; a routing and wavelength assignment (RWA) algorithm must reconcile the virtual topology obtained by VTTR with the physical topology. We propose an efficient algorithms that uses a partial LP relaxation technique with lazy constraints to improve substantially the scalability of VTTR, and, hence, of traffic grooming. Our approach delivers a desirable tradeoff between running time and quality of solution.

RWA is a fundamental problem in the design and control of optical networks. We introduce the concept of symmetric RWA solutions and present a new ILP formulation to construct optimally such solutions. The formulation scales to mesh topologies representative of backbone and regional networks. Numerical results demonstrate that the new formulation achieves a decrease of up to two orders of magnitude in running time compared to existing formulations. In particular, optimal solutions for topologies up to 20 nodes can be obtained within minutes using commodity CPUs, and larger networks can be solved in reasonable time. Our approach significantly lowers the barrier to entry in fully exploring the solution space of optical network design and in investigating the sensitivity of design decisions to forecast demands via extensive “what-if” analysis. Such analysis cannot be carried out currently without large investments in computational resources and time.

There has been a great interest in defining a new network architecture that can meet the needs of a future Internet. One of the main challenges in this context is how to realize the many different technical solutions that have developed in recent years in a single coherent architecture. In addition, it is necessary to consider how to ensure economic viability of architecture solutions. In this work, we discuss how to design a network architecture where choices at different layers of the protocol stack are explicitly exposed to users. This approach ensures that innovative technical solutions can be used and rewarded, which is essential to encourage wide deployment of this architecture.

Survivable MPLS technologies are crucial in ensuring reliable communication services. The fast reroute (FRR) mechanism has been standardized to achieve fast local repair of label switched paths (LSPs). We present a hybrid survivability scheme for MPLS networks that combines the well-known p-cycle method with FRR technology. While with pure FRR backup paths are planned individually for each link, the hybrid scheme selects backup paths embedded within a set of p-cycles that may be selected by taking a holistic view of network performance. The hybrid FRR/p-cycle method is fully RFC 4090-compliant, yet allows network operators to leverage a large existing body of p-cycle design techniques.

Network operators offer a variety of tiered services in which users may select only from a small set of tiers which offer progressively higher levels of service. Service bundling, whereby several services are combined together and sold as a single package, is also common in the telecommunications market. We consider the problem of determining optimal tiering structures for service bundles using tools from economics and utility theory. Our work provides insight into the selection and pricing of Internet tiered services.

The design of packet schedulers involves a tradeoff between implementation complexity, on one hand, and delay and fairness guarantees, on the other. In this paper, we present worst-case fair bin sort queuing (WBSQ), a new scheduler that has good worst-case fairness and delay properties, yet has low complexity and is amenable to simple hardware implementation. WBSQ achieves this performance by combining features of BSFQ and WF2Q+. We establish the worst-case fairness and delay properties of WBSQ through both analysis and simulation.

We address the issue of ensuring the integrity and privacy of communications in optical networks. To this end, we extend the traffic grooming concept to encompass flow isolation considerations through a multi-class traffic model. We develop, solve, and compare ILP formulations that ensure that only traffic components within the same class are groomed onto (share) the same wavelength. Our approach provides flow isolation guarantees with an increase in overall cost as a tradeoff.

In the past few years there has been vigorous debate regarding the size of buffers required at core Internet routers. Recent arguments supported by theory and experimentation show that under certain conditions, core router buffer sizes of a few tens of packets suffice for realizing acceptable end-to-end TCP throughputs. This is a significant step toward the realization of optical packet switched (OPS) networks, which are inherently limited in their ability to buffer optical signals. However, prior studies have largely ignored the presence of real-time traffic, which is increasing in importance as a source of revenue for Internet service providers. In this paper, we study the interaction that happens between real-time (open-loop) and TCP (closed-loop) traffic when they multiplex at buffers of very small size (few tens of packets) and make a significant discovery - namely that in a specific range of buffer size, real-time traffic losses increase as buffer size becomes larger. Our contributions pertaining to this anomalous behavior are threefold. First, we exhibit this anomalous loss performance for real-time traffic via extensive simulations using synthetic traffic and real video traces. Second, we develop quantitative models that reveal the dynamics of buffer sharing between real-time and TCP traffic that lead to this behavior. Third, we show how various factors such as the nature of real-time traffic, mixture of long-lived and short-lived TCP flows, and packet sizes impact the severity of the anomaly. Our study is the first to consider interactions between real-time and TCP traffic in very small (potentially all-optical) buffers and informs router manufacturers and network operators of the factors to consider when dimensioning such small buffer sizes for desired performance balance between real-time and TCP traffic.

WDM rings are now capable of supporting more than 100 wavelengths over a single fiber. Conventional link and path formulations for the RWA problem are inefficient due to the inherent symmetry in wavelength assignment and the fact that the problem size increases fast with the number of wavelengths. Although a formulation based on maximal independent sets (MIS) does not have these drawbacks, it suffers from the exponential growth in the number of variables with the increasing network size. We develop a new ILP formulation based on the idea of partitioning the path set and representing the maximal independent sets in the original network using the independent sets calculated in each of these partitions. This formulation trades off the number of variables with the number of constraints and, as a result, achieves a much better scalability in terms of network dimension. The proposed approach is compared with existing formulations on ring networks of various sizes and it is demonstrated that the new formulation achieves more than two orders of magnitude decrease in running time, making it possible to (1) solve optimally large network instances for any number of wavelengths, which cannot be solved with classical formulations, and (2) perform extensive “what-if” analysis to evaluate the sensitivity of the optimal solutions to uncertainties in forecast traffic scenarios.

We consider Internet broadband access as an elastic service whose value varies across segments of the user population. We show that introducing multiple tiers of service can be an effective market segmentation strategy that can lead to an increase of profits for the ISP. We also develop an efficient dynamic programming algorithm for the problem of determining optimally both the service tiers and their prices. Our approach provides new insights into the selection and pricing of Internet tiered services, and our results indicate that exponential tiering structures adopted by ISPs are far from optimal.

Power-awareness in networking attracts more attention as the trends in the energy consumption of the Internet raise growing concerns about the environmental impacts and sustainability of the network expansion. Building energy efficient equipment is definitely an integral part of the solution. However, such a strategy should be complemented with appropriate network protocols and routing methods to achieve maximum performance. In this paper, total power consumption of an optical WDM network is modeled in terms of the power consumed by individual lightpaths. The proposed model is then used to develop an ILP (Integer Linear Programming) formulation of the grooming problem. The exact solution of the formulation on a small network indicates that significant energy savings can be achieved with power efficient grooming.

Advances in the development of large scale distributed computing systems such as Grids and Computing Clouds have intensified the need for developing scheduling algorithms capable of allocating multiple resources simultaneously. In principle, the required resources may be allocated by sequentially scheduling each resource individually. However, such a solution can be computationally expensive, hence inappropriate for time-sensitive applications, and may lead to deadlocks. In this work we present an efficient online algorithm for co-allocating resources that also provides support for advance reservations. The algorithm utilizes data structures specifically designed to organize the temporal availability of resources, and implements co-allocation through efficient range searches that identify all available resources simultaneously. We use simulations driven by real workloads to show that the co-allocation algorithm scales to systems with large numbers of users and resources, and we perform an in-depth comparative analysis against existing batch scheduling mechanisms. Our findings indicate that the online scheduling algorithms may achieve higher utilization while providing smaller delays and better QoS guarantees without adding much complexity.

We consider networks offering tiered services and corresponding price structures, a model that has become prevalent in practice. We develop an economic model for such networks and make contributions in two important areas. First, we formulate the problem of selecting the service tiers and present an approximate yet accurate and efficient solution approach for tackling this nonlinear programming problem. Given the set of (near-) optimal service tiers, we then employ game-theoretic techniques to find an optimal price for each service tier that strikes a balance between the conflicting objectives of users and service provider. This work provides a theoretical framework for reasoning about and pricing Internet tiered services. Our results also indicate that tiering solutions currently adopted by ISPs do not perform well.

Optical packet switches of the foreseeable future are expected to have severely limited buffering capability, since storage of optical signals remains a difficult and expensive operation. Our observations in simulation of TCP and real-time traffic in networks with such small buffers have revealed regions of anomalous performance in which losses for real-time traffic become higher as buffers get larger. The detrimental impact of larger optical buffers is studied in this paper and three new contributions are made. First, we develop a Markov chain model that allows analytical computation of loss. Our model validates observations from simulation, and opens the doors to an analytical understanding of how various factors affect the anomaly. Second, we study the anomaly under realistic traffic mixes containing persistent and non-persistent TCP flows, and show that the traffic mix does not significantly alter the anomaly. Third, we show that larger diversity in packet size between TCP and real-time traffic increases the severity of the anomaly, and is an important consideration when sizing optical switch buffers, particularly since real-time and TCP ACK packets are significantly smaller than the TCP data packets. Our study informs switch manufacturers and network operators of factors to consider when selecting optical buffer sizes in order to achieve desired performance balance between TCP and real-time traffic.

We present a hierarchical algorithm for grooming lightpaths into wavebands, and routing wavebands over a network of multigranular switching nodes. This algorithm focuses on lowering the number of wavelengths W and ports over the network while being conceptually simple, scalable, and consistent with the way networks are operated and controlled in practice. Our experiments indicate that this algorithm easily scales across different waveband and network sizes.

In this paper, we propose an edge reconfigurable optical network as an intermediate step toward fully dynamic optical core network. ERON is an overlay-control network created by installing GMPLS-enabled MEMs optical switches at the edge of a core optical network composed of static lightpaths. We propose a network design algorithm that takes as input the key resource locations dispersed globally and a realistic traffic matrix from end-users and outputs a virtual topology comprised of the minimum required static lightpaths interconnected via ERON switches. This paper describes the key concepts involved in the design of an efficient ERON network combined with routing and reservation algorithms to assure low blocking probabilities. We also describe the management and control architecture and protocols required to provide end-user/application control of the dynamic lightpaths.

The design of the SILO network architecture of fine-grain services was based on three fundamental principles. First, SILO generalizes the concept of layering and decouples layers from services, making it possible to introduce easily new functionality and innovations into the architecture. Second, cross-layer interactions are explicitly supported by extending the definition of a service to include control interfaces that can be tuned externally so as to modify the behavior of the service. The third principle is ldquodesign for change:ldquo the architecture does not dictate the services to be implemented, but provides mechanisms to introduce new services and compose them to perform specific communication tasks. In this paper, we provide an update on the current status of the architecture and the prototype software implementation. We also introduce the concept of ldquosoftware defined opticsrdquo (SDO) to refer to the emerging intelligent and programmable optical layer. We then explain how the SILO architecture may enable the rapid adoption of SDO functionality as well as evolving optical switching models, in particular, optical burst switching (OBS).

We develop an economic model for networks offering tiered services and we formulate the problem of selecting the service tiers from three perspectives: one that considers the users' interests only, one that considers only the service provider's interests, and one that considers both simultaneously, i.e., the interests of society as a whole. We also present dynamic programming algorithms that solve these problems optimally. Our work provides a theoretical framework for reasoning about Internet tiered services, as well as a practical toolset for network providers to develop customized menus of service offerings.

Support for advance reservations of resources plays a key role in Grid resource management as it enables the system to meet user expectations with respect to time requirements and temporal dependence of applications, increases predictability of the system and enables co- allocation of resources. Despite these attractive features, adoption of advance reservations is limited mainly due to the fact that related algorithms are typically complex and fail to scale to large and loaded systems. In this work we consider two aspects of advance reservations. First, we investigate the impact of heterogeneity on Grid resource management when advance reservations are supported. Second, we employ techniques from computational geometry to develop an efficient heterogeneity-aware scheduling algorithm. Our main finding is that Grids may benefit from high levels of resource heterogeneity, independently of the total system capacity. Our results show that our algorithm performs well across several user and system performance and overcome the lack of scalability and adaptability of existing mechanisms.

We propose a new internetworking architecture that represents a departure from current philosophy and practice, as a contribution to the ongoing debate regarding the future Internet. Building upon our experience with the design and prototyping of the just-in-time protocol suite, we outline a framework consisting of (1) building blocks of fine-grain functionality, (2) explicit support for combining elemental blocks to accomplish highly configurable complex communication tasks, and (3) control elements to facilitate (what is currently referred to as) cross-layer interactions. In this position paper, we take a holistic view of network design, allowing applications to work synergistically with the network architecture and physical layers to select the most appropriate functional blocks and tune their behavior so as to meet the application's needs within resource availability constraints. The proposed architecture is flexible and extensible so as to foster innovation and accommodate change, it supports a unified Internet, it allows for the integration of security and management features at any point in (what is now referred to as) the networking stack, and it is positioned to take advantage of hardware-based performance-enhancing techniques.

Many network operators offer some type of tiered service, in which users may select only from a small set of service levels (tiers). In this work, we study the problem of designing a tiered-service network that allocates bandwidth in multiples of a basic bandwidth unit. Such a packet-switched network can enjoy many of the benefits, in terms of control and management, of a TDM network, but without the associated data plane rigidities.

The WF2Q+ scheduler combines all three properties that are important to a fair queueing algorithm: a tight delay bound, a small worst-case fair index value, and a relatively low worst-case complexity ofO(logn) for a link withnflows. We present a new implementation of WF2Q+ in which both the number of packet sorting operations and the computation of the virtual time function are independent of the numbernof flows. Our implementation exploits two widely observed characteristics of the Internet, namely that service providers offer some type of tiered service with a small number of service levels, and that a small number of packet sizes dominate. Our scheduler combines provably good performance with amenability to hardware implementation in high-speed routers.

While research on cross-layer network optimization has been progressing, useful implementations have been lagging because the current Internet architecture does not accommodate cross-layering gracefully. As part of our FIND project, we propose a software architecture for the future Internet that is designed to accommodate such interactions. We present a conceptual overview as well as high level software design and an early prototype implementation, and point out the strengths of our architecture.

Many network operators offer some type of tiered service, in which users may select only from a small set of service levels (tiers). Such a service has the potential to simplify a wide range of core network functions, allowing the providers to scale their operations efficiently. In this work, we provide a theoretical framework for reasoning about and tackling algorithmically the general problem of service tier selection. Drawing upon results from discrete location theory, we formulate the problem as ap-median problem under a new directional distance measure, and we develop efficient algorithms for a number of important variants. Our main finding is that, by appropriately selecting the set of service levels, network providers may realize the benefits of tiered service with only a small sacrifice in network resources.

We consider the problem of providing QoS guarantees to Grid users through advance reservation of resources. Advance reservation mechanisms provide the ability to allocate resources to users based on agreed-upon QoS requirements and increase the predictability of a Grid system, yet incorporating such mechanisms into current Grid environments has proven to be a challenging task due to the resulting resource fragmentation. We use concepts from computational geometry to present a framework for tackling the resource fragmentation, and for formulating a suite of scheduling strategies. We also develop efficient implementations of the scheduling algorithms that scale to large Grids. We conduct a comprehensive performance evaluation study using simulation, and we present numerical results to demonstrate that our strategies perform well across several metrics that reflect both user-and system-specific goals. Our main contribution is a timely, practical, and efficient solution to the problem of scheduling resources in emerging on-demand computing environments.

We consider the problem of supporting absolute QoS guarantees in terms of the end-to-end burst loss in OBS networks. We present a parameterized model for wavelength sharing which provides for isolation among different traffic classes while also making efficient use of wavelength capacity through statistical multiplexing. We develop a heuristic to optimize the policy parameters for a single link of an OBS network. We also develop a methodology for translating the end-to-end QoS requirements into appropriate per-link parameters so as to provide network-wide guarantees. Our approach is easy to implement, it can support a wide variety of traffic classes, and is effective in meeting the QoS requirements and keeping the loss rate of best-effort and overall traffic low

We consider the general problem of optimizing the performance of OBS networks with multiple traffic classes subject to strict (absolute) QoS constraints in terms of the end-to-end burst loss rate of each guaranteed class of traffic. We employ Markov decision process (MDP) theory to obtain optimal wavelength sharing policies for two performance objectives, namely, maximization of weighted network throughput and minimization of the loss rate of best-effort traffic, while meeting the QoS guarantees. The randomized threshold policies we obtain are simple to implement and operate, and make effective use of statistical multiplexing. In particular, the threshold randomization feature enables the policies to allocate bandwidth at arbitrarily fine sub-wavelength granularity, hence making effective use of the available network capacity.

We consider the problem of supporting absolute QoS guarantees in terms of the end-to-end burst loss in OBS networks. We present a parameterized model for wavelength sharing which provides for isolation among different traffic classes while also making efficient use of wavelength capacity through statistical multiplexing. We develop a heuristic to optimize the policy parameters for a single link of an OBS network. We also develop a methodology for translating the end-to-end QoS requirements into appropriate per-link parameters so as to provide network-wide guarantees. Our approach is easy to implement, it can support a wide variety of traffic classes, and is effective in meeting the QoS requirements and keeping the loss rate of best-effort and overall traffic low.

We consider the problem of providing absolute QoS guarantees to multiple classes of users of an OBS network in terms of the end-to-end burst loss. We employ Markov decision process (MDP) theory to develop wavelength sharing policies that maximize throughput while meeting the QoS guarantees. The randomized threshold policies we obtain are simple to implement and operate, and make effective use of statistical multiplexing.

We consider the problem of traffic grooming in WDM path, star, and tree networks. Traffic grooming is a variant of the well-known logical topology design, and is concerned with the development of techniques for combining low speed traffic components onto high speed channels in order to minimize network cost. Our contribution is two-fold. In the first part of the paper we present a wealth of results which settle the complexity of traffic grooming in path and star networks, by proving that a number of variants of the problem are computationally intractable. Since routing and wavelength assignment in these two topologies is trivial, these results demonstrate that traffic grooming is itself an inherently difficult problem. Our results have implications for ring and other more general topologies, which we explore. In the second part we design practical grooming algorithms with provable properties. Specifically, for all three topologies, we obtain a series of lower and upper bounds which are increasingly tighter but have considerably higher computational requirements; the series of upper bounds forms an algorithm for the traffic grooming problem with strong performance guarantees. We also present corresponding heuristics with good performance. Our work is a first step towards a formal and systematic approach to the grooming problem in general topologies that builds upon results and algorithms for more elementary networks

We present a framework for hierarchical traffic grooming in mesh networks with the objective of minimizing the total number of electronic ports. At the first level of hierarchy, we decompose the network into clusters and designate one node in each cluster as the hub for grooming traffic. At the second level, the hubs form another cluster for grooming inter-cluster traffic. We view each (first- or second-level) cluster as a virtual star, and we present an efficient near-optimal algorithm for determining the logical topology of lightpaths to carry the traffic within each cluster. Routing and wavelength assignment is then performed directly on the underlying physical topology. Our approach scales to large network sizes, and facilitates the control and management of multigranular networks. Comparisons to lower bounds indicate that it is also efficient in its use of the network resources of interest, namely, electronic ports and wavelengths.

A fundamental assumption underlying most studies of optical burst switched (OBS) networks is that full wavelength conversion is available throughout the network. In practice, however, economic and technical considerations are likely to dictate a more limited and sparse deployment of wavelength converters in the optical network. Therefore, we expect wavelength assignment policies to be an important component of OBS networks. In this paper, we explain why wavelength selection schemes developed for wavelength routed (circuit-switched) networks are not appropriate for OBS. We then develop a suite of adaptive and nonadaptive policies for OBS switches. We also apply traffic engineering techniques to reduce wavelength contention through traffic isolation. Our performance study indicates that, in the absence of full conversion capabilities, intelligent choices in assigning wavelengths to bursts at the source can have a profound effect on the burst drop probability in an OBS network.

A fundamental assumption underlying most studies of optical burst switched (OBS) networks is that full wavelength conversion is available throughout the network. In practice however, economic and technical considerations are likely to dictate a more limited and sparse deployment of wavelength converters in the optical network. Therefore, we expect wavelength assignment policies to be an important component of OBS networks. In this paper, we explain why wavelength selection schemes developed for wavelength routed networks are not appropriate for OBS. We then develop a suite of adaptive and non-adaptive policies for OBS switches. We also apply traffic engineering techniques to reduce wavelength contention through traffic isolation. Our performance study indicates that, in the absence of full conversion capabilities, intelligent choices in assigning wavelengths to bursts at the source can have a profound effect on the burst drop probability in an OBS network.

This paper studies the important fault management issue with focus on the fast restoration mechanisms for optical burst switched (OBS) networks. In order to reduce the burst losses during the restoration process, effective fast restoration schemes are necessary. This is illustrated via two basic fast restoration schemes, the distributed deflection scheme and the local deflection scheme, compared with the slow global routing update mechanism. A novel priority-based QoS restoration scheme is also proposed to provide differentiated restoration services. Through detailed descriptive analysis and a comprehensive simulation study, these fast restoration schemes demonstrate fast restoration process, low fault management overheads, and excellent burst loss performance. As far as we know, this is the first comprehensive study on the restoration mechanisms for OBS networks.

It has been widely recognized that physical layer impairments, including power losses, must be taken into account when routing optical connections in transparent networks. In this paper we study the problem of constructing light-trees under optical layer power budget constraints, with a focus on algorithms which can guarantee a certain level of quality for the signals received by the destination nodes. We define a new constrained light-tree routing problem by introducing a set of constraints on the source-destination paths to account for the power losses at the optical layer. We investigate a number of variants of this problem, we characterize their complexity, and we develop a suite of corresponding routing algorithms; one of the algorithms is appropriate for networks with sparse light splitting and/or limited splitting fanout. We find that, in order to guarantee an adequate signal quality and to scale to large destination sets, light-trees must be as balanced as possible. Numerical results demonstrate that existing algorithms tend to construct highly unbalanced trees, and are thus expected to perform poorly in an optical network setting. Our algorithms, on the other hand, are designed to construct balanced trees which, in addition to having good performance in terms of signal quality, they also ensure a certain degree of fairness among destination nodes. While we only consider power loss in this work, the algorithms we develop could be appropriately modified to account for other physical layer impairments, such as dispersion.

We consider an edge optical burst switching (OBS) node with or without converters, and with no buffering. The OBS node serves a number of users, each connected to the switch over a fiber link that supports multiple wavelengths. Each wavelength is associated with a 3-state Markovian burst arrival process. The arrival process permits short and long bursts to be modeled. We model the edge OBS node as a closed nonproduct-form queueing network, with multiple heterogeneous classes, and we develop a suite of approximate decomposition algorithms to analyze it. Our approximate algorithms have a good accuracy, and they provide insight into the effect of various system parameters on the performance of the edge OBS node.

No abstract available.

We simplify the periodic tasks scheduling problem by making a trade off between processor load and computational complexity. A set N of periodic tasks, each characterized by its density /spl rho//sub i/, contains n possibly unique values of /spl rho//sub i/. We transform N through a process called quantization, in which each /spl rho/i /spl isin/ N is mapped onto a service level s/sub j/ /spl isin/ L, where |L| = l /spl Lt/ n and /spl rho//sub i/ /spl les/ s/sub j/, (this second condition differentiates this problem from the p-median problem on the real line). We define the periodic task quantization problem with deterministic input (PTQ-D) and present an optimal polynomial time dynamic programming solution. We also introduce the problem PTQ-S (with stochastic input) and present an optimal solution. We examine, in a simulation study, the trade off penalty of excess processor load needed to service the set of quantized tasks over the original set, and find that, through quantization onto as few as 15 or 20 service levels, no more than 5 percent processor load is required above the amount requested. Finally, we demonstrate that the scheduling of a set of periodic tasks is greatly simplified through quantization and we present a fast online algorithm that schedules quantized periodic tasks.

We consider the problem of designing a virtual topology to minimize electronic routing, that is, grooming traffic, in wavelength routed optical rings. The full virtual topology design problem is NP-hard even in the restricted case where the physical topology is a ring, and various heuristics have been proposed in the literature for obtaining good solutions, usually for different classes of problem instances. We present a new framework which can be used to evaluate the performance of heuristics and which requires significantly less computation than evaluating the optimal solution. This framework is based on a general formulation of the virtual topology problem, and it consists of a sequence of bounds, both upper and lower, in which each successive bound is at least as strong as the previous one. The successive bounds take larger amounts of computation to evaluate, and the number of bounds to be evaluated for a given problem instance is only limited by the computational power available. The bounds are based on decomposing the ring into sets of nodes arranged in a path and adopting the locally optimal topology within each set. While we only consider the objective of minimizing electronic routing in this paper, our approach to obtaining the sequence of bounds can be applied to many virtual topology problems on rings. The upper bounds we obtain also provide a useful series of heuristic solutions.

We present an approximate analytical method to compute efficiently the call-blocking probabilities in wavelength-routing networks with multiple classes of both unicast and multicast calls. Our approach involves the following steps. We start with an approximate solution to a linear single-class unicast network which we developed earlier. Next, all classes of calls on a particular route are aggregated to give an equivalent single-class model. We then extend the path decomposition algorithms that we have developed for single-class networks to handle mesh networks with multiple classes of calls. We show how to use these path decomposition algorithms to decompose large networks with multicast paths into smaller subsystems with only linear paths, which, in turn, are solved by the product-form approximation algorithm. We also consider a state-dependent Poisson arrival process for multicast calls which is more accurate in capturing the behavior of these calls.

We study a class of circuit-switched wavelength-routing networks with fixed or alternate routing and with random wavelength allocation. We present an iterative path decomposition algorithm to evaluate accurately and efficiently the blocking performance of such networks with and without wavelength converters. Our iterative algorithm analyzes the original network by decomposing it into single-path subsystems. These subsystems are analyzed in isolation, and the individual results are appropriately combined to obtain a solution for the overall network. To analyze individual subsystems, we first construct an exact Markov process that captures the behavior of a path in terms of wavelength use. We also obtain an approximate Markov process which has a closed-form solution that can be computed efficiently for short paths. We then develop an iterative algorithm to analyze approximately arbitrarily long paths. The path decomposition approach naturally captures the correlation of both link loads and link blocking events. Our algorithm represents a simple and computationally efficient solution to the difficult problem of computing call-blocking probabilities in wavelength-routing networks. We also demonstrate how our analytical techniques can be applied to gain insight into the problem of converter placement in wavelength-routing networks.

We study the issues arising when considering the problem of reconfiguring broadcast optical networks in response to changes in the traffic patterns. Although the ability to dynamically optimize the network under changing traffic conditions has been recognized as one of the key features of multiwavelength optical networks, this is the first in-depth study of the tradeoffs involved in carrying out the reconfiguration process. We first identify the degree of load balancing and the number of retunings as two important, albeit conflicting, objectives in the design of reconfiguration policies. We then formulate the problem as a Markovian decision process and we develop a systematic and flexible framework in which to study reconfiguration policies. We apply results from Markov decision process theory to obtain optimal reconfiguration policies for networks of large size. The advantages of optimal policies over a class of threshold-bused policies are illustrated through numerical results.

We present MTCT, a congestion control scheme for large-scale reliable multicast. Congestion control for reliable multicast is important because of its wide applications in multimedia and collaborative computing, yet nontrivial, because of the potentially large number of receivers involved. Many schemes have been proposed to handle the recovery of lost packets in a scalable manner; but there is little work on the design and implementation of congestion control schemes for reliable multicast. We propose new techniques that can effectively handle instances of congestion occurring simultaneously at various parts of a multicast tree. Our protocol incorporates several novel features: (1) hierarchical congestion status reports that distribute the load of processing feedback from all receivers across the multicast group, (2) the relative time delay (RTD) concept which overcomes the difficulty of estimating round-trip times in tree-based multicast environments, (3) window-based control that prevents the sender from transmitting faster than packets leave the bottleneck link an the multicast path through which the sender's traffic flows, (4) a retransmission window that regulates the flow of repair packets to prevent local recovery from causing congestion, and (5) a selective acknowledgment scheme that prevents independent (i.e., non-congestion-related) packet loss from reducing the sender's transmission rate. We have implemented MTCP both on UDP in SunOS 5.6 and on the simulator ns, and we have conducted extensive Internet experiments and simulation to test the scalability and inter-fairness properties of the protocol. The encouraging results we have obtained support our confidence that TCP-like congestion control for large-scale reliable multicast is within our grasp.

We study a class of circuit-switched wavelength routing networks with and without wavelength converters, and we present the first part of a new analytical framework to accurately and efficiently evaluate the blocking performance of such networks. The model allows non-uniform traffic, it accounts for the correlation among the loads at all links in a path, and it can be used when the location of converters is fixed but arbitrary. We first construct an exact Markov process that captures the behaviour of a path in terms of wavelength use. We also obtain an approximate Markov process which has a closed-form solution that can be efficiently computed for short paths. We then develop an iterative algorithm to analyze approximately arbitrarily long paths. The algorithm decomposes a path into shorter segments which are then studied in isolation using the corresponding approximate Markov process. The individual solutions are appropriately combined to obtain a solution for the original path. Finally, we demonstrate how the analytical techniques can be used to gain insight into the problem of converter placement in wavelength routing networks.

In this paper we study the problem of dynamic load balancing in broadcast WDM networks by retuning a subset of transceivers in response to changes in the overall traffic pattern. Assuming an existing wavelength assignment and some information regarding the new traffic demands, we present two approaches to obtaining a new wavelength assignment such that (a) the new traffic load is balanced across the channels, and (b) the number of transceivers that need to be retuned is minimized. The latter objective is motivated by the fact that tunable transceivers take a non-negligible amount of time to switch between wavelengths during which parts of the network are unavailable for normal operation. Our main contribution is a new approximation algorithm for the load balancing problem that provides for tradeoff selection, using a single parameter, between the two conflicting goals. This algorithm leads to a scalable approach to reconfiguring the network since, in addition to providing guarantees in terms of load balancing, the expected number of retunings scales with the number of channels, not the number of nodes in the network.

We consider broadcast WDM networks operating with schedules that mask the transceiver tuning latency. We develop and analyze a queueing model of the network in order to obtain the queue-length distribution and the packet loss probability at the transmitting and receiving side of the nodes. The analysis is carried out assuming finite buffer sizes, non-uniform destination probabilities and two-state MMBP traffic sources; the latter naturally capture the notion of burstiness and correlation, two important characteristics of traffic in high-speed networks. We present results which establish that the performance of the network is a complex function of a number of system parameters, including the load balancing and scheduling algorithms, the number of available channels, and the buffer capacity. We also show that the behavior of the network in terms of packet loss probability as these parameters are varied cannot be predicted without an accurate analysis. Our work makes it possible to study the interactions among the system parameters, and to predict, explain and fine tune the performance of the network.

We consider the problem of coordinating access to the various channels of a single-hop WDM network. We present HiPeR-l, a new reservation protocol specifically designed to overcome the potential inefficiencies of operating in environments with non-negligible processing, tuning, and propagation delays. HiPeR-l differs from previous reservation protocols in that each control packet makes reservations for all data packets waiting in a node's queues, thus significantly reducing the control overhead. Packets are scheduled for transmission using algorithms that can effectively mask the tuning times. HiPeR-l also uses pipelining to mask the processing times and propagation delays. We use Markov chain theory to obtain a necessary and sufficient condition for the stability of the protocol. The stability condition provides insight into the factors affecting the operation of the protocol, such as the degree of load balancing across the various channels, and the quality of the scheduling algorithms. The analysis is fairly general, as it holds for MMBP-like arrival processes with any number of states, and for non-uniform destinations.

We consider the problem of supporting multipoint communication at the media access control (MAC) layer of broadcast-and-select WDM networks. We first show that bandwidth consumption and channel utilization arise as two conflicting objectives in the design of scheduling algorithms for multicast traffic in this environment. We then present a new technique for the transmission of multicast packets, based on the concept of a virtual receiver, a set of physical receivers which behave identically in terms of tuning. We also show that the number κ of virtual receivers naturally captures the tradeoff between channel utilization and bandwidth consumption. Our approach decouples the problem of determining the virtual receivers from the problem of scheduling packet transmissions, making it possible to employ existing scheduling algorithms that have been shown to successfully hide the effects of tuning latency. Consequently, we focus on the problem of optimally selecting the virtual receivers, and we prove that it is NP-complete. Finally, we present four heuristics of varying degrees of complexity for obtaining virtual receivers that provide a good balance between the two conflicting objectives.

We address the issue of providing efficient mechanisms for multidestination communication over one class of lightwave wavelength division multiplexing (WDM) architectures, namely, single-hop networks with tunability provided only at the receiving side. We distinguish a number of multicast traffic types, we present a number of alternative broadcast/multicast time-division multiple-access (TDMA) schedules for each type, and we develop heuristics to obtain schedules that result in low average packet delay. One of our major contributions is the development of a suite of adaptive multicast protocols which are simple to implement, and have good performance under changing multicast traffic conditions.

We study the problem or constructing multicast trees to meet the quality of service requirements of real-time interactive applications operating in high-speed packet-switched environments. In particular, we assume that multicast communication depends on: (1) bounded delay along the paths from the source to each destination and (2) bounded variation among the delays along these paths. We first establish that the problem of determining such a constrained tree is NP-complete. We then present a heuristic that demonstrates good average case behavior in terms of the maximum interdestination delay variation. The heuristic achieves its best performance under conditions typical of multicast scenarios in high speed networks. We also show that it is possible to dynamically reorganize the initial tree in response to changes in the destination set, in a way that is minimally disruptive to the multicast session.

We consider the problem of scheduling packet transmissions in a broadcast, single-hop wavelength-division multiplexing (WDM) network, with tunability provided only at one end. Our objective is to design schedules of minimum length to satisfy a set of traffic requirements given in the form of a demand matrix. We address a fairly general version of the problem as we allow arbitrary traffic demands and arbitrary transmitter tuning latencies. The contribution of our work is twofold, First we define a special class of schedules which permit an intuitive formulation of the scheduling problem. Based on this formulation we present algorithms which construct schedules of length equal to the lower bound provided that the traffic requirements satisfy certain optimality conditions. We also develop heuristics which, in the general case, give schedules of length equal or very close to the lower bound. Secondly, we identify two distinct regions of network operation. The first region is such that the schedule length is determined by the tuning requirements of transmitters; when the network operates within the second region however, the length of the schedule is determined by the traffic demands, not the tuning latency. The point at which the network switches between the two regions is identified in terms of system parameters such as the number of nodes and channels and the tuning latency. Accordingly, we show that it is possible to appropriately dimension the network to minimize the effects of even large values of the tuning latency.

We study the problem of constructing multicast trees to meet the quality of service requirements of real-time, interactive applications operating in high-speed packet-switched environments. In particular, we assume that multicast communication depends on (a) bounded delay along the paths from the source do each destination, and (b) bounded variation among the delays along these paths. We first establish that the problem of determining such a constrained tree is NP-complete. We then derive heuristics that demonstrate good average case behavior in terms of the maximum inter-destination delay variation of the final tree. We also show how to dynamically reorganize the initial tree in response to changes in the destination set, in a way that is minimally disruptive to the multicast session.

We consider the problem of scheduling packet transmissions in single-hop WDM networks, with tunability provided only at one end. Our objective is to design schedules of minimum length for a given traffic demand matrix. The contribution of our work is twofold. First we define a special class of schedules which permit an intuitive formulation of the scheduling problem. We then present algorithms which construct schedules of length equal to the lower bound provided that certain optimality conditions are satisfied. We also develop heuristics which, in the general case, give schedules of length equal or very close to the lower bound. Secondly, we identify two distinct regions of network operation. In the first region the schedule length is determined by the tuning requirements, while in the second it is determined by the traffic demands. The point at which the network switches between the two regions is identified in terms of the number of nodes and channels, and the tuning latency. Accordingly, we show that it is possible to appropriately dimension the network to offset the effects of even large values of tuning latency.

We consider a generalization of the multiple access problem where it is necessary to identify a subset of the ready users, not all. The problem is motivated by several "response collection" applications that arise in distributed computing and database systems. In these applications, a collector is interested in gathering a set of responses from a number of potential respondents. The collector and respondents communicate over a shared channel. We define three collection objectives and investigate a suite of protocols that can be used to achieve these objectives. The protocols are based on the use of polling, TDMA, and group testing. Using a binomial respondent model we analyze and, where applicable, optimize the performance of the protocols. Our concern is with cost measures that reflect the computational load placed on the system, as well as the delay incurred for achieving a particular objective.>

Considers single-hop lightwave networks with stations interconnected using wave division multiplexing. The stations are equipped with tunable transmitters and/or receivers. A predefined, wavelength-time oriented schedule specifies the slots and the wavelengths on which communication between any two pairs of stations is allowed to take place. The authors define a wide variety of schedules and develop a general framework for analyzing their throughput performance for any number of available wavelengths, any tunability characteristics, and general (potentially nonuniform) traffic patterns. They then consider the optimization of schedules given the traffic requirements and present optimization heuristics that give near-optimal results. They also investigate how the number of available wavelengths (channels) affects the system throughput, and develop techniques to efficiently share the available channels among the network stations. As a result, they obtain systems that are easy to scale while having very good performance.>

The authors address the open issue of providing efficient mechanisms for multi-destination communication over one class of lightwave WDM architectures, namely, single-hop networks. They suggest, analyze, and optimize several alternative approaches for broadcast/multicast. One of their major contributions is the development of a suite of adaptive multicast protocols which have very good performance, are very simple to implement, and are insensitive to propagation delays.>

Single-hop lightwave networks with stations interconnected using wavelength-division multiplexing are considered. The stations are equipped with tunable transmitters and/or receivers. Coordination between the transmitting and receiving stations is achieved by assuming synchronous control and a predefined, frequency-time oriented schedule which specifies the slots and the wavelengths on which communication between any two pairs of stations is allowed to take place. The authors define and analyze, in terms of throughput, all possible types of schedules in the situation where the number of available wavelengths is equal to the number of stations. The results are valid for the general case, i.e., nonuniform traffic. The optimization of schedules, given the traffic requirements, is considered, and optimization heuristics that give near-optimal results are presented.>

A generalization of the multiple access problem is considered where it is necessary to identify a subset of the ready users, not all. The problem is motivated by several response collection applications that arise in distributed computing and database systems. In these applications, a collector is interested in gathering a set of responses from a number of potential respondents. The collector and respondents communicate over a shared channel. Three collection objectives are defined, and a suite of protocols that can be used to achieve these objectives is investigated. The protocols are based on the use of polling, time division multiple access (TDMA) and group testing. Using a binomial respondent model, the performance of the protocols is analyzed and, where possible, optimized. The main concern is with cost measures that reflect the computational load placed on the system, as well as the delay incurred for achieving a particular objective.>