Search

A rate-based switch fabric called smoothed buffer crossbar has been proposed in our recent work. It can provide 100% rate-guaranteed service with only a two-cell buffer at each crosspoint, and can also support best-effort service with an additional bandwidth regulator. However, the widely used max- flow model for bandwidth regulation is neither scalable nor of 100% throughput. In order to evaluate the performance of bandwidth regulator, we first introduce the 100% ideal throughput measurement in this paper. Then we prove that the total arrival average (TAA) algorithm has got this property, which does not happen in the max-flow allocation. Then an O(N) algorithm called proportion scaling allocation (PSA) is presented. Simulations reveal that PSA can deliver nearly 100% throughput even in a frequently changing traffic pattern. As a comparison, both theoretical and experimental evidences are given to show the inefficiency of the max-flow model.

We demonstrate a new algorithm named FlexStem to predict RNA secondary structures with pseudoknots. Our approach is based on the free energy minimization criterion, and utilizes a sophisticated energy model that is more accurate and supports more types of pseudoknots. By using a "maximal stem" and "stem merging" strategy, the search space for RNA structure prediction is significantly reduced. We have also developed a greedy search algorithm with perturbation on stems. The FlexStem algorithm is applied to a large number of sequences taken from Sprinzl, Pseudobase and other reliable resource. We find that FlexStem outperforms the well-known optimal and heuristic algorithms such as Mfold, PKNOTS, HotKnots and ILM in overall sensitivity and has comparable results to those algorithms in overall specificity. Performance evaluation demonstrate that FlexStem requires significantly less time than the optimal algorithm PKNOTS. In addition, our algorithm has better prediction results on pseudoknot-free sequences compared to competing algorithms.

Simulation is crucial to performance evaluation of switches. Currently stochastic simulation is the predominant approach, which has two drawbacks: few workload patterns and long simulation times. In this paper, we propose a novel switch simulation method that is based on two techniques: exhaustive workload pattern generation and smoothed periodic input generation. The exhaustive workload pattern generation can produce a huge number of nonuniform workload patterns, which far exceeds the traditional few ones; conclusions based on such truly extensive simulations are much more convincing. The periodic input or cell arrival pattern outperforms the stochastic counterpart in terms of easy repetition and fast convergence of simulation; in particular, among periodic inputs, the smoothed periodic input is most favorable to switch scheduling, and hence switches performing poor with it probably performs worse under others. Combining these two techniques together can systematically identify lots of stuck states at which some switches show poor performances such as low throughput. Specifically, this method discovers that the throughput of iSLIP, FIRM and DRRM, each with one iteration, may be lower than 60% under certain nonuniform and smoothed periodic traffic pattern.

Input queued switches have been well studied in the recent past. A scheduling algorithm is required to schedule the transfer of packets through the switch fabric (e.g. crossbar) at every time slot. The maximum weight matching (MWM) algorithm is known to deliver 100% throughput under any admissible traffic. However, MWM is not practical for its high computational complexity O(N/sup 3/). In this paper, we study a class of approximation algorithms to MWM from the point of view of local search. Notably we observe that: (a) Local search is well suitable for parallel computation. (b) Each line card of high performance router has at least one processor. Based on the two important observations, a parallelized greedy scheduling algorithm is proposed. The proposed algorithm is proved to be rate stable under any admissible traffic. Simulation results show that our algorithm outperforms other randomized approximations to MWM.

Input queued switching architectures has become attractive for implementing high performance switches. Some maximal matching algorithms, e.g. PIM, iSLIP, are easily implemented in hardware, hence attract more attention in designing of the practical router. However, they usually need multiple iterations to achieve satisfying performance. In this paper, we propose a multiple-threshold based round robin matching algorithm (MTRRM) for high performance input queued crossbar switch scheduling. In MTRRM, when an input and an output are matched, the matching might be kept for more than one time slot. Simulation results show that our scheme can strongly reduce the average cell delay and increase the throughput under non-uniform traffic. MTRRM achieves quite good performance with single iteration and this promises us that it is more suitable for switch with high line rate or large number of ports.

We consider the problem of scheduling multicast traffic in a buffered crossbar switch with multiple input queues at each input port. In this paper, we design and investigate a series of combinations of queuing policies and scheduling algorithms and report the simulation result. It is shown that a small number of input queues at each input port can dramatically improve the performance under burst multicast traffic in buffered crossbar switches. Under this architecture, it is feasible to design simple queuing policies and scheduling algorithms for high speed switches while keeping high performance and small size of buffer within crossbar.

Input-queued (IQ) switch architectures have become predominant in high-speed switching for the past decade. Maximum weight matching (MWM) algorithms are known to achieve 100% throughput under any admissible traffic. Unfortunately, MWM is impractical for its high computational complexity O(N/sup 3/). In this paper, we study a new type of approximate algorithm to MWM using local search technique. Instead of using randomized technique which is mainly used by the existing approximations, our algorithm runs in a deterministic way which is easy to be implemented by hardware. It provides 100% throughput under any admissible traffic and simulation results show that the proposed algorithm with only 3 iterations outperforms the existing approximations to MWM.

The appeal of a combined input-crosspoint-queued (CICQ) switch is its distributed scheduling property, which is more scalable than an unbuffered crossbar switch. Round-robin algorithms are interesting because of simple hardware implementation. Although the existing round-robin algorithms achieve 100% throughput asymptotically under uniform traffic, these algorithms have poor performance under nonuniform traffic. In order to improve the performance of a CICQ switch (one cell per crosspoint buffer) under nonuniform traffic, this paper proposes a traffic adaptive round-robin algorithm named TARR. Unlike the existing round-robin algorithms, TARR has distinctive round-robin pointer updating rules which are powerful to cope with nonuniform traffic patterns. On the other hand, TARR is a quantum based algorithm, and the quantum assignment discipline is load adaptive. Extensive simulations show that TARR has a satisfactory performance under both uniform and nonuniform traffic patterns.

Scalable streams provide a layered representation for transmitting media contents over a channel with packet losses and variable delay. In general, real-time streaming scalable media to audience has timing constraints, and different layers in a frame have different importance to the playback quality reconstructed in client. In this paper, we proposes an efficient and simple real-time scheduling algorithm, Layer-Based Earliest Deadline First (LB-EDF) algorithm, which decides how to transmit/re-transmit video packets at any given time for delivery of scalable streaming media over a lossy channel. Besides real-time constraint, unequal priorities of scalable source bitstream in different layers are taken into account in the proposed algorithm. This guarantees the better usage of available bandwidth and the smoother playback. Simulated results show that, with the proposed approach, the playback quality has a greatly improvement.

Some wireless communication systems, such as mobile ad hoc network, operate on a limited battery supply, and energy efficiency is therefore crucial to the network survival time. This paper proposes a multiscale load adaptive scheduling (MLAS) scheme to determine the transmission time of the packets. In MLAS, traffic is predicted over the scale of time window, and then a transmission time stretching algorithm is proposed to adjust the packet transmission time packet by packet. Compared with the fixed transmission time scheme, MLAS can reduce the energy consumption of data transmission by up to 90% corresponding to the load factor and the burst characteristic. MLAS also outperforms the look ahead based scheme in the performance of energy efficiency with the same average delay.

Digital video cassette recording (VCR) functionality enables quick and user friendly browsing of multimedia content, thus is highly desirable in streaming video application. In this paper, we propose a layer-based implementation scheme and a layer-based soft real-time scheduling algorithm for efficient implementation of scalable streaming video system to provide full VCR functionality over a dynamic wireless network. Scalable streams provide a layer-based representation for transmitting media contents. Besides the real-time constraint, unequal priorities of scalable streams at different layers and frames are taken into account to support VCR functionality in the proposed algorithms. Thus, the better usage of available bandwidth and smoother playback can be achieved in the streaming system. Simulated results show that, with the proposed algorithms, the playback quality can be efficiently improved.

Scalable media streaming provides a layered representation for transmitting media contents over the Internet with packet loss and variable delay. It is an important problem about how to select and schedule packet delivery of a scalable streaming media server. In this paper, we propose a real-time scheduling algorithm based on imprecise computation model for real-time scalable media streams. The scheduling task of a scalable media stream is partitioned into two sub tasks: the mandatory subtask and the optional subtask. The mandatory subtask is for the substream of base layer and the optional subtask is for the substreams of enhancement layers. The imprecise computer model and scheduling algorithm provide scheduling flexibility by trading off video quality reconstructed in client to meet playback deadline. Thus, the better usage of available bandwidth and the smoother playback are achieved. Simulated results show that, with the proposed approach, the playback quality has an obvious improvement.