Scheduling algorithm for MPEG-2 TS multiplexers in CATV networks

We study the scheduling algorithm for multiplexers in CATV networks. First we propose the scheduling matrix concept, and then two kinds of scheduling algorithms are given, which are described with the scheduling matrix. Especially, we focus on the VBR scheduling algorithm being able to achieve a better display of the MPEG-2 program in CATV networks. The scheduler applying our VBR scheduling algorithm maintains, for each input stream, a counter to determine how many TS packets should be transmitted in the current scheduling cycle (one frame period) in order to prevent deadline violation. The real-time bit rate of each input stream is used to update the parameters of the scheduling matrix. Our VBR scheduling algorithm is compared numerically with the traditional CBR scheduling algorithm. The results of the simulation show that our VBR scheduling algorithm can achieve significantly lower delay, i.e., deadline violation probability, in comparison with the CBR scheduling algorithm. Also it is shown that a higher utilization of bandwidth can be achieved by means of our VBR scheduling algorithm than by the CBR scheduling algorithm     

Efficient multi-hop scheduling algorithms for packet transmissions in WDM optical star networks

This paper proposes multi-hop scheduling algorithms for the All-to-All Broadcast (AAB) problem in Wavelength Division Multiplexed (WDM) optical star networks. The multi-hop AAB problem can be split into two subproblems: Logical Topologies Construction (LTC) problem, and Transmission Scheduling (TS) problem. For improving the efficiency of multi-hop scheduling, we focus on a new multi-hop transmission model and transfer the LTC problem to a special case of the Round Robin Tournament (RRT) problem. In the proposed logical topologies, our multi-hop scheduling algorithms can easily overlap the tuning latency and reduce the number of tuning operations on each node. We compare our results with previous research in terms of schedule length. Overall results indicate that our multi-hop scheduling algorithms have better performance than previous algorithms.     

基于CATV网MPEG-2 TS复用器包调度算法

研究用于CATV网MPEG-2 TS复用器的包调度算法。提出了调度矩阵的概念，分别描述了传统的恒定速率（CBR）调度算法和本文所提出的可变速率（VBR）调度算法。VBR调度算法采用基于输入流统计特性的实时带宽分配策略，可获得较好的延时性能和较高的信道利用率。     

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.     

An efficient transmission scheduling algorithm for awavelength-reusable local lightwave network

Although single-hop star networks based on wave-length division multiplexing (WDM) are attractive owing to their all-optical communication features, the throughput of such lightwave networks is limited due to the small number of available wavelengths. In this paper, a wavelength-reusable local lightwave network that consists of two interconnected WDM star networks is proposed. Based on this architecture, the lower bounds for the problems of minimizing the switching duration and the number of switching modes are derived. A transmission scheduling algorithm for this architecture to efficiently reuse the wavelengths is also proposed. The analytical result shows that the proposed scheduling algorithm always produces solutions close to the lower bounds. Simulation results show that given the same number of users and available wavelengths, the solutions (in terms of the average switching duration and the average number of switching matrices) obtained by the proposed scheduling algorithm on the interconnected WDM networks are better than the optimal solution on a single-star WDM network. In most cases, the performance improvement achieves 20 to 45%     

Burst-based scheduling algorithms for non-blocking ATM switcheswith multiple input queues

This letter quantitatively evaluates two alternative approaches to the scheduling of traffic streams in a high-speed ATM switch with multiple input queues. Specifically, we compare a previously proposed algorithm, called parallel iterative matching (PIM)-which is a cell-based scheduling algorithm-with our newly proposed algorithm-which is a burst-based variation of the PIM scheduling algorithm. Extensive simulation results demonstrate that burst-based PIM scheduling outperforms cell-based PIM scheduling under a variety of realistic parameters     

Design of a Packet-Switched WDM Network with Multi-Wavelength Selectivity

The use of low-speed tunable devices in packet-switched WDM star networks may lead to throughput and delay penalties. We propose (i) a new receiver architecture using multi-wavelength selectivity to eliminate the penalties, and (ii) a corresponding optimal scheduling algorithm for uniform all-to-all transmission. This architecture results in significant cost reduction in comparison with existing pipeline technique. When using a two-wavelength simultaneous selection, our numerical results show that (i) the throughput can increase by 40% in comparison with using a tunable filter alone; (ii) the throughput degradation is 2% in comparison with using two tunable filters in systems using a pipeline technique.     

A Multilayer Optical Packet Switching Network Based on the Kautz Graph and Optical Passive Star Couplers

The multihop optical network is the most appropriate solution to satisfy the increasing applications of Internet services. This paper extends the regular Kautz graph to one with multiple layers in order to produce more architectural variations. The connectivity between adjacent layers utilizes the systematic connection patterns of a regular Kautz graph. A routing algorithm based on its property is presented. Optical passive star (OPS) couplers are adopted to implement our new topologies. Three scheduling criteria that can solve the contention problem in the intermediate nodes are evaluated and compared in terms of their capability to improve the accessibility.     

Prolonging lifetime for wireless rechargeable sensor networks through sleeping and charging scheduling

Prolonging network lifetime is a fundamental requirement in wireless sensor network (WSN). Existing charging scheduling algorithms suffer from high node redundancy and energy consumption issues. In this paper, we study WSN charging problem from the perspectives of energy conservation combined with energy replenishment scheduling. Firstly, we detect the redundant nodes whose energy is wasted in the network functionality and develop a K‐covering redundant nodes sleeping scheduling algorithm (KRSS) for reducing energy. Secondly, we employed multiple wireless charging vehicles (WCVs) for energy replenishment and optimize the charging scheduling algorithm to prevent any exhaustion of nodes, and we proposed a distance and energy–oriented charging scheduling algorithm (DECS) with multiple WCVs. Simulation experiments are conducted to show the advantages of the proposed KRSS+DECS, confirming that our scheme is capable of removing redundant nodes, lowering node failures, and prolonging network lifetime.     

Packet rescheduling in WDM star networks with real-time servicedifferentiation

In this paper, we propose a novel scheduling scheme, namely priority-differentiated scheduling (PDS), which is designed to handle real-time (high-priority) packets in wavelength division multiplexing (WDM) star networks. PDS allows high-priority packets to preempt the prescheduled low-priority (nonreal time) packets. By scheduling the high-priority packets first, and then having the preempted packets rescheduled, PDS guarantees that the high-priority packets can always achieve the earlier transmission than the others in order to meet the quality of service (QoS) requirements. In addition, it does not sacrifice the performance of nonreal-time packets. As a matter of fact, low-priority packets can also benefit from PDS algorithms. This scheme has the capability of handling channel collision and destination conflict, and it supports variable-length packets. This paper also provides an insight into the data channel selection technique along with PDS. With the proposed algorithm that selects a data channel with minimum scheduling latency (MSL), the channel throughput is improved. The performance of the PDS scheme has been extensively studied by means of numerical simulations     

Clustering‐based scheduling: A new class of scheduling algorithms for single‐hop lightwave networks

In wavelength division multiplexing (WDM) star networks, the construction of the transmission schedule is a key issue, which essentially affects the network performance. Up to now, classic scheduling techniques consider the nodes' requests in a sequential service order. However, these approaches are static and do not take into account the individual traffic pattern of each node. Owing to this major drawback, they suffer from low performance, especially when operating under asymmetric traffic. In this paper, a new class of scheduling algorithms for WDM star networks, which is based on the use of clustering techniques, is introduced. According to the proposed Clustering‐Based Scheduling Algorithm (CBSA), the network's nodes are organized into clusters, based on the number of their requests per channel. Then, their transmission priority is defined beginning from the nodes belonging to clusters with higher demands and ending to the nodes of clusters with fewer requests. The main objective of the proposed scheme is to minimize the length of the schedule by rearranging the nodes' service order. Furthermore, the proposed CBSA scheme adopts a prediction mechanism to minimize the computational complexity of the scheduling algorithm. Extensive simulation results are presented, which clearly indicate that the proposed approach leads to a significantly higher throughput‐delay performance when compared with conventional scheduling algorithms. We believe that the proposed clustering‐based approach can be the base of a new generation of high‐performance scheduling algorithms for WDM star networks. Copyright © 2008 John Wiley & Sons, Ltd.     

Traffic and Interference Adaptive Scheduling for Internet Traffic in UMTS

In this paper we propose a scheduling strategy for the radio resources management when transmitting Internet traffic over third-generation systems. More precisely, we consider the UMTS Terrestrial Radio Access Network (UTRAN) Time Division Duplex (TDD) mode standardized by ETSI. UTRAN TDD uses a hybrid solution of code and time division multiple access, called TD-CDMA. In UMTS systems a key issue in developing access methodologies for the available spectrum is an optimal management of the rare radio resources. In this paper we present a fair and efficient scheduling algorithm that adapts its behavior to traffic and interference conditions. Specifically, our scheduling algorithm is able to manage the radio resources taking into account both the traffic fluctuations in the uplink and downlink direction and the variations of the system interference. The goal of our scheduler is the data-throughput maximization for an efficient utilization of available radio resources. The effectiveness of our scheduling algorithm is shown by exploiting analytical tools.     

CS-POSA: A High Performance Scheduling Algorithm for WDM Star Networks

In this paper a new packet scheduling algorithm for WDM star networks is introduced. The protocol adopted is pre-transmission coordination-based and packet collisions have been eliminated due to predetermination of the timeslots each node transmits in a demand matrix. The requests of the transmitted packets are predicted through Markov chains in order to reduce the calculation time of the final scheduling matrix. This is accomplished by pipelining the schedule computation. The innovation that this algorithm introduces is to modify the service sequence of the node. The proposed algorithm is studied via extensive simulation results and it is proved that changing the sequence that nodes transmit, from the node with the largest number of requests to the node with the fewest requests, that there is an increase in the throughput of the network, with a minimum (almost zero) cost in mean time delay and in delay variance.     

Scheduling algorithm for the multiple rovers' access to single orbiter on the Mars relay communication links

The Mars relay communication services have played an important role on the scientific data transmission for several Mars surface exploration missions. However, such technologies based on CCSDS Proximity‐1 protocols only support one single user's access to orbiter at one relay communication session. In future deep space missions, there would be more rovers and facilities on the Mars surface, which requires a multiple access method with high efficiency and low resource occupation. In this article, we propose a distributed serial scheduling structure as "multiple leaky buckets + token bucket" and a scheduling algorithm as "queue equilibrium based proportional fair," in order to improve the multiple access performance on the comprehensive merits of fair access, data transfer throughput, and queue equilibrium. The mathematical model is constructed to validate our new scheduling structure and algorithm, and the multiple attribute decision‐making (MADM) method is used to compare our algorithm with the other three most frequently used algorithms as maximum rate, time polling, and proportional fair. Simulation results show that our scheduling structure and the new scheduling algorithm could find balance with fairness, throughput and queue equilibrium, which gets the best performance in all the four scheduling algorithms in the Mars relay communications case.     

Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks

We consider the problem of distributed scheduling in wireless networks subject to simple collision constraints. We define the efficiency of a distributed scheduling algorithm to be the largest number (fraction) such that the throughput under the distributed scheduling policy is at least equal to the efficiency multiplied by the maximum throughput achievable under a centralized policy. For a general interference model, we prove a lower bound on the efficiency of a distributed scheduling algorithm by first assuming that all of the traffic only uses one hop of the network. We also prove that the lower bound is tight in the sense that, for any fraction larger than the lower bound, we can find a topology and an arrival rate vector within the fraction of the capacity region such that the network is unstable under a greedy scheduling policy. We then extend our results to a more general multihop traffic scenario and show that similar scheduling efficiency results can be established by introducing prioritization or regulators to the basic greedy scheduling algorithm     

An isochronous and asynchronous traffic scheduling algorithm fordual-star WDM networks

In this paper, based on the concept of wavelength reusing, a new architecture for interconnecting two wavelength division multiplexing (WDM) star networks is proposed. According to this architecture, the problem of scheduling isochronous as well as asynchronous traffic is investigated. The lower bounds for the problem of minimizing the switching duration and the number of switching modes are derived. A transmission scheduling algorithm for the proposed architecture to efficiently reuse the wavelength is also proposed. For only asynchronous traffic, the analytical result shows that the proposed scheduling algorithm produces solutions equal to the lower bounds. For both isochronous and asynchronous traffic, simulation results show that the average switching duration and the average number of switching modes obtained by the proposed algorithm are quite close to the lower bounds. Simulation results also show that given the same number of users and available wavelengths, the solutions (in terms of the average switching duration and the average number of switching modes) obtained by the proposed scheduling algorithm on the dual-star WDM networks are better than the solutions obtained by the two-phase algorithm on the similar dual-star WDM networks     

A novel routing algorithm in distributed IEEE 802.16 mesh networks

In this paper, we propose a novel distributed routing algorithm for IEEE 802.16/WiMax based mesh networks. Our algorithm aims at providing routes for traffic flows with minimum end-to-end delays. Based on the underlying IEEE802.16 standard distributed scheduling mechanism, our routing algorithm is incorporated into the medium access control (MAC) layer. Each node determines the next-hop nodes for the passing flows according to the scheduling information and attempts to forward packets in the very earliest slots. In addition, a loop cancelation mechanism is proposed to avoid being trapped in path loops and thus guarantees the accessibility of our algorithm. The simulation results show that our proposal can considerably reduce the delay of traffic flows and also achieve load balance to a certain degree.     

A timestamp-sensitive scheduling algorithm for MPEG-II multiplexersin CATV networks

To achieve smooth display of MPEG-II programs in the residential cable TV networks, we present a timestamp-sensitive scheduling algorithm for MPEG-II multiplexers. The deadline-driven scheduler maintains, for each program stream, a counter and a timestamp to record and determine how many transport stream (TS) packets should be transmitted before the current scheduling cycle ends. The decoding timestamp (DTS) of TS packets is used to update the counter in order to prevent deadline violation. This algorithm is compared numerically with the timestamp-insensitive algorithm which runs constant-bit-rate (CBR) scheduling. The trace-driven simulation shows that the deadline violation of our timestamp-sensitive scheduling is much lower than CBR's and well controlled for programs with various degrees of burstiness. We also show that the algorithm can be further improved by adding a scheme to prevent buffer underflow and overflow at multiplexers and set-top-boxes, respectively     

Performance analysis of SIMO space-time scheduling with convex utility function: zero-forcing linear processing

In a multiple-antenna system, an optimized design across the link and scheduling layers is crucial toward fully exploiting the temporal and spatial dimensions of the communication channel. In this paper, based on discrete optimization techniques, we derive a novel analytical framework for designing optimal space-time scheduling algorithms with respect to general convex utility functions. We focus on the reverse link (i.e., client to base station) and assume that the mobile terminal has a single transmit antenna while the base station has n/sub R/ receive antennas. In order that our proposed framework is practicable and can be implemented with a reasonable cost in a real environment, we further assume that the physical layer involves only linear-processing complexity in separating signals from different users. As an illustration of the efficacy of our proposed analytical design framework, we apply the framework to two commonly used system utility functions, namely maximal throughput and proportional fair. We then devise an optimal scheduling algorithm based on our design framework. However, in view of the formidable time complexity of the optimal algorithm, we propose two fast practical scheduling techniques, namely the greedy algorithm and the genetic algorithm (GA). The greedy algorithm, which is similar to the one widely used in 3G1X and Qualcomm high-data-rate (HDR) systems (optimal when n/sub R/=1), exhibits significantly inferior performance when n/sub R/>1 as compared with the optimal approach. On the other hand, the GA is quite promising in terms of performance complexity tradeoff, especially for a system with a large number of users with even a moderately large n/sub R/. As a case in point, for a system with 20 users and n/sub R/=4, the GA is more than 36 times faster than the optimal while the performance degradation is less than 10%, making it an attractive choice in the practical implementation for real-time link scheduling.     

Efficient sequencing techniques for variable-length messages in WDMnetworks

Message sequencing and channel assignment are two important issues that need to be addressed when scheduling variable-length messages in a wavelength division multiplexing (WDM) network. Channel assignment addresses the problem of choosing an appropriate data channel via which a message is transmitted to a node. This problem has been addressed extensively in the literature. On the other hand, message sequencing which addresses the order in which messages are sent, has rarely been addressed. In this paper, we propose a set of scheduling techniques for single-hop WDM passive star networks, which address both the sequencing aspect and the assignment aspect of the problem. In particular, we develop two priority schemes for sequencing messages in a WDM network in order to increase the overall performance of the network. We evaluate the proposed algorithms, using analytical modeling and extensive discrete event simulations, by comparing their performance with state-of-the-art scheduling algorithms that only address the assignment problem. We find that significant improvement in performance can be achieved using our scheduling algorithms where message sequencing and channel assignment are simultaneously taken into consideration. This suggests that, when scheduling messages in WDM networks, one has to consider message sequencing, as well as channel assignment. As a result, we anticipate that this research will open new directions into the problem of on-line scheduling in WDM networks