Edge computing is poised to become a cornerstone of the emerging 6G landscape, where an ever-growing class of ultra-low-latency applications must be served close to the user. Despite its promise, real-world deployments remain nascent, with large-scale implementations anticipated by both Communication and Digital Service Providers (CSPs/DSPs) within the following years. Consequently, strategic edge network design is essential not only to maximize performance, but also to avoid redundant investments that can lead to an increased sum of Capital and Operational Expenditures (CAPEX/OPEX). In this work, we address a tri-fold problem: (i) the selection of deployment locations, (ii) the configuration of devices at the chosen location sites, and (iii) the assignment of the projected workload. Our objective is formulated as a weighted combination of the edge infrastructure’s establishment cost, the expected cumulative workload latency and the total expected energy consumption in the operational phase. To capture the spatial and temporal variability of demand, we solve the assignment subproblem over distinct snapshots, each representing a unique workload projection. We first present a Mixed Integer Linear Programming (MILP) formulation that yields the optimal solution; however, due to its computational intractability, we propose a novel adaptation of the Multi-Objective Evolutionary Algorithm by Decomposition (MOEA/D), with an embedded heuristic algorithm to assist in the chromosome fitness calculation. This method leverages the similarity among neighboring subproblems in a multi-objective framework to efficiently approximate the underlying Pareto frontier. In the experiments, the proposed method is contrasted with a sophisticated single-objective Rollout approach. Our results demonstrate the benefits of adopting a multi-objective algorithm in terms of performance, stability and interpretability across different scalarized subproblems. The proposed framework offers a practical intent-based decision support tool for edge infrastructure providers, weighing CAPEX against operating objectives ahead of initial deployment.

User Equipment (UE)-centric Cell-Free massive Multiple-Input Multiple-Output (CF mMIMO) has emerged as a key enabling architecture for sixth-generation (6G) networks, offering a favorable trade-off between performance gains, cost and energy-efficiency. However, optimizing Access Point (AP) deployment and hardware provisioning in UE-centric CF mMIMO remains a challenging task, because planning decisions are tightly coupled with complex operational decisions such as the dynamic AP-UE clustering. In this paper, we address the joint planning-and-operation problem for UE-centric CF mMIMO networks under realistic cost, energy and performance-related models and constraints. We propose a hierarchical optimization framework in which a novel Deployment Evolutionary Algorithm (DEA) iteratively refines AP locations and heterogeneous hardware configurations, while a Weight-driven Greedy Round-Robin (WG-RR) algorithm acts as an operational oracle, performing UE-centric AP–UE clustering during the operational phase in a manner consistent with operator-defined business intents (i.e. objective weights). To ensure robust and realistic network dimensioning, candidate deployments are evaluated over multiple traffic demand-oriented snapshots that capture UE mobility and spectral-efficiency demand fluctuations. Extensive multi-objective and multi-snapshot evaluations reveal significant spectral-efficiency diminishing returns with increasing deployment and cooperation density, exposing practical operating points that substantially reduce CAPEX and operational power with negligible performance loss. The results further demonstrate that heterogeneous AP deployments enable superior planning decisions, thereby supporting the gradual and sustainable integration of UE-centric CF mMIMO into existing multi-cell infrastructures.

The complexity of modern applications necessitates the decomposition of workloads into logically dependent subtasks. As infrastructures move closer to data sources to decongest backbone networks and reduce communication delays, task deployment and scheduling become increasingly challenging. Orchestrators must respect spatial and temporal dependencies among subtasks and computing nodes, while optimizing goals such as latency and energy consumption. As edge adoption remains limited, operators pursue cooperative solutions that share resources without requiring significant investment. We consider a collaborative infrastructure, split into multiple domains, each with proprietary resources, and a shared pool for all service demands. Multiple agents operate concurrently with partial knowledge of the system, cooperating to allocate shared resources efficiently. In this work, we propose a Multi-Agent Reinforcement Learning scheduler that leverages Graph Neural Networks to handle spatiotemporal dependencies and uses lightweight inter-domain messaging for inter-domain cooperation. The learned policy is scalable and effective, reducing execution time and energy, increasing parallelism and mitigating congestion in simulations with real workload data.

Edge computing brings processing closer to data sources, reducing latency and bandwidth usage for modern applications. However, the limited capacity of edge resources and volatile nature of workload demands create significant challenges for efficient resource management, often leading to resource underutilization. In this work, we propose a speculative resource allocation framework supported by stochastic workload forecasting, inspired by the Black-Scholes financial model. This framework dynamically assesses the risk associated with fluctuating demands over different time windows and proactively aligns resource allocation based on the performed risk assessments. The outcomes of this model drive a multi-objective heuristic mechanism that dynamically manages resources, speculatively aligning differing workload demands when placing them within a node, optimizing key performance metrics such as latency, infrastructure utilization, costeffectiveness, and potential application disruptions during execution. Our approach does not require training, making it more adaptable to fluctuating demands compared to machine learning-based methods. Through simulations we demonstrate that our framework improves performance and resource utilization, providing a scalable, responsive, and cost-effective solution that benefits both end-users and operators.

Edge computing has consolidated as an essential technology for addressing the stringent requirements of modern applications, by distributing computing resources closer to data sources. Nonetheless, this innovation introduces significant challenges for the infrastructure designers and operators, given the high number of edge locations, the heterogeneity of edge resources and the varying requirements of today’s applications. Effective edge-network design is critical to harnessing its full potential, ensuring optimal performance, resource availability and cost efficiency during the applications’ execution. In this work, we propose mechanisms that address the challenge of joint optimal edge deployment location and capacity and device configuration, with respect to workload constraints. We formulate the respective problem as a multi-objective optimization that simultaneously considers the activation and resource costs, energy efficiency, and the workload’s experienced latency. Initially, we present the Mixed Integer Linear Programming (MILP) formulation that yields the optimal solution. To tackle its increased computational complexity, we also propose a rollout mechanism. It iteratively leverages a best-fit heuristic to perform the resource allocation and thus evaluates the impact of different deployment schemes on the overall system performance in a reinforcement learning manner. Our simulation experiments demonstrate the effectiveness of the developed mechanisms in enhancing responsiveness, reducing energy consumption and optimizing the Return On Investment (ROI) of the infrastructure across various deployment scenarios.

The EU-funded EMPYREAN project (empyrean-horizon.eu) aims to establish a hyper-distributed computing paradigm, leveraging collaborative, heterogeneous IoT devices and federated resources. EMPYREAN focuses on developing technologies for efficient AI workload processing, secure distributed edge storage and cloud-native application development. It will offer open and standardised APIs and use open-source platforms. EMPYREAN's capabilities will be demonstrated through three use cases: advanced manufacturing, smart agriculture, and warehouse automation.

Edge computing is a recent paradigm where the processing takes place close to the data sources. It therefore reduces latency and saves bandwidth compared to traditional cloud computing. The latter can continue to play a supportive role. Edge-cloud computing provides benefits in many use cases including distributed computation algorithms, where the processing is divided into a number of tasks that are executed in parallel on different equipment. An important relevant challenge is to allocate the appropriate resources to process the data that are continuously generated from user devices. The issue becomes more complicated when we take into account the variations in the volume of the generated data as a function of time. In this paper we present a resource allocation algorithm for distributed computation with emphasis on machine learning algorithms. We consider that the resource requirements vary with time in a semi-static way that exhibits some daily pattern. We distinguish between periodic (expected) variations that occur during the day, and sporadic variations due to unexpected events. We propose an Integer Linear Programming algorithm to allocate the periodic resource requirements. To handle the non-periodic requirements, we consider a suitable prediction algorithm coupled with a reconfiguration algorithm that allocates the predicted required resources. Our results indicate that our proposal outperforms traditional allocation algorithms in terms of resource utilization, monetary cost and achieved accuracy.

Abstract The orchestration of cloud computing infrastructures is challenging, considering the number, heterogeneity and dynamicity of the involved resources, along with the highly distributed nature of the applications that use them for computation and storage. Evidently, the volume of relevant monitoring data can be significant, and the ability to collect, analyze, and act on this data in real time is critical for the infrastructure’s efficient use. In this study, we introduce a novel methodology that adeptly manages the diverse, dynamic, and voluminous nature of cloud resources and the applications that they support. We use knowledge graphs to represent computing and storage resources and illustrate the relationships between them and the applications that utilize them. We then train GraphSAGE to acquire vector-based representations of the infrastructures’ properties, while preserving the structural properties of the graph. These are efficiently provided as input to two unsupervised machine learning algorithms, namely CBLOF and Isolation Forest, for the detection of storage and computing overusage events, where CBLOF demonstrates better performance across all our evaluation metrics. Following the detection of such events, we have also developed appropriate re-optimization mechanisms that ensure the performance of the served applications. Evaluated in a simulated environment, our methods demonstrate a significant advancement in anomaly detection and infrastructure optimization. The results underscore the potential of this closed-loop operation in dynamically adapting to the evolving demands of cloud infrastructures. By integrating data representation and machine learning methods with proactive management strategies, this research contributes substantially to the field of cloud computing, offering a scalable, intelligent solution for modern cloud infrastructures.

Edge computing has emerged as a computing paradigm where the application and data processing takes place close to the end devices. It decreases the distances over which data transfers are made, offering reduced delay and fast speed of action for general data processing and store/retrieve jobs. The benefits of edge computing can also be reaped for distributed computation algorithms, where the cloud also plays an assistive role. In this context, an important challenge is to allocate the required resources at both edge and cloud to carry out the processing of data that are generated over a continuous (“infinite”) time horizon. This is a complex problem due to the variety of requirements (resource needs, accuracy, delay, etc.) that may be posed by each computation algorithm, as well as the heterogeneous resources’ features (e.g., processing, bandwidth). In this work, we develop a solution for serving weakly coupled general distributed algorithms, with emphasis on machine learning algorithms, at the edge and/or the cloud. We present a dual-objective Integer Linear Programming formulation that optimizes monetary cost and computation accuracy. We also introduce efficient heuristics to perform the resource allocation. We examine various distributed ML allocation scenarios using realistic parameters from actual vendors. We quantify trade-offs related to accuracy, performance and cost of edge/cloud bandwidth and processing resources. Our results indicate that among the many parameters of interest, the processing costs seem to play the most important role for the allocation decisions. Finally, we explore interesting interactions between target accuracy, monetary cost and delay.

Cell-Free (CF) technology is considered as a candidate to support the “5G and beyond” networks, mitigating the limitations of the traditional networks in terms of flexibility and intercell interference. These networks consist of distributed Access Points (APs) that form clusters, and co-operate in time to serve the User Equipment (UE) demands. The number of the AP that participate in a cluster and the level at which they cooperate impacts both the achieved spectral efficiency and the size of the utilized communication and processing resources, which in most cases are scarce and limited. In our work, we propose mechanisms that perform joint allocation of fiber and wireless resources in a converged fiber-wireless infrastructure, consisting of a TWDM PON, mMIMO Base Stations and CF. To perform the joint allocation of the wireless and wired resources, we propose an optimal Mixed Integer Linear Program (MILP). As the complexity is high and the execution time prohibitively long for real size scenarios, we also present a multi-agent rollout mechanism to efficiently tradeoff execution time with performance.

We present an end-to-end solution to facilitate the seamless execution of hardware-accelerated compute-intensive tasks on heterogeneous hardware platforms spanning the Cloud-Edge continuum. Our approach includes a programming interface, orchestration, application management components, the vAccel framework, and a library of hardware-accelerated kernels. These components enable a Function-as-a-Service (FaaS) based operational flow that supports numerous diverse use cases while minimizing the time required for the developer to integrate their code and for the vendor to provide hardware acceleration capabilities to end users. Experimental results showcase the merits of our approach.

Distributed storage systems spanning across different cloud data centers have substantially improved availability and flexibility for data storage and retrieval operations. However, stringent latency requirements of emerging applications necessitate optimized selection of storage resources that exhibit smaller delay. Introducing edge resources into distributed storage systems enables data placement closer to its source, but simultaneously increases the complexity of decision-making and orchestration processes for optimal data placement. In this work, we develop mechanisms for storing data across an infrastructure that includes both edge and cloud resources. Our approach focuses on optimizing data integrity, longevity, security, and cost, while leveraging erasure coding when performing the resource allocation. We first present a comprehensive mixed integer linear programming formulation of the storage resource orchestration problem. As the search space for the optimal solution can be vast and the execution time prohibitively large for real size problems, we also propose an innovative multi-agent heuristic approach that uses the rollout, a reinforcement based policy, to balance performance and execution time efficiently. Through various simulation experiments, we evaluate the developed mechanisms and trade-offs involved in our approach. By incorporating data from a multi-cloud provider, we further enhance the validity of the simulations and the conclusions drawn.

Networks are always progressing to support the evolving and diverse applications and the needs for improved capacity, latency and security. To this end, monitoring is key to ensuring the uninterrupted network operation and the QoS of the applications. Network Tomography uses a subset of monitoring information (corresponding to partial view of the network state) to estimate wide-sense network performance, including unmonitored parameters. In this paper, we present a novel Machine Learning (ML) formulation for Network Tomography. The proposed formulation accounts for realistic scenarios where: i) the existence of certain links of the network is not known (e.g., due to security reasons), ii) the routing is dynamic (non-deterministic), i.e., for the same origin-destination node pair, a different route may be selected depending on the state of certain links. Our simulations indicate that our proposal has better estimation accuracy compared to traditional algebraic or other ML approaches that cannot or do not take into account these two assumptions.

Edge computing has emerged as a paradigm for local computing/processing tasks, reducing the distances over which data transfers are made. Thus, an opportunity is presented for data transfer-intensive, distributed machine learning. In this paper we develop a solution for serving distributed Machine Learning (ML) training jobs at the edge– cloud continuum. We model the specific requirements of each ML job, and the features of the edge and cloud resources. Next, we develop an Integer Linear Programming algorithm to perform the resource allocation. We examine different scenarios (different processing and bandwidth costs) and quantify tradeoffs related to performance and cost of edge/cloud bandwidth and processing resources. Our simulations indicate that even though there are many parameters that determine the allocation, the processing costs seem to play on average the most important role. The cloud b/w costs can be significant in certain scenarios. Finally, in certain examined cases, significant monetary benefits can be achieved through the collaboration of both edge and cloud resources when compared to using exclusively edge or cloud resources.

The uncertain and non-dispatchable nature of renewable energy sources renders Demand Response (DR) a critical component of modern electricity distribution systems. Demand Response (DR) service provision takes place via aggregators and special distribution-level markets (e.g., flexibility markets), where small, distributed DR resources, such as building energy management systems, electric vehicle charging stations, micro-generation and storage, connected to the low-voltage distribution grid, offer DR services. In such systems, energy balancing (and thus, also DR decisions) have to be made close to real-time. Thus, market clearing algorithms for DR service provision must fulfill several requirements related to the efficiency of their operation. More specifically, a DR market clearing algorithm needs to be optimal in terms of cost-efficiency, scalable in terms of number of assets and locations, and able to satisfy real-time constraints. In order to cope with these challenges, this article presents a distributed DR market clearing algorithm based on Lagrangian decomposition, combined with an optimal cloud resource allocation algorithm for assigning the required computation power. A heuristic algorithm is also presented, able to achieve a near-optimal solution, within negligible computational time. Simulations, performed on a testbed, demonstrate the computational burden introduced by various DR models, as well as the heuristic algorithm's near-optimal performance. The resource allocation algorithm is able to service multiple DR requests (e.g., in multiple distribution networks), and minimize the cost of computational resources while respecting the execution time constraints of each request. This enables third parties to offer cost-efficient and competitive DR operation as a service.

In modern power systems with high penetration of renewable energy sources, the flexibility provided by distributed energy resources is becoming invaluable. Demand aggregators offer balancing energy in the real-time balancing market on behalf of flexible resources. A challenging task is the design of the offering strategy of an aggregator. In particular, it is difficult to capture the flexibility cost of a portfolio of flexibility assets within a price-quantity offer, since the costs and constraints of flexibility resources exhibit inter-temporal dependencies. In this article, we propose a generic method for constructing aggregated balancing energy offers that best represent the portfolio’s actual flexibility costs, while accounting for uncertainty in future timeslots. For the case study presented, we use offline simulations to train and compare different machine learning (ML) algorithms that receive the information about the state of the flexible resources and calculate the aggregator’s offer. Once trained, the ML algorithms can make fast decisions about the portfolio’s balancing energy offer in the real-time balancing market. Our simulations show that the proposed method performs reliably towards capturing the flexibility of the Aggregator’s portfolio and minimizing the aggregator’s imbalances.

The design and operation of any network are complex processes that require the evaluation, utilization and configuration of a variety of usually expensive network devices. Through the use of an emulation platform, network operators are able to examine different scenarios and network parameters and benefit from multi-objective decision mechanisms. These enable the decrease of the network design phase duration and the optimal operation of the network under different well examined conditions. In this work, we present an emulation platform for SDN-enabled 5G integrated Fiber-Wireless networks that provides a transparent view of the 5G infrastructure to any SDN-based control plane. We present the overall architecture and design of the emulator, along with the implementation details of its main components. Network devices are described through YANG models and are emulated using containerized processes, configured and managed through the Network Configuration (NETCONF) protocol. Finally, a number of emulation scenarios are described and evaluated, utilizing a joint fiber and wireless resource allocation algorithm that drives the SDN-enabled devices.

We present the Disaster Recovery Layer (DRL) that enables OpenStack-managed datacenter workloads, Virtual Machines (VMs) and Volumes, to be protected and recovered in another datacenter, in case of a disaster. This work has been carried out in the context of the EU FP7 ORBIT project that develops technologies for enabling business continuity as a service. The DRL framework is based on a number of autonomous components and extensions of OpenStack modules, while its functionalities are available through OpenStack's Horizon UI and command line interface. Also, the DRL's architecture is extensible, allowing for the easy and dynamic integration of protection, restoration and orchestration plug-ins that adopt new approaches. A distributed disaster detection mechanism was also developed for identifying datacenter disasters and alerting the DRL. For the evaluation of the DRL, a two (active and backup) datacenters testbed has been setup in respective sites in Umea and Lulea, 265km apart and connected through the Swedish national research and education network. In case of a disaster, traffic is redirected between the datacenters utilizing the BGP anycast scheme. The experiments performed, show that DRL can efficiently protect VMs and Volumes, with minimum service disruption in case of failures and low overhead, even when the available bandwidth is limited.

The efficient allocation of network resources is key to the overall performance and the quality of services provided. Thanks to their high data rates, optical networks are the cornerstone of present and future core, metro, access, and datacenter networking. Many works in the field, formulate resource allocation operations as offline combinatorial problems, assuming a known static traffic matrix, and use integer linear programming (ILP) as well as heuristics. In contrast, other works assume randomly generated traffic and propose online schemes that serve connection requests one by one. In practice, traffic in optical networks is neither static nor completely random, but is usually semi-periodic, following some (e.g., daily or weekly) pattern. We present a traffic-pattern-driven approach for elastic optical networks for serving immediate and in advance network requests, where the decisions of an offline process, optimizing resource allocation for the traffic pattern expected during an epoch (day, week, etc.), are analyzed and then drive the operation of an online process that serves requests one by one, as they arrive. In this way, the online mechanism's decisions come close to the optimal ones, if the traffic pattern indeed repeats itself to some extent, while its execution time remains small. We present two alternatives of this approach, the exact and the relative, based on the way the offline mechanism's decisions are analyzed and translated to online actions. Our simulation results exhibit the performance benefits of the pattern-driven approach under various traffic conditions.

Today's Data Centers networks depend on optical switching to overcome the scalability limitations of traditional architectures. All optical networks most often use slotted Time Division Multiple Access (TDMA) operation; their buffers are located at the optical network edges and their organization relies on effective scheduling of the TDMA frames to achieve efficient sharing of the network resources and a collision-free network operation. Scheduling decisions have to be taken in real time, a process that becomes computationally demanding as the network size increases. Accelerators provide a solution and the present paper proposes a scheduler accelerator to accommodate a data center network divided into points of delivery (pods) of racks and exploiting hybrid electro-optical top-of-rack (ToR) switches that access an all-optical inter-rack network. The scheduler accelerator is a parallel scalable architecture with application specific processing engines. Case studies of 2, 4, 8, 16 processors configuration are presented for the processing of all the transfer TDMA time slot requests for the cases of 512 and 1024 ToR network nodes. The architecture is realized on a Xilinx VC707 board to validate the results.

The shift of the radio processing to the cloud, through cloud Radio Access Networks (C-RAN) technologies and of the cloud processing to the edge, through edge computing, form the environment in which 5G systems are being implemented, fostered and transformed from a future technology to a mainstream one. By its nature, global optimization of the edge resource deployment cannot by easily performed considering the number and the diversity of the players that will be involved in the edge computing arena. As a result, building and maintaining more and more edge-located resources for serving radio and application data will eventually lead to increased cost and energy consumption and resource underutilization. One way to overcome this predicament, is through virtual resource consolidation, where separate but efficiently interconnected edge resources appear as a single computing entity, serving radio and application data. In this context, we present the Virtual Elastic Datacenters (VEDC) in the edge notion for 5G networks that can alleviate these issues. We also describe an Integer Linear Programming (ILP) based mechanism for the placement of baseband and application processing loads in a VEDC-based environment, and perform respective experiments. We show that through VEDC resource consolidation better quality services can be provided, while improving resource efficiency.

In the Internet of Things (IoT) era, a vast number of (smart) end devices forward their traffic to the Internet, either by direct communication to LTE networks, or by multihop transmissions to a specific gateway. Acquiring both types of communication capabilities for IoT end devices would be unnecessarily costly. Instead, for a cost effective IoT infrastructure, only devices performing as gateways could be fully equipped with such capabilities, while the remaining devices could have simple low cost wireless transceivers, of differing transmission specifications, to forward/relay the traffic toward a gateway. Furthermore, the IoT devices network should comply with specific quality of service (QoS) requirements, specified for each IoT device. In this context, the IoT network planning problem, where we have to select the number of gateways and their locations along with respective transceivers for IoT devices, is key to provide a low cost and QoS aware IoT infrastructure. We formulate the planning problem as an integer linear program (ILP) that minimizes the total cost of the devices deployed in the network, while achieving the mandatory QoS requirements. We also present a heuristic algorithm of lower complexity that was observed to provide solutions near the optimal ones, in scenarios that we tracked optimal solutions with the ILP. A variety of performance evaluation results exhibits the effectiveness of the proposed algorithms in terms of network cost and efficiency.

We propose a scheme to reduce monitoring uncertainties in optical networks. The proposed scheme uses monitoring data of optical connections (lightpaths) which can be obtained from coherent optical receivers that can also function as optical performance monitors (OPM). We exploit both space and time correlation of the monitoring data in order to reduce the monitoring uncertainties. The improved accuracy can result in various benefits, the most common one is that the Quality of Transmission (QoT) can be estimated with higher accuracy which can in turn lead to more optimized decisions and lower provisioning costs. In this paper we present another application, we show how to use the obtained accurate monitoring data to localize soft failures (also referred to as QoT problems) on a per link level.

Energy consumption and the associated costs constitute a crucial issue concerning the design and operation of data networks and data centers. Energy-awareness is required in all levels, ranging from physical layer to algorithms, protocols and applications. Architecture-wise, a promising solution for tackling the increasing energy requirements is the deployment of optics at both long and shorter distances, including within data centers. Vertical Cavity Surface Emitting Lasers (VCSEL) constitute a popular photonic transmitter technology used in numerous short-range applications, providing also the ability to reduce energy consumption by scaling down the transmission bit rate. In this study we focus on the algorithmic aspects of energy management by proposing an OptiMal EnerGy Aware (OMEGA) routing algorithm to operate in optical networks utilizing VCSEL-based opto-electronic links. The algorithm leverages the capability of VCSELs to adapt the energy dissipation with respect to the transmission bit rate. Simulation results, under various traffic patterns, show that OMEGA balances efficiently the traffic load over the network's links, resulting in high throughput and low energy consumption.

In the Internet of Things (IoT) era, a large number of data packets are exchanged among devices over the Internet. IoT (smart) end devices forward their traffic to the Internet, either by direct communication to LTE networks, or by multi-hop transmissions to a specific gateway. Acquiring both types of communication capabilities would be unnecessarily costly for IoT end devices. Instead, to lower the overall cost, only devices performing as gateways could be fully equipped with such capabilities, while the rest of the devices could have simple low cost wireless transmitters for forwarding the traffic towards a gateway. Towards this end, the decision on gateway placement is critical to provide low cost and Quality of Service (QoS). To address this design problem, we present an Integer Linear Programming (ILP) that minimizes the total cost of the network with respect to the deployed devices, while achieving mandatory QoS requirements. Using this formulation we obtain solutions for random topologies that exhibit the effectiveness of our approach in terms of network cost and efficiency.

The millions of tweets submitted daily overwhelm users who find it difficult to identify content of interest revealing the need for event detection algorithms in Twitter. Such algorithms are proposed in this paper covering both short (identifying what is currently happening) and long term periods (reviewing the most salient recently submitted events). For both scenarios, we propose fuzzy represented and timely evolved tweet-based theoretic information metrics to model Twitter dynamics. The Riemannian distance is also exploited with respect to words' signatures to minimize temporal effects due to submission delays. Events are detected through a multiassignment graph partitioning algorithm that: 1) optimally retains maximum coherence within a cluster and 2) while allowing a word to belong to several clusters (events). Experimental results on real-life data demonstrate that our approach outperforms other methods.

The Feed In Tariff policy (FIT) used for accelerating renewable energy investments cannot be retained as a sustainable business model for the future smart energy grid. It is also evident that the current centralized electricity market prevents small or very small energy producers, who usually generate energy by renewable means, to participate. In this paper, addressing the aforementioned problems, at first, we present a decentralized architecture (Virtual DER Clusters), where small Distributed Energy Sources (DERs) are united in coalitions, each participating in the market as a single entity. Then, efficient clustering algorithms are proposed based on a min-max optimization policy in order to dynamically derive the cluster that best satisfies coalition's goals. Maximization in the sense of increasing as much as possible the profits of small-scale energy producers. Minimization in the sense of creating dynamically most competitive clusters. In this paper, three clustering policy schemes are discussed, each presenting different advantages with respect to the contradictory benefits between DERs and power utilities. From the examined policies, a fair sharing allocation scheme seems to be a good compensator between the electricity market and the small-scale players.

The electricity market for Renewable Energy (RE) Sources (RES) has to be transformed into a market that is more competitive and decentralized than the current one, given the failure of subsidy policies, like the Feed-In-Tariff (FIT) policy, and the increase in the number of small producers but also in the number of power utilities. Clearly, each utility must follow regulation rules regarding the proportion of RES units it must have in its energy mix, in order to avoid emission penalties. Following a decentralized market scheme, we address the problem of allocating a total amount of RE demanded by a set of utilities in a local market to individual RES microgrids (MGs) that can cover the demands, considering two supply policies. In the first policy, a RES producer is assumed to be able to split its production into smaller parts so that it can supply multiple utilities, and a simple allocation algorithm is presented. In the second policy, a RES producer, due to market or technical constraints, cannot split its production and share it among utilities. In this case, we provide an algorithm that solves the problem effectively by viewing it as a knapsack problem. If the cost functions of MGs are independent of the utilities to which they sell (e.g., negligible transportation costs), the results show that the non-divisible policy slightly benefits the MGs. However, in a decentralized market, it is natural to assume that the cost functions of the producers depend on the location of the utilities. To account for this, we provide two more allocation algorithms under both examined supply policies. In this case, the non-divisible policy is much more profitable for MGs and, moreover, the entrance of new utilities in the market clearly benefits them over the divisible case.

The constant expansion of Renewable Energy Source (RES) installations results in increasing the price of electricity in an unsustainable way due to the Feed-In-Tariff (FIT) policy currently being used. The challenge is to create a more liberalized market mechanism without, however, deterring further small scale RES investments, which remain costly. In the current paper, we consider the local electricity market in a given country or geographical area (rural, island, or other), where a certain portion of demand is asked to be covered from DERs. As DERs tend to be to some extend isolated from the main grid, it is possible and desirable for a group of DERs in a geographical area to be organized in a static local association that acts as a multi-plant organization. If the DERs (being small and many, thus "price takers") negotiated as individual units with the market operator, they would achieve a price that is close to their marginal cost, which would be very small, much smaller than their average total cost. In this paper, we provide an algorithm that allows the coalition to offer its electricity production units at a higher price than normal market price without endangering their market share. The price they achieve is higher than if they participated in a complete liberalized market, but less than the tariff of the FIT policy. Interestingly, we find that the coalition has an optimal price at which its profits are maximized. Finally, we observed that if there are limited participants (coalitions) in the local electricity market, an upper bound needs to be set by a regulator, otherwise, the coalition will set the price at will.

Cloud computing and virtualized infrastructures are currently the baseline environments for the provision of services in different application domains. While the number of service consumers increasingly grows, service providers aim at exploiting infrastructures that enable non-disruptive service provisioning, thus minimizing or even eliminating downtime. Nonetheless, to achieve the latter current approaches are either application-specific or cost inefficient, requiring the use of dedicated hardware. In this paper we present the reference architecture of a fault-tolerance scheme, which not only enhances cloud environments with the aforementioned capabilities but also achieves high-performance as required by mission critical every day applications. To realize the proposed approach, a new paradigm for memory and I/O externalization and consolidation is introduced, while current implementation references are also provided.

Short distance optical interconnections, on-printed circuit boards, on-backplanes, and even on-chip, are a promising solution for replacing copper interconnections in future Data Center and HPC systems. Since photonic technology introduces new network building blocks, topology design for all the packaging levels should be reconsidered. This paper focuses on the on-board level of the packaging hierarchy, and proposes lay-out strategies for optical interconnection networks on optical printed circuit boards (OPCBs), based on direct topology families (tori, meshes and fully connected networks). We also describe a methodology for designing OPCBs given a set of input parameters, including building blocks specifications as well as traffic demands. The on-board topology design methodology generates all the feasible designs within the topology families examined, following our proposed OPCB lay-out approach, and selects the optimal designs based on specific optimization criteria.

We present a methodology, called communication-aware virtual infrastructures (COMAVI), for the concurrent migration of multiple Virtual Machines (VMs) in cloud computing infrastructures, which aims at the optimum use of the available computational and network resources, by capturing the interdependencies between the communicating VMs. This methodology uses multiple criteria for selecting the VMs that will migrate, with different weights assigned to each of them. COMAVI also selects the computing sites/units where the migrating VMs will be hosted, by accounting for the way migration affects the logical (or virtual) topologies formed by the communicating VMs and viewing this selection as a logical topology reconfiguration problem. COMAVI resolves the maximum possible number of VM resource shortages, while tending to minimize the number of migrations performed, the induced network overhead, the logical topology reconfigurations required, and the corresponding service interruptions. We evaluate the proposed method through simulations, where we exhibit their performance benefits.

Resource selection and task assignment are basic operations in distributed computing environments, like the grid and the cloud, where tasks compete for resources. The decisions made by the corresponding algorithms should be judged based not only on metrics related to user satisfaction, such as the percentage of tasks served without violating their quality-of-service (QoS) requirements, but also based on resource-related performance metrics, such as the number of resources used to serve the tasks and their utilization efficiency. In our work, we focus on the case of tasks with fixed but not strict time requirements, given in the form of a requested start and finish time. We propose an algorithm for assigning tasks to resources that minimizes the violations of the tasks' time requirements while simultaneously maximizing the resources' utilization efficiency for a given number of resources. The exact time scheduling of the tasks on the resources is then decided by taking into account the time constraints. The proposed scheme exploits concepts derived from graph partitioning, and groups together tasks so as to 1) minimize the time overlapping of the tasks assigned to a given resource and 2) maximize the time overlapping among tasks assigned to different resources. The partitioning is performed using a spectral clustering methodology through normalized cuts. Experimental results show that the proposed algorithm outperforms other scheduling algorithms for different values of the granularity and the load of the task requests.

The monitoring and the analysis of public clouds gains momentum, due to their widespread exploitation by individual users, researchers and companies for their daily tasks. We propose an algorithm for optimizing the cost and the utilization of a set of running Amazon EC2 instances by resizing them appropriately. The algorithm, namely Cost and Utilization Optimization (CUO) algorithm, receives information regarding the current set of instances used (their number, type, utilization) and proposes a new set of instances for serving the same load, so as to minimize cost and maximize utilization, or increase performance efficiency. CUO is integrated in Smart cloud Monitoring (SuMo), an open-source tool we develop for collecting monitoring data from Amazon Web Services (AWS) and analyzing them. A number of experiments are performed, using input data that correspond to realist AWS configuration scenarios, which exhibit the benefits of the CUO algorithm.

The cooperation among mobile hosts in wireless ad-hoc networks is usually in the form of nodes acting as intermediate relays that forward data from a source to an otherwise distant destination using point-to-point or point-to-multipoint links. A technique that has gained considerable recent attention is cooperative diversity, where nodes are organized for transmitting the same signal to a given, often otherwise unreachable, node. The receiver combines the multiple receptions to reconstruct the original signal. In this work, we examine the routing and power allocation problem under such a cooperative communications model, so as to obtain a cross-layer design of the network and the physical layer. We present and evaluate a multi-criteria cooperative routing algorithm that uses as parameters the nodes' residual energy and their transmission power. This algorithm selects for each source-destination pair a path, in the form of a sequence of groups of cooperative nodes, and the nodes' transmission powers. We perform a number of simulation experiments, assuming nodes with variable or fixed transmission power, evaluating the benefits of the proposed multi-criteria cooperative routing algorithm. The results show that our algorithm achieves significant energy savings and a larger number of successfully delivered packets than in the case where cooperation is not applied.

SUMMARY Grid scheduling algorithms are usually implemented in a simulation environment using tools that hide the complexity of the Grid and assumptions that are not always realistic. In our work, we describe the steps followed, the difficulties encountered and the solutions provided to develop and evaluate a scheduling policy, initially implemented in a simulation environment, in the gLite Grid middleware. Our focus is on a scheduling algorithm that allocates in a fair way the available resources among the requested users or jobs. During the actual implementation of this algorithm in gLite, we observed that the validity of the information used by the scheduler for its decisions affects greatly its performance. To improve the accuracy of this information, we developed an internal feedback mechanism that operates along with the scheduling algorithm. Also, a Grid computation resource cannot be shared concurrently between different users or jobs, making it difficult to provide actual fairness. For this reason we investigated the use of virtualization technology in the gLite middleware. We did a proof‐of‐concept implementation and performed an experimental evaluation of our scheduling algorithm in a small gLite testbed that proves the validity and applicability of our solutions. Copyright © 2012 John Wiley & Sons, Ltd.

We consider the problem of serving traffic in a spectrum-flexible optical network, where the spectrum allocated to an end-to-end connection can change so as to adapt to the time-varying required transmission rate. In the proposed framework, each connection is assigned a route and is allocated a reference frequency over that route, using an appropriate Routing and Spectrum Allocation (RSA) algorithm, but the spectrum it utilizes around the reference frequency is allowed to expand and contract to match source rate fluctuations. We propose and analyze three spectrum expansion/contraction (SEC) policies for modifying the spectrum allocated to each connection. The first policy, named the Constant Spectrum Allocation (CSA) policy, allocates a number of spectrum slots for exclusive use by each connection. We also present two policies that enable the dynamic sharing of spectrum slots among connections, named the Dynamic High Expansion-Low Contraction (DHL) and the Dynamic Alternate Direction (DAD) policy. We give exact formulas for calculating the blocking probability for a connection and for the whole network under the CSA policy and provide corresponding approximate analyses under the DHL and DAD policies. We also present a simple iterative RSA algorithm that uses the developed blocking models so as to minimize the average blocking of the network.

ABSTRACT We propose a class of novel energy‐efficient multi‐cost routing algorithms for wireless mesh networks, and evaluate their performance. In multi‐cost routing, a vector of cost parameters is assigned to each network link, from which the cost vectors of candidate paths are calculated using appropriate operators. In the end these parameters are combined in various optimization functions, corresponding to different routing algorithms, for selecting the optimal path. We evaluate the performance of the proposed energy‐aware multi‐cost routing algorithms under two models. In the network evacuation model, the network starts with a number of packets that have to be transmitted and an amount of energy per node, and the objective is to serve the packets in the smallest number of steps, or serve as many packets as possible before the energy is depleted. In the dynamic one‐to‐one communication model, new data packets are generated continuously and nodes are capable of recharging their energy periodically, over an infinite time horizon, and we are interested in the maximum achievable steady‐state throughput, the packet delay, and the energy consumption. Our results show that energy‐aware multi‐cost routing increases the lifetime of the network and achieves better overall network performance than other approaches. Copyright © 2011 John Wiley & Sons, Ltd.

We consider the online impairment-aware routing and wavelength assignment (IA-RWA) problem in transparent WDM networks. To serve a new connection, the online algorithm, in addition to finding a route and a free wavelength (a lightpath), has to guarantee its transmission quality, which is affected by physical-layer impairments. Due to interference effects, the establishment of the new lightpath affects and is affected by the other lightpaths. We present two multicost algorithms that account for the actual current interference among lightpaths, as well as for other physical effects, performing a cross-layer optimization between the network and physical layers. In multicost routing, a vector of cost parameters is assigned to each link, from which the cost vectors of the paths are calculated. The first algorithm utilizes cost vectors consisting of impairment-generating source parameters, so as to be generic and applicable to different physical settings. These parameters are combined into a scalar cost that indirectly evaluates the quality of candidate lightpaths. The second algorithm uses specific physical-layer models to define noise variance-related cost parameters, so as to directly calculate theQ-factor of candidate lightpaths. The algorithms find a set of so-called nondominated paths to serve the connection in the sense that no path is better in the set with respect to all cost parameters. To select the lightpath, we propose various optimization functions that correspond to different IA-RWA algorithms. The proposed algorithms combine the strength of multicost optimization with low execution times, making them appropriate for serving online connections.

Orthogonal Frequency Division Multiplexing (OFDM) has been recently proposed as a modulation technique for optical networks, due to its good spectral efficiency and impairment tolerance. Optical OFDM is much more flexible compared to traditional WDM systems, enabling elastic bandwidth transmissions. We consider the planning problem of an OFDM-based optical network where we are given a traffic matrix that includes the requested transmission rates of the connections to be served. Connections are provisioned for their requested rate by elastically allocating spectrum using a variable number of OFDM subcarriers. We introduce the Routing and Spectrum Allocation (RSA) problem, as opposed to the typical Routing and Wavelength Assignment (RWA) problem of traditional WDM networks, and present various algorithms to solve the RSA. We start by presenting an optimal ILP RSA algorithm that minimizes the spectrum used to serve the traffic matrix, and also present a decomposition method that breaks RSA into two substituent subproblems, namely, (i) routing and (ii) spectrum allocation (R+SA) and solves them sequentially. We also propose a heuristic algorithm that serves connections one-by-one and use it to solve the planning problem by sequentially serving all traffic matrix connections. To feed the sequential algorithm, two ordering policies are proposed; a simulated annealing meta-heuristic is also used to obtain even better orderings. Our results indicate that the proposed sequential heuristic with appropriate ordering yields close to optimal solutions in low running times.

We consider routing and wavelength assignment (RWA) in a WDM network consisting of optical cross-connect (OXC) nodes that have color and direction constraints. These restricted node architectures have a smaller cost than the more flexible (and best performing) ones usually assumed in the RWA problem. This introduces an interesting tradeoff between the network performance achieved, in terms of network blocking and number of manual interventions required, and the cost of the node architecture used. In the process of comparing the node architectures, we propose an adaptation of an RWA algorithm that accounts for the lack of node flexibility, aiming to achieve using the constrained node architectures, performance similar to that obtained with the fully flexible node architectures. Additionally, we consider different transponder assignment policies and determine their effect on performance.

We consider path protection in the routing and wavelength assignment (RWA) problem for impairment constrained WDM optical networks. The proposed multicost RWA algorithms select the primary and the backup lightpaths by accounting for physical layer impairments. The backup lightpath may either be activated (1+1 protection) or it may be reserved and not activated, with activation taking place when/if needed (1:1 protection). In case of 1:1 protection the period of time where the quality of its transmission (QoT) is valid, despite the possible establishment of future connections, should be preserved, so as to be used in case the primary lightpath fails. We show that, by using the multicost approach for solving the RWA with protection problem, great benefits can be achieved both in terms of the connection blocking rate and in terms of the validity period of the backup lightpath. Moreover the multicost approach, by providing a set of candidate lightpaths for each source destination pair, instead of a single one, offers ease and flexibility in selecting the primary and the backup lightpaths.

We consider the offline version of the routing and wavelength assignment (RWA) problem in transparent all-optical networks. In such networks and in the absence of regenerators, the signal quality of transmission degrades due to physical layer impairments. Because of certain physical effects, routing choices made for one lightpath affect and are affected by the choices made for the other lightpaths. This interference among the lightpaths is particularly difficult to formulate in an offline algorithm since, in this version of the problem, we start without any established connections and the utilization of lightpaths are the variables of the problem. We initially present an algorithm for solving the pure (without impairments) RWA problem based on a LP-relaxation formulation that tends to yield integer solutions. Then, we extend this algorithm and present two impairment-aware (IA) RWA algorithms that account for the interference among lightpaths in their formulation. The first algorithm takes the physical layer indirectly into account by limiting the impairment-generating sources. The second algorithm uses noise variance-related parameters to directly account for the most important physical impairments. The objective of the resulting cross-layer optimization problem is not only to serve the connections using a small number of wavelengths (network layer objective), but also to select lightpaths that have acceptable quality of transmission (physical layer objective). Simulations experiments using realistic network, physical layer, and traffic parameters indicate that the proposed algorithms can solve real problems within acceptable time.

We propose information aggregation as a method for summarizing the resource-related information, used by the task scheduler. Through this method the information of a set of resources can be uniformly represented, reducing at the same time the amount of information transferred in a Grid network. A number of techniques are described for aggregating the information of the resources belonging to a hierarchical Grid domain. This information includes the cpu and storage capacities at a site, the number of tasks queued, and other resource-related parameters. The quality of the aggregation scheme affects the efficiency of the schedulerpsilas decisions. We use as a metric of aggregation efficiency the Stretch Factor (SF), defined as the ratio of the task delay when the task is scheduled using complete resource information over the task delay when an aggregation scheme is used. The simulation experiments performed show that the proposed aggregation schemes achieve large information reduction, while enabling good task scheduling decisions as indicated by the SF achieved.

We describe our experiences from implementing and integrating a new job scheduling algorithm in the gLite Grid middleware and present experimental results that compare it to the existing gLite scheduling algorithms. It is the first time that gLite scheduling algorithms are put under test and compared with a new algorithm under the same conditions. We describe the problems that were encountered and solved, going from theory and simulations to practice and the actual implementation of our scheduling algorithm. In this work we also describe the steps one needs to follow in order to develop and test a new scheduling algorithm in gLite. We present the methodology followed and the testbed that was set up for the comparisons. Our research sheds light on some of the problems of the existing gLite scheduling algorithms and makes clear the need for the development of new.

We propose and evaluate an impairment-aware multi-parametric routing and wavelength assignment algorithm for online traffic in transparent optical networks. In such networks the signal quality of transmission degrades due to physical layer impairments. In the multi-parametric approach, a vector of cost parameters is assigned to each link, from which the cost vectors of candidate lightpaths are calculated. In the proposed scheme the cost vector includes impairment generating source parameters, such as the path length, the number of hops, the number of crosstalk sources and other inter-lightpath interfering parameters, so as to indirectly account for the physical layer effects. For a requested connection the algorithm calculates a set of candidate lightpaths, whose quality of transmission is validated using a function that combines the impairment generating parameters. For selecting the lightpath we propose and evaluate various optimization functions that correspond to different IA-RWA algorithms. Our performance results indicate that the proposed algorithms utilize efficiently the available resources and minimize the total accumulated signal degradation on the selected lightpaths, while having low execution times.

We design and implement a multicost impairment- aware routing and wavelength assignment algorithm for online traffic. In transparent optical networks the quality of a transmission degrades due to physical layer impairments. To serve a connection, the proposed algorithm finds a path and a free wavelength (a lightpath) that has acceptable signal quality performance by estimating a quality of transmission measure, called the Q factor. We take into account channel utilization in the network, which changes as new connections are established or released, in order to calculate the noise variances that correspond to physical impairments on the links. These, along with the time invariant eye impairment penalties of all candidate network paths, form the inputs to the algorithm. The multicost algorithm finds a set of so called non-dominated Q paths from the given source to the given destination. Various objective functions are then evaluated in order to choose the optimal lightpath to serve the connection. The proposed algorithm combines the strength of multicost optimization with low execution time, making it appropriate for serving online connections.

We consider the offline version of the routing and wavelength assignment (RWA) problem in transparent all-optical networks. In such networks and in the absence of regenerators, the signal quality of transmission degrades due to physical layer impairments. We initially present an algorithm for solving the static RWA problem based on an LP relaxation formulation that tends to yield integer solutions. To account for signal degradation due to physical impairments, we model the effects of the path length, the path hop count, and the interference among ligthpaths by imposing additional (soft) constraints on RWA. The objective of the resulting optimization problem is not only to serve the connection requests using the available wavelengths, but also to minimize the total accumulated signal degradation on the selected lightpaths. Our simulation studies indicate that the proposed RWA algorithms select the lightpaths for the requested connections so as to avoid impairment generating sources, thus dramatically reducing the overall physical-layer blocking when compared to RWA algorithms that do not account for impairments.

We present the conceptual basis and the initial planning for an open source management architecture for wireless sensor networks (WSN). Although there is an abundance of open source tools serving the administrative needs of WSN deployments, there is a lack of tools or platforms for high level integrated WSN management. This is because of a variety of factors, including the lack of open source management tools, the immaturity of tools that offer manageability for WSNs, the limited high level management capabilities of sensor devices and architectures, and the lack of standardization. The current work is, to our knowledge, the first effort to conceptualize, formalize and design a remote, integrated management platform for the support of WSN research laboratories. The platform is based on the integration and extension of two innovative platforms: jWebDust, a WSN operation and management platform, and OpenRSM, an open source integrated remote systems and network management platform. The proposed system architecture can support several levels of integration (infrastructure management, functionality integration, firmware management), corresponding to different use-cases and application settings.

We consider the offline version of the impairment-aware routing and wavelength assignment (IA-RWA) problem in transparent all-optical networks as a cross layer optimization problem. In optical networks and in the absence of regenerators, optical signal quality degrades due to physical layer impairments. We initially present an algorithm for solving the RWA problem based on an LP relaxation formulation that has acceptable integrality performance. To account for signal degradation due to physical layer impairments we extend our RWA formulation and constrain the interference among lightpaths using noise variance related parameters. The objective of the resulting optimization problem is not only to serve the connection requests by minimizing the number of utilized wavelengths, but also to select lightpaths that have acceptable physical layer performance.

In this work, we propose an energy-efficient multicasting algorithm for wireless networks for the case where the transmission powers of the nodes are fixed. Our algorithm is based on the multicost approach and selects an optimal energy-efficient set of nodes for multicasting, taking into account: i) the node residual energies, ii) the transmission powers used by the nodes, and iii) the set of nodes covered. Our algorithm is optimal, in the sense that it can optimize any desired function of the total power consumed by the multicasting task and the minimum of the current residual energies of the nodes, provided that the optimization function is monotonic in each of these parameters. Our optimal algorithm has non-polynomial complexity, thus, we propose a relaxation producing a near-optimal solution in polynomial time. The performance results obtained show that the proposed algorithms outperform established solutions for energy-aware multicasting, with respect to both energy consumption and network lifetime. Moreover, it is shown that the near-optimal multicost algorithm obtains most of the performance benefits of the optimal multicost algorithm at a smaller computational overhead.

A key problem in networks that support advance reservations is the routing and time scheduling of connections with flexible starting time. In this paper we present a multicost routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the data should start so as to minimize the reception time at the destination, or some other QoS requirement. The utilization profiles of the network links, the link propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm. We initially present a scheme of non-polynomial complexity to compute a set of so-called non-dominated candidate paths, from which the optimal path can be found. By appropriately pruning the set of candidate paths using path pseudo-domination relationships, we also find multicost routing and scheduling algorithms of polynomial complexity. We examine the performance of the algorithms in the special case of an Optical Burst Switched network. Our results indicate that the proposed polynomial time algorithms have performance that it is very close to that of the optimal algorithm.

In this paper we present a multicost algorithm for the joint time scheduling of the communication and computation resources that will be used by a task. The proposed algorithm selects the computation resource to execute the task, determines the path to route the input data, and finds the starting times for the data transmission and the task execution, performing advance reservations. We initially present an optimal scheme of non-polynomial complexity and by appropriately pruning the set of candidate paths we also give a heuristic algorithm of polynomial complexity. We evaluate the performance of our algorithm and compare it to that of algorithms that handle only the computation or communication part of the problem separately. We show that in a Grid network where the tasks are CPU- and data- intensive important performance benefits can be obtained by jointly optimizing the use of the communication and computation resources.

In this work we examine a task scheduling and data migration problem for grid networks, which we refer to as the data consolidation (DC) problem. DC arises when a task needs for its execution two or more pieces of data, possibly scattered throughout the grid network. In such a case, the scheduler and the data manager must select the data replicas to be used and the site where these will accumulate for the task to be executed. The policies for selecting the data replicas and the data consolidating site comprise the data consolidation problem. We propose and experimentally evaluate a number of DC techniques. Our simulation results brace our belief that DC is an important technique for data grids since it can substantially improve task delay, network load and other performance related parameters.

We design and implement various algorithms for solving the static RWA problem with the objective of minimizing the maximum number of requested wavelengths based on LP relaxation formulations. We present a link formulation, a path formulation and a heuristic that breaks the problem in the two constituent subproblems and solves them individually and sequentially. The flow cost functions that are used in these formulations result in providing integer optimal solutions despite the absence of integrality constraints for a large subset of RWA input instances, while also minimizing the total number of used wavelengths. We present a random perturbation technique that is shown to increase the number of instances for which we find integer solutions, and we also present appropriate iterative fixing and rounding methods to be used when the algorithms do not yield integer solutions. We comment on the number of variables and constraints these formulations require and perform extensive simulations to compare their performance to that of a typical min-max congestion formulation.

The existence of good probabilistic models for the job arrival process and job characteristics is important for the improved understanding of grid systems and the prediction of their performance. In this study, we present a thorough analysis of the job inter-arrival times, the waiting times at the queues, the execution times, and the data sizes exchanged at the kallisto.hellasgrid.gr cluster, which is part of the EGEE Grid infrastructure. By computing the Hurst parameter of the inter-arrival times we find that the job arrival process exhibits self-similarity/long-range dependence. We also propose simple and intuitive models for the job arrival process and the job execution times. The models proposed were validated and were found to be in very good agreement with our empirical measurements.

Future grid networks should be able to provide quality of service (QoS) guarantees to their users. In this work we propose a framework for grid networks that provides deterministic delay guarantees to its guaranteed service (GS) users and best effort service to its best effort (BE) users. The proposed framework is theoretically and experimentally analyzed. We also define four types of computational resources based on the type of users (GS, BE) these resources serve and the priority they give them. We implement the proposed QoS framework for grids and verify that it not only satisfies the delay guarantees given to GS users, but also improves performance in terms of deadlines missed and resource use. In our simulations, data from a real grid network are used, validating in this way the appropriateness and usefulness of the proposed framework.

In this paper, we present the architectural design of optical burst-buffers that can truly emulate input queuing and accommodate asynchronous burst operation. The architectural design uses wavelength converters and fixed feed-forward delay lines that are combined to form either a multiple-input buffer or a shared buffer. Both schemes are modular, allowing the logarithmic expansion of buffer size with the number of switching elements (wavelength converters).

In this work we study the combination of multicost routing and variable transmission power in wireless ad-hoc networks. In multicost routing, each link is assigned a cost vector consisting of several parameters. These parameters are treated separately and are combined at the end of the algorithm using various optimization functions, corresponding to different routing schemes, for selecting the optimal path. The cost parameters we use are the hop count, the interference caused, the node residual energies, and the node transmission powers. We assume that nodes can use power control to adjust their transmission power to the desired level. The experiments conducted show that the combination of multicost routing and adjustable transmission power can lead to reduced interference and energy consumption, improving network performance and lifetime.

In this paper, we propose a new algorithm for fair scheduling, and we compare it to other scheduling schemes such as the Earliest Deadline First and the First Come First Serve schemes. Our algorithm uses a max-min fair sharing approach for providing fair access to users. When there is no shortage of resources, the algorithm assigns to each task enough computational power for it to finish within its deadline. When there is congestion, the main idea is to fairly reduce the CPU rates assigned to the tasks, so that the share of resources that each user gets is proportional to the user’s weight. The weight of a user may be defined as the user’s contribution to the infrastructure or the price he is willing to pay for services or any other socioeconomic consideration. In our algorithms, all tasks whose requirements are lower than their fair share CPU rate are served at their demanded CPU rates. However, the CPU rates of tasks whose requirements are larger than their fair share CPU rate are reduced to fit the total available computational capacity in a fair manner.Three different versions of fair scheduling are adopted in this paper; the Simple Fair Task Order (SFTO), which schedules the tasks according to their respective fair completion times, the Adjusted Fair Task Order (AFTO), that refines the SFTO policy by ordering the tasks using the adjusted fair completion times, and the Max-min Fair Share (MMFS) scheduling policy, which simultaneously addresses the problem of finding a fair task order and assigning a processor to each task based on a Max-Min fair sharing policy. Experimental results and comparisons with traditional scheduling schemes, such as the Earliest Deadline First (EDF) and the First Come First Served (FCFS) are presented using three different error criteria. Validation of the simulations using real experiments of tasks generated from 3D image rendering processes is also provided. The three proposed scheduling schemes can be inte

This work provides a jitter analysis of size-based burst assembly algorithms and also discusses other burst assembly algorithms that use the packet delay as the assembly threshold to provide a bound on jitter.

In this paper we present a signaling protocol for QoS differentiation suitable for optical burst switching networks. The proposed protocol is a two-way reservation scheme that employs delayed and in-advance reservation of resources. In this scheme delayed reservations may be relaxed, introducing a reservation duration parameter that is negotiated during call setup phase. This feature allows bursts to reserve resources beyond their actual size to increase their successful forwarding probability and is used to provide QoS differentiation. The proposed signaling protocol offers a low blocking probability for bursts that can tolerate the round-trip delay required for the reservations. We present the main features of the protocol and describe in detail timing considerations regarding the call setup and the reservation process. We also describe several methods for choosing the protocol parameters so as to optimize performance and present corresponding evaluation results. Furthermore, we compare the performance of the proposed protocol against that of two other typical reservation protocols, a Tell-and-Wait and a Tell-and-Go protocol.

We present a detailed performance evaluation of a hybrid optical switching architecture called Overspill Routing in Optical Networks (ORION). The ORION architecture combines wavelength and (electronic) packet switching, so as to obtain the advantages of both switching paradigms. We have developed an extensive network simulator where the basic features of the ORION architecture were modeled, including suitable load-varying sources and edge/core node architectures. Various aspects of the ORION architecture were studied including the routing policies used (i.e. once ORION always ORION and lightpath reentry) and the various options available for the buffer architecture. The complete network study shows that ORION can absorb temporary traffic overloads, as intended, provided sufficient buffering is present.

We propose a MAC protocol for mobile ad hoc networks that uses power control for the RTS/CTS and DATA frame transmissions in order to improve energy and capacity utilization efficiency. Unlike IEEE 802.11, in our scheme the RTS frames are not sent using the maximum transmission power to silence neighbouring nodes, and the CTS frames do not silence all receiving nodes to the same degree. In contrast, the transmission power of the RTS frames follows a slow start principle, while the CTS frames, which are sent at maximum transmission power, prevent the neighbouring nodes from transmitting their DATA frames with power more than a computed threshold, while allowing them to transmit at power levels less than that threshold. This is done by including in the RTS and the CTS frames additional information, such as the power of the transmissions, and the interference tolerance of the nodes. Moreover the DATA frames are sent at the minimum required transmission power increased by a small margin to ensure connectivity with the intended receiver, so as to cause minimal interference to neighbouring nodes and allow for future interference to be added to the receiver of the DATA frames. The power to be used by the transmitter is computed by the recipient of the RTS frame and is included in the CTS frame. It is expected that a network with such a power management scheme would achieve a better throughput performance and more power savings than a network without such a scheme

We present a 40 Gb/s asynchronous self-routing network and node architecture that exploits bit and packet level optical signal processing to perform synchronization, forwarding and switching. Optical packets are self-routed on a hop-by-hop basis through the network by using stacked optical tags, each representing a specific optical node. Each tag contains control signals for configuring the switching matrix and forwarding each packet to the appropriate outgoing link and onto the next hop. Physical layer simulations are performed, modeling each optical sub-system of the node showing acceptable signal quality and bit error rates. Resource reservation-based signaling algorithms are theoretically modeled for the control plane capable of providing high performance in terms of blocking probability and holding time.

In this paper, we present a comprehensive traffic analysis of the Greek School Network (GSN), a wide area network designed to provide Internet access and services to about 15,000 units of primary and secondary education schools and administration offices. In our analysis, we have used measurements from the PATRAS region node obtained through the Cisco NetFlow and FlowScan tools. We have used classical analysis to obtain protocol and application traffic statistics. Our study revealed that TCP traffic is dominant in the network, while nearly 50% of the outgoing and 37% of the incoming traffic is peer-to-peer (P2P) traffic, with a further 25.6% of traffic using not registered ports and suspected to be P2P as well. Finally, we have also observed a remarkable traffic locality phenomenon in the P2P services, where more than the 90% of the traffic was heading or generated by 50 hosts.

We study energy efficient routing strategies for wireless ad-hoc networks. In this kind of network, energy is a scarce resource and its conservation and efficient use is a major issue. Our strategy follows the multi-cost routing approach, according to which a cost vector of various parameters is assigned to each link. The parameters of interest are the number of hops on a path, and the residual energy and transmission power of the nodes on the path. These parameters are combined in various optimization functions, corresponding to different routing algorithms, for selecting the optimal path. We evaluate the routing algorithms proposed in a number of scenarios, with respect to energy consumption, throughput and other performance parameters of interest. From the experiments conducted, we conclude that routing algorithms that take into account energy related parameters, increase the lifetime of the network, while achieving better performance than other approaches, such as minimum hop routing.

In this paper a performance analysis of the packet scheduling switch is presented. The scheduling switch uses a series of feedforward delays interconnected with elementary optical switches. This series of programmable delay blocks constitutes an optical buffer of depth T, whose purpose is to delay/re-arrange incoming packets that request the same outgoing link so as to resolve or reduce packet contention. Performance results have been obtained for random Bernoulli traffic, Pareto traffic, as well as for smooth traffic with an upper bound of inherent burstiness.

Implementation of a commercial application to a grid infrastructure introduces new challenges in managing the quality-of-service (QoS) requirements, most stem from the fact that negotiation on QoS between the user and the service provider should strictly be satisfied. An interesting commercial application with a wide impact on a variety of fields, which can benefit from the computational grid technologies, is three-dimensional (3-D) rendering. In order to implement, however, 3-D rendering to a grid infrastructure, we should develop appropriate scheduling and resource allocation mechanisms so that the negotiated (QoS) requirements are met. Efficient scheduling schemes require modeling and prediction of rendering workload. In this paper workload prediction is addressed based on a combined fuzzy classification and neural network model. Initially, appropriate descriptors are extracted to represent the synthetic world. The descriptors are obtained by parsing RIB formatted files, which provides a general structure for describing computer-generated images. Fuzzy classification is used for organizing rendering descriptor so that a reliable representation is accomplished which increases the prediction accuracy. Neural network performs workload prediction by modeling the nonlinear input-output relationship between rendering descriptors and the respective computational complexity. To increase prediction accuracy, a constructive algorithm is adopted in this paper to train the neural network so that network weights and size are simultaneously estimated. Then, a grid scheduler scheme is proposed to estimate the queuing order that the tasks should be executed and the most appopriate processor assignment so that the demanded QoS are satisfied as much as possible. A fair scheduling policy is considered as the most appropriate. Experimental results on a real grid infrastructure are presented to illustrate the efficiency of the proposed workload prediction--scheduling algorithm compared to other approaches presented in the literature.

We propose a priority-based balanced routing scheme, called the priority STAR routing scheme, which leads to optimal throughput and average delay at the same time for random broadcasting and routing. In particular, the average reception delay for random broadcasting required in n/sub 1//spl times/n/sub 2//spl times/.../spl times/n/sub d/ tori with n/sub i/=O(1), n-ary d-cubes with n=O(1), or d-dimensional hypercubes is O(d+1/(1-/spl rho/)). We also study the case where multiple communication tasks for random 1-1 routing and/or random broadcasting are executed at the same time. When a constant fraction of the traffic is contributed by broadcast requests, the average delay for random 1-1 routing required in any d-dimensional hypercube, any n-ary d-cube with n = O(1), and most n/sub 1//spl times/n/sub 2//spl times/.../spl times/n/sub d/ tori with n/sub i/=O(1) are O(d) based on priority STAR. Our simulation results show that the priority-based balanced routing scheme considerably outperform the best previous routing schemes for these networks.

In this paper we propose a mathematical game, called the ball-arrangement game (BAG). A game with a different set of rules (e.g., permissible moves) gives rise to a different network, and the algorithm that solves the game gives rise to a routing algorithm in that network. Based on the insights provided by BAG, we propose several new classes of symmetric and modular networks, called super Cayley graphs, that have optimal (intercluster) diameters and average (intercluster) distances, small (intercluster) node degrees, high bisection bandwidth, strong embedding capability, and optimal communication algorithms given their (intercluster) node degrees.

We propose the robust algorithm-configured emulation (RACE) scheme for efficient parallel computation and communication in the presence of faults. A wide variety of algorithms originally designed for fault-free meshes, tori, and k-ary n-cubes can be transformed to corresponding robust algorithm through RACE. In particular optimal robust algorithms can be derived for total exchange (TE) and ascend/descend operations with a factor of 1+o (1) slowdown. Also, RACE can tolerate a large number of faulty elements, without relying on hardware redundancy or any assumption about the availability of a complete subarray.

We propose a new media-access and connection-establishment protocol for an ad-hoc quasi-synchronous packet radio network (QSPNET). In the QSPNET, the bandwidth is partitioned into a data channel, used to transmit packets, and a control channel, used to make reservations. The transmitted waveforms in the QSPNET are made quasi-synchronous by using a local GPS clock. The QSPNET uses a novel linear decorrelator receiver for multiuser detection, which permits the reception of quasi-synchronous code division multiple access (QS-CDMA) waveforms. We initially describe the QSPNET and its connection and flow control protocols, giving the rules of transmission and reception followed by all mobiles. We also provide performance results for the case where connection requests are generated at each node of the QSPNET according to a random process over an infinite time horizon. In particular, we obtain results on the achievable throughput and the average delay as a function of the transmission radius, the quasi-synchronous uncertainty interval, the duration of the connections, and the buffer size per node.

We present an analysis for both oblivious and adaptive routing in regular, all-optical networks with wavelength translation. Our approach is simple, computationally inexpensive, accurate for both low and high network loads, and the first to analyze adaptive routing with wavelength translation in wavelength division multiplexed (WDM) networks while also providing a simpler formulation of oblivious routing with wavelength translation. Unlike some previous analyses which use the link independence blocking assumption and the call dropping (loss) model (where blocked calls are cleared), we account for the dependence between the acquisition of wavelengths on successive links of a session's path and use a lossless model (where blocked calls are retried at a later time). We show that the throughput per wavelength increases superlinearly (as expected) as we increase the number of wavelengths per link, due both to additional capacity and more efficient use of this capacity; however, the extent of this superlinear increase in throughput saturates rather quickly to a linear increase. We also examine the effect that adaptive routing can have on performance. The analytical methodology that we develop can be applied to any vertex and edge symmetric topology, and with modifications, to any vertex symmetric (but not necessarily edge symmetric) topology. We find that, for the topologies we examine, providing at most one alternate link at every hop gives a per wavelength throughput that is close to that achieved by oblivious routing with twice the number of wavelengths per link. This suggests some interesting possibilities for network provisioning in an all-optical network. We verify the accuracy of our analysis for both oblivious and adaptive routing via simulations for the torus and hypercube networks.

We propose a scalable networking scheme for high-speed networks where quality of service (QoS) is important. The main objective of the scheme is to provide QoS guarantees and to achieve scalability to very large traffic volume and link bandwidth. Other important goals include extensibility, small to moderate buffer requirements, high throughput, small latency, and loss-free communication. The proposed scheme can service a wide variety of traffic classes and is applicable to various switching and multiplexing techniques.

Current VLSI technology allows more than two wiring layers and the number is expected to rise in future. In this paper we show that, by designing VLSI layouts directly for an L-layer model, the layout area for a variety of networks can be reduced by a factor of about (L/2)/sup 2/ compared to the layout area required under a 2-layer model, and the volume and maximum wire length can be reduced by a factor of about L/2, leading to considerably lower cost and/or higher performance. The proposed layouts for k-ary n-cubes, hypercubes, butterfly networks, cube-connected cycles (CCC), folded hypercubes, generalized hypercubes, k-ary n-cube cluster-c, hierarchical hypercube networks, reduced hypercubes, hierarchical swap networks, and indirect swap networks, are the best layouts reported for these networks thus far and are optimal within a small constant factor under both the Thompson model and the multilayer grid model. All of our layouts are optimally scalable in that we can allow each network node to occupy the largest possible area (e.g., o(N/L/sup 2/) for hypercubes) without increasing the leading constant of the layout area, volume, or maximum wire length.

We present a scheme for optimal VLSI layout and packaging of butterfly networks under the Thompson model, the multilayer grid model, and the hierarchical layout model. We show that when L layers of wires are available, an N-node butterfly network can be laid out with area 4N2/L2 log22 N + o (N2/L2 log2 N), maximum wire length 2N/L log2 N + o (N/L log N), and volume 4N2/L log22 N + o (N2/L log2 N) , under the multilayer 2-D grid model, where only one active layer (for network nodes) is required and L layers of wires are available.

We propose a communication protocol, called the virtual circuit deflection (VCD) protocol, which combines some of the individual characteristics of virtual circuit switching and deflection routing. An advantage of the VCD protocol over previous (datagram) deflection schemes is that deflections in the former occur on a per session basis (or a per subsession basis, if sessions need to be split to find adequate capacity on the outgoing links), while in the latter, they occur on a per packet basis. This makes packet resequencing at the destination considerably easier to accomplish in the VCD protocol than in datagram deflection schemes. The VCD protocol exploits the storage arising from the high bandwidth-delay product of optical fibers to provide lossless communication with little buffering at the switches and without the need for advance reservations. This makes it particularly suitable for networks that use optical switching, where buffers are expensive to implement with current optical technology. We present a simple implementation of the VCD protocol for such networks, which requires only limited buffering, accomplished through the use of a minimal number of optical delay lines. We also analyze the performance of the protocol for the Manhattan Street network topology by using new analytical models. In particular, we examine the effect of the traffic load and the network size on the throughput and the length of the paths followed by the sessions, and compare the analytical results obtained with corresponding simulation results. The results indicate that the VCD protocol is efficient under both light and heavy traffic conditions, especially when the link capacities are large compared to the basic rate of individual sessions, as is expected to be the case in future multigigabit networks.

The dynamic broadcast problem is the communication problem where source packets to be broadcast to all the other nodes are generated at each node of a parallel computer according to a certain random process, such as a Poisson process. The lower bounds on the average reception delay required by any oblivious dynamic broadcast algorithm in a d-dimensional hypercube are /spl Omega/(d+1/1-/spl rho/) when packets are generated according to a Poisson process, where p is the load factor. The best previous algorithms for hypercubes only achieve /spl Omega/(d/1-/spl rho/) average reception delay. In this paper, we propose dynamic broadcast algorithms that require optimal O(d+1/1-/spl rho/) average reception delay in d-dimensional hypercubes and n/sub 1//spl times/n/sub 2//spl times//spl middot//spl middot//spl middot/n/sub d/ tori with n/sub i/=O(1). We apply the proposed broadcast scheme to a variety of other network topologies for efficient dynamic broadcast and present several methods for assigning priority classes to packets.

We analyze limited wavelength translation in all-optical, wavelength division multiplexed (WDM) wrap-around mesh networks, where up to W wavelengths, each of which can carry one circuit, are multiplexed onto a network link. All-optical wavelength translators with a limited translation range permit an incoming wavelength to be switched only to a small subset of the outgoing wavelengths. Although more restrictive than full wavelength translation (which permits an incoming wavelength to be switched to any outgoing wavelength), limited wavelength translation is a topic of recent study, since current practical wavelength translators are capable only of limited translation. We consider the case where an incoming wavelength can be switched to one of k (k=2,3) outgoing wavelengths (called the feasible wavelength set), and we obtain the probability that a session arriving at a node at a random time successfully establishes a connection from its source node to its destination node. Our analysis captures the state of a feasible wavelength set at a network node, which allows us to obtain the probability of successfully establishing the circuit. Based on this probability, we quantify the benefits of limited wavelength translation by demonstrating that in mesh networks, it can obtain most of the performance advantages of full translation at a fraction of the cost. Our work is the first to analyze limited wavelength translation for mesh networks under a probabilistic model, and accurately predicts the network performance over a wider range of network loads than previous works.

We propose a new class of interconnection networks, called macro-star networks, which belong to the class of Cayley graphs and use the star graph as a basic building module. A macro-star network can have node degree that is considerably smaller than that of a star graph of the same size, and diameter that is sublogarithmic and asymptotically within a factor of 1.25 from a universal lower bound (given its node degree). We show that algorithms developed for star graphs can be emulated on suitably constructed macro-stars with asymptotically optimal slowdown. This enables us to obtain through emulation a variety of efficient algorithms for the macro-star network, thus proving its versatility. Basic communication tasks, such as the multimode broadcast and the total exchange, can be executed in macro-star networks in asymptotically optimal time under both the single-port and the all-port communication models. Moreover, no interconnection network with similar node degree can perform these communication tasks in time that is better by more than a constant factor than that required in a macro-star network. We show that macro-star networks can embed trees, meshes, hypercubes, as well as star, bubble-sort, and complete transposition graphs with constant dilation. We introduce several variants of the macro-star network that provide more flexibility in scaling up the number of nodes. We also discuss implementation issues and compare the new topology with the star graph and other popular topologies.

The ready-to-go virtual circuit protocol (or RGVC) is an immediate transmission protocol, in which the source need not wait for an end-to-end roundtrip delay for reservations to be made before transmitting the data. The protocol is designed to handle the lossless transport of ABR traffic, and will be used in the 40 Gb/s Thunder and Lightning testbed being prototyped at the University of California at Santa Barbara (UCSB). An important advantage of the RGVC protocol over previous connection and flow control protocols is that it is suitable for networks in which the switches use FIFO buffers that are shared by multiple sessions. The RGVC protocol ensures lossless communication by coupling link capacity with buffer space, so that when a portion of a buffer at a node is occupied, a proportional fraction of the incoming capacity to that buffer is frozen. Given the constraints on the frozen capacity, an algorithm is executed at each node to allocate the transmission rate to each FIFO buffer so as to maximize capacity utilization. The requirement that the protocol operate with FIFO buffers at the network nodes poses some unique challenges in the design that are not present in rate- and credit-based schemes. Briefly, since several sessions share a common FIFO buffer, per-VC flow control is no longer possible so control over the rate of an individual session is lost. Also, since the contents of the buffers change dynamically, the buffer composition becomes difficult to determine. For the rate-allocation algorithm of the RGVC protocol to be executed, however, the contents of the FIFO buffers at a node must be known, To implement the bookkeeping required, we present two schemes: the measurement-based scheme, where the bookkeeping function is implemented via measurements, done essentially in hardware; and the estimation-based scheme, where the bookkeeping is done analytically via the exchange of control packets between nodes.

We analyze circuit switching in a multiprocessor network, where connection requests (or sessions) arrive at each node of the network according to a Poisson process with rate /spl lambda/. Each session joins the appropriate input-queue at its source node, and, upon advancing to the head of the queue, transmits a setup packet to establish a connection. If the setup packet is successful, it reserves the links on the path for the duration of the session, and the session is served without interruptions. Otherwise, the connection request remains queued at the source, and subsequent attempts are made to establish the circuit. We analyze the queue of connection requests at the input-buffer of a network link, and obtain analytic expressions for the stability region, the average queuing delay, the average connection time, the average waiting time, and the average total delay, which show how these parameters depend on system variables, such as network dimension and session arrival rate. The queuing analysis focuses on the input-queue of a particular link, and accounts for the interactions with queues of other links through the retrial attempts and the associated probability of success. The queuing analysis is independent of the particular network topology under consideration, as long as the probability that a session arriving at a random time successfully establishes a connection can be calculated for that network. Simulations demonstrate the close agreement between the observed network behavior and that predicted by the analysis.

We propose a new switching format for multiprocessor networks, which we call conflict sense routing protocol. This switching format is a hybrid of packet and circuit switching, and combines advantages of both. We initially present the protocol in a way applicable to a general topology. We then present an implementation of this protocol for a hypercube computer and a particular routing algorithm. We also analyze the steady-state throughput of the hypercube implementation for random node-to-node communications.

We consider the problem where packets are generated at each node of a network according to a Poisson process with rate /spl lambda/, and each of them has to be broadcast to all the other nodes. The network topology is assumed to be an arbitrary bidirectional graph. We derive upper bounds on the maximum achievable broadcast throughput, and lower bounds on the average time required to complete a broadcast. These bounds apply to any network topology, independently of the scheme used to perform the broadcasts. We also propose two dynamic broadcasting schemes, called the indirect and the direct broadcasting scheme, that can be used in a general topology, and we evaluate analytically their throughput and average delay. The throughput achieved by the proposed schemes is equal to the maximum possible, if a half-duplex link model is assumed, and is at least equal to one half of the maximum possible, if a full-duplex model is assumed. The average delay of both schemes is of the order of the diameter of the trees used to perform the broadcasts. The analytical results obtained do not use any approximating assumptions.

We consider the problem where broadcast requests are dynamically generated at random time instants at each node of a multiprocessor network. In particular, in our model packets arrive at each node of a network according to a Poisson process, and each packet has to be broadcast to all the other nodes. We propose an on-line, distributed routing scheme to execute the broadcasts in this dynamic environment. Our scheme consists of repeated execution of a partial multinode broadcast task, which is a static communication task where any M/spl les/N arbitrary nodes of an N-processor network broadcast a packet to all the other nodes. The dynamic broadcasting scheme that we propose can be used in any topology, regular or not, for which partial multinode broadcast algorithms with certain properties can be found. We derive such an algorithm and we analyze the corresponding dynamic broadcasting scheme for the hypercube network. We show that its stability region tends to the maximum possible as the number of nodes of the hypercube tends to infinity. Furthermore, for any fixed load in the stability region, the average delay is of the order of the diameter of the hypercube. Our analysis does not use any approximating assumptions.>

Considers two different hypercube routing schemes, which are called the simple and the priority schemes. The authors evaluate the throughput of both the unbuffered and the buffered version of these schemes for random multiple node-to-node communications. The results obtained are approximate, but very accurate as simulations indicate, and are given in particularly interesting forms. They find that little buffer space (between one and three packets per link) is necessary to achieve throughput close to that of the infinite buffer case. They also consider two deflection routing schemes, called the simple nonwasting deflection and the priority nonwasting deflection schemes. They evaluate their throughput-using simulations, and compare them to the priority scheme.>

Multinode broadcast (MNB) in a hypercube and in a ring network of processors is considered. It is assumed that the lengths of the packets that are broadcast are not fixed, but are distributed according to some probabilistic rule, and the optimal times required to execute the MNB are compared for variable and for fixed packet lengths. For large hypercubes, it is shown, under very general probabilistic assumptions on the packet lengths, that the MNB is completed in essentially the same time as when the packet lengths are fixed. In particular, the MNB is completed by time (1+ delta )T/sub s/ with probability at least 1- epsilon , for any positive epsilon and delta , where T/sub s /is the optimal time required to execute the MNB when the packet lengths are fixed at their mean, provided that the size of the hypercube is large enough. In the case of the ring, it is proved that the average time required to execute a MNB when the packet lengths are exponentially distributed exceeds by a factor of ln n the corresponding time for the case there the packet lengths are fixed at their mean, where n is the number of nodes of the ring.>