高性能路由器中交换机构的设计与实现

宽带 IP路由器是骨干网互连的重要设备 ,其交换机构决定了路由器的吞吐量和处理速度 .本文论述了交换容量为 6 4 G× 6 4 G的核心路由器中交换机构的设计与实现 ,介绍了交换板 ,高速串型背板的设计以及 IP包调度和排队原则 ,最后给出了核心路由器的实际测试结果 .另外 ,该交换结构还具有良好的可扩展性     

多速率环境下AODV协议的改进

分析AODV协议在多速率环境下的不足,提出一种改进的协议AODV-HC.AODV-HC采用传输容量作为判断路径优劣的标准,通过链路单向稳定性和链路传输能力的度量,构建路径传输容量度量体系.在路径选择上将每条链路的稳定性和链路可承载的容量纳入考虑因素,能有效解决多速率环境下多跳低速链路带来的吞吐量限制.通过对AODV协议的路由请求信息和路由表的扩充以及对路由发现和路由回复过程的改进来实现AODV-HC协议.仿真实验表明基于传输容量度量的AODV-HC协议在节点高密度分布时能够提高网络的饱和吞吐量和分组交付率,降低平均分组传输时延.     

一种排队延迟感知的LTE调度机制

长期演进(LTE)系统在分组交换域内承载语音业务,但对延迟和丢包敏感的语音业务服务质量较难得到保证。为此,提出一种排队延迟感知的语音分组调度机制,根据队列长度、信道条件、排队延迟以及业务最大允许延迟来确定用户调度优先级,从而实现用户资源的合理分配。理论分析和仿真结果表明,与VSM调度机制相比,该调度机制在确保时延和系统吞吐量满足要求的前提下,能有效地利用网络资源,降低丢包率,提高用户公平性。     

联合车速–队列感知的路边单元分组调度随机优化

路边单元(RSU)是车联网中为其无线覆盖范围内过往车辆提供信息服务的基础设施,路边单元间的分组传输可通过移动车辆"存储–载带–转发"的方式进行,其传输过程中分组的端到端时延由源RSU缓存中的排队时延与车辆载带过程的传播时延两部分组成.为使RSU间分组传输过程中平均端到端时延最小化,本文提出一种联合车速–队列感知的路边单元分组调度随机优化方法,该方法根据源RSU缓存队列长度和经过源RSU覆盖范围的车辆速度状态作分组调度决策.通过马尔科夫决策(MDP)框架对分组传输过程中的平均排队时延和平均传播时延进行分析,建立一个非线性平均端到端时延最小化问题并求解.仿真结果表明,所提出的RSU分组调度随机优化方法可以显著降低RSU间分组传输过程中的平均端到端时延,并提高系统中分组传输的吞吐量.     

基于寄存器插入环的环形交换结构

弹性分组环是（RPR）是基于分组业务优化的城域网络体系结构,其环形结构属于寄存器插入环。寄存器插入环同时具有时分复用和空分复用的特点,而且环形结构的调度简单,很适合作为交换结构使用。本文将寄存器插入环结构用于交换结构。以排队论为工具对环形交换结构进行建模,分析环形交换结构的性能。结果表明寄存器插入环结构是一种适合高速分组交换的结构。     

WSN中基于中继选择的DH-MSMR-CARQ时延与吞吐量分析

为提高无线传感器网络（WSN）的时延和吞吐量性能,提出了一种两跳多源多中继协同自动重传请求（DH-MSMR-CARQ）协议。建立最大比合并（MRC）下两种不同中继选择的DH-MSMR-CARQ协议Markov链模型,分别给出状态空间。基于截短,由各自的平均分组差错率和状态转移概率矩阵推导协议的平均传输时延和吞吐量解析表达式。数值模拟结果表明,源节点数、分组长度及最佳中继节点到目的节点的分组差错率是影响平均传输时延的关键因素,采用第一种中继选择方式具有更高的吞吐量。另外,在非极端恶劣信道环境下（源节点到中继节点的分组差错率小于0.8）,DH-MSMR-CARQ协议比可直达的SSSR-CARQ、MSSR-CARQ和MSMR-CARQ协议具有更高的吞吐量。     

千兆以太网交换的设计与测试验证

为提高嵌入式系统中多处理器节点间大数据量、高速率以太网通信能力,提出了一种具有多种介质接口、大交换容量的千兆以太网交换设计,重点阐述了以太网交换的总体架构方案设计、硬件电路设计,包括以太网交换核心电路设计、交换配置电路设计、监控电路设计等。针对千兆以太网交换性能的测试验证,提出了利用蛇形打流测试吞吐量和以太网口信号一致性的测试方法。     

支持多优先级分组交换调度算法研究及其调度器设计

输入缓存交换结构的特点是缓存器和交换结构的运行速率与端口速率相等、实现容易,但存在队头阻塞。如果采用虚拟输出排队方法和适当的分组调度算法可予以消除,使吞吐率达到100%。文章首先研究讨论了并行迭代匹配算法,滑动迭代匹配调度算法的基本原理、迭代仲裁步骤及其硬件实现;对高速分组交换调度算法的性能进行了分析比较。然后给出了在高速输入队列交换机中实现多优先级调度算法的调度器设计与实现方案。经设计实现证明高速分组交换调度算法不仅硬件实现简单,而且具有良好的特性。     

在CICQ交换结构下实现分布式的输入排队DRR分组公平调度

传统的基于crossbar的输入排队交换结构在提供良好的QoS方面存在很大的不足,而CICQ(combined input and crosspoint buffered queuing)交换结构与传统的交换结构比,不但能在各种输入流下提供接近输出排队的吞吐率,而且能提供良好的QoS支持。基于CICQ结构,提出了在输入排队条件下实现基于流的分布式DRR分组公平调度算法的方案,并通过仿真验证了这一方案的有效性。     

一种支持变长分组的CIOQ交换结构

在分析了组合输入输出排队结构的基础上,对传统CIOQ(Combined Input—Output Queued)的输出队列进行扩展和在内部交换结构中采用并行传送的方式,实现了交换调度的分布式操作和内部无加速的CIOQ交换;又通过将输出队列的状态信息反压到输入端和在输出端采取基于整包调度的算法,实现了对变长分组的交换,减小了定长信元交换中分组切割和重组的开销。     

Synchronous versus asynchronous operation of a packet switch with combined input and output queueing

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.     

On priority queues with priority jumps

In this paper, we investigate a simplified head-of-the-line with priority jumps (HOL-PJ) scheduling discipline. Therefore, we consider a discrete-time single-server queueing system with two priority queues of infinite capacity and with a newly introduced HOL-PJ priority scheme. We derive expressions for the probability generating function of the system contents and the packet delay. Some performance measures (such as mean and variance) of these quantities are derived and are used to illustrate the impact and significance of the HOL-PJ priority scheduling discipline in an output queueing switch. We compare this dynamic priority scheduling discipline with a first-in, first-out (FIFO) scheduling and a static priority scheduling (HOL) and we investigate the influence of the different parameters of the simplified HOL-PJ scheduling discipline.     

Port partitioning and dynamic queueing for IP forwarding

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.     

On the speedup required for combined input- and output-queued switching

Architectures based on a non-blocking fabric, such as a crosspoint switch, are attractive for use in high-speed LAN switches, IP routers, and ATM switches. When operating at the highest speed, memory bandwidth limitations dictate that queues be placed at the input of the switch. But it is well known that input-queueing can lead to low throughput, and does not allow the control of latency through the switch. This is in contrast to output-queueing which maximizes throughput and permits the accurate control of packet latency through scheduling. We ask the question: Can a switch with combined input and output queueing be designed to behave identically to an output-queued switch? In this paper, we prove that if the switch uses virtual output queueing and has an internal speedup of just four, it is possible for it to behave identically to an output-queued switch, regardless of the nature of the arriving traffic. Our proof is based on a novel scheduling algorithm, called Most Urgent Cell First. We find that with a speedup of four the most urgent cell first algorithm (or MUCFA) enables perfect emulation of a FIFO output-queued switch, i.e. one in which packets depart in the same order that they arrived. We extend this result to show that with a small modification, the MUCFA algorithm enables perfect emulation of a variety of output scheduling policies, including strict priorities and weighted fair-queueing. This result makes possible switches that perform as if they were output-queued, yet use memories that run more slowly.     

Analysis of transmission delay for a structured-priority packet-switching system

We consider a priority-based packet-switching system with three phases of the packet transmission time. Each packet belongs to one of several priority classes, and the packets of each class arrive at a switch in a Poisson process. The switch transmits queued packets on a priority basis with three phases of preemption mechanism. Namely, the transmission time of each packet consists of a preemptive-repeat part for the header, a preemptive-resume part for the information field, and a nonpreemptive part for the trailer. By an exact analysis of the associated queueing model, we obtain the Laplace-Stieltjes transform of the distribution function for the delay, i.e., the time from arrival to transmission completion, of a packet for each class. We derive a set of equations that calculates the mean response time for each class recursively. Based on this result, we plot the numerical values of the mean response times for several parameter settings. The probability generating function and the mean for the number of packets of each class present in the system at an arbitrary time are also given.     

Proposed high speed packet switch for broadband integrated networks

The design of a high speed, broadband packet switch with two priority levels for application in integrated voice/data networks is presented. The packet switch can efficiently cope with 128 byte packets converging on it from eight 140 Mbit/s dynamic time division multiplexed fibre optic links. The packet switch throughput varies with the load and traffic composition, and the delay experienced by voice and data packets is within 300 μs and 3 ms, respectively. The design is implemented by task-sharing in a multi-processor configuration. The design of the packet switch, including its subsystems, is detailed here.     

Load-balanced three-stage switch

A load-balanced two-stage switch is scalable and can provide close to 100% throughput. Its major problem is that packets can be mis-sequenced when they arrive at outputs. In a recent work, the packet mis-sequencing problem is elegantly solved by a feedback-based switch architecture. In this paper, we extend the feedback-based switch from two-stage to three-stage for further cutting down average packet delay while still ensuring in-order packet delivery and close to 100% throughput. The basic idea is to use the third stage switch to map heavy flows to experience less middle-stage delays. To identity heavy flows, an adaptive traffic estimation algorithm is proposed. To ensure max-min fairness in bandwidth allocation under any inadmissible traffic pattern, an efficient fair scheduler is devised.     

Analytical evaluation of average delay and maximum stable throughput along a typical two-way street for vehicular ad hoc networks in sparse situations

Intermittent connectivity is an intrinsic feature of vehicular ad hoc networks (VANETs) in sparse situations. This type of network is in fact an example of delay and disruption tolerant networks (DTNs). In this paper, we focus on a typical two-way street and analytically evaluate the maximum stable throughput and the average delay for packet forwarding along the street. To this end, we map the mobility patterns of the vehicles with different speeds onto suitable parameters of a BCMP queueing network and derive the location density of vehicles. Then, we employ another queueing network in order to model opportunistic multi-hop packet forwarding along the street with respect to the specifications of MAC and routing schemes. We propose a two-mode MAC scheme suitable for DTNs with predictable mobility patterns. We also consider the effect of vehicles’ velocities and opportunistic relaying for routing schemes. In our analysis, we evaluate the average delay and the maximum stable throughput for the proposed MAC and routing schemes. In the last part of the paper, we show the efficiency of the proposed analytical approach by some numerical results and confirm our analysis by simulation.     

Analysis of an FDDI network supporting stations with single-packet buffers

We present exact analysis of a nonsymmetric multiple-priority token ring network with single packet buffers under a timedtoken protocol, similar to that employed for medium access control of the Fiber Distributed Data Interface (FDDI) network. The single-packet buffer model is employed for describing the queueing operation characterizing typical user terminals. An iterative procedure is used to compute the limiting state distribution of the embedded Markov chains representing the system state process. We obtain the distributions of the token rotation time, the normalized throughput, and the mean packet waiting time. By using a counting process representing the numbers of transmitted and deferred packets in a token rotation cycle, we present a simplified analysis of a symmetric network containing a large number of stations. We illustrate the application of the analytic approach through numerical examples representing FDDI network systems operating under various traffic loading conditions.     

基于无线自组网络分时发送协议的路由汇聚容量

对于无线自组网而言,由于网络拓扑与路由选择的随机性,容量的分析显得尤为复杂。研究了能量约束对无线自组网容量性能的影响。该网络具有路由汇聚功能,且节点的发送过程基于分时竞争发送协议。在假设能量缓存中的能量值足够大时,节点就能发送数据的前提下,提出了一种基于闭合排队网络的容量分析模型。该模型同时考虑了数据细节、能量缓存以及随机接入协议。然后研究了能量约束对随机接入协议设计参数的影响,以优化网络性能。最后分析了能量约束对最大稳定容量、稳定域以及分组丢弃率的影响。仿真结果验证了所提分析模型的准确性。