Routing and control routing and control the internet

Algorithms and Models for Network Analysis and Design

R. G. Addie

iii

CONTENTS v

4.3 Performance Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.3.1 Measurement of Loss and Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

5.1.2 Subnetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5.1.3 Routing Domains in the Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

5.1.8 IP Version 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.1.9 Load Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.2.3 State-based Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

5.3 New Approaches to Congestion Control in the Internet . . . . . . . . . . . . . . . . . . . . . . . 121

5.3.5 Random Early Dropping of In and Out Packets (RIO) . . . . . . . . . . . . . . . . . . . . 123

5.4 New Approaches to Routing in the Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

6 Requirements Analysis 133

6.1 Traffic Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

7 Architecture 141

7.1 Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

7.3.1 Philosophy of TCP/IP Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

7.3.2 Philosophy of ATM Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

7.4 Security Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

7.4.1 Key Concepts in Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

7.4.6 SSL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

7.4.7 Pretty Good Privacy (PGP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

7.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

8 Equipment Choice 167

8.3.2 Layer 1 Switching Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

9 Design 177

9.1.4 Integer Programming and Mixed Integer Programming . . . . . . . . . . . . . . . . . . . 183

9.1.5 Non-linear Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

9.5 Design Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

A Netml, A Language for Describing Networks and Traffic 203

A.5 Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

A.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

Example 6.2 A Campus Traffic Survey. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 Example 7.1 N +1 Service Protection Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Example 7.2 Service Protection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Example 7.3 IP Over IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Example 7.4 Digital Signatures and Certificates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Example 7.5 Denial of Service Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 Example 7.6 SPAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 Example 7.7 Authority in PGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Example 7.8 Secure DNS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Example 7.9 Verisign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 Example 7.10 Security in a Campus Network. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

viii CONTENTS

x CONTENTS

List of Figures

1.5 A Solution when link costs depends only on length. The labels indicate the capacity required. . . . 16

2.1 A Fully Meshed Signalling Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.6 An equivalent Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.7 An equivalent Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.12 A Network with loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.13 A Digital Cross-connect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.18 The equivalent SDH Ring Network when CD is up and ED is up . . . . . . . . . . . . . . . . . . 35

2.19 A Larger Network of SDH Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.24 Three wavelengths used to connect end-to-end a ring of 5 nodes . . . . . . . . . . . . . . . . . . 42

2.25 Five wavelengths used to connect end-to-end a ring of 6 nodes . . . . . . . . . . . . . . . . . . . 42

3.5 A laboratory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

3.6 A national ISP network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.2 A campus network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

6.3 A Table for Recording Traffic Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

7.4 CATV Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

7.5 IP Over IP Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

9.4 An Alternative Minimal Spanning Tree Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

9.5 The flow which has been allocated at the end of Step 1 of the Max-flow algorithm . . . . . . . . . 181

9.10 A Ring Network (labelled) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

9.11 A Ring Network with many rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

A.3 netml schema, Part III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

A.4 netml schema, Part IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

A.8 netml schema, Part VIII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210

A.9 An example network, described by means of netml, Part I . . . . . . . . . . . . . . . . . . . . . . 211

A.14 An example network, described by means of netml, Part VI . . . . . . . . . . . . . . . . . . . . . 216

A.15 An example network, described by means of netml, Part VII . . . . . . . . . . . . . . . . . . . . 217

2.2 Costs of network components for Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.3 Incident Traffic at each Node for Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.1 A routing table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

6.1 Some traffic streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

9.2 Comparison of Costs of Plans A and B using Year 1 dollars . . . . . . . . . . . . . . . . . . . . . 185

9.3 Table of Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

9.8 Traffic for Example , year by year . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

9.9 Required Link Capacities for Example , year by year . . . . . . . . . . . . . . . . . . . . . . . . 190

9.13 Microwave link costs and availabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

xv

Structure and conventions of this book

The book is divided into chapters, chapters into sections, and so on. Each chapter also contains a number of examples and exercises. The examples provide guidance for how to solve the exercises. A list of all exercises and examples is provided just after the table of contents.

This is a hard subject to teach and to learn, primarily because the ground is shifting beneath our feet at such a rapid rate, that the entire basis for cost-effective, practical, network design can change overnight – or that’s what it feels like anyway.

For example, take a look at the textbooks cited above. Four of these ([2, 3, 4, 7]) purport to be books about designing networks. And yet the approach in each of these books is quite different. How important is switch-ing? What is the role of ATM? What about gigabit ethernet? And how important is it to be able to analyse the performance of networks?

Probability theory is, as the name suggests, much more theoretical. In probability theory there is a great deal of work on models which do not have a great currency in day-to-day earthly existence. Statistics, on the other hand, is largely focussed on situations which do arise regularly in daily life.

Fortunately, the parts of probability theory which need to be understood in order to tackle statistics are now well understood. It is not necessary to study all of probability theory in order to become a good statistician. The aim of this book is to establish the same relationship between performance analysis and network design: to present the theory of how to analyse networks which we need in order to be practical network administrators.

Every complex problem has a simple solution which is wrong.

To find the right solution might require some deeper searching.

[2] Diane Teare, editor. Designing CISCO Networks. CISCO Press, 1999.

[3] Howard C. Berkowitz. Designing Routing and Switching Architectures for Enterprise Networks. MacMillan Technical Publishing, 1999.

Chapter 1

Overview of Network Analysis and Design

Network analysis is the science of predicting the behaviour of a network given information about the design of the network and the type of uses to which it will be put. The primary concern is with the performance of the network, by which we mean: how many messages, or packets, will be lost, what sort of delay will these messages or packets experience, and how much will these delays vary over time. Periods during which a network is unable to function correctly because of equipment failure must be taken into account in the estimation of performance. Also, failures of network security which allow the network to be used for any purpose which is “not permissible” will need to be accounted as failures of network performance.

Network design is the discipline of choosing the components out of which a network should be built, both the types of components and how many of each is needed, and how they should be put together. The goal of all the decisions concerning these components – type, quantity and placement – is to meet the prescribed standards of performance of the network in regard to loss, delay, reliability and security.

The subject matter is subdivided according to three dimensions:

3

1.2 The Network Model
Underlying the study of networks is a model that we use intuitively and quite often quite consciously to help us understand how networks work.

But what is a model? Models are used in every aspect of science. In fact, it is likely that virtually everyone uses models unconsciously as a means to guide their interaction with the world on a daily basis. A good example of a model is a map. The map shows us how the real world works, in a limited way – it shows how to get from one place to another, for example. Most of the details of the real world are omitted from the map.

In the models, we shall call these signals traffic , and our concern with them will be limited to the logical impact that the traffic has on the operation of the network, and the degree to which this traffic occupies the resources of the network, i.e. the links and the nodes.

Thus, traffic is an abstraction of the signals occupying the hardware of our network. If a link is capable of conducting messages from one point (a node – the source of the link) to another (the destination), and the transmission system sends a fixed holding pattern when such messages are not being sent, we shall regard the signals making up the messages as the traffic and the holding pattern signal as no traffic. Thus, in our model, the nodes and the links are considered to be either idle, or occupied.

We will need to introduce some additional complexities in the model later, in particular, we will need to introduce buffering, and layers. These concepts will be explained at such time as they need to be introduced and used.

1.2.1 Terminology