Packet classification is a fundamental task in the control of network traffic, protection from cyber threats. Most layer 3 and higher network devices have a packet classification capability that determines whether to permit or discard incoming packets by comparing their headers with a set of rules. Although linear search is an intuitive implementation of packet classification, it is very inefficient. Srinivasan et al. proposed a novel lookup scheme using a hierarchical trie instead of linear search, which realizes faster packet classification with time complexity proportional to rule length rather than the number of rules. However, the hierarchical trie and its various improved algorithms allow only single prefix rules to be processed. Since it is necessary for layer 4 and higher packet classifications to deal with arbitrary bitmask rules in the hierarchical trie, we propose a run-based trie based on the hierarchical trie, but extended to deal with arbitrary bitmask rules. Our proposed algorithm achieves O((dW)2) query time and O(NdW) space complexity with N rules of length dW. The query time of our novel alrorithm doesn't depend on the number of rules. It solves the latency problem caused by increase of the rules in firewalls.

Password-based anonymous authentication schemes provide not only password-based authentication but also user anonymity. In [15], Yang et al., proposed a password-based anonymous authentication scheme (we call it YZWB10 scheme) using the password-protected credentials. This scheme has being standardized in ISO/IEC 20009-4 that was approved to proceed to the CD stage in the 49th ISO/IEC JTC 1/SC 27 Mexico meeting. In this paper, we analyze unlinkability of the YZWB10 scheme [15]. In particular, we show that a (malicious) server in the YZWB10 scheme can specify which user actually sent the login request to the server. Unlike Yang et al.,'s claim, the YZWB10 scheme [15] does not provide unlinkability against server.

For k ≥ 3, a convex geometric graph is called k-locally outerplanar if no path of length k intersects itself. In [D. Boutin, Convex Geometric Graphs with No Short Self-intersecting Path, Congressus Numerantium 160 (2003) 205-214], Boutin stated the results of the degeneracy for 3-locally outerplanar graphs. Later, in [D. Boutin, Structure and Properties of Locally Outerplanar Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 60 (2007) 169-180], a structural property on k-locally outerplanar graphs was proposed. These results are based on the existence of “minimal corner pairs”. In this paper, we show that a “minimal corner pair” may not exist and give a counterexample to disprove the structural property. Furthermore, we generalize the result on the degeneracy with respect to k-locally outerplanar graphs.

This paper presents comprehensive comparisons on the block error rate (BLER) performance of rate-one open-loop (OL) transmit diversity schemes with four antennas for discrete Fourier transform (DFT)-precoded Orthogonal Frequency Division Multiple Access (OFDMA). One candidate scheme employs a quasi-orthogonal (QO) - space-time block code (STBC) in which four-branch minimum mean-square error (MMSE) combining is achieved at the cost of residual inter-code interference (ICI). Another candidate employs a combination of the STBC and selection transmit diversity called time switched transmit diversity (TSTD) (or frequency switched transmit diversity (FSTD)). We apply a turbo frequency domain equalizer (FDE) associated with iterative decision-feedback channel estimation (DFCE) using soft-symbol estimation to reduce channel estimation (CE) error. The turbo FDE includes an ICI canceller to reduce the influence of the residual ICI for the QO-STBC. Based on link-level simulation results, we show that a combination of the STBC and TSTD (or FSTD) is suitable as a four-antenna OL transmit diversity scheme for DFT-precoded OFDMA using the turbo FDE and iterative DFCE.

In recent years, the time variation of Internet traffic has increased due to the growth of streaming and cloud services. Backbone networks must accommodate such traffic without congestion. Traffic engineering with traffic prediction is one approach to stably accommodating time-varying traffic. In this approach, routes are calculated from predicted traffic to avoid congestion, but predictions may include errors that cause congestion. We propose prediction-based traffic engineering that is robust against prediction errors. To achieve robust control, our method uses model predictive control, a process control method based on prediction of system dynamics. Routes are calculated so that future congestion is avoided without sudden route changes. We apply calculated routes for the next time slot, and observe traffic. Using the newly observed traffic, we again predict traffic and re-calculate the routes. Repeating these steps mitigates the impact of prediction errors, because traffic predictions are corrected in each time slot. Through simulations using backbone network traffic traces, we demonstrate that our method can avoid the congestion that the other methods cannot.

A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.

We present an I/O-size second-order analog to digital converter (ADC) combined with a time-to-digital converter (TDC) and a voltage-to-time converter (VTC). Our proposed VTC is optimized for metal--oxide--metal (MOM) capacitances, and is charged to the MOM capacitances by an input voltage. In a standard 65-nm CMOS process, a signal to noise and distortion ratio (SNDR) of 50,dB (8 bits) is achievable at an input signal frequency of 78,kHz and a sampling rate of 20,MHz, where the respective area and power are 6468,mm$^{mathrm{2}}$ and 509 $mu$W. The measured maximum integral nonlinearity (INL) of the proposed ADC is $-$1.41 LSBs. The active area of the proposed ADC is smaller than an I/O buffer. The proposed ADC is useful as an ADC I/O.

In bit-patterned media recording (BPMR), the readback signal is severely corrupted by the inter-symbol interference (ISI) and inter-track interference (ITI), especially at high recording densities, due to small bit and track pitches. One way to alleviate the ITI effect is to encode an input data sequence before recording, so as to avoid some data patterns that easily cause an error at the data detection process. This paper proposes an ITI-mitigating 5/6 modulation code for a multi-track multi-head BPMR system to eliminate the data patterns that lead to severe ITI. Specifically, each of the 5 user bits is converted into a 6-bit codeword in the form of a 3-by-2 data array, based on a look-up table. Experimental results indicate that the system with the proposed coding scheme outperforms that without coding, especially when an areal density is high and/or the position jitter is large.

TV white space (TVWS) brings potential opportunities to relieve the growing spectrum scarcity. Therefore organizations like the FCC have suggested the co-channel deployment of cellular networks (CNs) on condition that a keep-out distance from the protected region of TV receivers is maintained. However the consequent CN interference has not been described. In addition, considering the wide range of TV coverage, it is also inefficient and wasteful not applying the vacant spectra for secondary user (SU) communication by opportunistic access inside the TV coverage zone. In this paper, we first investigate the aggregate interference from CNs outside the protected area to find out how the interference is generated, and then research the available spectrum resource distribution for SUs inside the TV coverage zone under aggregate interference constraints to utilize TVWS more efficiently. Specifically, we model CN in three aspects. A close-form interference probability distribution function (PDF) is proposed. Since the PDF is too complex to analyze, we approximate it as Gaussian and prove the accuracy of our approximation with Kolmogorov-Smirnov test. Then, available spectra maximization is formulated as an optimization problem under both TV and SU receiver outage probability constraints. We find that available spectra demonstrate a volcano-shaped geographical distribution and optimal network-status-aware SU transmit power exists to maximize the spectra. Our analysis reveals the characteristics of interference in TVWS and contributes to the utilization improvement of white space.

In the traditional time delay estimation methods, it is usually implicitly assumed that the observed signals are either only direct path propagate or coherently received. In practice, the multipath propagation and incoherent reception always exist simultaneously. In response to this situation, the joint maximum likelihood (ML) estimation of multipath delays and system error is proposed, and the estimation of the number of multipath is considered as well for the specific incoherent signal model. Furthermore, an algorithm based Gibbs sampling is developed to solve the multi-dimensional nonlinear ML estimation. The efficiency of the proposed estimator is demonstrated by simulation results.

Developing a practical and accurate statistical parser for low-resourced languages is a hard problem, because it requires large-scale treebanks, which are expensive and labor-intensive to build from scratch. Unsupervised grammar induction theoretically offers a way to overcome this hurdle by learning hidden syntactic structures from raw text automatically. The accuracy of grammar induction is still impractically low because frequent collocations of non-linguistically associable units are commonly found, resulting in dependency attachment errors. We introduce a novel approach to building a statistical parser for low-resourced languages by using language parameters as a guide for grammar induction. The intuition of this paper is: most dependency attachment errors are frequently used word orders which can be captured by a small prescribed set of linguistic constraints, while the rest of the language can be learned statistically by grammar induction. We then show that covering the most frequent grammar rules via our language parameters has a strong impact on the parsing accuracy in 12 languages.

Multi-hop cooperative communication has been investigated in order to overcome disadvantages such as fading, obstruction and low power. In addition, with the goal of increasing access capacity, the orthogonal frequency division multiplexing (OFDM) modulation is being advanced as a solution. In this paper, we propose the approach of relay ordering in a Decode-and-Forward OFDM scheme. Combining techniques such as maximal ratio combining and selection combining are employed at receivers and approximate outage capacity probabilities are derived for evaluating system performance over frequency selective Rayleigh fading channels. Final, the expressions are validated by Monte-Carlo simulations, and are used to compare with the same scheme based relay selection.

Weak target detection is a key problem in passive bistatic radar (PBR). Track-before-detect (TBD) is an effective solution which has drawn much attention recently. However, TBD has not been fully developed in PBR. In this paper, the transition function and the selection of parameters in dynamic programming are analyzed in PBR. Then a novel processing scheme of dynamic programming based TBD is proposed to reduce the computation complexity without severely decreasing the detection performance. Discussions including complexity, detection performance, threshold determination, selection of parameters and detection of multitarget, are presented in detail. The new method can provide fast implementation with only a slight performance penalty. In addition, good multitarget detection performance can be achieved by using this method. Simulations are carried out to present the performance of the proposed processing scheme.

To ensure the security of image transmission, this paper presents a new image encryption algorithm based on a genetic algorithm (GA) and a piecewise linear chaotic map (PWLCM), which adopts the classical diffusion-substitution architecture. The GA is used to identify and output the optimal encrypted image that has the highest entropy value, the lowest correlation coefficient among adjacent pixels and the strongest ability to resist differential attack. The PWLCM is used to scramble pixel positions and change pixel values. Experiments and analyses show that the new algorithm possesses a large key space and resists brute-force, statistical and differential attacks. Meanwhile, the comparative analysis also indicates the superiority of our proposed algorithm over a similar, recently published, algorithm.

In this paper, we investigate iterative detection and decoding, a.k.a. turbo detection, for multiple-input multiple-output (MIMO) transmission. Specifically, we consider using a low complexity soft-in/soft-out MIMO detector based on belief propagation over a pair-wise graph that accepts a priori information feedback from a channel decoder. Simulation results confirm that considerable performance improvement can be obtained with only a few detection-and-decoding iterations if convolutional channel coding is used. A brief estimate is given of the overall complexity of turbo detectors, to verify the key argument that the performance of a maximum a posteriori (MAP) detector (without turbo iteration) can be achieved, at much lower computation cost, by using the low complexity soft-in/soft-out MIMO detector under consideration.

This paper proposes an ultra-low power fully on-chip CMOS relaxation oscillator (ROSC) for a real-time clock application. The proposed ROSC employs a compensation circuit of a comparator's non-idealities caused by offset voltage and delay time. The ROSC can generate a stable, and 32-kHz oscillation clock frequency without increasing power dissipation by using a low reference voltage and employing a novel compensation architecture for comparators. Measurement results in a 0.18-$mu$m CMOS process demonstrated that the circuit can generate a stable clock frequency of 32.55,kHz with low power dissipation of 472,nW at 1.8-V power supply. Measured line regulation and temperature coefficient were 1.1%/V and 120,ppm/$^{circ}$C, respectively.

Objects tracking methods have been wildly used in the field of video surveillance, motion monitoring, robotics and so on. Particle filter is one of the promising methods, but it is difficult to apply to real-time objects tracking because of its high computation cost. In order to reduce the processing cost without sacrificing the tracking quality, this paper proposes a new method for real-time 3D objects tracking, using parallelized particle filter algorithms by MapReduce architecture which is running on GPGPU. Our methods are as follows. First, we use a Kinect to get the 3D information of objects. Unlike the conventional 2D-based objects tracking, 3D objects tracking adds depth information. It can track not only from the x and y axis but also from the z axis, and the depth information can correct some errors in 2D objects tracking. Second, to solve the high computation cost problem, we use the MapReduce architecture on GPGPU to parallelize the particle filter algorithm. We implement the particle filter algorithms on GPU and evaluate the performance by actually running a program on CUDA5.5.

In recent years, various applications based on propagation characteristics have been developed. They generally utilize the locality of the fading characteristics of multipath environments. On the other hand, if a received signal at a remote location can be estimated beyond the correlation distance of the multipath fading environment, a wide variety of new applications can be possible. In this paper, we attempt to estimate a received signal at a remote location using the MUSIC method and the least squares method. Based on the plane wave assumption for each arriving wave, multipath environment is analyzed through estimation of the directions of arrival by the MUISC method and the complex amplitudes of the received signals by the least squares method, respectively. We present evaluation results on the estimation performance of the method by computer simulations.

Cell voltage equalizers are necessary to ensure years of operation and maximize the chargeable/dischargeable energy of series-connected supercapacitors (SCs). A two-switch voltage equalizer using a series-resonant voltage multiplier operating in frequency-multiplied discontinuous conduction mode (DCM) is proposed for series-connected SCs in this paper. The frequency-multiplied mode virtually increases the operation frequency and hence mitigates the negative impact of the impedance mismatch of capacitors on equalization performance, allowing multi-layer ceramic capacitors (MLCCs) to be used instead of bulky and costly tantalum capacitors, the conventional approach when using voltage multipliers in equalizers. Furthermore, the DCM operation inherently provides the constant current characteristic, realizing the excessive current protection that is desirable for SCs, which experience 0V and equivalently become an equivalent short-circuit load. Experimental equalization tests were performed for eight SCs connected in series under two frequency conditions to verify the improved equalization performance at the increased virtual operation frequencies. The standard deviation of cell voltages under the higher-frequency condition was lower than that under the lower-frequency condition, demonstrating superior equalization performance at higher frequencies.

The present paper proposes a method for simultaneously estimating the direction of arrival (DOA) and delay of multipath signals through the virtual array reception of broadband signals. In order to confirm the principles behind the proposed method, a broadband signal of 42MHz, equivalent to seven adjacent TV channels being transmitted from the Tokyo Skytree, was acquired and stored in a personal computer as the reception signal, which acts as reference signal. In addition, a multipath signal with DOA and delay was generated using a personal computer. Signal processing revealed that DOA and delay could be identified correctly. Finally, a multipath propagation analysis is conducted for an actual outdoor propagation environment as a demonstration of the proposed method.