Scheduling in Optical WDM Networks Using Hidden Markov Chain Based Traffic Prediction

This paper presents the design and performance analysis of a predictor-based scheduling algorithm for optical wavelength division multiplexed (WDM) networks. WDM technology provides multiple, simultaneous and independent gigabit-per-second channels on a single fiber. A reservation-based multiple access control (MAC) protocol is considered here for a local area WDM network based on the passive star topology. The MAC protocol schedules reservation requests from the network nodes on the multiple channels. In previous work, we have presented an on-line scheduling algorithm for such a network. We have shown earlier that schedule computation time can significantly affect performance and the scheduling algorithms should be simple for better performance. In this work, we further improve system performance by using a hidden Markov chain based prediction algorithm. The objective here is to reduce the amount of time spent in computing the schedule by predicting traffic requests. Performance analysis based on discrete-event simulation, varying parameters such as number of nodes and channels is presented. The results show that the error of prediction is reasonable for most cases: more than 70% of the time, the error between actual request and predicted request is less than 20%. Network throughput is higher with the proposed prediction algorithm due to pipelining of schedule computation.     

Optimal video stream multiplexing through linear programming

This paper presents a new optimal multiplexing scheme for compressed video streams based on their individual e-PCRTT transmission schedules. A linear programming algorithm is proffered, which takes into account the different constraints of each client. The algorithm simultaneously finds the optimum total multiplexed and individual stream schedules that minimize the peak transmission rate. Since the problem is formulated as a linear program it is bounded in polynomial time. It is shown that the algorithm succeeds in obtaining maximum bandwidth utilization with Quality of Service (QoS) guarantees. Simulation results using 10 real MPEG-1 video sequences are presented. The optimal multiplexing linear programming results are compared to the e-PCRTT and Join-the-Shortest-Queue (JSQ) procedures in terms of peak transmission bandwidth, P-loss performance and standard deviation. For several client buffer sizes, the rate obtained by our LP solution when compared to a previous e-PCRTT and JSQ methods resulted in reductions of 47% and 56%, respectively. This implies for a fixed rate problem that the proposed scheme can allow an increase in the number of simultaneously served video streams.     

Traffic statistics and performance evaluation in optical burst switched networks

Optical burst switching (OBS) is a promising switching technology to exploit the potential benefits of optical communication and, at the same time, support statistical multiplexing of data traffic at a fine granularity. To quantify its benefits, the paper describes several typical burst assembly algorithms and studies their impact on the assembled burst traffic characteristics as well as the performance of TCP traffic. Also described is a proactive burst scheduling algorithm, called burst overlap reduction algorithm (BORA), which schedules locally assembled bursts in such a way as to reduce burst contention at downstream nodes in OBS networks. Furthermore, to provide analytical insights into performance evaluation of OBS networks, a burst loss model at an OBS node and its extension to different reservation protocols are presented.     

Multihop packet scheduling in WDM/TDM networks with nonnegligibletransceiver tuning times

This paper addresses the design of packet transmission schedules in photonic slotted wavelength-division multiplexing/time-division multiplexing broadcast-and-select networks with W wavelengths and N nodes. Nodes are equipped with one tunable-wavelength transmitter with nonnegligible tuning times and one fixed-wavelength receiver. A new scheduling algorithm that exploits multihop packet transfer to shorten the duration of scheduling periods is first proposed. A single-hop scheduling algorithm that performs slightly better than previous proposals is then described. A simulation-based analysis of the two algorithms shows that they jointly lead to significant improvements in both throughput and delay with respect to previous single-hop schedules     

Burst scheduling algorithms for SS/TDMA systems

Efficient algorithms that generate a detailed operation plan for satellite-switched time-division multiple access (SS/TDMA) systems are proposed. A burst time plan generation problem is analyzed and two algorithms for burst scheduling are presented. The first method is an algorithm based upon a bin pack problem. The other algorithm schedules new bursts while reassigning already scheduled bursts by a single machine scheduling model. These algorithms are shown to be applicable to practical systems operating with transponder hopping and multidestination bursts. Simulation results for a number of example problems are presented     

Distributed scheduling of CDMA networks with minimal information

An algorithm which produces conflict-free communication schedules in mobility multihop radio networks is presented. These schedules are produced in a completely distributed manner. The algorithm is based on a globally known permutation on the nodes of the network. As a result the only knowledge needed on the part of individual nodes is the number of nodes in the network. This permutation guarantees that conflict-free schedules can be produced in a distributed manner. Two extensions to the basic permutation are discussed. The first enables neighboring nodes to enhance their communication schedules in a fast, robust, distributed manner. The second extension allows the algorithm to operate in the presence of secondary conflicts     

Segment-based approach for real-time reactive rescheduling forautomatic manufacturing control

We propose a new segment-based approach for a real-time reactive rescheduling method. The approach is applicable to actual large-scale manufacturing systems, such as fully automated semiconductor wafer fabrication lines. The proposed method can efficiently (in terms of computation time) schedule processing operations at equipment units by dividing a wide scheduling range into small segments and by using a greedy scheduling algorithm. It can also reactivate infeasible schedules without sacrificing the quality of schedules in terms of productivity as much as possible. From the simulation results obtained, we experimentally confirmed that the proposed method reactivates, without significant productivity loss caused by the rescheduling algorithm itself, infeasible schedules faster than a comparative method commonly in use today. Consequently, the proposed method manages to keep schedules at each equipment unit executable in terms of processing performance and schedule quality     

Closest coset decoding of |u|u+v| codes

The general concept of closest coset decoding (CCD) is presented, and a soft-decoding technique for block codes that is based on partitioning a code into a subcode and its cosets is described. The computational complexity of the CCD algorithm is significantly less than that required if a maximum-likelihood detector (MLD) is used. A set-partitioning procedure and details of the CCD algorithm for soft decoding of |u|u+v| codes are presented. Upper bounds on the bit-error-rate (BER) performance of the proposed algorithm are combined, and numerical results and computer simulation tests for the BER performance of second-order Reed-Muller codes of length 16 and 32 are presented. The algorithm is a suboptimum decoding scheme and, in the range of signal-to-noise-power-density ratios of interest, its BER performance is only a few tenths of a dB inferior to the performance of the MLD for the codes examined     

On the optimality of linear schedules

An algorithm can be modeled as a set of indexed computations, and a schedule is a mapping of the algorithm index space into time.Linear schedules are a special class of schedules that are described by a linear mapping and are commonly used in many systolic algorithms.Free schedules cause computations of an algorithm to execute as soon as their operands are available. If one computation uses data generated by another computation, then a data dependence exists between these two computations which can be represented by the difference of their indices (calleddependence vector). Many important algorithms are characterized by the fact that data dependencies areuniform, i.e., the values of the dependence vectors are independent of the indices of computations. There are applications where it is of interest to find an optimal linear schedule with respect to the time of execution ofa specific computation of the given algorithm. This paper addresses the problem of identifying optimal linear schedules for uniform dependence algorithms so that the execution time ofa specific computation of the algorithm is minimized and proposes a procedure to solve this problem based on the mathematical solution of a linear optimization problem. Also, linear schedules are compared with free schedules. The comparison indicates that optimal linear schedules can be as efficient as free schedules, the best schedules possible, and identifies a class of algorithms for which this is always true. This research was supported in part by the National Science Foundation under Grant DCI-8419745 and in part by the Innovative Science and Technology Office of the Strategic Defense Initiative Organization and was administered through the Office of Naval Research under contracts No. 00014-85-k-0588 and No. 00014-88-k-0723.     

MOTION COMPENSATION BASED ON MOTION VECTOR INTERPOLATION

A modified block matching algorithm (BMA) with motion correlation constraint (MCCBMA) is proposed at first. Then a novel motion compensation algorithm (INTPMC) which computes motion vector for each pixel by interpolating motion vectors is presented. In order to increase interframe prediction performance and decrease the computational complexity, an optimizing algorithm for partial motion vectors is described at last. Experimental results show that the proposed algorithm can improve the prediction performance obviously with a moderately increased complexity compared with the conventional full search block matching algorithm (FSBMA).     

基于运动矢量插值的运动补偿算法

本文首先研究了相关性约束运动估值算法,然后提出了基于运动矢量插值的运动估值算法,实验表明新算法的预测性能明显比传统块匹配运动估值算法(BMA)好,而且预测图象的主观质量得到显著改善。     

OBS网络中的最小间隙组调度算法

根据OBS网络的结构和特点,分析了OBS网络核心节点的数据信道调度算法,提出了一种新的数据信道调度算法--最小间隙组调度(SGGS)算法,并详细讨论了该算法的具体实现.该算法将到达核心节点的控制包分组,然后将这一组控制包按数据包到达先后的次序调度数据信道,从而达到合理调度和使用数据信道,最终实现改善整个OBS网络性能的目的.     

Fast GF(p) modular inversion algorithm suitable for VLSIimplementation

A new, efficient algorithm for modular inversion in Galois field GF(p) is presented. Very large scale integration (VLSI) implementation of the algorithm is described and the high performance and low silicon penalty is demonstrated     

Reduced complexity decision feedback equalization for digitalsubscriber loops

Decision feedback equalizers (DFEs) are widely used in modern local network digital transmission systems to remove the intersymbol interference caused by slowly decaying pulse tails. A gradient descent algorithm for adapting a coefficient to model the slowly decaying portion of the tail is described. An equalization strategy is described that exploits prior knowledge of the nature of the subscriber loop channel, together with the new adaptation algorithm, to give reduced complexity DFE structures. The use of this algorithm in FIR and IIR equalizer structures is described. The use of this algorithm in FIR and IIR equalizers is quantitatively compared to a conventional DFE in terms of performance and implementation complexity. An analysis is presented describing the operation of the adaptation algorithm in the presence of noise. Simulation results illustrate the training of the algorithm and its stability in the presence of near-end crosstalk noise     

LDPC码的自适应补偿最小和译码算法

LDPC码置信传播算法由于复杂度过高而无法实际应用,最小和算法虽然能降低复杂度但却带来了较大的性能损失。补偿最小和算法通过在最小和算法中引入固定修正因子,在几乎不增加算法复杂度的条件下获得接近置信传播算法的性能。为了进一步提升补偿最小和算法的性能,给出了补偿最小和算法的自适应修正因子的计算方法并结合层译码调度策略,提出层自适应补偿最小和算法。仿真表明,所提算法具有更优的性能和更快的收敛速度。     

Turbo码在深空通信中应用

Turbo码具有逼近Shannon容量限的优异性能,介绍了应用于深空通信的Turbo码编码方案和相应的译码算法,并给出了采用修正Max-Log-Map译码算法的深空CCSDS标准Turbo码的软件仿真性能和硬件系统实测性能。通过计算机仿真和硬件实测结果表明,采用该修正Max-Log-Map译码算法的Turbo码译码器易于硬件实现,同时Turbo码仿真性能和实际性能一致,适用于实际工程应用。     

Obtaining schedules for digital systems

A systematic technique is presented to derive correct schedules for a synchronous digital system, given a signal flow graph for an algorithm. It is also shown how to use this technique to derive designs that are optimal in having the lowest latency, the highest throughput, or the smallest number of registers. The same technique can also be used to verify digital systems that have already been designed     

Minimizing the Number of Multicast Transmissions in Single-Hop WDM Networks

The problem of minimizing the number of transmissions for a multicast transmission under the condition that the packet delay is minimum in single-hop wavelength division multiplexing (WDM) networks is studied in this paper. This problem is proved to be NP-complete. A heuristic multicast scheduling algorithm is proposed for this problem. Extensive simulations are performed to compare the performance of the proposed heuristic algorithm with two other multicast scheduling algorithms, namely, the greedy and no-partition scheduling algorithms. The greedy algorithm schedules as many destination nodes as possible in the earliest data slot. The no-partition algorithm schedules the destination nodes of a multicast packet to receive the packet in the same data slot without partitioning the multicast transmission into multiple unicast or multicast transmissions. Our simulation results show that (i) an algorithm which partitions a multicast transmission into multiple unicast or multicast transmissions may not always produce lower mean packet delay than the no-partition algorithm when the number of data channels in the system is limited and (ii) the proposed heuristic algorithm always produces lower mean packet delay than the greedy and the no-partition algorithms because this algorithm not only partitions a multicast transmission into multiple unicast or multicast transmissions to keep the packet delay low but also reduces the number of transmissions to conserve resources.     

Sequential algorithm for channel equalisation employing a stack

A sequential algorithm based on a stack, and applicable to the problem of recovering digital data after degradation by intersymbol interference and additive noise, is described. Results are presented showing a tradeoff between performance and equipment complexity, with performance asymptotic to the maximum-likelihood-sequence (Viterbi) estimate when the storage is large.     

Graph-based message-passing schedules for decoding LDPC codes

We study a wide range of graph-based message-passing schedules for iterative decoding of low-density parity-check (LDPC) codes. Using the Tanner graph (TG) of the code and for different nodes and edges of the graph, we relate the first iteration in which the corresponding messages deviate from their optimal value (corresponding to a cycle-free graph) to the girths and the lengths of the shortest closed walks in the graph. Using this result, we propose schedules, which are designed based on the distribution of girths and closed walks in the TG of the code, and categorize them as node based versus edge based, unidirectional versus bidirectional, and deterministic versus probabilistic. These schedules, in some cases, outperform the previously known schedules, and in other cases, provide less complex alternatives with more or less the same performance. The performance/complexity tradeoff and the best choice of schedule appear to depend not only on the girth and closed-walk distributions of the TG, but also on the iterative decoding algorithm and channel characteristics. We examine the application of schedules to belief propagation (sum-product) over additive white Gaussian noise (AWGN) and Rayleigh fading channels, min-sum (max-sum) over an AWGN channel, and Gallager's algorithm A over a binary symmetric channel.