Analysis and simulation of interrupt overhead impact on OS throughput in high‐speed networks

The paper presents analytical and simulation models to study the impact of interrupt overhead on operating system throughput of network elements such as PC‐based routers, servers, and hosts when subjected to high‐speed network traffic. Under such high network traffic, the system throughput will be negatively affected due to interrupt overhead caused by the incoming traffic. We first present an analytical model for the ideal system when interrupt overhead is ignored. We then present two models which describe the impact of high interrupt rate on system throughput. One model is for employing PIO in which network adapters are not equipped with DMA engines, and the other model is for employing DMA in which network adapters are equipped with DMA engines. The paper also describes detailed discrete‐event simulation models for the ideal system and for systems with DMA and PIO. Simulations results as well as reported experimental measurements show that our analytical models are valid and give a good approximation. Our analysis and simulation work can be valuable in providing insight to understand and predict system behaviour, as well as improving and maintaining good host performance. The paper identifies analytically critical design operation points such as that of overload condition. The paper also proposes solutions and recommendations for improving performance. Copyright © 2005 John Wiley & Sons, Ltd.     

Locked discrete event systems: How to model and how to unlock

To model qualitative aspects of discrete event systems, i.e., the order of the events is of sole importance, we use a triple consisting of the set of all possible events (the alphabet), the set of all behavior (possible strings of events), and the set of all tasks (completed behavior). We use this view to model synchronous as well as asynchronous connection of systems. Moreover, it is easy to define notions like deadlock and livelock in this view. We give a method to construct a second system that, in connection with the original system, gets rid of its deadlock and/or livelock. A state-space representation is introduced. In this representation computations can be done effectively.     

高负荷网络环境下改善网络服务器性能的方法

通过简单介绍网络服务器收发数据包的过程，分析造成高负荷网络环境下数据包转发性能下降的原因，同时引出接收活锁的概念，并介绍几种改善高负荷网络环境下网络性能的思路与方法。     

Livelocks in parallel programs

This paper is the second of a two-part series exploring the subtle correctness criterion of the absence of livelocks in parallel programs. In this paper we are concerned with the issue of proving this correctness criterion. It is shown that livelocks are not preserved by reduction, implying that reduction cannot be used directly in proving the absence of livelocks. Two applicable proof techniques are also presented. One is based on the notion of establishing sufficient conditions for livelock-freedom; the other is an extension of the well-founded set method for proving termination in sequential programs.     

采用轮询机制提高Linux系统的网络性能

目前,Linux操作系统被广泛应用在网络数据包收发系统中。这是因为,Linux采用中断机制来响应外部事件,保证了系统能够合理高效地利用CPU资源。但是,在高负荷网络环境下,大量的CPU资源将会被频繁到达的网卡中断占用,导致系统遭遇性能瓶颈,出现接收活锁1。为了避免在高负荷网络环境下系统性能下降,该文采用轮询机制处理网络数据的收发,而在低负荷网络环境中,仍然采用原有的中断机制。     

Networks on which hot-potato routing does not livelock

Summary. Hot-potato routing is a form of synchronous routing which makes no use of buffers at intermediate nodes. Packets must move at every time step, until they reach their destination. If contention prevents a packet from taking its preferred outgoing edge, it is deflected on a different edge. Two simple design principles for hot potato routing algorithms are minimum advance, that advances at least one packet towards its destination from every nonempty node (and possibly deflects all other packets), and maximum advance, that advances the maximum possible number of packets. Livelock is a situation in which packets keep moving indefinitely in the network without any packet ever reaching its destination. It is known that even maximum advance algorithms might livelock on some networks. We show that minimum advance algorithms never livelock on tree networks, and that maximum advance algorithms never livelock on triangulated networks. Received: March 1999 / Accepted: August 1999     

On the accuracy of two analytical models for evaluating the performance of Gigabit Ethernet hosts

In this paper we develop and assess the accuracy of two analytical models that capture the behavior of network hosts when subjected to heavy load such as that of Gigabit Ethernet. The first analytical model is based on Markov processes and queuing theory, and the second is a pure Markov process. In order to validate the models and assess their accuracy, two different numerical examples are presented. The two numerical examples use system parameters that are realistic and appropriate for modern hardware. Both analytical models give closed-form solutions that facilitate the study of a number of important system performance metrics. These metrics include throughput, latency, stability condition, CPU utilizations of interrupt handling and protocol processing, and CPU availability for user applications. The two models give mathematically equivalent closed-form solutions for all metrics except for latency. To address latency, we compare the results of both models with the results of a discrete-event simulation. The latency accuracy of the two models is assessed relative to simulation in terms of differences and percentage errors. The paper shows that the second model is more accurate.     

一种改进的死锁和活锁避免资源联合分配协议

提出一种改进的死锁和活锁避免资源联合分配协议——OODP3(Optimal ODP3),OODP3基于ODP3(Order-based Deadlock Prevention Protocol with Parallel requests)的安全状态方法避免死锁和活锁,但是,OODP3将其时间复杂度降到多项式级,并对O...     

BOIN:一种新型无缓存高性能计算机光互连网络

 现有的高性能计算机光互连网络大都需要对数据报文进行光-电-光转换并缓存,或者需要预先申请并建立从源节点到目的节点的光链路,这在一定程度上限制了网络性能.提出了一种既不需要对光数据报文进行缓存排队,也不需要预先申请并建立光链路的新型的光互连网络结构BOIN.给出了BOIN网络上的无死锁和无活锁路由算法,推导出BOIN网络中数据传输的延时上界,并通过模拟实验对比了BOIN网络与其它两种典型的网络的性能.实验结果表明,BOIN光互连网络具有良好的延时和吞吐率特性,能够很好地满足高性能计算机系统的要求.     

一种在Linux路由器中解决接收活锁问题的方案

作为中断驱动的操作系统，Linux易于发生数据接收活锁。文章分析了接收活锁产生的原因，提出了在Linux路由器中能有效避免活锁。提高包转发率的优化机制。并利用专业测试仪器进行了实验，最后给出了实验结果。