Optimization of Computer Networks (eBook)

Modeling and Algorithms: A Hands-On Approach

Pablo Pavón Mariño (Autor)

eBook Download: EPUB

2016
John Wiley & Sons (Verlag)
978-1-119-01333-4 (ISBN)

Infos

This book covers the design and optimization of computer networks applying a rigorous optimization methodology, applicable to any network technology.  It is organized into two parts. In Part 1 the reader will learn how to model network problems appearing in computer networks as optimization programs, and use optimization theory to give insights on them.  Four problem types are addressed systematically - traffic routing, capacity dimensioning, congestion control and topology design.

Part 2 targets the design of algorithms that solve network problems like the ones modeled in Part 1. Two main approaches are addressed - gradient-like algorithms inspiring distributed network protocols that dynamically adapt to the network, or cross-layer schemes that coordinate the cooperation among protocols; and those focusing on the design of heuristic algorithms for long term static network design and planning problems.

Following a hands-on approach, the reader will have access to a large set of examples in real-life technologies like IP, wireless and optical networks.  Implementations of models and algorithms will be available in the open-source Net2Plan tool from which the user will be able to see how the lessons learned take real form in algorithms, and reuse or execute them to obtain numerical solutions.

An accompanying link to the author's own Net2plan software enables readers to produce numerical solutions to a multitude of real-life problems in computer networks (www.net2plan.com).

Pablo Pavon Marino, Professor, Technical University of Cartaginia, Spain. Professor Pavon Marino has a PhD in telecommunications and his research interests in the past 15 years have been in network optimization and planning. He also lectures in network optimization and planning courses for computer networks. He is the author or co-author of more than 100 journals and conference papers, and he is the originator of the Net2Plan open-source initiative which includes the Net2Plan tool and public repository of algorithms and network planning resources (www.net2plan.com). He has participated in the organizing and technical committees at multiple international conferences, and he is Technical Editor of the Optical Switch and Networking Journal.

Rezensionen

?This is an exceptional textbook smoothly linking optimization theory with practical issues of computer network design?Almost all chapters contain a special section entitled ?Notes and Sources? reviewing the key literature, a set of exercises for students, and a comprehensive list of references. The book is full of useful design hints, lists of potential problems facing designers, as well as illustrative examples. Unlike many textbooks on optimization, this work smartly combines the depth of mathematical analysis with a very good understanding of practical engineering issues. One of the important added values of this book is that the code of the devised algorithms implemented in the Net2Plan tool is accessible and algorithm convergence of the case studies is illustrated in empirical tests. To sum it up, this is an excellent textbook not only for engineering students but also for researchers and practicing engineers working in the area of computer and telecommunication network design.?
-Andrzej Jajszczyk, AGH University of Science and Technology in Krakow, Poland

Textauszug

Chapter 1
Introduction

1.1 What is a Communication Network?

We are surrounded by communication networks, they are part of our life. If asked, we can easily enumerate examples of them: the fixed or mobile telephone network, the Internet, or someone's Ethernet home network would probably be the most popular answers. However, difficulties appear when we try to define the concept “communication network” more formally, without mentioning any specific network technology, looking for a definition applicable to any of them. We will start this book addressing precisely this basic question.

There are two basic elements on which networks are constructed: telecommunication systems and switching systems. A telecommunication system or “link” consists of a transmitter and one or more receivers connected through a medium that propagates the involved electromagnetic signals. Applying this definition, two telephones A and B directly connected through a bidirectional cable pair (Fig. 1.1) contain two telecommunication systems: (i) one composed of the transmitter at A, the medium A B, and the receptor at B, and (ii) another system formed by the transmitter at B, the medium B A and the receiver at A.

Figure 1.1 Two telecommunication systems

Telecommunication systems are the basis for assembling any communications service. However, no service can be reasonably built by pure aggregation of telecommunication systems. As an example, imagine we want to provide the telephone service to four users A, B, C, and D, using just “links”. To do that, we would need two telephones and one cable dedicated for each different user pair. The result would be something like Fig. 1.2.

Figure 1.2 Communication service built with dedicated telecommunication systems

The previous example illustrates that, although possible, it is not economically feasible to provide a communication service using just links. Inefficiency in Fig. 1.2 appears because each link is dedicated exclusively to a particular user pair, and is thus idle when corresponding users are not talking each other. Improving the efficiency in our example requires adding new elements to the picture that permits a link to be shared among several communications. And that is precisely where switching systems come into play.

A switching system or “node” is a device that connects telecommunication systems (links) among them, so that the information from one link can be forwarded to other. We can represent a switching system with a node with input ports and output ports, as shown in Fig. 1.3a. Each input port represents the receiver side of a link, each output port represents the transmitter side of other. The state of the switching system at a given moment is defined by the particular scheme in which input and output ports are internally connected. For instance, Fig. 1.3b represents a node configuration where information from input port 1 is forwarded to output port 2, while input port 3 is connected to output port 1.

Figure 1.3 Switching system (node)

The defining aspect to make a system like the one in Fig. 1.3 a switching system, is that it must be reconfigurable. That is, using mechanical, electronic, optical, or any other physical procedure, it should be possible to rearrange the internal connections between input and output ports, so that an outgoing link can be carrying at different moments the information received from different input links. Reconfigurability is the enabling feature to make output links become a shared resource among the input links.

Figure 1.4 helps us to illustrate how a combination of nodes an links supports a telephone service to seven users, using four nodes and seven (bidirectional) links. Naturally, a network like the one shown, requires extra elements to enable end-to-end communications. First, telephones become now a more sophisticated device, since a single telephone can be used in Fig. 1.4 to communicate with any other telephone. They are actually the sources and destinations of information. An addressing or numbering scheme is now required to identify each telephone individually, so that each user can decide the destination telephone to call to. Second, a decision on the sequence of links (route) to be traversed by each telephone call should be taken and signaled to the switching nodes that must reconfigure accordingly.

Figure 1.4 Communication network example

The previous network scheme should be enriched with the concept of multiplexed links. Previous examples have shown links as elements that can either carry one single telephone call, or otherwise be idle. In its turn, a multiplexed link is able to simultaneously carry several communications, so that the aggregated traffic can be de-aggregated again at the link receiver side. Many multiplexing technologies exist, according to the physical form in which the aggregation/deaggregation takes place, the most frequent being frequency multiplexing, time multiplexing, code multiplexing, or a combination of them. The particular multiplexing technique has no importance for the abstract network model we are pursuing. What is important, to capture the essence of multiplexing, is that links should be characterized by a link capacity, measured in arbitrary units (e.g., bits-per-second – bps – in digital links). In turn, sources should now be characterized as producers of traffic measured in the same units as the link capacities. Eventually, the link capacities become the shared resource, so that we will be able to compare the capacity of a link with the sum of the traffic of the sources traversing it.

Put together, we have identified four elements in a communication network: (i) information sources and destinations, (ii) links capable of propagating information between their end points, (iii) switching nodes capable of interconnecting links in a reconfigurable form, and (iv) addressing and signaling systems for controlling network operation.

1.2 Capturing the Random User Behavior

A characteristic aspect of communication networks is that they have to deal with the random nature of the user behavior. In Fig. 1.4 this means that we do not know beforehand who each user is willing to talk to at each moment. Random behavior is crucial for the dimensioning of resources such as link capacities in the network.

In Fig. 1.4, capacities are set so that two idle users will always be able to call each other, irrespective of what other users are doing. This is called a worst-case network dimensioning. However, this approach is clearly economically unfeasible for nontrivial scenarios. Just imagine that in Fig. 1.4 10,000 phones were connected to nodes 1 and 2. A worst-case dimensioning would need a capacity of 10,000 calls for links 1-3 and 2-3. These links would be clearly underutilized, since the probability of the two sets of 10,000 users using the phone at the same time is small.

For this reason, communication network design has been historically based on probabilistic models that characterize the random user behavior. A statistical characterization of the performances observed by the users, permits dimensioning the network resources so that the service degradation (or the probability of this to happen) becomes small enough. The statistical metrics of interest can be quite variable. However, two main alternatives appear corresponding to the two main strategies network apply for link capacity sharing: delay systems and loss systems:

• Delay systems. Delay systems typically correspond to the form in which packet switching networks operate. In packet switching networks, traffic sources split the information into fragments called packets. Each packet is attached to a header, with sufficient control information to permit the packet reach its destination. Nodes process incoming packets one by one and forward them to their corresponding output link. Link capacities are dimensioned so that the average flow of packets that traverses a link does not exceed its capacity, potentially with some safety margins. However, the random nature of packet arrival times makes that packets could find their output links busy with other packets. For this reason, nodes incorporate memories for storing packets waiting for their turn to be transmitted. The storage time or queue time is an added delay to the end-to-end communication. Moreover, traffic fluctuations can fill up these memories and force the nodes to discard packets. In these systems, the delay and the packet loss probabilities are the performance metrics of interest.
• Loss systems. Loss systems can appear in networks where the traffic takes the form of end-to-end connections. These connections can be circuits, in so-called circuit switching networks (e.g., telephone calls in the telephone network, lightpaths in WDM optical networks), or virtual circuits over packet switching networks (e.g., virtual circuits in MPLS networks). Each connection reserves a given amount of capacity in each of the traversed links. The reserved bandwidth is kept throughout the communication. If a connection request does not find a sequence of links with enough capacity, it is discarded (lost or blocked). The probability that a new connection request is blocked, or blocking probability, is the main...

Produkt-Details

• Erscheint lt. Verlag: 28.3.2016
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Informatik ► Theorie / Studium ► Algorithmen
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Themenwelt: Technik ► Nachrichtentechnik
• Schlagworte: algorithms • capacity dimensioning • Communication Technology - Networks • Computer Networks • Electrical & Electronics Engineering • Elektrotechnik u. Elektronik • Kommunikationsnetze • Modeling • network problems • Numerical Methods & Algorithms • numerical modeling • Numerische Methoden u. Algorithmen • Optimization • topology design • Traffic Routing
• ISBN-10: 1-119-01333-X / 111901333X
• ISBN-13: 978-1-119-01333-4 / 9781119013334