Matching From the First Iteration: An Iterative Switching Algorithm for an Input Queued Switch

An iterative switching algorithm for an input queued switch consists of a number of iterations in every time step, where each iteration computes a disjoint matching. If input is matched to output in a given iteration, a packet (if any) is forwarded from to in the corresponding time step. Most of the iterative switching algorithms use a request grant accept (RGA) arbitration type (e.g. iSLIP). Unfortunately, due to this particular type of arbitration, the matching computed in one iteration is not necessarily maximal (more input and output ports can still be matched). This is exactly why multiple iterations are needed. However, multiple iterations make the time step larger and reduce the speed of the switch. We present a new iterative switching algorithm (based on the RGA arbitration) called with the underlying assumption that the number of iterations is possibly limited to one, hence reducing the time step and allowing the switch to run at a higher speed. We prove that achieves throughput and delay guarantees with a speedup of 2 and one iteration under a constant burst traffic model, which makes as good as any maximal matching algorithm in the theoretical sense. We also show by simulation that achieves relatively high throughput in practice under uniform and non-uniform traffic patterns with one iteration and no speedup.     

Analytical Evaluation of PHM Convergence

The parallel hierarchical matching (PHM) algorithm is a distributed maximal size matching scheduler for virtual output-queued switches. In a previous letter, we formulated an upper bound on the maximum number of iterations PHM requires to achieve a maximal size matching in any traffic scenario. In this letter, we follow an analytical approach to find the average number of iterations for PHM to achieve a maximal size matching under diverse traffic models. The estimated number of iterations is$O(log_2N)$, as in the case of iSLIP-like algorithms.     

Adaptive Input Traffic Prediction Scheme for Absolute and Proportional Delay Differentiated Services in Broadband Convergence Network

In this paper, an algorithm that provides absolute and proportional differentiation of packet delays is proposed with the objective of enhancing quality of service in future packet networks. It features an adaptive scheme that adjusts the target delay for every time slot to compensate the deviation from the target delay, which is caused by prediction error on the traffic to arrive at the next time slot. It predicts the traffic to arrive at the beginning of a time slot and measures the actual arrived traffic at the end of the time slot. The difference between them is utilized by the delay control operation for the next time slot to offset it. Because the proposed algorithm compensates the prediction error continuously, it shows superior adaptability to bursty traffic and exponential traffic. Through simulations we demonstrate that the algorithm meets the quantitative delay bounds and is robust to traffic fluctuation in comparison with the conventional non‐adaptive mechanism. The algorithm is implemented with VHDL on a Xilinx Spartan XC3S1500 FPGA, and the performance is verified under the test board based on the XPC860P CPU.     

Fair Algorithms for Maximal Link Activation in Multihop Radio Networks

We present a distributed algorithm for obtaining a fair time slot allocation for link activation in a multihop radio network. We introduce the concept of maximal fairness in which the termination of a fair allocation algorithm is related to maximal reuse of the channel under a given fairness metric. The fairness metric can be freely interpreted as the expected link traffic load demands, link priorities, etc. Since respective demands for time slot allocation will not necessarily be equal, we define fairness in terms of the closeness of allocation to respective link demands while preserving the collision free property. The algorithm can be used in conjunction with existing link activation algorithms to provide a fairer and fuller utilization of the channel.     

Concurrent round-robin-based dispatching schemes for Clos-network switches

A Clos-network switch architecture is attractive because of its scalability. Previously proposed implementable dispatching schemes from the first stage to the second stage, such as random dispatching (RD), are not able to achieve high throughput unless the internal bandwidth is expanded. This paper presents two round-robin-based dispatching schemes to overcome the throughput limitation of the RD scheme. First, we introduce a concurrent round-robin dispatching (CRRD) scheme for the Clos-network switch. The CRRD scheme provides high switch throughput without expanding internal bandwidth. CRRD implementation is very simple because only simple round-robin arbiters are adopted. We show via simulation that CRRD achieves 100% throughput under uniform traffic. When the offered load reaches 1.0, the pointers of round-robin arbiters at the first- and second-stage modules are completely desynchronized and contention is avoided. Second, we introduce a concurrent master-slave round-robin dispatching (CMSD) scheme as an improved version of CRRD to make it more scalable. CMSD uses hierarchical round-robin arbitration. We show that CMSD preserves the advantages of CRRD, reduces the scheduling time by 30% or more when arbitration time is significant and has a dramatically reduced number of crosspoints of the interconnection wires between round-robin arbiters in the dispatching scheduler with a ratio of 1//spl radic/N, where N is the switch size. This makes CMSD easier to implement than CRRD when the switch size becomes large.     

Design of the Switching Controller for the High-Capacity Non-Blocking Internet Router

The sequential greedy scheduling (SGS) algorithm is a scalable maximal matching algorithm. This algorithm was conceptually proposed and well received since it provides non-blocking in an Internet router with input buffers and a cross-bar, unlike other existing implementations. In this paper, we implent a new design of the SGS algorithm, and determine its exact behaviour, performance and QoS that it provides. We examine different design options and measure the performance of their implementations in terms of their scalability and speed. It will be shown that multiple scheduler modules of a terabit Internet router can be implemented on a low-cost field-programmable gate-array (FPGA) device, and that the processing can be performed within the desired time slot duration. Proper functioning of the implemented scheduler was confirmed through thorough software and hardware testing.      

Time slot assignment in a heterogeneous environment of a SS/TDMA system

In this paper we consider the time slot assignment for a heterogeneous environment in which circuit-switched traffic and packet-switched traffic share the same satellite. In constructing a single time division multiple access (TDMA) frame for both traffic types, their different characteristics must be taken into account. This problem is known to be NP-complete and a couple of heuristic partial optimization algorithms have been developed. In this paper, we first provide a theoretical result to improve the existing partial optimization algorithms; then a fully optimizing heuristic algorithm is presented. Simulation results show that our algorithm provides a much better solution quality than existing ones. © 1997 John Wiley & Sons, Ltd.     

Preference-aware coding data broadcast in delay tolerant networks

Traditional data broadcasting schemes in delay tolerant networks assume that mobile users can only retrieve one data item in each time slot. In this paper, we propose a novel data broadcasting framework in the delay tolerant networks that exploits the concept of network coding to mix the delivered data items according to the user’s stored data items. Our approach enables a user to encode multiple data items dynamically in each time slot, and allows each user with a mobile device to retrieve a data item by using locally stored data items to decode the encoding data. Specifically, we design an algorithm called Preference-Aware Coding (PAC) to select the data items to be encoded in each time slot. The objective is to serve the maximal number of mobile users with the encoding data and minimize the access time required for data broadcasting in the delay tolerant networks. The algorithm avoids encoding unnecessary data in each time slot to reduce the access delay. We empirically implement the framework in the real delay tolerant networks, and simulation results show that the PAC algorithm can reduce the access time of the traditional scheme by 42 % on average.     

Bandwidth reservations by maximal matching algorithms

A maximal matching algorithm switches packets through a cross-bar with the speed-up of two without blocking them. Namely, traffic will go through the cross-bar controlled by a maximal matching algorithm if its outputs are not overloaded. Consequently, bandwidth reservations with delay guarantees are simple to provide. We propose a protocol for distributed bandwidth reservations, where users check the communication availability among themselves. It will be also shown that maximal matching algorithms cannot utilize full cross-bar capacity for some particular traffic patterns.     

一种基于IEEE802.16无线MESH网络集中调度机制的时隙分配方法

在基于IEEE 802.16的无线Mesht网络中,时隙分配算法对网络性能有重要影响.针对现有时隙分配算法只研究上行链路且时隙分配的结果导致中继节点在转发数据时频繁在相邻时隙间进行收发切换的问题,提出了一种上下行链路通用的时隙分配方法,对于上行链路,跳数较小节点的数据优先传输,而对于下行链路,跳数较大节点的数据优先传输,在传输路径上采用逐跳传输的策略.仿真结果证明了该算法的有效性.     

Impact of scheduling algorithms on performance of crosspoint-queued switch

The performance analysis of the 32?×?32 crosspoint-queued switch is presented in this paper. Switches with small buffers in crosspoints have been evaluated in the late 1980s but mostly for uniform traffic. However, due to technological limitations of that time, it was impractical to implement large buffers together with switching fabric. The crosspoint-queued switch architecture has been recently brought back into focus since modern technology enables an easy implementation of large buffers in crosspoints. An advantage of this solution is the absence of control communication between linecards and schedulers. In this paper, the performances of four algorithms (longest queue first, round robin, exhaustive round robin, and frame-based round robin matching) are analyzed and compared. The results obtained for the crosspoint-queued switch are compared with the output queued switch. Throughput, average cell latency and instantaneous packet delay variance are evaluated under uniform and nonuniform traffic patterns. The results will show that the longest queue first algorithm has the highest throughput in many simulated cases but the highest average cell latency and delay variance among observed algorithms. It will also be shown that the choice of the scheduling algorithm does not play a role in the switch performance if the buffers are long enough. This will prove that some form of round-robin-based algorithms become a better choice for implementation due to their simplicity, small hardware requirements, and avoidance of the starvation problem, which is a major drawback of the longest queue first algorithm.     

Low‐jitter slot assignment algorithm for deadline‐aware packet transmission in wireless video surveillance sensor networks

This work presents a distributed time‐slot assignment algorithm which adopts TDMA as Medium Access Control, specially suited to support applications with strict delay, jitter, and throughput requirements characterized by convergecast traffic pattern in sensor networks. (e.g. wireless video surveillance sensor networks). The proposed algorithm has three characteristics: (1) every node is guaranteed a path to the base station for its data delivery. In the path, sufficient resource is reserved and weighted fairness can be achieved. (2) It uses cascading time‐slot assignment and jitter minimization algorithm in each node to minimize jitter and end‐to‐end delay. (3) Nodes are only active during their scheduled slots and sleep otherwise. This offers energy saving by reducing idle listening and avoiding overhearing. The performance of the proposed algorithm is evaluated over simulations and analyzed theoretically in comparison with existing slot assignment algorithm. The results show that our algorithm provides lower end‐to‐end delay, jitter, and higher throughput. Copyright © 2010 John Wiley & Sons, Ltd.     

CDMA-based anti-collision algorithm for EPC global C1 Gen2 systems

Frame slotted ALOHA protocol as a key technology to improve system throughput has been widely applied to modern radio frequency identification systems. In this paper, a novel frame slotted ALOHA collision arbitration protocol based on code division multiple access has been proposed. The main aim of the proposed algorithm is to avoid collisions between multiple tags. In the scheme, an orthogonal sequence is used as the means to distinguish the transmitted data from different tags within the same time slot and frequency band. The theoretical analysis and simulation results proved that the performance of our proposed algorithm outperforms the existing ALOHA-based protocols.     

An Optimal Switching Algorithm for Multibeam Satellite Systems with Variable Bandwidth Beams

In this paper we consider an SS/TDMA system withMuplink beams andNdownlink beams, where uplink beamihas bandwidth βiand downlink beamjhas bandwidth αj. The maximum traffic which can be handled by the satellite (in any given time slot) is assumed to beK. Multiplexing and demuitiplexing are also assumed. An optimal time slot assignment algorithm to minimize the total transmission time for any given traffic demand matrix is proposed and analyzed. Other system configurations of interest are also discussed.     

Perfect match model‐based link assignment to design topology for satellite constellation system

In satellite constellation network, the satellites visible from one satellite are more than communication terminals (CTs) equipped. Each inter‐satellite link (ISL) would occupy one CT on each of two satellites connected by this ISL. Therefore, a fundamental problem considering link assignment is how to assign limited CTs for each satellite to establish ISLs with its visible satellites. Link assignment scheme based on perfect match model (LAS‐PMM) is proposed to make full use of huge bandwidth provided by CT. In LAS‐PMM, the problem of assigning all the CTs of each satellite to establish ISLs is modeled as a perfect matching problem, where a perfect matching is searched over a mixed complete bipartite graph. Simulation results show that LAS‐PMM is better than the regular and greedy LASs, in terms of CT utilization and average node‐to‐node distance. Copyright © 2015 John Wiley & Sons, Ltd.     

Scheduling algorithm for VOQ switches

A variety of matching schemes for VOQ switches that provide high throughput for uniform traffic have been proposed. The dual round robin matching (DRRM) scheme has performance similar to iSLIP and lower implementation complexity. DRRM with exhaustive service (EDRRM) algorithm was created as modification of DRRM algorithm with goal to improve performance of DRRM algorithm for bursty and non-uniform traffic conditions. Under extremely unbalanced arrival traffic, an exhaustive service policy may lead to unfairness and starvation. This paper proposes matching scheme for VOQ switches that provides high throughput almost the same as EDRRM scheme and avoid unfairness and starvation under unbalanced traffic.     

Round-robin selection with adaptable-size frame in a combined input-crosspoint buffered switch

As an alternative to input-buffered switches, combined input-crosspoint buffered switches relax arbitration timing and provide high-performance switching for packet switches with high-speed ports. It has been shown that these switches, with one-cell crosspoint buffer and round-robin (RR) arbitration at input and output ports, provide 100% throughput under uniform traffic. However, under admissible traffic patterns with nonuniform distributions, only weight-based selection schemes are reported to provide high throughput. We propose an RR based arbitration scheme for a combined input-crosspoint buffered packet switch that provides nearly 100% throughput for several admissible traffic patterns, including uniform and unbalanced traffic, using one-cell crosspoint buffers. The presented scheme uses adaptable-size frames, so that the frame size adapts to the traffic pattern.     

Fair-efficient call admission control policies for broadbandnetworks-a game theoretic framework

A fundamental problem in connection oriented multiservice networks (ATM and STM) is finding the optimal policy for call acceptance. One seeks an admission control policy that efficiently utilizes network resources while at the same time being fair to the various call classes being supported. The theory of cooperative games provides a natural and precise framework for formulating such multicriterion problems as well as solution concepts. The authors describe how this framework can be used for analysis and synthesis of call admission strategies in broadband networks. In particular they investigate the Nash (1950), Raiffa-Kalai-Smorodinsky (Raiffa, 1953; Kalai and Smorodinsky, 1975), and modified Thomson (Cao, 1982) arbitration solutions from game theory. The performance of all solutions is evaluated by applying the value iteration algorithm from Markov decision theory. The approach is illustrated on a one-link network example for which the exact solutions can be achieved. The results indicate that the arbitration schemes from game theory provide some attractive features especially when compared to traditional control objectives: blocking equalization and traffic maximization. The authors also compare the optimal solutions with some simplified policies belonging to four different classes: complete sharing, coordinate convex, trunk reservation, and dynamic trunk reservation. The comparison indicates that in many cases, the trunk reservation and dynamic trunk reservation policies can provide fair, efficient solutions, close to the optimal ones     

Binomial coding in distributed arbitration systems

A method for coding arbitration numbers in distributed arbitration schemes as used in Futurebus is proposed. The method is based on minimising the number of level changes in the arbitration process and allows one to reduce the arbitration time considerably. An algorithm for the construction of optimal codes for specified arbitration delay and number of arbitration lines is given.<>     

Comments on "An Efficient SS/TDMA Time Slot Assignment Algorithm"

The time slot assignment algorithm presented in the above paper needs certain improvements for it to be an efficient one. In this correspondence, the necessary improvements are incorporated and an improved SS/TDMA time slot assignment algorithm is presented. The new algorithm is compared to the old one and the computer simulation exhibits a better performance of the present algorithm.