Packet Forwarding Technologies

所需积分/C币:9 2019-04-28 15:58:44 14.59MB PDF
9
收藏 收藏
举报

Packet Forwarding Technologies
OTHER TELECOMMUNICATIONS BOOKS FROM AUERBACH Architecting the Telecommunication Security in Distributed, Grid, Mobile, Evolution: Toward Converged Network and Pervasive computing Services Yang xiao Vijay K Gurbani and Xian-He Sur SBN:0-8493-7921-0 SBN:0-84939567-4 TCP Performance over Business Strategies for the UMTS-HSDPA Systems NextGeneration network hamad Assaad and Djamal Zeghlache Nigel Seel SBN:0-8493-6838-3 SBN:0-8493-8035-9 Testing Integrated Qos of volP: Chaos Applications in Telecommunications Packets to Perceptual Voice Quality Peter Stavroulakis Vlatko Lipovac SBN:0-8493-3832-8 SBN:0-8493-3521-3 Context-Aware Pervasive Systems: The handbook of mobile middleware Architectures for a new breed of Paolo bellavista and antonio corradi Applications SBN:0-8493-3833-6 Seng Loke SBN:0-8493-7255-0 Traffic Management in IP-Based Communications Fundamentals of dsL Technology Trinh Anh Tuan Philip golden, Herve Dedieu, Krista s Jacobsen SBN:0-8493-9577 SBN:0-8493-1913-7 Understanding Broadband over Introduction to mobile communications Power Line Technology, Services, Markets Gilbert held Tony Wakefield, Dave McNally, David Bowler. SBN:0-8493-9846-0 Alan mayne SBN:1-4200-4653-5 Understanding IPTv Gilbert held IP Multimedia Subsystem: Service SBN:0-8493-7415-4 Infrastructure to Converge NGN, 3G and the internet WiMAX: A Wireless Technology Rebecca Copeland Revolution SBN:0-8493-9250-0 G.S.V. Radha Krishna rao. g. Radhaman SBN:0-8493-7059-0 MPLS for Metropolitan Area Networks Nam-Kee Tan WiMAX: Taking Wireless to the MAX |SBN:0-8493-2212-X Deepak Pareek SBN:0-8493-7186-4 Performance Modeling and Analysis of Bluetooth Networks: Polling Wireless Mesh Networking: Scheduling, and Traffic Control Architectures, Protocols and Jelena misic and vojislav B Misic Standards SBN:0-8493-3157-9 Yan Zhang, Jijun Luo and Honglin Hu A Practical Guide to content SBN:0-8493-7399-9 Delivery Networks Wireless mesh networks Gilbert held Gilbert Held SBN:0-8493-3649-X SBN:08493-2960-4 Resource, Mobility, and Securit Management in Wireless Networks and mobile communications Yan Zhang, Honglin hu, and masayuki Fujise SBN:0-8493-8036-7 AUERBACH PUBLICATIONS w.auerbach -publications. com To Order cal:1-800-2727737·Fax:1-800374-3401 E-mail: orders crcpress cor AU8057c00 O inddⅱ 11/14/20076:15:32PM PACKET FORWARDING TECHNOLOGIES WEIDONG WU Auerbach Publications Taylor& Francis Group New york London CRC Press is an imprint of the Taylor Francis Group, an informa business AU8057co0 O indoⅲi 11/14/20076:15:32PM Auerbach publications Taylor Francis Group 6000 Broken Sound Parkway nw, Suite 300 Boca raton Fl 33487-274 @2008 by Taylor& Francis Group, LLC Auerbach is an imprint of Taylor Francis Group, an Informa business No claim to original U.S. Government works Printed in the United States of America on acid-free pape 10987654321 International Standard Book Number-13: 978-0-8493-8057-0(Hardcover) This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with permission, and sources are indicated. a wide variety of references are listed. Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials or for the consequences of their use No part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electron ic, mechan ical,or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any informa ion storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from www.copyright.com/orcontacttheCopyrightClearanceCenter this ccc, z e Rosewessd ww e priyet ma ot923 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For orga tions that have been granted a photocopy license by the CCC, a separate system of payment has been arranged Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Library of Congress Cataloging-in-Publication Data Wu, Weidong Packet forwarding technologies /by Weidong W Pcm Includes bibliographical references and index ISBN-13:978-0-84938057-0 ISBN-10:0-8493-8057-X 1 Packet switching(Data transmission)2. Routers(Computer networks)I Title TK5105W832008 621.39′81-dc22 2007026355 Visit the Taylor Francis Web site at http://www.taylorandfrancis.com and thc auerbach web sitc at http://www.auerbach-publications.com AU8057 C000 indd iv 11/14/20076:15:32PM Contents P1 reface Acknowledgments……… About the author V11 Chapter 1 Introduction……………………,, 1. 1 Introduction ··4··::······· 1.2C once t of ro outers 2 1.3 Basic Functionalities of routers ·“···· 2 1.3.1 Route processing………… 2 1.3.2 Packet Forwarding 1.3.3 Router Special Services……………15 1.4 Evolu fro 1.4.1 First Generation--Bus-Based Router Architectures with Single Processor 1. 4.2 Second Generation--Bus-Based Router Architectures with Multiple processors 8 1.4.2.1 Architectures with Route Caching………………8 1.4.2. 2 Architectures with Multiple Parallel Forwarding Engines ......9 1.4.3 Third Generation-Switch Fabric-Based Router Architecture ...... 11 144 Fourth Generation- Scaling router Architccture Using Optics…………12 1.5 Key Components of a router.... 1.5. 1 Linecard 垂 1.5.1.1 Transponder/Tr 14 1.5.1.2 Framer 14 1.5. 1.3 Network Processor .......... 15 1514 Traffic Manager………… 15 .51.5CPU 16 1.5.2 Network Processor (NP) ······ 16 5.3 Switch Fab 1.5.3. 1 Shared Medium Switch 1.5.3.2 Shared Memory Switch Fabric 20 AU8057 C000 indd v 11/14/20076:15:32PM ■ Contents 153.3 Distributed Output Buffered Switch Fabric……………….21 1.5.3.4 Crossbar Switch 22 1.5.3.5 Space-Time Division Switc 1.5.4 IP-Address Lookup: A Bottleneck 27 Refo 2 Chapter2 Concept of IP-Address Lookup and Routing Table………,31 2.1 IP Address, Prefix, and routing table 31 2.2 Conccpt of IP-Address Looku 32 2.3 Matching te 1g echniques 33 2.3.1 Design Criteria and performance Requirement………………,3 24 Difficulty of the longest-Prefix Matching Problem…………,36 2.4.1 Comparisons with ATM Address and Phone Number 2.4.2 Internet Addressing arch 3 2.5 Routing Table Characteristics 2.5. 1 Routing Table St 2.5.2 Routing Table growtl 41 2.5.3I of address alle ng Table 43 2.5.3.1 Migration of Address Allocation Policy 253.2 Impact of Address Allocations on Routing Table size…………45 2.5.3.3Ir of address allocation on prefi wth24 Bit Length…… 46 2.5.4 Contributions te Routing table growth 46 2541 Multi-Homing….…,8 2.5.4.2 Failure to aggregate 48 254.3 Load Balancing… 2.5.4.4 Address fragmentation 50 2.5.5 Route Upd 50 2.6 Constructing Optimal Routing Tables .52 261 Filtering Based on Address Allocation Policies………….,52 2.6.1. 1 Three Filtering Rules 2. 6. 1. 2 Performance Evaluation ……….54 2.6.2 Minimization of the routing table with Address reassignments ........55 2621 Case of a single lp routing table…… 56 2.6.2.2 General Case ………………59 2.6.3 Optimal Routing Table Constructor 2.6.3.1 Description of the Algorithm 2.6.3.2 Improvements +++ 2.6.3. 3 Experiments and results Referenc 6 Chapter3 Classic schemes…………………………69 3. 1 Linear Search 3.2 Caching………… 69 3.2.1 Management Policies ....................................70 32.11 Cache Modeling…………… 70 3. 2. 1.2 Trace Generation 71 AU8057c00onddⅵ 11/14/20076:15:32PM Contents■vi 3.2. 1.3 Measurement Results 3. 2.1.4 Caching Cost Analysis 3.2.2 Characteristics of Destination Address locality 3.2.2.1 Locality: Concepts 80 3.2.2.2 Cache Replacement algorithms 81 3.2.2.3 Stack Reference Frequency 83 3.2.2.4 Analysis of Noninteractive Traffic....... 86 3.2.2.5 Cache Design Issues ··························· 87 3.2.3 Discussions 3.3 Binary Trie………… 3.Path- Compressed Trie…,,… 91 3.5 Dynamic Prefix Trie .92 3.5.1 Definition and Data Structure 3.5.2 Properties of dp-tries 3.5.3 Algorithms for DP-Tries 3.5.3.1 Insertion…… 垂·· 3.5.3.2 Deletion 102 3.5.3.3 Search 3.5.4 Performance 。垂 References 垂垂4垂非 …105 Chapter4 Multibit Tries…… 107 4.1 Level Compression Trie 107 411 Level Compression.…………107 4.1.2 Representation of LC-Tries 109 1··垂来 43 Building LC-Iries…:11 4.1.4 Experiments 112 4. 1.5 Modified LC-I 113 4.2 Controlled Prefix Expansion 113 4.2.1 Prefix Expansion 4.2.2 Constructing Multibit Tries 115 4.2.3 Efficient Fixed-Stride Tries 4.2.4 Variable-Stride tries 4. 3 Lulea algorithms 123 4.3.1 Level 1 of the data structure∴… 124 4.3.2 Levels 2 and 3 of the Data Structure.................... 127 4.3.3 Growth Limitations in the Current Design 128 4.3.4 Performance ·++ 4.4 Elevator Algorithm 128 4. 4. 1 Elevator-Stairs Algorithm 129 442 log W-Elevators Algorithm………………………13 43 Experiments… 4.5 Block Trees 138 4.5.1 Construction of block Trees ·.··························· 138 45.2 Lookup… ······ 45.3 Updates… 142 4.5.4 Stockpiling Au8057 C000 indd vii 11/14/20076:15:33PM vi■ Contents 4.5.5 Worst-Case Performance …...145 4.5.6 Experiments ...... 148 4.6 Multibit tries in hardware 4.6.1 Stanford hardware Trie 46.2 Tree Bitmap… 150 4.6.3 Tree Bitmap Optimizations………,,.… 154 4.6.4 Hardware Reference Design 157 Re eferences ··········· 162 hapter5 Pipelined Multibit Tries………………165 5. 1 Fast Incremental Updates for the pipelined Fixed-Stride Tries ......... 165 5.1.1 Pipelined Lookups Using Tries 165 5.1.2 Forwarding Engine Model and Assumption 5.1.3 Routing Table and route Update Characteristics.......... 169 5.1.4 Constructing Pipelined Fixed-Stride tries 垂当自垂 170 5.1.5 Reducing Write Bubbles 177 5. 1.5. 1 Separating Out Updates to Short Routes ......... 17 5.1.5.2 Node pull 5. 1.5.3 Eliminating Excess Writes 80 5.1.54 Caching Deleted SubTrees…………………,181 5.1.6 Summary and Discussion………………,184 5.2 Two-Phase Algorithm 5.2.1 Problem Statements 186 52.2 Computing MMs(W-1,k)………,186 5.2.3 Computing T(W-1,k) 524上 aster wo- Phase algorithm for k=2,3… 192 5.2.5 Partitioning Scheme . 5.2.6 Experimental Results 195 5.3 Pipelined variable-Stride multibit Tries........ 5.3.1 Construction of Optimal PVSt 5.3.2 Mapping onto a pipeline architecture 200 5.3.3 Experimental Results........ 202 References 204 Chapter6 Efficient Data Structures for bursty Access Patterns.o..... 205 6. 1 Table-Driven Schemes ··· ···· 205 6. 1.1 Table-Driven Models .·:···4·· 205 6.1.2 Dynamic Programming algorithm ,,, 207 6.1.3 Lagrange ar on Algorithm 209 6.2 Near-Optimal Scheme with Bounded Worst-Case Performance ∴211 6.2.1 Definition 垂垂 2 6.2.2 Algorithm MINDPQ 213 6.2.3 Depth-Ce d Weight Balanced t 216 6.2.4 Simulation∴ 217 63 Dynamic Biased Skip List……………………217 6.3.1 Regular Skip 218 6.3.2 Biased Skip list 219 au8057 C000 indd viii 11/14/20076:15:33PM Contents■ix 6.3.2.1 Data Structure 219 6.3.2.2 Search Algorithm .220 6.3.3 Dynamic BSL 221 6.3.3.1 Constructing Data Structure……… 221 6.3.3.2 Dynamic Self-Adjustment ) 6.3.3.3 Lazy Updating Scheme ) 6334 Experimental results…… 224 6.4 Collection of Trees for Bursty Access patterns 225 6.4.1 Prefix and Range 225 6.4.2 Collection of Red-Black TreeS(CRBT 226 64.3 Biased Skip Lists with Prefix Trees( BSLPT)………….27 6.4.4 Collection of Splay trees ............. 229 6.4.5 Experiments 230 References 234 Chapter 7 Caching Technologies 237 71 Suez lookup algorith……..27 7.1.1 Host Address Cache 237 7. 1.1.1 HAC Architecture 237 7. 1.1.2 Network Address routing table 240 7. 1.1.3 Simulations 242 71.2 Host Address Range Cache…………………….,243 7.1.3 Intelligent HARC 244 7. 1.3.1 Index Bit Selection ................ 244 7.1.3.2 Comparisons between IHARC and harC . ...... 240 7. 1.3.3 Selective Cache Invalidation .............................................248 7.2 Prefix Caching Schemes .......... 248 7.2.1Liu’ s Scheme 249 7.2.1.1 Prefix Cache …249 72.1.2 Prefix Memory.……,250 7.2.1.3 Experiments 251 72.2 Reverse routing Cache(RRC)……………252 7. 2.2.1 RRC Structure 252 72.2,2 Handling Parent Prefixes……………………252 7. 2.2.3 Updating RRC 7. 2.2.4 Performance Evaluation .255 7.3 Multi-Zone Caches 256 7.3. 1 Two-Zone Full Address Cache 25 7.3.2 Multi-Zone Pipelined Cache 垂··。 73.2.1 Architecture of mpo∴……1257 7.3.2.2 Search in MPC .·,················ 258 7.3.2.3 Outstanding miss Buffer 258 7.3.2. 4 Lookup Table Transf 260 7.3.2.5 Performance Evaluation .................. 261 7.3.3 Design Method of Multi- Zone Cache…….261 7.3.3. 1 Design Model 垂 262 73.3.2Two- Zone Design……………264 7.3.3.3 Optimization Tableau 2 AU8057co0 O inddⅸx 11/14/20076:15:33PM

...展开详情
试读 127P Packet Forwarding Technologies
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 签到新秀

关注 私信
上传资源赚钱or赚积分
最新推荐
Packet Forwarding Technologies 9积分/C币 立即下载
1/127
Packet Forwarding Technologies第1页
Packet Forwarding Technologies第2页
Packet Forwarding Technologies第3页
Packet Forwarding Technologies第4页
Packet Forwarding Technologies第5页
Packet Forwarding Technologies第6页
Packet Forwarding Technologies第7页
Packet Forwarding Technologies第8页
Packet Forwarding Technologies第9页
Packet Forwarding Technologies第10页
Packet Forwarding Technologies第11页
Packet Forwarding Technologies第12页
Packet Forwarding Technologies第13页
Packet Forwarding Technologies第14页
Packet Forwarding Technologies第15页
Packet Forwarding Technologies第16页
Packet Forwarding Technologies第17页
Packet Forwarding Technologies第18页
Packet Forwarding Technologies第19页
Packet Forwarding Technologies第20页

试读结束, 可继续阅读

9积分/C币 立即下载