Hyogon KIM Jongwon YOON Heejo LEE
We analytically prove that the error in the channel idle time-based collision probability estimation in face of non-saturated stations is bounded by 2/(CWmin+1) in the IEEE 802.11 wireless LANs (WLANs). This work explicitly quantifies the impact of non-saturation, and the result vindicates the use of the estimation technique in real-life IEEE 802.11 WLANs, in such applications as the acknowledgement-based link adaptation and the throughput optimization through contention window size adaptation.
Gang QIN Shingo ATA Ikuo OKA Chikato FUJIWARA
This paper investigates fast Packet Classification techniques, where a large routing table is divided into many much smaller tables by an index key at first; the resulting small tables are much easier to search. A traditional way is to use the front bits as the index key, but we show it's not an effective way to divide a routing table. In this paper, we propose three bit selection methods for division. They can be implemented by CAM or hash structure. Simulations show that the bit selection methods decrease the delay of classification 50% compared to the traditional method. We also propose an optimized method which is adapted to the biased traffic pattern, which shows 70% improvement in our simulation.
OBS is a realistic solution to the mismatch of the capacity of optical fiber and electrical switching in backbone photonic networks. One of the critical issues in OBS networks is to avoid burst contention at transit nodes. This problem induces the rapid growth of burst-transmission delay time under heavy traffic loads. In this paper, we propose a low-delay burst transmission scheme using burst segmentation at source node to suppress the growth in burst-transmission delay. In our scheme, a burst is divided and burst-transfer time is determined by the multiple information about reservation of other bursts at all transit nodes. We analyzed capabilities of the proposed scheme and found that it more efficiently suppresses the growth of the burst-transmission delay time in heavy traffic loads compared with some conventional signaling schemes.
Takeshi KUMAKI Yutaka KONO Masakatsu ISHIZAKI Tetsushi KOIDE Hans Jurgen MATTAUSCH
This paper presents a scalable FPGA/ASIC implementation architecture for high-speed parallel table-lookup-coding using multi-ported content addressable memory, aiming at facilitating effective table-lookup-coding solutions. The multi-ported CAM adopts a Flexible Multi-ported Content Addressable Memory (FMCAM) technology, which represents an effective parallel processing architecture and was previously reported in [1]. To achieve a high-speed parallel table-lookup-coding solution, FMCAM is improved by additional schemes for a single search mode and counting value setting mode, so that it permits fast parallel table-lookup-coding operations. Evaluation results for Huffman encoding within the JPEG application show that a synthesized semi-custom ASIC implementation of the proposed architecture can already reduce the required clock-cycle number by 93% in comparison to a conventional DSP. Furthermore, the performance per area unit, measured in MOPS/mm2, can be improved by a factor of 3.8 in comparison to parallel operated DSPs. Consequently, the proposed architecture is very suitable for FPGA/ASIC implementation, and is a promising solution for small area integrated realization of real-time table-lookup-coding applications.
Under the broadband-ubiquitous environment, digital content creation/distribution will be the key factor to activating new industries. This paper first describes the impact of a broadband-ubiquitous environment on digital content creation/distribution; then it proposes new models for digital content creation/distribution businesses. In a broadband-ubiquitous environment, the key is creation of moving picture content; thus the paper describes a system that allows non-CG experts to make CG movies easily.
Shen LI Lingfeng LI Takeshi IKENAGA Shunichi ISHIWATA Masataka MATSUI Satoshi GOTO
The coexistence of MPEG-2 and its powerful successor H.264/AVC has created a huge need for MPEG-2/H.264 video transcoding. However, a traditional transcoder where an MPEG-2 decoder is simply cascaded to an H.264 encoder requires huge computational power due to the adoption of a complicated rate-distortion based mode decision process in H.264. This paper proposes a 2-D Sobel filter based motion vector domain method and a DCT domain method to measure macroblock complexity and realize content-based H.264 candidate mode decision. A new local edge based fast INTRA prediction mode decision method is also adopted to boost the encoding efficiency. Simulation results confirm that with the proposed methods the computational burden of a traditional transcoder can be reduced by 20%30% with only a negligible bit-rate increase for a wide range of video sequences.
Takeshi KUMAKI Yasuto KURODA Masakatsu ISHIZAKI Tetsushi KOIDE Hans Jurgen MATTAUSCH Hideyuki NODA Katsumi DOSAKA Kazutami ARIMOTO Kazunori SAITO
This paper presents a novel optimized real-time Huffman encoder using a pipelined data path based on CAM technology and a parallel code-word-table optimizer. The exploitation of CAM technology enables fast parallel search of the code word table. At the same time, the code word table is optimized according to the frequency of received input symbols and is up-dated in real-time. Since these two functions work in parallel, the proposed architecture realizes fast parallel encoding and keeps a constantly high compression ratio. Evaluation results for the JPEG application show that the proposed architecture can achieve up to 28% smaller encoded picture sizes than the conventional architectures. The obtained encoding time can be reduced by 95% in comparison to a conventional SRAM-based architecture, which is suitable even for the latest end-user-devices requiring fast frame-rates. Furthermore, the proposed architecture provides the only encoder that can simultaneously realize small compressed data size and fast processing speed.
Seunglak CHOI Jinwon LEE Su Myeon KIM Junehwa SONG Yoon-Joon LEE
Most commercial Web sites dynamically generate their contents through a three-tier server architecture composed of a Web server, an application server, and a database server. In such an architecture, the database server easily becomes a bottleneck to the overall performance. In this paper, we propose WDBAccel, a high-performance database server accelerator that significantly improves the throughput of database processing. WDBAccel eliminates costly, complex query processing needed to obtain query results by reusing the results from previous queries for subsequent queries. This differentiates WDBAccel from other database cache systems, which employ traditional query processing. WDBAccel further improves its performance by fully utilizing main memory as the primary storage. This paper presents the design and implementation of the WDBAccel as well as the results of performance evaluation with a prototype.
With today's advances in peer-to-peer (P2P) techniques, a lot of non-document content has become searchable and usable. In the near future, since a huge amount of content will be distributed over the networks, not only index server searching but also P2P searching will become important because of its scalability and robustness. Typical P2P content searching services have some problems, such as low search precision ratio, significant increase in traffic and inundations of malicious content such as viruses. We propose a P2P content searching method in which a query is effectively forwarded only to peers that have indices of content semantically similar to the wanted content but not forwarded to the same peer repeatedly. It is based on the ideas of content addressable network (CAN) topology and a vector space method where vectors have a variable length. It maps non-document content to a vector space based on users' evaluations and manages the vector space or routes queries using the CAN topology control. The effectiveness of our method is shown by both analytical estimations and simulation experiments. The simulations clarified that our method is effective at improving the precision and recall ratios while reducing the amount of traffic compared with Gnutella flooding, the vector space method in which vector lengths are fixed (similar to the pSearch method), and Chord. In particular, when there was a lot of malicious content, our method exhibited a higher precision ratio than other methods.
Mansoo PARK Hoi-Rin KIM Yong Man RO Munchurl KIM
The noise robustness of an audio fingerprinting system is one of the most important issues in music information retrieval by the content-based audio identification technique. In a real environment, sound recordings are commonly distorted by channel and background noise. Recently, Philips published a robust and efficient audio fingerprinting system for audio identification. To extract a robust and efficient audio fingerprint, Philips applied the first derivative (differential) to the frequency-time sequence of the perceptual filter-bank energies. In practice, however, the noise robustness of Philips' audio fingerprinting scheme is still insufficient. In this paper, we introduce an extension method of the audio fingerprinting scheme for the enhancement of noise robustness. As an alternative to frequency filtering, a type of band-pass filter, instead of a high-pass filter, is used to achieve robustness to background noise in a real situation. Our experimental results show that the proposed filter improves the noise robustness in audio identification.
Huhnkuk LIM Changhwan OH Chang-Soo PARK
In an effort to reduce switch cost, we present the optimum numbers of tunable wavelength converters (TWCs) and internal wavelengths required for contention resolution of asynchronous and variable length packets, in the optical packet switch (OPS) with the shared fiber delay line (FDL) buffer. To optimize TWCs and internal wavelengths related to OPS design cost, we proposed a scheduling algorithm for the limited TWCs and internal wavelengths. For three TWC alternatives (not shared, partially shared, and fully shared cases), the optimum numbers of TWCs and internal wavelengths to guarantee minimum packet loss are evaluated to prevent resource waste. Under a given load, TWCs and internal wavelengths could be significantly reduced, guaranteeing the same packet loss as the performance of an OPS with full TWCs and internal wavelengths.
Content-based publish/subscribe systems provide a useful alternative to traditional address-based communication due to their ability to decouple communication between participants. It has remained a challenge to design a scalable overlay supporting the complexity of content-based networks, while satisfying the desirable properties large distributed systems should have. This paper presents the design of Mirinae, a new structured peer-to-peer overlay mesh based on the interests of peers. Given an event, Mirinae provides a flexible and efficient dissemination tree minimizing the participation of non-matching nodes. We also present a novel ID space transformation mechanism for balancing routing load of peers even with highly skewed data, which is typical of the real world. Our evaluation demonstrates that Mirinae is able to achieve its goals of scalability, efficiency, and near-uniform load balancing. Mirinae can be used as a substrate for content-search and range query in other important distributed applications.
Koji ABE Hiromasa IGUCHI Haiyan TIAN Debabrata ROY
According to the Gestalt principals, this paper presents a recognition method of grouping areas in trademark images modeling features for measuring the attraction degree between couples of image components. This investigation would be used for content-based image retrieval from the view of mirroring human perception for images. Depending on variability in human perception for trademark images, the proposed method finds grouping areas by calculating Mahalanobis distance with the features to every combination of two components in images. The features are extracted from every combination of two components in images, and the features represent proximity, shape similarity, and closure between two components. In addition, changing combination of the features, plural grouping patterns are output. Besides, this paper shows the efficiency and limits of the proposed method from experimental results. In the experiments, 104 participants have perceived grouping patterns to 74 trademark images and the human perceptions have been compared with outputs by the proposed method for the 74 images.
Daisuke TAKEMOTO Shigeaki TAGASHIRA Satoshi FUJITA
In this paper, we propose a new method to enhance the fault-tolerance of the Content Addressable Network (CAN), which is known as a typical pure P2P system based on the notion of Distributed Hash Table (DHT). The basic idea of the proposed method is to introduce redundancy to the management of index information distributed over the nodes in the given P2P network, by allowing each index to be assigned to several nodes, which was restricted to be one in the original CAN system. To keep the consistency among several copies of indices, we propose an efficient synchronization scheme based on the notion of labels assigned to each copy in a distinct manner. The performance of the proposed scheme is evaluated by simulation. The result of simulations indicates that the proposed scheme significantly enhances the fault-tolerance of the CAN system.
Vincenzo ERAMO Marco LISTANTI Luca Silvio BOVO
This paper compares selected Optical Packet Switching architectures that use the wavelength conversion technique to solve the packet contention problem. The architectures in question share wavelength converters, which are needed to wavelength translate arriving packets. This paper focuses on two architectures: the Shared Per Output Line (SPOL) and the Shared Per Input Line (SPIL) architectures, in which the wavelength converters are shared per output and input fiber respectively. The performance of the proposed architectures is evaluated for all the balance/unbalance combinations of input/output traffic. Packet loss probability is expressed as a function of the number of wavelength converters used, by means of analytical models validated by simulations. The results obtained show that the SPIL architecture, when compared to the SPOL architecture, allows for greater economies in terms of number of wavelength converters needed. While the performance of the two architectures tends to have similar values in a scenario with unbalanced input traffic and balanced output traffic, in unbalanced output traffic scenarios the SPIL architecture requires about 50% less wavelength converters than the SPOL architecture does, for a given packet loss probability.
Tazuko TOMIOKA Hiroyuki IBE Masatoshi SUZUKI Jun TAKEHARA Kyousuke DOBASHI Hiroyuki INAMURA
The characteristics of various techniques, including some new techniques, in mitigating wavelength contention in optical path setups were compared by simulations. The assumed network here is a WDM photonic network in which each node is equipped with a limited number of wavelength-tunable optical transceivers. In the photonic network, the frequency of optical path setups and releases is very high, because optical path lifetime is short and optical transceivers are time-shared, and therefore, the wavelength contention becomes a serious problem. In this paper, we propose four new techniques to mitigate the phenomenon. In those techniques, a new small-sized parameter, the history number, was introduced based on the conceptual requirements of the assumed network, namely, low-cost and low additional control load. The four proposed techniques are history recording (HR), history notifying (HN), conditional random selection (CRS), and HN with dithering target (HNDT). We have evaluated the characteristics of those techniques along with those of two conventional techniques: no mitigation and random selection (RS). The simulations were carried out while varying four parameters: the maximum generation number, the optical path lifetime, the number of wavelengths, and the number of optical transceivers per node. Consequently, it is clarified that for a sufficient number of wavelengths, namely, almost no limitation on number of wavelengths, the CRS technique is advantageous, and for a small number of wavelengths the HNDT technique is advantageous.
Shen LI Takeshi IKENAGA Hideki TAKEDA Masataka MATSUI Satoshi GOTO
Power efficiency and real-time processing capability are two major issues in today's mobile video applications. We proposed a novel Motion Estimation (ME) engine for power-efficient real-time MPEG-4 video coding based on our previously proposed content-based ME algorithm [8],[13]. By adopting Full Search (FS) and Three Step Search (TSS) alternatively according to the nature of video contents, this algorithm keeps the visual quality very close to that of FS with only 3% of its computational power. We designed a flexible Block Matching (BM) Unit with 16-PE SIMD data path so that the adaptive ME can be performed at a much lower clock frequency and hardware cost as compared with previous FS based work. To reduce the energy cost caused by excessive external memory access, on-chip SRAM is also utilized and optimized for parallel processing in the BM Unit. The ME engine is fabricated with TSMC 0.18 µm technology. When processing QCIF (15 fps) video, the estimated power is 2.88 mW@4.16 MHz (supply voltage: 1.62 V). It is believed to be a favorable contribution to the video encoder LSI design for mobile applications.
Hideki TODE ZhengYu XIE Koso MURAKAMI
At present, a demand to the technology of contents distribution by which each user can request the desired content through network is increasing. There are some merits and demerits respectively with the existing on-demand systems for contents distribution, such as the methods based on broadcast and select transfer or multicast one. In this paper, we propose a hybrid scheduling method which adaptively uses both broadcasting and multicasting in order to improve the system efficiency. Adequate channel boundary to adopt two different transfer mechanisms is found through analytical consideration. Also, performance improvement of our proposal is verified in terms of response time and request blocking rate through computer simulation.
LaeYoung KIM SuKyoung LEE JooSeok SONG
The most important design goal in Optical Burst Switching (OBS) networks is to reduce burst loss resulting from resource contention. Especially, the higher the congestion degree in the network is, the higher the burst loss rate becomes. The burst loss performance can be improved by employing a judicious congestion control. In this paper, to actively avoid contentions, we propose a peak load-based congestion control scheme that operates based on the highest (called peak load) of the loads of all links over the path between each pair of ingress and egress nodes in an OBS network. Simulation results show that the proposed scheme reduces the burst loss rate significantly, compared to existing OBS protocols, while maintaining reasonable throughput and fairness.
Chenyu PAN Merdan ATAJANOV Mohammad BELAYET HOSSAIN Toshihiko SHIMOKAWA Norihiko YOSHIDA
With the rapid spread of information and ubiquitous access of browsers, flash crowds, a sudden, unanticipated surge in the volume of request rates, have become the bane of many Internet websites. This paper models and presents FCAN, an adaptive network that dynamically optimizes the system structure between peer-to-peer (P2P) and client-server (C/S) configurations to alleviate flash crowds effect. FCAN constructs P2P overlay on cache proxy server layer to distribute the flash traffic from origin server. It uses policy-configured DNS redirection to route the client requests in balance, and adopts strategy load detection to monitor and react the load changes. Our preliminary simulation results showed that the system is overall well behaved, which validates the correctness of our design.