Optimization of the Scheduler for the Non-Blocking High-Capacity Router

The sequential greedy scheduling (SGS) is a scalable maximal matching algorithm that provides non-blocking in an Internet router with input buffers and a cross-bar. In this paper, we will present the FPGA design of the SGS scheduler. We have optimized scheduler components, and we will prove their correct functioning. The scheduler optimization significantly reduces the worst-case packet delay through the router.     

Router plugins: a software architecture for next-generation routers

Present-day Internet protocol routers typically employ monolithic operating systems that are not easily upgradable and extensible. With the rapid rate of protocol development it is becoming increasingly important to dynamically upgrade router software in an incremental fashion. We have designed and implemented a high-performance, modular, extended services router software architecture in the Net BSD operating system kernel. This architecture allows code modules, called plugins, to be dynamically added and configured at run time. One of the novel features of our design is the ability to bind different plugins to individual flows; this allows for distinct plugin implementations to seamlessly coexist in the same runtime environment. We achieve high performance through a carefully designed modular architecture, an innovative packet classification algorithm that is highly efficient, and by caching that exploits the flow-like characteristics of Internet traffic. Compared to a monolithic best effort kernel, our implementation requires an average increase in packet processing overhead of only 8%, or 600 cycles per packet when running on an Intel Pentium Pro at 233 MHz. By shortcutting the forward loop based on the per-flow state we establish, we can forward packets up to three times faster than the best effort kernel     

Optimal Burst Scheduling in Optical Burst Switched Networks

Optical burst switching (OBS) is an emerging technology that allows variable size data bursts to be transported directly over dense wavelength division multiplexing links. In order to make OBS a viable solution, the burst-scheduling algorithms need to be able to utilize the available wavelengths efficiently, while being able to operate fast enough to keep up with the burst incoming rate. For example, for a 16-port OBS router with 64 wavelengths per link, each operating at 10 Gb/s, we need to process one burst request every 78 ns in order to support an average burst length of 100 kB. When implemented in hardware, the well-known horizon scheduler has O(1) runtime for a practical number of wavelengths. Unfortunately, horizon scheduling cannot utilize the voids created by previously scheduled bursts, resulting in low bandwidth utilization. To date, minimum starting void is the fastest scheduling algorithm that can schedule wavelengths efficiently. However, while its complexity is O(log m), it requires 10 log m memory accesses to schedule a single burst. This means that it can take up to several microseconds for each burst request, which is still too slow to make it a practical solution for OBS deployment. In this paper, we propose an optimal burst scheduler using constant time burst resequencing (CTBR), which has O(1) runtime. The proposed CTBR scheduler is able to produce optimal burst schedules while having processing speed comparable to the horizon scheduler. The algorithm is well suited to high- performance hardware implementation.     

网络模拟中的路由器模型

文章通过对路由器体系结构和性能指标的分析,提出为网络模拟中的路由器建立模型的方法,为网络模拟网络总体设计提供了参考,给出了JuniperM160路由器和Cisco12008路由器在网络模拟中的模型实例。     

Impact of Redhat IPv6 router on heterogeneous host connections

Internet's popularity has been expanding on dramatic pace and the number of people getting connected to it multiplies regularly. With this high demand, the current Internet Protocol (IPv4) has reached its limits. The next generation Internet Protocol version6 (IPv6) has been incorporated into various operating systems. The motivation behind this work is how well IPv6 co‐operates with various operating systems. The performance of the IP stack, together with the behaviour of the OS greatly affects the efficiency of network applications built on top of it. The acceptance of IPv6 implementations on various operating systems heavily relies on the end‐user performance. In this paper, we propose to analyse these various IPv6 implementations for its host and router‐level supports. In this paper, we investigate the impact of Redhat‐based IPv6 router on IPv6 stacks of three different operating systems namely, Windows2003, Redhat Linux 9.0 (Redhat9.0) and FreeBSD4.9. Copyright © 2006 John Wiley & Sons, Ltd.     

片上网络路由器的交叉开关设计实现

交叉开关是片上网络路由器的关键部分。交叉开关的设计可以采用三态触发器或多路复用器实现。本文针对几种不同形式的交叉开关实现方案,比较了其面积和功耗的开销,同时设计了基于iSLIP算法的交叉开关调度机制。通过基本逻辑门搭建的多路复用器实现的交叉开关相比于采用三态门实现的交叉开关,在功耗、面积上有较大优势。采用iSLIP算法实现的片上网络交叉开关,具有最高的工作频率上限。     

BGP parallel computing model based on the iteration tree

Scalable architecture has become the main developing direction of core router in future Internet, and the major technical challenge faced by scalable router is the parallel computing technology in its control plane. This paper conducts an in-depth study of the parallel computing model of border gateway protocol (BGP) in scalable router. Based on hierarchical iteration tree, this paper gives a reasonable improvement of arborous BGP division scheme, which has the advantages of balanced task division and low communication cost. Detailed performance analysis is done and is compared with neighbor-based division scheme considering balance in the initial partition. At last, three implementations of the two schemes are compared and evaluated by using actual routing table data gained from Route Views. The conclusion is that, the developed division scheme based on iterative tree has a comprehensive advantage, which can provide workable models and methods to the expansion of control plane in the future scalable router system.     

Deferrable load scheduling under imperfect data communication channel

In smart grid, the real‐time pricing is implemented to motivate power consumers to change their consumption profile dynamically. With the real‐time pricing, a deferrable load can be scheduled by its scheduler optimally so that the power consumption cost will be minimized. However, when the data communication in smart grid suffers from interference, congestion, malfunction in devices, or even cyber attack, it is possible that the power price information cannot be transmitted successfully to the scheduler. As a result, the scheduling performance will be negatively affected by the suboptimal decision‐making because of incomplete power price information. To overcome this problem, a partially observable Markov decision process based deferrable load scheduling algorithm is proposed. Besides, the implementation of a standby alternative channel with the purpose to improve the reliability of the data communication in smart grid is also discussed in this paper. The numerical results show that the proposed partially observable Markov decision process based algorithm and the implementation of standby channel can effectively improve the scheduling performance when the scheduler lacks actual price information. Copyright © 2014 John Wiley & Sons, Ltd.     

A Multichannel Scheduler for High-Speed Wireless Backhaul Links with Packet Concatenation

Capacity has been an important issue for many wireless backhaul networks. Both the multihop nature and the large per packet channel access overhead can lead to its low channel efficiency. The problem may get even worse when there are many applications transmitting packets with small data payloads, e.g., Voice over Internet Protocol (VoIP). Previously, the use of multiple parallel channels and employing packet concatenation were treated as separate solutions to these problems. However, there is no available work on the integrated design and performance analysis of a complete scheduler architecture combining these two schemes. In this paper, we propose a scheduler that concatenates small packets into large frames and sends them through multiple parallel channels with an intelligent channel selection algorithm between neighboring nodes. Besides the expected capacity improvements, we also derive delay bounds for this scheduler. Based on the delay bound formula, call admission control (CAC) of a broad range of scheduling algorithms can be obtained. We demonstrate the significant capacity and resequencing delay improvements of this novel design with a voice-data traffic mixing example, via both numerical and simulation results. It is shown that the proposed packet concatenation and channel selection algorithms greatly outperform the round-robin scheduler in a multihop scenario.     

一种优化可配置的AES密码算法硬件实现

AES加密算法是下一代的常规加密算法，其将被广泛应用在政府部门和商业领域。本文首先介绍了AES加密算法．然后分析了其硬件实现的要点和难点，最后在Xilinx的FPGA VirtexII XC2V3000-4上对AES密码算法进行了实现和验证。本方案采用一种优化的非流水线加密解密数据路径；同时提出了一种新的可配置的动态密钥调度结构，使得该设计支持128、192和256比特的密钥；而且该设计可以配置AES的四种工作模式。实验的结果表明该设计比其它的设计具有更高的性能。     

Two-dimensional round-robin schedulers for packet switches withmultiple input queues

Presents a new scheduler, the two-dimensional round-robin (2DRR) scheduler, that provides high throughput and fair access in a packet switch that uses multiple input queues. We consider an architecture in which each input port maintains a separate queue for each output. In an N×N switch, our scheduler determines which of the queues in the total of N² input queues are served during each time slot. We demonstrate the fairness properties of the 2DRR scheduler and compare its performance with that of the input and output queueing configurations, showing that our scheme achieves the same saturation throughput as output queueing. The 2DRR scheduler can be implemented using simple logic components, thereby allowing a very high-speed implementation     

High-Performance Hybrid-Switching Optical Router for IP over WDM Integration

Because pure electrical routers with their bandwidth limitations can hardly keep up with the tremendous traffic growth in the Internet, optical routers based on various optical switching techniques including optical wavelength switching (OWS), optical burst switching (OBS), and optical packet switching (OPS) have been suggested to cope with this problem. However, because OBS and OPS are both in their early experimental phase and OWS only provides coarse granularity switching, a hybrid-switching optical router with combined OWS and electrical packet switching is a necessity in order to accommodate the entire multi-granularity traffic with multi-service requirements in a cost-effective manner. Its coordination capability of optical circuit switching and electrical packet switching enables efficient/intelligent usage of network resources. In this paper, we first review research and developments of such IP routers employing optical switching/interconnection techniques and examine how these techniques can be used inside routers to scale node capacity and to improve optical Internet performance. We also present and study the performance of a terabit optical router with an optical-electrical hybrid-switching fabric. The node architecture is based on the idea of IP over WDM integration with Generalized Multi-Protocol Label Switching (GMPLS). The network-level performance evaluations show that the proposed hybrid-switching optical router is a cost-effective solution for building the next generation GMPLS-based multi-granularity optical Internet.     

Netpiler: detection of ineffective router configurations

Configuring a network is a tedious and error-prone task. In particular, configuring routing policies for a network is complex as it involves subtle dependencies in multiple routers across the network. Misconfigurations are common and certain misconfigurations can bring the Internet down. In 2005, a misconfigured router in AS 9121 blackholed traffic for tens of thousands of networks in the Internet. This paper describes NetPiler, a system that detects router misconfigurations. NetPiler consists of a routing policy configuration model and a misconfiguration detection algorithm. The model is applicable to routing policies configured on a single router as well as to network-wide configuration. Using the model, NetPiler detects configuration commands that do not influence the behavior of the network - we call these configurations ineffective commands. Although the ineffective commands could be benign, sometimes when the commands are mistakenly configured to be ineffective, they cause the network to misbehave deviating from the intended behavior. We have implemented NetPiler in approximately 128,000 lines of C++ code, and evaluated it on the configurations of four production networks. NetPiler discovers nearly a hundred ineffective commands. Some of these misconfigurations can result in loss of connectivity, access to protected networks, and financial implications by providing free transit services. We believe NetPiler can help networks to significantly reduce misconfigurations.     

分级调度算法在路由交换机上的应用

本文提出了一种两级的分级调度模型,着重研究其算法的具体实现,并分析算法在路由交换机中的应用。分级调度算法的引入,保证在现有Internet体系结构下、best-effort服务能很好地与有QoS要求的实时服务相结合,仿真实验证明该发级调度算法可行有效。     

MPLS-Linux体系结构及交换路由性能分析

本文详细介绍了MPLS-Linux的体系结构、核心数据结构、标签交换过程和QoS运行等实现技术，通过对MPLS-Linux组成的交换路由系统进行性能测试和分析，发现：在链路轻载或预留带宽的情况下，交换路由系统对数据流的服务质量优于传统路由系统；只有综合应用策略路由、数据报分类调度和标签交换才能实现Internet环境下对端到端服务质量的控制。     

IP switching and gigabit routers

To cope with the growth in the Internet and corporate IP networks, we require IP routers capable of much higher performance than is possible with existing architectures. This article examines two approaches to the design of a high-performance router, the gigabit router and the IP switch, and then provides some detail on the implementation of an IP switch and the protocols associated with IP switching     

基于可编程路由技术的 MPLS 单标签分流传输算法

为提高数据传输的QoS(服务质量),运用MPLS(多协议标签交换)、并发多路径和可编程路由技术,提出了multipathMPLS算法,实现了单个转发等价类标签进行多个标签交换路径并行分流的传输算法。NS2仿真实验证明,该算法具备MPLS高速转发,并发多路径较高吞吐量,可编程路由器灵活部署等优点。     

Hardware/Software Co-Design of Run-Time Schedulers for Real-Time Systems

Wepresent the Serra Run-Time Scheduler Synthesis and AnalysisTool which automatically generates a run-time scheduler froma heterogeneous system-level specification in both Verilog HDLand C. Part of the run-time scheduler is implemented in hardware,which allows the scheduler to be predictable in being able tomeet hard real-time constraints, while part is implemented insoftware, thus supporting features typical of software schedulers. Serra's real-time analysis generates a priority assignment forthe software tasks in the mixed hardware-software system. Thetasks in hardware and software have precedence constraints, resourceconstraints, relative timing constraints, and a rate constraint.A heuristic scheduling algorithm assigns the static prioritiessuch that a hard real-time rate constraint can be predictablymet. Serra supports the specification of critical regions insoftware, thus providing the same functionality as semaphores.We describe the task control/data-flow extraction,synthesis of the control portion of the run-time scheduler inhardware, real-time analysis and priority scheduler template.We also show how our approach fits into an overall tool flowand target architecture. Finally, we conclude with a sample applicationof the novel run-time scheduler synthesis and analysis tool toa robotics design example.     

Integrated services architecture: the next‐generation internet

The integrated services architecture is a response to the growing variety and volume of traffic experienced in the Internet and intranets. It provides a framework for the development of protocols such as RSVP and RTP, to handle multimedia/multicast traffic and provides guidance to router vendors on the development of efficient techniques for handling a varied load. ISA is already influencing router and Internet design, and will have a greater impact over the next few years. Copyright © 1999 John Wiley & Sons, Ltd.     

Design and implementation of Single-Buffered routers

A Single-Buffered （SB） router is a router where only one stage of shared buffering is sandwiched between two interconnects in comparison of a Combined Input and Output Queued （CIOQ） router where a central switch fabric is sandwiched between two stages of buffering. The notion of SB routers was firstly proposed by the High-Performance Networking Group （HPNG） of Stanford University, along with two promising designs of SB routers： one of which was Parallel Shared Memory （PSM） router and the other was Distributed Shared Memory （DSM） router. Admittedly, the work of HPNG deserved full credit, but all results presented by them appeared to relay on a Centralized Memory Management Algorithm （CMMA） which was essentially impractical because of the high processing and communication complexity. This paper attempts to make a scalable high-speed SB router completely practical by introducing a fully distributed architecture for managing the shared memory of SB routers. The resulting SB router is called as a Virtual Output and Input Queued （VOIQ） router. Furthermore, the scheme of VOIQ routers can not only eliminate the need for the CMMA scheduler, thus allowing a fully distributed implementation with low processing and commu- nication complexity, but also provide QoS guarantees and efficiently support variable-length packets in this paper. In particular, the results of performance testing and the hardware implementation of our VOIQ-based router （NDSC~ SR1880-TTM series） are illustrated at the end of this paper. The proposal of this paper is the first distributed scheme of how to design and implement SB routers publicized till now.