As one of the technologies for the retrieval of desired contents over large-scale networks, multi-agent systems are receiving much attention. Since there are too many contents on the network to search them all exhaustively, some applications on multi-agent systems have time constraints, that is, they must obtain a result by a given deadline. To find better results for such applications, it is important for the agents to complete their tasks on as many nodes as possible by the deadline. However, most existing agent systems using round robin scheduling disciplines do not take time constraints into account. Therefore, agents are likely to miss their deadlines on many nodes. In this paper, we propose an efficient agent-dispatching method for time-constrained applications. This method decides creation and migration of a clone agent according to the estimated value of the number of agents that would have completed their tasks by the deadline. The results of our performance evaluation show that the proposed method increases the number of agents that complete their tasks.

Network tomography is an inference technique for internal network characteristics such as link loss rate and link delay from end-to-end measurements. In this paper, we consider network tomography for link loss rates, which is referred to as loss tomography. We propose a loss tomography scheme with bitwise operation-based in-network processing. Intermediate nodes generate coded packets by performing bitwise-operations on received packets so as to embed information about paths along which those packets have been transmitted. The coded packets are then forwarded to downstream nodes. In this way, receiver nodes obtain information about paths along which packets are transmitted successfully. Moreover, we show a recursion to compute the likelihood function of path loss rates, which can be utilized in estimating link loss rates from path loss information.

Mobile databases will play an important role in mobile computing environment, to provide data storing and data retrieval functionalities which are needed by most applications. In mobile computing environment, the wireless communication poses some problems, which require us to minimize its use. Replication is a database technique that is commonly used to fulfill the requirement in minimizing network usage. In this paper, we propose two replica allocation strategies, called primary-copy tracking replica allocation (PTRA) and user majority replica allocation (UMRA), which are better suited to the mobile computing environment. Their proposals are intended to cope with cost performance issues in data replication due to user mobility in mobile computing environment. To investigate their effectiveness, we provide access cost analysis and comparison on these strategies and the static replica allocation (SRA) strategy. We show that our proposed strategies outperform the SRA strategy when user mobility (inter-cell movement) is relatively low as compared with data access rate.

Communication among isolated networks (clusters) in delay tolerant networks (DTNs) can be supported by a message ferry, which collects bundles from clusters and delivers them to a sink node. When there are lots of distant static clusters, multiple message ferries and sink nodes will be required. In this paper, we aim to make groups, each of which consists of physically close clusters, a sink node, and a message ferry. Our objective is minimizing the overall mean delivery delay of bundles in consideration of both the offered load of clusters and distances between clusters and their sink nodes. Based on existing work, we first model this problem as a nonlinear integer programming. Using a commercial nonlinear solver, we obtain a quasi-optimal grouping. Through numerical evaluations, we show the fundamental characteristics of grouping, the impact of location limitation of base clusters, and the relationship between delivery delay and the number of base clusters.

We study wireless networked control systems (WNCSs), where controllers (CLs), controlled objects (COs), and other devices are connected through wireless networks. In WNCSs, COs can become unstable due to bursty packet losses and random delays on wireless networks. To reduce these network-induced effects, we utilize the packetized predictive control (PPC) method, where future control vectors to compensate bursty packet losses are generated in the receiving horizon manner, and they are packed into packets and transferred to a CO unit. In this paper, we extend the PPC method so as to compensate random delays as well as bursty packet losses. In the extended PPC method, generating many control vectors improves the robustness against both problems while it increases traffic on wireless networks. Therefore, we consider control vector selection to improve the robustness effectively under the constraint of single packet transmission. We first reconsider the input strategy of control vectors received by COs and propose a control vector selection scheme suitable for the strategy. In our selection scheme, control vectors are selected based on the estimated average and variance of round-trip delays. Moreover, we solve the problem that the CL may misconceive the CO's state due to insufficient information for state estimation. Simulation results show that our selection scheme achieves the higher robustness against both bursty packet losses and delays in terms of the 2-norm of the CO's state.

In this paper, we consider the broadcast storm problem in dense wireless ad hoc networks where interference among densely populated wireless nodes causes significant packet loss. To resolve the problem, we apply randomized network coding (RNC) to the networks. RNC is a completely different approach from existing techniques to resolve the problem, and it reduces the number of outstanding packets in the networks by encoding several packets into a single packet. RNC is a kind of linear network coding, and it is suited to wireless ad hoc networks because it can be implemented in a completely distributed manner. We describe a procedure for implementing the wireless ad hoc broadcasting with RNC. Further, with several simulation scenarios, we provide some insights on the relationship between the system parameters and performance and find that there is the optimal length of coding vectors for RNC in terms of packet loss probability. We also show a guideline for the parameter setting to resolve the broadcast storm problem successfully.

With the rapid increase of link speed in recent years, packet sampling has become a very attractive and scalable means in collecting flow statistics; however, it also makes inferring original flow characteristics much more difficult. In this paper, we develop techniques and schemes to identify flows with a very large number of packets (also known as heavy-hitter flows) from sampled flow statistics. Our approach follows a two-stage strategy: We first parametrically estimate the original flow length distribution from sampled flows. We then identify heavy-hitter flows with Bayes' theorem, where the flow length distribution estimated at the first stage is used as an a priori distribution. Our approach is validated and evaluated with publicly available packet traces. We show that our approach provides a very flexible framework in striking an appropriate balance between false positives and false negatives when sampling frequency is given.

We examine delay performance of packets from constant bit rate (CBR) traffic whose delay is affected by non-real-time traffic. The delay performance is analyzed by solving the Σ Di/G/1 queue with vacations. Our analysis allows heterogeneous service time and heterogeneous interarrival time. Thus, we can get the impact of packet length of a stream on the delay time of other streams. We then give various numerical results for enterprise multimedia networks, which include voice, video and data communication services. From our quantitative evaluation, we conclude that packet length of video traffic has large influence on the delay time of voice traffic while voice traffic gives a little impact on the delay time of video traffic.

Wireless networked control systems (WNCSs) are control systems whose components are connected through wireless networks. In WNCSs, a controlled object (CO) could become unstable due to bursty packet losses in addition to random packet losses and round-trip delays on wireless networks. In this paper, to reduce these network-induced effects, we propose a new design for multihop TDMA-based WNCSs with two-disjoint-path switching, where two disjoint paths are established between a controller and a CO, and they are switched if bursty packet losses are detected. In this system, we face the following two difficulties: (i) link scheduling in TDMA should be done in such a way that two paths can be switched without rescheduling, taking into account of the constraint of control systems. (ii) the conventional cross-layer design method of control systems is not directly applicable because round-trip delays may vary according to the path being used. Therefore, to overcome the difficulties raised by the two-path approach, we reformulate link scheduling in multihop TDMA and cross-layer design for control systems. Simulation results confirm that the proposed WNCS achieves better performance in terms of the 2-norm of CO's states.

Custody transfer in delay tolerant networks (DTNs) provides reliable end-to-end data delivery by delegating the responsibility of data transfer among special nodes (custodians) in a hop-by-hop manner. However, storage congestion occurs when data increases and/or the network is partitioned into multiple sub-networks for a long time. The storage congestion can be alleviated by message ferries which move around the network and proactively collect data from the custodians. In such a scenario, data should be aggregated to some custodians so that message ferries can collect them effectively. In this paper, we propose a scheme to aggregate data into selected custodians, called aggregators, in a fully distributed and autonomous manner with the help of evolutionary game theoretic approach. Through theoretical analysis and several simulation experiments, taking account of the uncooperative behavior of nodes, we show that aggregators can be selected in a self-organized manner and the number of aggregators can be controlled to a desired value.

Epidemic Routing is a data delivery scheme based on the store-carry-forward routing paradigm for sparsely populated mobile ad hoc networks. In Epidemic Routing, each node copies packets in its buffer into any other node that comes within its communication range. Although Epidemic Routing has short delay performance, it causes excessive buffer space utilization at nodes because many packet copies are disseminated over the network. In this paper, aiming at efficient buffer usage, we propose an XOR-based delivery scheme for Epidemic Routing, where nodes encode packets by XORing them when their buffers are full. Note that existing delivery schemes with coding are active coding, where source nodes always encode packets before transmitting them. On the other hand, the proposed scheme is passive coding, where source nodes encode packets only when buffer overflow would occur. Therefore, the behavior of the proposed scheme depends on the buffer utilization. More specifically, if sufficient buffer space is available, the proposed scheme delivers packets by the same operation as Epidemic Routing. Otherwise, it avoids buffer overflow by encoding packets. Simulation experiments show that the proposed scheme improves the packet delivery ratio.

To diffuse multimedia information services, communication networks must guarantee the quality of services (QoSs) requested by users. In addition, users should be allowed to observe the network in order to customize their own services. A new network management architecture is therefore essential. It must perceive not only node connectivity, but also network failure points and the traffic situation dynamically. This paper introduces the network map as such an architecture on personalized multimedia communication networks and proposes multiple QoS routing using the network map. Moreover, a prototype system is built in order to verify the availability of the network map.

In the Internet, because of huge scale and distributed administration, it is of practical importance to infer network-internal characteristics that cannot be measured directly. In this paper, based on a general framework we proposed previously, we present a feasible method of inferring packet loss rates of individual links from end-to-end measurement of unicast probe packets. Compared with methods using multicast probes, unicast-based inference methods are more flexible and widely applicable, whereas they have a problem with imperfect correlation in concurrent events on paths. Our method can infer link loss rates under this problem, and is applicable to various path-topologies including trees, inverse trees and their combinations. We also show simulation results which indicate potential of our unicast-based method.

We propose a new network architecture nemed Holonic Network for personalized multimedia communications, which is characterized by distributed cooperative networking based on autonomous management and all-optical transport networks. We than propose autonomous routing method. Moreover, an information searching method and a route generation method with network maps, which are essential for this network, are proposed. Lastly, we evaluate the proposed network performance by theoretical analysis and system emulation.

This paper proposes a contention-free burst scheduling scheme for optically burst-switched WDM networks. We construct contention-free wavelength planes (λ-planes) by assigning dedicated wavelengths to each ingress node. Bursts are transmitted to their egress nodes on λ-planes, along routes forming a spanning tree. As a result, contention at intermediate core nodes is completely eliminated, and contention at ingress nodes is resolved by means of electric buffers. This paper develops a spanning tree construction algorithm, aiming at balancing input loads among output ports at each ingress node. Furthermore, a wavelength assignment algorithm is proposed, which is based on the amount of traffic lost at ingress nodes. We show that the proposed scheme can decrease the burst loss probability drastically, even if traffic intensities at ingress nodes are different.

We consider a location-aware store-carry-forward routing scheme based on node density estimation (LA Routing in short), which adopts different message forwarding strategies depending on node density at contact locations where two nodes encounter. To do so, each node estimates a node density distribution based on information about contact locations. In this paper, we clarify how the estimation accuracy affects the performance of LA Routing. We also examine the performance of LA Routing when it applies to networks with homogeneous node density. Through simulation experiments, we show that LA Routing is fairly robust against the accuracy of node density estimation and its performance is comparable with Probabilistic Routing even in the case that that node density is homogeneous.

The MapReduce job scheduler implemented in Hadoop is a mechanism to decide which job is allowed to use idle resources in Hadoop. In terms of the mean job response time, the performance of the job scheduler strongly depends on the job arrival pattern, which includes job size (i.e., the amount of required resources) and their arrival order. Because existing schedulers do not utilize information about job sizes, however, those schedulers suffer severe performance degradation with some arrival patterns. In this paper, we propose a scheduler that estimates and utilizes remaining job sizes, in order to achieve good performance regardless of job arrival patterns. Through simulation experiments, we confirm that for various arrival patterns, the proposed scheduler achieves better performance than the existing schedulers.

In this paper, we study robust Principal Component Analysis (PCA)-based anomaly detection techniques in network traffic, which can detect traffic anomalies by projecting measured traffic data onto a normal subspace and an anomalous subspace. In a PCA-based anomaly detection, outliers, anomalies with excessively large traffic volume, may contaminate the subspaces and degrade the performance of the detector. To solve this problem, robust PCA methods have been studied. In a robust PCA-based anomaly detection scheme, outliers can be removed from the measured traffic data before constructing the subspaces. Although the robust PCA methods are promising, they incure high computational cost to obtain the optimal location vector and scatter matrix for the subspace. We propose a novel anomaly detection scheme by extending the minimum covariance determinant (MCD) estimator, a robust PCA method. The proposed scheme utilizes the daily periodicity in traffic volume and attempts to detect anomalies for every period of measured traffic. In each period, before constructing the subspace, outliers are removed from the measured traffic data by using a location vector and a scatter matrix obtained in the preceding period. We validate the proposed scheme by applying it to measured traffic data in the Abiline network. Numerical results show that the proposed scheme provides robust anomaly detection with less computational cost.

Network tomography is a technique for estimating internal network characteristics from end-to-end measurements. In this paper, we focus on loss tomography, which is a network tomography problem for estimating link loss rates. We study a loss tomography problem to detect links with high link loss rates in network environments with dynamically changing link loss rates, and propose a window-based sequential loss tomography scheme. The loss tomography problem is formulated as an underdetermined linear inverse problem, where there are infinitely many candidates of the solution. In the proposed scheme, we use compressed sensing, which can solve the problem with a prior information that the solution is a sparse vector. Measurement nodes transmit probe packets on measurement paths established between them, and calculate packet loss rates of measurement paths (path loss rates) from probe packets received within a window. Measurement paths are classified into normal quality and low quality states according to the path loss rates. When a measurement node finds measurement paths in the low quality states, link loss rates are estimated by compressed sensing. Using simulation scenarios with a few link states changing dynamically from low to high link loss rates, we evaluate the performance of the proposed scheme.

This survey summarizes the state-of-the-art research on network coding, mainly focusing on its applications to computer networking. Network coding generalizes traditional store-and-forward routing techniques by allowing intermediate nodes in networks to encode several received packets into a single coded packet before forwarding. Network coding was proposed in 2000, and since then, it has been studied extensively in the field of computer networking. In this survey, we first summarize linear network coding and provide a taxonomy of network coding research, i.e., the network coding design problem and network coding applications. Moreover, the latter is subdivided into throughput/capacity enhancement, robustness enhancement, network tomography, and security. We then discuss the fundamental characteristics of network coding and diverse applications of network coding in details, following the above taxonomy.