Hiroshi FUJIWARA Takahiro SEKI Toshihiro FUJITO
We consider a problem as follows: Given unit weights arriving in an online manner with the total cardinality unknown, upon each arrival we decide where to place it on the unit circle in $mathbb{R}^{2}$. The objective is to set the center of mass of the placed weights as close to the origin as possible. We apply competitive analysis defining the competitive difference as a performance measure. We first present an optimal strategy for placing unit weights which achieves a competitive difference of $rac{1}{5}$. We next consider a variant in which the destination of each weight must be chosen from a set of positions that equally divide the unit circle. We give a simple strategy whose competitive difference is 0.35. Moreover, in the offline setting, several conditions for the center of mass to lie at the origin are derived.
Mengmeng ZHANG Heng ZHANG Zhi LIU
The new generation video standard, i.e., High-efficiency Video Coding (HEVC), shows a significantly improved efficiency relative to the last standard, i.e., H.264. However, the quad tree structured coding units (CUs), which are adopted in HEVC to improve compression efficiency, cause high computational complexity. In this study, a novel fast algorithm is proposed for CU partition in intra coding to reduce the computational complexity. A rough minimum depth prediction of the largest CU method and an early termination method for CU partition based on the total coding bits of the current CU are employed. Many approaches have been proposed to reduce the encoding complexity of HEVC, but these methods do not use the total coding bits of the current CU as the main basis for judgment to judge the CU complexity. Compared with the reference software HM16.6, the proposed algorithm reduces encoding time by 45% on average and achieves an approximately 1.1% increase in Bjntegaard delta bit rate and a negligible peak signal-to-noise ratio loss.
In this letter, we propose a blind adaptive algorithm for joint compensation of inter-block interference (IBI) and frequency-dependent IQ imbalance using a single time-domain equalizer. We combine the MERRY algorithm for IBI suppression with the differential constant modulus algorithm to compensate for IQ imbalance. The effectiveness of the proposed algorithm is shown through computer simulations.
GuoJian OU ShiZhong YANG JianXun DENG QingPing JIANG TianQi ZHANG
This paper describes a fast and effective algorithm for refining the parameter estimates of multicomponent third-order polynomial phase signals (PPSs). The efficiency of the proposed algorithm is accompanied by lower signal-to-noise ratio (SNR) threshold, and computational complexity. A two-step procedure is used to estimate the parameters of multicomponent third-order PPSs. In the first step, an initial estimate for the phase parameters can be obtained by using fast Fourier transformation (FFT), k-means algorithm and three time positions. In the second step, these initial estimates are refined by a simple moving average filter and singular value decomposition (SVD). The SNR threshold of the proposed algorithm is lower than those of the non-linear least square (NLS) method and the estimation refinement method even though it uses a simple moving average filter. In addition, the proposed method is characterized by significantly lower complexity than computationally intensive NLS methods. Simulations confirm the effectiveness of the proposed method.
Makoto TAKITA Masanori HIROTOMO Masakatu MORII
Cassuto and Blaum presented a new coding framework for channels whose outputs are overlapping pairs of symbols in storage applications. Such channels are called symbol-pair read channels. Pair distance and pair error are used in symbol-pair read channels. Yaakobi et al. proved a lower bound on the minimum pair distance of cyclic codes. Furthermore, they provided a decoding algorithm for correcting pair errors using a decoder for cyclic codes, and showed the number of pair errors that can be corrected by their algorithm. However, their algorithm cannot correct all pair error vectors within half of the minimum pair distance. In this paper, we propose an efficient decoding algorithm for cyclic codes over symbol-pair read channels. It is based on the relationship between pair errors and syndromes. In addition, we show that the proposed algorithm can correct more pair errors than Yaakobi's algorithm.
Gang DENG Hong WANG Zhenghu GONG Lin CHEN Xu ZHOU
Address configuration is a key problem in data center networks. The core issue of automatic address configuration is assigning logical addresses to the physical network according to a blueprint, namely logical-to-device ID mapping, which can be formulated as a graph isomorphic problem and is hard. Recently years, some work has been proposed for this problem, such as DAC and ETAC. DAC adopts a sub-graph isomorphic algorithm. By leveraging the structure characteristic of data center network, DAC can finish the mapping process quickly when there is no malfunction. However, in the presence of any malfunctions, DAC need human effort to correct these malfunctions and thus is time-consuming. ETAC improves on DAC and can finish mapping even in the presence of malfunctions. However, ETAC also suffers from some robustness and efficiency problems. In this paper, we present GA-MAP, a data center networks address mapping algorithm based on genetic algorithm. By intelligently leveraging the structure characteristic of data center networks and the global search characteristic of genetic algorithm, GA-MAP can solve the address mapping problem quickly. Moreover, GA-MAP can even finish address mapping when physical network involved in malfunctions, making it more robust than ETAC. We evaluate GA-MAP via extensive simulation in several of aspects, including computation time, error-tolerance, convergence characteristic and the influence of population size. The simulation results demonstrate that GA-MAP is effective for data center addresses mapping.
Shixiong WANG Longjiang QU Chao LI Shaojing FU
In this paper, we investigate the security property of RSA when some middle bits of the private key d are known to an attacker. Using the technique of unravelled linearization, we present a new attack on RSA with known middle bits, which improves a previous result under certain circumstance. Our approach is based on Coppersmith's method for finding small roots of modular polynomial equations.
Yuta NAKATANI Atsushi TAKAHASHI
In the routing design of interposer and etc., the combination of a pin pair to be connected by wire is often flexible, and the reductions of the total wire length and the length difference are pursued to keep the circuit performance. Even though the total wire length can be minimized by finding a minimum cost maximum flow in set pair routing problems, the length difference is often large, and the reduction of it is not easy. In this paper, an algorithm that reduces the length difference while keeping the total wire length small is proposed. In the proposed algorithm, an initial routing first obtained by a minimum cost maximum flow. Then it is modified to reduce the maximum length while keeping the minimum total wire length, and a connection of the minimum length is detoured to reduce the length difference. The effectiveness of the proposed algorithm is confirmed by experiments.
Yohei ONISHI Hidaka KINUGASA Takashi MURAKI Motohiko ISAKA
We present numerical results on the rate-distortion performance of convolutional coding for the binary symmetric source, and show how convolutional codes approach the rate-distortion bound by increasing the trellis states.
SeongHan SHIN Kazukuni KOBARA Hideki IMAI
In the literature, many cryptosystems have been proposed to be secure under the Strong Diffie-Hellman (SDH) and related problems. For example, there is a cryptosystem that is based on the SDH/related problem or allows the Diffie-Hellman oracle. If the cryptosystem employs general domain parameters, this leads to a significant security loss caused by Cheon's algorithm [14], [15]. However, all elliptic curve domain parameters explicitly recommended in the standards (e.g., ANSI X9.62/63 [1], [2], FIPS PUB 186-4 [43], SEC 2 [50], [51]) are susceptible to Cheon's algorithm [14], [15]. In this paper, we first prove that (q-1)(q+1) is always divisible by 24 for any prime order q>3. Based on this result and depending on small divisors d1,d2≤(log q)2, we classify primes q>3, such that both (q-1)/d1 and (q+1)/d2 are primes, into Perfect, Semiperfect, SEC1v2 and Acceptable. Then, we describe algorithmic procedures and show their simulation results of secure elliptic curve domain parameters over prime/character 2 finite fields resistant to Cheon's algorithm [14], [15]. Also, several examples of the secure elliptic curve domain parameters (including Perfect or Semiperfect prime q) are followed.
Daniel LAGO Edmundo MADEIRA Deep MEDHI
With the growth of cloud-based services, cloud data centers are experiencing large growth. A key component in a cloud data center is the network technology deployed. In particular, Ethernet technology, commonly deployed in cloud data centers, is already envisioned for 10 Tbps Ethernet. In this paper, we study and analyze the makespan, workload execution times, and virtual machine migrations as the network speed increases. In particular, we consider homogeneous and heterogeneous data centers, virtual machine scheduling algorithms, and workload scheduling algorithms. Results obtained from our study indicate that the increase in a network's speed reduces makespan and workloads execution times, while aiding in the increase of the number of virtual machine migrations. We further observed that the number of migrations' behaviors in relation to the speed of the networks also depends on the employed virtual machines scheduling algorithm.
Weiqin YING Yuehong XIE Xing XU Yu WU An XU Zhenyu WANG
The conical area evolutionary algorithm (CAEA) has a very high run-time efficiency for bi-objective optimization, but it can not tackle problems with more than two objectives. In this letter, a conical hypervolume evolutionary algorithm (CHEA) is proposed to extend the CAEA to a higher dimensional objective space. CHEA partitions objective spaces into a series of conical subregions and retains only one elitist individual for every subregion within a compact elitist archive. Additionally, each offspring needs to be compared only with the elitist individual in the same subregion in terms of the local hypervolume scalar indicator. Experimental results on 5-objective test problems have revealed that CHEA can obtain the satisfactory overall performance on both run-time efficiency and solution quality.
Due to its on-demand and pay-as-you-go properties, cloud computing has become an attractive alternative for HPC applications. However, communication-intensive applications with complex communication patterns still cannot be performed efficiently on cloud platforms, which are equipped with MapReduce technologies, such as Hadoop and Spark. In particular, one major obstacle is that MapReduce's simple programming model cannot explicitly manipulate data transfers between compute nodes. Another obstacle is cloud's relatively poor network performance compared with traditional HPC platforms. The traditional Strassen's algorithm of square matrix multiplication has a recursive and complex pattern on the HPC platform. Therefore, it cannot be directly applied to the cloud platform. In this paper, we demonstrate how to make Strassen's algorithm with complex communication patterns “cloud-friendly”. By reorganizing Strassen's algorithm in an iterative pattern, we completely separate its computations and communications, making it fit to MapReduce programming model. By adopting a novel data/task parallel strategy, we solve Strassen's data dependency problems, making it well balanced. This is the first instance of Strassen's algorithm in MapReduce-style systems, which also matches Strassen's communication lower bound. Further experimental results show that it achieves a speedup ranging from 1.03× to 2.50× over the classical Θ(n3) algorithm. We believe the principle can be applied to many other complex scientific applications.
This paper proposes a network clock system that detects degradation in the frequency accuracy of network clocks distributed across a network and finds the sources of the degradation. This system uses two factors to identify degradation in frequency accuracy and an algorithm that finds degradation sources by integrating and analyzing the evaluation results gathered from the entire network. Many frequency stability measurement systems have been proposed, and most are based on time synchronization protocols. These systems also realize avoidance of frequency degradation and identification of the sources of the degradation. Unfortunately, the use of time synchronization protocols is impractical if the service provider, such as NTT, has already installed a frequency synchronization system; the provider must replace massive amounts of equipment with new devices that support the time synchronization protocols. Considering the expenditure of installment, this is an excessive burden on service providers. Therefore, a new system that can detect of frequency degradation in network clocks and identify the degradation causes without requiring new equipment is strongly demanded. The proposals made here are implemented by the installation of new circuit cards in current equipment and installing a server that runs the algorithm. This proposed system is currently being installed in NTT's network.
Yinfang HONG Hui LI Wenping MA Xinmei WANG
In the log-likelihood ratio (LLR) domain, the belief propagation (BP) decoding algorithm for polar codes incurs high computation complexity due to the computation of the hyperbolic functions in the node update rules. In this paper, we propose a linear approximation method based on the principle of equal spacing to simplify the hyperbolic functions in the BP decoding algorithm. Our method replaces the computation of hyperbolic functions with addition and multiplication operations in the node update rules. Simulation results show that the performance of the modified BP decoding algorithm is almost the same as the original BP decoding algorithm in the low Signal to Noise Ratio (SNR) region, and in the high SNR region the performance of our method is slightly worse. The modified BP decoding algorithm is only implemented with addition and multiplication operations, which greatly reduces computation complexity, and simplifies hardware implementation.
Yukiko MATSUSHIMA Nobuo FUNABIKI
Homemade cooking plays a key role for a healthy and cost-efficient life. Unfortunately, preparing multiple dishes is generally time-consuming. In this paper, an algorithm is proposed to minimize the cooking time by scheduling the cooking-step of multiple dishes. The cooking procedure of a dish is divided into a sequence of six types of cooking-steps to consider the constraints in cooks and cooking utensils in a kitchen. A cooking model is presented to optimize the cooking-step schedule and estimate the cooking time for a given starting order of dishes under various constraints of cooks and utensils. Then, a high-quality schedule is sought by repeating the generation of a new order and the model application based on exhaustive search and simulated annealing. Our simulation results and cooking experiments confirm the effectiveness of our proposal.
Tomoyuki SASAKI Hidehiro NAKANO Arata MIYAUCHI Akira TAGUCHI
This paper presents a particle swarm optimization network (PSON) to improve the search capability of PSO. In PSON, multi-PSOs are connected for the purpose of communication. A variety of network topology can be realized by varying the number of connected PSOs of each PSO. The solving performance and convergence speed can be controlled by changing the network topology. Furthermore, high parallelism is can be realized by assigning PSO to single processor. The stability condition analysis and performance of PSON are shown.
Yilong ZHANG Yuehua LI Guanhua HE Sheng ZHANG
Aperture synthesis technology represents an effective approach to millimeter-wave radiometers for high-resolution observations. However, the application of synthetic aperture imaging radiometer (SAIR) is limited by its large number of antennas, receivers and correlators, which may increase noise and cause the image distortion. To solve those problems, this letter proposes a compressive regularization imaging algorithm, called CRIA, to reconstruct images accurately via combining the sparsity and the energy functional of target space. With randomly selected visibility samples, CRIA employs l1 norm to reconstruct the target brightness temperature and l2 norm to estimate the energy functional of it simultaneously. Comparisons with other algorithms show that CRIA provides higher quality target brightness temperature images at a lower data level.
Hann-Tzong CHERN Chun-Chieh LEE Jhih-Syue JHOU
In Worldwide interoperability for Microwave Access (WiMAX) network, QoS(quality of service) is provided for service flows. For this, five classes of services are defined in IEEE 802.16. They are Unsolicited Grant Service (UGS), Extended Real-Time Polling Service (ertPS), Real-Time Polling Service (rtPS), Non Real-Time Polling Service (nrtPS) and Best Effort (BE). For real-time classes, the sent packet has a deadline. As the transmission delay is over the limitation of deadline, the packet becomes useless and will be discarded. Thus, they will be served earlier and have higher probability. Nevertheless, non-real-time packets need also to be served from time to time. The scheduler should assign proper bandwidth for non-real-time flows and send the real-time packets before they are discarded. To deicide the right allocated bandwidth, the arrival rate of each flow is a good parameter for assignment. The average µ and standard deviation σ of arrival rate correspond to the long term need and variation of load for one flow. Thus, we proposed a scheduling algorithm named BAcSOA in which µ+kσ is used as a reference to allocate bandwidth with weighted round robin for one flow [5]. Different classes of flows will be given different values of k which corresponds to the priorities of classes. In this algorithm, flow with higher priority should have larger value of k. The value of k will decide the performance of this class. In this paper, we revise the algorithm to EBAcSOA and propose a mathematical way to decide the value of k for a required performance. Then, a simulation platform is proposed to decide k such that a required performance can be obtained for an operating system. This approach may be different from other researches in which there is no required performance and the performance results are obtained only for several operating points. However, the approach proposed is more practical from the view of an operator and may become an attractive point for other researchers.
Anxin LI Anass BENJEBBOUR Xiaohang CHEN Huiling JIANG Hidetoshi KAYAMA
Non-orthogonal multiple access (NOMA) utilizing the power domain and advanced receiver has been considered as one promising multiple access technology for further cellular enhancements toward the 5th generation (5G) mobile communications system. Most of the existing investigations into NOMA focus on the combination of NOMA with orthogonal frequency division multiple access (OFDMA) for either downlink or uplink. In this paper, we investigate NOMA for uplink with single carrier-frequency division multiple access (SC-FDMA) being used. Differently from OFDMA, SC-FDMA requires consecutive resource allocation to a user equipment (UE) in order to achieve low peak to average power ratio (PAPR) transmission by the UE. Therefore, sophisticated designs of scheduling algorithm for NOMA with SC-FDMA are needed. To this end, this paper investigates the key issues of uplink NOMA scheduling such as UE grouping method and resource widening strategy. Because the optimal schemes have high computational complexity, novel schemes with low computational complexity are proposed for practical usage for uplink resource allocation of NOMA with SC-FDMA. On the basis of the proposed scheduling schemes, the performance of NOMA is investigated by system-level simulations in order to provide insights into the suitability of using NOMA for uplink radio access. Key issues impacting NOMA performance are evaluated and analyzed, such as scheduling granularity, UE number and the combination with fractional frequency reuse (FFR). Simulation results verify the effectiveness of the proposed algorithms and show that NOMA is a promising radio access technology for 5G systems.