Truck platooning is an innovative logistics approach to lower operational costs, particularly fuel consumption, while addressing contemporary transportation challenges. While recent studies on truck platooning have emphasized platoons’ energy savings, stability, and safety, there has been limited exploration of platoon formation and control. This paper uses optimal control theory to address the dispatching control of trucks with arriving platoons. In particular, trucks arrive at a highway station while platoons arrive alongside it. The station controls the truck holding and dispatching, where trucks are sent out with or without a platoon. Dispatching trucks with an arriving platoon reduces fuel consumption while waiting for a platoon to arrive increases the dwell time (i.e., transportation delay). We assume that an arriving platoon determines the number of trucks (i.e., the batch size) it can accept. Only a single truck can be dispatched if a platoon is absent. Hence, we formulate the dispatching control problem and derive the optimal policy for the discounted costs and the average cost governing the dispatch of trucks alongside platoons. We proved the optimality of threshold policies. Numerical results for the average cost case are presented. They are consistent with the optimal ones.

Task migration to remote servers offers a promising solution to the congestion issue in mobile edge computing systems. Our optimal task offloading design minimizes a system cost function, encompassing offloading and penalty costs. The offloading cost reflects external server resource usage, while the penalty cost accounts for task expiration risk. To optimize the expected cost over a time horizon, we employ Dynamic Programming (DP) and analyze its properties for an optimal offloading policy. “Curse of Dimensionality” of the DP equation poses computational challenges, especially with infinite state space. To mitigate this, we identify crucial policy properties, enabling DP evaluation on a finite state subset. Moreover, we show that the computation of the optimal task offloading decision at a given state can be deduced by leveraging the optimal decision taken at its “adjacent” states. We then provide numerical results to demonstrate parameter impact and validate theoretical findings.

Task offloading in mobile edge computing systems is subject to various random factors including the connection to external servers, new task requests from users, and the availability of local processing services. However, statistical information is often not available in practical scenarios. To tackle the issue, we adopt a Q-learning-based approach that learns the optimal task offloading policy through observations of random events. Traditional Q-learning methods may face challenges such as long training times and high memory usage due to the large state and action space. To overcome this problem, we propose a novel method that leverages the concept of adjacent state sequence. In this type of sequence, we can infer the optimal offloading decision of a system state from other states. This method aims to improve the convergence speed and memory efficiency of the learning model by reducing the number of parameters that need to be learned and stored. Those eliminated parameters instead can be computed via a derived linear expression. We conduct experiments to demonstrate the enhancement of our proposed method compared to the traditional$\mathbf{Q}-$learning in the studied problem.

Truck platooning is a promising technology that can reduce costs (fuel consumption) and enhance the overall transportation productivity. While recent research has focused on platoons' network and stability, few studies have tackled platooning formation and control. This paper uses Reinforcement Learning (RL) to study the dispatching control of trucks with arriving platoons, a problem first proposed in [1]. This work builds on [1] by considering the lack of the cost function and statistical knowledge. In particular, we employ Q-learning to compute the optimal dispatch control policy at a highway hub. Given the unbounded state space of the model, traditional Q-learning may converge slowly or even get stuck in sub-optimal policies. We improve Q-learning by confining the agent to transition in a finite subset of the state space. For this purpose, we use the switching condition property of the optimal policy (derived in [1]), the underlying random walk model, and a sensitivity analysis of the cost function. Our numerical results demonstrate that our Enhanced Q-learning converges significantly faster (up to 97%) in terms of CPU time and number of interactions.

As the automotive industry is developing autonomous driving systems and vehicular networks, attention to truck platooning has increased as a way to reduce costs (fuel consumption) and improve efficiency in the highway. Recent research in this area has focused mainly on the aerodynamics, network stability, and longitudinal control of platoons. However, the system aspects (e.g., platoon coordination) are still not well explored. In this paper, we formulate a platooning coordination problem and study whether trucks waiting at an initial location (station) should wait for a platoon to arrive in order to leave. Arrivals of trucks at the station and platoons by the station are modelled by independent Bernoulli distributions. Next we use the theory of Markov Decision Processes to formulate the dispatching control problem and derive the optimal policy governing the dispatching of trucks with platoons. We show that the policy that minimizes an average cost function at the station is of threshold type. Numerical results for the average cost case are presented. They are consistent with the optimal ones.

Inter-datacenter WANs connect geo-distributed datacenters and carry a considerable amount of traffic, generally a mix of flows. There has been little work done to provide custom guarantees depending on the nature of traffic requirements in such environments. In this paper we address this problem by proposing Vritti, an adaptable spatial-temporal system for traffic engineering in inter-datacenter WAN environments applicable to single and federated clouds. With Vritti, cloud providers can offer tailor-made guarantees to users with widely differing requirements (in terms of hard, soft or no deadlines) and traffic characteristics (in terms of known or unknown traffic volumes). We use linear programming to mathematically formulate the problem with the objective of maximizing utility. We propose two online algorithms to generate admission control, scheduling and routing decisions. Our simulations show that Vritti can effectively meet deadline transfers and provide fairness to non-deadline transfers in both single and federated cloud environments.

With over 300 billion vehicle trips made in the United States and 64 billion in France per year, network operators have the opportunity to utilize the existing road and highway network as an alternative data network to offload large amounts of delay-tolerant traffic. To enable the road network as a large-capacity transmission system, we exploit the existing mobility of vehicles equipped with wireless and storage capacities together with a collection of offloading spots. An offloading spot is a data storage equipment located where vehicles usually park. Data is transloaded from a conventional data network to the closest offloading spot and then shipped by vehicles along their line of travel. The subsequent offloading spots act as data relay boxes where vehicles can drop off data for later pick-up by other vehicles, depending on their direction of travel. The main challenges of this offloading system are how to compute the road path matching the performance requirements of a data transfer and how to configure the sequence of offloading spots involved in the transfer. We propose a scalable and adaptive centralized architecture built on software-defined networking that maximizes the utilization of the flow of vehicles connecting consecutive offloading spots. We simulate the performance of our system using real roads traffic counts for France. Results show that the centralized controlled offloading architecture can achieve an efficient and fair allocation of concurrent data transfers between major cities in France.

This work focuses on the design, analysis and evaluation of Dynamic Weighted Round Robin (DWRR) algorithms that can guarantee CPU service shares in clusters of servers. Our motivation comes from the need to provision multiple server CPUs in cloud-based data center environments. Using stochastic control theory we show that a class of DWRR policies provide the service differentiation objectives, without requiring any knowledge about the arrival and the service process statistics. The member policies provide the data center administrator with trade-off options, so that the communication and computation overhead of the policy can be adjusted. We further evaluate the proposed policies via simulations, using both synthetic and real traces obtained from a medium scale mobile computing application.

The US healthcare Affordable Care Act established the 30 day readmission protection program as one of the base lines of measuring quality of care at hospitals and post discharge. With reduced payment penalties for hospitals with excessive readmissions, hospitals have increased their focus on managin

In this paper, we study the problem of resource allocation in the setting of multitier data centers. Our main motivation and objective is to provide applications hosted in the data center with different service levels. In such centers, there are several mechanisms the designer can use to achieve such objectives. We restrict our attention to CPU time at the service tier as the resource; the objective we consider is service differentiation, expressed as allocating prespecified percentages of this resource to applications. Then, mechanisms at the designer's disposal to provide desired service differentiation include the triplet of load balancing through the switch fabric, enqueueing at a server and scheduling at a server. We focus on the enqueueing component of control mechanisms. We provide, through analysis and simulations “rules of thumb” for situations where simple enqueueing policies can provide service differentiation.

In recent years, service-oriented architectures (SOA) have emerged as the main solution for the integration of legacy systems with new technologies in the enterprise world. A service is usually governed by a client service contract (CSC) that specifies, among other requirements, the rate at which a service should be accessed, and limits it to no more than a number of service requests during an observation period. Several approaches, using both static and dynamic credit-based strategies, have been developed to enforce the rate specified in the CSC. Existing approaches have problems related to starvation, approximations used in calculations, and rapid credit consumption under certain conditions. In this paper, we propose and validate DoWSS, a doubly weighted algorithm for service traffic shaping. We show via simulation that DoWSS possesses several advantages: It eliminates the approximation issues, prevents starvation, and contains the rapid credit consumption issue in existing credit-based approaches.

In this paper, we conduct feasibility studies on the average delay space for Cloud computing, and we propose a heuristic method to control the vector of average delays, subject to predefined delay constraints. Our work is strongly motivated by the fact that delay control plays a critical role to improve Service Level Agreements (SLA) between users and Cloud service providers, which is necessary for empowering online business. Specifically, our main contributions are two-fold: First, the feasible regions of various routing algorithms for the system's dispatcher are investigated in depth. Second, a simple heuristic algorithm is designed, to move the average delay point along the feasible direction until achieving the delay constraints. Average delay is dependent on multiple factors such as job size, inter-arrival time, flow rate, and the dispatching rules of the system. Therefore, we vary their distribution, parameters and routing rules to examine how the feasible regions move or change. After establishing the feasible delay space, then by moving along the feasible directions, we show that a simple heuristic algorithm can achieve the delay constraints for a two queue system.

In Enterprise Data Centers (EDC), service providers are usually governed by Client Service Contracts (CSC) that specify, among other requirements, the rate at which a service should be accessed. The contract limits the rate to no more than a number of service requests during a given observation period. In two-tier setups, a cluster of Service-Oriented Networking (SON) Appliances form a pre-processing tier that accesses services in the service tier. SON Appliances locally shape the flow of requests to enforce the global rate defined in the CSC. Off-the-shelf SON Appliances present architectural limitations that prevent them from being used to efficiently perform traffic shaping in the presence of multiple service hosts. In this paper, besides identifying these limitations, we provide two contributions in this field. First, we introduce a SON Appliance architecture fit for multi-service traffic shaping. Second, we propose and validate an algorithm for multipoint-to-multipoint service traffic shaping in two-tier EDCs. We show via simulation that our approach solves the multipoint-to-multipoint service traffic shaping problem while pushing the system to its maximum capacity.

A large number of enterprise, web-based, distributed software applications are designed on Service Oriented Architecture (SOA) principles and hosted in large scale datacenters managed by cloud providers. Typically, Service Level Agreements (SLAs) are negotiated between the consumers of the cloud platform services and the cloud provider. In this work, we consider SLAs that involve percentiles of response times as part of the performance metrics; the SLAs stipulate that a penalty be charged to the cloud provider if the SLA targets are not met. The main motivation for considering such SLAs is their potential for price differentiation. We focus our analysis on the effects the penalty function has on the achieved response time percentiles. In particular, we analyze the effect of three commonly deployed choices (linear, exponential or step-wise functions) to relate the penalty charged and the achieved percentile. This analysis is NP-hard, so we employ a heuristic algorithm that is based on simulated annealing. Our results indicate that the linear penalty charging function is "best'' in the sense that it maximizes the achieved response time percentiles.

We consider geographically distributed data centers forming a collectively managed cloud computing system, hosting multiple Service Oriented Architecture (SOA) based context aware applications, each subject to Service Level Agreements (SLA). The Service Level Agreements for each context aware application require the response time of a certain percentile of the input requests to be less than a specified value for a profit to be charged by the cloud provider. We present a novel approach of data-oriented dynamic service-request allocation with gi-FIFO scheduling, in each of the geographically distributed data centers, to globally increase the profit charged by the cloud computing system. Our evaluation shows that our dynamic scheme far outperforms the commonly deployed static allocation with either First in First Out (FIFO) or Weighted Round Robin (WRR) scheduling.

In this work, we investigate the optimal key generation problem for a threshold security scheme in mobile ad hoc networks. The nodes in these networks are assumed to have limited power and critical security states. We model this problem using a closed discrete-time queuing system with L queues (one per node) randomly connected to K servers (where K nodes need to be contacted to construct a key). In this model, each queue length represents the available security-related credits of the corresponding node. We treat this problem as a resource allocation problem where the resources to be allocated are the limited power and security credits. We introduce the class of Most Balancing Credit Conserving (MBCC) policies and provide their mathematical characterization. We prove, using dynamic coupling arguments, that MBCC policies are optimal among all key generation policies; we define optimality as maximization, in a stochastic ordering sense, of a random variable representing the number of keys generated for a given initial system state.

We consider geographically distributed data centers forming a collectively managed cloud computing system hosting multiple applications, each subject to Service Level Agreements (SLA). The Service Level Agreements for each application require the response time of a certain percentile of the input requests to be less than a specified value, with the non-conforming requests being charged a penalty. We present a novel approach of heuristic-based request scheduling at each server, in each of the geographically distributed data centers, to globally minimize the penalty charged to the cloud computing system. We evaluate two variants of our heuristic-based approach, one based on the simulated annealing method of neighborhood searches and another based on gi-FIFO scheduling, which has been analytically proven to be the best schedule for percentile goals in a single machine, multi-class problem. We also compare our approaches with First In First Out (FIFO) and Weighted Round Robin (WRR) scheduling policies.

We investigate an optimal scheduling problem for a discrete-time system of two parallel queues with infinite capacity, sharing two symmetrical servers. This model can be used to study a variety of scheduling problems in wireless networks. At any time slot, a queue can be served by one or two connected servers; the queue-server connectivity is assumed to be random and modeled by a two-state Markov chain. The arrivals to each queue are assumed to be independent and identically distributed. A scheduled packet completes service successfully with a given probability. Otherwise, it has to be retransmitted in a later time slot. The optimal scheduling policy is defined as the server allocation policy that minimizes, in a stochastic ordering sense, the total number of packets in the system. We prove, using a dynamic coupling method, that a "Most Balancing" policy, a policy that attempts to balance the lengths of the two queues, is optimal. We also compare the performance of the optimal policy to that of a few other policies via simulations.

In this paper, we propose a novel autonomic service delivery platform for service-oriented network environments. The platform enables a self-optimizing infrastructure that balances the goals of maximizing the business value derived from processing service requests and the optimal utilization of IT resources. We believe that our proposal is the first of its kind to integrate several well-established theoretical and practical techniques from networking, microeconomics, and service-oriented computing to form a fully distributed service delivery platform. The principal component of the platform is a utility-based cooperative service routing protocol that disseminates congestion-based prices among intermediaries to enable the dynamic routing of service requests from consumers to providers. We provide the motivation for such a platform and formally present our proposed architecture. We discuss the underlying analytical framework for the service routing protocol, as well as key methodologies which together provide a robust framework for our service delivery platform that is applicable to the next-generation of middleware and telecommunications architectures. We discuss issues regarding the fairness of service rate allocations, as well as the use of nonconcave utility functions in the service routing protocol. We also provide numerical results that demonstrate the ability of the platform to provide optimal routing of service requests.

We investigate an optimal scheduling problem in a discrete-time system of L parallel queues that are served by K identical servers. This model has been widely used in studies of emerging 3G/4G wireless systems. We introduce the class of Most Balancing (MB) policies and provide their mathematical characterization. We prove that MB policies are optimal among all work conserving policies; we define optimality as minimization, in stochastic ordering sense, of a range of cost functions of the queue lengths, including the process of total number of packets in the system. We use dynamic coupling arguments for our proof. We also introduce the Least Connected Server First/Longest Connected Queue (LCSF/LCQ) policy as an approximate implementation of MB policies. We conduct a simulation study to compare the performance of several work conserving policies to that of the optimal one. In the simulations we relax some of the mathematical assumptions we required for the analytical proofs. The simulation results show that: (a) in all cases, MB policies outperform the other policies, (b) randomized policies perform fairly close to the optimal one, and, (c) the performance advantage of the optimal policy over the other work conserving policies increases as the channel connectivity decreases.

Service providers within an enterprise network are often governed by client service contracts (CSC) that specify, among other constraints, the rate at which a particular service instance may be accessed. The service can be accessed via multiple points (typically middleware appliances) in a proxy tier configuration. The CSC and thus the rate specified have to be collectively respected by all the middleware appliances. The appliances locally shape the service requests to respect the global contract. We investigate the case where the CSC limits the rate to a service to X requests with an enforcement/observation interval of T seconds across all the middleware appliances. In this paper, we extend, implement, and investigate the Credit-based Algorithm for Service Traffic Shaping (CASTS) in a production level enterprise network setting. CASTS is a decentralized algorithm for service traffic shaping in middleware appliances. We show that CASTS respects the CSC and improves the responsiveness of the system to the variations of the input rate and leads to larger service capacity when compared to the traditional static allocation approach.

In this paper, we propose a novel autonomic service delivery platform for service-oriented network environments. The platform enables a self-optimizing infrastructure that balances the goals of maximizing the business value derived from processing service requests and the optimal utilization of IT resources. We believe that our proposal is the first of its kind to integrate several well-established theoretical and practical techniques from networking, microeconomics, and service-oriented computing to form a fully-distributed service delivery platform. The principal component of the platform is a utility-based cooperative service routing protocol that disseminates congestion-based prices amongst intermediaries to enable the dynamic routing of service requests from consumers to providers. We provide the motivation for such a platform and formally present our proposed architecture. We discuss the underlying analytical framework for the service routing protocol, as well as key methodologies which together provide a robust framework for our service delivery platform that is applicable to the next-generation of middleware and telecommunications architectures.

The IEEE 802.17 resilient packet ring standard is a medium access control (MAC) protocol for metro-area ring networks. RPR supports spatial reuse which allows multiple nodes to send traffic at the same time. RPR employs a distributed fairness algorithm to maintain fairness among all nodes in accessing the ring. The performance of the RPR fairness algorithm depends on a number of configurable parameters. In this paper, we provide some recommendations for practitioners on how to configure the fairness algorithm in RPR to achieve a high performance while meeting fairness constraints throughout the ring. The performance metric is the achieved throughput which is translated into revenue for a service provider. We develop criteria which are used to set the parameters. We also study the effect of different parameters on the performance of the fairness algorithm through simulation results.

Ultra-wideband wireless (UWB) can provide the physical layer for high capacity personal area networks. When UWB is used for communication between many nodes, relatively long acquisition times are needed when dropping and re-establishing wireless links between the nodes. This paper describes the development and use of mathematical and simulation models to investigate the impact on average packet delay of dropping and reacquiring links between nodes to directly transmit packets versus simply forwarding packets through intervening nodes without breaking the established wireless links. The work presented here assumes that no specific MAC layer protocol, such as WiMedia UWB MAC, is operating. The paper describes the models, explains the selection of modeling parameters used, compares the average packet delay for a network of three simple UWB nodes, and explains the use of these results for network design engineers.

In order to reduce the amount of radio communications, wireless sensor networks may perform data aggregation, where relaying nodes perform in-network processing. Guaranteeing security in aggregation schemes is particularly challenging because node compromises in such a scenario are doubly problematic, both in terms data confidentiality (eavesdropping) and availability (denial of service). Indeed, by compromising an aggregator node the attacker would endanger all of the readings that are part of the aggregate the node is in charge of.

Self-Organized Networks (SONs) are a general description of autonomous networks without infrastructure, of which Ad Hoc, Sensor and Mesh networks are special cases. We had previously proposed a novel clustering architecture for SONs, named Taroko, that utilizes a fixed description of cluster routing tables to cope with SON's characteristics. Taroko uses trellis graphs to provide addressing/locating and routing capabilities for the SON, while providing a built-in multi-path routing scheme and redundancy in the addressing space. This paper focuses on comparing Taroko to AODV and OLSR in terms of both control and data plane metrics. The simulation results show that Taroko performs well, especially in the presence of large numbers of sources.

As the size of mobile self-organizing networks increases, the efficiency of location services must increase as well so that addressing/routing scalability does not become an issue. In this paper, we propose a novel architecture, called Twins, tailored for self-organizing networks. Twins architecture involves addressing and locating nodes in large networks, forwarding packets between them, and managing in the presence of mobility/topology changes. Twins defines a logical multidimensional space for addressing and forwarding, while location service and management operations make use of a one-dimensional space. To improve scalability and performance, forwarding is hop-by-hop with greedy next-hop choice and the location service uses a rendezvous paradigm to distribute information among nodes. In this paper, we describe the Twins architecture and present a performance evaluation to assess scalability, fairness in the overhead distribution among nodes, and routing robustness.

Self organized networks (SONs) are a general description of autonomous networks, of which ad hoc and sensor networks are special cases. Lack of infrastructure, limited resources and dynamic nature of nodes are some of the main characteristics of such networks. We had previously proposed a novel clustering architecture for SONs that utilizes a fixed description of cluster routing tables. The architecture uses trellis graphs, a concept borrowed from the domain of source coding, to provide addressing/locating and routing capabilities for the SON. The choice of a trellis graph (and its parameters) to represent a particular SON is not unique; moreover, as expected, it introduces overhead. In this paper we focus our study on a thorough examination of the effects of this choice on the control and data plane operations of the network. In a nutshell, we show that increasing the trellis size reduces control plane overhead significantly; on the other hand, increasing the trellis size has a mixed effect on data plane performance

The need for efficient location mechanisms is an important issue in scalable self-organizing networks. Existing solutions are inherently dependent on the spatial distribution of nodes in the topology. This leads to limitations that go against the principles of self-organization. In this paper, we propose Twins, an easily-managed location service for self-organizing networks. Twins defines a logical multidimensional space that is a strict mathematical representation of the network geographic space. This representation is obtained through Hilbert space-filling curves. The geographic space is used for addressing and routing, while localization is based on the curve. Control messages are routed based on the logical structure while data packets are routed in a hop-by-hop basis with greedy next-hop choice. In this paper, we evaluate the Twins management operations in terms of fairness of space sharing and logical/geographic distances between nodes and their location servers. Our results show that Twins assures a fair distribution of control overhead and scales well with the number of nodes.

Ultra-wideband wireless (UWB) may provide the physical layer for high capacity personal area networks in the future. Certain characteristics of the wireless links possible using this technology give rise to properties not seen with other wireless technologies. Two such properties are long synchronization times for link establishment and the ability to change individual link capacities by choosing PN codes of different lengths. The paper formulates a novel routing problem in UWB; in particular, we investigate the impact of UWB physical layer characteristics on average network transit delay for a UWB network with a ring topology. The paper derives an expression for average network transit delay as a function of the capacity between each pair of nodes in the network. Each node is assumed to have one input and one output link resulting in a ring network topology, which guarantees access to every node. An aggregate network capacity bound for all links is assumed. A Lagrangian function is defined to obtain the optimum link capacities in order to minimize the average network delays and the resulting formula for delay is explained.

This paper reports on a teaching and research SLA test-bed that we have constructed using specially developed soft DiffServ routing nodes operating in a Linux environment. The test-bed, and the associated tools, are intended for various levels of study of SLA translation and mapping algorithms. It is instrumented to provide considerable insight into the DiffServ behavior. The software is more modular, flexible and easier to configure than the "standard" Linux DiffServ offerings. This paper presents the architecture of our system, and reports on the proof-of-concept experiments that show that it can be used to implement a general Services Level Agreement (SLA) solution and study related issues. Initial empirical studies involve implementation of some of the quality of service (QoS) related IETF drafts and RFCs in a five-node test-bed, including an implementation and empirical evaluation of expedited forwarding (EF) PHB, assured forwarding (AF) PHB, virtual wire (VW) PDB, and of assured forwarding PDB.

Earliest deadline first scheduling with per-node traffic shaping (RC-EDF) has the largest schedulable region among all practical policies known today and has been considered a good solution for providing end-to-end packet delay bounds. In order to harness the traffic burstiness inside a network to satisfy the schedulability condition of EDF, per-node traffic shaping has been believed to be necessary. However, shaping introduces artificial packet delays. We show that by deadline assignments at each node that are strict time-shifting of the source packet arrival times, the functionality of shaping can be implicitly realized; the resulting schedulable region of the new scheduling policy is as large as that of RC-EDF. We name the new policy deadline-curve based EDF (DC-EDF). Not only working in a natural work-conserving way, when the global schedulability condition fails DC-EDF will also work in a "best-effort" way to allow packets excessively delayed at previous nodes to catch up and meet the end-to-end delay bounds. Therefore, DC-EDF is likely to provide "tight" statistical delay bounds. We also prove that a known EDF policy without traffic shaping also has a schedulable region as large as that of RC-EDF.

We propose a burstiness-class-based queuing (B-CBQ) scheme where connections are allocated to their classes based on a "burstiness" parameter derived from the leaky bucket source specifications. We derive delay bounds for burstiness-classes on per-switch and end-to-end basis. An optimization problem is defined and solved to find the optimal number of classes in order to minimize the delay bound through a switch for a connection admitted to the lowest burstiness-class. Finally, some simulation results are provided to illustrate the behavior of a B-CBQ switch.

Shared-buffer ATM switches can have severe cell loss under asymmetrical or heavy loading conditions, which makes buffer management essential. In this paper, we study the shared-buffer system under the class of all work-conserving pushout policies and derive the properties of the optimal policy, which gives the least-average expected total cell loss probability. In a 2/spl times/2 system with independent identically distributed Bernoulli arrivals, we show that the optimal policy can be characterized by a single threshold. In the case of correlated arrivals, modeled by a discrete batch Markovian arrival process, the optimal policy has multiple thresholds, one for each phase of the arrival process. For the N/spl times/N shared buffer ATM switch, we are unable to prove optimality of any policy, but we study the system via simulations. We provide a dynamic buffer management policy and compare its performance with that of static threshold-type policies.

We study the NP-hard delay-constrained least-cost path problem, and propose a simple, distributed heuristic solution: the delay-constrained unicast routing (DCUR) algorithm. The DCUR requires limited network state information to be kept at each node: a cost vector and a delay vector. We prove the DCUR's correctness by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. The worst case message complexity of the DCUR is O(|V|/sup 3/) messages, where |V| is the number of nodes. However simulation results show that, on average, the DCUR requires much fewer messages. Therefore, the DCUR scales well to large networks. We also use simulation to compare the DCUR to the optimal algorithm, and to the least-delay path algorithm. Our results show that the DCUR's path costs are within 10% from those of the optimal solution.

We formulate the problem of constructing broadcast trees for real-time traffic with delay constraints in networks with asymmetric link loads as a delay-constrained minimum spanning tree (DCMST) problem in directed networks. Then, we prove that this problem is NP-complete, and we propose an efficient heuristic to solve the problem based on Prim's algorithm for the unconstrained minimum spanning tree problem. Simulation results under realistic networking conditions show that our heuristic performance is close to optimal. Delay-constrained minimum Steiner tree heuristics can be used to solve the DCMST problem. Simulation results indicate that the fastest delay-constrained minimum Steiner tree heuristic, DMCT is not as efficient as the heuristic we propose, while the most efficient delay-constrained minimum Steiner tree heuristic, BSMA, is much slower than our proposed heuristic and does not construct delay-constrained broadcast trees of lower cost.

Multicast (MC) routing algorithms capable of satisfying the quality of service (QoS) requirements of real-time applications will be essential for future high-speed networks. We compare the performance of all of the important MC routing algorithms when applied to networks with asymmetric link loads. Each algorithm is judged based on the quality of the MC trees it generates and its efficiency in managing the network resources. Simulation results over random networks show that unconstrained algorithms are not capable of fulfilling the QoS requirements of real-time applications in wide-area networks. Simulations also reveal that one of the unconstrained algorithms, reverse path multicasting (RPM), is quite inefficient when applied to asymmetric networks. We study how combining routing with resource reservation and admission control improves the RPM's efficiency in managing the network resources. The performance of one semiconstrained heuristic, MSC, three constrained Steiner tree (CST) heuristics, Kompella, Pasquale, and Polyzos (1992), constrained adaptive ordering (CAO), and bounded shortest multicast algorithm (BSMA), and one constrained shortest path tree (CSPT) heuristic, the constrained Dijkstra heuristic (CDKS) are also studied. Simulations show that the semiconstrained and constrained heuristics are capable of successfully constructing MC trees which satisfy the QoS requirements of real-time traffic. However, the cost performance of the heuristics varies. The BSMA's MC trees are lower in cost than all other constrained heuristics. Finally, we compare the execution times of all algorithms, unconstrained, semiconstrained, and constrained.

We characterize the time-dependent behavior of a typical queuing system that arise in ATM networks under the presence of overloads. The transient queue length distribution and transient cell loss probability are obtained numerically and transient characteristics such as maximum overshoot and relaxation time are used to quantify the effects of congestion periods. A new measure, expected excess loss in overload (EELO) is defined to quantify the effects of overload when compared with the system behavior in the steady-state regime. The basic modeling technology that we use is an extended form of stochastic Petri nets and a software tool called the stochastic Petri net package (SPNP).

A parallel router architecture for processing network-layer protocols at FDDI (fiber distributed data interface) speeds is proposed. At high speeds the computing power of existing routers becomes the performance bottleneck (for processing small frame sizes). Hence, a completely different approach is required in designing a router. The opportunities of parallel processing in a network protocol are investigated. Several levels of parallel processing are considered, and an architecture for the most practical and feasible approach is proposed. The concept of a snoopy header cache is introduced. Algorithms for reducing the mean processing delay by balancing the load among the processors are discussed. The performance of the router is evaluated by analytic methods and is compared with simulation results. The results from both the analytic model and the simulator reinforce the choice of a header cache in a multiprocessor environment.>

The authors consider the integration problem of LAN/MAN traffic to WAN by ATM/SONET multiplexing. They propose separate buffers for voice and data to efficiently control the throughput of each traffic type. Transmission bandwidth is dynamically and adaptively shared between voice and data to guarantee grade of service (GOS) requirements for each traffic type. The authors propose two algorithms for access policies; the (N/sub 1/,N/sub 2/) scheme and its adaptive variation. Their algorithms do not require the knowledge of arrival statistics. In the fact scheme, they can play with the tradeoff between delay and cell loss probability of each traffic type. In the second scheme, for most of the time and under normal network conditions, voice traffic has higher priority. Data traffic has higher priority when the number of data cells queued reaches a certain threshold. They show how the network performance is affected by several system parameters.>