An analytical model for input-buffered optical packet switches with reconfiguration overhead

The overhead associated with reconfiguring a switch fabric in optical packet switches is an important issue in relation to the packet transmission time and can adversely affect switch performance. The reconfiguration overhead increases the mean waiting time of packets and reduces throughput. The scheduling of packets must take into account the reconfiguration frequency. This work proposes an analytical model for input-buffered optical packet switches with the reconfiguration overhead and analytically finds the optimal reconfiguration frequency that minimizes the mean waiting time of packets. The analytical model is suitable for several round-robin (RR) scheduling schemes in which only non-empty virtual output queues (VOQs) are served or all VOQs are served and is used to examine the effects of the RR scheduling schemes and various network parameters on the mean waiting time of packets. Quantitative examples demonstrate that properly balancing the reconfiguration frequency can effectively reduce the mean waiting time of packets.     

Minimizing Internal Speedup for Performance Guaranteed Switches With Optical Fabrics

We consider traffic scheduling in an N times N packet switch with an optical switch fabric, where the fabric requires a reconfiguration overhead to change its switch configurations. To provide 100% throughput with bounded packet delay, a speedup in the switch fabric is necessary to compensate for both the reconfiguration overhead and the inefficiency of the scheduling algorithm. In order to reduce the implementation cost of the switch, we aim at minimizing the required speedup for a given packet delay bound. Conventional Birkhoff-von Neumann traffic matrix decomposition requires N2 - 2N + 2 configurations in the schedule, which lead to a very large packet delay bound. The existing DOUBLE algorithm requires a fixed number of only 2N configurations, but it cannot adjust its schedule according to different switch parameters. In this paper, we first design a generic approach to decompose a traffic matrix into an arbitrary number of Ns (N² - 2N + 2 > N_S > N) configurations. Then, by taking the reconfiguration overhead into account, we formulate a speedup function. Minimizing the speedup function results in an efficient scheduling algorithm ADAPT. We further observe that the algorithmic efficiency of ADAPT can be improved by better utilizing the switch bandwidth. This leads to a more efficient algorithm SRF (scheduling residue first). ADAPT and SRF can automatically adjust the number of configurations in a schedule according to different switch parameters. We show that both algorithms outperform the existing DOUBLE algorithm.     

QoS-guaranteed packet scheduling in wireless networks

To guarantee the quality of service (QoS) of a wireless network, a new packet scheduling algorithm using cross-layer design technique is proposed in this article. First, the demand of packet scheduling for multimedia transmission in wireless networks and the deficiency of the existing packet scheduling algorithms are analyzed. Then the model of the QoS-guaranteed packet scheduling (QPS) algorithm of high speed downlink packet access (HSDPA) and the cost function of packet transmission are designed. The calculation method of packet delay time for wireless channels is expounded in detail, and complete steps to realize the QPS algorithm are also given. The simulation results show that the QPS algorithm that provides the scheduling sequence of packets with calculated values can effectively improve the performance of delay and throughput.     

Scheduling variable-length messages in a single-hop multichannellocal lightwave network

The design of a medium access control scheme for a single-hop, wavelength-division-multiplexing-(WDM) multichannel local lightwave network poses two major difficulties: relatively large transmitter/receiver tuning overhead and large ratio of propagation delay to packet transmission time. Most schemes proposed so far have ignored the tuning overhead, and they can only schedule fixed-length packet transmissions. To overcome these two difficulties, the authors propose several scheduling algorithms which can reduce the negative impact of tuning overhead and schedule variable-length messages. A separate channel (control channel) is employed for transmission of control packets, and a distributed scheduling algorithm is invoked at each node every time it receives a control packet. By allowing the length of messages to be variable, a long message can be scheduled with a single control packet transmission, instead of fragmenting it into many fixed-length packets, thereby significantly reducing the overhead of control packet transmissions and improving the overall system performance. Three novel scheduling algorithms are proposed, varying in the amount of global information and processing time they need. Two approximate analytical models are formulated to study the effect of tuning time and the effect of having a limited number of data channels. Extensive simulations are conducted. Average message delays are compared for all of the algorithms     

Routing strategies for maximizing throughput in LEO satellite networks

This paper develops routing and scheduling algorithms for packet transmission in a low Earth orbit satellite network with a limited number of transmitters and buffer space. We consider a packet switching satellite network, where time is slotted and the transmission time of each packet is fixed and equal to one time slot. Packets arrive at each satellite independently with a some probability during each time slot; their destination satellite is uniformly distributed. With a limited number of transmitters and buffer space on-board each satellite, contention for transmission inevitably occurs as multiple packets arrive at a satellite. First, we establish the stability region of the system in terms of the maximum admissible packet arrival rate that can possibly be supported. We then consider three transmission scheduling schemes for resolving these contentions: random packet win, where the winning packet is chosen at random; oldest packet win, where the packet that has traveled the longest distance wins the contention; and shortest hops win (SHW), where the packet closest to its destination wins the contention. We evaluate the performance of each of the schemes in terms of throughput. For a system without a buffer, the SHW scheme attains the highest throughput. However, when even limited buffer space is available, all three schemes achieve about the same throughput performance. Moreover, even with a buffer size of just a few packets the achieved throughput is close to that of the infinite buffer case.     

Performance analysis of an RSVP-capable router

RSVP is a bandwidth reservation protocol that allows distributed real-time applications such as videoconferencing software to make bandwidth reservations over packet-switched networks. Coupled with real-time scheduling mechanisms built into packet routers, the network guarantees to provide the reserved bandwidth throughout the lifetime of the applications. Although guaranteed services are of great value to both end users and carrier providers, their performance cost, due to additional control and data processing overhead, can potentially have a negative impact on the packet throughput and latency of RSVP-capable routers. The goal of this article is to examine the performance cost of RSVP based on measurements from an industrial-strength RSVP implementation on a commercial IP router. The focus is on the detailed evaluation of the performance implications of various architectural decisions in RSVP. We found that RSVP's control messages do not incur significant overhead in terms of processing delay and bandwidth consumption. However, the performance overhead of real-time packet scheduling is noticeable in the presence of a large number of real-time connections. In extreme cases, the performance guarantees of existing real-time connections may not be kept, and some best-effort packets are actually dropped, although the overall bandwidth requirement from these connections is smaller than the available link bandwidth     

TDMA scheduling design of multihop packet radio networks based onlatin squares

Many transmission scheduling algorithms have been proposed to maximize spatial reuse and minimize the time division multiple access (TDMA) frame length in multihop packet radio networks. Almost all existing algorithms assume exact network topology information and require recomputations when the network topology changes. In addition, existing work focuses on single channel TDMA systems. In this paper, we propose a multichannel topology-transparent algorithm based on latin squares. The proposed algorithm has the flexibility to allow the growth of the network, i.e., the network can add more mobile nodes without recomputation of transmission schedules for existing nodes. At the same time, a minimum throughput is guaranteed. We analyze the efficiency of this algorithm and examine the topology-transparent characteristics and the sensitivity on design parameters by analytical and simulation techniques     

Opportunistic Scheduling for Wireless Network Coding

This letter addresses a scheduling problem for wireless network coding (WNC). In our previous work, we have theoretically shown that the optimum number of nodes to be included into a network?coded packet as well as its transmission rate depends on time?varying link condition between a transmitting node and receiving nodes [1]. Based on this observation, this letter designs practical scheme which opportunistically selects scheduled nodes, packets to be coded and an employed modulation level according to time?varying channel conditions and packet length. The numerical results show that the proposed opportunistic scheduling can improve the overall throughput as compared with non?opportunistic approach.     

Training overhead for decoding random linear network codes in wireless networks

We consider multicast communications from a single source to multiple destinations through a wireless network with unreliable links. Random linear network coding achieves the min-cut flow capacity; however, additional overhead is needed for end-to-end error protection and to communicate the network coding matrix to each destination. We present a joint coding and training scheme in which training bits are appended to each source packet, and the channel code is applied across both the training and data. This scheme allows each destination to decode jointly the network coding matrix along with the data without knowledge of the network topology. It also balances the reliability of communicating the network coding matrices with the reliability of data detection. The throughput for this scheme, accounting for overhead, is characterized as a function of the packet size, channel properties (error and erasure statistics), number of independent messages, and field size. We also compare the performance with that obtained by individual channel coding of training and data. Numerical results are presented for a grid network that illustrate the reduction in throughput due to overhead.     

Scheduling with base station diversity and fairness analysis for the downlink of CDMA cellular networks

Efficient packet scheduling in CDMA cellular networks is a challenging problem due to the time variant and stochastic nature of the channel fading process. Selection diversity is one of the most effective techniques utilizing random and independent variations of diverse channels to improve the performance of communication over fading channels. In this paper, we propose two packet scheduling schemes exploiting base station selection diversity in the downlink of CDMA cellular networks. The proposed schemes rely on the limited instantaneous channel state information (CSI) to select the best user from the best serving base station at each time slot. This technique increases the system throughput by increasing multiuser diversity gain and reducing the effective interference among adjacent base stations. Results of Monte Carlo simulations are given to demonstrate the improvement of system throughput using the proposed scheduling schemes. In addition, we investigate fairness issue of wireless scheduling schemes. Due to different characteristics of wireless scheduling schemes, the existing fairness indexes may result in misleading comparison among different schemes. We propose a new fairness index to compare the overall satisfaction of the network users for different scheduling schemes. Copyright © 2006 John Wiley & Sons, Ltd.     

基于QoS付费业务的LTE下行跨层分组调度算法

准4G网络（LTE）即将商用会给人们带来更多的方便,以至于大量用户在日常生活中使用更多的QoS业务,这样系统会出现了拥塞和调度不够合理的情况,影响了高优先级业务的丢包率、时延和公平性。通过对LTE下行跨层分组调度各种算法的研究分析,从时延、丢包率、吞吐量和公平性等因素入手,在原有的比例公平性调度算法（PF）上进行改进,加入了补偿因子和付费权重值,使得改进型跨层调度算法,在吞吐量有一定提高的情况下,有效地降低了高优先级业务的丢包率和时延,并确保了高优先级业务的公平性。     

Temporal fairness guarantee in multi-rate wireless LANs for per-flow protection

Wireless LAN technologies such as IEEE 802.11a and 802.11b support high bandwidth and multi-rate data transmission to match the channel condition (i.e., signal to noise ratio). While some wireless packet fair queuing algorithms to achieve the per-flow throughput fairness have been proposed, they are not appropriate for guaranteeing QoS in multi-rate wireless LAN environments. We propose a wireless packet scheduling algorithm that uses the multi-state (multi-rate) wireless channel model and performs packet scheduling by taking into account the channel usage time of each flow. The proposed algorithm aims at per-flow protection by providing equal channel usage time for each flow. To achieve the per-flow protection, we propose a temporally fair scheduling algorithm called Contention-Aware Temporally fair Scheduling (CATS) which provides equal channel usage time for each flow. Channel usage time is defined as the sum of the packet transmission time and the contention overhead time due to the CSMA/CA mechanism. The CATS algorithm provides per-flow protection in wireless LAN environments where the channel qualities of mobile stations are dynamic over time, and where the packet sizes are application-dependent. We also extend CATS to Decentralized-CATS (D-CATS) to provide per-flow protection in the uplink transmission. Using an NS-2 simulation, we evaluate the fairness property of both CATS and D-CATS in various scenarios. Simulation results show that the throughput of mobile stations with stable link conditions is not degraded by the mobility (or link instability) of other stations or by packet size variations. D-CATS also shows less delay and less delay jitter than FIFO. In addition, since D-CATS can coordinate the number of contending mobile stations, the overall throughput is not degraded as the number of mobile stations increases. This work was supported in part by the Brain Korea 21 project of Ministry of Education and in part by the National Research Laboratory project of Ministry of Science and Technology, 2004, Korea.     

Performance of space-division multiple-access (SDMA) with scheduling

Efficient exploitation of spatial diversity is fundamentally important to resource critical wireless applications (Tsoulos 1999). In this paper, we first study the performance of intelligent scheduling for space-division multiple-access (SDMA) wireless networks (Suard 1998, Farsakh 1998). Based on the existing scheme, we propose a new medium access protocol (MAC) for multimedia SDMA/time-division multiple-access (TDMA) packet networks (Xu 1994, Ward 1993). The improved protocol performs scheduling based on users' spatial characteristics and quality-of-service parameters to achieve throughput multiplication and packet delay reduction. Performance of SDMA with scheduling is evaluated under mixed audio and data traffic patterns and results show that significant improvement in network performance can be achieved under the new protocol.     

一种具有小尺度公平的无线分组调度算法

本文在调度判决时考虑到用户的访问时延限制,比例公平调度算法基础上提出了M-PF算法。本文建立了无线分组调度系统模型,通过仿真对新算法在小尺度服务时间保证、大尺度服务时间公平和系统吞吐量等方面的性能进行分析,研究了系统参数对算法性能的影响。结果证明,新算法在保证系统吞吐量和大尺度公平性的同时可以提供更好的小尺度服务时间保证。     

Radio resources allocation for decentrally controlled relay stations

To enhance throughput and to extend coverage of wireless networks based on IEEE 802.16 standards, relay stations can be implemented. The crucial point influencing the overall system performance is allocation of appropriate amount of resources to individual relay stations depending on their current needs. If resources are not allocated properly, relay stations can experience congestion situations resulting in system throughput decrease and packet delays increase. If the base station is enhanced purely by centrally controlled relay stations, the base station itself is able to dynamically schedule data transmissions of its relays. Nevertheless, decentrally controlled relays schedule data for its users on its own and the base station is no longer capable to allocate the right amount of radio resources for them. The decentrally controlled relays have to ask for radio resources by means of existing scheduling services defined in IEEE 802.16 standard. While utilization of the conventional unsolicited grant service decreases the system capacity, the use of real-time polling or extended real-time polling services results in higher signaling overhead and longer packet delays. In order to maximize system throughput and to minimize packet delays and signaling overhead, we suggest a mechanism that pre-allocates to decentrally controlled relay stations a certain amount of default radio resources while the remaining resources are dynamically shared. The obtained results show that for low traffic load, overhead and packet delays are significantly smaller as relays do not have to ask base stations for resources. On the other hand, at heavy traffic load the system throughput slightly decreases whereas packet delays and signaling overhead are still significantly smaller.     

HSDPA分组调度算法与小区吞吐率研究

分组调度是HSDPA的核心技术之一,对网络性能有重要影响。在HSDPA分组调度功能和实现的基础上,重点分析对比3种典型分组调度算法原理及其对系统的影响,并通过实际测试验证,明确了不同调度算法对小区吞吐率的影响。结论:MAXCI算法下能够得到最大的系统吞吐量,公平性最差;RR算法公平性最好,系统资源利用率最低,吞吐率最小;EPF算法既考虑了用户的公平性,也能从一定程度上保证比较高的系统吞吐量,是一种实用的调度方法。     

QoS-aware joint working packet scheduling and call admission control for video streaming service over WiMAX network

In this paper, we propose a QoS-aware joint working packet scheduling algorithm and call admission control algorithm to support stable video streaming service to more subscribers over WiMAX network. The proposed call admission control algorithm estimates the network throughput by using a local linear model in terms of a control parameter of the proposed scheduling algorithm, and performs its own functions based on the information. The proposed scheduling algorithm continuously updates the control parameter to pursue an effective tradeoff between the quality-of-service of video streaming and the network throughput. Finally, simulation results are provided to show the performance of the proposed video streaming system.     

Simulation‐based real‐time routing protocol with load distribution in wireless sensor networks

In wireless sensor networks (WSNs), sensors gather information about the physical world and the base station makes decision and then performs appropriate actions upon the environment. This technology enables a user to effectively sense and monitor from a distance in real‐time. WSNs demand real‐time forwarding which means messages in the network are delivered according to their end‐to‐end deadlines (packet lifetime). This paper proposes a novel real‐time routing protocol with load distribution (RTLD) that ensures high packet throughput with minimized packet overhead and prolongs the lifetime of WSN. The routing depends on optimal forwarding (OF) decision that takes into account of the link quality (LQ), packet delay time and the remaining power of next hop sensor nodes. The proposed mechanism has been successfully studied through simulation work. Copyright © 2009 John Wiley & Sons, Ltd.     

On the packet loss overhead in buffer-limited ad hoc networks

This paper focuses on the routing overhead analysis in ad hoc networks. Available work in this research field considered the infinite buffer scenario, so that buffer overflow will never occur. Obviously, in realistic ad hoc networks, the node buffer size is strictly bounded, which leads to unavoidable packet loss. Once a packet is dropped by a relay node, the bandwidth consumption for the previous transmission is actually wasted. We define the extra wasted bandwidth as the packet loss (PL) overhead. A theoretical analysis framework based on G/G/1/K queuing model is provided, to estimate the PL overhead for any specific routing protocols. Then, with this framework, we propose a distributed routing algorithm termed as novel load-balancing cognitive routing (NLBCR). The OPNET network simulator is further conducted to compare the performance among the NLBCR, AODV and CRP. The results indicate that NLBCR can reduce routing overhead to a considerable extent, as well as improve the network throughput and decrease the end-to-end delay.     

Resource allocation for real-time traffic in unreliable wireless cellular networks

Providing reliable transmission for real-time traffic in wireless cellular networks is a great challenge due to the unreliable wireless links. This paper concentrates on the resource allocation problem aiming to improve the real-time throughput. First, the resource allocation problem is formulated as a Markov Decision Process and thus the optimal resource allocation policy could be obtained by adopting the value iteration algorithm. Considering the high time complexity of the optimal algorithm, we further propose an approximate algorithm which decomposes the resource allocation problem into two subproblems, namely link scheduling problem and packet scheduling problem. By this method, the unreliable wireless links are only constrained in the link scheduling problem, and we can focus on the real-time requirement of traffic in packet scheduling problem. For the link scheduling problem, we propose the maxRel algorithm to maximize the long-term network reliability, and we theoretically prove that the maxRel algorithm is optimal in scenarios with dynamic link reliabilities. The Least Laxity First algorithm is adopted for the packet scheduling problem. Extensive simulation results show that the proposed approximate resource allocation algorithm makes remarkable improvement in terms of time complexity, packet loss rate and delay.