Data Management and Routing
in General Networks
Dissertation of Harald Räcke
Contents
1 Introduction 1
1.1 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Communication-efficient Data Management Strategies 5
2.1 Formal description of the problems . . . . . . . . . . . . . . . . . . . 6
2.2 Related work and new results . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Previouswork........................... 10
2.2.2 Ourresults............................. 14
2.2.3 Furtherwork ........................... 15
2.3 Hierarchy-based algorithms . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Preliminaries ........................... 15
2.3.2 The bisimulation technique . . . . . . . . . . . . . . . . . . . 16
2.3.3 The virtual tree network . . . . . . . . . . . . . . . . . . . . . 18
2.3.4 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.5 Applications............................ 25
2.3.6 Constructing the hierarchical decomposition . . . . . . . . . 35
2.4 Optimal oblivious routing . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4.1 Preliminaries ........................... 48
2.4.2 LPformulation .......................... 50
2.5 Conclusions ................................ 54
3 Cost-efficient Data Management Strategies 65
3.1 Thecostbasedmodel........................... 66
3.2 Related work and new results . . . . . . . . . . . . . . . . . . . . . . 67
3.3 The approximation algorithm for arbitrary networks . . . . . . . . . 68
3.3.1 Proper placements . . . . . . . . . . . . . . . . . . . . . . . . 71
3.3.2 The approximation algorithm . . . . . . . . . . . . . . . . . . 75
- i -
Loading more pages...