viii CONTENTS 4.6 Buffer Management 163 4.6.1 Tail Drop 163 4.6.2 Drop on Full 164 4.6.3 Random Early Detection(RED)/164 4.6.4 Differential Dropping:RIO 167 4.6.5 Fair Random Early Detection(FRED)/168 4.6.6 Stabilized Random Early Detection(SRED)/170 4.6.7 Longest Queue Drop (LQD)/172 5 BASICS OF PACKET SWITCHING 176 5.1 Fundamental Switching Concept 177 5.2 Switch Fabric Classification /181 5.2.1 Time-Division Switching 181 5.2.2 Space-Division Switching 183 5.3 Buffering Strategy in Switching Fabrics /187 5.3.1 Shared-Memory Queuing 188 5.3.2 Output Queuing(OQ)/188 5.3.3 Input Queuing 189 5.3.4 Virtual Output Queuing (VOQ)/189 5.3.5 Combined Input and Output Queuing /190 5.3.6 Crosspoint Queuing 191 5.4 Multiplane Switching and Multistage Switching /191 5.5 Performance of Basic Switches /195 5.5.1 Traffic Model 196 5.5.2 Input-Buffered Switches /197 5.5.3 Output-Buffered Switches 199 5.5.4 Completely Shared-Buffered Switches /201 6 SHARED-MEMORY SWITCHES 207 6.1 Linked List Approach 208 6.2 Content Addressable Memory Approach /213 6.3 Space-Time-Space Approach 215 6.4 Scaling the Shared-Memory Switches /217 6.4.1 Washington University Gigabit Switch /217 6.4.2 Concentrator-Based Growable Switch Architecture /218 6.4.3 Parallel Shared-Memory Switches 218 6.5 Multicast Shared-Memory Switches 220 6.5.1 Shared-Memory Switch with a Multicast Logical Queue 220 6.5.2 Shared-Memory Switch with Cell Copy /220 6.5.3 Shared-Memory Switch with Address Copy 222Book1099 — “ftoc” — 2007/2/16 — 21:26 — page viii — #4 viii CONTENTS 4.6 Buffer Management / 163 4.6.1 Tail Drop / 163 4.6.2 Drop on Full / 164 4.6.3 Random Early Detection (RED) / 164 4.6.4 Differential Dropping: RIO / 167 4.6.5 Fair Random Early Detection (FRED) / 168 4.6.6 Stabilized Random Early Detection (SRED) / 170 4.6.7 Longest Queue Drop (LQD) / 172 5 BASICS OF PACKET SWITCHING 176 5.1 Fundamental Switching Concept / 177 5.2 Switch Fabric Classification / 181 5.2.1 Time-Division Switching / 181 5.2.2 Space-Division Switching / 183 5.3 Buffering Strategy in Switching Fabrics / 187 5.3.1 Shared-Memory Queuing / 188 5.3.2 Output Queuing (OQ) / 188 5.3.3 Input Queuing / 189 5.3.4 Virtual Output Queuing (VOQ) / 189 5.3.5 Combined Input and Output Queuing / 190 5.3.6 Crosspoint Queuing / 191 5.4 Multiplane Switching and Multistage Switching / 191 5.5 Performance of Basic Switches / 195 5.5.1 Traffic Model / 196 5.5.2 Input-Buffered Switches / 197 5.5.3 Output-Buffered Switches / 199 5.5.4 Completely Shared-Buffered Switches / 201 6 SHARED-MEMORY SWITCHES 207 6.1 Linked List Approach / 208 6.2 Content Addressable Memory Approach / 213 6.3 Space-Time-Space Approach / 215 6.4 Scaling the Shared-Memory Switches / 217 6.4.1 Washington University Gigabit Switch / 217 6.4.2 Concentrator-Based Growable Switch Architecture / 218 6.4.3 Parallel Shared-Memory Switches / 218 6.5 Multicast Shared-Memory Switches / 220 6.5.1 Shared-Memory Switch with a Multicast Logical Queue / 220 6.5.2 Shared-Memory Switch with Cell Copy / 220 6.5.3 Shared-Memory Switch with Address Copy / 222