This paper proposes a method to improve the routing performance of hierarchical Delaunay networks. Delaunay network is a network topology for peer-to-peer systems which is based on the Delaunay triangulation of point set associated with the set of peers. It has a favorable property as a topology for peer-to-peer systems such that a greedy routing scheme always delivers a given message to its destination. The key idea of the proposed method is to apply a hash function to the address of participant peers. More concretely, by applying a hash function to the coordinate point of the peers, we could realize an overlay so that the number of hops to the destination in the original network could be effectively reduced.

This paper proposes a batch-based method to effectively relax the flash crowd in P2P live streaming systems with the aid of the cloud. The role of the cloud is two folds. The first one is to determine the concrete overlay structure of batches consisting of nodes waiting in the request queue which is restricted to be a multiple-spanning-tree. With this approach we could maximize the resource utilization in each batch without increasing the load of the tracker. The second one is to feed recently issued chunks to the gateway of batches before connecting them to the existing overlay. The performance of the proposed method is evaluated by simulation. The result of simulations indicates that: 1) the proposed method reduces the waiting time of conventional method by 80%, and 2) the amount of data fetched from the cloud could effectively be reduced by decreasing the size of batches.

This paper proposes a batch-based method to effectively relax the flash crowd in P2P live streaming systems with the aid of the cloud. The role of the cloud is twofolds. The first one is to determine the concrete overlay structure of batches consisting of nodes waiting in the request queue which is restricted to be a multiple-spanning-tree. With this approach we could maximize the resource utilization in each batch without increasing the load of the tracker. The second one is to feed recently issued chunks to the gateway of batches before connecting them to the existing overlay. The performance of the proposed method is evaluated by simulation. The result of simulations indicates that: 1) the proposed method reduces the waiting time of conventional method by 80%, and 2) the amount of data fetched from the cloud could effectively be reduced by decreasing the size of batches.

This paper proposes a cost-effective index poisoning scheme for unstructured Peer-to-Peer (P2P) file sharing systems. Index poisoning is a technique which alters the index of illegal shared files so that they could not be reached by any peer which wishes to access them through the P2P. The proposed scheme is a combination of the following three periodical injections of the altered index: 1) injection to the owner of illegal files, 2) injection to upstream peers by setting a long lifetime to the index, and 3) injection to downstream peers by setting a short lifetime to the index. Results of simulations indicate that the proposed scheme attains almost the same performance with a naive scheme which injects altered copy with long lifetime to all peers, with a significant reduction of the cost, i.e., it reduces the spatial cost to one third and the network cost to a half.

In this work we present randomly optimized grid graphs that maximize the performance measure, such as diameter and average shortest path length (ASPL), with subject to limited edge length on a grid surface. We also provide theoretical lower bounds of the diameter and the ASPL, which prove optimality of our randomly optimized grid graphs. We further present a diagonal grid layout that significantly reduces the diameter compared to the conventional one under the edge-length limitation. We finally show their applications to three case studies of off-and on-chip interconnection networks. Our design efficiently improves their performance measures, such as end-to-end communication latency, network power consumption, cost, and execution time of parallel benchmarks.

In this paper, we consider the problem of constructing scale-free networks in a semi-deterministic manner. Scale-free networks have several favorable properties as the topology of interconnection networks such as the short diameter and the quick message propagation. The proposed algorithm is an extension of the Bulut's algorithm for constructing scale-free networks with designated minimum degree k and maximum degree m, such that: (1) it determines the ideal number of edges derived from the ideal degree distribution, and (2) after connecting each new node to k existing nodes as in the Bulut's algorithm, it adjusts the number of edges to the ideal value by conducting add/removal of edges. We prove that such an adjustment is always possible if the number of nodes in the network exceeds m2/k+m.

This paper studies the load balancing problem in distributed systems designed for massively multiplayer online role-playing games (MMORPGs). More concretely, we consider a distributed system of master-worker type in which each worker is associated with a particular region in the game field, and propose a scheme to balance the load of workers as much as possible. The basic idea of the proposed scheme is to dynamically adjust the number of workers associated with each region according to the number of players in the region. The performance of the scheme is evaluated by simulation. The simulation results indicate that it reduces the response time of a previous scheme proposed by Yu et al. by about 50%, which varies depending on the mobility pattern of the players.

In this paper, we propose a method to maintain a Peer-to-Peer (P2P) overlay in live streaming systems based on a hybrid of Content Delivery Network (CDN) and P2P Technology. The key idea of the proposed method is to explicitly take into account the upload capacity of each peer in selecting peers which can directly receive the live stream from a cache server in the CDN. In addition, it prepares several backup peers to support the task of upload in such a way that a stream is fed to a P2P client if the local buffer at the client becomes scarce. The performance of the proposed scheme is evaluated by simulation.

In this paper, we proposed a user management scheme for Peer-to-Peer (P2P) contents sharing systems. The proposed scheme assumes the existence of peer groups which provide sensitive, confidential contents to the group members, and controls the membership through the collaboration among group members. As the key technique, we use the delegation of the task of qualification to few selected group members, and a voting mechanism based on the (n, t)-threshold cryptosystem. We implemented a prototype of the proposed scheme using JXTA framework, and evaluated the performance experimentally. The experimental result indicates that although the time required for the admission control is proportional to the group size and the threshold used in the threshold cryptosystem, we can significantly reduce it by executing it in parallel. We also demonstrate the availability of the scheme by applying it to the P2P live video streaming system.

In this paper, we consider the problem of minimizing switching overhead of burst scheduling in time slicing mobile TV broadcast systems. This problem was formulated by Hsu and Hefeeda, and was given an elegant scheme with approximation ratio of at least two. Our proposed scheme significantly improves the previous scheme. More concretely, it generates a burst schedule for mobile TV systems whose switching overhead is at most (1/ln 2)+ε ≃ 1.4427 times of optimum, where ln is the natural logarithm and \epsilon is arbitrary positive constant. Our scheme is a combination of a binary partion of burst cycles and a shifting method which was originally proposed for the analysis of unit disk graphs.

In this paper, we consider the problem of automatic tag attachment to the documents distributed over a P2P network aiming at improving the efficiency of file search in such networks. The proposed scheme combines text clustering with a modified tag extraction algorithm, and is executed in a fully distributed manner. We conducted experiments to evaluate the accuracy of the proposed scheme. The result of experiments indicates that for more than 90% of documents, it attaches the same tags as the ones attached by human reviewers.

In hierarchical Peer-to-Peer (P2P) systems, several selected peers are promoted as super-peers to provide an efficient lookup service for the ordinary peers, although it would cause a service bottleneck and a heavy workload at the point of the promoted peers. In this paper, we propose a two-level caching architecture consisting of level-1 cache and level-2 cache to relax such bottlenecks in hierarchical P2Ps. Each cache is partitioned into two parts so that it could manage both of static and dynamic data in a space-efficient manner, where static data indicates popular pages which are frequently requested by many users and dynamic data indicates pages which may not be popular but repeatedly requested during a short time period. The performance of the proposed method is evaluated by simulation. The result indicates that our caching protocol significantly reduces the network traffic and exhibits a high hit rate even in small cache sizes.

In this paper, we propose a new network topology for P2P DHT (Distributed Hash Table) which provides a scalable lookup service for the peers participating in Peer-to-Peer (P2P) networks. The proposed topology is a contracted graph of the star graph, and realizes a short diameter with a small degree compared with conventional hyper cubic DHTs such as Chord and Kademlia.

In branch-and-bound (B&B) schemes for solving a minimization problem, a better lower bound could prune many meaningless branches which do not lead to an optimum solution. In this paper, we propose several techniques to refine the lower bound on the makespan in the multiprocessor scheduling problem (MSP). The key idea of our proposed method is to combine an efficient quadratic-time algorithm for calculating the Fernández's bound, which is known as the best lower bounding technique proposed in the literature with two improvements based on the notions of binary search and recursion. The proposed method was implemented as a part of a B&B algorithm for solving MSP, and was evaluated experimentally. The result of experiments indicates that the proposed method certainly improves the performance of the underlying B&B scheme. In particular, we found that it improves solutions generated by conventional heuristic schemes for more than 20 percent of randomly generated instances, and for more than 80 percent of instances, it could provide a certification of optimality of the resulting solutions, even when the execution time of the B&B scheme is limited by one minute.

In this paper, we propose a clustering scheme for unstructured P2Ps based on the notion of ``tit-for-tat'' strategy. The proposed scheme is a combination of an identification of critical links, local reconfiguration of incident links, and a retaliation rule. By adopting such a tit-for-tat strategy in selecting incident links to be disconnected while reconfiguring the underlying P2P overlay, it emerges a cooperative behavior of the participant peers. The performance of the proposed scheme is evaluated by simulation. The result of simulations indicates that under the proposed scheme, each peer can collect a large number of peers sharing similar interest, and it improves the performance of conventional clustering schemes.

In this paper, we propose a distributed algorithm to process conjunctive queries in P2P DHTs. The basic idea of the proposed scheme is to cache the search result for past conjunctive queries, and to use them to improve the efficiency of the succeeding query processing. As a concrete implementation of such result cache, we adopt Bloom filter in such a way that the cache size required for each query becomes as large as the size of each file index. The performance of the proposed scheme is evaluated by simulation. The result of simulations indicates that the proposed scheme is particularly effective for P2P DHTs with small storage size, and it reduces the amount of data transmissions to process given conjunctive queries by 49.7% compared with previous schemes.

A transposition graph is a Cayley graph in which each vertex corresponds to a permutation and an edge is placed between permutations iff they differ by exactly one transposition. In this article, we propose an efficient algorithm to find a collection of vertex-disjoint paths connecting a given source vertex s and a given set of destination vertices D. The running time of the algorithm is polynomial in the number of destination vertices, and the resultant path connecting s and each destination is longer than the distance to the destination by at most 16. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

In this paper, we propose a distributed scheme to recognize the shape of a dynamic event region in wireless sensor networks; i.e., a scheme to track the shape of a part of a given field concerned with a dynamic event such as gas leakage and a fire. The basic idea of our proposed scheme is to identif

In this paper, we propose a user management system for networked consumer electronics (nCE). The proposed system extends Tokunaga's hybrid P2P system in such a way that the inquiries concerned with client peers submitted by service-provider peers are handled by several authentication proxies instead of a centralized management peer, although client peers still have to register themselves to the centralized server. A prototype of the proposed system is implemented using JXTA framework, and is evaluated via experiments. The result of experiments indicates that the proposed system certainly reduces both the load of the centralized server and the time required for the authentication process.

In this paper, we consider a problem of finding "useful" files matching a given query in unstructured P2Ps. The proposed scheme is a variant of k-random walk, which combines a synchronization mechanism proposed by Lv et al. with a mechanism to evaluate the usefulness of discovered files. In addition, we apply a variant of popularity-biased k-random walk to accelerate the file search in normal k-random walk under uniform distribution. The goodness of the scheme is evaluated by simulation. The result of simulations indicates that the proposed biased k-random walk scheme certainly finds useful files in short time, without significantly increasing the number of message transmissions.

In this paper, we propose a hierarchical architecture to realize a real-time file search in P2P systems. The proposed architecture consists of three layers. Index of files held by the peers in the bottom layer is stored at the peers in the middle layer, and the correlation of peers in the two bottom layers is controlled by the peers in the top layer using the notion of tags. With such notion of tags, we can realize a quick upload of the file indexes and a quick forwarding of a given query requesting a shared file to a relevant peer. We implemented a prototype of the proposed system. The result of preliminary experiments conducted using the prototype system indicates that an upload of a file index and a query forwarding to a relevant peer take few second and 100 ms, respectively.

IEEE802.11e standard adopts several important techniques to guarantee the quality of service (QoS) of multimedia communications in wireless LAN. A key technique introduced in the standard is an efficient media access control based on hybrid coordination function (HCF), in which each flow is assigned an appropriate transmission opportunity (TXOP) to satisfy several requirements on the flow such as the delay bound and the communication bandwidth. Although it could provide an efficient tool to guarantee the QoS in wireless LAN, HCF has a serious drawback such that a useless bandwidth assignment frequently occurs, which is primarily due to the limitation of the scheme such that all flows share the same service interval (SI). In this paper, we propose a new scheduling scheme that associates each flow with its own SI according to the hardness of the delay bound. The effect of the scheme is experimentally evaluated by simulation. The result of simulations indicates that the number of admitted flows and the data transmission rate certainly increase by the proposed scheme

In wireless LAN, several terminals could share a single communication channel by using an appropriate media access control (MAC) mechanism. However, existing MAC schemes for wireless LAN have serious drawbacks such that it significantly degrades the throughput if it frequently occurs a collision of frames or a useless assignment of communication bandwidth. In this paper, we propose a new MAC scheme for wireless LAN to realize an efficient utilization of the communication bandwidth while suppressing the probability of frame collisions. The basic idea of the scheme is to conduct a channel assignment for each group which is dynamically constructed based on the unique identifier that is assigned to each terminal beforehand. The scheme could be customized by appropriately tuning parameters according to the given communication environment. The effect of the scheme is estimated by simulation. By the result of simulations, it is confirmed that the proposed scheme could achieve a stable performance for any access frequency.

In this paper, we propose a new class of parallel branch-and-bound (B&B) schemes. The main idea of the scheme is to focus on the functional parallelism instead of conventional data parallelism, and to support such a heterogeneous and irregular parallelism by using a collection of autonomous agents distributed over the network. After examining several design issues toward the implementation of a prototype of the distributed B&B system, we illustrate the result of our preliminary experiments conducted to estimate the performance of the proposed scheme. The result shows that it could cause a significant performance improvement if each agent autonomously changes its function type according to the change of the underlying environment.

This paper proposes a new linkage identification method based on the notion of evolution of linkages, which is designed for evolutionary computation schemes to solve combinatorial optimization problems (COP). Linkage identification is a task to identify an appropriate fragment of genes contained in a chromosome that is expected to significantly increase the fitness of the overall individuals. As a concrete target problem of the proposed scheme, we focus on the traveling salesman problem (TSP) that is known as a typical COP. The performance of the scheme is experimentally evaluated by using TSPLIB, and is compared with the performance of previous schemes. The result of experiments shows that the proposed scheme really improves the performance of the previous scheme, and the amount of improvement is 42.7% in the best case.

This paper proposes a fast branch-and-bound algorithm for solving the multiprocessor scheduling problem. The key point of our method is the proposal of an efficient quadratic algorithm for calculating the Fernandez and Bussell's (1973) lower bound. In the following, we discuss about the trade-off between the cost for calculating a lower bound and the size of pruned subtrees. Several experiments are conducted to evaluate the goodness of the proposed method.

In this paper, we consider the problem of multicasting a message in k-ary n-cubes under the store-and-forward model. The objective of the problem is to minimize the size of the resultant multicast tree by keeping the distance to each destination over the tree the same as the distance in the original graph. In the following, we first propose an algorithm that grows a multicast tree in a greedy manner, in the sense that for each intermediate vertex of the tree, the outgoing edges of the vertex are selected in a non-increasing order of the number of destinations that can use the edge in a shortest path to the destination. We then evaluate the goodness of the algorithm in terms of the worst case ratio of the size of the generated tree to the size of an optimal tree. It is proved that for any k/spl ges/5 and n/spl ges/6, the performance ratio of the greedy algorithm is c/spl times/kn-o(n) for some constant 1/1.2/spl les/c/spl les/1/2.

We propose a new scheduling method that can simultaneously achieve two main goals of task scheduling in distributed parallel systems; i.e., to minimize the execution time of a parallel job without disturbing the execution of other jobs. We challenge to achieve those goals by introducing a new scheduler, called active scheduler, that controls the priority of parallel programs dynamically and balances the workload of computers, depending on the current status of the runtime environment. The priority of parallel programs is controlled by controlling the concurrency of the programs. We implemented a prototype system to evaluate the effectiveness of active scheduler. The results of experiments imply that the overhead of introducing the active scheduler is bounded by 15% of the original execution time, and it is in fact effective to adjust the execution of parallel programs to an actual distributed parallel processing environment in which many users execute their jobs at the same time.

In this paper, we consider the problem of constructing a multicast tree in the star graph under the single-port communication model. Unlike previous studies for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex and propose a multicast scheme for the star graph of dimension n in 1.3125 log/sub 2/ n+O(log log n) time units, that is at most 1.3125 times of a trivial lower bound.

Let G be an undirected graph with a set of vertices V and a set of edges E. Given an integer r, we assign at most r labels (representing "resources") to each vertex. We say that such an assignment is an r-configuration if, for each label c, the vertices labeled by c form a dominating set for G. In this paper, we are interested in the maximum number, D r (G), of labels that can be assigned to the vertices of graph G by an r-configuration. The decision problem ``$D_1(G)\geq K$?" (known as the domatic number problem) is NP-complete. We first investigate D r (G) for general graphs and establish bounds on D r (G) in terms of D 1 (G) and the minimum vertex degree of G. We then discuss D r (G) for d-regular graphs. We clearly have $D_r (G) \leq r(d+1)$. We show that the problem of testing if D r (G) = r(d+1) is solvable in polynomial time for d-regular graphs with |V| = 2(d+1), but is NP-complete for those with |V| = a(d+1) for some integer $a \geq 3$. Finally, we discuss cubic (i.e., 3-regular) graphs. It is easy to show $2r \leq D_r (G) \leq 4r$ for cubic graphs. We show that the decision problem for D 1 (G) = K is co-NP-complete for K = 2 and is NP-complete for K = 4. Although there are many cubic graphs G with D 1 (G) = 2, surprisingly, every cubic graph has a 2-configuration with five labels, i.e., $D_2 (G) \geq 5$ and such a 2-configuration can be constructed in polynomial time. We use this fact to show $D_r (G) \geq \lfloor 5r/2 \rfloor$ in general.

This paper studies two neighborhood information dissemination problems in the star graph (n-star): The neighborhood broadcast problem (NBP) is the problem of disseminating a message from the source vertex to all the vertices adjacent to the source vertex and the neighborhood gossiping problem (NGP) is the problem of exchanging messages among all neighboring vertices in the given graph. We propose two neighborhood information dissemination schemes in n-star under the single-port, half-duplex model: The first scheme completes a neighborhood broadcast in 1.5 log/sub 2/ n+O(1) time units and the second scheme completes a neighborhood gossiping in 2.88 log/sub 2/ n+o(logn) time units. We also derive a lower bound on the neighborhood gossiping of 2.88 log/sub 2/ n+O(1) time units, which implies that the latter scheme is optimal with respect to the leading term.

In this paper, we propose a simple and nonadaptive fault-tolerant broadcast scheme in the star graph under the single-port, half-duplex communication model. The proposed scheme can tolerate up to n-2 vertex and/or edge faults in the star graph with nl vertices and takes at most n+4 more time units than an optimal nonadaptive broadcast scheme. Since it takes at least [log/sub 2/(nl)]=/spl Theta/(n log n) time units to complete a broadcast under the single port model, the gap between lower and upper bounds is fairly small.

Using a model based on the omni-directional robots developed at the Institute of Physical and Chemical Research (RIKEN), we discuss the possibility of automatically generating a collision avoidance algorithm for autonomous mobile robots. To this end, we show that an effective collision avoidance algorithm for two robots can be generated by a very simple learning algorithm that simulates a naive human trial-and-error learning process, using only the robots' sensor outputs and a suitable reward function, where the exact form of the reward function is also learned autonomously by the robots. We also discuss how a robot can use its "experience" gained in a simple environment to adjust itself to a more complex environment, by automatically generating a collision avoidance algorithm for a three-robot situation utilizing a reduced state space resulting from the learning process for the case of two robots. The results of computer simulation and the experiments conducted at RIKEN using physical robots demonstrate the effectiveness of the collision avoidance algorithms generated and our learning-based approach.

Let U be a given set of nodes of a parallel computer system and assume that each node u in U has a piece of information $t(u)$ called a token. This paper discusses the problem of each $u \in U$ broadcasting its token $t(u)$ to all nodes in U. We refer to this problem as the group-gossiping problem, which includes the (conventional) gossiping problem as a special case. In this paper, we consider the group-gossiping problem in n-cubes under a circuit-switching model and propose an optimal group-gossiping algorithm for n-cubes under the model.

A mesh-bus computer is a parallel computer in which nodes (i.e., processors) are arranged on a two-dimensional array, and nodes on each row and nodes on each column, respectively, are connected by a shared bus. The nodes communicate with each other by exchanging packets through shared buses in CREW manner. Suppose that each node initially contains a piece of information called a token. A gossiping problem is the routing problem of exchanging tokens among all nodes in the computer, which has been studied extensively as a basic communication scheme for sharing information among nodes in a parallel computer. In this paper, we propose three gossiping algorithms for mesh-bus computers assuming that each packet can carry at most l tokens in a step, where l is a function of the number of all nodes. It is shown that by selecting the fastest algorithm among them, for each given function l, a lower bound on the gossiping time can be attained asymptotically.

The distributed k-mutual-exclusion problem (k-mutex problem) is the problem of guaranteeing that at most k processes at a time can enter a critical section at a time in a distribution system. A method proposed for the solution of the distributed mutual exclusion problem (i.e., 1-mutex problem) by D. Barbara and H. Garcia-Molina (1987) is an extension of majority consensus and uses coteries. The goodness of coterie-based 1-mutex algorithm strongly depends on the availability of coterie, and it has been shown that majority coterie is optimal in this sense, provided that: the network topology is a complete graph, the links never fail, and p, the reliability of the process, is at least 1/2. The concept of a k-coterie, an extension of a coterie, is introduced for solving the k-mutex problem, and lower and upper bounds are derived on the reliability p for k-majority coterie, a natural extension of majority coterie, to be optimal, under conditions (1)-(3). For example, when k=3, p must be greater than 0.994 for k-majority coterie to be optimal.>

Three-dimensional VLSI (in short, 3-D VLSI) is a new device technology that is expected to realize high performance systems. In this paper, we propose an image processing architecture based on 3-D VLSI consisting of optically-connected layers. Since the optical inter-layer connection seems to have some of useful functions due to isotropic radiation of the light, we algebraicly formulate them as the picture processing operators. Moreover, we show that the operators are available for applications such as template matching. The availability of a proposed template matching algorithm is verified by simulation.