Sharded Router: A novel on-chip router architecture employing bandwidth sharding and stealing

Packet-based networks-on-chip (NoC) are considered among the most viable candidates for the on-chip interconnection network of many-core chips. Unrelenting increases in the number of processing elements on a single chip die necessitate a scalable and efficient communication fabric. The resulting enlargement of the on-chip network size has been accompanied by an equivalent widening of the physical inter-router channels. However, the growing link bandwidth is not fully utilized, because the packet size is not always a multiple of the channel width. While slicing of the physical channel enhances link utilization, it incurs additional delay, because the number of flit per packet also increases. This paper proposes a novel router micro-architecture that employs fine-grained bandwidth “sharding” (i.e., partitioning) and stealing in order to mitigate the elevation in the zero-load latency caused by slicing. Consequently, the zero-load latency of the Sharded Router becomes identical with that of a conventional router, whereas its throughput is markedly improved by fully utilizing all available bandwidth. Detailed experiments using a full-system simulation framework indicate that the proposed router reduces the average network latency by up to 19% and the execution time of real multi-threaded workloads by up to 43%. Finally, hardware synthesis analysis verifies the modest area overhead of the Sharded Router over a conventional design.     

MediaWorm: a QoS capable router architecture for clusters

With the increasing use of clusters in real-time applications, it has become essential to design high-performance networks with quality-of-service (QoS) guarantees. We explore the feasibility of providing QoS in wormhole switched routers, which are widely used in designing scalable, high-performance cluster interconnects. In particular, we are interested in supporting multimedia video streams with CBR and VBR traffic, in addition to the conventional best-effort traffic. The proposed MediaWorm router uses a rate-based bandwidth allocation mechanism, called Fine-Grained VirtualClock (FGVC), to schedule network resources for different traffic classes. Our simulation results on an 8-port router indicate that it is possible to provide jitter-free delivery to VBR/CBR traffic up to an input load of 70-80 percent of link bandwidth and the presence of best-effort traffic has no adverse effect on real-time traffic. Although the MediaWorm router shows a slightly lower performance than a pipelined circuit switched (PCS) router, commercial success of wormhole switching, coupled with simpler and cheaper design, makes it an attractive alternative. Simulation of a (2/spl times/2) fat-mesh using this router shows performance comparable to that of a single switch and suggests that clusters designed with appropriate bandwidth balance between links can provide required performance for different types of traffic.     

区分服务网络基于测量的接纳控制方案的设计与应用

提出了一种分布式可扩展的接纳控制方案，其目的是为区分服务网络提供端到端服务质量（Quality of Services,QoS)保证，该方案主要由以下部分构成：（1）连接接纳控制协议，主要负责主机和网络节点以及网络节点和带宽代理之间的信息传送，实现对连接请求的串行操作；（2）位于网络核心节点的可用带宽估计算法；（3）位于网络边缘节点的接纳控制算法；给出了该方案在视频传输方面的应用实例；利用多种网络拓扑结构和QoS指标评价该方案的性能，实验结果表明该方案能准确地控制可接纳区域和提高网络资源的利用率。     

QoS-supported On-chip Communication for Multi-processors

We present a Quality of Service (QoS)-supported on-chip communication that increases the shared communication resources for multi-processor systems on chip. Time-critical embedded systems require tight guaranteed services in terms of throughput, latency etc. in order to comply to hard real-time constraints. Typically, guaranteed-service schemes require dedicated/reserved resources (i.e. links) for communication and thus suffer from low resource utilization. So improving the bandwidth utilization by using the unused bandwidth among the other competing transactions in a fair fashion is an important issue. To the best of our knowledge, we are presenting the first approach for on-chip communication that provides a high resource utilization under a transaction-specific, flexible communication scheme. It provides tight time-related guarantees through our bounded arbitration scheme considering the lower and the upper bounds for each type of transactions. We demonstrate its advantages by means of a complete MPEG4 video decoder case study analysis and achieve under certain constraints a bandwidth utilization of up to 100% and 97% on average with a guaranteed 100% bandwidth. Thus, we provide an on-chip communication scheme that provides high bandwidth utilization while providing tight guarantee. Large parts of this work have previously been published at the IEEE International Conference on Hardware/Software Codesign and System Synthesis (Codes+ISSS), 2006.     

分级统筹分配令牌参数的流量整形算法

在区分服务网络中，流量整形是提供QoS保证的一项重要的技术，通常用于规整用户系统向网络提交的数据流。提出了一个新的流量整形架构——分级统筹令牌参数分配（HHTPA）整形器，在边缘路由器上通过分级整形、统筹实时更新令牌桶参数，动态分配剩余带宽，达到对用户数据进行流量整形和提高带宽利用率的目的，使得为高优先级服务预留但未使用的带宽也可被低优先级的服务使用。     

A novel resource scheduling algorithm for QoS-aware services on the Internet

The popularity and availability of Internet connection has opened up the opportunity for network-centric collaborative work that was impossible a few years ago. Contending traffic flows in this collaborative scenario share different kinds of resources such as network links, buffers, and router CPU. The goal should hence be overall fairness in the allocation of multiple resources rather than a specific resource. In this paper, firstly, we present a novel QoS-aware resource scheduling algorithm called Weighted Composite Bandwidth and CPU Scheduler (WCBCS), which jointly allocates the fair share of the link bandwidth as well as processing resource to all competing flows. WCBCS also uses a simple and adaptive online prediction scheme for reliably estimating the processing times of the incoming data packets. Secondly, we present some analytical results, extensive NS-2 simulation work, and experimental results from our implementation on Intel IXP2400 network processor. The simulation and implementation results show that our low complexity scheduling algorithm can efficiently maximise the CPU and bandwidth utilisation while maintaining guaranteed Quality of Service (QoS) for each individual flow.     

A core stateless bandwidth broker architecture for scalable support of guaranteed services

We present a novel bandwidth broker architecture for scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture, core routers do not maintain any QoS reservation states, whether per-flow or aggregate. Instead, the QoS reservation states are stored at and managed by a bandwidth broker. There are several advantages of such a bandwidth broker architecture. Among others, it avoids the problem of inconsistent QoS states faced by the conventional hop-by-hop, distributed admission control approach. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a core stateless virtual time reference system developed recently. This virtual time reference system provides a unifying framework to characterize, in terms of their abilities to support delay guarantees, both the per-hop behaviors of core routers and the end-to-end properties of their concatenation. We focus on the design of efficient admission control algorithms under the proposed bandwidth broker architecture. We consider both per-flow end-to-end guaranteed delay services and class-based guaranteed delay services with flow aggregation. Using our bandwidth broker architecture, we demonstrate how admission control can be done on a per domain basis instead of on a "hop-by-hop" basis. Such an approach may significantly reduce the complexity of the admission control algorithms. In designing class-based admission control algorithms, we investigate the problem of dynamic flow aggregation in providing guaranteed delay services and devise a new apparatus to effectively circumvent this problem. We conduct detailed analyses to provide theoretical underpinning for our schemes as well as to establish their correctness. Simulations are also performed to demonstrate the efficacy of our schemes.     

Performance analysis of a QoS capable cluster interconnect

The growing use of clusters in diverse applications, many of which have real-time constraints, requires quality-of-service (QoS) support from the underlying cluster interconnect. All prior studies on QoS-aware cluster routers/networks have used simulation for performance evaluation. In this paper, we present an analytical model for a wormhole-switched router with QoS provisioning. In particular, the model captures message blocking due to wormhole switching in a pipelined router, and bandwidth sharing due to a rate-based scheduling mechanism, called VirtualClock. Then we extend the model to a hypercube-style cluster network. Average message latency for different traffic classes and deadline missing probability for real-time applications are computed using the model.

We evaluate a 16-port router and hypercubes of different dimensions with a mixed workload of real-time and best-effort (BE) traffic. Comparison with the simulation results shows that the single router and the network models are quite accurate in providing the performance estimates, and thus can be used as efficient design tools.     

Asynchronous spatial division multiplexing router

Asynchronous quasi-delay-insensitive (QDI) NoCs have several advantages over their clocked counterparts. Virtual channel (VC) is the most utilized flow control method in asynchronous routers but spatial division multiplexing (SDM) achieves better throughput performance for best-effort traffic than VC. A novel asynchronous SDM router architecture is presented. Area and latency models are provided to analyse the network performance of all router architectures including wormhole, virtual channel and SDM. Performance comparisons have been made with different configurations of payload size, communication distance, buffer size, port bandwidth, network size and number of VCs/virtual circuits. Compared with VC, SDM achieves higher throughput with lower area overhead.     

A QoS Management and Control Architecture for Intranet

With the appearance of application, such as VoIP and VOD, traditional best-effort service of network cant meet the needs of these applications. This paper proposes a QoS management and control architecture for Intranet, through which guaranteed services of network can be implemented in Intranet. In this architecture, there is a QoS control server, which is responsible for QoS control and management,while the router forwards packets according to the command from it.     

SoMR: A scalable distributed QoS multicast routing protocol

Many Internet multicast applications such as teleconferencing and remote diagnosis have Quality-of-Service (QoS) requirements. The requirements can be additive (end-to-end delay), multiplicative (loss rate), or of a bottleneck nature (bandwidth). Given such diverse requirements, it is a challenging task to build QoS-constrained multicast trees in a large network where no global network state is available. This paper proposes a scalable QoS multicast routing protocol (SoMR) that supports all three QoS requirement types. SoMR is scalable due to small communication overhead. It achieves favorable tradeoff between routing performance and routing overhead by carefully selecting the network sub-graph in which it searches for a path that can support the QoS requirements. The scope of search is automatically tuned based on the current network conditions. An early-warning mechanism helps detect and route around the long-delay paths in the network. The operations of SoMR are completely decentralized. They rely only on the local state stored at each router.     

Impact of QoS operations on an experimental testbed network

By making the best use of limited bandwidth, quality of service (QoS) provisioning over internet is essential for satisfying various types of internet-application requirements. The traffic classification and scheduling are the key functions to provide various kinds of class of service (CoS) under an overload condition. This paper investigates QoS performance in a network equipment testbed when implementing these main functions. We examine the major CoS functions provided by the Juniper T320 router, and measure their performance. In addition to fundamental analysis of the QoS behavior, we show the impact of QoS operations on a parallel system distributed in multi-domain networks as a practical case study of grid environments.     

An end-to-end QoS framework with on-demand bandwidth reconfiguration

This paper proposes a new QoS framework, called the On-Demand QoS Path framework (ODP). It provides end-to-end QoS guarantees to individual flows with minimal overhead, while keeping the scalability characteristic of DiffServ. ODP exercises per-flow admission control and end-to-end bandwidth reservation at the edge of the network and only differentiates service types in the core of the network. In addition, to adapt to dynamically changing traffic load, ODP monitors the bandwidth utilization of the network and performs dynamic bandwidth reconfiguration in the network core based on the monitored bandwidth utilization. Through extensive simulations, the performance of ODP is investigated and compared with that of IntServ and DiffServ frameworks. The simulation results clearly showed that ODP provides end-to-end QoS guarantees to individual flows, which DiffServ can not provide, with much less overhead than IntServ.     

A measurement-based approach for dynamic QoS adaptation in DiffServ networks

This paper presents a practical approach to managing multimedia traffic in DiffServ network, using network monitoring feedback and control. We exploit the flexibility of multimedia traffic and process network level parameters to adapt the traffic according to the current state of the network. The latter is determined based on reports sent by bandwidth monitors installed on each node of a DiffServ Domain. The bandwidth monitors interact with a policy server which, depending on the network state, decides the policy(ies) that should be enforced by the DiffServ network. The implementation of the selected policies typically leads to accepting, remarking, or dropping the multimedia traffic entering the network. Multimedia streams may be assigned different levels of QoS, as interpreted by the marker at the DiffServ edge router and marked according to network state. To achieve such dynamic QoS adaptation for multimedia applications, we have implemented and evaluated a policy-based management system. Performance evaluation shows that multimedia applications adapt better to network conditions using our approach.     

基于堆排序的PQ+CBWFQ路由器排队调度算法

研究具有QoS特征、易于实现的排队算法一直是优化带宽的重要手段,也是提高宽带IP网络性能的主要途径。文章提出基于堆排序的PQ＋CBWFQ网络路由器排队调度算法进行具体实现,并给出低成本的硬件实现方案,对未来的高性能路由器设计具有重要的参考价值。     

A new approach to dynamic bandwidth allocation in Quality of Service networks: Performance and bounds

Efficient dynamic resource provisioning algorithms are necessary to the development and automation of Quality of Service (QoS) networks. The main goal of these algorithms is to offer services that satisfy the QoS requirements of individual users while guaranteeing at the same time an efficient utilization of network resources.In this paper we introduce a new service model that provides per-flow bandwidth guarantees, where users subscribe for a guaranteed rate; moreover, the network periodically individuates unused bandwidth and proposes short-term contracts where extra-bandwidth is allocated and guaranteed exclusively to users who can exploit it to transmit at a rate higher than their subscribed rate.To implement this service model we propose a dynamic provisioning architecture for intra-domain Quality of Service networks. We develop a set of dynamic on-line bandwidth allocation algorithms that take explicitly into account traffic statistics and users’ utility functions to increase users’ benefit and network revenue.Further, we propose a mathematical formulation of the extra-bandwidth allocation problem that maximizes network revenue. The solution of this model allows to obtain an upper bound on the performance achievable by any on-line bandwidth allocation algorithm.We demonstrate through simulation in realistic network scenarios that the proposed dynamic allocation algorithms are superior to static provisioning in providing resource allocation both in terms of total accepted load and network revenue, and they approach, in several network scenarios, the ideal performance provided by the mathematical model.     

支持服务质量的片上网络路由器设计

系统芯片的复杂应用使得片上互连成为系统性能的瓶颈,因此出现了以片上网络为核心的通信结构,而路由器是片上网络的关键部件,它完成数据在片上网络拓扑结构上的传输.设计了支持服务质量的片上网络路由器.采用面向连接的细粒度数据交换方式为确保通信服务提供严格的端对端延迟需求,采用无连接的数据交换方式支持尽力而为通信服务,同时采用均衡片上通信负载的路由算法,有效地提高了平均通信性能.     

Rate control of multi class priority flows with end-to-end delay and rate constraints for QoS networks

To address end-to-end quality of service (QoS) requirements, we derive a novel distributed combined rate and end-to-end delay control in a network serving multi-class flows with priority packet scheduling. We show that the control is globally asymptotically stable without information time lags. The stable flows attain the end-to-end delay requirements and have no packet loss. We also show that by enhancing the network with bandwidth reservation and admission control, minimum rate is also guaranteed. The stability with very long time lags of a discrete time version control with non-greedy flows and random packet arrivals is studied numerically by an NS2 packet-based simulation of the Australian Academic and Research Network.     

Service Adaptability in Multimedia Wireless Networks

Next-generation wireless communication systems aim at supporting wireless multimedia services with different quality-of-service (QoS) and bandwidth requirements. Therefore, effective management of the limited radio resources is important to enhance the network performance. In this paper, we propose a QoS adaptive multimedia service framework for controlling the traffic in multimedia wireless networks (MWN) that enhances the current methods used in cellular environments. The proposed framework is designed to take advantage of the adaptive bandwidth allocation (ABA) algorithm with new calls in order to enhance the system utilization and blocking probability of new calls. The performance of our framework is compared to existing framework in the literature. Simulation results show that our QoS adaptive multimedia service framework outperforms the existing framework in terms of new call blocking probability, handoff call dropping probability, and bandwidth utilization.