Website fingerprinting is a passive network traffic analysis technique that enables an adversary to identify the website visited by a user despite encryption and the use of privacy services such as Tor. Several website fingerprinting defenses built on top of Tor have been proposed to guarantee a user’s privacy by concealing trace features that are important to classification. However, some of the best defenses incur a high bandwidth and/or latency overhead. To combat this, new defenses have sought to be both lightweight — i.e., introduce a small amount of bandwidth overhead — and zero-delay to real network traffic. This work introduces a novel zero-delay and lightweight website fingerprinting defense, called BRO, which conceals the feature-rich beginning of a trace while still enabling the obfuscation of features deeper into the trace without spreading the padding budget thin. BRO schedules padding with a randomized beta distribution that can skew to both the extreme left and right, keeping the applied padding clustered to a finite portion of a trace. This work specifically targets deep learning attacks, which continue to be among the most accurate website fingerprinting attacks. Results show that BRO outperforms other well-known website fingerprinting defenses, such as FRONT, with similar bandwidth overhead.

As the field of quantum computing rapidly advances, there is a growing demand for skilled professionals adept in quantum computing and programming. Recognizing this need, in this paper, we share our experiences teaching an introductory-level quantum computing course to students at Cleveland State University (CSU). The course integrates dedicated hands-on programming labs, allowing students to verify their experimental results with corresponding examples from the textbook. These labs cover a diverse range of topics, including fundamental elements such as quantum gates and circuits, quantum key distribution protocols, and quantum algorithms. As educators, our goal is to share teaching insights and resources with fellow instructors in the field. This article elucidates the rationale behind the design of each experiment, providing a deeper understanding of quantum computing.

The protection of Industrial Control Systems (ICS) that are employed in public critical infrastructures is of utmost importance due to catastrophic physical damages cyberattacks may cause. The research community requires testbeds for validation and comparing various intrusion detection algorithms to protect ICS. However, there exist high barriers to entry for research and education in the ICS cybersecurity domain due to expensive hardware, software, and inherent dangers of manipulating real-world systems. To close the gap, built upon recently developed 3D high-fidelity simulators, we further showcase our integrated framework to automatically launch cyberattacks, collect data, train machine learning models, and evaluate for practical chemical and manufacturing processes. On our testbed, we validate our proposed intrusion detection model called Minimal Threshold and Window SVM (MinTWin SVM) that utilizes unsupervised machine learning via a one-class SVM in combination with a sliding window and classification threshold. Results show that MinTWin SVM minimizes false positives and is responsive to physical process anomalies. Furthermore, we incorporate our framework with ICS cybersecurity education by using our dataset in an undergraduate machine learning course where students gain hands-on experience in practicing machine learning theory with a practical ICS dataset. All of our implementations have been open-sourced.

With the advancement and development for more than two decades, WiFi has become an indispensable infrastructure in most of indoor venues. Indoor localization using this pre-existing infrastructure has been studied in the literature and is proven practically feasible, which mostly relies on WiFi fingerprints and the corresponding radiomap database. Since the radiomap essentially tells which APs are available and how strong their signals are at positions in the venue, this information can usefully utilized to “steer” to a better AP for the purpose of increasing the user throughput, which we call Guided Tour of Handoff Steering (GUT) in this paper. This steering is not much different from a conventional handoff, but it does not need an expensive scanning process owing to the radiomap, thus some additional handoffs are allowed than conventional handoffs. This leads to higher throughput, because a client can switch to a better AP whenever available. Based on an extensive experiment in a large-scale indoor venue of 119,685m2with 1,734 APs, it is observed that GUT achieves as much as 84% higher throughput, but the number of handoffs increases only a few. This result supports that the handoff steering is not as expensive as the conventional handoff in terms of latency and traffic.

Due to the low-speed GPS transmission and poor signal quality, localization is considered an expensive operation in battery-operated smartphones. This is even worse for apps that need a single location fix such as Foursquare and Flickr rather than continuous navigation because it cannot exploit the less-demanding “warm start” mode of GPS operation. This paper proposes GPS-Tether (GTR) which shares and reuses the known GPS coordinates among mobile devices in the proximity. Benefiting from unremitting Wifi discovery behaviors of smartphones, GTR does not need an additional protocol and does not disrupt operations of non-GTR clients. Experiments based on Samsung Galaxy smartphones and Monsoon Power Monitor show that GTR can extend smartphones battery usage as much as 19% compared to Assisted GPS (A-GPS). One important design goal is that it should require minimal changes for the implementation of GTR, which has been accomplished by incorporating the Wifi virtualization technique.

While numerous efforts have been made to save energy of “client” devices but it has not been addressed for access points (APs) as they are assumed to be supported by AC power. This paper proposes E-MAP, which is an energy saving algorithm for a tethering smartphone that plays a role of mobile AP (MAP) temporarily. It saves MAP's energy by introducing the sleep cycle as in power save mode (PSM) in 802.11 but successfully keeps clients from transmitting while it sleeps. One important design goal of E-MAP is backward compatibility, i.e., it requires no modification on the client side and supports PSM and adaptive PSM (A-PSM) as well as normal constant awake mode (CAM) clients. Experiments show that E-MAP reduces the energy consumption of a Wifi tethering smartphone by up to 54% with a little impact on packet delay under various traffic patterns derived from real-life traces.

This paper proposes an energy-saving bit-rate adaptation algorithm for Software-defined Radio (SDR)-based wireless systems, called Joint Rate and Voltage Fallback (JRF). It exploits the unused network time in underutilized networks by using a lower bit-rate than what an underlying rate adaptation algorithm such as Auto-rate Fallback (ARF) or Robust Rate Adaptation Algorithm (RRAA) dictates. While slow or low bitrate communication potentially consumes more energy due to its extended communication time, it saves energy in SDR due to the possibility of reducing the speed and the voltage of the microprocessor that runs the SDR software. The net result favors a lower rate communication in terms of energy performance. To analyze the tradeoff quantitatively, this paper evaluates the computational complexity of SDR communication software by using BBN 802.11b implementation in GNU Radio. Moreover, for an extensive evaluation, we conducted the simulation study based on OPNET, which shows that JRF improves energy cost by as much as 78.0% compared to No Rate and Voltage Scaling (NoRVS) and as much as 51.3% compared to Independent Rate and Voltage Scaling (IRVS).

Being readily available in most of 802.11 radios, multirate capability appears to be useful as WiFi networks are getting more prevalent and crowded. More specifically, it would be helpful in high-density scenarios because internode distance is short enough to employ high data rates. However, communication at high data rates mandates a large number of hops for a given node pair in a multihop network and thus, can easily be depreciated as per-hop overhead at several layers of network protocol is aggregated over the increased number of hops. This paper presents a novel multihop, multirate adaptation mechanism, called multihop transmission opportunity (MTOP), that allows a frame to be forwarded a number of hops consecutively to minimize the MAC-layer overhead between hops. This seemingly collision-prone nonstop forwarding is proved to be safe via analysis and USRP/GNU Radio-based experiment in this paper. The idea of MTOP is in clear contrast to the conventional opportunistic transmission mechanism, known as TXOP, where a node transmits multiple frames back-to-back when it gets an opportunity in a single-hop WLAN. We conducted an extensive simulation study via OPNET, demonstrating the performance advantage of MTOP under a wide range of network scenarios.

In interference-rich and noisy environment, wireless communication is often hampered by unreliable communication links. Recently, there has been active research on cooperative communication that improves the communication reliability by having a collection of radio terminals transmit signals in a cooperative way. This paper proposes a medium access control (MAC) algorithm, called Cooperative Diversity MAC (CD-MAC), which exploits the cooperative communication capability of the physical (PHY) layer to improve robustness in wireless ad hoc networks. In CD-MAC, each terminal proactively selects a partner for cooperation and lets it transmit simultaneously so that this mitigates interference from nearby terminals, and thus, improves the network performance. For practicability, CD-MAC is designed based on the widely adopted IEEE 802.11 MAC. For accurate evaluation, this study presents and uses a realistic reception model by taking bit error rate (BER), derived from Intersil HFA3861B radio hardware, and the corresponding frame error rate (FER) into consideration. System-level simulation study shows that CD-MAC significantly outperforms the original IEEE 802.11 MAC in terms of packet delivery ratio and end-to-end delay.

Wireless multihop communication is becoming more important due to the increasing popularity of wireless sensor networks, wireless mesh networks, and mobile social networks. They are distinguished from conventional multihop networks in terms of scale, traffic intensity and/or node density. Being readily-available in most of 802.11 radios, multirate facility appears to be useful to address some of these issues and is particularly helpful in high-density scenarios where inter-node distance is short, demanding a prudent multirate adaptation algorithm. However, communication at high bit rates mandates a large number of hops for a given node pair and thus, can easily be depreciated as per-hop overhead at several layers of network protocol is aggregated over the increased number of hops. This paper presents a novel multihop, multirate adaptation mechanism, called Multihop Transmission OPportunity (MTOP), that allows a frame to be forwarded a number of hops consecutively but reduces the MAC-layer overhead between hops. This seemingly collision-prone multihop forwarding is proven to be safe via analysis and USRP/GNU Radio-based experiment. The idea of MTOP is in clear contrast to, but not mutually exclusive with, the conventional opportunistic transmission mechanism, referred to as TXOP, where a node transmits multiple frames back-to-back when it gets an opportunity. We conducted an extensive simulation study via ns-2, demonstrating the performance advantage of MTOP under a wide range of network scenarios.

Exploiting the multirate capability in mobile ad hoc networks (MANETs) is more complex than in single-hop WLANs because of the rate-distance and rate-hop count tradeoffs. This paper proposes path-centric on-demand rate adaptation for MANETs (PRAM) protocol. A unique feature that sets PRAM apart from most of previous studies is its path-centric approach. While others focus on finding the best data rate for each link and offering a routing path as a collection of links at their best rates, PRAM finds the best data rate for a source-destination pair and then, dynamically adapts it based on path lifetime and other factors. Another distinctive feature of PRAM is that it can be seamlessly incorporated with an on-demand routing protocol. Extensive performance study based on NS-2 has demonstrated that PRAM achieves as much as 71.7% higher packet delivery ratio than fixed-rate cases (6~54 Mbps) and as much as 43.2% higher than the multihop version of the well- known ARF mechanism in a wide range of network scenarios. It is also shown that PRAM is capable of using a mixture of data rates in an adaptive manner.

Internet-based vehicular ad hoc network (IVANET) is an emerging technique that combines a wired Internet and a vehicular ad hoc network (VANET) for providing universal information and service accessibility. A key design optimization technique in IVANETs is to cache the frequently accessed data items in a local storage of vehicles. Since vehicles are not critically limited by the storage/memory space and power consumption, cache replacement scheme for accommodating new data items is not an issue. Rather, a more critical design question is how to keep the cached copies valid or to invalidate them when the original data items are updated. This is particularly important in IVANETs, where vehicles move very fast. This paper proposes state-aware cooperative cache invalidation (CCI) scheme and its enhancement (ECCI) that take advantage of the underlying location management mechanism. Extensive performance study shows that the proposed schemes can reduce the query delay as much as 69% and increase the cache hit rate up to 57% in comparison to two existing cache invalidation techniques, called poll-each-read (PER) and extended asynchronous (EAS). Note that PER and EAS have been modified to work in IVANETs.

MyMemex server consists of a web server, a data collection agent, a file handler, and a database. The data collection agent makes connections to the company web services and stores the collected "web data" (phone logs, credit card usage logs, e- mails, and so on) to the memex database. The web server enables the users to view the collected data and get the results for the queries. The users can also upload the "file data" such as image, video, and audio files locally stored in user's personal computer. Before saving the memex data, the web server converts the various types of data into the standard 4W1H form. The "memex event ontology" is used in the conversion. Related events tend to happen consecutively. A group of related events is called an "episode". Given a series of memex events, MyMemex employs a heuristic algorithm to solve the episode classification problem.

In mobile ad hoc networks (MANETs), every node overhears every data transmission occurring in its vicinity and thus, consumes energy unnecessarily. However, since some MANET routing protocols such as dynamic source routing (DSR) collect route information via overhearing, they would suffer if they are used in combination with 802.11 PSM. Allowing no overhearing may critically deteriorate the performance of the underlying routing protocol, while unconditional overhearing may offset the advantage of using PSM. This paper proposes a new communication mechanism, called RandomCast, via which a sender can specify the desired level of overhearing, making a prudent balance between energy and routing performance. In addition, it reduces redundant rebroadcasts for a broadcast packet, and thus, saves more energy. Extensive simulation using NS-2 shows that RandomCast is highly energy-efficient compared to conventional 802.11 as well as 802.11 PSM-based schemes, in terms of total energy consumption, energy goodput, and energy balance.

Internet-based vehicular ad hoc network (IVANET) is an emerging technique that combines a wired Internet and a vehicular ad hoc network (VANET) for developing a next generation of ubiquitous communication infrastructure and improving universal information and service accessibility. A key optimization technique in IVANETs is to cache frequently accessed data items in a local storage of vehicles. Since vehicles are not critically limited by the storage space, it is a less of a problem which data items to cache. Rather, a critical design issue is how to invalidate them when data items are updated. This is particularly a concern due to vehiclespsila high-speed mobility. In this paper, we propose a novel cache invalidation algorithm that takes advantage of the underlying location management scheme to reduce the number of broadcast operations and the corresponding query delay. Numerical results indicate that the proposed scheme significantly reduces the communication cost, and thus is proven to be a viable solution for IVANETs.

This paper proposes a medium access control (MAC) algorithm, called Cooperative Diversity MAC (CD-MAC), which exploits the cooperative communication capability to improve robustness inwirelessadhocnetworks. In CD-MAC, each terminal proactively selects a relay for cooperation and lets it transmit simultaneously when it is beneficial in mitigating interference from nearby terminals and thus improving the network performance. For practicability, CD-MAC is designed based on the widely adopted IEEE 802.11 MAC. System-level simulation study shows that CD-MAC significantly outperforms the original IEEE 802.11 MAC in terms of packet delivery ratio.

Carrier-sense medium access control (MAC) protocols such as the IEEE 802.11 distributed coordination function (DCF) avoid collisions by holding up pending packet transmission requests when a carrier signal is observed above a certain threshold. However, this often results in unnecessarily conservative communication, thus making it difficult to maximize the utilization of the spatial spectral resource. This paper shows that a higher aggregate throughput can be achieved by allowing more concurrent communications and adjusting the communication distance on the fly, which needs provisions for the following two areas. On the one hand, carrier sense-based MAC protocols do not allow aggressive communication attempts when they are within the carrier senseable area. On the other hand, the communication distance is generally neither short nor adjustable because multihop routing protocols strive for providing minimum hop paths. This paper proposes a new MAC algorithm, called multiple access with salvation army (MASA), which adopts less sensitive carrier sensing to promote more concurrent communications and adjusts the communication distance adaptively via "packet salvaging" at the MAC layer. Extensive simulation based on the ns-2 has shown MASA to outperform the DCF, particularly in terms of packet delay. We also discuss the implementation of MASA based on the DCF specification

According to the carrier sensing mechanism adopted by distributed coordination function (DCF) in IEEE 802.11 standard, a node defers its communication if it senses the medium busy. However, this deferment might block more concurrent communications than necessary. In addition, in DCF, the time duration of deferment is not delivered to all potential interferers, particularly those in the distance. This paper proposes collision-aware DCF (CAD) that efficiently utilizes the available channel resource along both the spatial and time dimensions. Basically, CAD embeds the spatial and time reservation requirements in the PHY header, which is transmitted at the lower data rate, so that a larger group of potential interferers become aware of the ongoing communication and thus avoid collisions. Extensive simulation based on the ns-2 has shown that CAD offers as much as 21% higher packet delivery rate and 91 % lower packet delay than DCF with the CBR (constant bit rate) traffic

Recently, researchers have discovered that many of social, natural and biological networks are characterized by scale-free power-law connectivity distribution and a few densely populated nodes, known as hubs. We envision that wireless communication or sensor networks are directly deployed over such real-world networks to facilitate communication among participating entities. Here nodes move in such a way that they exhibit scale-free connectivity distribution at any instance, which cannot be modeled by most of the prior mobility models such as random waypoint (RWP) mobility model. This paper proposes clustered mobility model (CMM), which facilitates in forming hubs in a network satisfying the scale-free property. We call this a scale-free wireless network (SFWN). In CMM, it is possible to control the degree of node concentration or non-homogeneity to easily assess the strengths and weaknesses of the scale-free phenomena. To the best of the authors' knowledge, there has been no such mobility model reported in the literature and we believe the proposed CMM can be usefully used to investigate the properties of the SFWNs that are likely to occur in a real deployment of wireless multihop and sensor networks. Another important feature of CMM is that it does not possess any unintended spatial and temporal characteristics found in other mobility models such as RWP. Finally, to highlight the difference between a SFWN and a conventional wireless network, extensive simulation study has been conducted to measure network capacities at the physical, link and network layers

In a typical wireless mobile ad hoc network (MANET) using a shared communicationmedium, every node receives or overhears every data transmission occurring in its vicinity. However, this technique is not applicable when a power saving mechanism (PSM) such as the one specified in IEEE 802.11 is employed, where a packet advertisement period is separated from the actual data transmission period.When a node receives an advertised packet that is not destined to itself, it switches to a low-power state during the data transmission period, and thus, conserves power. However, since some MANET routing protocols such as Dynamic Source Routing (DSR) collect route information via overhearing, they would suffer if they are used with the IEEE 802.11 PSM. Allowing no overhearing may critically deteriorate the performance of the underlying routing protocol, while unconditional overhearing may offset the advantage of using PSM. This paper proposes a new communication mechanism, called RandomCast or Rcast, via which a sender can specify the desired level of overhearing in addition to the intended receiver. Therefore, it is possible that only a random set of nodes overhear and collect route information for future use. Rcast improves not only the energy efficiency, but also the energy balance among the nodes, without significantly affecting the routing efficiency. Extensive simulation using the ns-2 network simulator shows that Rcast is highly energy-efficient compared to the original IEEE 802.11 PSM and On-Demand Power Management (ODPM) protocol in terms of total energy consumption (157% to 236% less than PSM and 28% to 131% less than ODPM) and energy balance (four times less variance than ODPM) among the nodes.

IEEE 802.11 MAC, called the Distributed Coordination Function (DCF), employs carrier sensing to effectively avoid collisions, but this makes it difficult to maximally reuse the spatial spectral resource available for exposed terminals. This paper proposes a new MAC algorithm, called Multiple Access with Salvation Army (MASA), which adopts less sensitive carrier sensing to promote more spatial reuse of the channel. However, this may result in a higher collision probability. MASA alleviates this problem by adaptively adjusting the communication distance via "packet salvaging" at the MAC layer. Extensive simulation based on the ns-2 has shown MASA to offer as much as 25% higher packet delivery rate and 27% higher throughput than the DCF with the CBR (constant bit rate) and TCP traffic, respectively. In particular, a significant reduction in packet delay, 86% and 70% lower packet delay with the CBR and TCP traffic, makes MASA suitable for delay-sensitive applications. For practicality, we discuss the implementation of MASA based on the DCF specification.

While most previous studies on mobile ad hoc networks (MANETs) rely on the assumption that nodes are randomly distributed in the network coverage area, this assumption is unlikely to hold, as nodes tend to be cluttered around hot spots like the site of an accident or disaster. We refer to this as a clustered layout. Intuitively, a MANET with the clustered layout may suffer from serious performance degradation due to the excessive collisions in congested hot spots and space underutilization of sparse areas. In this paper, we propose a power-controlled network protocol, called the power-stepped protocol (PSP), that maximizes the spatial utilization of limited channel bandwidth. Using a number of discrete power levels available for the underlying wireless network hardware, PSP finds the appropriate power level for each node in a distributed and a coordinated manner without causing any serious problem at the medium access control and network routing layers. A unique feature of this approach is the use the chosen radio power for both data and control packets, and thus, it requires neither any special mechanism (e.g., a separate control channel) nor frequent power adjustments. Our extensive ns-2-based simulation results have shown the proposed PSP provides excellent performance in terms of packet delivery ratio and delay, as well as the network capacity.

Due to its topological generality and flexibility, the k-ary n-cube architecture has been actively researched for various applications. However, the processor allocation problem has not been adequately addressed for the k-ary n-cube architecture, even though it has been studied extensively for hypercubes and meshes. The earlier k-ary n-cube allocation schemes based on conventional slice partitioning suffer from internal fragmentation of processors. In contrast, algorithms based on job-based partitioning alleviate the fragmentation problem but require higher time complexity. This paper proposes a new allocation scheme based on isomorphic partitioning, where the processor space is partitioned into higher dimensional isomorphic subcubes. The proposed scheme minimizes the fragmentation problem and is general in the sense that any size request can be supported and the host architecture need not be isomorphic. Extensive simulation study reveals that the proposed scheme significantly outperforms earlier schemes in terms of mean response time for practical size k-ary and n-cube architectures. The simulation results also show that reduction of external fragmentation is more substantial than internal fragmentation with the proposed scheme.

Group communication is a useful mechanism guaranteeing consistency among replicated objects. The existing approaches do not allow transparent plug-in of group communication protocols into CORBA. They either require modification of CORBA or OS, or provide no room for incorporating group communication transport protocols into CORBA. We thus propose a generic group communication framework that allows transparent plug-in of various group communication protocols with no modification of existing CORBA. We extend the open communications interface (OCI) to support interoperability, reusability of existing group communication, and independency on ORB and OS. We also define the group communication inter-ORB protocol (GCIOP) as a group communication instantiation of the general inter-ORB protocol (GIOP) that encapsulates underlying group communication protocols. The proposed scheme can be exploited for fault-tolerant CORBA (FT CORBA).

Abstract Although establishing correct and efficient routes is an important design issue in mobile ad hoc networks (MANETs), a more challenging goal is to provide energy efficient routes because mobile nodes' operation time is the most critical limiting factor. This article surveys and classifies the energy‐aware routing protocols proposed for MANETs. They minimize either theactive communication energyrequired to transmit or receive packets or theinactive energyconsumed when a mobile node stays idle but listens to the wireless medium for any possible communication requests from other nodes.Transmission power control approachandload distribution approachbelong to the former category, andsleep/power‐down mode approachbelongs to the latter category. While it is not clear whether any particular algorithm or a class of algorithms is the best for all scenarios, each protocol has definite advantages/disadvantages and is well suited for certain situations. The purpose of this paper is to facilitate the research efforts in combining the existing solutions to offer a more energy efficient routing mechanism. Copyright © 2003 John Wiley & Sons, Ltd.

This paper presents Linux/SimOS, a Linux operating system port to SimOS, which is a complete machine simulator from Stanford. The motivation for Linux/SimOS is to alleviate the limitations of SimOS, which only supports proprietary operating systems. The contributions made in this paper are two-fold: First, the major modifications that were necessary to run Linux on SimOS are described. Second, a detailed analysis of the UDP/IP protocol and M-VIA is performed to demonstrate the capabilities of Linux/SimOS. The simulation study shows that Linux/SimOS is capable of capturing all aspects of communication performance, including the effects of the kernel, device drivers, and network interface.

Supporting mobility in real-time applications such as Internet telephony is in demand as the mobile Internet becomes prevalent. A simple solution is to use Mobile JP in order to provide transparent handoffs to upper layer applications. However, due in part to the Mobile IP's limitations such as triangular routing delay and encapsulation overhead, application-layer solutions for mobile Internet telephony has been developed by extending Session Initiation Protocol (SIP). This work presents experimental results on Internet telephony based on Mobile IP and examines its feasibility by analyzing delay factors and increased network toads. We found that packet size in terms of number of frames per packet is important in optimizing the packet transmission delay and network load without hindering the interactivity in voice conversations. Our major contribution is to give a real experience on voice over Mobile IP and to raise a need of designing delay-aware and/or load-aware scheme for Internet telephony.

This paper reevaluates the multicast protocols for MANETs in terms of energy efficiency and proposes a new robust multicast protocol, called two-tree multicast (TTM). Multicast protocols can be broadly categorized into two types, tree-based multicast and mesh-based multicast, based on the network structure along which multicast packets are delivered to multiple receivers. Mesh-based protocols are more robust to mobility and result in high packet delivery ratio. On the other hand, multicast trees are more energy efficient than multicast meshes. This is because mesh-based protocols depend on broadcast flooding within the mesh and therefore, mobile nodes in the mesh must receive all multicast packets during the multicast communication. The proposed TTM uses two trees, a primary and an alternative backup tree, to improve energy efficiency compared to the mesh-based protocols and to offer a better energy balance and packet delivery ratio than the free-based protocols. Performance evaluation study shows that the proposed TTM saves energy consumption by a factor of 1.9/spl sim/4.0 compared to the mesh-based multicast. In terms of combined performance metric, energy per delivered packet, TTM shows up to 80% and 40% improved performance than the mesh-based multicast and the conventional shared tree multicast, respectively.

Mapping virtual process topology to physical processor topology is one of the most important issues in parallel computing. The mapping problem for switch-based cluster systems of irregular topology is very complicated due to the connection irregularity and routing complexity. This paper proposes two mapping schemes for irregular cluster systems, which try to map the nearest neighbors in the process topology to physically adjacent processors. In addition, an application-oriented performance metric, weighted cardinality, is introduced to represent the quality of mapping. A simulation study shows that, for a virtual topology of a 16/spl times/16 mesh, the proposed mapping schemes result in better mapping quality and about 15/spl sim/20% shorter communication latency compared to random mapping. The proposed algorithms should also be beneficial when they are applied to metacomputing and cluster of cluster systems, where the communication costs are an order of magnitude different depending on the relative position of the processor nodes.

A number of research efforts have been devoted to reduce energy consumption of a processor without impacting the performance through the use of dynamic voltage scaling (DVS). The paper presents two DVS algorithms on MPEG decoding. One is DVS with delay and drop rate minimizing algorithm (DVS-DM) where voltage is determined based on previous workload only. Another algorithm scales the supply voltage according to the predicted MPEG decoding time and previous workload (DVS with predicted decoding time or DVS-PD). Simulation results show that DVS-PD improves energy efficiency as much as 56% compared to the conventional shutdown algorithm. We also found that the amount of energy saving with DVS-PD is not affected by the fluctuation of the movie stream, but is related to the error rate of the predictor, which implies that if decoding time is predicted more accurately, the DVS algorithm can be more efficient.

Object replication is a technique to enhance fault tolerance and high availability. Group communication is a useful mechanism guaranteeing the consistency among replicated objects. We propose a generic group communication framework that allows transparent plug-in of various group communication protocols with no modification of existing CORBA. For this, we extend the Open Communications Interface (OCI) to support interoperability, reusability of existing group communication, and independency on ORB and OS. The proposed scheme is composed of group membership, group IOR, and group multicast. Experimental results show that group object invocation using the proposed scheme performs substantially better than group object invocations using IIOP as the number of members in a group increases.

For supporting real-time interaction in distributed virtual environments (DVEs), it is common to replicate virtual world data at clients from the server. For efficient replication, two schemes are used together in general - prioritized transfer of objects and a caching and prefetching technique. Existing caching and prefetching approaches for DVEs exploit spatial relationship based on distances between a user and objects. However, spatial relationship fails to determine which types of objects are more important to an individual user, not reflecting user's interests. We propose a scalable data management scheme using user-based caching and prefetching exploiting the object's access priority generated from spatial distance and individual user's interest in objects in DVEs. We also further improve the cache hit rate by incorporating user's navigation behavior into the spatial relationship between a user and the objects in the cache. By combining the interest score and popularity score of an object with the spatial relationship, we improve the performance of caching and prefetching since the interaction locality between the user and objects are reflected in addition to spatial locality. The simulation results show that the proposed scheme outperforms the hit rate of existing caching and prefetching by 10% on average when the cache size is set to basic cache size, the size of expected number of objects included in the user's viewing range.

This paper proposes a Barrier Tree for Meshes (BTM) to minimize the barrier synchronization latency for two-dimensional (2D) meshes. The proposed BTM scheme has two distinguishing features. First, the synchronization tree is 4-ary. The synchronization latency of the BTM scheme is asymptotically /spl theta/(log/sub 4/ n), while that of the fastest scheme reported in the literature is bounded between /spl Omega/(log/sub 3/ n) and /spl theta/(n/sup 1/2/), where n is the number of member nodes. Second, nonmember nodes are neither involved in the construction of a BTM nor actively participate in the synchronization operations, which avoids interference among different process groups during synchronization. This not only results in low setup overhead, but also reduces the synchronization latency. The low setup overhead is particularly effective for the dynamic process model provided in MPI-2. Extensive simulation study shows that, for up to 64/spl times/64 meshes, the BTM scheme results in about 40/spl sim/70 percent shorter synchronization latency and is more scalable than conventional schemes.

This paper proposes a solution to delivering multicast data reliably not only to/from fired hosts but also to/from mobile hosts in combined fixed/mobile IP networks, particularly with regard to the per-source shortest path multicast routing protocol and remote subscription option in the IETF mobile IP multicast standard. We propose exploiting tree-based error recovery, well-established concept for reliable multicast in fixed networks, where a hierarchical logical tree of a source and receivers is constructed over which the responsibility of error recovery is distributed. We introduce a new entity named ARMM (Agent for Reliable Mobile Multicast) located at each cell of the wireless/mobile networks. Each ARMM participates in a logical tree as a parent of mobile hosts in the corresponding cell. It is responsible for retransmission and requesting for retransmission on behalf of the mobile hosts. With aid of ARMM, the proposed scheme features (1) adaptive reconstruction of logical trees due to host mobility, (2) retransmission to mobile hosts via optimal routes, (3) abstracting a group of mobile hosts into a single ARMM (and thus reducing logical tree maintenance overhead), (4) efficient use of wireless bandwidth for retransmission, and (5) low processing burden on mobile hosts themselves. The experimental results show that the proposed scheme provides higher scalability than a scheme applying a generalized tree-based reliable multicast in mobile environments.

Task allocation using cubic partitioning of multistage interconnection networks (MINs) offers several advantages over random allocation of resources. The objective of this paper is to analyze MIN reliability considering the cubic allocation algorithm. A comprehensive analytical model is derived for predicting reliability of MIN-based systems where tasks are allocated using the buddy strategy. System reliability with the free list allocation policy is computed via simulation. It is shown that the system reliability is dependent on the allocation algorithm and the free list policy is superior to the buddy scheme in this respect. Two types of mapping algorithms known as conventional and bit reversal are used on a baseline MIN to show that the same allocation algorithm can result in different reliability and performance. A performance-related reliability measure is analyzed using probability of acceptance as the performance measure to demonstrate the trade-offs between performance and reliability.

This paper addresses task allocation schemes for MIN-based multiprocessors. Two types of allocation policies, cubic and noncubic, are discussed here. Conflicts through the network and inability to partition the system effectively are the main bottlenecks in a MIN-based system. To solve both the problems, a renaming scheme for input and output ports of a MIN is proposed. We use the baseline MIN as an example in this work and call the renaming scheme as bit reversal (BR) matching pattern. Allocation with the new matching pattern minimizes conflicts and partitions the system completely into independent subsystems. The novelty of this matching pattern is that we can use any dynamic cubic allocation and/or scheduling scheme developed for the hypercubes also for the MIN machines. The BR matching pattern can be used with any kind of MIN. An allocation policy for noncubic tasks is also presented with this matching pattern. Various performance measures with different allocation algorithms are compared via simulation. The advantages of the algorithms with the proposed matching pattern are shown in terms of system efficiency, delay and task miss ratio.>

Efficient task management in a hypercube multi-processor becomes difficult due to system overflow, where an incoming job cannot be allocated in spite of a sufficient number of free processors. Overflow occurs either due to the inability of recognizing a free subcube or due to external fragmentation. In this paper, we propose an allocation strategy that tries to scale down an incoming job size if it cannot fit into a fragmented hypercube. We call it limit allocation. We discuss three simple schemes, Limit-k, Greedy and Average. We conduct both analysis and simulation to characterize and compare various allocation policies. An M/M/m queueing model is developed to predict the behavior of buddy, free list and limit-k policies. The simulation study shows that the two adaptive schemes, greedy and average, outperform all other schemes reported so far in the literature.

Processor allocation and job scheduling are com plementary techniques to improve the performance of multiprocessors. It has been observed that all the hypercube allocation policies with the FCFS schedul ing show little performance difference. A greater im pact on the performance can be obtained by efficient job scheduling. This paper presents an effort in that direction by introducing a new scheduling algorithm called lazy scheduling for hypercubes. The motivation of this scheme is to eliminate the limitations of the FCFS scheduling. This is done by maintaining sep arate queues for different job sizes and delaying the allocation of a job if any other job(s) of the same di mension is(are) running in the system. Simulation studies show that the hypercube performance is dra matically enhanced by using the lazy scheme as com pared to the FCFS scheduling. Comparison with a re cently proposed scheme called scan indicates that the lazy scheme performs better than scan under a wide range of workloads.

Cubic and noncubic task allocation algorithms for multistage-interconnection-network (MIN)-based multiprocessors are presented. Conflicts in passage through the network and inability to partition the system effectively are the main bottlenecks in a MIN-based system. To solve both problems, a renaming scheme called bit reversal (BR) matching pattern is proposed. This matching pattern minimizes conflicts and partitions the system completely into subsystems. Simulation results that show the advantage of allocation algorithms using the proposed matching pattern in terms of system efficiency, delay, and task miss ratio are presented.>