Torus Exchange Exchange Properties Of The Structure Of Multi-priority Business

Along with the development of Internet application, the web-based services become more and more widely used. On one hand, it requires the core network router be able to switch large amount of data. On the other hand, it also requires the network router support prioritized traffic. The Torus switching fabric, as an agile and extensible switching fabric with high throughput, has become one of the optional structures of Terabit router, a new generation high capacity router for the core network.Traditionally, the differentiated services for prioritized traffic depend on the prioritized scheduling of resources in the switching fabric. However, because of the special topology of Torus switching fabric, the routing algorithm has more impact on the performance of the switching fabric rather than the scheduling scheme. Therefore, the main purpose of our work is to find a routing algorithm to support prioritized traffic and analyze its influence on the performance of Torus.Priority Quadrant Routing (PQR) is proposed. It is a deadlock-free adaptive routing algorithm supporting prioritized traffic for Torus. PQR can support 3 different priorities of traffic in 2-dimension Torus, and 4 in 3-dimenison Torus. In PQR, an n-dimension Torus network is divided into quadrants for each source-destination node-pair (SD pair), and a Quadrant Priority (QP) is assigned to each quadrant for routing strategies of different priority traffic. PQR provides both minimal path and non-minimal path for low priority traffic to avoid occupying hot resources, while the high priority traffic can only route on minimal path for low latency. In this way, PQR can achieve higher throughput than minimal routing algorithms, and provide a low latency of high priority traffic.Then the Priority Quadrant Routing with Load Balance (PQR-LB) algorithm is proposed. In this algorithm, according to status of current traffic load, the lower priority traffic can route to the link with comparatively low traffic load. For some time, the traffic sent to every link can be balanced. Thus, Torus with PQR-LB can achieve high throughput even on the adversarial traffic patterns. This thesis is organized as follows:Chapter 1 introduces the background knowledge of Terabit router and Torus switching fabric, and explains the wormhole and virtual channel schemes and concept of virtual network.Chapter 2 clarifies the routing classification and deadlock problem in Torus, analyzes two classical deadlock-free algorithms and one QoS supportive strategy. Chapter 3 gives the key idea and process of PQR algorithm. It describes the prioritized traffic model PQR supports; explains how prioritized quadrants are divided. Then, the constraints and routing function are given. According to the routing strategy, we can prove that PQR is deadlock-free, also, how the prioritized traffic is routed and the process of PQR is described.Chapter 4 proposes the PQR-LB algorithm. It first analyzes the unbalanced traffic pattern's impact on the performance of switching fabric, and then the main idea of PQR-LB is given that the algorithm can adaptively select the path which has comparatively low traffic load. Then the 2 level of scheduling strategy is introduced, and the improvement on the scheduling scheme to support prioritized traffic is described.Chapter 5 analyzes the simulation data of these 2 algorithms. It compares the overall throughput, end-to-end latency and load balance between the 2 algorithms. Also, the throughput, latency and load balance of different priority of traffic are compared and analyzed. Then the 6th chapter gives a summary of the whole thesis.