共查询到19条相似文献,搜索用时 203 毫秒
1.
为提高高速通信网络的通信效率,针对VOQ交换机,提出在交换机的各个输出端口中进行分布式通信调度(DSA)的策略。DSA算法可直接支持变长数据包通信调度,克服了传统信元交换只能调度定长数据包的缺点,降低了交换机的实现复杂度。仿真结果表明:在各种流量下,DSA算法都比信元调度算法具有更好的调度性能。 相似文献
2.
用多FIFO输入缓冲队列消除HOL阻塞 总被引:1,自引:0,他引:1
鄂大伟 《计算机应用与软件》2001,18(2):17-24,41
对于输入端口具有单输入FIFO(先入先出)队列的输入缓冲信元交换机(如ATM),影响交换吞吐率的主要因素是信头阻塞(HOL)。本文分析了在单FIFO队列情况下的信元阻塞的原因及解决办法,给出了输入端口具有多FIFO队列在信元交换结构,描述了基于N-FIFO输入缓冲的排队策略和迭代匹配算法,并对它们的性能进行了分析。 相似文献
3.
鄂大伟 《计算机工程与应用》2001,37(11):79-82,95
对于输入端口具有单FIFO(先入先出)队列的输入缓冲交换机(如ATM),影响交换吞吐率的主要因素是信头阻塞(HOL)。文章给出了输入端口具有多FIFOl队列的信元交换机结构,阐述了PIM、iSLIP、iLRU、iLQF等多种迭代匹配算法,并对它们的性能进行了分析和比较。 相似文献
4.
5.
针对基于虚拟输出排队的输入队列交换机应用于控制网络所存在的诸多困难,提出了一种新的输入队列交换机结构,并根据新的结构设计了一种基于记录矩阵和需求矩阵的信元传输川页序控制方案,以解决交换机中存在的信元行为及时延的不确定性问题。交换机采用两级调度机制,链接调度提供分级服务,交换调度实现端口匹配,以适应控制网络的流量特征。 相似文献
6.
7.
匈牙利算法在输入排队调度仿真中的应用研究 总被引:2,自引:0,他引:2
匈牙利算法是图论中完成二分图匹配的经典算法之一。输入排队的Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量为目的。因而在调度算法理论研究中应用了二分图最大匹配的Maximum Size Matching(MSM)和Maximum Weight Matching(MWM)算法成为各种调度算法性能的评价标准。文中介绍了匈牙利算法在输入排队调度算法仿真中的应用,并且得出相应典型算法的性能仿真曲线,从而为进一步研究调度算法打下理论基础。 相似文献
8.
使用Ford-Fulkerson算法研究输入排队调度 总被引:1,自引:0,他引:1
法拉 《计算机工程与应用》2005,41(9):79-81,110
Ford-Fulkerson算法是图论中求解网络最大流的经典算法之一。输入排队Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量。因而在调度算法理论研究中把应用了二部图最大匹配的MaximumSizeMatching(MSM)和MaximumWeightMatching(MWM)算法作为目前各种调度算法性能评价标准。论文介绍了如何使用Ford-Fulkerson算法求解二部图的最大匹配,并且应用算法于输入排队调度算法仿真中,得出对应典型算法MSM和MWM的性能仿真曲线,从而为进一步研究调度算法打下理论基础。 相似文献
9.
Internet核心路由器多采用输入缓冲交换矩阵,研究输入缓冲队列的调度算法十分重要。加权调度算法具有较高的性能,但由于硬件实现困难,因此很少得到应用。提出了一种简单的加权高度算法L2QF,该算法采用串行轮询的思想,根据虚拟输出队列的长度依次为每个输入端口选择一个输出端口。L2QF算法具有LQF算法的性能,但复杂性仅为o(N^2)。由于L2QF是所有LQF算法中复杂性最低的算法,而且以叠代的方式的执行,因此易于硬件实现。 相似文献
10.
缓冲交叉开关交换结构多播调度算法研究 总被引:1,自引:0,他引:1
高性能核心交换设备多播调度受到越来越多的关注·交叉开关结构下的多播调度方案或者性能较差,或者过于复杂,难于应用在高速交换场合·为此,提出一种面向多播的多输入队列缓冲交叉开关体系结构·将多播调度分解为信元分派、输入调度、输出调度3个可分布式并行执行的子问题,并设计了相应的调度算法,降低了算法复杂性·实验结果表明,交叉点缓冲区容量与输入队列数量对多播性能都具有很大的影响·在突发流量到达下,与单多播输入队列的体系结构相比,无论是采用O(1)复杂度的HA-RR-RR还是复杂度更高的调度算法,均能显著提高系统吞吐性能· 相似文献
11.
通过研究4种经典的CICQ调度算法,提出一种高性能的LQF_DRR交换调度算法。该算法在输入端采用最长队列优先调度策略,在输出端采用DRR调度机制,通过输入端与输出端的相互配合,优先服务异常队列,以减小交换结构输入端长队列对算法性能的影响。仿真结果证明该算法在各种流量下都有良好的时延性能和稳定性。 相似文献
12.
iSLIP调度算法研究及其实现 总被引:4,自引:0,他引:4
目前,为提高交换系统吞吐率,设计开发高性能网络交换机或路由器内部交换结构的技术已趋成熟.但易于在硬件中实现的、高效的队列调度算法仍然是一项值得研究的重要技术.文章首先讨论了对于输入缓冲采用FIF0队列交换系统,其吞吐率主要受HOL队首阻塞的影响.然后研究了iSLIP调度算法的基本原理、迭代仲裁步骤及它在硬件中的实现.针对硬件交换转发判决这一关键问题,给出了在输入队列交换机中采用虚拟输出队列的交换结构和多优先级调度算法的硬件实现方案.最后,对isLIP算法的性能进行了分析比较,证明isLIP算法的实现方案不仅实现简单,而且具有良好的特性. 相似文献
13.
14.
Synchronous versus asynchronous operation of a packet switch with combined input and output queueing
Ilias Iliadis 《Performance Evaluation》1992,16(1-3):241-250
A single-stage non-blocking N × N packet switch with combined input and output queueing is considere. The limited queueing at the output ports partially resolves output port contention. Overflow at the output queues is prevented by employment of a backpressure mechanism and additional queueing at the input ports. This paper investigates the performance of the switch under two different modes of operation: asynchronous and synchronous or slotted. For the purpose of comparison a switch model is developed. Assuming Poisson packet arrivals, several performance measures are obtained analytically. These include the distribution of the delay through the switch, the input queue length distribution, packet losses at the inputs in the case of finite input queues, and the maximum switch throughput. The results obtained demonstrate a slight performance advantage of asynchronous over synchronous operation. However, the maximum switch throughput is the same for both modes of operation. 相似文献
15.
《Computer Communications》2001,24(15-16):1607-1617
Performance of an input-buffered ATM switch is limited by the head-of-line (HOL) blocking problem. HOL blocking is even more pronounced in multicast switch where cells compete for multiple outputs simultaneously. Previous studies in input-buffered unicast switch have shown that HOL blocking can only be eliminated by using per-output queuing and sophisticated scheduling methods, such as the maximal weight matching (MWM) or the parallel iterative matching (PIM) methods. The MWM or PIM types of scheduling algorithm cannot be applied to multicast switch because of the high computation complexity. In this paper, we present a reservation based scheduling algorithm, which employs per-VC queuing for multicast connections and per-output queuing for unicast connections. Instead of the input ports sending a huge amount of state information to the output ports for processing, we circulate reservation vectors amongst the input ports. Each input port will then make reservation based on its local state and the availability of the output ports. The scheduling is done on a frame by frame basis. While the input ports are transmitting cells according to the schedule of the current frame, the next frame schedule is computed. Simulations reveal that our method substantially outperforms the methods that employ FIFO queuing discipline. 相似文献
16.
Designing and implementing a fast crossbar scheduler 总被引:1,自引:0,他引:1
Crossbar switches frequently function as the internal switching fabric of high performance network switches and routers. However, for fairness and high utilization, a crossbar needs an intelligent, centralized scheduler. We describe the design and implementation of a scheduling algorithm for configuring crossbars in input queued switches that support virtual output queues and multiple priority levels of unicast and multicast traffic. We carried out this design for Stanford University's Tiny Tera prototype, a fast, label-swapping packet switch. Its scheduler, designed to configure a crossbar once every 51 ns, implements the ESLIP scheduling algorithm, which consists of multiple round-robin arbiters 相似文献
17.
Kenji Yoshigoe 《Computer Communications》2009,32(4):740-749
A combined input and crosspoint queued (CICQ) switch is receiving significant attention to be the next generation high speed packet switch for its scalability; however, a multi-cabinet implementation of a combined input and crosspoint queued (CICQ) switch unavoidably introduces a large round-trip time (RTT) latency between the line cards and switch fabric, resulting a large crosspoint (CP) buffer requirement. In this paper, virtual crosspoint queues (VCQs) that significantly reduces the CP buffer requirement of the CICQ switch is investigated. The VCQs unit resides inside the switch fabric, is dynamically shared among virtual output queues (VOQ) from the same source port, and is operated at the line rate, making the implementation practical. A threshold-based exhaustive round-robin (T-ERR) arbitration is employed to reduce buffer hogging at VCQ. The T-ERR at VCQ and CP arbiters serves packets residing in a longer queue more frequently than packet residing in a shorter queue. Consequently, the T-ERR, drastically increases the throughput of the CICQ switch with small CP buffers. A multi-cabinet implementation of CICQ switch do not support multicasting traffic well since a combination of small CP buffer in the switch fabric and a large RTT latency between the line cards and switch fabric results in non-work conservation of the intra-switch link. Deployment of multicast FIFO buffer between the input buffer and CP buffer shows a promise. With its ability to achieve high throughput independent of RTT and switch port size, the integration of the VCQ architecture and T-ERR scheduler to the CICQ switch is ideal for supporting ever-increasing Internet traffic that requires higher data rate, larger switch size, and efficient multicasting. 相似文献
18.
《Computers & Operations Research》2002,29(9):1157-1172
With the increase of internet protocol (IP) packets the performance of routers became an important issue in internet/working. In this paper we examine the matching algorithm in gigabit router which has input queue with virtual output queueing. Dynamic queue scheduling is also proposed to reduce the packet delay and packet loss probability. Port partitioning is employed to reduce the computational burden of the scheduler in a switch which matches the input and output ports for fast packet switching. Each port is divided into two groups such that the matching algorithm is implemented within each pair of groups in parallel. The matching is performed by exchanging the pair of groups at every time slot. Two algorithms, maximal weight matching by port partitioning (MPP) and modified maximal weight matching by port partitioning (MMPP) are presented. In dynamic queue scheduling, a popup decision rule for each delay critical packet is made to reduce both the delay of the delay critical packet and the loss probability of loss critical packet. Computational results show that MMPP has the lowest delay and requires the least buffer size. The throughput is illustrated to be linear to the packet arrival rate, which can be achieved under highly efficient matching algorithm. The dynamic queue scheduling is illustrated to be highly effective when the occupancy of the input buffer is relatively high.Scope and purposeTo cope with the increasing internet traffic, it is necessary to improve the performance of routers. To accelerate the switching from input ports to output in the router partitioning of ports and dynamic queueing are proposed. Input and output ports are partitioned into two groups A/B and a/b, respectively. The matching for the packet switching is performed between group pairs (A, a) and (B, b) in parallel at one time slot and (A, b) and (B, a) at the next time slot. Dynamic queueing is proposed at each input port to reduce the packet delay and packet loss probability by employing the popup decision rule and applying it to each delay critical packet.The partitioning of ports is illustrated to be highly effective in view of delay, required buffer size and throughput. The dynamic queueing also demonstrates good performance when the traffic volume is high. 相似文献