In this work, we focus on resolving the intrinsic drawbacks presented in the current LTE (Long-Term Evolution) D2D (Device-to-Device) communications protocol for Out-of-Coverage (OOC) scenarios in better serving First Responders (FRs) by proposing three novel compatible priority-based preemptive scheduling schemes. In these ways, effective Quality-of-Service (QoS), Priority and Preemption (QPP) capabilities can be provided to FRs with very limited amount of overhead being introduced. We conduct extensive simulations with various group settings to show that the schemes will indeed significantly enhance some of the vital performance metrics. Our results prove that D2D communications are worth further investigations for envisioned near future integrated Public Safety Networks.

The Third Generation Partnership Project (3GPP) defines various pre-configured channel parameters for the Long-Term Evolution (LTE) Device-to-Device (D2D) communications with Physical Sidelink (SL) Channels. In this paper, we investigate the impacts of channel parameter settings on the performance of content deliveries for Public Safety Network (PSN) applications in Out-of-Coverage (OOC) scenario. We first measure the reliability of the SL channels under various sets of channel parameters using Monte Carlo simulations. Then, for a given PSN application, the acquired reliability results are utilized to help determining the amount of delay that is to be introduced to the system, such that the throughput requirement for the application is assured during the transmissions. To the best of our knowledge, this is the first LTE D2D work that focuses on OOC mission-critical communications performance in group traffic settings. Our results are valuable to both network operators, for using them as references in selecting a best set of channel parameters, and to future studies on more complex transmission patterns and network scenarios using D2D communications in PSNs.

Public safety incidents typically involve a significant amount of group traffic and have a stringent requirement of connection reliability. Hence multicast could potentially improve network and user performance significantly, which triggered our study on Long-Term Evolution (LTE) Multicast Broadcast Single Frequency Network (MBSFN). In this paper, we first derive a realistic MBSFN Signal-to-Interference-plus-Noise Ratio (SINR) analytical model, with multiple antennas, multipath channel, and equalizer considered. Then through comprehensive system level simulations, we compare MBSFN and unicast in terms of resource efficiency v.s. throughput, as well as outage probability. We also study the impacts of MBSFN size and quantify the MBSFN SINR improvement due to diversity combining and interference reduction, respectively.

Physical-Layer (PHY) based secrecy has inherent advantages for generating symmetric keys in communication security, due to the reciprocity of the wireless communications channel. However, since noises are independently acquired and the communication channel is of half-duplex, the bit streams independently obtained from the PHY-layer by the two sides of a communications channel are usually not identical. This imperfection prevents the direct application of the PHY-layer secrecy for generating symmetric keys. In this paper, we propose a novel algorithm for dynamic symmetric key generation by utilizing the Golay code structure. The proposed algorithm achieves as much as 100% symmetric key generation rate when compared to the naive approach at a small extra computational cost. The performance of the proposed algorithm is evaluated using experimentally observed distribution of PHY-layer generated bit mismatches with MATLAB ITU channel models as the basis of a theoretical analysis. Our design is shown to provide a good trade-off between symmetric key generation rate and computational complexity without additional information leakage.

Public safety incidents typically involve significant amount of group traffic. This paper initializes our study in exploring the potential spectrum savings and improvement in first responders experience by using Multicast Broadcast Single Frequency Network (MBSFN) to serve group traffic among first responders. Towards this goal, this paper proposes a comprehensive methodology that closely follows The 3rd Generation Partnership Project (3GPP) specifications and considers unicast multiple-input multiple-output (MIMO) and MBSFN without MIMO. High fidelity Block Error Rate (BLER) curves for both MBSFN and unicast are generated, and Signal-to-noise ratio (SNR) points to switch Channel Quality Indicators (CQIs) are extracted and analyzed. Several simulation scenarios have been designed and the empirical results are analyzed.

In this paper we address the challenge of multiuser scheduling in the downlink of Long Term Evolution (LTE) by bringing innovation in the concept of proportional fairness. We plug geometric average into the selection criterion of User Equipments (UEs) as opposed to widely used arithmetic average. We prove that the geometric average throughput converges to the solution of an ordinary differential equation, a similar result shown in the convergence of arithmetic average based Proportional Fair Scheduling (PFS). Extensive simulation results show that geometric average of UEs throughputs converge faster than arithmetic mean. This feature enables throughput increase in the cell while guaranteeing better fairness and Quality of Service (QoS) and imposing low Block Error Ratio (BLER). The superiority of the proposed algorithm is demonstrated by comparing the performance of the proposed scheduler with well- known standard schedulers under different simulation environments.

In dynamic cognitive radio networks (CRNs), unlicensed secondary users (SUs) opportunistically transmit in the spectrum holes left available by licensed primary users (PUs), without knowing in advance their presence on the channels. For SUs with multi-channel transmission capability, the process of selecting the channels to use by sequentially sensing the presence of PUs and evaluating the channel gains, incurs performance tradeoffs, power constraints, and expensive computations. In this paper, the channel selection problem for SU throughput maximization, limited by the power available at SUs, is formulated in a CRN with both heterogeneous PU-traffic and channel conditions. Our proposed optimal algorithm only requires linear-time and quadratic-space online complexities and cubic offline complexities, with the latter needed when CRN characteristics significantly change. This represents a significant improvement over existing algorithms. Our solution achieves throughput and delays close to maximum, not compromising accuracy for efficiency as approximate channel selection algorithms need to do.

Cognitive Radio Network (CRN) technology allows secondary users (SUs) to transmit data exploiting the wireless resources not utilized by licensed primary users (PUs). Channel exploration by SUs for finding transmission opportunities incurs non-negligible costs and is a key challenge in successful operation of CRN. In this paper, we investigate the joint effect of channel exploration order and stopping rule for channel selection with the goal of maximizing SUs' throughput. The main contribution of this paper is the near optimal exploration order and optimal stopping rule, paired with a new and more general characterization of PUs' traffic configurations in CRN. The proposed algorithm uses an analytical model that incorporates channel and PUs' activity history to make the best decision at each decision point, according to the current SUs' exploration results. The simulation study shows that the proposed algorithm significantly improves the SUs' throughput over the existing methods. The proposed optimal stopping algorithm runs in polynomial-time, which is another major contribution of this paper, since it is a significant complexity reduction from the typical exponential order of backward induction algorithms.

In Cognitive Radio Networks (CRNs) secondary users (SUs) are allowed to transmit data exploiting the wireless resources (i.e., channels) not utilized by licensed primary users (PUs). Efficient resource discovery for finding available channels is a key aspect for successful SUs' operation. In this paper we investigate and propose different algorithms to discover the best CRN channels that, exploited for transmission jointly as aggregate OFDM carriers, will maximize SUs' throughput. By using CRN channels statistics such as channel availability and link quality, together with current channel discovery results, SUs attempt to make the best choice at each decision point. This is choosing to continue the discovery process or stop and transmit using the aggregated resources found available so far. All the proposed algorithms run in polynomial time, which is a significant complexity reduction from the typical exponential order of optimal stopping rule algorithms. The simulation study confirms the validity of our algorithms in different CRN scenarios, comparing their throughput performance with the theoretically best achievable results.

Cognitive Radio Networks (CRNs) aim to maximize the utilization of existing wireless channels by allowing secondary users (SUs) to transmit when licensed primary users (PUs) are not using the same channels. An SU monitors the CRN channels, sensing PU presence to avoid interference and estimating the link quality before transmitting. It stops when one or more available channels with satisfactory link quality are found. Algorithms for making the optimal decision regarding when to stop exploring the channels and start transmitting are expensive in terms of time and space, which are both scarce in hardware-constrained SUs, such as mobile devices. In this paper, we propose a low-complexity algorithm, which utilizes link quality and PU-activity statistics of the CRN channels to pre-compute a set of decision thresholds that will aid the channel exploration phase in maximizing SU-throughput. Our algorithm takes quadratic time and space for offline computations and linear time and space for online processing, which makes it very suitable for space and energy constrained mobile SUs. Our extensive simulation study and analytical model matching the simulation results demonstrate our solution's validity by showing the closeness of throughput and delay performances with the optimum solution as well as solutions by the well-known backward induction method, which often runs in exponential time for offline computations.

Large amount of electronic clinical data encompasses important information in free text format. To be able to help guide medical decision-making, text needs to be efficiently processed and coded. In this research, we investigate techniques to improve classification of Emergency Department computed tomography (CT) reports. The proposed system uses Natural Language Processing (NLP) to generate structured output from the reports and then machine learning techniques to code for the presence of clinically important injuries for traumatic orbital fracture victims. Topic modeling of the corpora is also utilized as an alternative representation of the patient reports. Our results show that both NLP and topic modeling improves raw text classification results. Within NLP features, filtering the codes using modifiers produces the best performance. Topic modeling shows mixed results. Topic vectors provide good dimensionality reduction and get comparable classification results as with NLP features. However, binary topic classification fails to improve upon raw text classification.

Location-based services (LBS) have become an immensely valuable source of real-time information and guidance. Nonetheless, the potential abuse of users' sensitive personal data by an LBS server is evolving into a serious concern. Privacy concerns in LBS exist on two fronts: location privacy and query privacy. In this paper we investigate issues related to query privacy. In particular, we aim to prevent the LBS server from correlating the service attribute, e.g., bar/tavern, in the query to the user's real-world identity. Location obfuscation using spatial generalization aided by anonymization of LBS queries is a conventional means to this end. However, effectiveness of this technique would abate in continuous LBS scenarios, i.e., where users are moving and recurrently requesting for LBS. In this paper, we present a novel query-perturbation-based scheme that protects query privacy in continuous LBS even when user-identities are revealed. Unlike most exiting works, our scheme does not require the presence of a trusted third party.

Achieving accurate and efficient fault localization in large transparent all-optical networks (TONs) is an important and challenging problem due to unique fault-propagation, time constraints, and scalability requirements. In this paper, we introduce a novel technique for optimizing the speed of fault-localization through the selection of an active set of monitors for centralized and hierarchically-distributed management. The proposed technique is capable of providing multiple levels of fault-localization-granularity, from individual discrete optical components to the entire monitoring domains. We formulate and prove the NP-completeness of the optimal monitor activation problem and present its Integer Linear Program (ILP) formulation. Furthermore, we propose a novel heuristic whose solution quality is verified by comparing it with an ILP. Extensive simulation results provide supporting analysis and comparisons of achievable alarm-vector reduction, localization coverage, and time complexity, for flat and hierarchically distributed monitoring approaches. The impact of network connectivity on fault localization complexity in randomly generated topologies is also studied. Results demonstrate the effectiveness of the proposed technique in efficient and scalable monitoring of transparent optical networks.

This paper considers the channel-assignment and scheduling in wireless mesh networks that employ multiple radios and multiple channels. In contrast to the various algorithms available in the literature, we explicitly model the delay overhead that is incurred during channel switching, and use that delay in the design of algorithms. We prove that the well known Greedy Maximal Scheduling (GMS) algorithm does not have any provable efficiency ratio when the switching overhead is considered. We present a centralized algorithm (CGSSO), and a dynamic algorithm (DMSSO), both of which consider switching overhead. Simulation results show that the proposed algorithms significantly outperform other algorithms in packet throughput and average packet delay metrics. Results also show that the improvements in performance become more pronounced as the switching delay increases.

In this paper, we consider the important aspect of quality of service (QoS) in wireless mesh networks, focusing on packet delays and packet drops. We observe that the options of solely focusing on throughput, and of only depending on the QoS type characterization by the application level protocol is not sufficient. We propose the use of multiple queues to hold the packets based on their QoS requirement (not necessarily corresponding to the QoS application types). We suggest the technique of reinforcement learning (RL) for the important step of assigning packet to one of the queues, and present an implementation using the TD(0) algorithm. We present various simulation results comparing our algorithm to other known algorithms and frameworks. Our results indicate that our RL-based algorithm is significantly better than previously known results in packet drop ratio.

We develop a rate adaptation scheme for 802.11 networks termed SRC that is based on a novel combination of sequential hypothesis testing and short-term loss ratios. The underlying design of SRC represents a fundamental departure from previous rate adjustment strategies that employ fixed-size observation windows and seemingly-intuitive rate increase guidelines. Through extensive simulation results, SRC is shown to be robust to dynamic characteristics of the wireless channel and to significantly increase network throughput over existing mainstream rate adaptation solutions. SRC does not require any type of specialized hardware or modifications to the existing 802.11 standard.

User-generated content (UGC) also known as user- created content (UCC) refers to various kinds of media contents that are produced by end users. A recent trend in the use of the Internet exhibits that data traffic from UGC is rapidly growing with the potential to create a huge amount of uplink traffic for wireless operators. As the reality of UGC's scope and power is becoming crystalized, modeling and analysis of uplink traffic has just begun to receive growing attention in the wireless community. Consequently, we have also analyzed live uplink traffic traces obtained by monitoring 3G networks of a mobile data service provider (SK Telecom in Korea). Our statistical analysis shows the self-similarity in this traffic trace. In order to evaluate the impact of this characteristics on mobile data networks, we use the WiMAX module available in OPNET software. Our trace-driven simulation results indicate burstiness in the aggregated traffic received at a base station (BS) as well as in the traffic generated at each subscriber station (SS). The impact of the data burst at SSs is shown to be negligible when the overall traffic load is relatively small but become significant when a large volume of delay-sensitive traffic is generated in many SSs even if the overall network load is less than the network capacity.

Increasing demand for high data-rate multimedia real time services has led to the use of asynchronous time shared channels in the forward link for real-time services in 3G wireless networks, such as HSDPA, EV-DO and EV-DV. While network service providers would like to impose operational policies on the packet schedulers based on QoS requirements by real-time services to maximize profit, existing schedulers are not capable to deal with such challenge due to time varying channel conditions and constraints on the total forward link transmit power. In this paper, we consider the problem of scheduling users on the forward link in a multiuser system where multiple users can be scheduled during each interval. We introduce a delay aware policy driven scheduling algorithm SPS-Delay (Strict Policy Scheduling for Delay) to support differentiated QoS requirements in the form of tolerable latency specified by the user applications. We developed an HSDPA system in OPNET, and implemented our scheduling algorithm along with other well- known algorithms. Our simulations show that SPS-Delay reduces packet drop rate by as much as 80% and increases the number of satisfied users by as much as 32% when compared to PF.

High-Speed Downlink Packet Access (HSDPA) uses a shared forward link packet data channel that can achieve peak data rates up to 14.4 Mbps. The newly introduced features that are key to reaching such high rates are link adaptation, Hybrid ARQ (HARQ) and fast scheduling. The decision to admit new users is still taken by the Radio Network Controller (RNC); however, the scheduling role has been moved to the base station (Node-B) for fast adaptability. Although in high speed cellular networks, opportunistic scheduling can exploit multi-user diversity to maximize throughput, with the growing need for strict QoS guarantees for services such as streaming, gaming, and VoIP, a balance should be struck between maximizing throughput and providing user satisfaction. Service operators can enforce their own policies in providing user satisfaction. In this paper, we consider a QoS-aware policy driven scheduling algorithm and its interaction with the admission control mechanism at the RNC. We developed a dynamic HSDPA network simulator in OPNET with link adaptation, HARQ, fast scheduling and quality based admission control. Our simulations show that even with the presence of an admission controller at RNC, the well-known proportional fairness (PF) algorithm dismally fails to provide user satisfaction for streaming services, whereas our Strict Policy Scheduling (SPS) algorithm substantially increases user satisfaction as intended by the admission controller while providing a significant cell capacity gain.

This paper considers the problem of maximizing the system throughput in IEEE 802.16 broadband access networks with mesh topology, and the following results are presented. We consider a linear chain network and discuss its applicability for providing cost effective solutions in sparsely populated areas, such as interstate highways and rural communities. We provide an optimal scheduling algorithm and establish an analytical result on the length of the schedule for linear chain networks. We also consider the problem of routing and packet scheduling in general topology, and show its NP-completeness. Based on our optimal algorithm for linear networks, we propose algorithms that find routes and schedules of packet transmissions in general mesh topologies. The performance of our proposed algorithms is analyzed using the NS-2 simulator. The results show that the proposed algorithms perform significantly better than other existing algorithms.

Rapid fault identification and localization in optical networks are crucial due to high data rates. These problems are more challenging than in traditional electronic networks because of optical transparency. In a transparent optical network which does not regenerate optical signals, a fault may propagate to various parts of the network from the origin, and multiple alarms can be generated for a single failure. In order to reduce the number of redundant alarms, simplify fault localization, and reduce the fault localization time, the number and location of fault monitors that are turned on should be optimized for a given network. In this paper, we formulate a problem on the optimal activation of network monitoring devices and propose a solution approach. First, we provide a brief summary of available physical-layer monitoring devices, and then present a scheme for optimal monitor activation. We show the NP-completeness of the problem and present a mixed-integer-linear-program (MILP) formulation of it. We also present a heuristic, whose performance is evaluated through comparisons with the solutions to the MILP, as well as a naive monitor activation approach.

To support high data rates, CDMA lx Ev- DO utilizes TDMA technology on the downlink allowing a single receiver per time slot. Accordingly, a scheduling algorithm is necessary to determine which user receives data in a given time slot. Typically, schedulers consider efficiency (increasing network throughput) or fairness (fair allocation of resources among users) as the basis for scheduling. To realize a reasonable tradeoff between efficiency and fairness, opportunistic schedulers have been proposed that take advantage of instantaneous improvements in users radio conditions by serving them at higher rates. However, given the increasing demand to support user QoS requirements, a QoS-aware scheduler may need to serve users even at times of inadequate radio conditions. In this paper, we propose a QoS-aware packet scheduling algorithm that takes into account policy rules that govern the relationships between different user QoS classes. Our scheduler uses marginal utility functions defined to embody the given rules when selecting users to be served on the downlink. Our scheduling algorithm is implemented in the OPNET module of the CDMA lx Ev-DO system that we have developed, and its performance is compared to other scheduling algorithms. The simulation results show that our scheduler performs well ensuring the policy rules are followed, meeting users' QoS requirements, and providing fairness among users within the same QoS class.

Ad hoc networks employ a decentralized unstructured networking model that relies on node cooperation for key network functionalities such as routing and medium access. In this paper, we develop and evaluate a model based on the sequential probability ratio test to characterize how nodes can differentiate between routes that include misbehaving nodes (infected routes) and routes that do not. An advantage of the model is that the number of observations required to evaluate a route need not be determined in advance.

Increasing demand for high data-rate multimedia services has led to the emergence of high-speed data transfer features such as high-speed downlink packet access (HSDPA) for WCDMA networks. The role of the MAC-hs scheduler is vital in HSDPA in improving overall system performance. Using opportunistic scheduling to exploit multi-user diversity for efficient transmission of best effort services or considering user fairness constraints has been the main focus of most scheduling algorithms. However the need for strict QoS support for services such as streaming, gaming, and VoIP is growing. Service operators can enforce their own policies in meeting these QoS requirements. In this paper we introduce two QoS-aware policy driven scheduling algorithms. We developed an HSDPA system in OPNET, and implemented our scheduling algorithms along with other well-known algorithms. OPNET simulations show that unlike other schedulers, our strict and loose policy scheduling (SPS and LPS) algorithms comply with the policy constraints if allowed by radio conditions and cell capacity.

Sensors are envisioned to be at the center of distributed collaborative computing services involving time-critical decision support. Sensors are small devices with limited communication and computational capabilities that collect data on their neighboring physical world and send the data periodically to server machines. Sensors form a collaborative network with these servers, where the sensors gather information and the servers perform various operations (e.g. filter, aggregate, join etc) on the information streams in real-time according to predefined queries or rules. Sensor data streams are continuous, un-ending and have highly volatile characteristics. As a result, traditional database systems are inappropriate for handling queries for sensor streams, and several stream data management systems have been proposed in the literature. In this paper we focus on a special type of query, namely join queries, which is the most expensive query operator. Here, we address the problem of finding an optimal join tree that maximizes throughput for sliding window based multi-join queries over continuous sensor data streams. We present a polynomial time algorithm Fodp and three variants of Fodp. Our experiments in ARES show that for almost all instances, trees from Fodp and its variants perform close to the optimal trees from our exponential time algorithm OptDP (Gomes, 2006), and significantly better than existing XJoin based heuristic algorithms

As the commercial success of the IEEE 802.11 protocol has made wireless infrastructure widely deployed, user organizations are increasingly concerned about the new vulnerabilities to their networks. While various security issues have been extensively studied, the threats posed by denial-of-service (DoS) attacks have not been fully exploited. In this paper, we consider DoS attacks posed by cheating on the backoff rules in the IEEE 802.11 DCF protocol and propose a scheme detecting such adversaries. Our scheme is based on the sequential hypothesis testing. We first develop analytical models for packet interarrival time distribution from each station in the network where multiple cheating stations co-exist. Using the characterization of this probability distribution, we develop an algorithm to detect cheating stations based on the throughout degradations observed at normal stations. Our simulation results show that the proposed algorithm only requires very small number of observations of packets with very small value (i.e., less than 0.1%) of false positive and false negative decisions. That is, our proposed algorithm performs significantly fast and also accurately.

Sensors are becoming ubiquitous, and increasingly integrated with our lives. Sensors usually send sampled data periodically using wireless connections to server machines. The servers perform various operations (e.g. filter, aggregate, join etc) on this data in real-time according to predefined queries or rules. In this paper, we address the problem of finding an optimal join tree that maximizes throughput for sliding window based multi-join queries over continuous sensor data streams. We develop a dynamic programming algorithm OptDP, that produces an optimal tree but runs in an exponential time in the number of input streams. We then present a polynomial time greedy algorithm XGreedyJoin. Our experiments in ARES show that for almost all instances, trees from XGreedyJoin perform close to the optimal trees from OptDP, and significantly better than existing XJoin based heuristic algorithms

This paper studies the effects of the sub-carrier grouping on the scheduling problem in a wireless network with multiple carriers. In particular, the authors consider the trade-offs between the size of the sub-carrier groups and the link throughput for various sub-carrier grouping models, with each corresponding to a different level of CSI tracking and system design complexity. The paper assumes that a single user is communicating with the base station using the entire sub-carriers. This assumption is motivated by the OFDM, which uses multiple carriers in order to benefit from the frequency selective fading introduced by spreading the information bits over the entire signal band. An offline dynamic programming algorithm for finding an optimal solution for the case of spectrum- and time-perfect estimates is also presented. The performance can potentially be improved by using high-level modulation on the sub-carriers with good channel conditions.

Summary form only given. As the energy consumption in wireless sensor nodes is dominated by the radio transmission circuitry, the network configuration must be designed to minimize the power consumption by transmission radios. Sensor nodes are generally equipped with short-range radios that require low power consumption. But the current technology allows each node to adjust its transmission power. We consider the dual power radios in which the radio of each node can be assigned high-or low-power during the network initializing stage. Our primary goal in such an assignment is to minimize the overall power consumption by radios to maximize the network lifetime while maintaining the full network connectivity, the most fundamental network functionality. Using a graph-theoretic approach, we formulate the problem as a "minimum subgraph" problem, show its NP-completeness, establish upper and lower bounds on the optimum solution, and present a near-optimal heuristic algorithm and simulation results.

Network survivability is a crucial requirement in high-speed optical networks. Typical approaches of providing survivability have considered the failure of a single component such as a link or a node. We motivate the need for considering double-link failures and present three loopback methods for handling such failures. In the first two methods, two edge-disjoint backup paths are computed for each link for rerouting traffic when a pair of links fails. These methods require the identification of the failed links before recovery can be completed. The third method requires the precomputation of a single backup path and does not require link identification before recovery. An algorithm that precomputes backup paths for links in order to tolerate double-link failures is then presented. Numerical results comparing the performance of our algorithm with other approaches suggest that it is possible to achieve almost 100% recovery from double-link failures with a moderate increase in backup capacity. A remarkable feature of our approach is that it is possible to trade off capacity for restorability by choosing a subset of double-link failures and designing backup paths using our algorithm for only those failure scenarios.

Network survivability is a crucial requirement in high-speed optical networks. Typical approaches of providing survivability have considered the failure of a single component such as a link or a node. We consider a failure model in which any two links in the network may fail in an arbitrary order. Three loopback methods of recovering from double-link failures are presented. The first two methods require the identification of the failed links, while the third one does not. However, precomputing the backup paths for the third method is more difficult than for the first two. A heuristic algorithm that pre-computes backup paths for links is presented. Numerical results comparing the performance of our algorithm with other approaches suggests that it is possible to achieve 100% recovery from double-link failures with a modest increase in backup capacity.

The design of logical topologies in wavelength-routing multihop optical networks is a well-studied problem. We consider logical topology (LT) design over the popular ring and linear topologies. Our objective is the minimization of the electronic processing delay for the worst case traffic flow. For uniform traffic between nodes, this delay minimization corresponds to minimizing the number of hops on a shortest path between the farthest two nodes in the logical topology (the diameter of the logical topology). The simple structure of the physical topologies enables us to present a rigorous analysis of the problem. We present lower bounds for the achievable diameter wherever possible and propose practical logical topology design algorithms and corresponding upper bounds. We also present an application of the LT designs in the linear topology to the survivability of ring networks.

Given the increasing traffic on the World Wide Web (Web), it is difficult for a single popular Web server to handle the demand from its many clients. By clustering a group of Web servers, it is possible to reduce the origin Web server's load significantly and reduce user's response time when accessing a Web document. A fundamental question is how to allocate Web documents among these servers in order to achieve load balancing? In this paper, we are given a collection of documents to be stored on a cluster of Web servers. Each of the servers is associated with resource limits in its memory and its number of HTTP connections. Each document has an associated size and access cost. The problem is to allocate the documents among the servers so that no server's memory size is exceeded, and the load is balanced as equally as possible. In this paper, we show that most simple formulations of this problem are NP-hard, we establish lower bounds on the value of the optimal load, and we show that if there are no memory constraints for all the servers, then there is an allocation algorithm, that is within a factor 2 of the optimal solution. We show that if all servers have the same number of HTTP connections and the same memory size, then a feasible allocation is achieved within a factor 4 of the optimal solution using at most 4 times the optimal memory size. We also provide improved approximation results for the case where documents are relatively small.

We consider multiwavelength wavelength-routing networks operating in circuit-switched mode. Wavelength utilization is poor in such networks if sessions require only a fraction of a wavelength's capacity. An all-optical approach to improve wavelength utilization is to use time division multiplexing (TDM) on each wavelength, and switch time slots and wavelengths. In this paper, we address the off-line multirate session scheduling problem, i.e., the problem of assigning time slots and wavelengths to a given static set of multirate sessions, in ring topologies. Given a set of sessions and their relative rates, our objective is to maximize network throughput. This objective translates to the problem of minimizing the maximum length of a TDM frame over all wavelengths. We first show that the off-line single-rate session scheduling problem is equivalent to the off-line wavelength assignment problem, and hence obtain bounds on frame length. We then present scheduling algorithms with provable worst-case bounds on frame length for multirate session scheduling.

This paper considers the transmission of uniform deterministic traffic in an optical broadcast-star network using wavelength division multiplexing. Lower bounds are established on the minimum time to exchange information between every node pair in such a network with tunable transmitters and fixed-tuned receivers. Three different scheduling algorithms are developed that are strictly optimal in three regimes of system parameters. The results are applicable to arbitrary tuning delays and arbitrary numbers of wavelength channels, and indicate the existence of a well-defined transition regime from tuning-limited operation to bandwidth-limited operation.

We consider the problem of embedding complete binary trees into meshes with the objective of minimizing the link congestion. Gibbons and Paterson showed that a complete binary tree Tp (with 2p − 1 nodes) can be embedded into a 2-dimensional mesh of 2p nodes with link congestion two. Using the dimension-ordered routing, the authors showed that Tp can be embedded into a 2-dimensional mesh of (81/64)2p nodes with link congestion one and mesh of 2p nodes with link congestion two. This paper shows that the increase of the dimension of a mesh gives a better embedding. In particular, Tp can be embedded into a 3-dimensional mesh with 2p nodes such that the link congestion of each dimension is two, two, and one if the dimension-ordered routing is used and two, one, and one if the dimension-ordered routing is not imposed. For a 4-dimensional mesh of 2p nodes, we show that Tp can be embedded with link congestion one in each dimension if p = 4k for an integer k. © 1997 John Wiley & Sons, Inc. Networks 30: 283–292, 1997

This paper considers the problem of allocating files in a document tree among multiple processors in a parallel webserver. It is assumed that access patterns are characterized by branching probabilities for an access that starts at a node and progresses down the tree. A combinatorial optimization problem is formulated that includes load balancing and communication costs. The general problem is shown to be NP-complete, and a pseudo-polynomial time algorithm is outlined. In addition, two fast heuristic algorithms are presented and evaluated using simulation.

This paper is concerned with broadcasting on 2-dimensional torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. It is assumed that there are α and β physical channels in the X- and Y-dimensions, respectively, and path selection between any two nodes is done using row-column routing. Given an n × n mesh or torus, we first discuss the lower bounds of broadcasting time; any broadcasting algorithm requires at least [log(2α + 2β + 1)n2] time steps and no broadcasting algorithm achieves this lower bound if α < β(2β + 1). We then show that broadcasting on a (2α + 2β + 1)p × (2α + 2β + 1)p torus can be done in 2p time steps, which is optimum, for any α ≥ 3 and β = 1. We also present approximation algorithms for the cases of mesh when α ≥ 1 and β = 1 and torus when α ≤ 2 and β = 1. © 1996 John Wiley & Sons, Inc.

All-optical networks (AONs) with a broadcast-star based physical topology offer the possibility of transmission scheduling to resolve channel and receiver conflicts. This paper considers the problem of scheduling packet transmissions in a wavelength-division multiplexed (WDM) optical network with tunable transmitters and fixed-tuned receivers. The scheduling problem is complicated by tuning latency, a limited number of channels, and arbitrary traffic demands. We first analyze scheduling all-to-all packet transmissions and obtain a new lower bound for the schedule length. The lower bound is achieved by an algorithm proposed by Pieris and Sasaki (1994). We then extend the analysis to the case of arbitrary traffic demands and obtain lower bounds for the schedule length. Two constructions for scheduling algorithms are provided through list scheduling and multigraphs. The upper bounds so obtained not only provide performance guarantees with arbitrary demands, but also nearly meet the lower bound in simulations.

This paper considers the problem of embedding complete binary trees into meshes using the row-column routing and obtained the following results: a complete binary tree with 2/sup p/-1 nodes can be embedded (1) with link congestion one into a /sup 9///sub 8//spl radic/(2/sup p/)/spl times//sup 9///sub 8//spl radic/(2/sup p/) mesh when p is even and a /spl radic/(/sup 9///sub 8/2/sup p/)/spl times//spl radic/(/sup 9///sub 8/2/sup p/) mesh when p is odd, and (2) with link congestion two into a /spl radic/(2/sup p/)/spl times//spl radic/(2/sup p/) mesh when p is even, and a /spl radic/(2/sup p-1/)/spl times//spl radic/(2/sup p-1/) mesh when p is odd.

We consider the problem of broadcasting on torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. In this paper, we obtain an optimal broadcasting algorithm that uses pd time steps for a d-dimensional torus with (2d+1)/sup p/ nodes in each side of the torus. Using this algorithm, we show that a broadcasting on a d-dimensional mesh with the same size can be done in pd+p+d-1 time steps.

It is shown that for a given p (1or=5 remains connected provided that at most two neighbors of any processor are allowed to fail.>

Abstract A natural communication problem in a multicomputer system, such as the hypercube, is that a processor (called the source) wants to send a message to a number of other processors (destinations). A message‐routing paradigm for such a multidestination communication has been formulated as finding a subgraph called an Optimal Communication Tree (OCT). We prove that the problem of finding an OCT is NP‐hard for the n‐cube graph as well as for a graph whose maximum degree is at most three. Heuristics for finding suboptimal communication trees for the hypercube multicomputer are discussed.

In topological design of multicomputer systems (e.g., the hypercube), the edge- and vertex-connectivities have traditionally been used as deterministic measures of fault-tolerance. These measures have been noted to have some deficiencies and as a result several generalizations of graph connectivity have been proposed. In this paper, the authors examine some instances of the connectivity generalization proposed by Esfahanian and Hakimi, (1988). This generalization of graph connectivity can be used to model the fault-tolerance analysis of multicomputers in which any set S of the multicomputer components is considered fault free if the set S does not satisfy some given topological property rho . Using this model and different definitions of rho , the authors establish the complexity of analyzing the fault-tolerance of multicomputers.>

The vertex- (respectively, edge-) deletion graph bipartization problem is the problem of deleting a set of vertices (respectively, edges) from a graph so as to make the remaining graph bipartite. This paper first shows that the vertex-deletion graph bipartization problem has a solution of size k or less if and only if the edge-deletion graph bipartization problem has a solution of size k or less, when the maximum vertex degree is limited to three. This immediately implies that (1) the vertex-deletion graph bipartization problem is NP-complete for cubic graphs, and (2) the minimum vertex-deletion graph bipartization problem is solvable in polynomial time for planar graphs when the maximum vertex degree is limited to three. It is then proved that the vertex-deletion graph bipartization problem is NP-complete for planar graphs when the maximum vertex degree exceeds three. Using this result, it is finally shown that the via minimization problem, which arises in the design of integrated circuits and printed circuit boards, is NP-complete even when the maximum “junction” degree is limited to four.

Abstract The scheduling of data transfers in networks, where the schedule does not permit interruption and each communication module can be used as a transmitter and as a receiver (i.e., as a transceiver) was studied by Coffman et al. The same problem when interruption in the schedule is permitted and the transmitting and receiving modules are distinct was studied by Choi and Hakimi among others. Hajek and Sasaki studied another interesting variation of the problem where interruption is permitted but each communication module is a transmitter and a receiver. This paper presents certain generalizations and improvements of Hajek and Sasaki's results.

Abstract The scheduling of data transfers in networks, where the schedule does not permit interruption and each communication module can be used as a transmitter and as a receiver (i.e., as a transceiver) was studied by Coffman et al. The same problem when interruption in the schedule is permitted and the transmitting and receiving modules are distinct was studied by Choi and Hakimi among others. Hajek and Sasaki studied another interesting variation of the problem where interruption is permitted but each communication module is a transmitter and a receiver. This paper presents certain generalizations and improvements of Hajek and Sasaki's results.

The scheduling of file transfers in networks to minimize the overall finishing time was studied by Coffman, et al. where the schedule does not permit interruption and each communication module can be used as a transmitter and as a receiver. They first presented complexity results under various conditions. Then they showed that the general problem is NP-complete and provided approximation algorithms. This paper first presents more efficient approximation algorithms with better performances than the above authors’ algorithms for the cases of trees and multitrees. Furthermore, there are simple distributed implementations of our approximation algorithms. Then this paper provides a polynomial time algorithm for finding an optimum schedule for an odd cycle, whose complexity was left as an open question by the above authors.