Intel Software Guard Extensions (SGX) remote attestation enables enclaves to authenticate hardware inside which they run, and attest the integrity of their enclave memory to the remote party. To enforce direct control of attestation, Intel mandates attestation to be verified by Intel's attestation service. This Intel-centric attestation model, however, neither protects privacy nor performs efficiently when distributed and frequent attestation is required. This paper presents OPERA, an Open Platform for Enclave Remote Attestation. Without involving Intel's attestation service while conducting attestation, OPERA is unchained from Intel, although it relies on Intel to establish a chain of trust whose anchor point is the secret rooted in SGX hardware. OPERA is open, as the implementation of its attestation service is completely open, allowing any enclave developer to run her own OPERA service, and its execution is publicly verifiable and hence trustworthy; OPERA is privacy-preserving, as the attestation service does not learn which enclave is being attested or when the attestation takes place; OPERA is performant, as it does not rely on a single-point-of-verification and also reduces the latency of verification.

Speculative execution side-channel vulnerabilities in micro-architecture processors have raised concerns about the security of Intel SGX. To understand clearly the security impact of this vulnerability against SGX, this paper makes the following studies: First, to demonstrate the feasibility of the attacks, we present SgxPectre Attacks (the SGX-variants of Spectre attacks) that exploit speculative execution side-channel vulnerabilities to subvert the confidentiality of SGX enclaves. We show that when the branch prediction of the enclave code can be influenced by programs outside the enclave, the control flow of the enclave program can be temporarily altered to execute instructions that lead to observable cache-state changes. An adversary observing such changes can learn secrets inside the enclave memory or its internal registers, thus completely defeating the confidentiality guarantee offered by SGX. Second, to determine whether real-world enclave programs are impacted by the attacks, we develop techniques to automate the search of vulnerable code patterns in enclave binaries using symbolic execution. Our study suggests that nearly any enclave program could be vulnerable to SgxPectre Attacks since vulnerable code patterns are available in most SGX runtimes (e.g., Intel SGX SDK, Rust-SGX, and Graphene-SGX). Third, we apply SgxPectre Attacks to steal seal keys and attestation keys from Intel signed quoting enclaves. The seal key can be used to decrypt sealed storage outside the enclaves and forge valid sealed data; the attestation key can be used to forge attestation signatures. For these reasons, SgxPectre Attacks practically defeat SGX's security protection. Finally, we evaluate Intel's existing countermeasures against SgxPectre Attacks and discusses the security implications.

Designing fast and secure RFID private authentication with structured key management is one of the most essential components for RFID-enabled large-scale object management. Since group keys are shared by some tags in structured key-based authentication, physical tampering of tags, so called the compromise attack, may enable the adversary to obtain group keys stored in the compromised tags, which in turn can be used to distinguish other tags. All existing structured key-based protocols try to reduce the common group key effect to preserve high privacy. However, the theoretical bound of weak privacy achievable by structured key-based authentication remains unknown. In this paper, we investigate weak privacy in RFID authentication. To this end, we first formulate a mathematical model which identifies the probability of two tags being linked with respect to the number of group keys. Our model shows that the existing solutions are far from the ultimate goal in weak privacy. Then, we propose a k-neighbor graph-based RFID authentication (KNGA) protocol, where random walk over a k-neighbor graph is performed. In addition, we show that KNGA achieves the performance bound, and we then quantify the degree of privacy by anonymity. Finally, the extensive simulations demonstrate that the proposed protocol successfully achieves its design goals.

Due to software implementation failure and misuse of cryptography, data encryption can no longer be considered a safeguard from security attacks. As a result, adversaries with eavesdropping capability along a routing path can compromise data privacy. In addition, should an adversary be one of the intermediate relay nodes in a path, she can deny data forwarding to disconnect the end-to-end communications. One solution is to avoid message routing through certain insecure areas, such as malicious countries or likely-compromised nodes. To this end, an avoidance routing based on the single path has been proposed. However, this single-path-based protocol relies on the availability of a safe path, i.e., no adversary is in the proximity of the whole path, which is difficult to achieve and therefore limits the routing opportunity. To tackle this issue, we propose an avoidance routing framework, namely timer-based multi-path avoidance routing (TMPAR). In our approach, a source node first encodes a message into k different pieces, and each piece is sent via a different path. During its path discovery phase, a timer is used to efficiently discover a better set of paths. The destination can assemble the original message easily. Under the condition that no adversary obtains all the k pieces of the message, the proposed TMPAR can securely deliver a message to its destination in spite of eavesdropping. The extensive ns-2 simulation results demonstrate that our TMPAR achieves its design goals.

Searchable encryption enables searches to be performed on encrypted documents stored on an untrusted server without exposing the documents or the search terms to the server. Nevertheless, the server typically learns which encrypted documents match the query-the so-called access pattern-since the server must return those documents. Recent studies have demonstrated that access patterns can be used to infer the search terms in some scenarios. In this paper, we propose a framework to protect systems using searchable symmetric encryption from access-pattern leakage. Our technique is based on d-privacy, a generalized version of differential privacy that provides provable security guarantees against adversaries with arbitrary background knowledge.

In this paper, we present HYPERRACE, an LLVM-based tool for instrumenting SGX enclave programs to eradicate all side-channel threats due to Hyper-Threading. HYPERRACE creates a shadow thread for each enclave thread and asks the underlying untrusted operating system to schedule both threads on the same physical core whenever enclave code is invoked, so that Hyper-Threading side channels are closed completely. Without placing additional trust in the operating system's CPU scheduler, HYPERRACE conducts a physical-core co-location test: it first constructs a communication channel between the threads using a shared variable inside the enclave and then measures the communication speed to verify that the communication indeed takes place in the shared L1 data cache-a strong indicator of physical-core co-location. The key novelty of the work is the measurement of communication speed without a trustworthy clock; instead, relative time measurements are taken via contrived data races on the shared variable. It is worth noting that the emphasis of HYPERRACE's defense against Hyper-Threading side channels is because they are open research problems. In fact, HYPERRACE also detects the occurrence of exception-or interrupt-based side channels, the solution.s of which have been studied by several prior works.

Privacy protection is the primary concern when RFID applications are deployed in our daily lives. Due to the computational power constraints of passive tags, non-encryption-based singulation protocols have been recently developed, in which wireless jamming is used. However, the existing private tag access protocols without shared secrets rely on impractical physical layer assumptions, and thus they are difficult to deploy. To tackle this issue, we first redesign the architecture of RFID system by dividing an RF reader into two different devices, an RF activator and a trusted shield device (TSD). Then, we propose a novel coding scheme, namely Random Flipping Random Jamming (RFRJ), to protect tags' content. Unlike the past work, the proposed singulation protocol utilizes only the physical layer techniques that are already implemented. Analyses and simulation results validate our distributed architecture with the RFRJ coding scheme, which defends tags' privacy against various adversaries including the random guessing attack, correlation attack, ghost-and-leech attack, and eavesdropping.

The performance of key authentication and the degree of privacy in large-scale RFID systems are considered by many researchers as tradeoffs. Based on how keys are managed in the system, the privacy preserving tag authentications proposed in the past can be categorized into tree-based and group-based approaches. While a tree-based approach achieves high performance in key authentication, it suffers from the issue of low privacy should a fraction of tags be compromised. On the contrary, while group-based key authentication is relatively invulnerable to compromise attacks, it is not scalable to a large number of tags. In this paper, we propose a new private tag authentication protocol based on skip lists, named randomized skip lists-based authentication (RSLA). Without sacrificing the authentication performance, RSLA provides a high privacy preserving mechanism. While RSLA provides the same level of unpredictability-based-privacy and indistinguishability-based privacy compared with other structured key management approaches, our scheme achieves the highest system anonymity with good performance in key look up and update. In addition, the simulation results match our analyses closely.

The speedy advancement in computer hardware has caused data encryption to no longer be a 100% safe solution for secure communications. To battle with adversaries, a countermeasure is to avoid message routing through certain insecure areas, e.g., Malicious countries and nodes. To this end, avoidance routing has been proposed over the past few years. However, the existing avoidance protocols are single-path-based, which means that there must be a safe path such that no adversary is in the proximity of the whole path. This condition is difficult to satisfy. As a result, routing opportunities based on the existing avoidance schemes are limited. To tackle this issue, we propose an avoidance routing framework, namely Multi-Path Avoidance Routing (MPAR). In our approach, a source node first encodes a message into k different pieces, and each piece is sent via k different paths. The destination can assemble the original message easily, while an adversary cannot recover the original message unless she obtains all the pieces. We prove that the coding scheme achieves perfect secrecy against eavesdropping under the condition that an adversary has incomplete information regarding the message. The simulation results validate that the proposed MPAR protocol achieves its design goals.

The performance of key authentication and the degree of privacy in large-scale RFID systems are considered by many researchers as tradeoffs. Based on how keys are managed in the system, the privacy preserving tag authentications proposed in the past can be categorized into tree-based and group-based approaches. While a tree-based approach achieves high performance in key authentication, it suffers from the issue of low privacy should a fraction of tags be compromised. On the contrary, while group-based key authentication is relatively invulnerable to compromise attacks, it is not scalable to the large number of tags. In this paper, we propose a new private tag authentication protocol based on skip lists, named Randomized Skip Lists-based Authentication. Without sacrificing the authentication performance, our scheme provides a strong privacy preserving mechanism.

Intrusion detection is a significant application in wireless sensor networks (WSNs). S. Kumar et al have introduced the concept of barrier coverage, which deploys sensors in a narrow belt region to guarantee that any intrusion across the region is to be detected. However, the practical issues have not been investigated such as scheduling sensors energy-efficiently while guaranteeing the detection probability of any intrusion across the region based on probabilistic sensing model. Besides, the intruders may be humans, animals, fighter planes or other things, which obviously have diverse moving speeds. In this paper, we analyze the detection probability of arbitrary path across the barrier of sensors theoretically and take the maximum speed of possible intruders into consideration since the sensor networks are designed for different intruders in different scenarios. Based on the theoretical analysis of detection probability, we formulate Minimum Weight ε-Barrier Problem about how to schedule sensors energy-efficiently and prove it is NP-hard. We propose both global and local solutions to the problem. The global solution called Minimum Weight Barrier Algorithm is a bounded approximation algorithm, based on which a localized protocol for energy-efficient scheduling is designed. To evaluate our design, we analyze the performance of our approaches theoretically and also perform extensive simulations to demonstrate the effectiveness of our proposed algorithm.

Intrusion detection is a significant application in wireless sensor networks (WSNs). S. Kumar et al have introduced the concept of barrier coverage, which deploys sensors in a narrow belt region to guarantee that any intrusion across the region is to be detected. However, the practical issues have not been investigated such as scheduling sensors energy-efficiently while guaranteeing the detection probability of any intrusion across the region based on probabilistic sensing model, which is a more realistic sensing model. Besides, the intruders may be humans, animals, fighter planes or other things, which obviously have diverse moving speeds. In this paper, we analyze the detection probability of arbitrary path across the barrier of sensors theoretically and take the maximum speed of possible intruders into consideration since the sensor networks are designed for different intruders in different scenarios. Based on the theoretical analysis of detection probability, we formulate a Minimum Weight ∈-Barrier Problem about how to schedule sensors energy-efficiently. We show the problem NP-hard and propose a bounded approximation algorithm, called Minimum Weight Barrier Algorithm (MWBA) to schedule the activation of sensors. To evaluate our design, we analyze the performance of MWBA theoretically and also perform extensive simulations to demonstrate the effectiveness of our proposed algorithm.

One of the extensively studied coverage models in wireless sensor networks is barrier coverage, which guarantees that any movement crossing the given belt must be detected, while the direction of the movement is not required. For some intrusion detection applications, it may be the case that only one direction of crossing (the belt) is illegal such as border guarding. Therefore, we introduce a new coverage model called one-way barrier coverage, which requires that the network reports illegal intruders while ignores legal intruders. We propose an appropriate definition for one-way barrier coverage. We deeply investigate one-way barrier coverage with binary sensors. Our research illustrates that it is not straightforward to provide oneway barrier coverage even though there is only one intruder. When there are multiple intruders, we introduce the concept of neighboring barriers and design different protocols to provide one-way barrier coverage for different sensor models based on neighboring barriers.

In this paper, we study optimal deployment in terms of the number of sensors required to achieve four-connectivity and full coverage under different ratios of sensors' communication range (denoted by rc) to their sensing range (denoted by rs). We propose a new pattern, the Diamond pattern, which can be viewed as a series of evolving patterns. When rc/rs¿ ¿(3), the Diamond pattern coincides with the well-known triangle lattice pattern; when rc/rs¿ ¿(2), it degenerates to a Square pattern (i.e., a square grid). We prove that our proposed pattern is asymptotically optimal when rc/rs> ¿(2) to achieve four-connectivity and full coverage. We also discover another new deployment pattern called the Double-strip pattern. This pattern provides a new aspect to research on optimal deployment patterns. Our work is the first to propose an asymptotically optimal deployment pattern to achieve four-connectivity and full coverage for WSNs. Our work also provides insights on how optimal patterns evolve and how to search for them.

Global barrier coverage, which requires much fewer sensors than full coverage, is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors can not locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms, thus limiting its use in practice. In this paper, we introduce the concept of local barrier coverage to address this limitation. Motivated by the observation that movements are likely to follow a shorter path in crossing a belt region, local barrier coverage guarantees the detection of all movements whose trajectory is confined to a slice of the belt region of deployment. We prove that it is possible for individual sensors to locally determine the existence of local barrier coverage, even when the region of deployment is arbitrarily curved. Although local barrier coverage does not deterministically guarantee global barrier coverage, we show that for thin belt regions, local barrier coverage almost always provides global barrier coverage. To demonstrate that local barrier coverage can be used to design localized algorithms, we develop a novel sleep-wakeup algorithm for maximizing the network lifetime, called localized barrier coverage protocol (LBCP). We prove that LBCP guarantees local barrier coverage and show that LBCP provides close to optimal enhancement in the network lifetime, while providing global barrier coverage most of the time. They outperform an existing algorithm called randomized independent sleeping (RIS) by up to six times.

To make a network last beyond the lifetime of an individual sensor node, redundant nodes must be deployed. What sleep-wake-up schedule can then be used for individual nodes so that the redundancy is appropriately exploited to maximize the network lifetime? We develop optimal solutions to both problems for the case when wireless sensor nodes are deployed to form an impenetrable barrier for detecting movements. In addition to being provably optimal, our algorithms work for nondisk sensing regions and heterogeneous sensing regions. Further, we provide an optimal solution for the more difficult case when the lifetimes of individual nodes are not equal. Developing optimal algorithms for both homogeneous and heterogeneous lifetimes allows us to obtain, by simulation, several interesting results. We show that even when an optimal number of sensor nodes has been deployed randomly, statistical redundancy can be exploited to extend the network lifetime by up to seven times. We also use simulation to show that the assumption of homogeneous lifetime can result in severe loss (two-thirds) of the network lifetime. Although these results are specifically for barrier coverage, they provide an indication of behavior for other coverage models.

In this paper, we study deployment patterns to achieve full coverage andk-connectivity(k≤ 6) under different ratios of the sensor communication range (denoted byRc) to the sensing range (denoted byRs) for homogeneous wireless sensor networks (WSNs). In particular, we propose new patterns for 3- and 5-connectivity. We also discover that there exists a hexagon-based universally elemental pattern that can generate all known optimal patterns. The previously proposed Voronoi-based approach cannot be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon-based methodology. We prove the optimality of deployment patterns to achieve 3-connectivity, 4-connectivity, and 5-connectivity for certain ranges ofRc/Rs, respectively, and prove the optimality of deployment patterns to achieve 6-connectivity under all ranges ofRc/Rs.

Sensors may fail due to various reasons such as heat, malicious activity, environmental hazards, extended use, and lack of power. As more and more sensors fail, certain desired properties such as barrier coverage will diminish and eventually fall below a desired level. In such a case, the network will have to be repaired. It is therefore desirable to have mechanisms to monitor network properties. In this article, we are interested in measuring the quality of barrier coverage, which is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. In the literature, researchers only consider whether or not a sensor network provides barrier coverage. This is equivalent to measuring its quality as either 0 or 1. We believe quality of barrier coverage is not binary and propose a metric for measuring it. If the measured quality is short of a desired value, we further identify all local regions that need to be repaired. The identified regions are minimal in the sense that if one of them is not repaired then the resulting network will still be short of quality. We also discuss how to actually repair a region.

We study the issue of optimal deployment to achieve four connectivity and full coverage for wireless sensor networks (WSNs) under different ratios of sensors' communication range (denoted by rc) to their sensing range (denoted by rs). We propose a "Diamond" pattern, which can be viewed as a series of different evolving patterns. When rc/rsges radic3, the Diamond pattern coincides with the well-known triangle lattice pattern; when rc/rsges radic2, it degenerates to a "Square" pattern. We prove the Diamond pattern to be asymptotically optimal when rc/rsges radic2- Our work is the first to propose an asymptotically optimal deployment pattern to achieve four connectivity and full coverage for WSNs. We hope our work will provide some insights on how optimal patterns evolve and how to search for them.

In this paper, we propose deployment patterns to achieve full coverage and three-connectivity, and full coverage and five-connectivity under different ratios of sensor communication range (denoted by Rc) over sensing range (denoted by Rs) for wireless sensor networks (WSNs). We also discover that there exists a hexagon-based universally elemental pattern which can generate all known optimal patterns. The previously proposed Voronoi-based approach can not be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon based methodology, and prove their optimality among regular patterns when Rc/Rs ≥ 1. We conjecture that our patterns are globally optimal to achieve full coverage and three-connectivity, and full coverage and five-connectivity, under all ranges of Rc/Rs. With these new results, the set of optimal patterns to achieve full coverage and k-connectivity (k≤6) is complete, for the first time.

Sensors may fail due to various reasons such as heat, malicious activity, environmental hazards, extended use, and lack of power. As more and more sensors fail, certain desired properties such as barrier coverage will diminish and eventually fall below a desired level. In such a case, the network will have to be repaired. It is therefore desirable to have mechanisms to monitor network properties. In this paper, we are interested in measuring the quality of barrier coverage. In the literature, researchers only consider whether or not a sensor network provides barrier coverage. This is equivalent to measuring its quality as either 0 or 1. We believe quality of barrier coverage is not binary and propose a metric for measuring it. If the measured quality is short of a desired value, we further identify all local regions that need to be repaired. The identified regions are minimum in the sense that if one of them is not repaired then the resulting network will still be short of quality. We also discuss how to actually repair a region.

The problem of sleep wakeup has been extensively studied for the full coverage model, where every point in the deployment region is covered by some sensor. Since the sleep-wakeup problem is NP-Hard for this model, several heuristics exist. For the model of barrier coverage, however, where sensors are deployed to form an impenetrable barrier for detecting moving objects (a flagship application of wireless sensor networks), design of an optimal sleep-wakeup algorithm is open. In this paper, we solve this open problem by proposing optimal algorithms not only for the often-used case of equal lifetime but also for the much harder case when sensor lifetimes are different. We prove the optimality of both algorithms. Our algorithms can be used to maintain not just barrier coverage but fault tolerant connectivity, as well, while maximizing the network lifetime. We use simulation to show that for random deployments, even when a minimal number of sensors have been deployed, our optimal algorithms can increase the network lifetime by 500% (from 10 weeks to more than a year). Finally, we show that using our optimal algorithms increases the network lifetime six times longer than that achievable using an existing sleep wake-up algorithm called Randomized Independent Sleeping (RIS).

Global barrier coverage that requires much fewer sensors than full coverage, is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors can not locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms, thus limiting its use in practice.

This paper studies the fundamental problem of clock synchronization in IEEE 802.11-based multihop ad hoc networks. Clock synchronization is important for power saving, network throughput, and efficiency of many protocols in an IEEE 802.11-based mobile ad hoc network. The scalability problem of 802.11 timing synchronization has been studied extensively in single hop ad hoc networks, and good solutions are available. These solutions, however, do not perform well in a multihop environment. A few multihop solutions for clock synchronization have been proposed recently, but the performances are still not very good. The maximum clock offset is still more than 200 mus for these protocols. This paper proposes an adaptive protocol through beacon transmission prioritization, frequency adjustment, and construction of dominating set. The frequency adjustment is proved to be bounded. Simulation studies show that the proposed protocol is able to limit the maximum clock offset to under 50 mus after protocol stabilization. The improvement is more than 400 percent over the current solutions. The proposed protocol also shows great long-term stability, and it handles mobility very well.

It is well-known that placing disks in the triangular lattice pattern is optimal for achieving full coverage on a plane. With the emergence of wireless sensor networks, however, it is now no longer enough to consider coverage alone when deploying a wireless sensor network; connectivity must also be con-sidered. While moderate loss in coverage can be tolerated by applications of wireless sensor networks, loss in connectivity can be fatal. Moreover, since sensors are subject to unanticipated failures after deployment, it is not enough to have a wireless sensor network just connected, it should be k-connected (for k > 1 ). In this paper, we propose an optimal deployment pattern to achieve both full coverage and 2-connectivity, and prove its optimality for all values of rc/rs, where rc is the communication radius, and rs is the sensing radius. We also prove the optimality of a previously proposed deployment pattern for achieving both full coverage and 1-connectivity, when rc/rs < √3 .Finally, we compare the efficiency of some popular regular deployment patterns such as the square grid and triangular lattice, in terms of the number of sensors needed to provide coverage and connectivity.

This paper studies the scalability and compatibility problems of clock synchronization in IEEE 802.11 ad hoc networks. The scalability problem of 802.11 timing synchronization has been recognized and studied by researchers in the field, but the proposed solutions are not meeting industry expectation. The compatibility issue is not well investigated by the research community yet. The compatibility issue is very important and practical because of the large deployment base of 802.11 networks. In this paper, we try to address both issues. We propose a simple, compatible protocol without any change of beacon format. The frequency adjustment is proved to be bounded and the maximum clock offset is controlled under 20 /spl mu/s. It is a significant improvement over the current results in the field. The current solutions with similar complexity can only control the maximum clock offset around 125 /spl mu/s for compatible solutions and 50 /spl mu/s for non-compatible protocols.

In this paper we study the defense of sensor networks against search-based physical attacks. We define search-based physical attacks as those, where an attacker detects sensors using signal detecting equipment and then physically destroys the detected sensors. In this paper, we propose a sacrificial node-assisted approach to defend against search-based physical attacks. The core principle of our defense is to trade short term local coverage for long term global coverage through the sacrificial node-assisted attack notification and states switching of sensors. The performance metric we use is accumulative coverage (AC), which effectively captures coverage and lifetime of the sensor networks to measure sensor network performance. Our simulation results clearly demonstrate that our defense approach can significantly decrease losses in AC even under intense search-based physical attacks.

Majority of papers in the area of wireless sensor networks (WSNs) have an element of energy-efficiency and associated with it an analysis of network lifetime. Yet, there is no agreement on how to analyze the lifetime of a WSN. As a result, errors are frequently made on both sides. Some underestimate the network lifetime by an order of magnitude, while others end up overestimating the lifetime by a significant factor. This paper presents a first step towards standardizing the lifetime analysis of WSNs. We focus on WSNs deployed for always-on applications, where the problem of power management is most severe because the environment needs to be monitored continuously. Underestimation of network lifetime is common when proposing sleep-wakeup schemes, where it is frequently assumed that in the absence of a sleep-wakeup scheme, a sensor node from the Mica family lasts 3-5 days on a pair of AA batteries. We show that the same sensor node can be made to last more than 36 days, even if it is continuously monitoring the environment. Overestimation typically occurs when proposing non-sleep-wake up power management schemes such as in-network data aggregation. Overestimation occurs because several network activities (e.g periodic routing messages) are assumed to have negligible effect on the network lifetime and therefore are ignored in the lifetime analysis. We use our recent experience in deploying ExScal (a large-scale WSN for intrusion detection) to identify major components in the network lifetime analysis. We then present a careful lifetime analysis of ExScal and show how to analyze the effects of using various non-sleep-wake up power management schemes such as hierarchical sensing, low-power listening, and in-network data aggregation on the network lifetime. Our lifetime analysis will be useful as a template in analyzing the lifetime of other WSNs deployed for always-on applications

This paper studies the fundamental problem of clock synchronization in IEEE 802.11-based multihop ad hoc networks. Clock synchronization is important for power saving, network throughput and many basic operations of 802.11 protocols in a multihop ad hoc network (MANET). The scalability problem of 802.11 timing synchronization has been studied extensively in single hop ad hoc networks and good solutions are available. However these solutions do not perform well in the MANET environment. A few multihop solutions were proposed; but the performance is still not very good. The maximum clock offset is still over 200 /spl mu/s for these protocols. In this paper, we propose an adaptive protocol through beacon transmission prioritization, frequency adjustment and construction of dominating set. The frequency adjustment is proved to be bounded. Simulation shows that we are able to control the maximum clock offset under 50 /spl mu/s after protocol stabilization. The improvement is more than 400% over the current solutions with similar complexity. The new protocol also shows great long-term stability.

In old times, castles were surrounded by moats (deep trenches filled with water, and even alligators) to thwart or discourage intrusion attempts. One can now replace such barriers with stealthy and wireless sensors. In this paper, we develop theoretical foundations for laying barriers of wireless sensors. We define the notion of k-barrier coverage of a belt region using wireless sensors. We propose efficient algorithms using which one can quickly determine, after deploying the sensors, whether a region is k-barrier covered. Next, we establish the optimal deployment pattern to achieve k-barrier coverage when deploying sensors deterministically. Finally, we consider barrier coverage with high probability when sensors are deployed randomly. We introduce two notions of probabilistic barrier coverage in a belt region -- weak and strong barrier coverage. While weak barrier-coverage with high probability guarantees the detection of intruders as they cross a barrier of stealthy sensors, a sensor network providing strong barrier-coverage with high probability (at the expense of more sensors) guarantees the detection of all intruders crossing a barrier of sensors, even when the sensors are not stealthy. Both types of barrier coverage require significantly less number of sensors than full-coverage, where every point in the region needs to be covered. We derive critical conditions for weak k-barrier coverage, using which one can compute the minimum number of sensors needed to provide weak k-barrier coverage with high probability in a given belt region. Deriving critical conditions for strong k-barrier coverage for a belt region is still an open problem.

This paper studies a fundamental problem, clock synchronization, in IEEE 802.11 ad hoc networks. Clock synchronization is important for frequent hopping spread spectrum (FHSS) to ensure that all stations "hop" at the same time; it is also necessary for FHSS, direct sequence spread spectrum (DSSS) and orthogonal frequency-division multiplexing (OFDM) to perform power management. The synchronization mechanism specified in the IEEE 802.11 standards has a severe scalability problem. Remedies have been proposed to solve the scalability problem, but these solutions either can not handle mobility very well or the protocol is too experimental without solid analysis. In this paper, we analyze the root cause of the scalability problem and propose two protocols with analytical guidance for implementation. The new solutions are distributed, scalable and very adaptive to station mobility. The maximum clock drift is improved from over 4000 /spl mu/s to under 125 /spl mu/s and 50 /spl mu/s respectively for our new protocols.

Sensor networks are often desired to last many times longer than the active lifetime of individual sensors. This is usually achieved by putting sensors to sleep for most of their lifetime. On the other hand, surveillance kind of applications require guaranteed k-coverage of the protected region at all times. As a result, determining the appropriate number of sensors to deploy that achieves both goals simultaneously becomes a challenging problem. In this paper, we consider three kinds of deployments for a sensor network on a unit square - a √n x √n grid, random uniform (for all n points), and Poisson (with density n). In all three deployments, each sensor is active with probability p, independently from the others. Then, we claim that the critical value of the function npπr2/log(np) is 1 for the event of k-coverage of every point. We also provide an upper bound on the window of this phase transition. Although the conditions for the three deployments are similar, we obtain sharper bounds for the random deployments than the grid deployment, which occurs due to the boundary condition. In this paper, we also provide corrections to previously published results for the grid deployment model. Finally, we use simulation to show the usefulness of our analysis in real deployment scenarios.

The IEEE 802.11 standards support the peer-to-peer mode independent basic service set (IBSS), which is an ad hoc network with all its stations within each other's transmission range. In an IBSS, it is important that all stations are synchronized to a common clock. Synchronization is needed for frequency hopping and power saving. The synchronization mechanism specified in the IEEE 802.11 standards has a severe scalability problem. The probability that stations may get out of synchronization is pretty high in large IBSS. A new synchronization algorithm has been proposed for large-scale ad hoc networks. We propose a more efficient algorithm in this paper that synchronizes the clock more accurately. We are able to synchronize the clock within 100 /spl mu/s when the number of stations is more than 300. This is a big improvement over the current best algorithm and the 802.11 specified protocol. To our best knowledge, the current best algorithm can synchronize the clock within 550 /spl mu/s for a 300-station network. The 802.11 standard protocol can have clock drift over 5000 /spl mu/s for the same network.

We investigate the power mode management problem for an IEEE 802.11-based mobile ad hoc network (MANET) that allows mobile hosts to tune to the power-saving (PS) mode. We adopt an asynchronous approach proposed in [Y. C. Tseng et al., (2002)] and correlate this problem to the quorum system concept. We identify a rotation closure property for quorum systems. It is shown that any quorum system that satisfies this property can be translated to an asynchronous power-saving protocol for MANETs. We derive a lower bound for quorum sizes for any quorum system that satisfies the rotation closure property. We identify a group of quorum systems that are optimal or near optimal in terms of quorum sizes, which can be translated to efficient asynchronous power-saving protocols. We also propose a new e-torus quorum system, which can be translated to an adaptive protocol that allows designers to trade hosts' neighbor sensibility for power efficiency.

Bluetooth is a radio interface standard used to build a personal area ad-hoc network(PAN) by interconnecting mobile electronics devices. In PAN, different applications and protocols place different QoS demands on the link. To meet these requirements properly, Bluetooth specification provides quality of service(QoS) configuration. In particular, Bluetooth LMP commands are used to configure the poll interval to provide QoS service to the higher layer. However, a method to provide QoS in scatternet is absent in the specification. Moreover, in scatternet, the schedule exerts a direct influence on the basic QoS properties like bandwidth, delay and jitter. We present two versions of QoS-aware scheduling algorithms: a perfect assignment algorithm for bipartite scatternet and a distributed, local algorithm. Also, both algorithms are shown to be perfect over tree scatternet. Finally, we present the performance and QoS evaluation. It is shown that the delay and jitter of the schedule generated by the algorithms have tight bounds.

Abstract Multicast/broadcast is an important service primitive in networks. It is supported by all IEEE 802.x standards, including 802.11. The IEEE 802.11 multicast/broadcast protocol is based on the basic access procedure of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). This protocol does not provide any media access control (MAC) layer recovery on multicast/broadcast frames. As a result, the reliability of the multicast/broadcast service is reduced owing to the increased probability of lost frames resulting from interference or collisions. Recently, a few MAC protocols have been proposed to enhance the reliability and the efficiency of the 802.11 multicast/broadcast protocol. In this paper, we observe that these protocols are still unreliable or inefficient. To redress the problems of reliability and efficiency, we propose a reliable Batch Mode Multicast MAC protocol (BMMM), which in most cases reduces the number of contention phases fromnto 1, wherenis the number of intended receivers in the multicast/broadcast. This considerably reduces the time required for a multicast/broadcast. We then propose a Location Aware Multicast MAC protocol (LAMM), which uses station location information to further improve upon BMMM. Extensive analysis and simulation results validate the reliability and efficiency of our multicast MAC protocols. Copyright © 2003 John Wiley & Sons, Ltd.

Bluetooth utilizes fast frequency hopping to mitigate interference from other wireless devices and other Bluetooth piconets that share the same frequency range. However, it still can not avoid the interference between piconets entirely. In our simulation, we observed that the inter-piconet interference can significantly degrade the system throughput by more than 30%. The system throughput within a piconet can be improved by a proper arrangement of the segmentation/reassembling (SAR) policy and a good selection of MAC scheduling protocols. Many SAR policies and MAC scheduling protocols were proposed, but none of them takes the inter-piconet interference into consideration. In this paper, we study the impact of the interference on the performance of TCP traffic over a Bluetooth scatternet with multiple overlapping piconets. To alleviate the impact, we propose interference-aware SAR policies as well as the interference-aware MAC scheduling protocols. The simulation results show that our schemes help reduce the impact of the inter-piconet interference by more than 50%.

Broadcast service is fundamental in ad hoc networks for different applications and dynamic source routing protocols. One problem that makes the traditional broadcast protocol inefficient is the broadcast storm problem. To alleviate the broadcast storm problem, the number of re-transmissions for a broadcast needs to be reduced. One possible solution is to use the node's geometric location information to obtain a smaller subset of neighbors (called local cover set) for re-transmissions. In this paper, we investigate the unique existence of the optimal local cover set. Based on the proof, we construct a location-based algorithm to compute the local cover set. We prove the correctness of our algorithm and discuss the time complexity of the algorithm. The simulation shows that the local cover set generated by our algorithm is significantly smaller than the graph-based broadcast protocol of Wu and Li (see Proc. DIAL M, Aug. 1999, p.7-14).

Multicast/broadcast is an important service primitive in networks. The IEEE 802.11 multicast/broadcast protocol is based on the basic access procedure of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). This protocol does not provide any media access control (MAC) layer recovery on multicast/broadcast frames. As a result, the reliability of the multicast/broadcast service is reduced due to the increased probability of lost frames resulting from interference or collisions. In this paper, we propose a reliable Batch Mode Multicast MAC protocol, BMMM, which substentially reduces the number of contention phases, thus considerably reduces the time required for a multicast/broadcast. We then propose a Location Aware Multicast MAC protocol, LAMM, that uses station location information to further improve upon BMMM. Extensive analysis and simulation results validate the reliability and efficiency of our multicast MAC protocols. 1

The IEEE 802.11 standards support the peer-to-peer mode Independent Basic Service Set (IBSS), which is an ad hoc network with all its stations within each other's transmission range. In an IBSS, it is important that all stations are synchronized to a common clock. Synchronization is necessary for frequency hopping spread spectrum (FHSS) to ensure that all stations "hop" at the same time; it is also necessary for both FHSS and direct sequence spread spectrum (DSSS) to perform power management. This paper evaluates the synchronization mechanism, which is a distributed algorithm, specified in the IEEE 802.11 standards. By both analysis and simulation, it is shown that when the number of stations in an IBSS is not very small, there is a non-negligible probability that stations may get out of synchronization. The more stations, the higher probability of asynchronism. Thus, the current IEEE 802.11's synchronization mechanism does not scale; it cannot support a large-scale ad hoc network. To alleviate the asynchronism problem, this paper proposes a simple modification to the current synchronization algorithm. The modified algorithm is shown to work well for large ad hoc networks.

Ad hoc networks in wireless communications is a challenging field due to the constant change of network topology. Broadcast service in ad hoc networks is critical in supporting various important applications and message routing. We examine the problem of the traditional broadcast protocol (i.e., flooding) in mobile wireless ad hoc networks, also known as "broadcast storm problem". We introduce a location aided algorithm to compute the optimal local cover set without delay and without much communication overhead. Based on the algorithm, we propose three new location-aided broadcast protocols for ad hoc networks that compute the optimal local cover set for retransmissions on-the-fly. We compare and analyze the simulation results of our protocols and others. The results show that our new protocols save a significant amount of wireless bandwidth and consume less overhead.

Distributed dynamic channel allocation (DDCA) is a fundamental resource management problem in mobile cellular networks. It has a flavor of distributed mutual exclusion but is not exactly a mutual exclusion problem. We establish the exact relationship between the two problems. Specifically, we introduce the problem of relaxed mutual exclusion to model one important aspect of the DDCA problem. We develop a general algorithm that guarantees relaxed mutual exclusion for a single resource and prove necessary and sufficient conditions for the information structure. Considering distributed dynamic channel allocation as a special case of relaxed mutual exclusion, we apply and extend the algorithm to further address the issues that arise in distributed channel allocation such as deadlock resolution, dealing with multiple channels, design of efficient information structures, and channel selection strategies. Based on these results, we propose an example distributed channel allocation scheme using one of the information structures proposed. Analysis and simulation results are provided and show that the results of this research can be used to design more efficient distributed channel allocation algorithms.

Building efficient ad hoc networks for wireless communications is challenging due to the dynamic nature of the hosts. Broadcast service in ad hoc networks is critical in supporting various applications and protocols. However, excessive redundant retransmissions of traditional broadcast protocols in mobile wireless ad hoc networks have caused the infamous "broadcast storm problem." Various broadcast protocols have been proposed to alleviate the broadcast storm problem. We identify two primary design issues, namely defer time generation and redundant message classification, for all these protocols. We propose a distance-based defer time scheme for the first issue and an angle-based scheme for the second issue. The two schemes together result in a broadcast protocol that enjoys flooding's high reachability and non-flooding schemes' bandwidth efficiency.

This paper presents a restoration scheme to minimize spare bandwidth reservation of bandwidth guaranteed paths that can recover 100% from single failure in MPLS mesh networks. Our new algorithm establishes multiple backup LSP for each primary LSP while backup LSP are multiplexed efficiently to reduce the resource reserved for backup LSP. The new scheme has several advantages compared with current work: the overall resource requirements for backup paths are reduced by about 20% to 30%; it balances the network resource utilization during the backup path reservation stage, it also balances the network load at path switchover stage. The new algorithm can admit more bandwidth guaranteed flows and it can improve the survivability of the networks. It can recover from multiple link failures when it is used with admission control. We extend the RSVP protocol to support our path restoration scheme in MPLS networks. We present the procedures to setup the backup paths, perform label binding and reserve backup resources. Explicit notification is utilized to improve the response time of network failover.

A major concern about wireless QoS is call dropping rate. On the other hand, efficient use of the scarce wireless bandwidth has always been of top importance. In the literature, these two issues are addressed separately by reservation and dynamic channel allocation. In this paper, we intend to provide an efficient approach to address both issues. We first explore combining dynamic channel allocation with reservation. Two approaches, namely hard reservation and soft reservation, are pointed out and examined. Then we propose to use soft reservation and to adaptively adjust the number of reserved channels by means of monitored network parameters. Extensive simulations are provided to compare the performances of different approaches. The results show our proposed approach guarantees a low call dropping rate while providing efficient bandwidth usage.

Distributed channel allocation is a fundamental resource management problem in mobile cellular networks. It has a flavor of distributed mutual exclusion but is not exactly a mutual exclusion problem (because a channel may be reused in different cells). However it is still not clear what is the relationship between the two problems. We establish the exact relationship between the two. Specifically, we introduce the problem of relaxed mutual exclusion to model the problem of distributed channel allocation. We develop a general algorithm that guarantees relaxed mutual exclusion for a single resource, prove a necessary and sufficient condition for the information structure, and address the issues that arise in relaxed mutual exclusion, including deadlock resolution, dealing with multiple resources, and design of efficient information structure.

In mobile (wireless) networks, one major concern about quality of service (QoS) is call dropping, where a handoff call is dropped due to insufficient wireless resources. Previous research on this issue suggested to reserve a certain amount of bandwidth for handoff calls. While such reservation schemes can reduce call dropping rate, it is at the cost of low bandwidth efficiency. In this paper we propose a new approach that combines dynamic channel allocation and call admission control for bandwidth management. Simulation studies show that the proposed approach is capable of keeping the call dropping rate below a prespecified value while improving bandwidth utilization by 20% to 30%.

Intelligent Transportation Systems (ITS) have become a focus for many countries. To achieve ITS, Inter Vehicle Communication (IVC) is required for the exchange and distribution of data such as congestion or emergency information. If this communication can be done without fixed infrastructure, the systems can be deployed quickly and on a larger scale. Ad hoc networking technologies are one such technology to achieve IVC. However, if generic ad hoc network solutions are applied directly to IVC, performance can degrade quickly as the system scales particularly for broadcast type messages. In this paper we propose two new broadcast protocols that reduce bandwidth required for broadcast communication by taking advantage of a vehicle's highly directional movement and Global Positioning Information. To show the performance of our new protocols, we compare our approach with generic ad hoc broadcasting techniques. Our results show that it is possible to achieve several hundred percent improvement of bandwidth utilization with very slight sacrifice of reachability.

Handoff in a wireless ATM network is an important and challenging problem. Previous research on this topic suggested using a cross-over switch (COS) for inter-switch handoffs. One overlooked problem with COS based handoff schemes is the possible disjointed connection for a mobile-to-mobile communication. Although one may argue that this may occur only occasionally, it does present a serious design flaw and should be corrected. We propose a general approach and a permission based inter-switch handoff protocol for mobile-to-mobile connection in wireless ATM networks. The proposed approach/protocol takes advantages of the ATM PNNI hierarchical information to detect potentially "unsafe" handoffs. Analysis shows that our approach/protocol avoids disjointed connection for mobile-to-mobile connections while keeping the overhead low.

Media access control (MAC) for broadband wireless networks is a hard and important problem. Previous studies on this problem suggested using reservations and demand assignments, i.e., mobile terminals (MTs) send requests to the base station (they may contend with each other for the access) to reserve transmission resources (time slots, codes, etc.) when they have data to send. These protocols may cause degradation of QoS, due to the fact that MTs could fail frequently competing for the access. Especially, these protocols can not meet the QoS requirements of delay sensitive and bursty data. We propose a novel MAC protocol which uses transmission collision as a useful information for random access. Analysis shows it overcomes the above mentioned problem (and thus guarantees better QoS) while consuming less wireless resources and system overhead.

There are two approaches to distributed implementation of dynamic carrier allocation (DCA) strategies: the update approach and the search approach. We first investigate the fundamental differences between the two approaches: two simple and representative schemes, namely the basic update scheme and the basic search scheme, are presented and compared. We argue that the update approach is more appropriate than the search approach for mobile cellular networks. Then we propose an advanced update scheme that is more efficient than the basic update scheme in terms of message complexity and carrier acquisition delay. The advanced update scheme can support a group of DCA strategies which require resource planning.

Probes and tokens are used in many deadlock detection and resolution algorithms. A deadlock is detected by propagating probes along dependency edges. When the initiator p/sub i/ of a probe receives its probe back, it knows of the existence of a deadlock. p/sub i/ then sends out a token to clean up those probes in the deadlock; cycle which, if not removed, may later lead to phantom deadlock detections. Only after the token returns to p/sub i/ is the deadlock resolved by aborting a 'victim' (usually p/sub i/). As a result, all involved transactions remain waiting and all involved resources locked until the token returns to p/sub i/, although the deadlock was already detected when the probe returned to p/sub i/. This paper proposes the idea of barriers to allow the deadlock to be resolved without waiting for the token to return to p/sub i/, thereby reducing the average deadlock persistence time considerably.

Priority-based dynamic carrier allocation strategies can be classified into three categories: static-priority, dynamic-priority, and hybrid-priority strategies. Strategies based on static priorities do not consider the local carrier reuse conditions, while dynamic-priority strategies do take these conditions into consideration. Intuitively, one would expect dynamic-priority strategies to perform better than static- and hybrid-priority strategies, but in the literature it is the other way around-existing dynamic-priority strategies are out-performed by some static- and hybrid-priority strategies. We propose a dynamic-priority strategy which is a significant improvement over all existing strategies. Under various traffic conditions, our simulation results indicated that the proposed strategy could reduce the call blocking/failure rate by a margin ranging from 15% to 95%.

Recently, DQDB (IEEE 802.6) MAN has been proposed as a component of Personal Communication Networks, in which base stations of wireless infrastructures are connected by a number of DQDBs which in turn are connected via bridges. We propose a protocol for call setup and path migration in a cluster of DQDBs. The protocol uses a link-state-like routing method for path selection and a source-routing-based scheme for path establishment. In addition, we propose a labeling scheme that makes it possible to carry the path information needed by the source routing protocol in a single 53-octet DQDB slot. Without such a labeling scheme, source routing would be inefficient for our purpose.

The DQDB (IEEE 882.6) MAN has been proposed as a component of the personal communication networks, in which the base stations of the wireless infrastructures are connected by a number of DQDBs which in turn are connected by bridges. We propose a protocol for call setup and path migration in a cluster of DQDBs. To pursue simplicity, efficiency, and speed in path setup, we use a link-state-like routing method for path selection, and a source-routing-based protocol for path establishment. The feasibility of the source routing protocol in a DQDB cluster is guaranteed by our novel labeling scheme. Each label represents the routing direction from one DQDB to another such that a path can be represented by a sequence of labels. Because of the locality property of the labels, a few bits are enough to denote the labels unambiguously. Using multi-bit labels instead of multi-byte physical addresses, a path can be specified in a 53-octet DQDB slot.

A reconfigurable mesh, R-mesh for short, is a two-dimensional array of processors connected by a grid-shaped reconfigurable bus system. Each processor has four I/O ports that can be locally connected during execution of algorithms. This paper considers the d-dimensional Euclidean minimum spanning tree (EMST) and the all nearest neighbors (ANN) problem. Two results are reported. First, we show that a minimum spanning tree of n points in a fixed d-dimensional space can be constructed in O(1) time on a /spl radic/(n/sup 3/)/spl times//spl radic/(n/sup 3/) R-mesh. Second, all nearest neighbors of n points in a fixed d-dimensional space can be constructed in O(1) time on an n/spl times/n R-mesh. There is no previous O(1) time algorithm for the EMST problem; ours is the first such algorithm. A previous R-mesh algorithm exists for the two-dimensional ANN problem; we extend it to any d-dimensional space. Both of the proposed algorithms have a time complexity independent of n but growing with d. The time complexity is O(1) if d is a constant.

This paper focuses on efficient multicasting in wormhole-routed networks. A trip-based model is proposed to support adaptive, distributed, and deadlock-free multiple multicast on any network with arbitrary topology using at most two virtual channels per physical channel. This model significantly generalizes the path-based model proposed earlier which works only for Hamiltonian networks and cannot be applicable to networks with arbitrary topology resulted due to system faults. Fundamentals of the trip-based model, including the necessary and sufficient condition to be deadlock-free, and the use of appropriate number of virtual channels to avoid deadlock are investigated. The potential of this model is illustrated by applying it to hypercubes with faulty nodes. Simulation results indicate that the proposed model can implement multiple multicast on faulty hypercubes with negligible performance degradation.

We propose an architecture of FDDI-based mobile networks and address issues that arise in providing real-time communication services on such networks. A wide range of problems concerning synchronous bandwidth management and quality of service guarantee are identified. To solve these problems, we present a dynamic bandwidth management scheme, a source handoff protocol and two approaches to handling destination handoffs. These schemes make handoffs transparent to mobile users; no degradation in quality of service will be observed during handoffs. The proposed solutions are compatible with the FDDI standards.

The paper presents a fault tolerant termination detection algorithm based on a previous fault sensitive scheme by Dijkstra and Scholten. The proposed algorithm can tolerate any number of crash failures. It runs as efficiently as its nonfault tolerant predecessor if no process actually fails during the computation, and otherwise incurs only a small amount of cost for each actual failure. It is assumed that the underlying communication network provides such services as reliable end to end communication, failure detection, and fail flush.>

A wide range of graphs with regular structures are shown to be embeddable in an injured hypercube with faulty links. These include rings, linear paths, binomial trees, binary trees, meshes, tori, and many others. Unlike many existing algorithms which are capable of embedding only one type of graphs, our algorithm embeds the above graphs in a unified way, all centered around a notion called edge matrix. In many cases, the degree of fault tolerance offered by the algorithm is optimal or near-optimal.

Managing computing resources in a hypercube entails two steps. First, a job must be chosen to execute from among those waiting (job scheduling). Next a particular subcube within the hypercube must be allocated to that job (processor allocation). Whereas processor allocation has been well studied, job scheduling has been largely neglected. The goal of this paper is to compare the roles of processor allocation and job scheduling in achieving good performance on hypercube computers. We show that job scheduling has far more impact on performance than does processor allocation. We propose a new family of scheduling disciplines, called Scan, that have particular performance advantages. We show that performance problems that cannot be resolved through careful processor allocation can be solved by using Scan job-scheduling disciplines. Although the Scan disciplines carry far less overhead than is incurred by even the simplest processor allocation strategies, they are far more able to improve performance than even the most sophisticated strategies. Furthermore, when Scan disciplines are used, the abilities of sophisticated processor allocation strategies to further improve performance are limited to negligible levels. Consequently, a simple O(n) allocation strategy can be used in place of these complex strategies.>

We consider the problem of embedding a ring in a hypercube that contains possible faulty nodes. Existing algorithms allow the number of faulty nodes to be at most 2n-\Theta(\sqrt {nlogn}), where n is the dimension of the hypercube. We propose an embedding scheme that can tolerate up to \Theta(2^{n/2}) faulty nodes, largely increasing the number of tolerable faulty nodes in a ring embedding.

A composition requires three operations: join, project, and duplicate elimination. A hot-spot composition algorithm is proposed in an attempt to achieve savings on both join and external sort operations. The proposed algorithm reduces the effort of performing the join operation by using a novel hot-spot technique. Several experiments have been conducted, and it is shown that the hot-spot composition algorithm outperforms other algorithms under almost every condition. The composition operation is implemented as a primitive operation in the algorithm.>

The authors consider a hypercube system that runs more than one job at a time, with each job allocated a subcube. They discuss the problem of migrating (relocating) a job from one subcube to another, assuming a circuit-switching hypercube network. An algorithm is presented for constructing parallel circuits between two subcubes so that the tasks of a job can be migrated simultaneously. It is shown that no matter how fragmented the hypercube is, one can always construct parallel paths between two given subcubes. Furthermore, one can always minimize the maximum length of the constructed circuits. A solution that minimizes the maximum length of the circuits will also minimize the total length. The circuits are mutually edge-disjoint and do not use any edge that has been used by other jobs. The time complexity of the algorithm is O(n/sup 2/m), where n is the dimension of the hypercube system and m is the number of jobs already in the system.>

The roles of processor allocation and job scheduling in achieving good performance on hypercube computers are compared. It is shown that the choice of job scheduling discipline has a dramatic effect on performance. A family of scheduling disciplines, called Scan, with particular performance advantages is proposed. Furthermore, it is shown that if Scan scheduling is used, the choice of processor allocation strategy has negligible effect on performance. As a result, complex allocation strategies can be replaced by a simple O(n) strategy.>

The commenters point out that conjectures in the above-named paper (ibid., vol.C-33, no.4, p.323-333) concerning the structure of a least-cost generalized hypercube can be proved.>

The authors formalize the problem of minimizing the length of the longest interprocessor wire as the problem of embedding the processors of a hypercube onto a rectangular mesh, so as to minimize the length of longest wire. Where neighboring nodes of the mesh are taken as being at unit distance from one another, and where wires are constrained to be laid out as horizontal and vertical wires, the length of the wire joining nodes u and v of the mesh equals the graph-theoretic distance between u and v. The problem of minimizing delays due to interprocessor communication is then modeled as the problem of embedding the vertices of a hypercube onto the nodes of a mesh, so as to minimize dilation. Two embeddings which achieve dilations that (for large n) are within 26% of the lower bound for square meshes and within 12% for meshes with aspect ratio 2 are presented.>

Consideration is given to the performance of parallel best-bound-first branch-and-bound algorithms in which several nodes with least lower bounds are expanded simultaneously. It is well known that anomalies may occur in the execution of a parallel branch-and-bound algorithm. The authors show the conditions under which anomalies are guaranteed not to occur when the number of processors is doubled, or not even doubled.

We develop an $O(q^2 n + n\log n)$ algorithm to obtain a preemptive schedule that minimizes maximum lateness when n jobs with given due dates and memory requirements are to be scheduled on m processors $(n \geqq m)$ of given memory sizes q is the number of distinct due dates. The value of the minimum maximum lateness can itself be found in $O(qn + n\log n)$ time.