This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.

In this paper, we consider consecutive burst transmission with burst loss recovery based on Forward Error Correction (FEC) in which redundant data is transmitted with multiple bursts. We propose two burst generation methods: Out-of Burst Generation (OBG) and In-Burst Generation (IBG). The OBG generates a redundant burst from redundant data, while the IBG reconstructs a burst from an original data block and a part of the redundant data. For both methods, the resulting bursts are transmitted consecutively. If some bursts among the bursts are lost at an intermediate node, the lost bursts can be recovered with the redundant data using FEC processing at the destination node. We evaluate by simulation the proposed methods in a uni-directional ring network and NSFNET, and compare the performances of the proposed methods with the extra-offset time method. Numerical examples show that the proposed methods can provide a more reliable transmission than the extra-offset time method for the OBS network where the maximum number of hops is large. Moreover, it is shown that the end-to-end transmission delay for our proposed methods can be decreased by enhancing the FEC processor or by increasing the number of FEC processors.

In optical burst switching (OBS) networks, burst with different numbers of hops experience unfairness in terms of the burst loss probability. In this paper, we propose a preemptive scheme based on the number of transit hops in OBS networks. In our proposed scheme, preemption is performed with two thresholds; one is for the total number of hops of a burst and the other is for the number of transit hops the burst has passed through. We evaluate the performance of the scheme by simulation, and numerical examples show that the proposed scheme improves the fairness among the bursts with different numbers of hops, keeping the overall burst loss probability the same as that for the conventional OBS transmission without preemption.

Traffic congestion in road networks has been studied as the congestion game in game theory. In the existing work, the road usage by each agent was assumed to be static during the whole time horizon of the agent's travel, as in the classical congestion game. This assumption, however, should be reconsidered because each agent sequentially uses roads composing the route. In this paper, we propose a multi-agent distributed route selection scheme based on a gradient descent method considering the time-dependency among agents' road usage for vehicular networks. The proposed scheme first estimates the time-dependent flow on each road by considering the agents' probabilistic occupation under the first-in-first-out (FIFO) policy. Then, it calculates the optimal route choice probability of each route candidate using the gradient descent method and the estimated time-dependent flow. Each agent finally selects one route according to the optimal route choice probabilities. We first prove that the proposed scheme can exponentially converge to the steady-state at the convergence rate inversely proportional to the product of the number of agents and that of individual route candidates. Through simulations under a grid-like network and a real road network, we show that the proposed scheme can improve the actual travel time by 5.1% and 2.5% compared with the conventional static-flow based approach, respectively. In addition, we demonstrate that the proposed scheme is robust against incomplete information sharing among agents, which would be caused by its low penetration ratio or limited transmission range of wireless communications.

The Proof of Stake (PoS) protocol is one of the consensus algorithms for blockchain, in which the integrity of a new block is validated according to voting by nodes called validators. However, due to validator-oriented voting, voting results are likely to be false when the number of validators with wrong votes increases. In the PoS protocol, validators are motivated to vote correctly by reward and penalty mechanisms. With such mechanisms, validators who contribute to correct consensuses are rewarded, while those who vote incorrectly are penalized. In this paper, we consider an incentivization mechanism based on the voting profile of a validator, which is estimated from the voting history of the validator. In this mechanism, the stake collected due to the penalties are redistributed to validators who vote correctly, improving the incentive of validators to contribute to the system. We evaluate the performance of the proposed mechanism by computer simulations, investigating the impacts of system parameters on the estimation accuracy of the validator profile and the amount of validator's stake. Numerical results show that the proposed mechanism can estimate the voting profile of a validator accurately even when the voting profile dynamically changes. It is also shown that the proposed mechanism gives more reward to validators who vote correctly with high voting profile.

It has been reported that IP packet traffic exhibits the self-similar nature and causes the degradation of network performance. Therefore it is crucial for the appropriate buffer design of routers and switches to predict the queueing behavior with self-similar input. It is well known that the fitting methods based on the second-order statistics of counts for the arrival process are not sufficient for predicting the performance of the queueing system with self-similar input. However recent studies have revealed that the loss probability of finite queuing system can be well approximated by the Markovian input models. This paper studies the time-scale impact on the loss probability of MMPP/D/1/K system where the MMPP is generated so as to match the variance of the self-similar process over specified time-scales. We investigate the loss probability in terms of system size, Hurst parameters and time-scales. We also compare the loss probability of resulting MMPP/D/1/K with simulation. Numerical results show that the loss probability of MMPP/D/1/K are not significantly affected by time-scale and that the loss probability is well approximated with resulting MMPP/D/1/K.

Bitcoin is one of popular cryptocurrencies widely used over the world, and its blockchain technology has attracted considerable attention. In Bitcoin system, it has been reported that transactions are prioritized according to transaction fees, and that transactions with high priorities are likely to be confirmed faster than those with low priorities. In this paper, we consider performance modeling of Bitcoin-blockchain system in order to characterize the transaction-confirmation time. We first introduce the Bitcoin system, focusing on proof-of-work, the consensus mechanism of Bitcoin blockchain. Then, we show some queueing models and its analytical results, discussing the implications and insights obtained from the queueing models.

The project of interconnecting CATV in Hyogo Prefecture, Japan has started since March, 1998. In this project, there are three CATV companies in Hanshin area; Kobe, Nishinomiya and Amagasaki. An ATM switch is equipped in each company and these CATVs are connected serially in the above order. Each company provides the video service to the rest of companies using the MPEG2 over ATM. Each MPEG2 stream is sent to the other two CATV companies according to the function of multicast implemented in ATM switch. In the coverage of each CATV, subscribers utilize Internet connection using cable modems as well as standard CATV broadcasting service. In this paper, we present the outline of the research project in Hyogo Prefecture, Japan, and examine the jitter processes of MPEG streams of the testbed network by the simulation. In our testbed network, cells with two types of requirement for QoS are multiplexed; cells for MPEG2 which require the real-time transmission and those for Internet packets which are much more sensitive for the cell loss ratio. We investigate the jitter processes under some scenarios and show how the jitter process is affected by the Internet traffic and the other cell streams of MPEG2. Furthermore, we study the effect of the number of ATM switches on the jitter process when more CATV networks are added serially.

Hybrid FEC/ARQ, which is a mixture of forward error correction (FEC) and automatic repeat request (ARQ), is a well-known technique aiming for packet-loss recovery to guarantee quality of service (QoS) for real-time communications. In this paper, focusing on layered video transmission over wireless network environment, we propose a proactive retransmission scheme for hybrid FEC/ARQ. In the proposed scheme, a receiver host periodically sends probe packets to a sender host in order to check wireless channel state. If the sender host does not receive any probe packet during a pre-specified interval, it regards the wireless channel as being in burst loss state, and it proactively retransmits packets expected to be lost during the burst loss period. The buffer management associated with layered video coding is also taken into consideration. The performance of the proposed scheme is investigated by simulation. Numerical examples show that the proposed scheme transmits packets of the base layer more successfully than the conventional FEC/ARQ.

In this paper, we propose a new preemptive scheme with release message in optical burst switching (OBS) networks. In the proposed scheme, when a low priority burst is preempted at some intermediate node, two RELEASE messages are sent immediately from the intermediate node to both source and destination nodes (two-way release message transmission), and the RELEASE messages release the corresponding wavelengths for the preempted burst. We consider six wavelength selection rules for the preemption and evaluate the performances of the selection rules by simulations. Numerical examples show that our scheme utilizes wavelengths effectively and, with the optimal selection rule, can decrease the burst loss probability in a large-scale DWDM network.

The ATM-ABR service category provides minimum cell rate (MCR) guarantees and robust connections even with insufficient network resources. Recently proposed rate-management algorithms for supporting multimedia applications over ABR mainly aim at minimizing the cell loss and delay. However, jitter is also an important element of QoS for multimedia applications. In this paper, we focus our attention on the arrival point of the critical cell corresponding to the end of data packet and propose a simple cell scheduling scheme for source node to reduce the jitter on application level over the ATM-ABR service class. In our proposed method, critical cells are delayed intentionally and the packet stream at application level becomes smooth. We verify the effectiveness of our proposed algorithm by an analytical model and simulation. From those results, we find that our proposed scheduling algorithm is effective in reducing the application level jitter even when the tagged cell stream is transmitted along the path with multiple nodes.

This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.

To establish a network service in network functions virtualization (NFV) networks, the orchestrator addresses the challenge of service chaining and virtual network function placement (SC-VNFP) by mapping virtual network functions (VNFs) and virtual links onto physical nodes and links. Unlike traditional networks, network operators in NFV networks must contend with both hardware and software failures in order to ensure resilient network services, as NFV networks consist of physical nodes and software-based VNFs. To guarantee network service quality in NFV networks, the existing work has proposed an approach for the SC-VNFP problem that considers VNF diversity and redundancy. VNF diversity splits a single VNF into multiple lightweight replica instances that possess the same functionality as the original VNF, which are then executed in a distributed manner. VNF redundancy, on the other hand, deploys backup instances with standby mode on physical nodes to prepare for potential VNF failures. However, the existing approach does not adequately consider the tradeoff between resource efficiency and service availability in the context of VNF diversity and redundancy. In this paper, we formulate the SC-VNFP problem with VNF diversity and redundancy as a two-step integer linear program (ILP) that adjusts the balance between service availability and resource efficiency. Through numerical experiments, we demonstrate the fundamental characteristics of the proposed ILP, including the tradeoff between resource efficiency and service availability.

In this paper, we consider QoS-guaranteed wavelength allocation for WDM networks with limited-range wavelength conversion. In the wavelength allocation, the pre-determined number of wavelengths are allocated to each QoS class depending on the required loss probability. Moreover, we consider two wavelength selection rules and three combinations of the rules. We analyze the connection loss probability of each QoS class for a single link using continuous-time Markov chain. We also investigate the connection loss probability for a uni-directional ring network by simulation. In numerical examples, we compare connection loss probabilities for three combinations of selection rules and show how each combination of selection rules affects the connection loss probability of each QoS class. Furthermore, we show how wavelength conversion capability affects the connection loss probability. It is shown that the proposed allocation with appropriate wavelength selection rule is effective for QoS provisioning when the number of wavelengths is large. We also show the effective combination of wavelength selection rules for the case with small wavelength conversion capability.