IEN 184 ISSUES IN INTERNETTING PART 1: MODELLING THE INTERNET Eric C. Rosen Bolt Beranek and Newman Inc. May 1981 IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen ISSUES IN INTERNETTING PART 1: MODELLING THE INTERNET 1. Modelling the Internet This is the first in a series of papers which attempt to deal with the problems of internetting in a comprehensive manner. By "internetting", we mean the establishment of data communications among some set of host computers which cannot all access the SAME data communications network (though we will, of course, require that each host be on some particular data communications network). The traditional approach to getting data from a host on one network to a host on another is to pass the data through an intermediate, or "gateway", host, which is a host on both networks. As we shall see, however, building an internet which is sufficiently robust, and which offers sufficiently high performance, to be useful in day-to-day data communications operations involves much more than simply pasting networks together in a pairwise manner. Rather, it requires us to build an entirely new network, which can be regarded as being hierarchically "above" the existent data communications networks. We shall see that building this new network is no simple task, but that it raises all the same issues that one must deal with in building any sort of data communications network. Our basic approach will be to consider SYSTEMATICALLY the ways in which an internet is and is not similar to "ordinary" data communications - 1 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen networks, so that we can easily see how the knowledge we have gained from studying such networks (in particular, the ARPANET) can be applied to internetting. This paper will present a model for the internet which will help us to organize the issues; further papers will deal more explicitly with such issues as internet access, addressing, routing, and congestion control. 1.1 The Model Described We begin by introducing a very general model for a class of abstract entities called NETWORK STRUCTURES. A Network Structure consists of three kinds of entities: SWITCHES, PATHWAYS, and HOSTS. When we say that a particular entity is a Host WITHIN SOME PARTICULAR NETWORK STRUCTURE, we mean that within that Network Structure it functions as a data sink and/or source, and does not perform such functions as store-and-forwarding traffic which originated elsewhere and is destined for elsewhere. By saying that a certain entity is a Switch WITHIN A PARTICULAR NETWORK STRUCTURE, we mean that, within that Network Structure, it is responsible for store-and-forward functions, i.e., for receiving data from a source Host, and sending it (possibly through a sequence of intermediate Switches) into a destination Host. A Pathway WITHIN A PARTICULAR NETWORK STRUCTURE is a communications path which has as one endpoint a Switch of the Network Structure, as its other endpoint either a Switch or a Host of that Network Structure, and NO intermediate Switches of that Network Structure. - 2 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen It is important to understand that the notion of a Network Structure is intended to be an abstraction which we use in order to impose a conceptual organization on a set of physical entities. It makes no sense simply to ask of some particular computer, is it a Host or a Switch, unless one also references some particular Network Structure. Saying that a computer is, e.g., a Switch, attributes to it a certain functionality relative to a certain Network Structure. A particular computer might well be a Switch in one Network Structure while simultaneously being a Host within another Network Structure. (We will capitalize the terms "Host," "Switch," "Pathway," and "Network Structure" as a reminder of the abstract nature of these terms.) Let's look at some examples. The ARPANET can be regarded as a Network Structure whose Switches are the IMPs, whose Pathways are the telephone lines that connect the IMPs, as well as the 1822 and VDH lines, and whose Hosts are the devices connected to the IMPs via either the 1822 or VDH interfaces. From the perspective of this Network Structure, the Pathways (telephone lines) have no internal structure, but rather are merely a passive and transparent medium. When we say that the Pathways have no internal structure, we mean simply that they contain no intermediate Switches (i.e., IMPs) and no Hosts of the particular Network Structure (the ARPANET) under discussion. Of course, this is quite a significant abstraction. What we regard as a simple wire (a telephone line) may in fact be no wire at all, but - 3 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen an entire network, the telephone network! Within the telephone network, there may be any number of fancy computer switching devices, which might be just as complicated as the ARPANET's IMPs. From the perspective of the telephone company, one might want to regard each telephone line as a Network Structure, which contains exactly two Hosts (viz., the two IMPs at the end-points of the line). The Switches of this Network Structure are the telephone switching devices, and the Pathways really are just wires. Or, if we had reason to, we could regard the ARPANET as a sort of hybrid Network Structure, whose Switches included both the IMPs and the telephone company switching devices, and whose Pathways were wires terminating either at the IMPs or the other switching devices. As it happens, we generally don't find this last means of conceptual organization to be very useful. Since we have no control over, and little information about, the telephone company switching devices, it is most "convenient" not to have to think about them, but rather to just regard each telephone line as a simple Pathway, with no internal structure, and no intermediate Switches. It is important to understand that calling the ARPANET a Network Structure whose Switches are IMPs and whose Pathways are telephone lines does not beg any questions about how the telephone network really works; it is just a matter of imposing a conceptual organization that we find useful for some purpose. - 4 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen Of course, the telephone lines are not the only Pathways in the ARPANET. Each (local or distant) host is also the endpoint of a Pathway, though one which really is a wire. In general, we will find it useful to distinguish those Pathways in a Network Structure which connect Host to Switch (ACCESS PATHWAYS) from those which connect Switch to Switch (INTERNAL PATHWAYS). Another example of a Network Structure is one whose Switches are the gateways on the ARPA Catenet, whose Pathways are segments of ARPA-controlled networks, and whose Hosts are hosts on the networks which are part of the Catenet. Within this Network Structure, the gateways must be regarded as Switches, since they perform store-and-forward functions, and data from one host to another is routed through a sequence of gateways. Of course, a gateway, while a Switch within the Network Structure of the Catenet, may also be a Host within the Network Structure of the ARPANET. The proper classification of an entity is a matter of what function it performs within the concrete realization of some particular Network Structure; the same physical entity may perform different functions in different Network Structures of which it is a part. We should be a bit more precise about the Pathways of the Catenet Network Structure. Suppose there are 4 gateways on the ARPANET. Then the gateways are fully connected through a set of 12 distinct Pathways (i.e., each gateway has a Pathway to each of - 5 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen the other 3 gateways). Although each of the 12 Pathways utilizes the ARPANET, we really have 12 distinct Pathways, each of which has different characteristics as regards delay, throughput, and operability. That is why we said above that the Pathways of the Catenet should be identified with SEGMENTS of ARPA-controlled networks, rather than with the entire networks. Furthermore, each of the 4 Gateways has a distinct Pathway to EACH host on the ARPANET. That is, within the Network Structure of the Catenet, each of the hosts on the ARPANET (all of which are also Hosts on the internet) is MULTI-HOMED to each of the 4 Gateways via a distinct Pathway. IN PRINCIPLE, THIS MULTI-HOMING IS NO DIFFERENT THAN THE MULTI-HOMING OF A SINGLE (LOGICALLY ADDRESSED) HOST TO TWO DIFFERENT ARPANET IMPS (see IEN 183). As we shall see, regarding all the Hosts on the Catenet as being multi-homed to the Switches (i.e., gateways) of the Catenet is a very important feature of the network architecture we will propose for internetting. We will argue that many of the problems encountered in the current Catenet configuration are a result of the failure to properly conceive internet hosts as being multi-homed, and that the lessons learned from a study of how to do multi-homing on individual packet-switching networks can be applied fairly directly. The "Network Structure" model is intended to be completely general. We can, for example, handle an arbitrarily nested hierarchical internet by establishing a Network Structure whose - 6 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen Pathways are themselves complex internet configurations. We can also model overlapping internet configurations. Consider, for example, four machines, A, B, C, and D connected in order in a ring. In principle, we could treat this as two Network Structures, one in which A and C are Switches and B and D are Hosts, and another in which B and D are Switches and A and C are hosts. This might be useful if, for example, we have two different internets, with incompatible gateways, connecting the same set of packet-switching networks. The model should be general enough to accommodate complex configurations like this. 1.2 Deficiencies of the Old Model The idea that the design of an architecture for the internet should be guided by the development of an abstract model is hardly original. The earliest IENs often considered the need for a model, but the discussion there seems to be at an insufficient level of abstraction. That is, there is much discussion of the need for a "model of a gateway," but no discussion of the need for a model of the internet as a gestalt, with a network architecture of which the gateways are only a part. It is apparent though that gateway designers and implementers did work with an IMPLICIT model of the internet in mind. While the gateway was the focus of much discussion, however, little critical attention was focussed on the implicit model of the internet itself. This implicit model represents the - 7 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen gateways as ordinary network nodes, and the component networks of the internet as ordinary network lines. Surprisingly, hosts are not represented at all in this model. (One may be tempted to think of a host as a sort of piece of one of the "lines" in this model, but remember that the lines are not supposed to have any internal structure.) The internet routing problem was conceived of as the problem of how to get data from one gateway through a sequence of intermediate gateways to a destination network (which, in the model, is a destination line!?). Our experience with the Catenet should have made it quite clear by now that the basic idea underlying this implicit model is overly simplistic. This basic idea is that the end-user will know what network his destination host is attached to, and only needs the gateways to get his data somewhere or other (it doesn't matter where) on that destination network. At that point, the destination network is supposed to take over, and there is no further work for the gateways to do. We now know, of course, that things are not so simple. The way in which the gateways get traffic to the destination network may be very important. A particular host on a particular network might be reachable from one gateway on that network, but not from another gateway on that network. (This is the "partitioned net" problem.) Or performance considerations might dictate that a host be reached through one gateway in preference to another gateway on that same net. It should not be any surprise that this sort of problem has - 8 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen proved very troublesome in the Catenet, for the problem is built right into the conceptual mechanism that guided the development of the Catenet. The fact that the old implicit model of the internet contains no representation at all of hosts makes it virtually impossible for gateways that were built with that model in mind to have any means of representing host-specific information. It also makes it virtually impossible to take advantage of (or even to take cognizance of) the way in which Hosts can be regarded as being "multi-homed" to the gateways. Failure to model the hosts also makes it difficult to handle the case of hosts which are not always connected to the same network (e.g., "mobile hosts"), or hosts which are connected to two or more networks. Further difficulties arise from the way in which networks are represented as "lines." If a network is like a line, then it must be either up or down. There is no way to represent the fact that some "parts" of the "line" can be reached from only one end-point, but not the other. That is, it is difficult to make the internet system respond to peculiarities in the behavior or operational status of the underlying packet-switching networks, since much of that behavior has no analog in the world of telephone lines. Of course, it cannot really be claimed that problems like these can never be resolved at all within the current Catenet configuration, but only that possible resolutions will not fit easily into the Catenet's architecture, and so will - 9 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen generally appear to be "kludges" or "hacks" which are grafted on in order to get around particular operational problems as they happen to arise. Perhaps a reading of some of the more recent IENs will bear out this impression. In attacking the old implicit internet model, we are not simply trying to beat a dead horse, or to attack a straw man. Rather, we are just trying to emphasize that the way in which one initially models or thinks of a set of related problems will necessarily have a large effect on the way the problems are dealt with in the final system. A good model for the internet should provide a framework for discussion of internetting issues which enables us to place each issue in proper perspective, and which makes clear the inter-relationships among the various problems and proposed solutions to them. When important problems (such as the "partitioned net" problem) cannot even be stated in the terms of a particular model, it becomes clear that that model does not provide a proper framework for the discussion of the issues. A good model should also make it possible to evaluate the effect of various schemes as part of an integrated system, making it easier to determine whether or not some proposed scheme gives rise to more problems than it solves. By allowing us to see solutions to particular problems as part of an integrated system, the model also gives us a means of choosing among different schemes which seem to solve the same problem, since some of those schemes may fit more easily or more naturally into the integrated system than - 10 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen do others. A good model should also suggest solutions to problems that have previously seemed very vexing (we shall argue, in subsequent papers of this series, for example, that representing hosts as being multi-homed to gateways suggests certain addressing schemes that might otherwise be overlooked, and also subsumes a number of problems previously thought unrelated under a common rubric). We believe that the model we proposed in the previous section offers a much more coherent framework; hopefully this will become apparent as we begin to work through the issues of internetting in this and subsequent papers. 1.3 The Importance of Pathway Characteristics As we have already pointed out, the proposed new model of the internet as a Network Structure allows us to see the ARPANET itself as an internet, built upon pieces of the telephone network. In principle, then, the ARPANET is no different than the Catenet, which is an internet built upon pieces of the ARPANET, SATNET, and various other ARPA-controlled networks. Yet it does seem that the Catenet poses problems which are more difficult and less tractable than are the problems posed by the ARPANET. Why should this be the case, if the ARPANET and the Catenet are both internets of a sort? The answer seems to lie in the characteristics of the individual networks that constitute the Pathways in these two different "internets." The pieces of - 11 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen the telephone network which transmit data within the ARPANET do so with well-known and well-understood (indeed, with constant) delay characteristics. The capacity of these pieces of the telephone network is also a constant. Many of the ARPANET's protocols and algorithms (both internally and at the host access level) make use of these facts, and break down when applied to Pathways of significantly different characteristics. Even within the ARPANET, we have seen the importance of modifying our protocols and algorithms to take account of differing Pathway characteristics. For example, the line up/down protocol which each pair of neighboring IMPs runs together to determine the operational status of the line connecting them must be tuned differently for lines of differing bandwidths or propagation delays. Particular difficulty has been encountered in making this protocol work properly over "line 77," the "transparent" connection via SATNET to London. One problem in trying to extend ARPANET-like protocols and algorithms to the Catenet environment is to come to a better understanding of how those protocols and algorithms actually depend on assumptions about the Pathway characteristics. Since many of these assumptions may be implicit, and nowhere clearly stated, this is not a simple problem. As we develop our proposed internet architecture, we will try to emphasize the role played by assumptions about Pathway characteristics. - 12 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen (Although we will be primarily concerned with protocols and algorithms to be used in the actual day-to-day operation of the internet, it is worth noting that the variability of the Pathway characteristics of the internet also has implications with respect to the topological layout of the internet. When designing the topology of a packet-switching network, one often makes use of mathematical tools (often automated) for optimizing the topology with respect to some cost-function, such as delay. These mathematical tools are based on particular mathematical models of networks which in turn are based on results from queuing theory which assert a particular relationship between delay and load over telephone lines. Whatever the merits of those mathematical models (and there is much to question in them), they will not be applicable at all to the topological design of the internet. When a Pathway is a packet-switching network, rather than a telephone line, it is probably meaningless even to ask what its bandwidth is, since it just does not have a constant bandwidth. That is, the maximum throughput that can be obtained between two gateways over a particular packet-switching network will vary quite a bit over time, and will depend on what happens to be going on within that network. In addition, the relationship between delay over a packet-switching network and the offered load is much more difficult to model mathematically than is the same relationship over a telephone line. Issues of how to properly lay out the topology of the internet to obtain - 13 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen best performance or least "cost" probably will not be able to be dealt with in any systematic way until we have much more experience with day-to-day internet operations.) The gateways which are currently deployed on the Catenet do not seem to take Pathway characteristics into account at all. Certainly there has been no attempt to optimize the gateways to the particular packet-switching networks that they are connected to, or even to make the gateways take proper notice of the various protocol messages that the networks will send to the gateways. To some extent, gateways really do seem to treat packet-switching networks as mere wires, simply throwing the bits at the network interface, and not dealing with the various exception states that continually arise when attempting to access a network. One of the main themes that we shall be developing is that A ROBUST AND HIGH-PERFORMANCE NETWORK STRUCTURE JUST IS NOT POSSIBLE UNLESS THE SWITCHES ARE CAREFULLY TUNED TO MAKE THE MOST EFFICIENT POSSIBLE USE OF THE PATHWAYS. As we have stated above, the ARPANET IMPs often have to be tuned to the particular characteristics of different telephone lines, and it is that much more important for the gateways to be tuned to the particular characteristics of the packet-switching networks that serve as Pathways between them. It is important to understand that this sort of issue does not apply only to the way in which gateways use the INTERNAL PATHWAYS of the internet, but also to the way in which hosts and gateways use the ACCESS PATHWAYS of the internet. - 14 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen We will develop these issues in much more detail in subsequent papers. We have claimed that the only reason we tend to regard the telephone network as a Pathway with no internal structure is that we find it "convenient" to do so. If we are going to properly apply the Network Structure model to the ARPANET, the Catenet, or any other networking or internetting environment, it is important to come to a clear understanding of just when it is and is not "convenient" or "useful" to ignore the internal structure of a communications medium, and model it as a Pathway. (Though ignoring the internal structure of a communications medium is NOT the same thing as ignoring its delay/throughput/reliability characteristics; as we shall repeatedly emphasize, there are no conditions under which it is possible to do that without incurring extreme penalties in efficiency and/or reliability.) There are basically two good reasons why we might want to ignore the internal structure of a communications medium: 1) Efficiency. Some algorithms or protocols in the Network Structure may need to be driven off some sort of model or representation of the network. For example, the SPF routing algorithm in the ARPANET has a database which represents the network topology. (We will often use the term "SPF routing" to refer to the ARPANET's current routing algorithm [1,2], in contradistinction to the - 15 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen ARPANET's original routing algorithm [3]. The Catenet's current routing algorithm is based on the original ARPANET routing algorithm, but internetters should be aware that that algorithm had a number of serious deficiencies, especially under heavy load, and was removed from the ARPANET over two years ago, to be replaced with SPF routing.) Dividing a single network into several different Network Structures, and representing some of those as Pathways with no internal structure, may be necessary if we need to keep a bound on the size of the database while allowing the actual physical configuration of the network to grow without bound. This is one of several important considerations driving the internet development. 2) Partial transparency. One may want to be able to replace the networks which underlie certain Pathways without having to make extensive changes to the software of the Switches. Or one may simply not be able or willing to get any information about some underlying network. Either of these is a good reason to try to treat that underlying network transparently. Note, however, that the best that we can hope to achieve is PARTIAL transparency. If a Pathway is replaced by another Pathway of very different characteristics, we cannot realistically expect to maintain efficient performance - 16 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen without modifying the Switches in some way to take account of the new characteristics. However, it may be possible to restrict the magnitude of the changes; for example, perhaps only the software in the Switches which are the endpoints of the Pathways will need to be changed. This is an issue that we will have to consider in great detail; certainly it is one of the most important considerations driving the internet effort. Note that these considerations, important as they may be, are really just matters of degree, and generally must be traded off against other considerations. We can ignore the internal structure of a Pathway to a greater or lesser degree. It is possible, for example, that we will want our internet gateways to exchange information with certain ARPANET IMPs, even though in general we want the internet gateways to be able to ignore the internal structure of the ARPANET. The principle of ignoring the internal structure of a Pathway is supposed to be a tool to help us, not a straitjacket to prevent us from getting needed information. This is another issue to which we shall return repeatedly in subsequent papers of this series. One of the aspects of a Network Structure that is most sensitive to Pathway characteristics, and to the decision to ignore the internal structure of a Pathway, is its MAINTAINABILITY. Maintainability is one of the most important, - 17 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen though most neglected, areas of network design. In the long run, the ability to maintain the network (which means the ability to isolate faults and to repair them) can have a much larger effect on the network's efficacy as a communications utility than almost any other consideration. In some sense, maintainability is the "bottom line;" if a network is subject to repeated inexplicable failures and degradations, then the users will be driven away, and all the effort that has gone into careful optimizations of the algorithms and protocols will have been wasted. In a complex Network Structure, which may include Pathways of arbitrary internal complexity, maintainability is a very crucial issue. A good example of the kinds of problems that can arise may be taken from our experience with the ARPANET's line 77 (the "transparent" connection to the London-TIP via SATNET). The ARPANET generally treats this as if it were a telephone circuit, even though it actually consists of a large number of terrestrial access lines, SIMPs (SATNET nodes), and satellite broadcast facilities, any component of which might fail in its own peculiar way. When this special connection was installed, the intention was that it be as transparent as possible to the ARPANET. It turns out, however, that a side-effect of treating SATNET transparently is that IT ALSO BECOMES TRANSPARENT TO THE FAULT-ISOLATION TECHNIQUES WHICH ARE USUALLY USED FOR TROUBLE-SHOOTING ARPANET LINES. That is, the usual fault isolation techniques do not see into the structure of this "line", and hence can say no more than that the - 18 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen line is up or down. While this is a consequence of the transparent design, it causes great difficulty, especially since the various components of this line are maintained by different organizations, each of which prefers to believe that the problem is someone else's responsibility. Furthermore, since the IMPs at each end of the line (which are also Hosts on the Network Structure of SATNET) don't realize that they are actually accessing another network, and don't use the usual network access protocol for SATNET, some of SATNET's standard fault isolation techniques are bypassed too. A problem that has been recurring with some frequency is that the ARPANET's line up/down protocol just will not bring the SATNET "line" up, even though SATNET itself seems to be working fine, according to the independent SATNET monitoring. At one time, the team of ARPANET and SATNET people working on the problem originally seemed to be in agreement that the source of the problem was in the design of the ARPANET's line up/down protocol. On further investigation, however, it turned out that the real problem was that the terrestrial access line between the London-TIP and one of the SIMPs really was experiencing intermittent failures, and hence that the ARPANET's protocol had been performing correctly when it refused to bring the SATNET "line" up. However, since neither the SIMP nor the London-TIP (really a host on SATNET) treated this access line as SATNET-host access lines are normally treated, the SATNET people found it very difficult to test this - 19 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen line by itself in order to do fault isolation. If we have a Network Structure whose Pathways can themselves be arbitrarily complex and nested internets, then this sort of problem can be expected to arise with great frequency, UNLESS PROPER INSTRUMENTATION AND FAULT ISOLATION MECHANISMS ARE DESIGNED INTO THE NETWORK STRUCTURE FROM THE VERY BEGINNING. To some extent, some of these problems may just be inevitable once we decide to ignore the internal structure of a Pathway. The extent to which this is or is not true is a very important issue for us to consider, since it may ultimately be one of the most important factors in determining whether a reliable, operational, flexible, and growing internet configuration is really feasible. We will try to keep maintainability issues in mind throughout our entire discussion of the internet architecture that we propose. To a lesser extent, this sort of problem can occur even purely within the ARPANET. Since ARPANET links are really pieces of the telephone network, it is worth asking whether the transparency of the telephone network impacts our ability to maintain the ARPANET. In fact, this does sometimes cause problems. When the ARPANET Network Control Center complains to the telephone company that a line is not operational, they really cannot provide the telephone company with very much data as to what is really wrong. Sometimes it takes the telephone company a long time to fix the problem, and it is not uncommon for the telephone company to claim that a line is fixed and to return the - 20 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen line to the ARPANET, after which it is discovered that the ARPANET's line up/down protocol still will not bring it up (because the packet error rate is too great). Yet the situation is generally acceptable -- the ARPANET itself does a good enough job of detecting when there are problems with the lines, and the phone company does a good enough job (generally) of fault isolation within their own network to be able to fix problems relatively quickly. However, in a Network Structure whose Pathways consist of packet-switching networks, rather than telephone lines, we probably wouldn't be so lucky. The more complex and poorly understood the Pathways actually are (and the behavior of packet-switching networks, not to mention internets, is still quite poorly understood), the less likely it is that a simple complaint to the maintainer of the Pathway will get timely results. As the Pathway characteristics become more and more complex, it will become more and more important to have instrumentation at all levels, including the Switches and Hosts at Pathway end-points, to aid in diagnosing possible problems. As much as we might want to be able to regard the Pathways as fully transparent, it may turn out that the sort of instrumentation needed to help in fault isolation is dependent on the particular characteristics of the Pathway. This is another issue that we will have to keep in mind throughout. Wherever possible, as we develop our proposed internet architecture, we will try to "parameterize" the effect of Pathway - 21 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen characteristics on the robustness and performance of the architecture. It will certainly be important to know whether it is really possible to build a robust high-performance Network Structure out of Pathways with totally arbitrary characteristics (probably not), and if not, just how many constraints we must put on the Pathway characteristics in order to get reasonable performance out of our architecture. This approach will help us to get some understanding in advance of how large and varied a configuration our architecture can support. This approach will also help us to understand how our architecture can be adapted to other applications in which we can place more constraints than would be appropriate for the Catenet. Consider, for example, a Network Structure all of whose Pathways are versions of the ARPANET which are largely homogeneous and under the control of a single organization. Within this Network Structure, we might be able to introduce much more effective and efficient routing and congestion control mechanisms than in a Network Structure whose Pathways consist of many different kinds of networks controlled by many different organizations with varied interests (e.g., the Catenet). In fact, this rather homogeneous Network Structure might not properly be called an "internet" at all; it might just be regarded as the ARPANET with area routing. ("Area routing" refers to any routing scheme in which a network is divided into several areas, such that Switches in each area have explicit routes only to other Switches in the same area, but not to - 22 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen Switches in other areas. Routes are available for getting to other areas, but the internal structure of these other areas is disregarded. The term is usually applied to routing schemes used in single homogeneous, packet-swtiching networks, as opposed to internets, however.) One of the advantages of our model is that it enables us to see internetting and area routing as applications that differ only in regard to the Pathway characteristics of the appropriate Network Structure. 1.4 A Functional View of the Internet Let's look now at how we might model the OPERATION of a Network Structure. There seem to be four main steps involved in getting data from a source Host to a destination Host: 1) A source Host submits a message to a source Switch, providing it with the name of a destination Host to which the message should be delivered, as well as with any other information which is needed to specify necessary constraints on the characteristics of data delivery. (Note that we said "the NAME of a destination Host", not the address of a destination Host. We will return to this very important point in later papers.) 2) The source Switch must map the name of the destination Host into the address OF A DESTINATION SWITCH. This may or may not be identical to the source Switch itself. If - 23 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen the name of the destination Host maps to several possible destination Switch addresses (multi-homing), the source Switch must choose one, and this must be one which has a currently operational Pathway to the destination Host. 3) Using the routing scheme of the Network Structure, the source Switch must get the message to the destination Switch, via some (possibly empty) sequence of intermediate Switches. 4) The destination Switch must get the message to the destination Host. This model of operation attempts to make a clear separation between the protocols which the source and destination Hosts must use to access the Network Structure (steps 1 and 4), the protocols which the Network Structure uses internally to move data from one point to another (steps 2 and 3), and the protocols used by the Hosts to talk to each other. This separation is required by the precepts of protocol layering, and also by common sense, since only with a clear separation of access functions from internal functions can we maintain the flexibility to make internal changes in the Network Structure without impacting the access software in the Hosts. The need for this separation between access functions and internal functions is taken for granted in most ordinary packet-switching applications, but has not been incorportated at all into the current Catenet. The - 24 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen current Catenet protocols freely intermix access functions with internal functions, and in fact there is only a single protocol, IP, which contains elements needed for Hosts to talk to each other, for Hosts to talk to Switches, and for Switches to talk to Switches. This seems to be a consequence of the old idea that the internet is just a series of networks pasted together by hosts which are on two or more of the networks. That idea makes it difficult to distinguish the gateways from the hosts, or to properly take account of the fact that although gateways are Hosts in some Network Structure (that of the individual packet-switching networks), they are also Switches in another (that of the internet). A proper distinction of access functions from internal functions seems essential, though, if we are to build an internet which functions as a real network, rather than as a series of pasted together networks and gateways. Any Network Structure which is to be operational must have some way of performing these four steps. Furthermore, in order for particular applications to get satisfactory performance out of their use of the Network Structure, the Network Structure must perform these functions under certain constraints with respect to delay, throughput, reliability, sequential delivery, and fault detection. (By "fault detection", we mean the ability of the Network Structure to inform the user about exceptional conditions, such as the destination host's being down or unreachable. This constraint is often neglected in the design of - 25 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen network architectures or protocols, but seems quite important in a robust operational environment.) The ability to gather and report exception information at various levels of protocol is important both for system maintenance and for general user satisfaction. Nothing makes a worse impression on a user than a mysterious degradation in service about which he can get no feedback. It is not immediately obvious, though, to what extent the various protocols used to operate a Network Structure must ensure that these constraints are met. It is generally understood that if some application requiring inter-process communication must place constraints (such as sequentiality) on the characteristics of the communications, then the application itself must utilize some high level protocol (at the Host-Host level, or even higher) which will enforce the constraints, rather than depending on the low-level communications medium to enforce them. What seems to be less generally understood is the fact that, in general, and other things being equal, the performance which some user gets from his high-level protocol will be better if the lower level protocols pass data to the high level protocols in a way which already satisfies the constraints that the high level protocols must impose. For example, an application which requires sequentiality will have to use a high level protocol like TCP which guarantees sequentiality. However, the end user will generally see much better performance, in terms of throughput and delay, if the protocols below TCP maintain - 26 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen sequentiality, since this will require TCP to do less work, and put less of a drain on the resources (such as buffer space, sequence number space, and host CPU bandwidth) needed by TCP. The area of fault detection and reporting provides a good example here. A user attempting to talk to a dead host might find his TCP typing the message "excessive retransmissions" to him. This sort of message would not generally be too useful to a user since, if he is not a network expert, it gives him no clue of what the actual situation is. The average user might prefer to know that the destination host is dead, so he can try again later, but this information is very difficult, if not impossible, to obtain solely at the TCP level, although it might be quite simple to obtain at a lower protocol level. Of course, putting more functionality in lower level protocols also has a cost, as well as a potential benefit, and costs often trade off with benefits in surprising ways. As we shall see, producing an operational Network Structure requires a large number of protocols, and we will attempt to deal with considerations like these as we consider specific protocol issues. Not surprisingly, we will find that cost-benefit trade-offs for both access protocols and internal protocols will often depend on the characteristics of the Pathways in the Network Structure. - 27 - IEN 184 Bolt Beranek and Newman Inc. Eric C. Rosen REFERENCES 1. J.M. McQuillan, I. Richer, E.C. Rosen, "The New Routing Algorithm for the ARPANET", IEEE TRANSACTIONS ON COMMUNICATIONS, May 1980. 2. E.C. Rosen, "The Updating Protocol of ARPANET's New Routing Algorithm," COMPUTER NETWORKS, February 1980. 3. J.M McQuillan, G. Falk, I. Richer, "A Review of the Development and Performance of the ARPANET Routing Algorithm," IEEE TRANSACTIONS ON COMMUNICATIONS, December 1978. - 28 -