Various graph algorithms have been developed with multiple random walks, the movement of several independent random walkers on a graph. Designing an efficient graph algorithm based on multiple random walks requires investigating multiple random walks theoretically to attain a deep understanding of their characteristics. The first meeting time is one of the important metrics for multiple random walks. The first meeting time on a graph is defined by the time it takes for multiple random walkers to meet at the same node in a graph. This time is closely related to the rendezvous problem, a fundamental problem in computer science. The first meeting time of multiple random walks has been analyzed previously, but many of these analyses focused on regular graphs. In this paper, we analyze the first meeting time of multiple random walks in arbitrary graphs and clarify the effects of graph structures on expected values. First, we derive the spectral formula of the expected first meeting time on the basis of spectral graph theory. Then, we examine the principal component of the expected first meeting time using the derived spectral formula. The clarified principal component reveals that (a) the expected first meeting time is almost dominated by $n/(1+d_{ m std}^2/d_{ mavg}^2)$ and (b) the expected first meeting time is independent of the starting nodes of random walkers, where n is the number of nodes of the graph. davg and dstd are the average and the standard deviation of weighted node degrees, respectively. Characteristic (a) is useful for understanding the effect of the graph structure on the first meeting time. According to the revealed effect of graph structures, the variance of the coefficient dstd/davg (degree heterogeneity) for weighted degrees facilitates the meeting of random walkers.

In this paper, we reveal inherent robustness issues of XCP (eXplicit Control Protocol), and propose extensions to XCP for increasing its robustness. XCP has been proposed as an efficient transport-layer protocol for wide-area and high-speed network. XCP is a transport-layer protocol that performs congestion control based on explicit feedback from routers. In the literature, many performance studies of XCP have been performed. However, the effect of traffic dynamics on the XCP performance has not been fully investigated. In this paper, through simulation experiments, we first show that XCP has the following problems: (1) the bottleneck link utilization is lowered against XCP traffic dynamics, and (2) operation of XCP becomes unstable in a network with both XCP and non-XCP traffic. We then propose XCP-IR (XCP with Increased Robustness) that operates efficiently even for dynamic XCP and non-XCP traffic.

The research on Delay Tolerant Networks (DTN) has been activated aiming at a variety of potential applications toward ubiquitous society. The vehicular network is one of the promising areas for applying DTN. In this paper, the end-to-end delay characteristics for vehicular ad-hoc broadcast DTN is analyzed, where the dynamic vehicle mobility model is introduced. The analysis is applied to the two realistic road models, that is, one-way and two-way traffic models. The simulation study demonstrates validity of our analysis for use in generic vehicle networks.

In this paper, we analyze the stability of XCP (eXplicit Control Protocol) in a network with heterogeneous XCP flows (i.e., XCP flows with different propagation delays). Specifically, we model a network with heterogeneous XCP flows using fluid-flow approximation. We then derive the conditions that XCP control parameters should satisfy for stable XCP operation. Furthermore, through several numerical examples and simulation results, we quantitatively investigate effect of system parameters and XCP control parameters on stability of the XCP protocol. Our findings include: (1) when XCP flows are heterogeneous, XCP operates more stably than the case when XCP flows are homogeneous, (2) conversely, when variation in propagation delays of XCP flows is large, operation of XCP becomes unstable, and (3) the output link bandwidth of an XCP router is independent of stability of the XCP protocol.

In this paper, we propose a novel Autonomous Decentralized Control (ADC) scheme for indirectly controlling a system performance variable of large-scale and wide-area networks. In a large-scale and wide-area network, since it is impractical for any one node to gather full information of the entire network, network control must be realized by inter-node collaboration using information local to each node. Several critical network problems (e.g., resource allocation) are often formulated by a system performance variable that is an amount to quantify system state. We solve such problems by designing an autonomous node action that indirectly controls, via the Markov Chain Monte Carlo method, the probability distribution of a system performance variable by using only local information. Analyses based on statistical mechanics confirm the effectiveness of the proposed node action. Moreover, the proposal is used to implement traffic-aware virtual machine placement control with load balancing in a data center network. Simulations confirm that it can control the system performance variable and is robust against system fluctuations. A comparison against a centralized control scheme verifies the superiority of the proposal.

In this paper, we investigate the performance of Thorup's algorithm by comparing it to Dijkstra's algorithm for large-scale network simulations. One of the challenges toward the realization of large-scale network simulations is the efficient execution to find shortest paths in a graph with N vertices and M edges. The time complexity for solving a single-source shortest path (SSSP) problem with Dijkstra's algorithm with a binary heap (DIJKSTRA-BH) is O((M + N) log N). An sophisticated algorithm called Thorup's algorithm has been proposed. The original version of Thorup's algorithm (THORUP-FR) has the time complexity of O(M + N). A simplified version of Thorup's algorithm (THORUP-KL) has the time complexity of O(M α(N) + N) where α(N) is the functional inverse of the Ackerman function. In this paper, we compare the performances (i.e., execution time and memory consumption) of THORUP-KL and DIJKSTRA-BH since it is known that THORUP-FR is at least ten times slower than Dijkstra's algorithm with a Fibonaccii heap. We find that (1) THORUP-KL is almost always faster than DIJKSTRA-BH for large-scale network simulations, and (2) the performances of THORUP-KL and DIJKSTRA-BH deviate from their time complexities due to the presence of the memory cache in the microprocessor.

Spectral graph theory gives an algebraic approach to the analysis of the dynamics of a network by using the matrix that represents the network structure. However, it is not easy for social networks to apply the spectral graph theory because the matrix elements cannot be given exactly to represent the structure of a social network. The matrix element should be set on the basis of the relationship between persons, but the relationship cannot be quantified accurately from obtainable data (e.g., call history and chat history). To get around this problem, we utilize the universality of random matrices with the feature of social networks. As such a random matrix, we use the normalized Laplacian matrix for a network where link weights are randomly given. In this paper, we first clarify that the universality (i.e., the Wigner semicircle law) of the normalized Laplacian matrix appears in the eigenvalue frequency distribution regardless of the link weight distribution. Then, we analyze the information propagation speed by using the spectral graph theory and the universality of the normalized Laplacian matrix. As a result, we show that the worst-case speed of the information propagation changes up to twice if the structure (i.e., relationship among people) of a social network changes.

Spectral graph theory provides an algebraic approach to investigate the characteristics of weighted networks using the eigenvalues and eigenvectors of a matrix (e.g., normalized Laplacian matrix) that represents the structure of the network. However, it is difficult to accurately represent the structures of large-scale and complex networks (e.g., social network) as a matrix. This difficulty can be avoided if there is a universality, such that the eigenvalues are independent of the detailed structure in large-scale and complex network. In this paper, we clarify Wigner's Semicircle Law for weighted networks as such a universality. The law indicates that the eigenvalues of the normalized Laplacian matrix of weighted networks can be calculated from a few network statistics (the average degree, average link weight, and square average link weight) when the weighted networks satisfy a sufficient condition of the node degrees and the link weights.

Computer networks require sophisticated control mechanisms to realize fair resource allocation among users in conjunction with efficient resource usage. To successfully realize fair resource allocation in a network, someone should control the behavior of each user by considering fairness. To provide efficient resource utilization, someone should control the behavior of all users by considering efficiency. To realize both control goals with different granularities at the same time, a hierarchical network control mechanism that combines microscopic control (i.e., fairness control) and macroscopic control (i.e., efficiency control) is required. In previous works, Aida proposed the concept of chaos-based hierarchical network control. Next, as an application of the chaos-based concept, Aida designed a fundamental framework of hierarchical transmission rate control based on the chaos of coupled relaxation oscillators. To clarify the realization of the chaos-based concept, one should specify the chaos-based hierarchical transmission rate control in enough detail to work in an actual network, and confirm that it works as intended. In this study, we implement the chaos-based hierarchical transmission rate control in a popular network simulator, ns-2, and confirm its operation through our experimentation. Results verify that the chaos-based concept can be successfully realized in TCP/IP networks.

It is not easy to provide energy supply based on renewable energy enough to satisfy energy demand anytime and anywhere because the amount of renewable energy depends on geographical conditions and the time of day. In order to maximize the satisfaction of energy demand by renewable energy, surplus energy generated with renewable energy should be stored in batteries, and transmitted to electric loads with high demand somewhere in the electricity system. This paper proposes a novel autonomous decentralized mechanism of energy interchanges between distributed batteries on the basis of the diffusion equation and MCMC (Markov Chain Monte Carlo) for realizing energy supply appropriately for energy demand. Experimental results show that the proposed mechanism effectively works under several situations. Moreover, we discuss a method to easily estimate the behavior of the entire system by each node with the proposed mechanism, and the application potentiality of this estimating method to an efficient method working with non-renewable generators while minimizing the dependence of non-renewable energy, and an incentive mechanism to prevent monopolizing energy in systems.