One of the important problems in overlay multicast is how to deal with node failures and ungraceful leavings. When a non-leaf end host fails or leaves the multicast session, all downstream nodes will be affected. In this paper, we adopt the proactive approach, which pre-calculates a candidate node (called parent-to-be) for each node to connect to in case its current parent dies. The goal is to recover the overlay multicast tree quickly so that the disruption of service to those affected nodes is minimized. We combine the local parent-to-be locating and global parent-to-be locating schemes together, in order to take advantage of less interference in the local scheme and the flexibility of the global scheme. The quality of the recovered tree is improved while the responsiveness of the proactive approach is maintained.
Kei IWASAKI Fujiichi YOSHIMOTO Yoshinori DOBASHI Tomoyuki NISHITA
Caustics are patterns of light focused by reflective or refractive objects. Because of their visually fascinating patterns, several methods have been developed to render caustics. We propose a method for the quick rendering of caustics formed by refracted and converged light through transparent objects. First, in the preprocess, we calculate sampling rays incident on each vertex of the object, and trace the rays until they leave the object taking refraction into account. The position and direction of each ray that finally transmits the transparent object are obtained and stored in a lookup table. Next, in the rendering process, when the object is illuminated, the positions and directions of the rays leaving the object are calculated using the lookup table. This makes it possible to render refractive caustics due to transparent objects at interactive frame rates, allowing us to change the light position and direction, and translate and rotate the object.
Sebastian FERBER Carsten SCHMIDT-LANGHORST Reinhold LUDWIG Christof BOERNER Colja SCHUBERT Vincent MAREMBERT Marcel KROH Hans-Georg WEBER
We describe a transmission system having a data rate of 160 Gbit/s based on the RZ-DPSK modulation format. The 160 Gbit/s single-polarization signal is generated by optical time division multiplexing technology using the base rate of 40 Gbit/s. The setup is explained and results are given with a special focus on the stability issue of the transmission system. The pulse source, the optical gate for demultiplexing, the clock recovery and the balanced photo-detector are based on semiconductor components. We present long-term bit error measurements (10 hours) over two different long-haul fiber links. The first link comprises 3106 km standard single mode fiber and uses a PMD mitigation scheme. The other link consists of 4 dispersion managed 80 km fiber spans without the need for an additional PMD compensation. Using EDFA amplification solely and also no FEC, error-free operation was achieved over several hours, only limited by slow drift effects in the laboratory system.
Shinya MIYAZAKI Mamoru ENDO Masashi YAMADA Junichi HASEGAWA Takami YASUDA Shigeki YOKOI
This paper presents a deformable fast computation elastic model for real-time processing applications. 'Gradational element resolution model' is introduced with fewer elements for fast computation, in which small elements are laid around the object surface and large elements are laid in the center of the object. Elastic element layout is changed dynamically according to the deformation of cutting or tearing objects. The element reconstruction procedure is applied little by little for each step of the recursive motion generation process to avoid an increase in motion computation time.
Masaru KAMADA Kaoru KUROSAWA Yasuhiro OHTAKI Shusuke OKAMOTO
A compromising technique is proposed for deterring clients from cheating by robot players in skill-based real-time network games. This technique is to inject a fair random noise into the manual input for a real-time game modeled as a chaotic dynamical system. The fair random noise is determined by means of the bit commitment protocol so that neither host nor client can control the noise in their favor. A scenario possibly plotted by a robot player for its victory may be spoiled by slight noise injection because of the sensitivity of chaotic systems to the input. The noise injection brings a luck-based factor into a skill-based game. In this sense, the technique proposed in this paper is not a solution but a compromise for the inherent problem of robot players with the skill-based network games. An example implementation of pinball is presented.
By using multiple transmit antennas, wireless systems have a large capacity in time-varying multipath fading channels. Space-time block code (STBC), space-frequency block code (SFBC), and space-time-frequency (STF) block code are well-known techniques in transmitter diversity schemes. While the SFBC (or the STF block coded) system gives full diversity at frequency-nonselective channels, it breaks down when used in a frequency-selective environment. This is because the SFBC (or the STF block code) scheme disregards frequency selectivity of the channel by assuming that channel frequency responses (CFRs) at adjacent subcarriers are the same. In this paper, we propose efficient channel estimation and symbol decoding methods, which consider the difference between CFRs at the adjacent subcarriers of the SFBC (or the STF block coded) orthogonal frequency division multiplexing (OFDM) system in multipath fading channels. The proposed method gives initial channel information by designing a simple training symbol, and the CFRs at all the subcarriers and the differences between the CFRs are easily calculated by using an interpolation method or a discrete Fourier transform (DFT) operation.
Masahiro YOSHIDA Yuka OBU Tatsuhiro YONEKURA
Performing a musical session via networks requires real-time interaction. There exists, however, the problem of delay between the network nodes, which causes musical sessions become an impediment. To overcome this problem, we have proposed a new protocol for musical session called Mutual Anticipated Session (M.A.S.), which is a type of ensemble that controls appropriate timing of sounds. In the M.A.S, one player's performance precedes the other players', thus this performance is called a "precedent musical performance," and we call a time lapse between the players' performance as "precedent time." In the current M.A.S, it is assumed that the tempo during the performance is constant. In such a case, however, players' requirements to perform more expressively or more emotionally by varying the tempo are sacrificed. Thus, in this paper, enhancement of function that accommodates changes of the tempo by predicting tendency of it is realized. Finally we evaluate the enhancement both by system performance test and by task performance of subject experiments.
Tae Joong EOM Myoung Jin KIM Byeong Ha LEE In Chol PARK
We have implemented a distributed sensor system based on an array of fiber Bragg gratings (FBGs), which can measure up to 1000 points with a single piece of fiber. The system consists of FBGs having the same resonant wavelengths and small reflectivities (0.1 dB), and a wavelength tunable optical time-domain reflectometer (OTDR). To interrogate the distributed grating sensors and to address the event locations simultaneously, we have utilized the tunable OTDR. A thermoelectric temperature controller was used to tune the emission wavelength of the OTDR. The operating temperature of the laser diode was changed. By tuning the pulse wavelength of the OTDR, we could identify the FBGs whose resonant wavelengths were under change within the operating wavelength range of the DFB LD. A novel sensor cable with dry core structure and tensile cable was fabricated to realize significant construction savings at an industrial field and in-door and out-door applications. For experiments, a sensor cable having 52 gratings with 10 m separations was fabricated. To prevent confusion with unexpected signals from the front-panel connector zone of the OTDR, a 1 km buffer cable was installed in front of the OTDR. The proposed system could distinguish and locate the gratings that were under temperature variation from 20 to 70.
The supertask approach was proposed by Moir and Ramamthy as a means of supporting non-migratory tasks in Pfair-scheduled systems. In this approach, tasks bound to the same processor are combined into a single server task, called a supertask, which is scheduled as an ordinary Pfair task. When a supertask is scheduled, one of its component tasks is selected for execution. In previous work, Holman et al. showed that component-task deadlines can be guaranteed by inflating each supertask's utilization. In addition, their experimental results showed that the required inflation factors should be small in practice. Consequently, the average inflation produced by their rules is much greater than that actually required by the supertasks. In this paper, we first propose a notion of Transient Behavior Prediction for supertasks, which predicts the latest possible finish time of subtasks that belong to supertasks. On the basis of the notion, we present an efficient schedulability algorithm for Pfair supertasks in which the deadlines of all component tasks can be guaranteed. In addition, we propose a task merging process which combines the unschedulable supertasks with some Pfair tasks; hence, a newly supertask can be scheduled in the system. Finally, we propose the new reweighting functions that can be used when the previous two methods fail. Our reweighting functions produce smaller inflation factor than the previous work does. To demonstrate the efficacy of the supertasking approach, we present the experimental evaluations of our algorithm, which decreases substantially a number of reweights and the size of inflation when there are many supertasks in the Pfair-scheduled systems.
Just-in-time scheduling problem is the problem of finding an optimal schedule such that each job finishes exactly at its due date. We study the problem under a realistic assumption called periodic time slots. In this paper, we prove that this problem cannot be approximated, assuming P≠NP. Next, we present a heuristic algorithm, assuming that the number of machines is one. The key idea is a reduction of the problem to a network flow problem. The heuristic algorithm is fast because its main part consists of computation of the minimum cost flow that dominates the total time. Our algorithm is O(n3) in the worst case, where n is the number of jobs. Next, we show some simulation results. Finally, we show cases in which our algorithm returns an optimal schedule and is a factor 1.5 approximation algorithm, respectively, and also give an approximation ratio depending on the upper bound of set-up times.
Takanori FUKUOKA Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE
The 2-vertex-connectivity augmentation problem of a graph with degree constraints, 2VCA-DC, is defined as follows: "Given an undirected graph G = (V,E) and an upper bound a(v;G) Z+{} on vertex-degree increase for each v V, find a smallest set E′ of edges such that (V,E E′) has at least two internally-disjoint paths between any pair of vertices in V and such that vertex-degree increase of each v V by the addition of E′ to G is at most a(v;G), where Z+ is the set of nonnegative integers." In this paper we show that checking the existence of a feasible solution and finding an optimum solution to 2VCA-DC can be done in O(|V|+|E|) time.
This paper addresses the estimation of time delay between two spatially separated noisy signals by system identification modeling with the input and output corrupted by additive white Gaussian noise. The proposed method is based on a modified adaptive Butler-Cantoni equalizer that decouples noise variance estimation from channel estimation. The bias in time delay estimates that is induced by input noise is reduced by an IIR whitening filter whose coefficients are found by the Burg algorithm. For step time-variant delays, a dual mode operation scheme is adopted in which we define a normal operating (tracking) mode and an interrupt operating (optimization) mode. In the tracking mode, only a few coefficients of the impulse response vector are monitored through L1-normed finite forward differences tracking, while in the optimization mode, the time delay optimized. Simulation results confirm the superiority of the proposed approach at low signal-to-noise ratios.
We analyze the performance of an adaptive hybrid search code acquisition algorithm for direct-sequence code division multiple access (DS-CDMA) systems under slowly-moving mobile environments. The code acquisition algorithm is designed to provide the desired feature of constant false alarm rate (CFAR) to cope with nonstationarity of interference in CDMA forward links. An analytical expression for the mean acquisition time is first derived and the probabilities of detection, miss, and false alarm are then obtained for frequency-selective Rayleigh fading environments. The fading envelope of a received signal is assumed to be constant over the duration of post-detection integration (PDI), which is most reasonable, especially for slowly-moving mobile environments. The performance of the designed code acquisition algorithm shall be evaluated numerically to examine the effect of some design parameters, such as the sub-window size, the size of the PDI, the decision thresholds in search and verification modes, and so on, considering IMT-2000 environments.
Yeh, Shen, and Hwang recently proposed a secure one-time password authentication scheme using smart cards. They modified the famous S/KEY scheme to achieve security against preplay attacks and off-line dictionary attacks. However, this article shows that their scheme is vulnerable to preplay attacks.
BGP might experience a lengthy path exploration process to reach the convergence after the routing changes. found that the BGP rate-limiting timer--MinRouteAdvertisementInterval (MRAI) has an optimal value Mo that achieves the best trade-off between the stability and the convergence speed. In this paper, with the aid of a timed BGP model, we investigate the effects of MRAI and its optimal value Mo for the BGP convergence process. We find that an adequately long MRAI timer can batch-remove candidate paths and ensure the routing stability in the convergence process. There exists a minimal MRAI Ms that achieves the effect, which is also the upper bound of Mo and provides an approximation of Mo. We calculate the approximations of Ms for different settings and estimate the optimal MRAI for the Internet. According to the results, the optimal MRAI for the Internet might be 5-10 times less than the current default value used in the Internet. The simulations taken with SSFNet and the experiments conducted over the Planet-Lab demonstrate the correctness of our analysis.
Shou-Kuo SHAO Malla REDDY PERATI Meng-Guang TSAI Hen-Wai TSAO Jingshown WU
Most of the proposed self-similar traffic models are asymptotic in nature. Hence, they are less effective in queueing-based performance evaluation when the buffer sizes are small. In this paper, we propose a short range dependent (SRD) process modelling by a generalized variance-based Markovian fitting to provide effective queueing-based performance measures when buffer sizes are small. The proposed method is to match the variance of the exact second-order self-similar processes. The fitting procedure determines the related parameters in an exact and straightforward way. The resultant traffic model essentially consists of a superposition of several two-state Markov-modulated Poisson processes (MMPPs) with distinct modulating parameters. We present how well the resultant MMPP could emulate the variance of original self-similar traffic in the range of the specified time scale, and could provide more accurate bounds for the queueing-based performance measures, namely tail probability, mean waiting time and loss probability. Numerical results show that both the second-order statistics and queueing-based performance measures when buffer capacity is small are more accurate than that of the variance-based fitting where the modulating parameters of each superposed two-state MMPP are equal. We then investigate the relationship between time scale and the number of superposed two-state MMPPs. We found that when the performance measures pertaining to larger time scales are not better than that of smaller ones, we need to increase the number of superposed two-state MMPPs to maintain the accurate and reliable queueing-based performance measures. We then conclude from the extensive numerical examples that an exact second-order self-similar traffic can be well represented by the proposed model.
Seung Hoon NAM Jaehak CHUNG Chan-Soo HWANG Young-Ho JUNG
We extend the differential space time block code (STBC) using nonconstant modulus constellations of two transmit antennas to four transmit antennas case. The proposed method obtains larger minimum Euclidean distances than those of conventional differential STBC with PSK constellations. We derive the symbol error rate (SER) performance of the proposed method and demonstrate the SER performance using computer simulations for both static and fast fading channels. For transmission rates greater than 2 bits/channel use and 3 bits/channel use, the proposed method outperforms the conventional differential STBC.
Zhicheng SUI Qingji ZENG Shilin XIAO
Based on traffic prediction, a new reservation method is proposed to reduce delay and void filling ratio at edge node of optical burst switching networks. Simulation studies show that our method achieves an important improvement and has a dynamic optimum weight value in a certain offset time.
Nenad VESELINOVIC Tadashi MATSUMOTO Christian SCHNEIDER
Spatial correlation among antenna elements both at transmitter and receiver sides in MIMO communications is known to have a crucial impact on system performances. Another factor that can severely degrade receiver performances is the timing offset relative to the channel delay profile. In this paper we derive a novel receiver for turbo MIMO equalization in space-time-trellis-coded (STTrC) system to jointly address the problems described above. The equalizer is based on low complexity MMSE filtering. A joint detection technique of the several transmit antennas is used to reduce the receiver's sensitivity to the spatial correlation at the transmitter and receiver sides. Furthermore, only the significant portion of the channel impulse response (CIR) is taken into account while detecting signals. The remaining portion of CIR is regarded as the unknown interference which is effectively suppressed by estimating its covariance matrix. By doing this the receiver's complexity can be reduced since only a portion of the CIR has to be estimated and used for signal detection. Furthermore, by suppressing the interference from the other paths outside the equalizers coverage the receiver's sensitivity to the timing offset can be reduced. The proposed receiver's performance is evaluated using field measurement data obtained through multidimensional channel sounding. It is verified through computer simulations that the performance sensitivity of the joint detection-based receiver to the spatial correlation is significantly lower than with the receiver that detects only one antenna at a time. Furthermore, the performance sensitivity to the timing offset of the proposed receiver is shown to be significantly lower than that of the receiver that ignores the existence of the remaining multipath CIR components.
Minkyu PARK Sangchul HAN Heeheon KIM Seongje CHO Yookun CHO
Multiprocessor architecture becomes common on real-time systems as the workload of real-time systems increases. Recently new deadline-based (EDF-based) multiprocessor scheduling algorithms are devised, and comparative studies on the performance of these algorithms are necessary. In this paper, we compare EDZL, a hybrid of EDF and LLF, with other deadline-based scheduling algorithms such as EDF, EDF-US[m/(2m-1)], and fpEDF. We show EDZL schedules all task sets schedulable by EDF. The experimental results show that the number of preemptions of EDZL is comparable to that of EDF and the schedulable utilization bound of EDZL is higher than those of other algorithms we consider.