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