Based on an extremely popular short course conducted by the authors for several Fortune companies, this volume is designed to help professionals develop a deeper understanding of data networks and evolving integrated networks, and to explore today's various analysis and design tools.
KEY TOPICS: It begins with an overview of the principles behind data networks, then develops an understanding of the modeling issues and mathematical analysis needed to compare the effectiveness of different networks.
Toggle navigation. Main Data Networks 2nd Edition. Data Networks 2nd Edition Dimitri P. Computers - Networking. ISBN Your tags:. Send-to-Kindle or Email Please login to your account first Need help? Please read our short guide how to send a book to Kindle. The file will be sent to your email address. It may take up to minutes before you receive it.
The file will be sent to your Kindle account. It may takes up to minutes before you received it. Please note : you need to verify every book you want to send to your Kindle.
The major purpose of this book is to convey that con- ceptual understanding to the reader. Previous books in this field broadly separate into two major categories. The first, exemplified by Tannenbaum [Tan81] and Stallings [Sta85], are primarily descriptive in nature, focusing on current practice and selected details of the operation of various existing networks. This book, in contrast, is balanced between description and analysis.
The descriptive material, however, is used to illustrate the underly- ing concepts, and the analytical material is used to provide a deeper and more precise understanding of the concepts.
We feel that a continuing separation between description and analysis is unwise in a field after the underlying con- cepts have been developed; understanding is then best enhanced by focusing on the concepts.
The book is designed to be used at a number of levels, varying from a senior undergraduate elective, to a first year graduate course, to a more ad- vanced graduate course, to a reference work for designers and researchers in the field. The material has been tested in a number of graduate courses at M. This is followed by careful descriptions of mad- elling issues and then by mathematical analysis. Finally, the insights to be gained from the analysis are explained and examples are given to clarify the more subtle issues.
Figures are liberally used throughout to illustrate the ideas. For lower- level courses, the analysis can be glossed over; this allows the beginning and intermediate-level to grasp the basic ideas, while enabling the more advanced student to acquire deeper understanding and the ability to do research in the field. Chapter 1 provides a broad introduction to the subject and also develops the layering concept.
This layering allows the various issues of data networks to be developed in a largely independent fashion, thus making it possible to read the subsequent chapters in any desired depth including omission without seri- ously hindering the ability to understand other chapters.
Chapter 2 treats the two lowest layers of the above layering. The lowest, or physical, layer is concerned with transmitting a sequence of bits over a physical communication medium.
We provide a brief introduction to the subject which will be helpful but not necessary in understanding the rest of the text. The next layer, data link control, deals with tansmitting packets reliably over a communi- cation link. Section 2. Chapter 3 develops the queueing theory used for performance analysis of multiaccess schemes Chapter 4 and, to a lesser extent, routing algorithms Chapter 5.
Less analytical courses will probably omit most of this chapter, simply adopting the results on faith. Little's theorem and the Poisson process should be covered however, since they are simple and gready enhance under- standing of the subsequent chapters. This chapter is rich in results, often de- veloped in a far simpler way than found in the queueing literature. This simplicity is achieved by considering only steady-state behavior and by some- times sacrificing rigor for darity and insight.
Mathematically sophisticated read- ers will be able to supply the extra details for rigor by themselves, while for most readers the extra details would obscure the line of argument Chapter 4 develops the topic of multiaccess communication, including local area networks, satellite networks, and radio networks.
Less theoretical courses will probably skip the last half of section 4. Conceptually, one Bains a great deal of insight into the nature of istri algorithms in this chapter. Sapte develops the subject of routing. Along with routing tseli, which ts treated in greater depth than elsewhere in the literature.
There is also a treatment of topological design and a section on recovery from link failures. Chapter 6 deals with flow control or congestion control as it is sometimes called. The first three sections are primarily descriptive, describing first the objectives and the problems in achieving these objectives.
The last section is more advanced and analytical, weating recent work in the area. A topic that is not treated in any depth in the book is that of higher-laver protocols, namely the various processes required in the computers and devices using the network to communicate meaningfully with cach other given the capability of reliable transport of packets through the network provided by the lower layers. This topic is different in nature than the other topics covered and would have doubled the size of the book if weated in depth.
We apologize in advance for the amount of acronyms and jargon in the book. We felt it was necessary to include at least the most commonly used acronyms in the field, both to allow readers to converse with other workers in the field and also for the reference value of being able wo find out what these acronyms mean. An extensive set of problems are given at the end of each chapter except the first. They range from simple exercises to gain familiarity with the basic concepts and techniques to advanced problems extending the results in the text.
Solutions of the problems are given in a manual available to instructors trom Prentice-Hall. Each chapter contains also a brief section of sources and suggestions for further reading. Again, we apologize in advance to the many authors whose contributions have not been mentioned. The literature in the data network field is vast, and we limited ourselves to references that we found most useful, or that contain material supplementing the text.
In particular we are indebted to the many students who have used this material in courses. Their comments have helped greatly in clarifying the topics. We are equally indebted to the many colleagues and advanced graduate students who have provided detailed critiques of the various chapters. Special thanks go to our colleague Pierre Humblet whose advice, knowledge, and deep insight have been invaluable. We are also grateful to Nancy Young for typing the many revisions and to Amy Hendrikson for computer typesetting the book using the T,X system.
Where necessary, the messages were manually relayed at intermediate points. A major development, in the early s, was the use of communication links to connect central computers to remote terminals and other peripheral devices, such as printers and remote job entry points RJE see Fig. Finally, to free the central processor from handling all this communication, special processors called front ends were developed to control the communication to and from all the peripherals.
This led to the more complex structure shown in Fig. The communication is automated in such systems, in contrast to telegraphy, for example, but the control of the communication is centrally exercised at the computer. External devices are connected to the subnet via links to the subnet nodes. Many of the interesting problems associated with data networks, such as the distributed contro] of the system, the relaying of messages over multiple communication links, and the sharing of communication links between Many users and processes, do not arise in these centralized systems.
Figure 1. Outside the subnet are the various computers, data bases, terminals, etc. The nodes of the subnet, usually computers in their own right, serve primarily to route the messages through the subnet.
These nodes are sometimes called IMPs interface message processors and sometimes called switches. It is helpful, however, to view the subnet nodes as being logically distinct from the computers outside the subnet. It is important to observe that in Figs. Keeping this picture of external devices around a communication subnet in mind will make it easier both to understand network layering later in this chapter and to understand the issues of distributed network control throughout the text.
Since there has been an explosive growth in the number of data net- works. The major driving force in the rapid advances in computers, communication, and data networks has been solid state technology and in particular the development of Very Large Scale Integration VLSI. In computers, this has led to faster, less expensive processors; faster, larger, less expensive priasery memory; and facter, larger, loco expensive Lulh sturaye.
The result has been the lowering of the cost of computation by roughly a factor of two every two years. On the other hand, with the development of more and more powerful micro- processor chips, there has been a shift in cost effectiveness from large time-shared computer facilities to small, but increasingly powerful, personal computers and work stations. Thus, on the one hand, an increasing number of applications can be computerized at reasonable cost, and on the other hand, the primary growth is in the number of computer systems rather than in the increasing power of a small number of very large computer systems.
Each new application, however, requires new specialized software which is initially expensive until a market de- velops and which requires a user learning curve. Thus, it is difficult to forecast the details of the growth of the computer market and similarly of the data network market. The cost of a data link increases with the available data rate, but the increase is much less than linear in the data rate. Thus, the cost per transmitted binary symbol decreases with the data rate of the link.
It is often economically advantageous for many users to share one high-rate data link rather than having separate data links for each this effect is seen in Fig. One result of sharing high-speed i-e. This occurs because the communication path could include a short link to a shared long-distance, high- speed link and then another short link to the destination.
Estimating the cost of transmission facilities is highly specialized and complex. The cost of a communication link depends on whether one owns the facility or leases it; with leasing, the cost depends on the current competitive and regulatory situation. The details of communication cost will be ignored in what follows, but there are two overall effects of these costs that are important.
First, for wide area networks i. Thus, it is desirable to use the communication links efficiently, perhaps at added compu- tational costs. As will be shown in section 1. Second, for local area networks, the cost of a network is not dominated by transmission costs. Coaxial cable and even a twisted pair of wires can achieve relatively high-speed communication at modest cost in a small geographic area.
This type of network structure is discussed in Chapter 4. There are two important pending developments that could radically change the importance of using transmission facilities efficiently in wide area data networks. The first is the installation of high-speed optical fibers. In this case, accessing, processing, and switching at the ends of such a facility become the important problems.
Current voice telephone networks will eventually be replaced with all-digital networks, providing both telephone service and high-data-rate digital service wherever telephones now exist. A brief description of several applications requiring communication will help to understand the basic problems that arise with data networks. First, there are many applications centered on remote accessing of data bases. Simple examples are the information services and financial services available to personal computer users.
In some of these examples, there is a cost trade-off between maintaining the data base wherever it might be required and the communication cost of remotely accessing it as required. In other examples, in which the data base is rapidly changing, there is no alternative to communication between the remote sites and the central data base. Next, there are many applications involving the remote updating of data bases, perhaps in addition to accessing the data.
Airline reservation systems, auto- matic teller machines, inventory control systems, automated order entry systems. In general, for applications of this type, there are many geographically separated points at which data enter the system and often many geographically separated points at which outputs are required. Whether the inputs are processed and stored at one point as in Figs. There is also a need for considerable care to ensure that delays within the system do not give rise to faulty outputs.
Another popular application is electronic mail between the human users of 8 network. Such mail can be read, filed, forwarded to other individuals, perhaps with added comments, or read by the addressee at different locations.
It is clear that such a service has many advantages over postal mai] in terms of delivery speed and flexibility. It also has advantages over voice telephone service in terms of providing a record, reducing cost for long-distance calls , and eliminating the need for both users to communicate at the same time.
As a final application, one might want to use a remote computer system for some computational task. This could happen as a means of load sharing if the local computer is overutilized. It could also arise if there is no local computer, if the local computer is inoperational, or the remote computer is better suited to the given task. If such a task is too large for any one computer, it might be shared between remote computer systems.
Tt will be noted that all the applications above could be satisfied by a net- work with centralized computer facilities as in Figs. To see this, simply visualize moving all of the computers in a network, such as Fig.
Such a structure would both allow for shared memory between the computers and for centralized repair. Why, then, are data net- works with geographically distributed computational facilities growing so quickly in importance?
One major reason is the cost of communication. With distributed computers, many computational tasks can be handled locally. Even for the appli- cations above, the communication costs can often be reduced significantly by locel Processing. Another reason is that organizations often acquire computers for local automation tasks, and only after this local automation takes place does the need for remote interactions arise.
Finally, organizations often wish to have control of their own computer systems rather than be overly dependent on the pricing poli- cies, software changes, and potential security violations of a computer utility shared with many organizations.
Another advantage often claimed for a network with distributed computa- tional facilities is increased reliability. For the centralized system in Fig. For the network in Fig. If all the computers in a network were centralized, then the network could be destroyed by a catastrophe at the central site.
Aside from this possibility, how- ever, a central site can be more carefully protected and repairs can be made more quickly and easily than with distributed computational sites. Other than these ef- fects, there appears to be no reason why geographically distributed computational facilities are inherently more or less reliable than geogaphically centralized but logically distributed facilities.
At any rate, the main focus in what follows will be on networks as in Fig. For example, in an airline reservation system, we would regard a request, for a reservation, including date, flight number, passenger names, etc. If that same document is then forwarded to several other users, we would sometimes want to regard this forwarding as several new messages and sometimes as forwarding of the same message, depending on the context. In a file transfer system, a message would usually be regarded as a file.
In an image transmission system i. In an application requiring interactive communication between two or more users, a message would be one unit of communication from one user to another. Thus, in an interactive transaction, user 1 might send a message to user 2, user 2 might reply with a message to 1, who might then send another message to 2, and so forth until the completion of the overall transaction.
If a recipient receives only part of a message, it is usually worthless. It is sometimes necessary to make a distinction between a message and the representation of the meseage. Both in a subnet and in a computer, a message is usually represented as a string of binary symbols, 0 or 1. For brevity, a binary symbol will be referred to as a bit. When a message goes from sender to recipient, there are frequently a number of transformations on the string of bits used to represent the message.
Such a transformation is sometimes desirable for the sake of data compression and sometimes for the sake of facilitating the communication of the message through the network. A brief description of these two purposes follows. From the standpoint of information theory, a message is regarded as one of a collection of possible messages, with a probability distribution on the likelihood of different messages.
Such probabilities can only be crudely estimated either a priori or adaptively. The idea, then, is to assign shorter bit atrings to more probable messages and longer bit strings to less probable messages.
For example, with text, one can represent common letters in the alphabet: or common words in the dictionary with a small number of bits and represent unusual letters or words with more bits- As another example, in an airline reservation system, the common messages have a very tightly constrained format date, flight number, names, etc. Data compression will be discussed more in Chapter 2 in the context of compressing contro] overhead. Transforming message representations to facilitate communication, on the other hand, is a central topic for data networks.
It will also be shown that transmitting very long messages as units in a subnet is harmful in several ways including delay, buffer management, and congestion control. Thus, messages represented by long strings of bits are usually broken into shorter bit strings called packets. These packets can then be transmitted through the subnet as individual entities and reassembled into messages at the destination. The purpose of a subnet, then, is to receive packets at the nodes from sites outside the subnet, then transmit these packets over some path of communication links and other nodes, and finally deliver them to the destination sites.
The subnet must somehow obtain information about where the packet is going, but the meaning of the corresponding message is of no concern within the subnet. To the subnet, a packet is simply a string of bits that must be reliably and quickly sent through the subnet.
Why special arrangements should be made for two users to start exchanging messages is a topic for later discussion. For now, simply consider the sessions in a network at a given time as the current set of user pairs that are occasionally sending messages to each other. Thus, for a given session between user 1 and 2, for example, there is some sequence of messages that go from 1 to 2 and some sequence of messages that go from 2 to 1. From the standpoint of the users, these messages are typically triggered by particular events.
From the standpoint of the subnet, however, these message initiation times are somewhat arbitrary and unpredictable. It is reasonable, for subnet purposes, to model the sequence of times at which Messages or packets arrive for a given session as a random process. For simplicity, these arrivals will usually be modeled as occuring at random points in time, inde- Pendently of each other and of the arrivals for other sessions.
This type of arrival Process is called a Poisson process and will be defined and discussed in section 3. This model is not. However, Such simple models provide insight into the major trade-offs involved in. Since the design and implementation of g subnet is o time concuming procose, and since applications are rapidly changing and expanding, subnets must.
Any complex model of message arrivals for sessions is likely to be invalid by the time the network is used. This point of view, that subnets must be designed to work independently of the fine details of applications, will be discussed further in section 1.
At this point, we have a conceptual view, or model, of the function of a subnet, It will provide communication for a slowly varying set of sessions; within each session, messages of some random length distribution arrive at random times according to some random process. Since we will largely ignore the interaction between the two directions of message flow for a session, we shall usually model a two-way seasion as two one-way sessions, one corresponding to the message flow in one direction and the other in the opposite direction.
In what follows, we use the word session for such one-way sessions. In matters such as session initiation and end-to-end acknowledgement, distinctions are made between two-way and one-way sessions.
Although the detailed characteristics of different kinds of applications will not be examined, there are some gross characteristics of sessions that must be kept in mind. The most important are listed: 1. Message arrival rate and variability of arrivals. Typical arrival rates for ses- sions vary from one hundred arrivals per second to one arrival per many sainutes. Session holding time. Sometimes as with electronic mail a session is ini- tiated for a single message. Other sessions last for a working day or even permanently.
Expected message length and length distribution. Allowable delay. The allowable expected delay varies from about. In other applications, there is a maximum allowable delay in contrast to ea ee ie Risse a Packetized voiee, Jength segments of the incom encoded into pack- aoe the source.
At the destination, these packets must. For some applications, all messages must be delivered error free. For example, in banking applications, in transmission of computer programs, or in file transfers, a single bit error in a message can have serious conse- quences.
In other applications, such as electronic mail, all messages must be delivered, but an occasional bit error in a message can usually be visually corrected by the reader.
Finally, in other applications, both occasional bit errors and occasional loss of entire packets or messages are allowable. For example, in distributed sensor systems, messages are sometimes noisy when transmitted, and occasional lost messages are soon replaced with more up- to-date messages. For packetized voice, the occasional loss or late delivery of a packet or an occasional bit error simply increase the nojsiness of the received voice signal.
It should be noted, however, that the use of data com- pression for packetized voice and other applications greatly increases the need for error-free communication. Message and packet ordering. The packets within a message must either be maintained in the correct order going through the network or restored to the correct.
For many applications such as updating data bases , messages must also be delivered in the correct order, whereas for other applications, message order is unimportant.
This will be discussed in section 2. One is interactive terminal to computer sessions in which messages are short, message rate is low, the delay requirement is moderately stringent, and the need for reliability is high. Another is file transfer sessions in which the messages are very long, the message arrival rate is typically low, the delay requirement is very relaxed, and the need for reliability is very high.
The third is packetized voice. Here the concept of a message is not very useful, but the packets are short, the packet arrival rate is high, the maximum delay requirement is stringent, and the need for reliability is rather low.
A network that can handle all these applications together will probably not have too much difficulty with all the other applications of interest- a 1. The expected transmission time of a message is X. Thus, the link is used at most AX of the time, approach will be given, showing how it overcomes the above inefficiency. For the circuit switching approach, when a session s is initiated, it is allocated a given transmission rate r.
A path is then created from the transmitting site through the subnet and to the destination site. Each communication link on this path then allocates a portion 7, of its total transmission capability im the given direction for that session.
This allocation of transmission rates to different sessions on a communication link is usually done by time-division multiplexing TDM or frequency-division multiplexing FDM , but the details of that will be explained later.
What is important is that the sum of the transmission rates for all the sessions using a link cannot execed the total transmission rate of the link. Thus, if a communication link is fully allocated to existing sessions, a new session cannot use that link. The nodes then simply take the incoming bit stream for a given session off the incoming link and switch it to the allocated portion of the outgoing link. This is not quite as simple as it appears, but the technology for doing this is old and well established.
Circuit switching is almost universally used for telephone networks but is rarely used for data networks. Given the simplicity and well-developed technology for cireuit switching, we must ask why it is inappropriate for data networks. Let be the message arrival rate for a given session s. This argument is made precise in Chapter 3. Given this, it is easy to calculate the responses in the figure.
From Eq. This means that if this interval is much larger than the signaling interval T between successive input pulses, then significant amounts of intersymbol interference will occur. Physically, a channel cannot respond to an input before the input occurs, and therefore A t should be 0 for t 0, then integrating Eq. Finally, since Eq. One sees from Eq. Such filters can be closely approximated in practice subject to additional delay, i.
These filters can and often are used to overcome the effects of intersymbol interference. The difficulty with this argument is that the additive noise that is always present on a channel has been ignored. Noise is added to the signal at various points along the propagation path, including at the receiver. Thus, the noise is not filtered in the channel in the same way as the signal. If H Jf is very small in some interval of frequencies, the signal is greatly attenuated at those frequencies, but typically the noise is not attenuated.
The cutoff point between large and small depends on the noise level and signal level and is not. For each sample, there is one such function, centered at the sample and with a scale factor equal to the sample value. We shall not attempt. The equalization at the receiver would then be required to either equalize H f over a broader band of frequencies, thus increasing the noise, or to allow more intersymbol interference. This theorem states that if a waveform tis imi to frequencies at most W i.
The filter H' f here is the composite of the pulse-shaping filter at the transmitter, the channel filter, and the equalizer filter. It is important to recognize that the sampling theorem specifies the number of samples per second that can be utilized on a low-pass channel, but it does not specify how many bits can be mapped into one sample. Figure 2. A binary 1 is mapped into a positive Dulse followed by a negative pulse, and a binary 0 is mapped into a nesative Pulse followed by positive pulse.
0コメント