Cormode / Thottan Algorithms for Next Generation Networks

1. Auflage 2010
ISBN: 978-1-84882-765-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 462 Seiten

Reihe: Computer Communications and Networks

Data networking now plays a major role in everyday life and new applications continue to appear at a blinding pace. Yet we still do not have a sound foundation for designing, evaluating and managing these networks. This book covers topics at the intersection of algorithms and networking. It builds a complete picture of the current state of research on Next Generation Networks and the challenges for the years ahead. Particular focus is given to evolving research initiatives and the architecture they propose and implications for networking. Topics: Network design and provisioning, hardware issues, layer-3 algorithms and MPLS, BGP and Inter AS routing, packet processing for routing, security and network management, load balancing, oblivious routing and stochastic algorithms, network coding for multicast, overlay routing for P2P networking and content delivery. This timely volume will be of interest to a broad readership from graduate students to researchers looking to survey recent research its open questions.

Autoren/Hrsg.

Thottan, Marina

Cormode, Graham

Inhaltsverzeichnis

1;Endorsements;6
2;Foreword;7
3;Preface;10
4;Acknowledgements;13
5;Contents;14
6;List of Contributors;16
7;Part I Network Design;18
7.1;1 Design for Optimizability: Traffic Management of a Future Internet;19
7.1.1;1.1 Introduction;19
7.1.2;1.2 Traffic Management Today;21
7.1.2.1;1.2.1 Traffic Engineering;21
7.1.2.2;1.2.2 Pros and Cons of Traffic Management;23
7.1.3;1.3 Design Optimizable Protocols;23
7.1.3.1;1.3.1 Changing the Shape of the Constraint Set;24
7.1.3.2;1.3.2 Adding Variables to Decouple Constraints;26
7.1.3.3;1.3.3 Combining Objectives to Derive Protocols;28
7.1.4;1.4 Open Challenges in Traffic Management Optimization;30
7.1.4.1;1.4.1 Performance vs. Overhead Trade-Off;30
7.1.4.2;1.4.2 End-to-End Traffic Management;31
7.1.4.3;1.4.3 Placement of Functionality;32
7.1.5;1.5 Conclusions and Future Work;33
7.1.6;References;34
7.2;2 Valiant Load-Balancing: Building Networks That Can Support All Traffic Matrices;35
7.2.1;2.1 Introduction;35
7.2.1.1;2.1.1 The Wide Use of VLB;36
7.2.1.2;2.1.2 A Simple VLB Network;37
7.2.2;2.2 VLB in Heterogeneous Networks;38
7.2.3;2.3 Fault-Tolerance in a VLB Network;41
7.2.4;2.4 VLB for Peering Traffic;43
7.2.5;2.5 Discussions;44
7.2.6;References;45
7.3;3 Geometric Capacity Provisioning for Wavelength-Switched WDM Networks;47
7.3.1;3.1 Introduction;47
7.3.1.1;3.1.1 System Model;49
7.3.2;3.2 Wavelength-Granularity Switching;51
7.3.2.1;3.2.1 Asymptotic Analysis;52
7.3.2.2;3.2.2 Minimum Distance Constraints;53
7.3.2.3;3.2.3 Optimal Provisioning;55
7.3.2.4;3.2.4 Numerical Example;57
7.3.2.5;3.2.5 Non-IID Traffic;59
7.3.3;3.3 Conclusion;61
7.3.4;References;61
7.4;4 Spectrum and Interference Managementin Next-Generation Wireless Networks;63
7.4.1;4.1 Introduction;63
7.4.2;4.2 Review of Enabling Technologies;65
7.4.2.1;4.2.1 Contiguous and Non-contiguous Orthogonal Frequency Division Multiple Access;65
7.4.2.2;4.2.2 MIMO Signal Processing;65
7.4.3;4.3 Fractional Frequency Reuse;66
7.4.3.1;4.3.1 Concept Overview;66
7.4.3.2;4.3.2 Algorithm Overview;67
7.4.3.3;4.3.3 Algorithm Performance;69
7.4.4;4.4 Network MIMO;73
7.4.4.1;4.4.1 Algorithms;75
7.4.4.2;4.4.2 Simulation Results;78
7.4.5;4.5 Challenges in Taking Theory to Practice;79
7.4.6;4.6 Summary;80
7.4.7;References;80
7.5;5 Cross-Layer Capacity Estimation and Throughput Maximization in Wireless Networks;82
7.5.1;5.1 Introduction;82
7.5.2;5.2 Network Model;85
7.5.2.1;5.2.1 Interference Models;86
7.5.2.2;5.2.2 Network Flows;87
7.5.3;5.3 Capacity of Random Wireless Networks;88
7.5.3.1;5.3.1 Capacity Upper Bound;89
7.5.3.2;5.3.2 Lower Bound;91
7.5.4;5.4 Capacity of Arbitrary Wireless Networks;93
7.5.4.1;5.4.1 An Approximation Algorithm for MAXFLOW;93
7.5.4.1.1;5.4.1.1 Geometric Packing Based Necessary Conditions for Link Scheduling ;94
7.5.4.1.2;5.4.1.2 Inductive Scheduling Algorithm ;95
7.5.4.1.3;5.4.1.3 Link-Flow Stability: Sufficient Conditions ;96
7.5.4.1.4;5.4.1.4 Scheduling End-to-End Flows ;97
7.5.5;5.5 Dynamic Control for Network Stability;99
7.5.5.1;5.5.1 Network Layer Capacity Region;100
7.5.5.2;5.5.2 Dynamic Back-Pressure Algorithm;102
7.5.5.3;5.5.3 Analysis;103
7.5.5.4;5.5.4 Complexity Issues;105
7.5.6;5.6 Survey of Cross-Layer Throughput Estimation and Optimization in Wireless Networks;106
7.5.6.1;5.6.1 Scaling Laws for Random Networks;106
7.5.6.2;5.6.2 Estimating the Throughput Capacity;107
7.5.6.2.1;5.6.2.1 Linear Programming Techniques for Arrival Processes with Constant Bit Rate;107
7.5.6.2.2;5.6.2.2 Techniques for Admissible Stochastic Arrival Processes;108
7.5.6.2.3;5.6.2.3 Techniques for Adversarial Queuing Models;108
7.5.7;5.7 Open Problems;109
7.5.8;References;110
7.6;6 Resource Allocation Algorithms for the Next Generation Cellular Networks;114
7.6.1;6.1 Introduction;114
7.6.2;6.2 Cell Planning Problems;117
7.6.2.1;6.2.1 The Main New Factors in Planning Future Networks;119
7.6.2.2;6.2.2 On Discrete Location Problems in Combinatorial Optimization;120
7.6.2.3;6.2.3 Formulation and Background;121
7.6.2.4;6.2.4 The Interference Model;121
7.6.2.5;6.2.5 The Budgeted Cell-Planning Problem;123
7.6.2.6;6.2.6 How Well the Budgeted Cell Planning Problem (BCPP) Can Be Approximated?;123
7.6.2.7;6.2.7 The k4k-Budgeted Cell Planning Problem;124
7.6.2.8;6.2.8 An e-13e-1-Approximation Algorithm;125
7.6.2.8.1;6.2.8.1 The Client Assignment Problem;126
7.6.2.8.2;6.2.8.2 The Budgeted Maximum Assignment Problem;127
7.6.2.8.3;6.2.8.3 Approximating k4k-BCPP;128
7.6.2.9;6.2.9 The Minimum-Cost Cell Planning Problem;129
7.6.2.10;6.2.10 A Greedy O(logW)-Approximation Algorithm;131
7.6.2.11;6.2.11 Challenges and Open Problems;133
7.6.3;6.3 Cell Selection Problems;134
7.6.3.1;6.3.1 Model and Definitions;138
7.6.3.2;6.3.2 Approximating AoNDM and r-AoNDM Problems;138
7.6.3.3;6.3.3 A Cover-by-one 1-r2-r-Approximation Algorithm;139
7.6.3.4;6.3.4 Challenges and Open Problems;141
7.6.4;6.4 Concluding Remarks;142
7.6.5;References;142
7.7;7 Ethernet-Based Services for Next Generation Networks;145
7.7.1;7.1 Introduction;145
7.7.2;7.2 Carrier Ethernet Services Architecture;147
7.7.2.1;7.2.1 Ethernet Virtual Connection;148
7.7.2.2;7.2.2 Defining Ethernet Services;149
7.7.2.3;7.2.3 Ethernet Service Definitions;149
7.7.2.3.1;7.2.3.1 Ethernet Line (E-Line) Services;149
7.7.2.3.2;7.2.3.2 Ethernet LAN Services;150
7.7.2.3.3;7.2.3.3 Ethernet E-TREE Services;152
7.7.3;7.3 Ethernet Service Attributes;153
7.7.3.1;7.3.1 Ethernet Virtual Connection Type (EVC Type);153
7.7.3.2;7.3.2 Class of Service Identifier (CoS ID);156
7.7.3.2.1;7.3.2.1 Physical Port;156
7.7.3.2.2;7.3.2.2 Priority Code Point/User Priority;156
7.7.3.2.3;7.3.2.3 IP/MPLS DiffServ/IP TOS;157
7.7.3.2.4;7.3.2.4 Ethernet Control Protocols;157
7.7.3.3;7.3.3 Bandwidth Profile (BWP);157
7.7.3.4;7.3.4 Traffic Descriptors;159
7.7.3.4.1;7.3.4.1 Frame Color and Token Disposition;159
7.7.3.4.2;7.3.4.2 Frame Coloring and Frame Disposition;159
7.7.3.5;7.3.5 Performance Service Attribute;160
7.7.3.5.1;7.3.5.1 Frame Loss;160
7.7.3.5.2;7.3.5.2 Frame Delay;161
7.7.3.5.3;7.3.5.3 Frame Delay Variation;161
7.7.3.5.4;7.3.5.4 Ethernet Quality of Service;162
7.7.4;7.4 Implementing Ethernet Transport Services;163
7.7.4.1;7.4.1 Addressing Ethernet as Dedicated Network Infrastructure;163
7.7.4.2;7.4.2 Addressing Ethernet as Switched Network Infrastructure;164
7.7.4.3;7.4.3 Addressing Ethernet Connectivity Service;166
7.7.4.4;7.4.4 Addressing Ethernet as a Service Interface ;166
7.7.5;References;167
7.8;8 Overlay Networks: Applications, Coexistence with IP Layer, and Transient Dynamics;170
7.8.1;8.1 Introduction;170
7.8.1.1;8.1.1 Overlay Network Architecture;172
7.8.1.2;8.1.2 Challenges and Design Issues;173
7.8.2;8.2 Applications of Overlay Networks;174
7.8.3;8.3 Coexistence of Overlay and IP Layers;175
7.8.3.1;8.3.1 Equilibrium Behavior;176
7.8.3.2;8.3.2 Transient Behavior;176
7.8.3.3;8.3.3 Coping with Cross-Layer Interactions;178
7.8.4;8.4 Interactions Between Multiple CoexistingOverlay Networks;179
7.8.4.1;8.4.1 Interactions Leading to Suboptimal Equilibrium Point;180
7.8.4.2;8.4.2 Transient Overlay Network Protocol Interactions;180
7.8.4.2.1;8.4.2.1 Conditions for Traffic Oscillations;181
7.8.4.2.2;8.4.2.2 Analyzing Traffic Oscillations;183
7.8.4.3;8.4.3 Coping with Interactions Between Coexisting Overlays;187
7.8.5;8.5 Summary;187
7.8.6;References;188
8;Part II Network Operations;191
8.1;9 Hash-Based Techniques for High-Speed Packet Processing;192
8.1.1;9.1 Introduction;192
8.1.2;9.2 Background;193
8.1.2.1;9.2.1 Hash-Based Data Structures;194
8.1.2.1.1;9.2.1.1 Hash Functions;194
8.1.2.1.2;9.2.1.2 Bloom Filters and Their Variants;196
8.1.2.1.3;9.2.1.3 Hash Tables;200
8.1.2.2;9.2.2 Application Performance Measures and Memory Models;203
8.1.2.3;9.2.3 History of Hash-Based Techniques;205
8.1.3;9.3 Lookups in a Non-uniform Memory Model: On-Chip Summaries of Off-Chip Hash Tables;207
8.1.4;9.4 Lookups in a Uniform Memory Model: Hardware Hash Tables with Moves;211
8.1.4.1;9.4.1 The First Approach: The Power of One Move;211
8.1.4.2;9.4.2 The Second Approach: De-amortizing Cuckoo Hashing;213
8.1.5;9.5 Bloom Filter Techniques;214
8.1.5.1;9.5.1 Improved (Counting) Bloom Filters;214
8.1.5.2;9.5.2 Approximate Concurrent State Machines;217
8.1.5.3;9.5.3 More Applications of Bloom Filters;217
8.1.6;9.6 Measurement Applications Using Hash-Based Algorithms;220
8.1.6.1;9.6.1 Finding Heavy-Hitters and Flow Size Distributions;220
8.1.6.2;9.6.2 Measuring the Number of Flows on a Link;222
8.1.7;9.7 Conclusion;224
8.1.8;References;225
8.2;10 Fast Packet Pattern-Matching Algorithms;230
8.2.1;10.1 Motivation;230
8.2.2;10.2 Introduction to Regular Expressions;232
8.2.3;10.3 Traditional Regular Expression Matching Schemes;232
8.2.3.1;10.3.1 DFA;233
8.2.3.2;10.3.2 NFA;233
8.2.3.3;10.3.3 Lazy DFA;235
8.2.4;10.4 Regular Expression Matching in Network Scanning Applications;235
8.2.4.1;10.4.1 Patterns Used in Networking Applications;235
8.2.4.2;10.4.2 Analysis of Regular Expressions That Generates Large DFAs;237
8.2.4.2.1;10.4.2.1 DFAs of Quadratic Size;237
8.2.4.2.2;10.4.2.2 DFAs of Exponential Size;239
8.2.5;10.5 Regular Expression Rewriting Techniques;240
8.2.5.1;10.5.1 Rationale Behind Pattern Rewriting ;240
8.2.5.2;10.5.2 Rewrite Rules for DFAs with Quadratic Size;242
8.2.5.3;10.5.3 Rewrite Rule for DFAs of Exponential Size;242
8.2.5.4;10.5.4 Guidelines for Pattern Writers;244
8.2.6;10.6 D2FA: Algorithms to Reduce DFA Space;245
8.2.7;10.7 Bifurcated, History-Augmented DFA Techniques;247
8.2.8;10.8 Summary;249
8.2.9;References;249
8.3;11 Anomaly Detection Approaches for Communication Networks;250
8.3.1;11.1 Introduction;250
8.3.2;11.2 Discrete Algorithms for Network Anomaly Detection;252
8.3.2.1;11.2.1 Heavy-Hitter Detection;253
8.3.2.2;11.2.2 Heavy-Change Detection;255
8.3.3;11.3 Statistical Approaches for Network Anomaly Detection;257
8.3.3.1;11.3.1 Model-Based Detection;258
8.3.3.1.1;11.3.1.1 Change-Point Detection;258
8.3.3.1.2;11.3.1.2 Kalman Filter;259
8.3.3.2;11.3.2 Model-Based Learning – Approximating an Assumed Model;259
8.3.3.2.1;11.3.2.1 Covariance Matrix Analysis;259
8.3.3.2.2;11.3.2.2 Wavelet Analysis;260
8.3.3.2.3;11.3.2.3 Information Theoretic Approaches;261
8.3.3.3;11.3.3 Statistical Learning for Anomaly Detection;262
8.3.3.3.1;11.3.3.1 Unsupervised Anomaly Detection;263
8.3.3.3.2;11.3.3.2 Learning with Additional Information;268
8.3.4;11.4 Challenges and Deployment Issues;269
8.3.5;References;270
8.4;12 Model-Based Anomaly Detection for a Transparent Optical Transmission System;273
8.4.1;12.1 Introduction;273
8.4.2;12.2 Background on Raman-Amplified Transmission Systems;275
8.4.3;12.3 Establishing Baseline Distributions for Alarm Decision Rules;277
8.4.3.1;12.3.1 The Ripple Measure as a Performance Metric;278
8.4.3.1.1;12.3.1.1 Prediction of Ripple via Simulation;278
8.4.3.2;12.3.2 Issues in Using Simulation to Generate Null Distributions;279
8.4.3.3;12.3.3 Experimental Design;279
8.4.3.4;12.3.4 Simulation Results & ANOVA;281
8.4.3.5;12.3.5 Derivation of Alarm Decision Rules;285
8.4.4;12.4 Anomaly Detection Using the Detailed Physical Model;287
8.4.4.1;12.4.1 Calibration Procedure for Detailed Physical Model;289
8.4.4.2;12.4.2 Detection of Poor Fit to Raman Gain Profile;290
8.4.4.3;12.4.3 Detection of Premature Signal Degradation and Pump Failure;291
8.4.5;12.5 Anomaly Detection Using the R-Beta Model;292
8.4.6;12.6 Conclusions;295
8.4.7;References;296
8.5;13 In-Network Monitoring;297
8.5.1;13.1 Introduction;298
8.5.2;13.2 Basic Monitoring Techniques and the Cost of Monitoring;299
8.5.3;13.3 End-to-End Aggregate QoS Monitoring;301
8.5.3.1;13.3.1 Autonomous Monitoring of Streams;303
8.5.3.1.1;13.3.1.1 Single Flow Analysis;305
8.5.3.2;13.3.2 Simulation Results;307
8.5.3.2.1;13.3.2.1 Single Flow Simulations;307
8.5.3.2.2;13.3.2.2 Multiple Flow Simulations;309
8.5.4;13.4 Continuous Monitoring of Network-Wide Aggregates;312
8.5.4.1;13.4.1 The Problem;314
8.5.4.2;13.4.2 Data Structures;314
8.5.4.3;13.4.3 The Execution Model;315
8.5.4.4;13.4.4 Ancillary Functions;315
8.5.4.5;13.4.5 The Algorithm;316
8.5.5;13.5 Refinements of the Generic Protocol for Tree-Based Aggregation;317
8.5.5.1;13.5.1 Continuous Monitoring of Aggregates with Performance Objectives;318
8.5.5.1.1;13.5.1.1 Problem Statement;318
8.5.5.1.2;13.5.1.2 Filter Computation;318
8.5.5.1.3;13.5.1.3 Evaluation Results;319
8.5.5.1.4;13.5.1.4 Related Work;321
8.5.5.2;13.5.2 Efficient Detection of Threshold Crossing;321
8.5.5.2.1;13.5.2.1 Problem Statement;321
8.5.5.2.2;13.5.2.2 Local Threshold and Hysteresis Mechanism;321
8.5.5.2.3;13.5.2.3 Local Threshold Recomputation;323
8.5.5.2.4;13.5.2.4 Evaluation Results;324
8.5.5.2.5;13.5.2.5 Related Work;325
8.5.6;References;326
8.6;14 Algebraic Approaches for Scalable End-to-End Monitoring and Diagnosis;328
8.6.1;14.1 Introduction;328
8.6.2;14.2 Related Work;331
8.6.2.1;14.2.1 End-to-End Monitoring;331
8.6.2.2;14.2.2 End-to-End Diagnosis;331
8.6.3;14.3 Models and Architecture;333
8.6.3.1;14.3.1 Algebraic Model;334
8.6.3.2;14.3.2 System Architecture;336
8.6.4;14.4 Tomography-Based Overlay Monitoring System (TOM);337
8.6.4.1;14.4.1 Measurement Path Selection;337
8.6.4.2;14.4.2 Path Loss Rate Calculations;337
8.6.5;14.5 Least-Biased End-to-End Network Diagnosis System;338
8.6.5.1;14.5.1 Minimal Identifiable Link Sequence;338
8.6.5.2;14.5.2 MILSes in Undirected Graphs;340
8.6.5.3;14.5.3 MILSes in Directed Graphs;341
8.6.5.3.1;14.5.3.1 Special Properties for Directed Graphs;341
8.6.5.3.2;14.5.3.2 Practical Inference Methods for Directed Graphs;342
8.6.6;14.6 Evaluations;343
8.6.6.1;14.6.1 Scalability Analysis;344
8.6.6.1.1;14.6.1.1 Explanation from Internet Topology;346
8.6.6.2;14.6.2 Internet Experiments;346
8.6.6.2.1;14.6.2.1 Granularity of MILSes and Diagnosis;346
8.6.7;14.7 Conclusions;347
8.6.8;References;348
9;Part III Emerging Applications;350
9.1;15 Network Coding and Its Applications in Communication Networks;351
9.1.1;15.1 Introduction;351
9.1.1.1;15.1.1 Motivation;351
9.1.1.2;15.1.2 Related Work;354
9.1.2;15.2 Network Coding Fundamentals;354
9.1.2.1;15.2.1 Network Model;354
9.1.2.2;15.2.2 Encoding Model;356
9.1.2.3;15.2.3 Coding Advantage;358
9.1.3;15.3 Algebraic Framework;358
9.1.4;15.4 Required Field Size;363
9.1.5;15.5 Random Network Coding;366
9.1.6;15.6 Polynomial-Time Algorithm;367
9.1.7;15.7 Network Coding in Undirected Networks;371
9.1.8;15.8 Practical Implementation;373
9.1.8.1;15.8.1 Peer-to-Peer Networks;375
9.1.8.2;15.8.2 Wireless Networks;377
9.1.9;15.9 Conclusion;379
9.1.10;References;379
9.2;16 Next Generation Search;381
9.2.1;16.1 Introduction;381
9.2.2;16.2 Search in the Web;383
9.2.2.1;16.2.1 Text-Based Web Search;383
9.2.2.2;16.2.2 Link-Based Web Search;385
9.2.2.2.1;16.2.2.1 PageRank;385
9.2.2.2.2;16.2.2.2 HITS;386
9.2.3;16.3 Distributed Search;387
9.2.3.1;16.3.1 BlockRank;388
9.2.3.2;16.3.2 Distributed Computation of Ranking Scores;390
9.2.3.2.1;16.3.2.1 ServerRank;390
9.2.3.2.2;16.3.2.2 SiteRank;390
9.2.3.3;16.3.3 The JXP Method for Robust PageRank Approximation;391
9.2.3.3.1;16.3.3.1 Optimization: Light-Weight Merging of Local Graphs;393
9.2.3.3.2;16.3.3.2 Convergence Analysis;393
9.2.4;16.4 Social Search;394
9.2.4.1;16.4.1 Structure of Social Networks;395
9.2.4.2;16.4.2 Navigating in Small-World Graphs;396
9.2.4.3;16.4.3 Search in Social Tagging Systems;398
9.2.5;16.5 Other Topics;400
9.2.5.1;16.5.1 Searching the Live Web;400
9.2.5.1.1;16.5.1.1 Blog Search;400
9.2.5.1.2;16.5.1.2 News Search;403
9.2.5.2;16.5.2 Searching with Context;405
9.2.6;16.6 Conclusions;406
9.2.7;References;406
9.3;17 At the Intersection of Networks and Highly Interactive Online Games;410
9.3.1;17.1 Introduction;410
9.3.1.1;17.1.1 Game Genres;411
9.3.1.2;17.1.2 Communication Models;412
9.3.1.3;17.1.3 Potential for Collateral Damage;413
9.3.1.4;17.1.4 Chapter Outline;414
9.3.2;17.2 Phases of Network Activity Caused by First-Person Shooter Games;415
9.3.2.1;17.2.1 Server Discovery;415
9.3.2.2;17.2.2 Game Play;416
9.3.2.3;17.2.3 Content Download;416
9.3.3;17.3 Sensitivities of Game Players to Network Latency;417
9.3.3.1;17.3.1 Observed Impact of Latency;417
9.3.3.2;17.3.2 Mitigating Latency;418
9.3.4;17.4 Server Discovery Protocols;419
9.3.4.1;17.4.1 Counterstrike:Source Server Discovery;419
9.3.4.2;17.4.2 Reducing Probe Traffic during Counterstrike: SourceServer Discovery;422
9.3.4.2.1;17.4.2.1 Clustering, Calibration, and Optimized Probing;423
9.3.4.2.2;17.4.2.2 Illustrating AS-Based Optimization;424
9.3.4.2.3;17.4.2.3 Implementation Issues for AS-Based Optimization;425
9.3.4.3;17.4.3 Impact of Access Links on Server RTT Estimation;426
9.3.5;17.5 Measuring and Synthesizing Long- and Short-Term Traffic Patterns;428
9.3.5.1;17.5.1 Long-Timescale Game-Play and Server-Discovery Traffic;429
9.3.5.2;17.5.2 Short-Timescale Game-Play Traffic;431
9.3.5.3;17.5.3 Synthesizing Large Numbers of Players;433
9.3.5.4;17.5.4 Short-Timescale Server Discovery Traffic;435
9.3.6;17.6 Detection of Live Game Traffic;436
9.3.7;17.7 Conclusion;438
9.3.8;References;439
9.4;18 Wayfinding in Social Networks;442
9.4.1;18.1 Introduction;442
9.4.2;18.2 The Small-World Phenomenon;443
9.4.3;18.3 Kleinberg's Small-World Model: the Navigable Grid;445
9.4.4;18.4 Geography and Small Worlds;448
9.4.5;18.5 Variable Population Density and Rank-Based Friendship;451
9.4.6;18.6 Going Off the Grid;454
9.4.6.1;18.6.1 Non-Grid-Based Measures of Similarity;454
9.4.6.2;18.6.2 Simultaneously Using Many Different Notions of Similarity;456
9.4.6.3;18.6.3 From Birds of a Feather to Social Butterflies (of a Feather);457
9.4.7;18.7 Discussion;458
9.4.8;References;461
10;Index;464