In this paper, we investigate a fundamental assignment problem for a type of constrained group service. A group is considered successfully formed only if the number of assigned patrons falls within the specified lower and upper-bound constraints. We introduce the concept of rank-consistent to characterize a useful subset of the assignment problem. Although the problem is still NP-hard, we introduce the technique of allocation vectors to handle the complexity. This technique not only allows us to exploit several characteristics for performance optimization but also enables us to design a generic procedure to obtain the optimal physical assignment under a given allocation vector. We lay the foundation of a 1/2 approximation algorithm and a branch and bound algorithm for seeking the optimal solution. The branch and bound algorithm employs a specific pattern of optimal allocation vector and several newly proposed pruning techniques, especially the one that utilizes the dominance relations between allocation vectors. Extensive experiments demonstrate that our algorithm is much more effective than a set of heuristic greedy algorithms.

Network Function Virtualization (NFV) pushes the hardware-based network functions to generic servers as software and brings a highly flexible for deployment. The availability of Virtual Machines (VMs) enables the dynamic placement of Virtual Network Functions (VNFs) on demand, and it can reduce a large number of manual configuration processes that increase deployment efficiency. However, some services require more than one VNF to process. Therefore, the network flows need to traverse a set of sequential network functions called Service Function Chain (SFC). How to efficiently route traffic along service function chain and place VNFs in a network under operational constraints is a crucial issue. In this paper, we must overcome two challenges: (1) determining a flow path that traverses suitable network functions in the required order to meet the requirement of services, and (2) considering network loading and other dynamic characteristics when traffic is routed through existing VNFs. Thus, we present methods to solve the routing and placement problems for the service function chain. Our solutions transform the network representation to a virtual layered graph that considers NFV processing latency and allows conventional shortest path algorithms to solve the problem. We are not only pursuing high success rates to serve more flows but also taking into account the execution time of the algorithms.

Group services are highly important for a variety of computing application domains. In this paper, we study the fundamental problem of allocating a set of service patrons to a set of service groups in an attempt to maximize the total profit gained by the grouping platform. The problem under consideration is unique in that group service is not provided at all unless its lower bound requirement is satisfied. In addition, we allow each service patron to join multiple groups. In this paper, after proving the hardness property of the problem, we focus first on a special case of the problem. To this end, we propose two approaches. One aims at providing a suboptimal solution using a 1/2-approximation algorithm. The other approach turns to seeking an optimal solution using a branch and bound technique. For this purpose, we introduce a theorem that captures a useful property of an optimal allocation. Based on this theorem, we design an efficient branch and bound algorithm to find an optimal solution. We then extend these methods to solve the general problem. Extensive experiments show that our branch and bound algorithm is able to obtain an optimal solution with a small amount of computation time in many different settings.

There are two preference-based queries commonly used in database systems: (1) top-k query and (2) skyline query. By combining the ranking rule used in top-\(k\) query and the notion of dominance relationships utilized in the skyline query, a top-\(k\) dominating query emerges, providing a new perspective on data processing. This query returns the \(k\) records with the highest domination scores from the dataset. However, the processing of the top-\(k\) dominating query is complex when the dataset operates under a streaming model. With new data being continuously generated while stale data being removed from the database, a continuous top-\(k\) dominating query (cTKDQ) requires that updated results can be returned to users at any time. This work explores the cTKDQ problem and proposes a unique indexing structure, called a Close Dominance Graph (CDG), to support the processing of a cTKDQ. The CDG provides comprehensive information regarding the dominance relationship between records, which is vital in answering a cTKDQ with a limited search space. The update process for a cTKDQ is then converted to a simple update affecting a small portion of the CDG. Experimental results show that this scheme is able to offer much better performance when compared with existing solutions.

Target detection is an important problem in wireless sensor networks where a number of sensors form a network to detect the presence or absence of a certain target or event. Data fusion is a potential method broadly used to improve detection performance when the sampling data are noisy. However, low detection probability cannot be avoided if detection decisions are made based on a collection of sampling data taken at just one particular moment. This paper adopts fusion-based sequential detection to guarantee the quality of detection results. A fusion center is used to collect local data from individual sensors periodically. A final detection decision is made only after the pre-defined constraints of false alarm and missing probability are satisfied. Rules for each sensor to make local decisions and for the fusion center to make global decisions are derived. Simulations are conducted to show the latency of making the final decisions based on the proposed fusion scheme.

Video multicast exploits the wireless broadcast nature to transmit a video stream to multiple clients with a minimum bandwidth requirement. Assigning a suitable transmission bit-rate to each scalable coded block in a video stream is however a challenging problem because clients in a wireless network have heterogeneous channel quality and experience different packet loss probability. Prior work attempts to transmit the base-layer stream at a low transmission bit-rate to ensure a high reception probability, and hence the basic visual quality. Such methods however are over-simplified for a video stream that supports multiple quality levels in a video frame and needs explicit rate assignment for each block. We propose in this paper a dependency-aware rate scheduling scheme that assigns each block a rate according to dependency between blocks. With consideration of block dependency, we can better utilize limited wireless bandwidth to deliver important blocks, and minimize the number of undecodable blocks due to the loss of their reference blocks at the receivers. The simulation results show that since our scheme reduces the number of undecodable blocks, it achieves a higher overall video quality for a multicast group than the existing schemes under different client distributions.

The spatial query has been one of the highly demanded services in mobile computing system recently. To protect users' location privacy, existing architecture provides a trustworthy anonymizer to blur users' location from the service provider. However, with mobile capability, users' location extends from one spot to a continuous traveling route. For such continuous spatial query, it raises much more challenges for an anonymizer to protect users' continuous privacy. This paper conducts research on ensuring users' location privacy under the network-constrained road network environments. We first argue that the concept of continuous location privacy should be transferred to users' path privacy, which are consecutive road segments that needs to be protected. A novel M-cut requirement is proposed to achieve the goal of user path privacy. Mobile users can customize their privacy level through M-cut requirement. Last, two methods of constructing the cloaked spatial region are provided in our research, namely Random Selection and Junction Sharing. These algorithms support path privacy and also take system computation and communication overhead into consideration.

NAND flash memory has gained its popularity in a variety of applications as a storage medium due to its low power consumption, nonvolatility, high performance, physical stability, and portability. In particular, Multi-Level Cell (MLC) flash memory, which provides a lower cost and higher density solution, has occupied the largest part of NAND flash-memory market share. However, MLC flash memory also introduces new challenges: (1) Pages in a block must be written sequentially. (2) Information to indicate a page being obsoleted cannot be recorded in its spare area due to the limitation on the number of partial programming. Since most of applications access NAND flash memory under FAT file system, this article designs an MLC Flash Translation Layer (MFTL) for flash-memory storage systems which takes constraints of MLC flash memory and access behaviors of FAT file system into consideration. A series of trace-driven simulations was conducted to evaluate the performance of the proposed scheme. Although MFTL is designed for MLC flash memory and FAT file system, it is applicable to SLC flash memory and other file systems as well. Our experiment results show that the proposed MFTL could achieve a good performance for various access patterns even on SLC flash memory.

Cache sharing has been a popular technique used to facilitate data access in mobile network environments. The key to this technique is to allow an efficient sharing of cache contents between neighboring nodes without introducing excessive amount of communication overhead. In this paper, we propose a cache-sharing protocol, called ‘Pull with Piggybacked Push (PPP)’, which exploits data request broadcasts by performing data pull and index push operations together. Taking advantage of both push- and pull-based approaches, PPP gains benefits from both ends: performance and communication overhead. PPP is unique in that it yields good performance over diverse operating environments, while accomplishing it with lower communication overhead than the previous methods. In addition, it adapts well to different data access patterns. As a result, better scalability is achieved by the proposed protocol.

This work considers data query applications in tree-structured networks, where a given set of source nodes generate (or collect) data and forward the data to some halfway storage nodes for satisfying queries that call for data generated by all source nodes. The goal is to determine an optimal set of storage nodes that minimizes overall communication cost. Prior work toward this problem assumed homogeneous channel cost, which may not be the case in many network environments. We generalize the optimal storage problem for a tree-structured network by considering heterogeneous channel costs. The necessary and sufficient conditions for the optimal solution are identified, and an algorithm that incurs a linear time cost is proposed. We have also conducted extensive simulations to validate the algorithm and to evaluate its performance.

Diskless checkpointing is an important technique for performing fault tolerance in distributed or parallel computing systems. This study proposes a new approach to enhance neighbor-based diskless checkpointing to tolerate multiple failures using simple checkpointing and failure recovery operations, without relying on dedicated checkpoint processors. In this scheme, each processor saves its checkpoints in a set of peer processors, called checkpoint storage nodes. In return, each processor uses simple XOR operations to store a collection of checkpoints for the processors for which it is a checkpoint storage node. This study defines the concept of safe recovery criterion, which specifies the requirement for ensuring that any failed processor can be recovered in a single step using the checkpoint data stored at one of the surviving processors, as long as no more than a given number of failures occur. This study further identifies the necessary and sufficient conditions for satisfying the safe recovery criterion and presents a method for designing checkpoint storage node sets that meet these requirements. The proposed scheme allows failure recovery to be performed in a distributed manner using XOR operations.

NAND flash memory has gained its popularity in a variety of applications as a storage medium due to its low power consumption, non-volatility, high performance, physical stability, and portability. In particular, Multi-Level Cell (MLC) flash memory, which provides a lower cost and higher density solution, has occupied the largest part of NAND flash-memory market share. However, MLC flash memory also introduces new challenges: (1) Pages in a block must be written sequentially. (2) Information to indicate a page being obsoleted cannot be recorded in its spare area. This paper designs an MLC Flash Translation Layer (MFTL) for flash-memory storage systems which takes new constraints of MLC flash memory and access behaviors of file system into consideration. A series of trace-driven simulations is conducted to evaluate the performance of the proposed scheme. Our experiment results show that the proposed MFTL outperforms other related works in terms of the number of extra page writes, the number of total block erasures, and the memory requirement for the management.

The goal of the network mobility (NEMO) management is to effectively reduce the complexity of handoff procedure and keep the mobile devices connected to the Internet. Vehicle is moving so fast that it may cause the handoff and packet loss problems. Both of the problems will lower down the throughput of the network. To overcome these problems, we propose a novel NEMO protocol for vehicular ad hoc network (VANET). In freeway, since every car is moving in a fixed direction with high moving speed, the car adopting our protocol can acquire IP address from the VANET through vehicle to vehicle communications. The vehicle can rely on the assistance of the front vehicle to execute the pre-handoff procedure or it may acquire its new IP address through multi-hop relays from the car on the lanes of the same or opposite direction and thus reduces the handoff delay and maintain the connectivity to the Internet. Simulation results have shown that the proposed scheme is able to reduce both handoff delay and packet loss rate.

The problem of cache sharing for supporting data access in mobile ad hoc networks is studied in this paper. The key to this problem is to discover a requested data item in an efficient manner. In the paper, we propose two caching protocols, IXP and DPIP, which distinguish themselves from the existing ones in that they fully exploit in-zone broadcasts to facilitate cache sharing operation. In particular, the DPIP protocol offers an implicit index push property, which is highly useful for enhancing cache hit ratio in the neighborhood of a data requester node. Moreover, our protocols also exploit the broadcasts to facilitate the design of a simple but efficient count-based cache replacement scheme. Performance study shows that the proposed protocols can significantly improve the performance of data access in a mobile ad hoc network.

In this paper, we present a novel protocol for disseminating data in broadcast environments such that view consistency, a useful correctness criterion for broadcast environments, is guaranteed. Our protocol is based on concurrency control information that is constructed by the server and is broadcasted at the beginning of each broadcast cycle. The concurrency control information mainly captures read-from relations among update transactions. A salient feature of the protocol is that the concurrency control information is small in size, but precise enough for reducing unnecessary abortion of mobile transactions. The small-sized concurrency control information implies low communication overhead on broadcasting system. In addition, the computation overheads imposed by the algorithm on the server and the clients are low. We also address the reliability issue of wireless communication and the incorporation of a prefetching mechanism into our protocol. Simulation results demonstrate the superiority of our protocol in comparison with existing methods. Furthermore, we have extended our protocol to deal with local view consistency which requires that all mobile transactions submitted by the same client observe the same serial order of update transactions

This paper investigates the impact on the power saving mechanism (PSM) of the cellular digital packet data (CDPD) caused by random frame errors and losses. To combat such random frame errors and losses, a selective repeat (SR) protocol of automatic repeat request (ARQ) protocols in charge of recovery of garbled/lost frames is combined with the original PSM of CDPD and then study the enhanced PSM and investigate the effect of channel conditions including bit error rate and frame loss probability as well as frame buffer size and window size of SR-ARQ to the PSM through numerical examples. The results provided in this paper are able to serve as guidelines on system design and parameter setting for CDPD when an imperfect channel is taken into consideration to reflect the realistic situation.

We propose a new quorum-based scheme for managing replicated data in distributed systems. We first introduce a concept called difference pair to establish the basics for cyclic read-write coteries. A simple and efficient model is then presented to facilitate the construction of read-write coteries. The read-write coteries generated by the model are strictly symmetric. Our model can be applied to an arbitrary number of copy sites. More importantly, by introducing a parameter in the construction model, our scheme offers the flexibility of adjusting the sizes of read and write quorums. Such flexibility allows read and write quorums to be readily tailored for each individual data item according to its own request demand. Enhancement of data availability is also addressed by our model.

In this paper, we propose a fault-tolerant routing scheme for meshes with solid faults. A Rag bit is introduced for guiding misrouted messages. By fully utilizing virtual channels of each class, our algorithm uses only three virtual channels to ensure the property of deadlock freeness. Our scheme is able to handle solid faults whose associated fault rings overlap. In addition, the proposed algorithm can be used to route messages when fault regions touch the boundaries of the mesh.

This paper presents a model for designing adaptive wormhole routing algorithms for meshes without virtual channels. The model restricts the locations where some turns can be taken so that deadlock is avoided. In comparison with previous methods, the degree of routing adaptiveness provided by the model is more even for different source-destination pairs. The mesh network may benefit from this feature in terms of communication efficiency. Simulation results show that the even adaptiveness provided by the odd-even turn model makes message routing less vulnerable to nonuniform factors such as hot spot traffic. In addition, this property results in a smaller fluctuation of the network performance with respect to different traffic patterns.

A new quorum-based replica control scheme for managing replicated data in distributed systems is proposed. We first introduce a concept called relaxed difference pair to establish the basics for cyclic read-write coteries. A simple and efficient model is then presented to facilitate the construction of read-write coteries. The read-write coteries generated by the model are symmetric. The proposed scheme can be applied to arbitrary number of data copies. More importantly, by introducing a parameter in the construction model, our scheme provides the flexibility of adjusting the sizes of read and write quorums. Such flexibility allows one to construct a read-write coterie that best suits the environment of the target system.

This paper presents a submesh allocation scheme for two-dimensional mesh systems. The submesh detection process considers only those available free submeshes that border from the left on some allocated submeshes or have their left boundaries aligned with that of the mesh. Fragmentation in the system can be reduced as a result. More importantly, we present an efficient approach to facilitate the detection of such available submeshes. The basic idea of the approach is to place the allocated submeshes of the busy set in a certain order so as to reduce the complexity of subtraction operations required for submesh detection. The method is simple and causes an amount of overhead which is only a fraction of that produced by previous algorithms. Extensive simulation has been conducted to evaluate the performance of the proposed scheme. The results show that when allocation overhead is considered, the proposed scheme may outperform previous methods.

This paper presents a fault-tolerant multicast scheme for hypercube multicomputers. The method is based on the routing capability information that is stored in each node. In comparison with the previous schemes, this information is able to capture the fault status more precisely. Two multicast algorithms are presented in the paper. These algorithms multicast messages in an attempt to minimize derouting so that time optimality can be achieved. Moreover, the routing capability information is used to guide derouting in an efficient manner when such needs arise. The amount of traffic incurred is addressed in the paper. The hardware design for the algorithms is also discussed. Extensive simulation has been conducted to evaluate the performance of the scheme. The results show the effectiveness of the proposed algorithms.

Jia (1995) proposed a multicast scheme, using propagation trees, to ensure the total ordering (including causal ordering) delivery of messages for group communication. Our study indicates that causal relation between some messages may not actually be presented in this protocol. We then present a revised approach for closed group communication.

The concept of routing capability is proposed to assist fault-tolerant routing in hypercubes. Routing capability is defined with respect to the entire spectrum of distance. As a result, the amount of information that is useful for message routing is increased. An algorithm is presented to facilitate efficient fault-tolerant routing of messages. The algorithm routes a message in an attempt to minimize derouting. Furthermore, the concept of directed routing capability which contains more useful information for fault-tolerant routing is introduced. Simulation results demonstrate the usefulness of our approach.

This paper addresses fault-tolerant routing which is concerned with finding feasible minimum paths in a faulty hypercube. The concept of routing capability, which is defined with respect to the entire spectrum of distance, is proposed to assist routing function. The amount of information that is useful for message routing is increased with our scheme. The proposed algorithm routes a message in an attempt to minimize derouting. In particular, it makes use of the information embedded in routing capabilities to establish a path for a message for which an upper bound on its length may be determined at the source. We then propose the notion of directed routing capability which captures more useful information for shortest path routing in comparison with undirected counterpart. Routing in hypercubes with link failures is also addressed.

We investigate fault-tolerant routing which aims at finding feasible minimum paths in a faulty hypercube. The concept of unsafe node and its extension are used in our scheme. A set of stringent criteria is proposed to identify the possibly bad candidates for forwarding a message. As a result, the number of such undesirable nodes is reduced without sacrificing the functionality of the mechanism. Furthermore, the notion of degree of unsafeness for classifying the unsafe nodes is introduced to facilitate the design of efficient routing algorithms which rely on having each node keep the states of its nearest neighbors. We show that a feasible path of length no more than the Hamming distance between the source and the destination plus four can always be established by the routing algorithm as long as the hypercube is not fully unsafe. The issue of deadlock freeness is also addressed in this research. More importantly, another fault-tolerant routing algorithm, which requires only a constant of five virtual networks in wormhole routing to ensure the property of deadlock freeness for a hypercube of any size, is presented in this paper.

We propose an approach for implementing rollback recovery in a distributed computing system. A concept of logical ring is introduced for the maintenance of information required for consistent recovery from a system crash. Message processing order of a process is kept by all other processes on its logical ring. Transmission of data messages are accompanied by the circulation of the associated order messages on the ring. The sizes of the order messages are small. In addition, redundant transmission of order information is avoided, thereby reducing the communication overhead incurred during failure free operation. Furthermore, updating of the order information and garbage collection task are simplified in the proposed mechanism. Our approach does not require information about message processing order be written to stable storage; in fact, the time consuming operations of saving information in stable storage are confined to the checkpointing activities. When failures occur, a surviving process need roll back only if some preceding order information is totally lost, which is relatively unlikely considering the ever growing speed of communication networks. It is shown that a system can recover correctly as long as there exists at least one surviving process.

The paper presents a process-replication protocol which aims at providing fault-tolerance as well as performance improvement to applications such as long-running and real-time tasks. Identical delivering order of messages are enforced on all replicas of a troupe using multicasts for inter- and intra-troupe communication. The detailed design of the protocol is given in the paper. The protocol is self-contained in the sense that crashes in a troupe are handled internally without affecting the operation of other troupes. The crash-handling procedure is simple and associated overhead during fail-free operation is small. The protocol takes advantages of the redundancy of processes to expedite the completion of a distributed task by speeding up the determination of message sequences and transmission of outgoing data messages at the expense of small control messages. Simulation is carried out to show the performance improvement.>

In this paper we propose a new mechanism for implementing checkpoint/rollback-recovery in a distributed computing system. A logical-ring structure is introduced for the maintenance of recovery-related information. Message processing order of a process is maintained by all other processes on its associated ring. It requires no time-consuming operations of writing order information into stable storage. As a result, fail-free overhead is small. When failures occur, only failed processes have to roll back to their latest checkpoints. Surviving processes continue execution without being blocked. Output commit is fast as it needs no synchronization before a message is sent to the outside world.>

A set of routing criteria is proposed for circuit-switched hypercubes that exploit the flexibility provided by the hypercube. The routing criteria are provably deadlock-free and route messages along shortest paths. The number of shortest paths allowed by the routing criteria is more than one for most source-destination pairs. It is shown that the flexibility provided by the routing criteria can be used to limit the negative effects due to component-failures. The exact number of disrupted source-destination pairs are derived in the presence of a single faulty link or a single faulty node. It is shown that these numbers can be minimized using the relabeling techniques proposed. It is shown that the criteria, if used effectively, lead to a significant improvement in performance over the e-cube routing strategy for non-uniform traffic.>

A study is made of three dynamic load balancing policies in distributed systems with service interruptions, namely, sender initiated, receiver initiated, and a combination of the two, in different cases: performing and not performing load-balancing functions while the computers are in the middle of interruptions. The policies are analyzed by using decomposition approximation and matrix-geometric solution techniques. Simulations are used to validate the analytical results. The policies are compared to each other and to no load balancing. Sensitivities of the performance to the characteristics of interruptions and design parameters are studied. It is concluded that load balancing has a significant advantage in improving performance. Performing load-balancing functions while the computers are in the middle of interruptions also provides considerable performance improvement.>

Optimal allocation of redundant resources in distributed computing systems is studied. In the model, the triple module redundancy (TMR) scheme is adopted to enhance the reliability of the operations. A retrieval request from a site for a database will be processed by three database servers. The output results will be obtained by majority voting. The objective is to find the number of database copies and their locations that optimize the total operation cost. Both static and dynamic allocation environments are considered. The problem is formulated as a zero/one integer programming problem. Preliminary test results show that the algorithm has fast convergence and provides a tight lower bound for the optimal operational cost. In particular, it offers high flexibility in terms of termination criteria, which makes it useful in a dynamic allocation environment.>

A new resource allocation model is presented in which a given number of copies of a single resource are allocated to the processing sites in such a way that the total communication cost incurred is minimized. The accessing scheme considers both the communication costs and the load levels at the resource sites. Load leveling is imposed as a constraint. This improves system throughput as well as response time. The allocation provided by the model reflects the realistic environment more accurately and therefore gives a better dynamic performance. It is shown that the model can be extended to include other costs such as installation cost and communication cost due to 'write' accesses.>

Optimal allocation of redundant resources in distributed computing systems is studied. In this model, a request from a processing site for a resource can be satisfied by any one of the copies. Among the redundant copies of the resources, the least-expensive and the second-least-expensive ones are considered for accessing by each processing site, which is measured in terms of communication cost. This access scheme offers to encompass some of the intrinsically important features, such as graceful degradation and reliability consideration, in the design model. The increase of communication cost due to the failures of resources should be gradual to maintain the system performance. With the present formulation, the goal of the allocation is to minimize the total communication cost incurred. The Lagrangian relaxation and subgradient methods are applied to solve this problem. An efficient algorithm based on these techniques, and computational results, are presented.>