Broadband Packet Switching Technologies

Automatic repeat request ŽARQ., wireless ATM ŽWATM. switches, BAHAMA wireless ATM LAN, 343

Backpressure ŽBP. scheme, abacus switch performance, cell loss probability ŽCLP., 206 208

BAHAMA wireless ATM LAN, wireless ATM ŽWATM. switches, 343

Banyan-based switches:

augemented multiple-path architecture, 30 batcher-sorting network, 106 109 buffering strategies, 34 35

common properties, 103 106 deflection routing, 114 125

dual shuffle-exchange network, error correction, 118 125

shuffle-exchange network, 117 118 tandem switches, 114 117

interconnection networks, 103 106 multicast copy networks, 125 138

broadcast banyan network, 127 129 boolean interval splitting algorithm,

128 129

nonblocking condition, 129 self-routing algorithm, 127 128

concentration, 132 decoding, 133

encoding process, 129 132 overflow and call splitting, 133 134

overflow and input fairness, 134 138 concentration, 137 138

cyclic running adder network ŽCRAN., 135 137

output contention resolution algorithms, 110 112

single-path topologies, 28 29 Sunshine switch, 112 114

Base station controller ŽBCS., wireless ATM ŽWATM. switches, 339

Batcher-sorting network, banyan-based switches, 106 109

ring reservation, 110 112 Sunshine switch, 112 114

three-phase implementation algorithm, 109 110

Benes network topology, Washington University gigabit switch ŽWUGS., 95 96

Bernoulli arrival process:

input-buffered switch, random traffic and, 52

tandem-crosspoint ŽTDXP. switch performance, 246 247

INDEX 441

Bernoulli distribution, fault-tolerant multicast output-buffered ATM switch, performance analysis, 181 185

Best-first lowest-output-occupancy-cell-first algorithm ŽLOOFA., input-buffered switch, 79 80

Best-matching-prefix problem, internet protocol ŽIP. route lookups, binary search, 381 384

Bidirectional arbiter ŽNTT., input-buffered switch, 67 70

Binary search, internet protocol ŽIP. route lookups:

best-matching prefix, 381 384 multiway search, cache exploitation,

385 388

Binary tree, internet protocol route lookups, 368 369

Bit error rate ŽBER.:

optical interconnection network ŽOIN., power budget analysis, 328

wireless ATM ŽWATM. switches, data link control layer, 346 347

Blocking switch:

internal link blocking, 17 18 three-stage Clos switches as, 31 33

BNR switch, architecture, 289 290 Boolean interval spitting algorithm:

banyan network switches, multicast copy, 126 broadcast banyan network ŽBBN., 128 129

Broadband Radio Access Networks ŽBRAN. project, wireless ATM ŽWATM. switches, medium access control layers, 346

Broadband switching systems ŽBSSs., packet switch architecture, 13 14

Broadcast banyan network ŽBBN., multicast copying, 125, 127 129

boolean interval splitting algorithm, 128 129 nonblocking condition, 129

self-routing algorithm, 127 128 Broadcast channel number ŽBCN.:

abacus switch: architecture, 191 193

input port controller implementation, 198 banyan network switches, multicast copy, 126 two-stage multicast out-put-buffered ATM

switch ŽMOBAS., translation tables, 161 163

Broadcast mode, asynchronous transfer mode ŽATM. networks, 45

Buffered multistage concentration network ŽBMCN., enhanced abacus switch, 214 217

442 INDEX

Buffering strategies:

asynchronous transfer mode ŽATM. switches, 17

crosspoint-buffered switches, 35 input-buffered switches, 35 36 internally buffered switches, 34 35 multistage shared-buffer switches, 36 output-buffered switches, 36 recirculated buffered switches, 35 shared-buffer switches, 36 virtual-output-queuing ŽVOQ. switches,

36 37

crossbar switches, 26 27

wireless ATM ŽWATM. switches, handoff process, 350 351

Burst length ŽBL., wireless ATM ŽWATM. switches, mobility-support ATM switch, 360 362

Bursty traffic model:

abacus switch, maximum throughput performance, 202 203

input-buffered switch, 52 53 wireless ATM ŽWATM. switches,

mobility-support ATM switch, 360 362 Bus interface, single-stage knockout switch,

143

Bus matrix switch ŽBMX., buffering strategy, 26 27

Caching technique, internet protocol route lookups, 369

multiway binary search, cache exploitation, 385 388

Call splitting:

asynchronous transfer mode ŽATM. switches, 20 24

banyan-based switches, overflow and, 133 134

Capacity graphing, Path switching, 270 272 Cell additionrdeletion:

shared-memory switch, linked list logical queues, 86 90

tandem banyan switching fabric ŽTBSF., deflection routing, 116 117

Cell copy, multicast shared-memory switch, 98 99

Cell delay variation ŽCDV., design and performance criteria, 13 14

Cell delineation unit, 3M optical switch, 294 296

Cell interleaving, abacus-based packet switching, 222 224

Cell loss probability ŽCLP.:

abacus switch performance, 206 208

asynchronous transfer mode ŽATM. networks, 428 429

design and performance criteria, 14 knockout-based switches:

channel grouping, 152 154 single-stage knockout switch, 144 146

output-buffered switch, performance evaluation, 41 44

shared-buffer switches, performance evaluation, 44 46

two-stage multicast out-put-buffered ATM switch ŽMOBAS., 163 169

wireless ATM ŽWATM. switches, mobility-support ATM switch, 361 362

Cell routing, wireless ATM ŽWATM. switches: handoff process, crossover switch ŽCOS.,

351 352

mobility-support ATM switch, 353 358 Cell sequence number ŽCSN., wireless ATM

ŽWATM. switches, data link control layer, 347

Cell synchronization unit, 3M optical switch, 297 301

Centralized connection processors, asynchronous transfer mode ŽATM. switches, 16

Central switching network, Washington University gigabit switch ŽWUGS., 95 96

Channel grouping, knockout-based switches, 150 154

cell loss probability, 152 154 maximum throughput, 150 152

Circuit switching schemes, asynchronous transfer mode ŽATM. switches, 15 16

Cisneros-Brackett optical switch, architecture, 287 288

Classless interdomain routing ŽCIDR., internet protocol route lookups, 366

Clos-network switches: Atlanta switch:

architecture, 261 configuration, 259 261

distributed and random and arbitration, 261 262

multicasting, 262 263

blocking switch, three-stage Clos switches as, 31 33

concurrent round-robin dispatching switch: architecture, 264 265

concurrent dispatching, 265 267 configuration, 263 264 desynchronization effect, 267 268

dynamic routing, suboptimal straight matching method, 258 259

path switch: configuration, 268 272

heterogeneous capacity assignment, 274 277

homogeneous capacity and route assignment, 272 274

research issues, 253 255

routing properties and scheduling methods, 255 257

Codeword array ŽCWA., internet protocol ŽIP. route lookups, gigabit switch routers, construction algorithm, 393 395

Complete partitioning, shared-memory switch, 24

Complexity comparisons:

enhanced abacus switch, 219 220 optical interconnection network ŽOIN.,

324 326

Compressed next-hop array ŽCNHA., internet protocol ŽIP. route lookups, gigabit switch routers, 393 395

Concentration modules ŽCM., enhanced abacus switch:

buffered multistage concentration network ŽBMCN., 214 217

memoryless multistage concentration network, 212 214

Concentration principle:

banyan network switches, multicast copy, 132 cyclic running adder network ŽCRAN.,

137 138

overflow fairness, 134 138 single-stage knockout switch, 144 146

construction, 146 150 Concentrator-based growable switch

architecture, multistage shared-memory applications, 96

Concurrent round-robin dispatching ŽCRRD. switch:

architecture, 264 265 concurrent dispatching, 265 267 configuration, 263 264

desynchronization effect, 267 268 Congestion flow, asynchronous transfer mode

ŽATM. networks, 428

Connection rerouting, wireless ATM ŽWATM. switches, handoff process, 348 350

Content-addressable memory ŽCAM. technique, shared-memory switch, 91 93

Contention resolution algorithms, STAR-TRACK switch, 286 287

Contention resolution device ŽCRD., Cisneros-Brackett optical switch, 287 288

Contention switches, single-stage knockout switch, concentrator construction,

146 150

INDEX 443

Control packets, wireless ATM ŽWATM. switches, radio access layers, 345 346

Control plane ŽC-plane., asynchronous transfer mode ŽATM. network protocol, 409

Copy number ŽCN., banyan network switches, multicast copy, 125 126

cyclic running adder network ŽCRAN., 136 138

encoding process, 130 132

Critical cell first ŽCCF., input-buffered switch, output-queuing emulation, 74 75

Crossbar switches: architecture, 25 27 buffering strategies, 35

multicast grouping networks ŽMGNs., 159 160

Crossover switch ŽCOS., wireless ATM ŽWATM. switches:

handoff process, 350

buffering strategies, 350 351 cell routing, 351 352 mobility-support ATM switch,

352 362 Crosspoint-buffered switches:

multiple-QoS scalable distributedarbitration switch ŽMSDA.: performance analysis, 236 238 structure, 234 236

research issues, 227 229

scalable distributed-arbitration switch ŽSDA.:

performance analysis, 231 233 structure, 229 231

Crosspoint unit ŽXPU., input-buffered switch, token tunneling, 71 72

Cross-stuck ŽCS. fault, fault-tolerant multicast output-buffered ATM switch:

fault detection, 172 174

location and configuration, 175 177 performance analysis, 182 183 switch element ŽSWE., 170 171

Crosstalk analysis, optical interconnection network ŽOIN., 328 331

Cyclic redundancy check ŽCRC., 3M optical switch, cell delineation unit, 294 296

Cyclic running adder network ŽCRAN., banyan-based switches, overflow and input fairness, 135 138

Data link control ŽDLC. layer, wireless ATM ŽWATM. switches:

NEC WATMnet prototype system, 341 342 protocol, 340 341

research and development, 337 338

444 INDEX

Data link control layer, wireless ATM ŽWATM. switches, radio access layers, 346 347

Data packet flow, terabit IP router architecture, 305 306

Data structure layers, internet protocol ŽIP. route lookups:

forwarding table construction, 374 377 gigabit switch routers, 388 395

Decoding, banyan-based switches, multicast copy networks, 133

Deflection routing, banyan-based switches, 114 125

dual shuffle-exchange network, error correction, 118 125

shuffle-exchange network, 117 118 tandem switches, 114 117

Delay performance: abacus switch, 203 205

scalable distributed-arbitration ŽSDA. switch, 231 233

tandem-crosspoint ŽTDXP. switch, 248 251 DelPrefix ŽX,Y. algorithm, internet protocol

ŽIP. route lookups, two-trie structure, 402 403

Delta-based switches, architecture, 29 Dense-wavelength-division-multiplexing ŽDWDM. equipment, channel multiplexing applications, 12

Descrambling procedures, SONET protocols, 417 418

Destination address ŽDA., banyan-based switches, Sunshine switch, 113 114

Desynchronization, concurrent round-robin dispatching ŽCRRD., 267 268

DIR-24-8-BASIC scheme, internet protocol ŽIP. route lookups, memory access speeds, 377 381

Dispatching, concurrent round-robin dispatching ŽCRRD. switch, 265 267

Distributed Bragg reflector ŽDBR., optical interconnection network ŽOIN., input optical module ŽIOM., 310

Distributed-queuing request update multiple access ŽDQRUMA., wireless ATM ŽWATM. switches, 343

Dual round-robin matching ŽDRRM.: Clos-network switches, concurrent

round-robin dispatching ŽCRRD. switch, 264

input-buffered switch scheduling, 62 65 Dual shuffle-exchange network ŽDSN.,

deflection routing, error correction, 118 125

Duan’s switch, properties, 283 284

Dummy address encoder ŽDAE., banyan-based switches, 125

encoding process, 129 132

Dummy address interval, banyan network switches, multicast copy, 126

Dynamic routing, Clos network switches, suboptimal straight matching method, 258 259

Edge coloring, Path switches, 276 277 Electroabsorption modulators ŽEAM., optical

interconnection network ŽOIN., complexity comparisons, 324 326 Electronic interconnection network ŽEIN.,

terabit IP routers, optical packet switches, 301 303

Encoding process, banyan-based switches, multicast copy networks, 129 132

Enhanced abacus switch, 211 220

buffered multistage concentration network, 214 217

complexity comparisons, 219 220 memoryless multistage concentration

network, 212 214 resequencing cells, 217 219

Erbium-doped fiber amplifier ŽEDFA.: 3M optical switch, 292 294

optical interconnection network ŽOIN., power budget analysis, 326 328

Error control systems, wireless ATM ŽWATM. switches, data link control layer, 346 347

Error-correcting routing, dual shuffle-exchange network ŽSN., 118 125

External modulator ŽEM., optical interconnection network ŽOIN., input optical module ŽIOM., 310

Far end block error ŽFEBE. function, SONET protocols, 416 417

Fault detectors ŽFD., fault-tolerant multicast output-buffered ATM switch, 172 174

cross-stuckrtoggle-stuck detection, 172 173 vertical-stuckrhorizontal-stuck fault

detection, 173

Fault location and configuration, fault-tolerant multicast output-buffered ATM switch, 174 181

Fault-tolerant multicast output-buffered ATM switch, 169 185

fault detection, 172 174 cross-stuckrtoggle-stuck detection,

172 173

vertical-stuckrhorizontal-stuck fault detection, 173

fault location and reconfiguration, 173 181 cross-stuckrtoggle-stuck cases, 175 177 vertical-stuckrhorizontal-stuck cases,

177 181

performance analysis, switch reconfiguration, 181 185

cross-stuckrtoggle-stuck cases, 182 183 horizontal-stuck case, 184 185 vertical-stuck case, 183 184

switch element fault model, 169 172 cross-stuck ŽCS. fault, 170 171 toggle-stuck ŽTS. fault, 171 172 verticalrhorizontal-stuck ŽVSrHS. fault,

172

Feedback priority ŽFP. signals: abacus switch:

input port controller implementation, 198 multicast contention resolution algorithm,

195 197

enhanced abacus switch:

buffered multistage concentration network ŽBMCN., 214 217

memoryless multistage concentration network, 213 214

Fiber throughput technology, link transmission speed, 1

Fine adjustment circuit timing, 3M optical switch cell synchronization unit, 299 301

First-come, first-served ŽFCFS. principle, abacus switch, architecture, 193

First-in-first-out ŽFIFO. buffer: ATM switch structure, 58 concentrator-based growable switch

architecture, 96 input-buffered switches:

performance evaluation, 37 40 scheduling algorithms, 57

3M optical switch, 293 294 output-buffered switch, performance

evaluation, 40 44

shared-memory switch, linked list logical queues, 90

single-stage knockout switch, 143 terabit IP router architecture:

data packet flow, 305 306

routing module and route controller, 308 time-division switching ŽTDS.,

shared-medium switch, 22 23 wireless ATM ŽWATM. switches,

mobility-support ATM switch, 355 358 Fixed-size data units, high-end routers, IP

architecture, 11 12

INDEX 445

Fixed wireless networks, wireless ATM ŽWATM. switches, 338

Forward error correction ŽFEC., wireless ATM ŽWATM. switches, BAHAMA wireless ATM LAN, 343

Forwarding information base ŽFIB., optical interconnection network ŽOIN., terabit IP router architecture, 308 309

Forwarding table:

internet protocol ŽIP. route lookups, fast route lookup configuration, 373 377

internet protocol route lookups, 367 Frame number, wireless ATM ŽWATM.

switches, radio access layers, 345 346 Frequency justification, SONET protocols,

418 419

Full sharing, shared-memory switch, 24 Fully interconnected switches, architecture,

26, 28

GeomrGr1 queuing model, input-buffered switches, performance evaluation, 39 40

Gigabit switch routers, internet protocol ŽIP. route lookups, 388 396

algorithms and data structures, 388 395 CBMrCNHA construction, 393 395 NHA construction algorithm, 392 393 performance analysis, 395 396

Grant pointer, input-buffered switch scheduling:

iSLIP scheme, 60 62

iterative round-robin matching ŽiRRM., 60 Greedy lowest-output-occupancy-cell-first

algorithm ŽLOOFA., input-buffered switch, 78 80

Group expansion ratio, abacus switch: architecture, 191 193

cell loss probability ŽCLP., 206 208 maximum throughput performance, 200 203

Handoff process, wireless ATM ŽWATM. switches, 347 352

buffering, 350 351 connection rerouting, 348 350 COS cell routing, 351 352

mobility-support ATM switch, 353 358 Handoff rate ŽHR., wireless ATM ŽWATM.

switches, mobility-support ATM switch, 360 362

Hardware systems, internet protocol ŽIP. route lookups, memory access speeds, 377 381

Header error control ŽHEC.:

design and performance criteria, 14 SONET protocols, 423 425

446 INDEX

Header field values, asynchronous transfer mode ŽATM. networks, 428 429

Head-of-line ŽHOL. blocking: abacus switch:

architecture, 192 193 delay, 203 205

input port controller implementation, 197 198

maximum throughput performance, 199 203

multicast contention resolution algorithm, 194 197

packet interleaving, 221 222 research issues, 189 190

asynchronous transfer mode ŽATM. switches, 19

Cisneros-Brackett optical switch, 288 enhanced abacus switch, resequencing,

217 219

input-buffered switches, 37 40 Bernoulli arrival process and random

traffic, 52

dual round-robin matching ŽDRRM. scheduling, 63 65

models, 51

throughput limitation, 49 50 virtual-output-queuing ŽVOQ.-based

matching, 55 57

window-based lookahead selection, 54 55 optical interconnection network ŽOIN.,

302 303

ping-pong arbitration unit ŽPAU., 315 324

shared-memory switch:

linked list technique, 85 90

multicast shared-memory switch, 97 98 tandem-crosspoint ŽTDXP. switch:

delay performance, 248 251 input-output-buffered switches, 239 241 unicasting operation, 244 245

virtual-output-queuing ŽVOQ. switches, 36 37

wave-mux switch, 291

wireless ATM ŽWATM. switches, mobility-support ATM switch, 354 358

Head pointer ŽHP.:

shared-memory switch, logical queue, 85 90 wireless ATM ŽWATM. switches,

mobility-support ATM switch, 356 358 Head pointer register ŽHPR., shared-memory

switch, linked list logical queues, 86 90 HEC checking mechanism, 3M optical switch,

cell delineation unit, 294 296

Heterogeneous capacity assignment, Path switching, 274 277

edge coloring, 276 277 roundoff procedure, 275 276

virtual path capacity allocation ŽVPCA., 274 275

High-end routers, IP architecture, 10 12 Homogeneous capacity, Path switching,

272 274

Homowavelength crosstalk, optical interconnection network ŽOIN., 328 331

HPS finite state machine, 3M optical switch, cell delineation unit, 295 296

Hungarian algorithm, Path switches, 276 277 HUNT state, 3M optical switch, cell

delineation unit, 295 296 HYPASS optical switch, configuration,

284 286

Idle address FIFO ŽIAF., shared-memory switch:

content-addressable memory ŽCAM. technique, 92 93

linked list logical queues, 86 90

IDLE interface, banyan-based switches, ring head-end ŽRHE., 111 112

Incoherent crosstalk, optical interconnection network ŽOIN., 328 331

Index reference ŽIR., banyan network switches, multicast copy, 126

Input-buffer delay, abacus switch performance, 203 205

cell loss probability ŽCLP., 206 208 Input-buffered switch:

asynchronous transfer mode ŽATM.: buffering strategies, 35 36 defined, 16

lowest-output-occupancy-cell-first algorithm ŽLOOFA., 78 80

models:

head-of-line blocking phenomenon, 51 traffic models, throughput results, 52 53

output-queuing emulation, 72 78 Chang algorithms, 73 74 critical cell first ŽCCF., 74 75

last in, highest priority ŽLIHP., 75 78 most-urgent-cell-first algorithm

ŽMUCFA., 72 73 performance evaluation, 37 40 performance improvement:

internal capacity increase, 53 54 scheduling efficiency, 54 57

research issues, 49 50

scheduling algorithms, 57 71

dual round-robin matching ŽDRRM., 62 65

iterative round-robin matching ŽiRRM., 58 60

iterative round-robin with SLIP ŽiSLIP., 60 62

parallel iterative matching ŽPIM., 58 round-robin arbitersrselectors, 67 72 bidirectional arbiter ŽNTT., 67 70

token tunneling, 69 72

round-robin greedy scheduling ŽRRGS., 65 67

Input concentration, banyan network switches, multicast copy, 132

cyclic running adder network ŽCRAN., 137 138

overflow fairness, 134 138

Input forwarding engine ŽIFE., terabit IP routers, optical packet switches:

data packet flow, 305

routing module and route controller, 306 Input group module ŽIGM., wave-mux switch,

290 291

Input line interface ŽILI., terabit IP router architecture:

data packet flow, 305 306

routing module and route controller, 306 Input optical modules ŽIOM., optical

interconnection network ŽOIN., 309 315 crosstalk analysis, 328 331

Input-output-buffered switches, tandem-crosspoint ŽTDXP. switch, 239 241

Input packet filter ŽIPF., terabit IP router architecture, data packet flow, 305 306

Input port controllers ŽIPCs.: abacus switch:

architecture, 190 193

enhanced configuration, 211 220 implementation, 197 198

multicast contention resolution algorithm, 194 197

ATM switch structure, 58 banyan-based switches, Sunshine switch,

113 114

fault-tolerant multicast output-buffered ATM switch, fault detection, 173

two-stage multicast out-put-buffered ATM switch ŽMOBAS., 154 157

translation tables, 160 163

Input port processors ŽIPPs., Washington University gigabit switch ŽWUGS., 94 96

Input queuing, crossbar switches, buffering strategy, 26

INDEX 447

Input routing module ŽIRM., optical interconnection network ŽOIN., terabit IP router architecture, 303

Input smoothing, input-buffered switch, 53 Input switch interface ŽISI., terabit IP router

architecture:

data packet flow, 305 306

routing module and route controller, 306 308

Input thread ŽIT., input-buffered switch, output-queuing emulation, 74

Integrated local management interface ŽILMI., asynchronous transfer mode ŽATM. network protocol, 409 410

Interconnection complexity, optical interconnection network ŽOIN., 326

Intermediate stage controller ŽISC., buffered multistage concentration network ŽBMCN., 216 217

Internal blocking, banyan-based switches, 105 Internal capacity, input-buffered switch:

multiline Žinput smoothing., 53 parallel switching, 54

speedup factor, 54

Internal link blocking, asynchronous transfer mode ŽATM., 17 18

Internet protocol ŽIP.: dominance of, 2 route lookups:

caching technique, 369 design issues, 368 369

gigabit switch routers, 388 396 algorithms and data structures, 388 395 CBMrCNHA construction, 393 395 NHA construction algorithm, 392 393 performance analysis, 395 396

hardware, memory access speeds, 377 381 multiway search, 381 388

binary search, best-matching prefix, 381 384

cache line exploitation, 385 388 performance analysis, 388 precomputed 16-bit prefix table,

384 385 Patricia tree, 372

research issues, 365 366

small forwarding tables, fast lookups, 373 377

standard trie structure, 369 372 two-trie structure, 396 404

AddPrefix Ž X, Y, Z . algorithm, 399 402 DelPrefix Ž X, Y . algorithm, 402 403 IPLookup Ž X . algorithm, 397 398 performance analysis, 403 404

prefix update algorithm, 398 399

448 INDEX

Internet protocol ŽContinued. router systems:

architectures, 9 13, 366 367 high-end routers, 10 12 low-end routers, 9 10 middle-end routers, 10

switch fabric for high-end routers, 12 13 function, 89

terabit routers, optical interconnection network:

complexity issues, 324 326 crosstalk analysis, 328 331 network configuration, 309 315

ping-pong arbitration ŽPPA. unit, 315 324 power budget analysis, 326 328

research issues, 301 303

router module and route controller, 306 309

terabit architecture, 303 306 Interworking function ŽIWF., wireless ATM

ŽWATM. switches, 339

IPLookup Ž X . algorithm, internet protocol ŽIP. route lookups, two-trie structure, 397 398

IP route lookup algorithm, internet protocol route lookups, multiway binary search, cache exploitation, 387 388

Iterative round-robin matching ŽiRRM., input-buffered switch scheduling, 58 60with SLIP ŽiSLIP., 60 62

Knockout-based switches: channel grouping, 150 154

cell loss probability, 152 154 maximum throughput, 150 152

concentration principle, 144 146 concentrator construction, 146 150 fault-tolerant multicast output-buffered

ATM switch, 169 185 fault detection, 172 174

cross-stuckrtoggle-stuck detection, 172 173

vertical-stuckrhorizontal-stuck fault detection, 173

fault location and reconfiguration, 173 181 cross-stuckrtoggle-stuck cases, 175 177 vertical-stuckrhorizontal-stuck cases,

177 181

performance analysis, switch reconfiguration, 181 185

cross-stuckrtoggle-stuck cases, 182 183 horizontal-stuck case, 184 185 vertical-stuck case, 183 184

switch element fault model, 169 172 cross-stuck ŽCS. fault, 170 171 toggle-stuck ŽTS. fault, 171 172 verticalrhorizontal-stuck ŽVSrHS. fault,

172

research issues, 141 142 single-stage architecture, 142 143

two-stage multicast out-put-buffered ATM switch, 154 169

multicast grouping network, 157 160 multicast knockout principle, 163 169

translation tables, 160 163 two-stage configuration, 154 157

Knockout principle:

channel grouping, 152 154 development of, 141 142

Label-routing methods, ATM switch structure, 79

Label switching routers ŽLSRs., applications, 2 LambdaRouter, Internet protocol ŽIP. over

wavelength networks, 12

Last in, highest priority ŽLIHP. scheme, input-buffered switch, output-queuing emulation, 75 78

Latin square assignment, Path switching, 272 274

Line interface card ŽLIC., ATM switch structure, 58

Linked list technique, shared-memory switch, 84 90

®s. content-addressable memory ŽCAM. technique, 92

Local priority ŽLP., abacus switch, multicast contention resolution algorithm, 195 197

Logical queues: shared-memory switch:

linked list technique, 84 90

multicast shared-memory switch, 97 98 wireless ATM ŽWATM. switches,

mobility-support ATM switch, 355 358 Lookup algorithms:

gigabit switch routers, 388 395

IP route lookup algorithm, multiway binary search, 387 388

two-trie IP route lookup structure, 397 398 Low-end routers, IP architecture, 910 Lowest-output-occupancy-cell-first algorithm

ŽLOOFA., input-buffered switch, 78 80

Magic WAND, wireless ATM ŽWATM. switches, 343 344

Management plane, asynchronous transfer mode ŽATM. network protocol, 410

Markov chain modeling, output-buffered switch, performance evaluation, 41 44

Markov process, input-buffered switches, performance evaluation, 38 40

Maximal matching, input-buffered switches, virtual-output-queuing ŽVOQ.-based matching, 56 57

Maximum matching, input-buffered switches, virtual-output-queuing ŽVOQ.-based matching, 56 57

Maximum throughput:

abacus switch performance, 199 203 knockout-based switches, channel grouping,

150 152

MEDIAN system, wireless ATM ŽWATM. switches, 344

Medium access control ŽMAC. layer, wireless ATM ŽWATM. switches:

NEC WATMnet prototype system, 341 342 protocol, 340 341

radio access layers, 346

research and development, 337 338 Memory access speeds, internet protocol ŽIP.

route lookups, hardware systems, 377 381 Memoryless multistage concentration network

ŽMMCM., enhanced abacus switch, 212 214

Memory-space-memory ŽMSM., Atlanta switch configuration, 259 263

Merge networks, banyan-based switches, batcher-sorting network, 106 109

Microelectromechanical systems ŽMEMS., LambdaRouter technology, 12

Middle-size routers, IP architecture, 10 Mobility-support ATM switch, wireless ATM

ŽWATM. switches, 352 362 design issues, 353 358 performance analysis, 358 362

3M optical switch: architecture, 291 294

cell delineation unit, 294 296 cell synchronization unit, 297 301 VCI-overwrite unit, 296 297

Most significant bit ŽMSB., abacus switch, packet interleaving, 221 222

Most-urgent-cell-first algorithm ŽMUCFA., input-buffered switch, output-queuing emulation, 72 73

Multicast cell counters ŽMCCs., multicast shared-memory switch, 99 101

Multicast contention resolution algorithm, abacus switch, 193 197

INDEX 449

Multicast contention resolution unit ŽMCRU., abacus switch, input port controller implementation, 197 198

Multicast copy networks, banyan-based switches, 125 138

broadcast banyan network, 127 129 boolean interval splitting algorithm,

128 129

nonblocking condition, 129 self-routing algorithm, 127 128

concentration, 132 decoding, 133

encoding process, 129 132 overflow and call splitting, 133 134

overflow and input fairness, 134 138 concentration, 137 138

cyclic running adder network ŽCRAN., 135 137

Multicast grouping networks ŽMGNs.: abacus switch:

architecture, 190 193

enhanced configuration, 211 220 multicast contention resolution algorithm,

195 197

two-stage multicast output-buffered ATM switch ŽMOBAS., 154 157

cell loss rates, 163 169 switch module, 157 160 translation tables, 160 163

Multicasting:

asynchronous transfer mode ŽATM. networks, 45, 19 20

asynchronous transfer mode ŽATM. switches, call splitting, 20 21

Atlanta switches, 262 263 tandem-crosspoint ŽTDXP. switch, 246

Multicast output-buffered ATM switch ŽMOBAS.:

abacus switches, architectural comparisons, 190 193

two-stage structure, 154 169

multicast grouping network, 157 160 multicast knockout principle, 163 169 translation tables, 160 163

two-stage configuration, 154 157 Multicast pattern maskers ŽMPMs.:

abacus switch, architecture, 191 193 fault-tolerant multicast output-buffered

ATM switch, fault detection, 172 173 multicast grouping networks ŽMGNs.,

157 160

Multicast pattern ŽMP.: abacus switch:

architecture, 191 193

450 INDEX

Multicast pattern ŽContiued.

input port controller implementation, 198 terabit IP router architecture, routing

module and route controller, 307 308 Multicast shared-memory switch, 96 101

address copy, 99 101 cell copy, 98 99 logical queuing, 97 98

Multicast translation tables ŽMTTs.: abacus switch, architecture, 190 193 fault-tolerant multicast output-buffered

ATM switch, fault detection, 173 two-stage multicast out-put-buffered ATM

switch ŽMOBAS., 154 157, 160 163 Multiline internal capacity, input-buffered

switch, 53

Multiplane switches, space-division switching ŽSDS. architecture, 33

Multiple-path switches: architecture, 29 34

space-division switching ŽSDS., 29 34 augmented banyan switches, 30

multiplane switches, 33 recirculation switches, 33 34 three-stage Clos switches, 30 33

Multiple-QoS scalable distributed-arbitration switch ŽSDA.:

performance analysis, 236 238 structure, 234 236

Multi-protocol label switching ŽMPLS., advantages, 2

Multistage shared-memory switch, 94 96 concentrator-based growable switch

architecture, 96

Washington University gigabit switch, 94 96 Multiway search, internet protocol ŽIP. route

lookups, 381 388

binary search, best-matching prefix, 381 384 cache line exploitation, 385 388 performance analysis, 388

precomputed 16-bit prefix table, 384 385

NEC WATMnet prototype system, wireless ATM ŽWATM. switches, 341 342

Network interface card ŽNIC.: asynchronous transfer mode ŽATM.

switches, 15

internet protocol route lookups, 366 367 Network node interface ŽNNI., asynchronous transfer mode ŽATM. networks, 35

Network processor, internet protocol route lookups, 366 367

Next-generation internet ŽNGI., terabit IP routers, optical interconnection network:

complexity issues, 324 326 crosstalk analysis, 328 331 network configuration, 309 315

ping-pong arbitration ŽPPA. unit, 315 324 power budget analysis, 326 328

research issues, 301 303

router module and route controller, 306 309 terabit architecture, 303 306

Next-hop array ŽNHA., internet protocol ŽIP. route lookups, gigabit switch routers,

388 395

construction algorithm, 392 393

Next pointers ŽNP., shared-memory switch, linked list logical queues, 86 90

Nonblocking conditions:

broadcast banyan network ŽBBN., 129 Clos network switches, 255

Nonblocking switch: banyan-based switches, 105 106 internal link blocking, 17 18

three-stage Clos switches as, 31 33 Not-acknowledgment ŽNACK. signal:

multiple-QoS scalable distributed-arbitration switch ŽSDA., 236

scalable distributed-arbitration ŽSDA. switch, 229 231

tandem-crosspoint ŽTDXP. switch: delay performance, 248 251 multicasting operation, 246 unicasting operation, 243 245

NTT’s wireless ATM access, wireless ATM ŽWATM. switches, 343

OC-N multiplexer, SONET protocols, 422 423 Olivetti’s radio ATM LAN, wireless ATM

ŽWATM. switches, 342

One-shot scheduling, asynchronous transfer mode ŽATM. switches, multicast call splitting, 20 21

On-off model:

abacus switch performance, 198 199 input-buffered switch, bursty traffic and,

52 53

optical interconnection network ŽOIN., power budget analysis, 327 328

Open systems interconnection ŽOSI. reference model, asynchronous transfer mode ŽATM. networks, 35

Optical cross connect ŽOXC. system, LambdaRouter technology, 12

Optical delay line, 3M optical switch cell synchronization unit, 298 301

Optical interconnection network ŽOIN., terabit IP routers, optical packet switches: