Random walks on graphs are widely used for diverse applications in information science, such as data analysis, search, and network exploration; however, they often suffer from localized stagnation within densely connected subgraphs, leading to decreased exploration efficiency. To address this issue, we propose Coarse Walk, a new random walk method that probabilistically switches between the original graph G and a coarsened graph Gc. By traversing both G and Gc, Coarse Walk introduces non-local transitions without relying on global information about the entire graph, thus enabling the agent to escape local clusters. We evaluate Coarse Walk on six graph types (Random, Barábasi–Albert, Tree, Comb, Caveman, and Barbell) using six different random walk variants (SRW, BiasedRW, 3-History, NBRW, SARW, and VARW), measuring performance in terms of cover time and average hitting time. The results demonstrate that Coarse Walk significantly improves exploration efficiency for graphs with strong local substructures―such as Caveman and Barbell graphs―while providing only modest or negligible gains on graphs without prominent clusters, such as Random and Barábasi–Albert graphs.

Graphs play a crucial role in various research fields, including network science, machine learning, and data analysis. Algorithms based on random walks have become popular for information diffusion, target node research, and exploration on graphs. Random walk algorithms can be classified into local and non-local random walks. Local random walks enable transition between adjacent nodes based on predefined probabilities, while non-local random walks enable transitions that extend beyond immediate neighbors. While non-local random walks enable faster graph exploration by reaching beyond immediate neighbors, these methods typically require the agent to have full knowledge of the entire graph and the ability to freely move to any non-adjacent node, which makes them difficult to implement in large-scale networks. The aim of this study is to develop a local random walk that improves graph exploration efficiency using only limited non-local information, without requiring the agent to have knowledge of the global graph structure. Specifically, we propose a random walk called Sprint Walk, in which certain nodes in the graph record the shortest paths to a small number of anchor nodes, thereby enabling non-local-like transition behavior by the agent. Through simulation experiments, we demonstrate that Sprint Walk significantly reduces search and exploration time compared to classical local random walk algorithms, including the Simple Random Walk (SRW), Biased Random Walk (BiasedRW), Non-Backtracking Random Walk (NBRW), and Self-Avoiding Random Walk (SARW) across nine graph types.

Random walk-based algorithms are a key technique in many engineering applications, such as graph exploration, information diffusion, social network analysis, recommendation systems, machine learning, and biological network modeling, due to their adaptability, scalability, and simplicity. Although previous research has demonstrated that random walks exhibit vulnerability to certain link-rewiring attacks, a broader range of adversarial attack strategies remains largely unexplored. In this paper, we systematically investigate how diverse link deletion methods — bridge removal, hub removal, and exit blocking — combined with three link addition methods — triangle, loopback, and cluster trapping — impact the target node search (hitting time) and graph exploration (cover time) of the most standard types of random walk algorithms, such as Simple Random Walk, Degree-based Random Walk, and Memory-based Random Walk, across four types of graphs (Erdos and Rényi, Barabási-Albert (BA), voronoi, and regular) through simulation experiments. We also propose a mitigation strategy called the link reinforcement strategy, which strengthens the resilience of random walks against the aforementioned nine adversarial attacks. This paper highlights the weaknesses of random walk algorithms against adversarial attacks and presents an effective method to mitigate performance degradation caused by these attacks.

Graph coarsening is a widely used technique for reducing the complexity of large-scale networks while preserving their essential structural properties. However, coarsening alters the degree distribution, a key characteristic of graphs, making it crucial to understand these transformations. In this study, we analyze the impact of various coarsening algorithms—including RM, COARSENET, MGC, LVN, LVE, kron, and HEM—on the degree distribution of undirected graphs. We first develop an analytical model describing how the degree distribution evolves under RM-based coarsening and validate our findings using numerical experiments on diverse graph types. Additionally, we investigate the feasibility of recovering the original degree distribution from the coarsened graph using both analytical methods and graph neural networks. Our results indicate that RM retains the degree distribution more accurately for graphs with low average degree, while COARSENET and MGC cause significant alterations. Although analytical reconstruction performs well for low-degree graphs, its accuracy declines for graphs with higher connectivity. In contrast, graph neural networks consistently achieve high reconstruction accuracy across all coarsening methods, with particularly strong performance when using LVE and kron.

In this paper, we address the challenge of discovering hidden nodes in unknown social networks, formulating three types of hidden-node discovery problems, namely, Sybil-node discovery, peripheral-node discovery, and influencer discovery. We tackle these problems by employing a graph exploration framework grounded in machine learning. Leveraging the structure of the subgraph gradually obtained from graph exploration, we construct prediction models to identify target hidden nodes in unknown social graphs. Through empirical investigations of real social graphs, we investigate the efficiency of graph exploration strategies in uncovering hidden nodes. Our results show that our graph exploration strategies discover hidden nodes with an efficiency comparable to that when the graph structure is known. Specifically, the query cost of discovering 10% of the hidden nodes is at most only 1.2 times that when the topology is known, and the query-cost multiplier for discovering 90% of the hidden nodes is at most only 1.4. Furthermore, our results suggest that using node embeddings, which are low-dimensional vector representations of nodes, for hidden-node discovery is a double-edged sword: it is effective in certain scenarios but sometimes degrades the efficiency of node discovery. Guided by this observation, we examine the effectiveness of using a bandit algorithm to combine the prediction models that use node embeddings with those that do not, and our analysis shows that the bandit-based graph exploration strategy achieves efficient node discovery across a wide array of settings.

In distributed learning, the parameters of a regression or classification model are estimated from training data ob-served at each node distributed in a network without aggregating the data at one place. In particular, approximating a kernel function using Random Fourier Features (RFF) enables large-scale distributed learning. In the literature, Random Fourier Features distributed online kernel-based learning (RFF-DOKL) has been proposed; however, the impact of the network topology on the performance of RFF - DO KL has not been well understood. In this paper, we investigate the impact of the network topology among learning nodes on the performance of RFF - DO KL. Furthermore, we clarify the conditions and underlying factors that influence the performance. Specifically, we experimentally examine the convergence speed, model accuracy, and total communication cost (i.e., total number of message exchanges among learning nodes) in different types of network topologies with the same number of learning nodes.

Graphs serve as powerful representations for various real-world systems such as social networks, biological networks, and communication networks. Random walk algorithms have gained popularity for graph-based data analysis and processing, finding applications across various domains. Understanding and enhancing these algorithms is crucial for ensuring high-quality protocols, controls, and services in large-scale communication networks. While conventional random walks typically rely on local information, there is potential to improve node search efficiency by incorporating information beyond the local context. Concurrently, there is growing interest in machine learning techniques that represent data as graphs rather than vectors, known as graph and node embedding algorithms. This paper investigates whether leveraging node embedding vectors generated by such techniques can enhance the efficiency and effectiveness of random walks on a graph. To address this, we propose EmbedRW (Embedded Random Walk), which integrates node embedding techniques with random walk design. Through simulation experiments, we demonstrate that utilizing node embeddings can significantly reduce the search time for the target node across a wide range of graphs.

Random walks are being used for target node search and graph exploration in various fields, including communications and social networking. However, frequent revisits of the random walk agent to the same node degrade the efficiency of node search and graph exploration. To address this issue and improve the efficiency of node search and graph exploration, a variety of random walk-based algorithms with history, such as self-avoiding random walk (SARW) and k-history random walk (k-History), have been developed. Although these approaches accelerate node search and graph exploration with a random walk agent, they require the agent to have a non-negligible amount of memory space to store many nodes on large-scale graphs. To address this issue, it is essential to clarify efficient memory management strategies for random walk agents. In this paper, we propose novel random walk-based algorithms called BloomWalk and CuckooWalk, in which an agent performs history-based random walks on a graph using a probabilistic data structure to record previously visited nodes in memory efficiently. Experimental results demonstrate that Bloom Walk and CuckooWalk enable efficient node search on unknown graphs even with the very limited memory capacity.

TCP BBR (Bottleneck Bandwidth and Round-trip Propagation Time) has been proposed as an efficient congestion control mechanism that manages network congestion based on end-to-end measurements of bottleneck link bandwidth and round-trip time (RTT), rather than relying on the detection of packet loss events, as used by loss-based TCPs such as TCP CUBIC. Unlike loss-based congestion control mechanisms, TCP BBR estimates the available bandwidth of the bottleneck router and the network's round-trip propagation delay to adjust its congestion window, aiming to achieve the optimal operating point of the network. Numerous studies have examined the performance of TCP BBR through experiments and simulations, but analytical studies primarily focused on modeling its characteristics and behaviors during startup or steady-state phases, falling short in analyzing its dynamic behavior under changing network conditions. This paper presents a discrete-time fluid model to mathematically describe the dynamic interaction between TCP BBR flows and intermediate routers in an arbitrary network topology. The model captures the relationship among the time evolution of TCP BBR congestion window, bottleneck link bandwidth and RTT measurements, and packet queuing in routers, at the granularity of round-trip times. Through numerical examples, we demonstrate the effectiveness of our fluid model for TCP BBR and reveal optimal pacing gain settings analytically.

With the exponential growth of these networks, traditional packet-level simulations have become computationally prohibitive, making fluid-based simulations a more viable option due to their efficiency and scala-bility. We propose a novel fluid-based simulation technique that significantly accelerates the computation of intercon-nected, time-varying delay elements, which are critical in the numerical simulations of large-scale networks. Our approach leverages the inherent loops within fluid models of large-scale networks to reduce computational burden. To demonstrate the effectiveness of our technique, we introduce FLNET (Fluid-based Large-scale NETwork simulator), an efficient and scalable network simulator designed for large-scale TCP/IP networks adhering to TCP congestion control algorithms. Through rigorous experiments with FLNET, we reveal that our technique enables faster and more efficient network simulations, achieving a performance gain of approximately 3 to 5 times faster than the conventional fluid-based simulator. This paper contributes to the field by offering a scalable solution to the challenges of simulating large-scale networks, paving the way for more accurate and efficient network analysis and planning.

Random walk-based algorithms are frequently utilized to target node search and graph exploration in unknown graph structures. Unlike deterministic algorithms such as breadth-first search and depth-first search, target node search and graph exploration with random walk algorithms are expected to exhibit robustness against adversarial attacks because of their probabilistic nature. The characteristics of random walks when adversaries change the topology of the graph, known as adversarial attacks on random walks, have been just recently received attention. These attacks have been shown to significantly degrade the efficiency of target node search and graph exploration with random walks. However, questions regarding how robust random walks are against more realistic attacks persist. In this paper, we investigate adversarial attacks in the form of rewiring a limited number of links during target node search and graph exploration, particularly in scenarios where mobile agents employ random walk algorithms. The goal is to quantitatively determine how robust or vulnerable the conventional random walk algorithms are against link rewiring attacks. We consider three types of link rewiring attacks (centrality method, clustering method, and starting node method) and evaluate how they affect target node search (hitting time) and graph exploration time (cover time) of five major random walk algorithms on a graph - Simple Random Walk (SRW), Non-Backtracking Random Walk (NBRW), k-History random walk (k-History), Biased Random Walk (BiasedRW), and Vicinity Avoidance Random Walk (VARW) - in five graphs through simulation experiments.

MultiPath TCP (MP-TCP) allows the use of multiple paths between two end hosts for a single data transmission, extending the capabilities of SinglePath Transmission Control Protocol (SP-TCP). AIMD congestion control algorithm can be implemented on each subpath of the MP-TCP sender. However, the characteristics of the AIMD-type window flow control depend on the control parameters (α, β). There have been some guidelines proposed to select proper control parameters (α, β) that can achieve fair bandwidth sharing between SP-TCP and MP-TCP senders using existing MP-TCP congestion algorithms. However, current guidelines do not offer a solution that can simultaneously increase the throughput of an MP-TCP sender and ensure fairness between MP-TCP and SP-TCP senders. To address this issue, this study proposes a control parameter setting for an MP-TCP sender that can maximize the sender’s throughput and ensure fairness between SP-TCP and MP-TCP senders. We derive a fluid model of a network that includes SP-TCP and MP-TCP senders, describing the relationship between control parameters, the aggregate throughput of an MP-TCP sender, and the packet loss rate of a router.

Information-Centric Networking (ICN) has gained attention as one of the next-generation internet architectures that focuses on the data being transmitted rather than the hosts transmitting it. Due to the differences between ICN and TCP/IP networks, it is not possible to evaluate the performance of ICN using network simulators designed for TCP/IP. A number of studies have been conducted to develop ICN network simulators. However, further acceleration of ICN network simulators is expected to enable large-scale ICN network performance evaluation. In this paper, we analyze the performance bottleneck of the flow-level ICN simulator called FICNSIM (Fluid-based ICNSIMulator) by profiling its performance using the Julia language source code. Specifically, we identify the processing that is causing the performance bottleneck of FICNSIM and investigate the scalability of FICNSIM with respect to network scale.

This paper addresses a research question: - how accurately can a TCP throughput prediction model be constructed while preserving the privacy of a large number of Internet users? In the field of communication networks, accurate performance prediction of TCP flows is crucial for realizing high-quality services. In recent years, machine learning techniques have advanced and approaches for TCP throughput prediction based on centralized machine learning have emerged. However, approaches for TCP throughput prediction lack the privacy protection of Internet users and struggle to cope with a large amount of training data. Federated Learning (FL) is a novel decentralized machine learning paradigm that was introduced in 2017, allowing for multiple learning clients to collaboratively train the parameters of the global model. In this paper, we propose the Federated Learning-based PERFormance predictor (FL-PERF) of TCP flows, which builds a global TCP throughput prediction model using FL with multiple learning clients in a privacy-preserving manner. Through experiments, we investigate the accuracy of the TCP throughput prediction model obtained with FL-PERF through experiments and then discuss its privacy and scalability.

In recent years, it is expected that ICDTN (Information-Centric Delay/Disruption- Tolerant Net-working) incorporating the communication paradigm of Information-Centric Networks will be realized in an environment where communication links between nodes are intermittent, and its effectiveness has been actively investigated. To realize efficient content delivery in ICDTN, it is necessary to appropriately select content request message routing and content response message routing in a network environment where heterogeneous communication links with different characteristics are intermittent. In this paper, we first clarify how communication link heterogeneity affects the communication characteristics of content routing in ICDTN. Specifically, the heterogeneity of communication links is modeled as two types of ON/OFF models with different link avail-ability. In addition, we analytically derive the average content delivery delay when the end-to-end routing is used as the routing method for request messages and the traceback routing is used as the routing method for response messages. Furthermore, through several numerical examples, we investigate the effect of the heterogeneity of communication links on the average content delivery delay.

The first meeting time is defined by the time it takes for multiple mobile agents starting random walks from different nodes on a graph to first meet at the same node. Understanding the characteristics of the first meeting time is important to design an efficient rendezvous algorithm on a graph. In the previous work, we analyzed two mobile agents performing simple random walks with the same transition probability, and derived the expected value of the first meeting time. In this paper, we derive the spectral formula for the expected first meeting time of diverse random walk agents with different transition probabilities and movement frequencies.

In recent years, ICN (Information-Centric Networking) that focuses on the data being transferred, rather than hosts exchanging the data, has been attracting attention as one of the promising next-generation Internet architectures. It has developed that fluid model of large-scale ICN networks, which is aimed at analyzing the performance of transport layer protocols in ICN networks. In this paper, we present a flow-level ICN sim-ulator called FICNSIM (Fluid-based ICN SIMulator), which is based on the numerical solver for ICN fluid models. In particular, we introduce two types of FICNSIM implementations: a highly customizable implementation in the Python language and a high-performance implementation in the Julia language. Furthermore, through several experiments, we evaluate the effectiveness of our FICNSIM implementation. Consequently, we show that our implemented FICNSIM can perform a high-speed simulation execution compared to a conventional packet-level ICN simulator.

In recent years, Information-Centric Networking (ICN) that mainly focuses on contents that are transmitted and received instead on end hosts that transmit and receive contents has been under the spotlight. In the literature, there have been several studies on contents caching, which is one of the notable features in ICN. Furthermore, in recent years, the solution of the cache allocation problem has been studied with mathematical approaches as well as simulation experiments However, it is not well understood how the optimal cache allocation is affected by several factors such as the network topology and the total cache size. In this paper, by combining our performance analysis of ICN on an arbitrary network topology and conventional heuristic for optimization problems (i.e., generic algorithm), we investigate how the optimal cache allocation to routers is affected by several factors. Furthermore, we validate our experimental findings using a simplified model of an ICN network in the parking-lot configuration.

Acquisition and estimation of the topology of evolving and large-scale networks such as communication networks and social networks are not trivial because of their scale, complexity, and dynamics. In general, the topology of a communication network can be represented as a graph composed of many vertices and edges, and the estimation problem of the network topology can be handled as a topology estimation problem of the topology from limited knowledge on the graph. The network topology estimation problem covers a wide range of variations depending on the available data, constraints, and the objective function. Variants of the network topology estimation problem can be classified into two categories: direct and indirect. In the indirect network topology estimation problem, only information regarding the network topology to be estimated is known. In this paper, we propose an indirect network topology estimation method called TOPFLOW (network TOPology inference from FLOW sets), which estimates the topology of the entire network from the limited number of flow sets observed at measurement nodes in the network. Furthermore, we extensively investigate the effectiveness of TOPFLOW through a number of experiments with diverse networks with different structures and scales. Our findings include that the estimation accuracy grows almost linearly as the ratio of measurement nodes increases in some network topologies.

Emergence of IoT (Internet of Things) applications poses challenges on the networking infrastructure since those applications must accommodate a large number of end nodes (e.g., smart sensor devices), and the communication among those nodes are unreliable. In the last decade, DTN (Delay/Disruption-Tolerant Networking) has been actively studied by many researchers, which aims to provide efficient and reliable end-to-end communication in environments where end-to-end paths can not be reliably established. In DTN re-search, superiority and inferiority of several classes of routing mechanisms have been clarified. However, it is still an open question how effectively or ineffectively end-to-end routing performs in networks with moderately intermittent communication links. In this paper, we therefore address the following research questions: (1) does end-to-end routing perform effectively in a large-scale network with many nodes, each of which is connected with a few other nodes via intermittent communication links? (2) how is the average end-to-end message delivery delay affected by the degree (i.e., the total number of incoming and outgoing links) of source and destination nodes? To answer the above research questions, we analytically derive the average message delivery delay with end-to-end routing on a complex network with an arbitrary degree distribution.

A blind search in a network is used to discover a target node without detailed knowledge on the network. Because of its simplicity and the robust against network uncertainty, the blind search has been widely utilized by diverse applications in different types of networks (e.g., unstructured P2P (Peer-to-Peer) networks, ICNs (Information Centric Networks), mobile ad-hoc networks, and social networks). One of the major drawbacks of the blind search is its inefficiency; i.e., a large number of message exchanges is unavoidable for shortening the search time. In this paper, we propose an efficient blind search method utilizing the rendezvous of multiple random walkers, whose transition probabilities are adjusted based on our analysis results. Through simulation experiments, we show that the performance of the proposed search method is comparable with the flooding, which is the fastest but the least efficient method among blind search methods, and that it requires much smaller message exchanges than the flooding. We also show that the proposed search method works more effectively in scale-free networks than in non-scale-free networks.

Influence maximization in a social network has been intensively studied, motivated by its application to so-called viral marketing. The influence maximization problem is formulated as a combinatorial optimization problem on a graph that aims to identify a small set of influential nodes (i.e., seed nodes) such that the expected size of the influence cascade triggered by the seed nodes is maximized. In general, it is difficult in practice to obtain the complete knowledge on large-scale networks. Therefore, a problem of identifying a set of influential seed nodes only from a partial structure of the network obtained from network sampling strategies has also been studied in recent years. To achieve efficient influence propagation in unknown networks, the number of sample nodes must be determined appropriately for obtaining a partial structure of the network. In this paper, we clarify the relation between the sample size and the expected size of influence cascade triggered by the seed nodes through mathematical analyses. Specifically, we derive the expected size of influence cascade with random node sampling and degree-based seed node selection. Through several numerical examples using datasets of real social networks, we also investigate the implication of our analysis results to influence maximization on unknown social networks.

In recent years, expectations for large-scale wireless sensor networks have been rapidly increased due to miniaturization, cost reduction, reduction in power consumption of wireless sensor devices, and the emergence of wireless sensor network applications such as IoT (Internet Of Things). However, in addition to the uncertainty inherent in wireless sensor networks, due to the uncertainty caused by the expansion of wireless sensor networks, it is not easy to realize a highly efficient and reliable large-scale wireless sensor network. The uncertainty of wireless sensor networks is classified into three types: the uncertainty of nodes such as sensor nodes and sink nodes, the uncertainty of wireless communication links among nodes, and the uncertainty of traffic transferred over the wireless sensor network. In this paper, as a wireless communication standard, we focus on IEEE 802.15.4, which is designed for short-range wireless networks called PANs (Personal Area Networks), and analyze large-scale wireless sensor networks using fluid approximation. Specifically, IEEE 802.15.4 large-scale wireless sensor networks are analyzed by extending the modeling approach for generic CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) wireless networks. Moreover, our analysis makes it possible to probabilistically model temporal fluctuation of wireless communication ranges of nodes as network uncertainty. As a result, our analysis clarifies the effect of link uncertainty on the average message delivery delay in wireless sensor networks.

To realize an efficient DTN (Delay/Disruption-Tolerant Networking) routing, it is required to quickly deliver the message from the source node to the destination node as well as to quickly delete disused message replicas from the network. Epidemic routing, which indefinitely forwards message replicas to all encountered nodes, realizes the near-optimal message delivery delay when a limited number of messages are transferred. However, its performance is significantly degraded when a number of messages are transferred simultaneously. In our previous work, we have proposed a simple but effective extension to epidemic routing called restrained epidemic routing, which intentionally suppresses message forwardings at the later stage of epidemic-style message dissemination. In this paper, we analyze the characteristics of restrained epidemic routing when the contact relation between nodes is given by a general contact model such as complex networks. Specifically, we describe the dynamics of restrained epidemic routing on a complex network with a given degree distribution as differential equations using the degree-based mean field approximation.

DTN routing aims to realize message delivery from a node (source node) in the network to another specific node (destination node) without using dedicated communication infrastructure. Depending on the mobility of the source and the destination nodes, DTN routing is classified into four classes: mobile-to-mobile, fixed-to-mobile, mobile-to-fixed, and fixed-to-fixed. Most of conventional DTN routing studies have been focusing on mobile-to-mobile DTN routing. A large number of mathematical analyses and performance evaluations of mobile-to-mobile DTN routing have been performed, but the characteristics of other classes - in particular, mobile-to-fixed and fixed-to-fixed DTN routing - have not been well clarified. In this paper, as a mobile-to-fixed and fixed-to-fixed DTN routing, we focus on a position-based single-copy DTN routing. We build an analytical framework for those DTN routing mechanisms. Namely, we describe the average behavior of message delivery between the source node and the destination node. We then derive the average message delivery delay in the position-based single-copy DTN routing. Through numerical examples, we quantitatively compare the performances of a multi-copy mobile-to-mobile DTN routing and the position-based and single-copy mobile-to-fixed DTN routing.

PTP (Precision Time Protocol) is a network protocol for achieving more precise time synchronization among networked devices than the conventional NTP (Network Time Protocol). Although hardware-assisted timestamp during PTP message exchanges has been commonly used for realizing a high-precision time synchronization, software-only implementations are also studied in the literature. A software-only implementation must cope with jitter and noise observed in timestamps in PTP messages so that undesirable effects such as clock fluctuation and/or desynchronization can be mitigated. A software-only implementation of the PTP protocol called PTPd includes a clock adjustment mechanism (clock servo), which utilizes two types of low-pass filters and a PI (Proportional Integral) controller in classical control theory. In this paper, we build a discrete model of a networked system utilizing the PTP protocol and the clock adjustment mechanism at the slave device. We also analyze the stability of the entire system. Through numerical examples, we investigate the effect of control parameters of the clock adjustment mechanism on both steady-state and transient-state characteristics.

In recent years, a statistical approach called sparse modeling has been studied extensively for estimating unobserved model parameters from a small number of observations using the sparsity of model parameters. Although sparse modeling has been applied to many practical problems in the fields of signal processing and image processing, to the best of our knowledge, few studies have applied it to the field of information networking. In this paper, we investigate whether a sparse representation of network topology can be obtained from a dictionary trained with a dictionary learning algorithm in sparse modeling. Specifically, we train a dictionary from a number of learning network topologies using the K-SVD algorithm, which is one of conventional dictionary learning algorithms, and obtain a sparse representation of the network topology by solving an l0-norm minimization problem for given network topology and the trained dictionary. Furthermore, through experiments, the effects of several factors - the network (i.e., topology and network size) and the dictionary (i.e., dictionary size) - on sparse representation of network topologies are investigated. Our finding includes that graphs whose structure is uniform (e.g., tree) and networks with cluster structure are suitable for sparse representation of network topologies.

Robustness against failure and attack is one of the essential properties of large-scale dynamical system such as power grids, transportation system, communication systems, and computer networks. Despite its popularity and intuitiveness, a major drawback of descriptive robustness metrics such as the size of the largest connected component and the diameter is its computational complexity. On the contrary, predictive metrics such as the spectral radius, the natural connectivity, and the algebraic connectivity are much easier to obtain than descriptive metrics, but the predictability of those measures against different levels and types of failures/attacks has not been well understood. In this paper, we therefore investigate how effectively predictive metrics (spectral measures) can estimate the robustness of a network against random node removal. Our finding includes that, among five types of spectral measures, the effective resistance is most suitable for predicting the largest cluster component size under low node removal ratio, and that the predictability of the effective resistance is stable for various networks generated with different network generation models.

Advanced Driver-Assistance System (ADAS) technology has been developed in recent years for realizing an automotive network based on Ethernet and serial-bus based communication such as Control Area Network (CAN). EthernetAVB (Audio/Video Bridging) is a promising technique for realizing highly-reliable and low-latency Ethernet communication. Transport protocols for realizing low-latency communication (e.g., low-latency TCP) in data center networks have also been studied extensively. However, these communication standards are implemented in limited network devices and operating systems, making it difficult to construct an experiment environment for complex automotive networks comprising many Electronic Control Units (ECUs). In this paper, we propose a network emulator called ATINET (AuTomotive IP NETwork emulator), which supports EthernetAVB (802.1Qav) in layer-2 and ECN (RFC 3168) in layer-3 using network virtualization techniques in the Linux operating system.

In recent years, a statistical approach called sparse modeling has been studied extensively for estimating unobserved model parameters from a small number of observations by using the sparsity of model parameters. Although sparse modeling has been applied to many practical problems in the fields of signal processing and image processing, to the best of our knowledge, few studies have applied it to the field of information networking. In this paper, we investigate how sparse modeling can be applied to a network flow problem. Specifically, we focus on the minimum link flow problem that is similar to the classical minimum cost flow problem except that its objective is to minimize the number of links consisting a flow rather than the total link cost. We present a sparsemodeling- based formulation of the minimum link flow problem and investigate how effectively our formulation of the minimum link flow problem can be solved using a conventional greedy algorithm called Orthogonal Matching Pursuit (OMP). We also extend our sparse-modeling-based approach to a constrained minimum link flow problem with finite link capacities. For solving the constrained minimum link flow problem, we propose a greedy algorithm called Constrained Orthogonal Matching Pursuit (COMP).

In recent years, a statistical approach for estimating unobserved model parameters from a small number of observations utilizing the sparsity of model parameters called sparse modeling have been extensively studied. In our previous work, we have shown the effectiveness of sparse modeling for a network flow problem called minimum link flow problem, which finds, for given incoming/outgoing rate requirements at nodes, a set of flows satisfying requirements with the least number of links. This paper extends our sparse-modeling based approach to a more complex problem - estimation of betweenness centrality, which is one of the major graph indices. In this paper, we present a sparse-modeling based solution for betweenness centrality estimation. Betweenness centralities of all nodes in an undirected graph are estimated from shortest-path trees, each of which is obtained as the solution for the l1-norm minimization problem.

DTN (Delay/Disruption-Tolerant Networking) aims to realize efficient and reliable end-to-end communication even when communication links among nodes are intermittently connected due to several reasons such as unstable wireless connectivity and dynamic network topology. It is well known that end-to-end routing is suitable for networks with non-intermittent (i.e., always connected) communication links. Also, it is well known that opportunistic routing is suitable for networks with highly intermittent communication links since the end-to-end path between the source and the destination nodes is not likely to exist. In this paper, we address the research question - for a given level of link intermittency, which of end-to-end routing and opportunistic routing is better than the other in terms of the average end-to-end message delivery delay? We try to answer this question through mathematical analysis. Specifically, we analytically derive average end-to-end message delivery delays with the end-to-end routing and the epidemic routing.

Presents the introductory welcome message from the conference proceedings. May include the conference officers' congratulations to all involved with the conference event and publication of the proceedings record.

It is widely known that scale-free networks are robust against random node removals, which is one of major interesting findings in network science. This suggests that, for instance, communication networks such as the Internet is robust against random node failures caused by breakdowns and/or malicious attacks if their network topologies are scale-free networks. Generally, the ratio of failed devices (e.g., routers) to operational devices is not so high. In this paper, we revisit the robustness of complex networks against random node removals. Through simulations, we compare the robustness of scale-free and non-scale-free networks against random node removals. Our findings include that, contrary to common understanding, random networks are more robust than scale-free networks except for extremely high node removal ratios. We also show that the robustness of random networks can be further improved by bounding the minimum node degree of those networks.

Recently, Content-Centric Networking (CCN) has been extensively studied by networking researchers as a promising network architecture to realize an information-centric network. In CCN, to reduce the amount of redundant Interest and Data packet transmissions, routers can aggregate multiple Interest packets requesting the identical content into a single packet. In the literature, the effect of Interest packet aggregation at CCN router on the performance has been investigated. In this paper, we analyze the impact of delayed packet forwarding at routers on the performance of CCN. With delayed packet forwarding, every router does not immediately forward the Interest packet; instead, it intentionally delays packet forwarding by a fixed amount of time. We analytically derive the content delivery delay with and without delayed packet forwarding at routers to reveal the impact of delayed packet forwarding.

Recently, Content-Centric Networking (CCN) has been extensively studied by networking researchers as a promising network architecture to realize an information-centric network. When a CCN router receives multiple Interest packets requesting identical content, it can aggregate those packets into a single Interest packet in order to reduce the amount of redundant Interest and Data packet transmission. In the literature, it is known that Interest packet aggregation significantly affects the performance of a CCN network. In this paper, we propose a method called Probabilistic Interest Packet Aggregation (PIPA). We investigate the fundamental characteristics of PIPA - in particular, the relation between its Interest packet aggregation probability and the average chunk delivery delay - through both simulation experiments and mathematical analyses. Our findings include that by appropriately aggregating Interest packets at a CCN router using PIPA, the average chunk delivery delay can be reduced by approximately 15% compared with the case without PIPA.

Influence maximization is a combinatorial optimization problem on a graph: Given a social network, an influence maximization algorithm aims to find a set of influential (seed) nodes in the network such that the expected number of nodes influenced by the seed nodes is maximized under the given cascade model. Most influence maximization algorithms proposed in the literature assume that ground-truth influence spread probabilities are available. In reality, however, it is natural to assume that there exists a deviation of the influence spread probability used in the influence maximization algorithms from actual influence spread probability. In this paper, we examine the robustness of existing influence maximization algorithms against non-adversarial perturbations in influence spread probabilities. Our results show that the effectiveness of state-of-the-art approximation and heuristic algorithms may be significantly degraded, and lightweight heuristic algorithms can outperform state-of-the-art algorithms when the perturbations are large.

In this paper, we propose a delivery control method of floating contents called PFCS (Proportional control for Floating Content Sharing) and investigate its properties through stability analysis. By intentionally limiting the coverage and the lifetime of epidemic broadcasting, floating contents can be shared among mobile nodes without dedicated infrastructure. Information sharing with floating contents is realized by (1) embedding the usable area (i.e., anchor zone) and the lifetime (i.e., TTL (Time-to-Live)) in a message, (2) forwarding the message among mobile nodes only in its anchor zone, (3) deleting the message if it expires, and (4) deleting the message, if necessary, once the mobile node carrying the message leaves the anchor zone. Hence, if message forwarding among mobile nodes is discontinued or some messages are lost due to buffer overflow of a mobile node, floating contents may be vanished. Such a limitation becomes more problematic when the anchor zone accommodates a number of floating contents. In this paper, we therefore propose a delivery control method of floating contents called PFCS, which controls the message possession ratio (i.e., the fraction of mobile nodes carrying a message in the anchor zone). We also perform stability analysis of PFCS to investigate fundamental properties of PFCS. Through numerical examples and simulation results, we demonstrate the effectiveness of PFCS as well as the validity of our approximate analysis.

In this paper, we derive the average message delivery of epidemic routing with broadcasting ACKs (ACKnowledgements) in DTN (Delay/Disruption-Tolerant Networking). The epidemic routing achieves near-optimal performance in terms of the message delivery delay when there exists only a single message in the network. However, if there exist multiple messages, epidemic routing generates excessive amount of message copies, resulting in poor performance. One of the promising techniques to alleviate the drawbacks of epidemic routing is broadcasting ACKs, which propagates information on the successful delivery of the message to all other nodes to eliminate unnecessary copies to avoid the waste of network bandwidth. In the literature, the performance of epidemic routing with broadcasting ACKs for a single message has been analyzed. However, to the best of our knowledge, the performance of epidemic routing with broadcasting ACKs under multiple concurrent message routings has not been well understood. In this paper, utilizing the Markov model of epidemic routing with broadcasting ACKs, we derive the average message delivery delay of epidemic routing with multiple messages, each of which competes for the network bandwidth.

In this paper, we derive the average and the distribution of message delivery delays in a geographic DTN routing with multiple mobile agents, whose mobility patterns are given by random walks on a graph and message routing algorithm is FIFO (First-In First-Out) algorithm. A geographic DTN routing aims at realization of message delivery among multiple (generally, geographically-dispersed) geographic locations on a field without necessity of specific communication infrastructure by utilizing mobility of mobile agents. We model the behaviors of mobile agents as multiple random walks on a graph. In this paper, two types of workload models - one-time workload model (i.e., simultaneous generation at the initial state) and continuous workload model (i.e., Poisson message arrival) - are considered. Our analysis reveals the effect of system parameters - the number of mobile agents on the field, the number of message loadings at a geographic location, the message generation rate and the number of message replicas - on the average and the distribution of message delivery delays. We also discuss the feasibility of a specific application of geographic DTN routing - communication among evacuation sites in disaster area.

In this paper, we investigate the effect of scale-free structure of a network topology on performance of CCN (Content-Centric Networking). Specifically, we generate multiple scale-free and non-scale-free network topologies by two synthetic network generation models (i.e., scale-free tree and generalized BA model). We compare the average delivery delay and throughput of CCN with scale-free and non-scale-free network topologies. Our findings include that (1) the average content delivery delays in scale-free networks are much smaller than that of non-scale-free networks (2) however, the difference in average content delivery delay is not as large as the difference in their average path lengths, and (3) the average throughput in scale-free networks is higher than that of non-scale-free networks regardless of the network generation model and the distribution of content popularity.

We model the behavior of a mobile agent as a random walk on a network, and derive the formula of the expected time until two random walkers meet on the basis of the spectral graph theory. The validity of the derived formula is confirmed by the comparison with simulation results. We believe that our work contributes to understanding the property of epidemic information dissemination, and designing a mechanism for efficient dissemination in mobile ad hoc networks.

In this paper, we propose a modeling approach for a Content-Centric Networking (CCN) network by considering the dynamics of its transport layer protocol. Transport layer protocols for CCN have mainly been investigated through simulation experiments because CCN itself is a complicated network architecture compared with IP, and the complex interaction between CCN caching and the behavior of a transport layer protocol must be considered. Several analytical studies of transport layer protocols in CCN have been reported; however, these modeling approaches cannot model the dynamical behavior of a transport layer protocol or a large-scale CCN network. In this paper, by extending an existing large-scale CCN modeling approach, we build a fluid-based model for a CCN network with an AIMD-based window flow control mechanism. Moreover, we verify the validity of our approximate analysis by comparing the analytical results with simulation results.

Recently, Content-Centric Networking (CCN) has been extensively studied by networking researchers as one of the promising network architectures for realizing information-centric networks. CCN adopts a fundamentally different communication paradigm from that of the conventional Internet Protocol (IP). Therefore, advanced transport protocols developed for IP cannot be directly used in CCN. In this paper, we propose a packet loss detection mechanism called Interest ACKnowledgement (ACK). Interest ACKs provides information on the history of successful Interest packet receptions at a repository (i.e., content provider), this information is conveyed to the corresponding entity (i.e., content consumer) via the header of Data packets. Interest ACKs enable the entity to quickly and accurately detect Interest and Data packet losses in the network. We conduct simulations to investigate the effectiveness of Interest ACKs in a rather simple network topology. Our results show that Interest ACKs are effective for improving the adaptability, stability, and fairness of CCN with window-based flow control and that packet losses at the repository can be reduced by 10%-20%.

Presents the introductory welcome message from the conference proceedings. May include the conference officers' congratulations to all involved with the conference event and publication of the proceedings record.

In this paper, we derive the average message delivery delay in a geographic DTN routing with multiple mobile agents, where mobility patterns are given by random walk on a graph and message routing algorithm is the Random algorithm. A geographic DTN routing aims at realization of message delivery among multiple (generally, geographically-dispersed) geographic locations on a field without necessity of specific communication infrastructure by utilizing mobility of mobile agents. We model the behaviors of mobile agents as multiple random walks on a graph. Our analysis reveals the effect of system parameters - the number M of mobile agents on the field and the number K of message loads at a geographic location - on the average message delivery delay.

In this paper, we quantitatively investigate the optimality of the shortest-path routing in Content-Centric Networking (CCN) in terms of application-level performance metrics. We compare the average content delivery delay under the shortest-path routing with that under the optimal two-hop detour routing in two networks (triangular network and seven-node network). Our findings include that the shortest-path routing is optimal under a balanced network with comparable content store sizes at routers, and that the optimal two-hop detour routing achieves better application-level performance when the content store size ratio is large.

Rateless erasure code (REC) is an erasure code, where the encoder generates a potentially infinite number of encoded symbols and the original message can be reconstructed from a sufficient number of correctly received packets. Many REC-based transmission protocols have been proposed for improving network throughput in lossy channel. However, state-of-the-art RECs (such as LT code and Raptor code) are not efficient for transmitting short messages. Recent studies suggest that network traffic is characterised by bursts of short messages and thus existing transmission protocols do not benefit from the gains of deploying REC. In this paper, we propose an REC-based transmission protocol, namely UDP-RC, which integrates the simplicity of UDP and strength of systematic Random code suited to network traffic with short messages. It attains high throughput by transmitting short messages reliably with lower overheads over lossy channel. We experimentally show that UDP-RC achieves at least 50% higher throughput and maintains more stable throughput compared to TCP (Transmission Control Protocol) and UDT (UDP Data transfer) protocol under both ideal and lossy channel conditions.

We propose a novel problem called influence maximization for unknown graphs, and propose a heuristic algorithm for the problem. Influence maximization is the problem of detecting a set of influential nodes in a social network, which represents social relationships among individuals. Influence maximization has been actively studied, and several algorithms have been proposed in the literature. The existing algorithms use the entire topological structure of a social network. In practice, however, complete knowledge of the topological structure of a social network is typically difficult to obtain. We therefore tackle an influence maximization problem for unknown graphs. As a solution for this problem, we propose a heuristic algorithm, which we call IMUG (Influence Maximization for Unknown Graphs). Through extensive simulations, we show that the proposed algorithm achieves 60--90% of the influence spread of the algorithms using the entire social network topology, even when only 1--10% of the social network topology is known. These results indicate that we can achieve a reasonable influence spread even when knowledge of the social network topology is severely limited.

In this paper, we extensively evaluate the effectiveness of using a user's social media activities for estimating degree of depression. As ground truth data, we use the results of a web-based questionnaire for measuring degree of depression of Twitter users. We extract several features from the activity histories of Twitter users. By leveraging these features, we construct models for estimating the presence of active depression. Through experiments, we show that (1) features obtained from user activities can be used to predict depression of users with an accuracy of 69%, (2) topics of tweets estimated with a topic model are useful features, (3) approximately two months of observation data are necessary for recognizing depression, and longer observation periods do not contribute to improving the accuracy of estimation for current depression; sometimes, longer periods worsen the accuracy.

In this paper, using an autonomous and distributed approach, we aim at realizing a control mechanism, which is scalable in terms of the network size, for joint optimization of the multi-path routing and bandwidth allocation (MRBA). Multi-path routing is to determine multiple paths from the source node to the sink node such that the traffic demand by the source node can be successfully transferred to the sink node as well as the total network cost can be minimized. Bandwidth allocation is to decide the amount of bandwidth assigned to the flow at every link along multi-paths from the source node to the sink node, which are chosen by the multi-path routing. In this paper, we propose a distributed and scalable flow control mechanism called DFC-BP (Distributed Flow Control with Backward Propagation), which simultaneously solves multi-path routing and bandwidth allocation. DFC-BP is an autonomous and decentralized hop-by-hop flow control mechanism which can minimize the total network cost utilizing the backward propagation from downstream nodes to upstream nodes. We also investigate the effectiveness of DFC-BP in terms of efficiency, transient performance, adaptability, and parameter sensitivity through simulation experiments. Our findings include that the total network cost realized by DFC-BP is comparable to that by a centralized heuristic algorithm, and that DFC-BP quickly adapts to the occurrence of multiple link failures.

Random code is a rateless erasure code that can reconstruct the original message of k symbols from any k + 10 encoded symbols with high probability of complete decoding (PCD), i.e. 99.9% successful decoding, irrespective of the message length, k . Nonetheless, random code is inefficient in reconstructing short messages. For example, a message of k = 10 symbols requires k + 10 = 20 encoded symbols, i.e. two times the original message length in order to achieve high PCD. In this study, the authors propose micro‐random code that encodes and decodes the original message using symbols of smaller dimensions, namely micro symbols. The authors’ analysis and numerical simulations show that micro‐random code achieves high PCD with only k + 1 encoded symbols. As the trade‐off for such a gain, the number of steps for decoding increases exponentially with each incrementing segmentation factor, α . In addition, the numerical results show that the decoding time increases by about 400% at α = 10, depending on the processing power of the system.

In the last decade, research and development of microbots, whose sizes are in the range between a few millimeters to centimeters, have been actively performed. One of promising applications of microbots is survivor discovery in disaster areas. Contrary to high expectations to many microbot applications, in the literature, exploratory performance with microbots and requirements on microbot functionalities have not been fully discussed. In this paper, we therefore analyze the exploratory performance of microbot swarm (i.e., A great number of autonomous and independent microbot) in a three-dimensional field where every microbot independently searches for target objects. We derive the target discovery ratio as well as the optimal dropping avoidance probability of microbots, with which each microbot probabilistically prevents itself to fall onto the lower layer using an edge-detection sensor. Moreover, through several numerical examples, we investigate how the exploratory performance of microbot swarm is affected by several system parameters such as the number of microbots, the area of a layer, the density of openings in the layer, and the dropping avoidance probability a microbot.

Research on social network analysis (SNA) has been actively pursued. Most SNAs focus on either social relationship networks (e.g., Friendship and trust networks) or social interaction networks (e.g., Email and phone call networks). It is expected that the social relationship network and social interaction network of a group would be closely related to each other. For instance, people in the same community in a social relationship network are expected to communicate with each other more frequently than with people in different communities. To the best of our knowledge, however, there is not yet any empirical evidence to support the existence of such interaction locality in large-scale online social networks. This paper aims to bridge the evidence gap between intuition about interaction locality and confirmation that it occurs. We investigate the strength of interaction locality in large-scale social networks by analyzing several types of data: logs of mobile phone calls, email messages, and message exchanges in a social networking service. Our results show that strong interaction locality is observed equally in the three datasets and suggest that the strength of the interaction locality is fractal, by which we mean that the strength is invariant with regard to the scale of the community.

Control of a large-scale network using a centralized approach is essentially difficult due to its large end-to-end delay, high heterogeneity of a large number of network components, low availability and/or reliability caused by network component failures. In this paper, we aim at realizing a control mechanism for both per-flow path selection and available bandwidth allocation using an autonomous and distributed approach. Per-flow path selection is to select multiple paths from the source node to the sink node such that the traffic demand by the source node can be transferred to the sink node as well as the total network cost can be minimized. Available bandwidth allocation is to decide the amount of bandwidth assigned to every link in the paths from the source node to the sink node, which are chosen by the perflow path selection. In this paper, we propose a distributed and scalable flow control mechanism called DFC-BP (Distributed Flow Control with Backward Propagation), which simultaneously solves per-flow path selection and available bandwidth allocation. We also investigate the effectiveness of DFC-BP in terms of efficiency and transient performance through simulation experiments.

Data-centric networking has recently been getting increased attention. A representative design of data-centric networking is CCN (Content-Centric Networking), which routes packets within a network based on their content identifiers. CCN is basically designed to be open because ease of data reuse is one of the greatest advantages of data-centric networking. However, being used for real-world networking, completely open data-centric networking is not sufficient. It is required to realize closed communication within a group of users. In this paper, we propose Virtual Content-Centric Networking (VCCN), which realizes closed communication within a group of users with CCN router virtualization. This paper presents four building blocks of VCCN: extension of the content identifier, CCN router virtualization, packet transport between virtualized CCN routers, and Social Network Services cooperative user/group identification. Moreover, we implemented VCCN's basic features by extending the CCNx software and performed a preliminary performance evaluation of our VCCN implementation.

Social network analysis has been actively pursued to provide an understanding of complex social phenomena. However, graphs used for social network analyses generally contain several errors in their nodes, links, and link weights. In recent years, huge amount of data representing human-to-human interactions are available, and their availability enables us to obtain various types of real social networks. In this paper, we investigate the effect of link weight quantization on the centrality measures in five types of real social networks. Consequently, we show that graphs with high skewness in their degree distribution and/or with high correlation between node degrees and link weights are robust against link weight quantization.

In this paper, we investigate the effectiveness of the records of user's activities in Twitter, which is a popular microblogging site, for estimating his/her depressive tendency. We construct multiple regression model to estimate user's depressive tendency from the frequencies of words used by the user. We perform experiments to estimate participants' depressive tendencies using the constructed regression model. Our experimental results show that there exists medium positive correlation (correlation coefficient r ≃ 0.45) between the Zung's Self-rating Depression Scale, which is a popular measure for estimating depressive tendency, and estimated score obtained from the regression model.

Gradient-based routing, where each node calculates a metric that indicates how useful a node might be in relaying messages to a sink node and transmits messages according to the metric, is one of promising approaches for Delay Tolerant Mobile Sensor Networks. However, existing gradient-based routing methods do not consider node mobility to form their gradient and this may result in inefficient message relays and degradation in their performance. In this paper, we discuss how node mobility affects message delivery in gradient-based routing and propose a gradient-based routing method that incorporates node mobility into its gradient to reduce the effect of inefficient message relays. The key idea of our proposal is to distinguish nodes leaving from a sink node from nodes approaching to a sink node. Since those leaving nodes are less useful to relay messages to a sink node, our proposed method prevents nodes from transmitting messages to nodes leaving from a sink node. Through simulations, we show that our proposal decreases the average message delivery delay under various node mobility models. Moreover, our proposal reduces the average message delivery delay by up to 50% in the case that nodes move straightly.

Virtual machine live migration, which migrates a virtual machine between data centers, is studied as a way to improve quality of services hosted on clouds. Meanwhile, traffic engineering is performed in networks that connect geographically-dispersed data centers. These two controls are originally designed and operated individually. Though it is naturally expected that integrating virtual machine live migration and the traffic engineering could result in a good overall performance, the effectiveness of such an integrated control has not been well understood. In this paper, we therefore quantitatively investigate its effectiveness. We first formulate an integrated control and an individual control as mixed integer programming problems in which the objective function is minimization of the average link delay in the network. Through numerical examples, we show that the integrated control can reduce the average link delay by at most 24 % and it can accommodate as 1.3 times much as incoming traffic compared with the individual control.

In some delay-tolerant communication systems such as vehicular ad-hoc networks, information flow can be represented as an infectious process, where each entity having already received the information will try to share it with its neighbours. The random walk and random waypoint models are popular analysis tools for these epidemic broadcasts, and represent two types of random mobility. In this paper, we introduce a simulation framework investigating the impact of a gradual increase of bias in path selection (i.e. reduction of randomness), when moving from the former to the latter. Randomness in path selection can significantly alter the system performances, in both regular and irregular network structures. The implications of these results for real systems are discussed in details.

We propose a room-shaped information environment called Ambient Suite that enhances interpersonal communication. In Ambient Suite, the room itself works as both sensors to estimate the conversation states of participants and displays to present information to stimulate conversation. This paper introduces an implementation assumed standing-party situations as a typical use case of Ambient Suite. From the result of user study using its implementation, we confirmed that our system adequately encouraged participant conversations.

In this paper, we present our vision on large-scale and dynamic social network analysis in real environment, which is expected to be enabled by introduction of large-scale heterogeneous sensors in ambient environment. We address challenges toward realization of large-scale dynamic social network analysis in real environment, and discuss several promising applications. We finally present our preliminary experimental results of dynamic social network analysis for six-person social gatherings in real environment.

In this paper, we propose a novel communication paradigm called group-oriented communication. Different from conventional unicast-based communications, group-oriented communication is entirely based on group-based communication. Our group-oriented communication is essentially a type of many-to- many communication, but it realizes any type of communications including one-to-one, one-to-many, many-to-one and many-to- many communications based on group-based communication. With our group-oriented communication, diverse social activities can be shifted into a communication network in a straightforward way, and users' requirements on security/reliability can be fulfilled. In this paper, we first qualitatively discuss advantages of our group-oriented communication by comparing with the conventional IP-based network. We then discuss four design goals of a network architecture for our group-oriented communication: supporting dynamic entity/group, supporting address operation expression, realization of entity/group find ability, and realization of security. After carefully examining these design goals, we design a network architecture for realizing our group-oriented communication. Through quantitative evaluations, we show that the network architecture for our group-oriented communication should be packet-based, that reachability control is the core networking technology, and that the network architecture should have the two-layer structure consisting of transport and control layers.

XCP (eXplicit control protocol) has been proposed as an efficient transport protocol for a wide-area and high-speed network. XCP is a transport-layer protocol that performs congestion control using explicit feedback from routers. In the literature, many simulation-based performance studies of XCP has been performed. However, the effect of traffic dynamics on the XCP performance has not been investigated. In this paper, through simulation experiments, we first show that XCP has the following problems: (1) utilization of the bottleneck link is lowered due to XCP traffic dynamics, and (2) in environment where non-XCP traffic and XCP traffic coexist, control of XCP becomes unstable. We then propose XCP-IR (XCP with increased robustness) that operates efficiently even for dynamic traffic. Through simulation experiments, we show that XCP-IR operates efficiently even for dynamic traffic.

In this paper, we analyze 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 are very large, operation of XCP becomes less stable, and (3) output link bandwidth of an XCP router is independent of stability of the XCP protocol.

In this paper, we propose a flow-level simulator called FSIM (Fluid-based SIMulator) for performance evaluation of large-scale networks, and verify its effectiveness using our FSIM implementation. The notable features of our flow-level simulator FSIM are its accuracy and fast simulation execution compared with conventional flow-level simulators. For improving simulation accuracy, our flow-level simulator FSIM utilizes accurate fluid-flow models. For accelerating simulation execution speed, our flow-level simulator FSIM adopts an adaptive numerical computation algorithm for ordinary differential equations. Another notable feature of our flow-level simulator FSIM is its compatibility with the existing network performance analysis tool. In this paper, through several experiments using our FSIM implementation, we evaluate the effectiveness of our flow-level simulator FSIM in terms of simulation speed, accuracy and memory consumption. Consequently, we show that our flow-level simulator FSIM outperforms a conventional flow-level simulator; i.e., it realizes approximately 100% faster simulation with higher accuracy and less memory consumption than a conventional flow-level simulator.

GridFTP has been used as a data transfer protocol to effectively transfer a large volume of data in grid computing. GridFTP supports a feature called parallel data transfer that improves throughput by establishing multiple TCP connections in parallel. However, for achieving high GridFTP throughput, the number of TCP connections should be optimized based on the network status. In this paper, we propose an automatic parallelism tuning mechanism called GridFTP-APT (GridFTP with automatic parallelism tuning) that adjusts the number of parallel TCP connections only using information measurable in the grid middleware. Through simulation experiments, we demonstrate that GridFTP-APT significantly improves the performance of GridFTP in various network environments.

In recent years, IP-based virtual private networks (IP-VPNs), which provide a virtual privately owned network over an IP network, have attracted attention. With existing IP-VPNs, however, there is a serious problem that fairness among IP-VPN customers is not satisfied. In our previous work, we have proposed an IP-VPN fairness control mechanism called I2VFC (Inter-and Intra-VPN Fairness Control) that realizes fairness among IP-VPN customers. In this paper, we quantitatively show effectiveness of our I2VFC using simulation experiments and prototype system experiments. Focusing on inter-VPN fairness, intra-VPN fairness, and scalability, we extensively analyze the performance of I2VFC. Consequently, we show that I2VFC can realize both inter-and intra-VPN fairness under diverse control parameter configurations, indicating robustness and parameter insensitivity of our I2VFC. We also show that I2VFC has a practically sufficient scalability in terms of the transfer speed and the number of VPNs accommodated. For instance, measurement results using our prototype system show that with a modern desktop computer, I2VFC can support approximately 1.6 [Gbit/s] bandwidth and 1,300 numbers of VPNs.

In this paper, we propose a network model partition method called QD-PART (Quasi-Dynamic network model PARTition method) for accelerating parallel network simulation. The key of QD-PART is to utilize the fact that a network simulation is typically repeated several times with the same parameter set for estimating the confidence interval of steady state measures. QD-PART gradually optimizes partition of a network model based on past simulation results such as the total simulation time, CPU usage of computing resources, and traffic intensity (i.e., the number of packets transmitted) of each link. At the end of each parallel simulation run, QD-PART re-partitions the network model based on such information aiming at minimizing communication overhead among computing resources and balancing load of sub-network models executed on computing resources. Through several experiments using a parallel-distributed network simulator, we show how parallel network simulation can be accelerated using QD-PART by gradually improving the network model partition.

In recent years, IP-based virtual private networks (IP-VPNs), which provide a virtual privately owned network over an IP network, have attracted attention. With existing IP-VPNs, however, there is a serious problem that fairness among IP-VPN customers is not satisfied. In this paper, we first discuss design objectives of a control mechanism for achieving fair IP-VPN services: achieving inter-VPN fairness, achieving intra-VPN fairness, easy deployment into existing IP networks, and achieving a high scalability. We then propose an IP-VPN fairness control called 12FVC (inter-and intra-VPN fairness control) for realizing a fair IP-VPN service in a scalable way. The core of 12VFC is an AIMD (additive increase and multiplicative decrease) window flow control operating among IP-VPN service provider's edge routers. 12VFC has the advantage that an IP-VPN service provider can arbitrarily specify inter-VPN fairness criteria by utilizing analytic results of AIMD window flow control. Moreover, 12VFC can be easily deployed into existing IP networks by simply modifying edge routers. Through several simulation experiments, we demonstrate that 12VFC realizes both inter-VPN fairness and intra-VPN fairness with extremely high accuracy.

Another version of TCP called TCP Vegas has been proposed and studied in the literature. It can achieve better performance than the current TCP Reno. In our previous studies, steady-state behavior of a window-based flow control mechanism based on TCP Vegas has been analyzed for a simple network topology. In this paper, we extend our analysis to a generic network topology where multiple bottleneck links exist. We first derive equilibrium values of a window size of a TCP connection and the number of packets waiting in a router's buffer in steady state. We also derive throughput of each TCP connection in steady state, and investigate the effect of control parameters of TCP Vegas on fairness among TCP connections. We then present several numerical examples, showing how control parameters of TCP Vegas should be configured for achieving both stability and better transient performance.

A rate-based congestion control algorithm regulates cell emission rate of source end systems based on feedback information from the network. It was standardized by the ATM Forum for application to an ABR (available bit rate) service class. In the standard, two types of congestion notification methods of the switch are specified: EFCI marking and explicit-rate marking. In this paper, we focus on the explicit-rate marking switch. We propose our enhancements on a recently proposed switch algorithm known as the max-min scheme. The main objective of our enhancements is to control the queue length of the switch for preventing cell loss and achieving full link-utilization. We show the effectiveness of our switch algorithm by simulation experiments.

An ATM switch with both input and output buffers provided with a back-pressure function has been proposed as a cost-effective switch architecture. The back-pressure function prohibits cell transmission from the input buffer to the corresponding output buffer to avoid cell loss at the output buffer due to a temporary congestion. Especially when this switch is applied to ATM LANs for data transfer services, its performance should be evaluated by taking into account bursty traffic. In this paper, we show the maximum throughput, the packet delay distribution, and the approximate packet loss probability of such an ATM switch for bursty traffic through an analytic method. In addition to a balanced traffic condition, an unbalanced traffic and a mixture of bursty and stream traffic are also analyzed. Through several numerical examples, we quantitatively show the effects of the average packet length and the output buffer size on its performance. Key words: ATM LAN, Input/Output Buffered Type S...