Degree-sequenced matching algorithms for input-queued switches

This paper presents a class of algorithms for scheduling packets in input-queued switches. As opposed to previously known algorithms that focus only on achieving high throughput, these algorithms seek to achieve low average delay without compromising the throughput achieved. Packet scheduling in input-queued switches based on the virtual-output-queued architecture is a bipartite graph matching problem wherein ports are represented by vertices and the traffic flows by the edges. The set of matched edges determine the packets that are to be transferred from the input ports to the output ports. Current matching algorithms implicitly prioritize high-degree vertices, i.e., ports with a large number of flows, causing longer delays at ports with a smaller number of flows. Motivated by this observation, we present three matching algorithms based on explicitly prioritizing low-degree vertices and the edges through them. Using both real gateway traffic traces as well as synthetically generated traffic, we present simulation results showing that this class of algorithms achieves a low average delay as compared to other scheduling algorithms of equivalent complexity while still achieving similar throughput. We also show that these algorithms determine the maximum size matching in almost all cases.     

High-speed buffer management for 40 gb/s-based photonic packet switches

We develop a method of high-speed buffer management for output-buffered photonic packet switches. The use of optical fiber delay lines is a promising solution to constructing optical buffers. The buffer manager determines packet delays in the fiber delay line buffer before the packets arrive at the buffer. We propose a buffer management method based on a parallel and pipeline processing architecture consisting of (log/sub 2/N+1) pipeline stages, where N is the number of ports of the packet switch. This is an expansion of a simple sequential scheduling used to determine the delays of arriving packets. Since the time complexity of each processor in the pipeline stages is O(1), the throughput of this buffer management is N times larger than that of the sequential scheduling method. This method can be used for buffer management of asynchronously arriving variable-length packets. We show the feasibility of a buffer manager supporting 128 /spl times/ 40 Gb/s photonic packet switches, which provide at least eight times as much throughput as the latest electronic IP routers. The proposed method for asynchronous packets overestimates the buffer occupancy to enable parallel processing. We show through simulation experiments that the degradation in the performance of the method resulting from this overestimation is quite acceptable.     

Capacity and delay of hybrid wireless broadband access networks

An optical network is too costly to act as a broadband access network. On the other hand, a pure wireless ad hoc network with n nodes and total bandwidth of W bits per second cannot provide satisfactory broadband services since the pernode throughput diminishes as the number of users goes large. In this paper, we propose a hybrid wireless network, which is an integrated wireless and optical network, as the broadband access network. Specifically, we assume a hybrid wireless network consisting of n randomly distributed normal nodes, and m regularly placed base stations connected via an optical network. A source node transmits to its destination only with the help of normal nodes, i.e., in the ad hoc mode, if the destination can be reached within L (L /spl geq/ 1) hops from the source. Otherwise, the transmission will be carried out in the infrastructure mode, i.e., with the help of base stations. Two transmission modes share the same bandwidth of W bits/sec. We first study the throughput capacity of such a hybrid wireless network, and observe that the throughput capacity greatly depends on the maximum hop count L and the number of base stations m. We show that the throughput capacity of a hybrid wireless network can scale linearly with n only if m = Ω(n), and when we assign all the bandwidth to the infrastructure mode traffics. We then investigate the delay in hybrid wireless networks. We find that the average packet delay can be maintained as low as Θ(1) even when the per-node throughput capacity is Θ(W).     

On asymptotically fair transmission scheduling over fading channels with measurement delay

We examine the effect of measurement delays on the throughput of certain downlink data packet systems operating over Rayleigh fading channels. In these systems the base station (BS) schedules a single user at a time and transmits at a rate which is based on measurements of the BS's received power performed by the user. The same subject was also discussed in a recent paper, titled "Asymptotically fair transmission scheduling over fading channels" by Berggren and Jantti (2004). They studied the effects of measurement delays on the operation of the scheduler. As a consequence of the delay, it is possible that by the time the BS actually transmits data, the propagation channels might have changed, such that the scheduler's choice no longer conforms to the desired scheduling policy, resulting in loss of system throughput and multi-user gain. Berggren and Jantti assume that perfect link adaptation is nevertheless always assured, i.e., that the BS transmits at a rate that matches precisely the current state of the selected user's channel. However, measurement delays lead also to mismatch between the data rate the BS transmits to the chosen user, and the current state of the propagation channel to that user. We believe that this mismatch must also be taken into account. In this letter we propose to use a backoff factor and analyze its mitigating effect on losses introduced by measurements delay in a Rayleigh fading environment. We then show the resulting gain in system throughput for optimal choices of the backoff factor     

PROTON: a media access control protocol for optical networks withstar topology

A new multiple access protocol called PROTON (PROTocol for Optical Networks) is developed for optical local area networks based on a passive star topology. PROTON uses wavelength division multiplexing (WDM) and is highly bandwidth-efficient. One of the available wavelengths is used as a control channel. Time is divided into fixed-sized slots. The size of the slots is the same for the control and the data channels. Before transmitting a packet, a station must compete with others for a slot in a data wavelength, using a collision-free procedure. Transmitting stations and the corresponding wavelengths for their data transmissions are determined at each station by a simple arbitration scheme. The protocol is suitable for networks where the number of users can be much larger than the number of available data channels. In addition to propagation delays, it is considered that transmitter and receiver tuning times as well as the times required to process control packets are not negligible. Whenever possible, and to maximize the throughput of the network, tuning and processing times of transmitters and receivers are overlapped with each other and with data transmission times. Also, data slot requests and packet transmissions are scheduled in a pipeline fashion, thus reducing the detrimental effects on throughput and packet delay of long propagation delays. The paper includes an analysis of the maximum throughput characteristics of PROTON. An analytical model is developed, and several performance measures are obtained     

Performance Constraint Analysis of WDM LANs with Nonzero Propagation Delays and Destination Conflicts

In this paper, we study the effect of the round trip propagation delay on performance measures of wavelength division multiplexing (WDM) networks. Even though the impact of propagation delay is substantial in the optical network's behavior, most of the studies ignore the effect of this time component in throughput and delay evaluation. We assume a WDM local area network (LAN) where the round trip propagation delay is less or equal to a data packet transmission time. The proposed asynchronous transmission policy avoids data channel collision. In the analysis, we take into account the propagation delays and the effect of receiver collision for a system with a finite number of stations.     

Super-Fast Delay Tradeoffs for Utility Optimal Fair Scheduling in Wireless Networks

We consider the fundamental delay tradeoffs for utility optimal scheduling in a general network with time-varying channels. A network controller acts on randomly arriving data and makes flow control, routing, and resource allocation decisions to maximize a fairness metric based on a concave utility function of network throughput. A simple set of algorithms are constructed that yield total utility within$O(1/V)$of the utility-optimal operating point, for any control parameter$V≫0$, with a corresponding end-to-end network delay that grows only logarithmically in$V$. This is the first algorithm to achieve such “super-fast” performance. Furthermore, we show that this is the best utility-delay tradeoff possible. This work demonstrates that the problem of maximizing throughput utility in a data network is fundamentally different than related problems of minimizing average power expenditure, as these latter problems cannot achieve such performance tradeoffs.     

On scheduling all-to-all personalized connection and cost-effectivedesigns in WDM rings

We consider the problem of scheduling all-to-all personalized connections (AAPC) in WDM rings. Scheduling one connection for every source-destination pair in a network of limited connectivity provides a way to reduce routing control and guarantee throughput. For a given number of wavelengths K and a given number of transceivers per node T, we first determine the lower bound (LB) on the schedule length, which depends on both K and T. To achieve the LB, either the network bandwidth, the I/O capacity, or both should be fully utilized. This approach first constructs and then schedules circles, each of which is formed by up to four non-overlapping connections and can fully utilize the bandwidth of one wavelength. The proposed circle construction and scheduling algorithms can achieve the LB if K⩽T相似文献   

A novel medium access control protocol for WDM-based LAN's andaccess networks using a master/slave scheduler

We describe an architecture and medium access control (MAC) protocol for wavelength-division multiplexing (WDM) networks. Our system is based on a broadcast star architecture and uses an unslotted access protocol and a centralized scheduler to efficiently provide bandwidth-on-demand in WDM networks. To overcome the effects of propagation delays the scheduler measures the delays between the terminals and the hub and takes that delay into account when scheduling transmissions. Simple scheduling algorithms, based on a look-ahead capability, are used to overcome the effects of head-of-line blocking. An important application area for this system is in optical access networks, where this novel MAC protocol can be used to access wavelengths in a WDM passive optical network (PON)     

Cross-Layer Design for End-to-End Throughput and Fairness Enhancement in Multi-Channel Wireless Mesh Networks

In this paper, we study joint rate control, routing and scheduling in multi-channel wireless mesh networks (WMNs), which are traditionally known as transport layer, network layer and MAC layer issues respectively. Our objective is to find a rate allocation along with a flow allocation and a transmission schedule for a set of end-to-end communication sessions such that the network throughput is maximized, which is formally defined as the maximum throughput rate allocation (MRA) problem. As simple throughput maximization may result in a severe bias on rate allocation, we take account of fairness based on a simplified max-min fairness model and the proportional fairness models. We define the max-min guaranteed maximum throughput rate allocation (MMRA) problem and proportional fair rate allocation (PRA) problem. We present efficient linear programming (LP) and convex programming (CP) based schemes to solve these problems. Numerical results show that proportional fair rate allocation schemes achieves a good tradeoff between throughput and fairness.     

Maximizing the Network Stability in Mobile WiMAX Mesh Networks

Resource scheduling and routing tree construction in WiMAX mesh centralized scheduling are not defined in the standard and thus are subject to extensive research. In this paper, we consider routing and scheduling in a WiMAX-based mesh network. We assume that nodes are not necessarily stationary, but rather mobile with a mobility that may yield to frequent topology changes (e.g., failure of existing links and creation of new transmission links). We model the joint routing and scheduling as an optimization problem whose objective is either to determine a minimum length schedule by maximizing spectrum spatial reuse or maximizing the network lifetime by routing around the less stable RF-links, while satisfying a set of (uplink/downlink) end-to-end demands. While solving the problem with the two objectives, we study the tradeoffs between these two objectives. We show that minimizing the schedule length forces the joint routing and scheduling problem to generate a routing tree and feasible transmission groups which favor higher spectrum spatial reuse (and hence higher system throughput), irrespective of the robustness of the selected transmission links. In addition, we show that maximizing the network stability or lifetime yields the selection of different routing trees and slot assignments which do not necessarily result in shorter schedule length. We perform numerical experiences where we compare the performances of our proposed models with respect to the network stability and resource spatial reuse.     

A Joint Transmission Grant Scheduling and Wavelength Assignment in Multichannel SG-EPON

In this paper, we investigate the problem of transmission grant scheduling in multichannel optical access networks using a scheduling theoretic approach. A novel cost-effective multichannel Ethernet passive optical network (EPON) is considered for our study. We show that the problem can be modeled as an open shop (OS) and we formulate the joint scheduling and wavelength assignment problem as a mixed integer linear program (MILP). Since the problem is shown to be NP-hard, we introduce a tabu-search-based heuristic for solving the joint problem. Different other heuristics are also considered and their performances are compared with those of tabu and MILP. Results indicate that by appropriately scheduling transmission grants and assigning wavelengths, substantial and consistent improvements may be obtained in the network performance. For example, tabu shows a reduction of up to 29% in the schedule length with substantial reduction in channel idle gaps yielding to both higher channel utilization and lower queueing delays. Additionally, when the number of channels in the network is not small, the benefits of performing appropriate wavelength assignment, together with transmission scheduling, are observed and discussed. We further perform a packet-level simulation on the considered network to study the benefits of efficient grant scheduling.     

Design and Analysis of a Channel Access Protocol for WDM-Based Single-Hop Optical Networks*

We propose a channel access protocol for single-hop wavelength division multiplexing (WDM) optical networks. Each node is equipped with a fixed-tuned transmitter, a tunable transmitter, a fixed-tuned receiver, and a tunable receiver. The proposed protocol alleviates the drawbacks of a previous protocol [1], e.g., invalid data transmissions that follows receiver collisions and possible acknowledgment packet collisions with header/data packets, while retaining many advantages. As a result, the network performance in terms of throughput and packet delay is improved. Analytical models based on the timing diagram analysis, the continuous-time Markov chain, and the randomization technique are developed to assess the proposed protocol, and are validated through event-driven simulation. The performance is evaluated in terms of channel utilization, mean packet delay, and packet delay distribution with variations in the number of nodes, the offered traffic, the size of data packets, and the network propagation delay. Through numerical results and simulation studies, we show that the proposed protocol achieves better channel utilization and incurs lower packet delays.     

Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks

The question of providing throughput guarantees through distributed scheduling, which has remained an open problem for some time, is addressed in this paper. It is shown that a simple distributed scheduling strategy, maximal scheduling, attains a guaranteed fraction of the maximum throughput region in arbitrary wireless networks. The guaranteed fraction depends on the ldquointerference degreerdquo of the network, which is the maximum number of transmitter-receiver pairs that interfere with any given transmitter-receiver pair in the network and do not interfere with each other. Depending on the nature of communication, the transmission powers and the propagation models, the guaranteed fraction can be lower-bounded by the maximum link degrees in the underlying topology, or even by constants that are independent of the topology. The guarantees are tight in that they cannot be improved any further with maximal scheduling. The results can be generalized to end-to-end multihop sessions. Finally, enhancements to maximal scheduling that can guarantee fairness of rate allocation among different sessions, are discussed.     

Graph‐based optimal asynchronous scheduling in large propagation delay underwater acoustic sensor networks

Optimal scheduling is essential to minimize the time wastage and maximize throughput in high propagation delay networks such as in underwater and satellite communication. Understanding the drawbacks of synchronous scheduling, this paper addresses an asynchronous optimal scheduling problem to minimize the time wastage during the transmission. The proposed scheduling problem is analyzed in both broadcast and non‐broadcast networks, which is highly applicable in high propagation delay networks. In broadcast networks, the proposed scheduling method reduces to a graph‐theoretic model that is shown to be equivalent to the classic algorithmic asymmetric traveling salesman problem (TSP) which is NP‐Hard. Although it is NP‐Hard, the TSP is well‐investigated with many available methods to find the best solution for up to tens of thousands of nodes. In non‐broadcast networks, the optimal solution to the scheduling problem considers the possibility of parallel transmission, which is optimized using graph coloring algorithm. The groups obtained through graph coloring are solved using Asymmetric Traveling Salesman algorithm to obtain the optimal schedule. The proposed method efficiently solves the scheduling problem for networks of practical size.     

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.     

On the All-to-All Broadcast Problem in Optical Networks1

This paper considers the transmission of uniform deterministic traffic in an optical broadcast-star network using Wavelength Division Multiplexing. Lower bounds are established on the minimum time to exchange information between every node pair in such a network with tunable transmitters and fixed-tuned receivers. Three different scheduling algorithms are developed that are strictly optimal in three regimes of system parameters. The results are applicable to arbitrary tuning delays and arbitrary numbers of wavelength channels, and indicate the existence of a well-defined transition regime from tuning-limited operation to bandwidth-limited operation. Finally, the problem of computing the optimal number of wavelengths is addressed to achieve a schedule with minimum schedule length, and exact solutions are given.     

Optimization of multipath transmission path scheduling based on forward delay in vehicular heterogeneous network

In order to solve the problem that the data packets were out of order at the receiving end in the multipath transmission,which greatly reduced the transmission performance,an optimization algorithm was proposed for multipath transmission path scheduling based on forward delay in the vehicle heterogeneous network.The main idea of the proposed algorithm was to schedule data packets through a concurrent path according to the forward delay and throughput difference estimated by the sender.A simulation experiment was carried out on NS-3.The simulation results show that compared with the previous algorithm,the proposed algorithm has better performance than other algorithms in reorder-buffer-occupancy density (RBD) and throughput.The problem of out-of-order data packets at the receiving end is significantly reduced,and the total system throughput and network utilization have been improved.     

Prediction‐based MAC‐layer sensing in cognitive radio networks

We consider a cognitive radio network which coexists with multiple primary users (PUs) and secondary users (SUs) transmit over time‐varying channels. In this scenario, one problem of the existing work is the poor performances of throughput and fairness due to variances of SUs' channel conditions and PUs' traffic patterns. To solve this problem, we propose a novel prediction‐based MAC‐layer sensing algorithm. In the proposed algorithm, the SUs' channel quality information and the probability of the licensed channel being idle are predicted. Through the earlier predicted information, we schedule the SUs to sense and transmit on different licensed channels. Specifically, multiple significant factors, including network throughput and fairness, are jointly considered in the proposed algorithm. Then, we formulate the prediction‐based sensing scheduling problem as an optimization problem and solve it with the Hungarian algorithm in polynomial time. Simulation results show that the proposed prediction‐based sensing scheduling algorithm could achieve a good tradeoff between network throughput and fairness among SUs. Copyright © 2014 John Wiley & Sons, Ltd.     

A periodic scheduling problem in flow control for datacommunication networks

The scheduling of user-session transmission-priority time slots in time-periodic frames on links in a network is considered from an algorithmic standpoint. Priority slot schedules with low schedule delays can be used in a flow control scheme to lower limits on packet intranetwork delay. An NP-completeness result is proved, showing that for general networks the scheduling of priority slots to obtain a minimum sum of schedule delays is algorithmically hard. Minimum-delay scheduling algorithms for special classes and a scheduling heuristic for general networks are presented