Oblivious network routing : algorithms and applications / S.S. Iyengar and Kianoosh G. Boroojeni.

Format:

Book

Contributor:

Iyengar, S. S. (Sundararaja S.)

Boroojeni, Kianoosh G., 1989-

Language:

English

Subjects (All):

Adaptive routing (Computer network management).

Physical Description:

1 online resource (xiii, 160 pages) : illustrations

Place of Publication:

Cambridge, Massachusetts : The MIT Press, [2015]

System Details:

text file

Summary:

"Our increasingly integrated world relies on networks both physical and virtual to transfer goods and information. The Internet is a network of networks that connects people around the world in a real-time manner, but it can be disrupted by massive data flows, diverse traffic patterns, inadequate infrastructure, and even natural disasters and political conflict. Similar challenges exist for transportation and energy distribution networks. There is an urgent need for intelligent and adaptable routing of network flows, and a rich literature has evolved that treats "oblivious network design." This book offers novel computational schemes for efficiently solving routing problems in unpredictable circumstances and proposes some real world applications for them. The versatile routing schemes mathematically guarantee long-term efficiency and are most appropriate for networks with non-deterministic (or oblivious) current and past states. After an introduction to network design and the importance of routing problems, the book presents mathematical tools needed to construct versatile routing schemes, emphasizing the role of linked hierarchical data structures, both top-down and bottom-up. It then describes two important applications of versatile routing schemes: a secure model for congestion-free content-centric networks (which will play a key role in the future of the Internet) and a novel approach for the distribution of green power resources on a smart electricity grid."

Contents:

Chapter 1 Introduction to Network Design 1

1.1 Single-Source Network Routing Problem 2

1.1.1 Preliminary Definitions 2

Ground Transportation Example 3

1.1.2 Edge Routing Cost 5

1.1.3 Network Routing Cost 10

1.2 General Network Routing Problem 12

Routing Cost Optimization 15

1.3 Oblivious Routing Cost Environment 16

Dynamic Approach 18

Versatile Approach 19

1.4 Fractional versus Integral Routing 20

Routing Cost of the Fractional Solution 22

Obliviousness of the Routing Cost Environment 22

1.5 Summary and Outlook 23

Exercises 24

Suggested Heading 25

Part I Mathematical Foundation 27

Chapter 2 Hierarchical Routing Tools and Data Structures 29

2.1 Preliminary Definitions 30

2.2 Hierarchical Decomposition Tree 32

2.2.1 Hierarchical Decomposition Sequence 32

2.2.2 Tree Definition 34

2.3 Hierarchical Independence Tree Type-1 36

2.3.1 Independent Set of Vertices 36

2.3.2 HIT Definition and Properties 38

2.3.3 Induced Partitions of HIT 44

2.4 Hierarchical Independence Tree Type-2 47

2.5 Hierarchical Independence Tree Type-0 51

2.6 Summary and Outlook 55

Exercises 55

Suggested Reading 57

Chapter 3 Routing Schemes in Oblivious Network Design 59

3.1 A Top-Down Versatile Routing Scheme 59

3.1.1 Routing Problem Specification 61

3.1.2 Padded Hierarchical Decomposition Sequence 61

Fakcharoenphol's Algorithm 63

3.1.3 The Routing Scheme Construction 69

Fractional Scheme 70

Integral Scheme 73

3.1.4 Routing Cost Analysis 76

Competitive Ratio of the Integra) Scheme 81

3.2 A Bottom-Up Versatile Routing Scheme 82

3.2.1 Problem Specification 83

3.2.2 Scheme Construction 84

Solution Cost Analysis 85

3.3 Summary and Outlook 89

Exercises 89

Suggested Reading 90

Part II Applications 93

Chapter 4 A Secure Versatile Model of Content-Centric Networks 95

4.1 Security Preliminaries 96

Confidentiality 96

Integrity 96

Availability 97

Privacy 97

Host-Oblivious Security Schemes 97

4.2 The Hybrid Model Description 98

Phase 0: Key Distribution 100

Phase 1: Requesting Content 101

Responding to the Request 102

Phase 3: Choosing the Supplying Device 102

Phase 4: Data Transmission 102

4.3 Message Forwarding in the Routing Nodes 103

Forwarding REQ and NOTIF 103

Forwarding REG and ACK 105

Forwarding DATA 105

4.4 Oblivious Routing Problem Specification 107

4.4.1 Definitions 107

4.4.2 Graph Representation of the Hybrid Model 108

4.4.3 Oblivious Routing Cost Environment 110

4.5 A Versatile Routing Scheme 112

Busch's Randomized Algorithm 112

4.6 Node Congestion Prevention 114

4.6.1 Preliminary Definitions 115

4.6.2 The Expected Competitive Ratio 116

4.7 Routing Cost Analysis 119

4.8 Summary and Outlook 122

Exercises 122

Suggested Reading 122

Chapter 5 Versatile Distribution of Green Power Resources 123

5.1 Introduction 124

A Residential Electricity System 124

5.2 Electricity System Reliability 127

5.2.1 Stochastic Processes 128

5.2.2 Modeling with Stochastic Processes 129

5.2.3 Reliability Analysis 131

Impact of Auxiliary Power Plants on System Reliability 132

5.3 Analysis of the Energy Distribution Cost 138

5.3.1 Global Controller 139

Step 1 140

Step 2 140

Step 3 142

5.3.2 Energy Flow Cost Function 142

Edge Cost Function 143

5.4 Cost Optimization of Energy Distribution 144

5.4.1 Computation of Energy Flow Values Using Rosen's Method 146

5.4.2 Competitive Ratio of Cost Distribution 150

5.5 Summary and Outlook 151

Exercises 151

Suggested Reading 151.

Notes:

OCLC-licensed vendor bibliographic record.

ISBN:

9780262328968

0262328968

OCLC:

927400711

Access Restriction:

Restricted for use by site license.