Second Edition Data Networks DIMITRI BERTSEKAS Massachusetts Institute of Technology ROBERT GALLAGER Massachusetts Institute of Technology PRENTICE HALL,Englewood Cliffs,New Jersey 07632
Second Ed ition Data Networks DIMITRI BERTSEKAS Massachusetts Institute of Technology ROBERT GALLAGER Massachusetts Institute of Technology PRENTICE HALL, Englewood Cliffs, New Jersey 07632
Higher layer black box communication system Module Peer processes Module Lower layer black box communication system -Lower layer peer processes- Introduction and Layered Network Architecture 1.1 HISTORICAL OVERVIEW Primitive forms of data networks have a long history,including the smoke signals used by primitive societies,and certainly including nineteenth-century telegraphy.The mes- sages in these systems were first manually encoded into strings of essentially binary symbols,and then manually transmitted and received.Where necessary,the messages were manually relayed at intermediate points. A major development,in the early 1950s,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(RJEs)(see Fig.1.1).The number of such peripheral devices expanded rapidly in the 1960s with the development of time-shared computer systems and with the increasing power of central computers.With the proliferation of remote peripheral devices,it became uneconomical to provide a separate long-distance communication link to each peripheral.Remote multiplexers or concentrators were de- veloped to collect all the traffic from a set of peripherals in the same area and to send it on a single link to the central processor.Finally,to free the central processor from handling all this communication,special processors called front ends were developed to
1 L L Higher layer black box communication system , ,. , I Module - - - - Peer processes - - - - Module I L ... " - ,.-- Lower layer black box , :;. communication system '7 I Module - - -Lower layer peer processes- -- Module I I I Introduction and Layered Network Architecture 1.1 HISTORICAL OVERVIEW Primitive forms of data networks have a long history, including the smoke signals used by primitive societies, and certainly including nineteenth-century telegraphy. The messages in these systems were first manually encoded into strings of essentially binary symbols, and then manually transmitted and received. Where necessary, the messages were manually relayed at intermediate points. A major development, in the early 1950s, 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 (RIEs) (see Fig. 1.1). The number of such peripheral devices expanded rapidly in the 1960s with the development of time-shared computer systems and with the increasing power of central computers. With the proliferation of remote peripheral devices, it became uneconomical to provide a separate long-distance communication link to each peripheral. Remote multiplexers or concentrators were developed to collect all the traffic from a set of peripherals in the same area and to send it on a single link to the central processor. Finally, to free the central processor from handling all this communication, special processors called front ends were developed to 1
2 Introduction and Layered Network Architecture Chap.1 Printer Terminal Central processor RJE Figure 1.1 Network with one central processor and a separate communication link to each device. control the communication to and from all the peripherals.This led to the more com- plex structure shown in Fig.1.2.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.While it is perfectly appropriate and widely accepted to refer to such a system as a data network or computer communication network,it is simpler to view it as a computer with remote peripherals.Many of the interesting problems associated with data networks,such as the distributed control 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. The ARPANET and TYMNET,introduced around 1970,were the first large-scale, general-purpose data networks connecting geographically distributed computer systems, users,and peripherals.Figure 1.3 shows such networks.Inside the "subnet"are a set of nodes,various pairs of which are connected by communication links.Outside the subnet are the various computers,data bases,terminals,and so on,that are connected via the subnet.Messages originate at these external devices,pass into the subnet,pass from node to node on the communication links,and finally pass out to the external recipient. 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.In some networks (e.g.,DECNET), nodes in the subnet might be physically implemented within the external computers using the network.It is helpful,however,to view the subnet nodes as being logically distinct from the external computers. It is important to observe that in Figs.1.1 and 1.2 the computer system is the center of the network,whereas in Fig.1.3 the subnet (i.e.,the communication part of the network)is central.Keeping this picture of external devices around a communication
2 Introduction and Layered Network Architecture Chap. 1 Figure 1.1 Network with one central processor and a separate communication link to each device. control the communication to and from all the peripherals. This led to the more complex structure shown in Fig. 1.2. 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. While it is perfectly appropriate and widely accepted to refer to such a system as a data network or computer communication network, it is simpler to view it as a computer with remote peripherals. Many of the interesting problems associated with data networks, such as the distributed control 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. The ARPANET and TYMNET, introduced around 1970, were the first large-scale, general-purpose data networks connecting geographically distributed computer systems, users, and peripherals. Figure 1.3 shows such networks. Inside the "subnet" are a set of nodes, various pairs of which are connected by communication links. Outside the subnet are the various computers, data bases, terminals, and so on, that are connected via the subnet. Messages originate at these external devices, pass into the subnet, pass from node to node on the communication links, and finally pass out to the external recipient. 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. In some networks (e.g., DECNET), nodes in the subnet might be physically implemented within the external computers using the network. It is helpful, however, to view the subnet nodes as being logically distinct from the external computers. It is important to observe that in Figs. 1.1 and 1.2 the computer system is the center of the network, whereas in Fig. 1.3 the subnet (i.e., the communication part of the network) is central. Keeping this picture of external devices around a communication
Sec.1.1 Historical Overview 3 Printer Multiplexer Central Front Printer processor end Terminal controller Multiplexer Figure 1.2 Network with one central processor but with shared communication links to devices. Personal computer Subnet erminal 鱼 CPU 曲型 CPU 出型 Figure 1.3 General network with a subnet of communication links and nodes.External devices are connected to the subnet via links to the subnet nodes
Sec. 1.1 Historical Overview 3 Central processor Figure 1.2 Network with one central processor but with shared communication links to devices. QI Subnet Personal computer Figure 1.3 General network with a subnet of communication links and nodes. External devices are connected to the subnet via links to the subnet nodes
Introduction and Layered Network Architecture Chap.1 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 book. The subnet shown in Fig.1.3 contains a somewhat arbitrary placement of links between the subnet nodes.This arbitrary placement (or arbitrary topology as it is often called)is typical of wide area networks(i.e.,networks covering more than a metropolitan area).Local area networks (i.e.,networks covering on the order of a square kilometer or less)usually have a much more restricted topology,with the nodes typically distributed on a bus,a ring,or a star. Since 1970 there has been an explosive growth in the number of wide area and local area networks.Many examples of these networks are discussed later,including as wide area networks,the seminal ARPANET and TYMNET,and as local area networks, Ethernets and token rings.For the moment,however,Fig.1.3 provides a generic model for data networks. With the multiplicity of different data networks in existence in the 1980s,more and more networks have been connected via gateways and bridges so as to allow users of one network to send data to users of other networks (see Fig.1.4).At a fundamental level, one can regard such a network of networks as simply another network,as in Fig.1.3, with each gateway,bridge,and subnet node of each constituent network being a subnet node of the overall network.From a more practical viewpoint,a network of networks is much more complex than a single network.The problem is that each constituent subnet has its own conventions and control algorithms (i.e.,protocols)for handling data,and the gateways and bridges must deal with this inhomogeneity.We discuss this problem later after developing some understanding of the functioning of individual subnets. Personal computer Wide-area network Subnet Local area network 型电 Terminal H坐 Local area network CPU CPU Figure 1.4 Network of interconnected networks.Individual wide area networks (WANs) and local networks (LANs)are connected via bridges and gateways
4 Introduction and Layered Network Architecture Chap. 1 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 book. The subnet shown in Fig. 1.3 contains a somewhat arbitrary placement of links between the subnet nodes. This arbitrary placement (or arbitrary topology as it is often called) is typical of wide area networks (i.e., networks covering more than a metropolitan area). Local area networks (i.e., networks covering on the order of a square kilometer or less) usually have a much more restricted topology, with the nodes typically distributed on a bus, a ring, or a star. Since 1970 there has been an explosive growth in the number of wide area and local area networks. Many examples of these networks are discussed later, including as wide area networks, the seminal ARPANET and TYMNET, and as local area networks, Ethemets and token rings. For the moment, however, Fig. 1.3 provides a generic model for data networks. With the multiplicity of different data networks in existence in the 1980s, more and more networks have been connected via gateways and bridges so as to allow users of one network to send data to users of other networks (see Fig. 1.4). At a fundamental level, one can regard such a network of networks as simply another network, as in Fig. 1.3, with each gateway, bridge, and subnet node of each constituent network being a subnet node of the overall network. From a more practical viewpoint, a network of networks is much more complex than a single network. The problem is that each constituent subnet has its own conventions and control algorithms (i.e., protocols) for handling data, and the gateways and bridges must deal with this inhomogeneity. We discuss this problem later after developing some understanding of the functioning of individual subnets. Subnet o rr=-=n IL-JI CPf7 TI, Terminal Figure 1.4 Network of interconnected networks. Individual wide area networks (WANs) and local networks (LANs) are connected via bridges and gateways
Sec.1.1 Historical Overview 5 In the future,it is likely that data networks,the voice network,and perhaps cable TV networks will be far more integrated than they are today.Data can be sent over the voice network today,as explained more fully in Section 2.2,and many of the links in data networks are leased from the voice network.Similarly,voice can be sent over data networks.What is envisioned for the future,however,is a single integrated network, called an integrated services digital network(ISDN),as ubiquitous as the present voice network.In this vision,offices and homes will each have an access point into the ISDN that will handle voice,current data applications,and new applications,all with far greater convenience and less expense than is currently possible.ISDN is currently available in some places,but it is not yet very convenient or inexpensive.Another possibility for the future is called broadband ISDN.Here the links will carry far greater data rates than ISDN and the network will carry video as well as voice and data.We discuss the pros and cons of this in Section 2.10. 1.1.1 Technological and Economic Background Before data networks are examined,a brief overview will be given,first,of the tech- nological and economic factors that have led to network development,and second,of the applications that require networks.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 primary memory; and faster,larger,less expensive bulk storage.The result has been the lowering of the cost of computation by roughly a factor of 2 every two years.This has led to a rapid increase in the number of cost effective applications for computers. On the other hand,with the development of more and more powerful microproces- sor chips,there has been a shift in cost effectiveness from large time-shared computer facilities to small but increasingly powerful personal computers and workstations.Thus, the primary growth in computation is in the number of computer systems rather than in the increasing power of a small number of very large computer systems. This evolution toward many small but powerful computers has had several effects on data networks.First,since individual organizations use many computers,there is a need for them to share each other's data,thus leading to the network structures of Figs. 1.3 and 1.4.(If,instead,the evolution had been toward a small number of ever more powerful computer systems,the structure of Fig.1.2 would still predominate.)Second, since subnet nodes are small computers,the cost of a given amount of processing within a subnet has been rapidly decreasing.Third,as workstations become more powerful, they deal with larger blocks of data (e.g..high-resolution graphics)and the data rates of present-day wide area data networks are insufficient to transmit such blocks with acceptable delay. The discussion of computational costs above neglects the cost of software.While the art of software design has been improving,the improvement is partly counterbalanced by the increasing cost of good software engineers.When software can be replicated, however,the cost per unit goes down inversely with the number of replicas.Thus
Sec. 1.1 Historical Overview 5 In the future, it is likely that data networks, the voice network, and perhaps cable TV networks will be far more integrated than they are today. Data can be sent over the voice network today, as explained more fully in Section 2.2, and many of the links in data networks are leased from the voice network. Similarly, voice can be sent over data networks. What is envisioned for the future, however, is a single integrated network, called an integrated services digital network (ISDN), as ubiquitous as the present voice network. In this vision, offices and homes will each have an access point into the ISDN that will handle voice, current data applications, and new applications, all with far greater convenience and less expense than is currently possible. ISDN is currently available in some places, but it is not yet very convenient or inexpensive. Another possibility for the future is called broadband ISDN. Here the links will carry far greater data rates than ISDN and the network will carry video as well as voice and data. We discuss the pros and cons of this in Section 2.10. 1.1.1 Technological and Economic Background Before data networks are examined, a brief overview will be given, first, of the technological and economic factors that have led to network development, and second, of the applications that require networks. 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 primary memory; and faster, larger, less expensive bulk storage. The result has been the lowering of the cost of computation by roughly a factor of 2 every two years. This has led to a rapid increase in the number of cost effective applications for computers. On the other hand, with the development of more and more powerful microprocessor chips, there has been a shift in cost effectiveness from large time-shared computer facilities to small but increasingly powerful personal computers and workstations. Thus, the primary growth in computation is in the number of computer systems rather than in the increasing power of a small number of very large computer systems. This evolution toward many small but powerful computers has had several effects on data networks. First, since individual organizations use many computers, there is a need for them to share each other's data, thus leading to the network structures of Figs. 1.3 and 104. (If, instead, the evolution had been toward a small number of ever more powerful computer systems, the structure of Fig. 1.2 would still predominate.) Second, since subnet nodes are small computers, the cost of a given amount of processing within a subnet has been rapidly decreasing. Third, as workstations become more powerful, they deal with larger blocks of data (e.g., high-resolution graphics) and the data rates of present-day wide area data networks are insufficient to transmit such blocks with acceptable delay. The discussion of computational costs above neglects the cost of software. While the art of software design has been improving, the improvement is partly counterbalanced by the increasing cost of good software engineers. When software can be replicated, however, the cost per unit goes down inversely with the number of replicas. Thus
6 Introduction and Layered Network Architecture Chap.1 even though software is a major cost of a new computer system,the increasing market decreases its unit cost.Each advance in solid-state technology decreases cost and in- creases the performance of computer systems;this leads to an increase in market,thus generating decreased unit software costs,leading,in a feedback loop,to further increases in market.Each new application,however,requires new specialized software which is initially expensive (until a market develops)and which requires a user learning curve. Thus,it is difficult to forecast the details of the growth of both the computer market and the data network market. 1.1.2 Communication Technology The communication links for wide area networks are usually leased from the facilities of the voice telephone network.In Section 2.2 we explain how these physical links are used to transmit a fixed-rate stream of binary digits.The rate at which a link transmits binary digits is usually referred to as the data rate,capacity,or speed of the link,and these data rates come in standard sizes.Early networks typically used link data rates of 2.4,4.8,9.6, and 56 kilobits/sec,whereas newer networks often use 64 kilobits/sec,1.5 megabits/sec, and even 45 megabits/sec.There are major economies of scale associated with higher link speeds;for example,the cost of a 1.5 megabit/sec link is about six times that of a 64 kilobit/sec link,but the data rate is 24 times higher.This makes it economically advantageous to concentrate network traffic on a relatively small set of high-speed links (This effect is seen in Fig.1.2 with the use of multiplexers or concentrators to share communication costs.) One result of sharing high-speed (i.e.,high data rate)communication links is that the cost of sending data from one point to another increases less than linearly with the geographic separation of the points.This occurs because a user with a long communi- cation path can share one or more high-speed links with other users(thus achieving low cost per unit data)over the bulk of the path,and use low-speed links(which have high cost per unit data)only for local access to the high-speed links. 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 several overall effects of these costs that are important. First,for wide area data networks,cost has until recently been dominated by transmission costs.Thus,it has been desirable to use the communication links efficiently, perhaps at added computational costs.As will be shown in Section 1.3,the sporadic nature of most data communication,along with the high cost of idle communication links,led to the development of packet data networks. Second,because of the gradual maturing of optical fiber technology,transmission costs,particularly for high data rate links,are dropping at an accelerating rate which is expected to continue well into the future.The capacity of a single optical fiber using today's technology is 109to 1010 bits/sec,and in the future this could rise to 1014 or more.In contrast,all the voice and data traffic in the United States amounts to about
6 Introduction and Layered Network Architecture Chap. 1 even though software is a major cost of a new computer system, the increasing market decreases its unit cost. Each advance in solid-state technology decreases cost and increases the performance of computer systems; this leads to an increase in market, thus generating decreased unit software costs, leading, in a feedback loop, to further increases in market. Each new application, however, requires new specialized software which is initially expensive (until a market develops) and which requires a user learning curve. Thus, it is difficult to forecast the details of the growth of both the computer market and the data network market. 1.1.2 Communication Technology The communication links for wide area networks are usually leased from the facilities of the voice telephone network. In Section 2.2 we explain how these physical links are used to transmit a fixed-rate stream of binary digits. The rate at which a link transmits binary digits is usually referred to as the data rate, capacity, or speed of the link, and these data rates come in standard sizes. Early networks typically used link data rates of 2.4, 4.8, 9.6, and 56 kilobits/sec, whereas newer networks often use 64 kilobits/sec, 1.5 megabits/sec, and even 45 megabits/sec. There are major economies of scale associated with higher link speeds; for example, the cost of a 1.5 megabit/sec link is about six times that of a 64 kilobit/sec link, but the data rate is 24 times higher. This makes it economically advantageous to concentrate network traffic on a relatively small set of high-speed links. (This effect is seen in Fig. 1.2 with the use of multiplexers or concentrators to share communication costs.) One result of sharing high-speed (i.e., high data rate) communication links is that the cost of sending data from one point to another increases less than linearly with the geographic separation of the points. This occurs because a user with a long communication path can share one or more high-speed links with other users (thus achieving low cost per unit data) over the bulk of the path, and use low-speed links (which have high cost per unit data) only for local access to the high-speed links. 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 several overall effects of these costs that are important. First, for wide area data networks, cost has until recently been dominated by transmission costs. Thus, it has been desirable to use the communication links efficiently, perhaps at added computational costs. As will be shown in Section 1.3, the sporadic nature of most data communication, along with the high cost of idle communication links, led to the development of packet data networks. Second, because of the gradual maturing of optical fiber technology, transmission costs, particularly for high data rate links, are dropping at an accelerating rate which is expected to continue well into the future. The capacity of a single optical fiber using today's technology is 109 to 1010 bits/sec, and in the future this could rise to 1014 or more. In contrast, all the voice and data traffic in the United States amounts to about
Sec.1.1 Historical Overview 7 1012 bits/sec.Optical fiber is becoming widespread in use and is expected to be the dominant mode of transmission in the future.One consequence of this is that network costs are not expected to be dominated by transmission costs in the future.Another consequence is that network link capacities will increase dramatically;as discussed later, this will change the nature of network applications. Third,for local area networks,the cost of a network has never been 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.The use of such me- dia and the desire to avoid relatively expensive switching have led to a local area network technology in which many nodes share a common high-speed communication medium on a shared multiaccess basis.This type of network structure is discussed in Chapter 4. 1.1.3 Applications of Data Networks With the proliferation of computers referred to above,it is not difficult to imagine a growing need for data communication.A brief description of several applications requir- ing communication will help in understanding the basic problems that arise with data networks. First,there are many applications centered on remote accessing of central storage facilities and of data bases.One common example is that of a local area network in which a number of workstations without disk storage use one or more common file servers to access files.Other examples are the information services and financial services available to personal computer users.More sophisticated examples,requiring many interactions between the remote site and the data base and its associated programs, include remote computerized medical diagnoses and remote computer-aided education. 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,automatic teller machines,inventory control systems,automated order entry systems,and word pro- cessing with a set of geographically distributed authors provide a number of examples. Weather tracking systems and military early warning systems are larger-scale examples. 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.1.1 and 1.2)or processed and stored at many points (as in Fig.1.3),there is a need for a network to collect the inputs and disseminate the outputs.In any data base with multiple users there is a problem maintaining consistency (e.g.,two users of an airline reservation system might sell the same seat on some flight).In geographically distributed systems these problems are particularly acute because of the networking delays. The communication requirements for accessing files and data bases have been increasing rapidly in recent years.Part of the reason for this is just the natural growth
Sec. 1.1 Historical Overview 7 1012 bits/sec. Optical fiber is becoming widespread in use and is expected to be the dominant mode of transmission in the future. One consequence of this is that network costs are not expected to be dominated by transmission costs in the future. Another consequence is that network link capacities will increase dramatically; as discussed later, this will change the nature of network applications. Third, for local area networks, the cost of a network has never been 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. The use of such media and the desire to avoid relatively expensive switching have led to a local area network technology in which many nodes share a common high-speed communication medium on a shared multiaccess basis. This type of network structure is discussed in Chapter 4. 1.1.3 Applications of Data Networks With the proliferation of computers referred to above, it is not difficult to imagine a growing need for data communication. A brief description of several applications requiring communication will help in understanding the basic problems that arise with data networks. First, there are many applications centered on remote accessing of central storage facilities and of data bases. One common example is that of a local area network in which a number of workstations without disk storage use one or more common file servers to access files. Other examples are the information services and financial services available to personal computer users. More sophisticated examples, requiring many interactions between the remote site and the data base and its associated programs, include remote computerized medical diagnoses and remote computer-aided education. 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, automatic teller machines, inventory control systems, automated order entry systems, and word processing with a set of geographically distributed authors provide a number of examples. Weather tracking systems and military early warning systems are larger-scale examples. 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. 1.1 and 1.2) or processed and stored at many points (as in Fig. 1.3), there is a need for a network to collect the inputs and disseminate the outputs. In any data base with multiple users there is a problem maintaining consistency (e.g., two users of an airline reservation system might sell the same seat on some flight). In geographically distributed systems these problems are particularly acute because of the networking delays. The communication requirements for accessing files and data bases have been increasing rapidly in recent years. Part of the reason for this is just the natural growth
8 Introduction and Layered Network Architecture Chap.1 of an expanding field.Another reason is that workstations are increasingly graphics oriented,and transmitting a high-resolution image requires millions of bits.Another somewhat related reason is that the link capacities available in local area networks have been much larger than those in wide area networks.As workstation users get used to sending images and large files over local area nets,they expect to do the same over wide area networks.Thus the need for increased link capacity for wide area networks is particularly pressing. Another popular application is electronic mail between the human users of a net- work.Such mail can be printed,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 mail in terms of delivery speed and flexibility. In comparison with facsimile,which has become very popular in recent years,elec- tronic mail is more economical,has the flexibility advantages above,and is in principle more convenient for data already stored in a computer.Facsimile is far more convenient for data in hard-copy form (since the hard copy is fed directly into the facsimile machine). It appears clear,however,that the recent popularity of facsimile is due to the fact that it is relatively hassle-free,especially for the occasional or uninitiated user.Unfortunately, electronic mail,and more generally computer communication,despite all the cant about user friendliness,is full of hassles and pitfalls for the occasional or uninitiated user. There is a similar comparison of electronic mail with voice telephone service.Voice service,in conjunction with an answering machine or voice mail service,in principle has most of the flexibility of electronic mail except for the ability to print a perma- nent record of a message.Voice,of course,has the additional advantage of immediate two-way interaction and of nonlinguistic communication via inflection and tone.Voice communication is more expensive,but requires only a telephone rather than a telephone plus computer. 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.Important special cases of the latter are very large problems that require supercomputers.These problems frequently require massive amounts of communication,particularly when the output is in high resolution graphic form.Present-day networks,with their limited link speeds,are often inadequate for these tasks.There are also"real-time"computational tasks in which the computer system must respond to inputs within some maximum delay.If such a task is too large for the local computer,it might be handled by a remote supercomputer or by a number of remote computers working together.Present-day networks are also often inadequate for the communication needs of these tasks. It will be noted that all the applications above could be satisfied by a network with centralized computer facilities as in Fig.1.1 or 1.2.To see this,simply visualize moving all the large computers,data bases,and subnet nodes in the network of Fig.1.3 to one centralized location,maintaining links between all the nodes previously connected. The central facilities would then be connected by short communication lines rather than long,but aside from some changes in propagation delays,the overall network would be
8 Introduction and Layered Network Architecture Chap. 1 of an expanding field. Another reason is that workstations are increasingly graphics oriented, and transmitting a high-resolution image requires millions of bits. Another somewhat related reason is that the link capacities available in local area networks have been much larger than those in wide area networks. As workstation users get used to sending images and large files over local area nets, they expect to do the same over wide area networks. Thus the need for increased link capacity for wide area networks is particularly pressing. Another popular application is electronic mail between the human users of a network. Such mail can be printed, 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 mail in terms of delivery speed and flexibility. In comparison with facsimile, which has become very popular in recent years, electronic mail is more economical, has the flexibility advantages above, and is in principle more convenient for data already stored in a computer. Facsimile is far more convenient for data in hard-copy form (since the hard copy is fed directly into the facsimile machine). It appears clear, however, that the recent popularity of facsimile is due to the fact that it is relatively hassle-free, especially for the occasional or uninitiated user. Unfortunately, electronic mail, and more generally computer communication, despite all the cant about user friendliness, is full of hassles and pitfalls for the occasional or uninitiated user. There is a similar comparison of electronic mail with voice telephone service. Voice service, in conjunction with an answering machine or voice mail service, in principle has most of the flexibility of electronic mail except for the ability to print a permanent record of a message. Voice, of course, has the additional advantage of immediate two-way interaction and of nonlinguistic communication via inflection and tone. Voice communication is more expensive, but requires only a telephone rather than a telephone plus computer. 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. Important special cases of the latter are very large problems that require supercomputers. These problems frequently require massive amounts of communication, particularly when the output is in high resolution graphic form. Present-day networks, with their limited link speeds, are often inadequate for these tasks. There are also "real-time" computational tasks in which the computer system must respond to inputs within some maximum delay. If such a task is too large for the local computer, it might be handled by a remote supercomputer or by a number of remote computers working together. Present-day networks are also often inadequate for the communication needs of these tasks. It will be noted that all the applications above could be satisfied by a network with centralized computer facilities as in Fig. 1.1 or 1.2. To see this, simply visualize moving all the large computers, data bases, and subnet nodes in the network of Fig. 1.3 to one centralized location, maintaining links between all the nodes previously connected. The central facilities would then be connected by short communication lines rather than long, but aside from some changes in propagation delays, the overall network would be
Sec.1.2 Messages and Switching 9 unchanged.Such a geographically centralized but logically distributed structure would both allow for shared memory between the computers and for centralized repair.Why, then,are data networks with geographically distributed computational and data base facilities growing so quickly in importance?One major reason is the cost and delay of communication.With distributed computers,many computational tasks can be handled locally.Even for remote tasks.communication costs can often be reduced significantly by some local 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 policies, software changes,and potential security violations of a computer utility shared with many organizations. Another advantage often claimed for a network with distributed computational facilities is increased reliability.For the centralized system in Fig.1.2 there is some truth to this claim,since the failure of a communication link could isolate a set of sites from all access to computation.For the geographically centralized but logically distributed network,especially if there are several disjoint paths between each pair of sites,the failure of a communication link is less critical and the question of reliability becomes more complex.If all the large computers and data bases in a network were centralized,the network could be destroyed by a catastrophe at the central site.Aside from this possibility,however,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 effects,there appears to be no reason why geographically distributed computational facilities are inherently more or less reliable than geographically centralized (but logically distributed)facilities.At any rate,the main focus in what follows will be on networks as in Figs.1.3 and 1.4,where the communication subnet is properly viewed as the center of the entire network. 1.2 MESSAGES AND SWITCHING 1.2.1 Messages and Packets A message in a data network corresponds roughly to the everyday English usage of the word.For example,in an airline reservation system,we would regard a request for a reservation,including date,flight number,passenger names,and so on,as a message. In an electronic mail system,a message would be a single document from one user to another.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.e.,pic- tures,figures,diagrams,etc.).we would regard a message as an image.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
Sec. 1.2 Messages and Switching 9 unchanged. Such a geographically centralized but logically distributed structure would both allow for shared memory between the computers and for centralized repair. Why, then, are data networks with geographically distributed computational and data base facilities growing so quickly in importance? One major reason is the cost and delay of communication. With distributed computers, many computational tasks can be handled locally. Even for remote tasks, communication costs can often be reduced significantly by some local 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 policies, software changes, and potential security violations of a computer utility shared with many organizations. Another advantage often claimed for a network with distributed computational facilities is increased reliability. For the centralized system in Fig. 1.2 there is some truth to this claim, since the failure of a communication link could isolate a set of sites from all access to computation. For the geographically centralized but logically distributed network, especially if there are several disjoint paths between each pair of sites, the failure of a communication link is less critical and the question of reliability becomes more complex. If all the large computers and data bases in a network were centralized, the network could be destroyed by a catastrophe at the central site. Aside from this possibility, however, 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 effects, there appears to be no reason why geographically distributed computational facilities are inherently more or less reliable than geographically centralized (but logically distributed) facilities. At any rate, the main focus in what follows will be on networks as in Figs. 1.3 and lA, where the communication subnet is properly viewed as the center of the entire network. 1.2 MESSAGES AND SWITCHING 1.2.1 Messages and Packets A message in a data network corresponds roughly to the everyday English usage of the word. For example, in an airline reservation system, we would regard a request for a reservation, including date, flight number, passenger names, and so on, as a message. In an electronic mail system, a message would be a single document from one user to another. 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.e., pictures, figures, diagrams, etc.), we would regard a message as an image. 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
