文档介绍：MASSEY UNIVERSITY
SCHOOL OF ENGINEERING AND ADVANCED TECHNOLOGY
Engineering Project
Submitted as part requirement for (Hons).
ROUTING IN SMALL-WORKS
AMIR HOSHANG KIOUMARS
2010
SUPERVISOR
Associate Professor Stephen Marsland
Table of contents i
Summary 1
Introduction 2
Background 4
Network elements 5
Types of works 6
Storing a graph or work 7
Routing protocols 8
Distance vector algorithms 8
Link-state algorithms 8
The small-world effect 9
Making a small-work 10
Characterization of small work 11
Characteristic path length (L) 11
Clustering coefficient (C) 11
Small-work Ratio 11
Small-world routing 12
Routing metrics 13
Greedy algorithms 14
Greedy choice property  14
Optimal substructure  14
The Dijkstra’s algorithm 16
The algorithm 16
Running time 17
i
Kleinberg’s greedy algorithm 18
Development and exposition of work 19
Selecting a programming language 20
Selecting a suitable IDE (compiler) 21
Selecting the routing algorithms (RA’s) 22
Selecting metrics items for RA’s 23
Experimental design 24
The Dijkstra’s and Kleinberg’s parison results 26
Improving the Kleinberg’s greedy algorithm 36
Improve Kleinberg pseudo code 37
The modified Kleinberg’s algorithm results 42
Results 52
Analytical results 52
Statistical results 53
Extension the model to scale-works 57
Conclusions 58
The project and project proposal 59
References 62
Appendix 1: Project proposal 64
Appendix 2: Project analysis results 85
Summary
The purpose of this project was to study routing in small-works.
The objective was to collect a set parison metrics between a selected routing algorithm and a specific routing algorithm that already exist and based on these metrics, investigate:
how they work
how good they pared to others in terms of delivering data faster (time), visiting minimum number of nodes (hop counts) and optimality (shortest path)
how it would be possible to improve these algorithms either by modifying the existing ones or implemen