To meet the increasing demand for low-latency processing in mobile and IoT devices, edge computing offloads user application tasks to nearby cloudlets (edge servers). Modern applications comprise multiple interdependent tasks with diverse service requirements that must be preloaded on cloudlets. This creates a coupled optimization challenge: jointly deciding task offloading locations and service caching across cloudlets. Inter-task dependencies further complicate the problem by introducing additional communication delays through data transfers and connectivity between cloudlets. Unlike existing studies that rely on a centralized controller with global knowledge, this work introduces a distributed framework for dependency-aware task offloading and service caching. This decentralized design reduces communication overhead and improves scalability. In the proposed framework, each cloudlet observes user task arrivals and network conditions, then applies a deep reinforcement learning (DRL) model enhanced with guided action shaping to determine task-offloading decisions. In parallel, service caching is performed independently by each cloudlet based on its observed service-demand statistics. Simulation results demonstrate that the proposed algorithm outperforms existing benchmarks for dependent task offloading and service caching. Moreover, it exhibits strong adaptability to dynamic environments, enabling more efficient and scalable edge computing.

As 4G networks evolve toward full 5G deployment and beyond 5G (B5G) research begins, new vertical opportunities are being introduced in the context of intelligent transportation, power systems, smart-city urban operation, security services, etc. The diversity of the vertical requirements as well as their particular implementation in citywide locations will make it a real challenge to be able to assess or predict application performance for some of those verticals. In this article, we were motivated by the fact that because of the very nature of verticals and their interaction with a very large-scale telecommunications infrastructure, neither measurements nor small-scale simulations will be sufficient for application performance monitoring and prediction. To enable the assessment and prediction of verticals, so-called Quality of Experience (QoE), we propose a comprehensive framework for very large-scale simulation. The framework is based on the random generation of realistic key performance indicators (KPIs), which vary according to changes produced by the dynamics of urban systems. The probability distributions used for context-dependent random generation are built from samples taken from either “traditional” small-scale simulations or real local measurements. Finally, we present the framework’s key features and current roadblocks for an end-to-end widespread implementation.

When using parallel computing to run large-scale simulations, the parts of the system being simulated in different cores or threads often interact and exchange information, constraining the threads to be synchronized. Simulating wireless networks with mobility, when a user equipment (UE) ceases to be served by one Base Station (BS), to be served by a new one, a synchronization point may be required, if the new BS is being simulated in another thread. In a large-scale distributed wireless network with high mobility, the simulation speed-up obtained from multi-threading could be lost to the overhead burden for synchronizing the threads. We propose a heuristic approach to assign BSs to threads in such a way as to minimize the number of synchronization points. In a time interval of the simulation, accumulated interactions are interpreted as growing graphs. Advancing through the simulation time until the number of disconnected graphs is equal to the number of desired threads, showed to be a good strategy to determine the longest intervals that can be simulated without synchronization points while taking advantage of multi-threading. By means of simulation tests we show decrements of up to 100.0 %, in the number of synchronization points, in comparison to those required for the same simulation times when assigning BSs to threads in a random and balanced way.

Distributed energy resources (DERs) often rely on renewable sources whose random power fluctuations bring about voltage disturbances in distribution networks. Under such circumstances, voltage regulation through centralized control of DERs requires reliable detection and coordination mechanisms. This article proposes a new data-driven approach for event-triggered and coordinated control of DERs based on features of voltage disturbances. Synchrophasor datasets are processed to construct disturbance matrices that quantify spatio-temporal features of voltage disturbances. The estimated features are employed in clustering and control of DERs to suppress incipient events before exceeding a critical time. The proposed approach is tested in the IEEE 123-bus network, which has 15 solar photovoltaic sources with battery energy storage systems. The simulation results validate reliability and efficiency of the proposed method, and confirm that feature extraction combined with coordination of DERs can improve reliable and economic operation of distribution grids with renewables.

Electrical distribution network operators require measurements from phasor measurement units (PMUs), micro-PMUs ( μPMUs), and smart meters (SMs) in order to develop efficient distributed management system (DMS) applications. The high data-rate transmission of those measurements is a burden to the underlying communication system and its feasibility needs to be investigated. In this paper, we propose a method to characterize the traffic generated by a DMS application in a smart city scenario and an analysis of its impact on a realistic LTE infrastructure. Real geographic data on the position of SMs, PMUs, and μPMUs are employed to accurately model this DMS application and its generated traffic. A realistic LTE infrastructure is used to measure the load of DMS traffic at each eNodeB. The impact of synchronous and asynchronous DMS traffic on the LTE access is discussed, and bottlenecks in the LTE communication network are identified.

A new mathematical model and methodology are proposed to evaluate the performance of large-scale RF-mesh networks that use time-slotted ALOHA with frequency hopping spread spectrum. This type of architecture is quite usual in advanced metering infrastructures. An analytic formulation for the delay, based on Markov-modulated modeling of the system, is derived. The formula can be extended to evaluate other important performance metrics. The proposed methodology is applied to a large scale network of several thousands of nodes, and numerical results are reported to show the wide variety of performance evaluations that are enabled. The usefulness of the assessment of the feasibility of different types of applications (e.g., smart-metering and sensor networks) is shown. An analysis of the scalability of this methodology and a comparison with simulation results are also presented.

This article presents a new model and a resolution algorithm, based on Tabu Search, for the assignment of Virtual Machines (VMs) to servers in a data center. We propose a Mixed Integer Programming (MIP) model that optimizes the Quality of Service (QoS) and power consumption of applications, taking into account their communication traffic and dynamic aspects. A hierarchic method and a Tabu Search heuristic that considers the network topology are developed to solve cases with realistic sizes-e.g., a data center with 1600 servers per pod, for up to 128,000 total servers-. The method specifically considers the optimal mapping of the application graph into the data center network. The proposed scheduler is compared with 1) a static method that does not consider workload variations, and 2) the first-fit policy as a sample of methods that do not consider communication traffic among VMs.

We tackle the problem of a network switch enforcing fair bandwidth sharing of the same link among many TCP-like senders. Most of the mechanisms to solve this problem are based on complex scheduling algorithms, whose feasibility becomes very expensive with today's line rate requirements, i.e. 10-100 Gbit/s per port. We propose a new scheme called FDPA in which we do not modify the scheduler, but instead we use an array of rate estimators to dynamically assign traffic flows to an existing strict priority scheduler serving only few queues. FDPA is inspired by recent advances in programmable stateful data planes. We propose a design that uses primitives common in data plane abstractions such as P4 and OpenFlow. We conducted experiments on a physical 10 Gbit/s testbed, we present preliminary results showing that FDPA produces fairness comparable to approaches based on scheduling.

We provide a comprehensive delay and queueing analysis for two baseline medium access control protocols for multi-user cognitive radio networks with homogeneous users and channels and investigate the impact of different network parameters on the system performance. In addition to an accurate Markov chain, which follows the queue status of all users, several lower complexity queueing theory approximations are provided. Accuracy and performance of the proposed analytical approximations are verified with extensive simulations. It is observed that using an Aloha-type access to the control channel, a buffering MAC protocol, where in case of interruption the CR user waits for the primary user to vacate the channel before resuming the transmission, outperforms a switching MAC protocol, where the CR user vacates the channel in case of appearance of primary users and then compete again to gain access to a new channel. The reason is that the delay bottleneck for both protocols is the time required to successfully access the control channel, which occurs more frequently for the switching MAC protocol. It is thus shown that a clustering approach, where users are divided into clusters with a separate control channel per cluster, can significantly improve the performance by reducing the competitions over control channel.

Dynamic spectrum access (DSA) enables secondary networks to find and efficiently exploit spectrum opportunities. A key factor to design a DSA network is the spectrum sensing algorithms for multiple channels with multiple users. Multi-user cooperative channel sensing reduces the sensing time, and thus it increases transmission throughput. However, in a multi-channel system, the problem becomes more complex since the benefits of assigning users to sense channels in parallel must also be considered. A sensing schedule, indicating to each user the channel that it should sense at different sensing moments, must be thus created to optimize system performance. In this paper, we formulate the general sensing scheduling optimization problem and then propose several sensing strategies to schedule the users according to network parameters with homogeneous sensors. Later on, we extend the results to heterogeneous sensors and propose a robust scheduling design when we have traffic and channel uncertainty. We propose three sensing strategies, and, within each one of them, several solutions, striking a balance between throughput performance and computational complexity, are proposed. In addition, we show that a sequential channel sensing strategy is the one to be preferred when the sensing time is small, the number of channels is large, and the number of users is small. For all the other cases, a parallel channel sensing strategy is recommended in terms of throughput performance. We also show that a proposed hybrid sequential-parallel channel sensing strategy achieves the best performance in all scenarios at the cost of extra memory and computation complexity.

In this study, we propose a queueing model to analyse the performance of an opportunistic spectrum access (OSA) system with service interruptions operating over heterogeneous channels in which the service transmission rate and the service interruption rate after the transmission is resumed are generally different than their value prior to the interruption. We first propose Markov chain models to analyse this system under memoryless service time and availability periods. On the basis of simplification assumptions, we also provide an analytical z ‐Transform analysis of the Markov models. The Markov model and approximations are validated with accurate system simulations. We also provide numerical results illustrating the non‐convex relations between the traffic metrics and system parameters and that the proposed models are essential for optimal OSA network planning and operation. We further analyse and discuss the OSA queueing model for general distribution of service time and availability periods. The analytical and simulation results indicate that for usual system parameters, the queue average occupancy is similar for different distributions of service time and availability periods and that the memoryless Markov models can be used to accurately predict the heterogeneous OSA system traffic performance.

Dynamic spectrum access (DSA) for secondary networks improves the spectrum utilization by finding spectrum opportunities and exploiting them efficiently. A key factor to design a DSA network is the spectrum sensing algorithms for multiple channels with multiple users. Multi-user cooperative channel sensing reduces the sensing time, thus increasing the transmission throughput. However, in a multi-channel system, the problem becomes more complex since a sensing schedule, indicating to each user the channel that it must sense at different sensing moments, must be created to optimize system performance. In this paper, we first propose a general sensing strategy to schedule the users according to network parameters. We propose three sensing strategies, and within each one of them several solutions striking a balance between throughput performance, memory usage, and computational complexity are proposed. In addition, we show that the proposed sequential sensing strategy is the one to be preferred when the sensing time is small, the number of channels is large, and the number of users is small. For all the other cases, the parallel sensing strategy is recommended in terms of throughput performance. We also show that a proposed hybrid sequential-parallel sensing strategy achieves the best performance in all scenarios at the cost of extra complexity.

Recent data confirm that the power consumption of the information and communications technologies (ICT) and of the Internet itself can no longer be ignored, considering the increasing pervasiveness and the importance of the sector on productivity and economic growth. Although the traffic load of communication networks varies greatly over time and rarely reaches capacity limits, its energy consumption is almost constant. Based on this observation, energy management strategies are being considered with the goal of minimizing the energy consumption, so that consumption becomes proportional to the traffic load either at the individual-device level or for the whole network. The focus of this paper is to minimize the energy consumption of the network through a management strategy that selectively switches off devices according to the traffic level. We consider a set of traffic scenarios and jointly optimize their energy consumption assuming a per-flow routing. We propose a traffic engineering mathematical programming formulation based on integer linear programming that includes constraints on the changes of the device states and routing paths to limit the impact on quality of service and the signaling overhead. We show a set of numerical results obtained using the energy consumption of real routers and study the impact of the different parameters and constraints on the optimal energy management strategy. We also present heuristic results to compare the optimal operational planning with online energy management operation .

Cognitive radio networks (CRNs) benefit from several features, such as decision-making, spectrum-awareness and reconfigurability, which enable them to perform spectrum migration in order to recover the link when the operating channel becomes occupied. The time spent for channel migration and recovery is a function of the order in which the channels are selected to be sensed. For optimal sensing order, the parameters which have mostly been considered in the literature are the availability and the quality of the channels. Another important parameter is the channel stability, which is the duration that a channel remains continuously available. We extend in this paper a single-slot model to propose novel decision making dynamic programming (DP) models where availability, quality and stability of the channels are taken into account. Considering the need for differentiation in cognitive radio network, we also propose a differentiated dynamic programming model considering different classes of traffic where the sensing order is determined based on an aggregated cost function. Simulation results show the superiority of decision-making based on DP models compared to other common schemes such as myopic, random or average-based.

The ubiquity of cloud applications requires the meticulous design of cloud networks with high quality of service, low costs, and low CO2emissions. This paper presents a planning problem and an extremely efficient tabu search heuristic for optimizing the locations of cloud data centers and software components while simultaneously finding the information routing and network link capacities. The objectives are to optimize the network performance, the CO2emissions, the capital expenditures (CAPEX), and the operational expenditures (OPEX). The problem is modeled using a mixed-integer programming model and solved with both an optimization solver and a tabu search heuristic. A case study of a web search engine is presented to explain and optimize the different aspects, showing how planners can use the model to direct the optimization and find the best solutions. The efficiency of the tabu search algorithm is presented for networks with up to 500 access nodes and 1,000 potential data center locations distributed around the globe.

Given Cloud Computing geographical distribution on multiple regions, the location of data centers, servers and software components and the way information is routed are fundamental issues in system performance. This article presents the Cloud Location and Routing Problem (CLRP), a mathematical problem aiming at solving all those issues in a multi-layer and integrated fashion through a convex integer programming formulation. The results underline the importance of location and routing when offering content to the whole Internet in an efficient way, showing that the budget and the number of data centers opened have a critical impact in overall network performance.

In this paper we introduce a joint planning and energy management framework for Wireless Mesh Networks. In order to show that power management should be integrated at the planning steps to produce an effective energy-efficient network, we present a mathematical model considering a trade-off between capital and energy-related operational expenses. Results demonstrating the impact of different coverage strategies on the energy efficiency are also showed.

We propose a multi-period model to minimize the energy consumption of IP networks while guaranteeing the satisfaction of all the traffic demands. Energy savings are achieved by putting into sleep mode cards and chassis. The multi-period optimization is constrained by inter-period limitations necessary to guarantee the stability of the networks. Both exact and heuristic solutions are proposed. Results show that up to 50% of the energy savings can be achieved for realistic test scenarios in networks operated with flow-based routing protocols (i.e. MPLS).

In this paper, we introduce a queueing approach with server interruptions to analyze the performance of a cognitive radio (CR) link subject to recurrent failures and interruptions. This general model can be used to analyze the traffic metrics as a function of different recovery schemes, channel bandwidth variations and service differentiation. As a first step, we solve in this paper the queueing model without service variation and differentiation. Numerical results to illustrate the analysis accuracy are provided.

We introduce a novel approach that jointly optimizes planning and management for cellular networks, aiming at limiting the energy expenses while guaranteeing QoS and minimizing operators capital expenses. Results from LTE test networks confirm that an effective energy-efficient operation depends on the planning decisions and show that power savings of up to 54% can be obtained with modest increases in initial investments.

In this paper, for the purpose of service differentiation in opportunistic spectrum access (OSA) enabled networks, we take different priority queueing disciplines into account as decision variables in a dynamic optimization model. The objective is to optimize, after the departure of each packet, a weighted utility function of the performance of different classes of cognitive radio traffic by dynamically deciding the priority queueing discipline. A dynamic programming (DP) model, which takes into account the channel availability and channel handover recovery periods of the OSA network, is provided for two classes of traffic to solve this problem. Simulation results are presented.

In this study, the authors provide an analytical framework to assess network-level quality of service (QoS) measures for differentiated, non-saturated traffic in infrastructure-mode 802.11 wireless local area networks using the distributed coordination function access mechanism. The authors build on a general analytical framework that takes into account the medium access control (MAC) access mechanism, the MAC layer packet buffer and the characteristics of the offered load to obtain the probability of a collision with M classes of traffic. The authors then derive analytical expressions for the throughput, the end-to-end packet delay and the packet delay outage probability for differentiated traffic. A case study of voice-over-IP (VoIP) traffic in 802.11b/g networks is used to validate the theoretical framework. The analytical results are in good agreement with the simulation results, showing that although the collision probability for packets transmitted at the access point (AP) is lower than for packets transmitted from the clients, the end-to-end delay in the downlink is much longer than that in the uplink because of the large queuing delay because of the multiplexing of several VoIP connections at the AP. The authors also compare the maximum number of VoIP connections that can be admitted in an 802.11 network while respecting their QoS constraints; these were computed with the proposed theoretical model, an ns-2 simulation model and other schemes previously proposed in the literature. The results indicate that their approach is more accurate over a wide range of parameter values, thus demonstrating the validity, the flexibility and the robustness of the proposed theoretical framework.

Current network planning and design methods use the average delay, packet loss and throughput as metrics to optimize the network cost and performance. New multimedia applications, on the other hand, also have critical jitter requirements that are not taken into account by these methods. Here, we explore the impact on the network performance of adding these jitter constraints. We use a fast jitter calculation model to solve the optimal routing problem for flows subject to jitter or delay constraints. We find that the optimal routing is very different for the two kinds of flows: They should be routed on different paths, the jitter-constrained flows should not be split on multiple paths while the opposite conclusion is true for delay-constrained flows.

Cognitive radios (CR) are an efficient approach to deploy a secondary network in the vacant portions of the spectrum licensed to primary networks. However, when primary users return to a channel used by a CR, the later should vacate the channel and start a restoration process by searching and sensing other channels. The restoration process objective is to find the best channel in the shortest time. We propose in this paper a framework where the intrinsic features of learning and history-awareness of CRs are used to improve the restoration mechanism performance by providing a shorter restoration time or a restored channel with a higher quality. We study both distributed and centralized history-aware restoration schemes and show that it can provide significant improvements for both schemes. However, history-awareness should be carefully used in distributed algorithms since it can be detrimental in certain cases due to the increased users' contention for the best channels.

This paper addresses the problem of energy consumption in the Metropolitan Area Networks that employ Carrier Grade Ethernet. The objective is to minimize the energy consumption of nodes and links, managing the traffic through the Multiple Spanning Tree Protocol (MSTP), where the spanning trees are appropriately chosen from a given set and matched with the traffic demands. We present a modelling framework, a resolution approach and comment on the different features that affect energy performance.

This paper presents an analysis of a compiled database of power consumption and networking functionalities found in datasheets of routers and switches of some major manufacturers. We found very striking differences in consumption between switches and routers of the same nominal capacity. The paper analyzes the significance of such results and sheds some light on the most consuming elements and networking features that could be extremely useful in the re-planning and operation of energy-efficient networks.

The issue of Internet energy consumption and its contribution to global warming has been gaining importance lately. In this paper we present a compilation of facts and data extracted from scattered Internet sources and provide an overview of the basic ideas and most relevant methods suggested to red

In this paper, we evaluate the impact of the wireless channel and physical layer parameters on the performance of VoIP traffic in IEEE 802.11g networks. The wireless channel is modeled using a finite state Markov chain based on an adaptive modulation and coding scheme. The transition probabilities encompass the effects of the time-varying wireless channel, such as the Doppler frequency and the operating SNR, and the physical layer target packet error rate. This model is implemented inthe NS-2 tool and used to analyze the QoS (delay and packetdrop rate) of real-time multimedia traffic in realistic wireless channels. Numerical results showing the physical layer impact on the number of supported VoIP calls in an 802.11g network are presented. We also demonstrate that the admission region in the presence of mixed VoIP and data remains linear, even after considering the complex wireless channel effects.

This paper presents the design and dimensioning optimization of a novel optical network structure, called the Petaweb, having a total capacity of several Pb/s (1015bit/s). Its topology is a superimposition of stars that drastically eases signaling and switching operations. Firstly, we deal with the network model, focusing on the insertion of the time-sharing of the optical channel in network components and in lightpath provisioning. The design problem is jointly a network dimensioning and an assignment problem; we propose for the dimensioning an integer linear programming formulation and a linear resolution algorithm for the assignment. We also propose the use of a quasi-regular topology extracted from the optimized regular topology to reduce costs and improve the network utilization.

This paper deals with the design of a new proposed optical core transport network called the YottaWeb, which offers information delivery at rates thousand of times those of today's Internet. The YottaWeh is based upon the concept of agile cores of a previous named PetaWeb architecture that provides direct optical paths between electronically controlled edge nodes. A fundamental question is how to arrange the edge nodes around the agile cores into a suitable and efficient YottaWeb that could gracefully expand as demand increases, while considering the mean hop value weighted by the demand, as the main performance measure. Based on the proposal to create a multidimensional lattice structure of agile cores, we review previous algorithms proposed for the resultant highly combinatorial problem. Next, we propose a MetaSearch procedure based on Tabu Search and VNS. The performance of this procedure is assessed using a set of networks with random chaotic traffic. Comparative results will be discussed.

This paper deals with the topological design of a yotta-bit-per-second (1yotta=10/sup 24/) multidimensional network. The YottaWeb is a recently proposed architecture based upon agile optical cores that provides fully meshed connectivity with direct optical paths between edge nodes that are electronically controlled. In order to arrange the edge nodes around the agile cores (ACs) into a suitable and efficient YottaWeb, one proposal is to create a multidimensional lattice structure of ACs. The problem of designing such a structure is highly combinatorial. In this paper, we present the problem, that we call nodal arrangement problem, and we propose a meta-search procedure based on Tabu and VNS to solve it. The performance of the algorithm is gauged using a set of randomly generated networks with different distribution of traffic.

In this paper, we present a new methodology for the design of fault-tolerant logical topologies in wavelength-routed optical networks supporting Internet protocol (IP) datagram flows. Our design approach generalizes the "design protection" concepts, and relies on the dynamic capabilities of IP to reroute datagrams when faults occur, thus achieving protection and restoration, and leading to high-performance cost-effective fault-tolerant logical topologies. In this paper, for the first time we consider resilience properties during the logical topology optimization process, thus extending the optimization of the network resilience also to the space of logical topologies. Numerical results clearly show that our approach outperforms previous ones, being able to obtain very effective survivable logical topologies with limited computational complexity.

In this paper we illustrate a new methodology for the design of fault-tolerant logical topologies in wavelength-routed optical networks exploiting wavelength division multiplexing, and supporting both unicast and multicast IP datagram flows. Our approach to protection and restoration generalizes the "design protection" concepts, and relies on the dynamic capabilities of IP routing to re-route IP datagrams when faults occur, thus leading to high-performance cost-effective fault-tolerant logical topologies. Our design methodology for the first time considers the resilience properties or the topology during the logical topology optimization process, thus extending the optimization of the network resilience performance also on the space of the logical topologies. Numerical results clearly show that our approach is able to obtain very good logical topologies with limited complexity.

In this article we propose a model for the topological design problem of multitechnology networks that includes the location of switches and their port configuration, the design of an access network (with single and double access links) and a backbone network. The model specifically takes into account different types of modular switches where each type is characterized by its cost, its capacity in terms of the number of slots, and by its switch fabric capacity. The mutitechnology qualifier stems from the fact that several technologies and rates can be used in the access network. The proposed model is of the integer-programming variety, and in order to find a good solution, we propose a starting heuristic that provides an initial solution and the tabu-search algorithm to improve the solution. Lower bounds are proposed and used to assess the performance of the tabu-based approach. Numerical results for randomly generated problems with up to 500 clients and 50 potential switch sites are presented. The tabu-search algorithm produced solutions that were, on average, within 2.11% of the best lower bound.

We propose a framework for the overall design problem of Internet protocol (IP) networks with performance guarantees that includes the location of IP switches, their configuration with respect to ports, the design of an access network, the design of a core network, the link dimensioning and traffic routing. The model specifically takes into account the failure scenarios of interest to the network planner and that different types of switches can be used. In order to be able to offer performance guarantees (in terms of bandwidth) for transport layer connections, we suppose that the switches support per-flow queuing with weighted fair queuing (WFQ) and longest-queue drop (LQD). Moreover, we consider the routing constraints imposed by the open shortest path first (OSPF) routing mechanism, The proposed model is of the integer programming variety, and in order to find a good solution, we propose a tabu search algorithm. A detailed network design example is presented.

This paper presents a mixed 0–1 linear programming model for the metropolitan area network (MAN) expansion problem. The model includes the location of new switch sites, the update of the configuration of the switches (with respect to port and shelf types), the update of the access network, and the expansion of the backbone (core) network. In addition, we consider that several technologies (e.g., frame relay and asynchronous transfer mode) and rates (e.g., OC-3 and OC-12) may be used in the access network. A multiple-ring topology is chosen for the backbone network since it is sparse, therefore not too expensive, while providing protection against single-link or switch failure. To find a good solution, we propose an initial heuristic that provides a starting solution and a tabu–based heuristic to improve the solution. Finally, we present an illustrative example of a MAN design with its successive expansions, followed by a systematic set of experiments designed to assess the performance of the proposed algorithms. © 2000 John Wiley & Sons, Inc.

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu search algorithm for the STP in graphs. The main feature of this algorithm is a sophisticated strategy for quickly obtaining a very good solution and powerful diversification mechanisms. Computational results on the benchmark problems of the OR-Library, for which optimal solutions are known, indicate that the proposed algorithm outperforms other recent heuristics. © 1999 John Wiley & Sons, Inc. Networks 34: 162–172, 1999

The search history of memory based heuristics like tabu search can be used to design a category of parallel algorithms, called cooperative search. These algorithms execute in parallel several search programs on the same optimization problem instance. At run time, the data gathered in the memory by one sequential search program need not be used only by this program, but it can be recycled and shared with other concurrently executing tabu search programs for the same purpose. In this paper we compare the global behavior of cooperating and non-cooperating tabu search programs. We show that cooperating programs tend to have a search pattern which is less diversified than non-cooperating programs. Our findings also indicate that this second order impact of the sharing of gathered data on the search behaviors of cooperating programs is not related to the optimization properties of the individual tabu programs.

Multicommodity flow (MF) models are well known and have been widely used in the design of packet-switched networks. They have also been used as approximations in the design of circuit-switched networks with reliability constraints. We investigate the usefulness of multicommodity models both as routing models and as an integral part of design models conceived under the failure propagation strategy. First, we compare the performance measures calculated by the models with results produced by a real-time technique. Next, we study the performance of networks dimensioned with flow models and with known adaptive models under failures of transmission facilities when a real-time routing technique is used. Results obtained using realistic data show that the MF models compare favorably with exact dimensioning algorithms when failures are considered.

We consider a model for communications network design that includes the optimal location of switches (of which there are several types) and the design of the access and backbone networks. The model is of the integer programming variety, and in order to find its solution, we propose a greedy heuristic that yields a good starting solution and a more sophisticated heuristic based on tabu search. Finally we present numerical results for problems including as much as 200 user sites and 20 potential switch sites.

Abstract One important issue being addressed in the design of Distributed Computer Networks is how to increase the availability of time‐changing information even in the event of failures. Recently, a technique called “stashing” was proposed. Stashing a file signifies placing a copy of that file in several nodes of the network. In addition, a “predicate” has been defined as a consistency requirement for a particular file copy with respect to the original. We address the problem of minimizing the propagation cost of stashed copies subject to predicate restrictions imposed by the user. In the version of the problem that we tackle, the user may receive a copy with a predicate better than requested. We call this problem the Dynamic Predicate Stashing Copy Problem (DPSCP) and propose a formulation to solve it. Resolution approaches, numerical results, and properties of the problem are also discussed. © 1993 by John Wiley & Sons, Inc.

A reliability measure that takes into account routing and rerouting policies after failures as well as the capacity of the network to satisfy its demand is proposed. The measure, based on the evaluation of the lost call traffic, needs resolution of a routing model for the states of perfect functioning as well as the most probable failure states. A type of routing model useful for network planning is also proposed. The model is closer to reality and easier to implement than the other classical multicommodity formulations. A convex-simplex implementation with a reoptimization feature explicitly adapted to the proposed model is used.>