324
`
`THE NETWORK LAYER
`
`CHAP. 5
`
`can assume that the subnet provides OSI service, even if it does not. Since internet(cid:173)
`working frequently involves connecting one or more nonstandard networks, having
`a structural way to deal with strange subnets is essential.
`In the previous example, the subnet service was not good enough (it lacked
`NSAP addressing). It can also happen that the subnet service is too good, and must
`be de-enhanced (degraded?) to match up to what the internet sublayer requires.
`One example is a relay between a datagram subnet and a virtual circuit subnet.
`The internet sublayer can be designed with either type of service in mind. If
`datagram service has been chosen, then it is up to the subnet enchancement layer on
`the virtual circuit side to hide the virtual circuits and just provide datagram service
`to the internet sublayer. If it cannot devise any better strategy, for every datagram
`offered to it, it can establish a virtual circuit, send the datagram, and then release
`the virtual circuit. In practice, the subnet enhancement sublayer would not release
`the virtual circuit until it had been idle for several minutes because there is a high
`probability it could be used again.
`The principal task of the internet sublayer is end-to-end routing. When a packet
`arrives at a relay, it works its way up to the internet sublayer, which examines it
`and decides whether to forward it, and if so, using which subnet (a multilateral
`relay may have several subnets to choose from). To a first approximation, routing
`across multiple subnets is similar to routing within a single subnet, and the tech(cid:173)
`niques we have studied earlier are relevant. For a large internet, hierarchical rout(cid:173)
`ing is an obvious candidate, since it frees the relays from having to know about the
`internal structure of distant subnets.
`The relay of Fig. 5-27 extends up as far as layer 3 and moves packets between
`networks in that layer. In the general (non OSI) case, relaying can be done in any
`layer. Four common types of relays are as follows:
`
`Layer 1: Repeaters copy individual bits between cable segments.
`
`Layer 2: Bridges store and forward frames between LANs.
`
`Layer 3: Gateways store and forward packets between dissimilar networks.
`
`Layer 4: Protocol converters provide interfacing in higher layers.
`
`Repeaters are low-level devices that amplify just electrical signals. They are
`needed to provide current to drive long cables. In 802.3, for example, the timing
`properties of the MAC protocol (the value of 't chosen) allow cables up to 2.5 km,
`but the transceiver chips can only provide enough power to drive 500 meters. The
`solution is to use repeaters to extend the cable length where that is desired.
`Unlike repeaters, which copy the bits as they arrive, bridges are store-and(cid:173)
`f orward devices. A bridge accepts an entire frame and passes it up to the data link
`layer where the checksum is verified. Then the frame is sent down to the physical
`layer for forwarding on a different subnet. Bridges can make minor changes to the
`
`Ex.1067.121
`
`DELL
`
`

`

`SEC. 5.4
`
`INTERNETWORK.ING
`
`325
`
`frame before forwarding it, such as adding or deleting some fields from the frame
`header. Since they are data link layer devices, they do not deal with headers at
`layer 3 and above, and cannot make changes or decisions that depend on them.
`Gateways are conceptually similar to bridges, except that they are found in the
`network layer. The relay of Fig. 5-27 is a gateway. Some people use the term gate(cid:173)
`way in a generic sense, applicable to any layer, and the term router for a network
`layer gateway. In this chapter "gateway" will refer to the network layer.
`As a general rule, the networks connected by a gateway can differ much more
`than those connected by a bridge. In Fig. 5-26, the LANs are connected by a
`bridge; the LAN-WAN and WAN-WAN relays are gateways. A major advantage
`of gateways over bridges is that they can connect networks with incompatible
`addressing formats, for example, an 802 LAN using 48-bit binary addresses and an
`X.25 network using 14 decimal digit X.121 addresses.
`At the transport layer and above, the relays are usually called protocol convert(cid:173)
`ers, although the term "gateway'' is used by some people, as mentioned above.
`The job of a protocol converter is much more complex than that of a gateway. The
`protocol converter must convert from one protocol to another without losing too
`much meaning in the process. An example of a protocol converter is a relay that
`translates the OSI transport protocol to the protocol used in the ARP A Internet
`(TCP). Another example of protocol conversion is converting OSI mail messages
`(MOTIS) to ARPA Internet format (RFC 822).
`Regardless of which layer the relaying is done in, the complexity of the job
`depends mostly on how similar the two networks are in terms of frames, packets,
`messages, and protocols. Some of the ways networks can differ are frame, packet,
`and message size, checksum algorithms, maximum packet lifetimes, connection(cid:173)
`oriented vs. connectionless protocols, and timer values. Sometimes the conversion
`is not even possible, for example, when trying to forward expedited data (someone
`hit the DEL key) through a network not having any concept of expedited data.
`
`5.4.2. Bridges
`
`In this section we will look at bridge design. In the following ones we will
`study gateways. In a sense, the material about bridges might logically have been
`covered in Chapter 3 or Chapter 4, but as a convenience to the reader, we have
`decided to put all the material on internetworking in one place. Most bridges con(cid:173)
`nect 802 LAN s, so we will concentrate primarily on 802 bridges.
`Before getting into the technology of bridges, it is worthwhile taking a look at
`some common situations in which bridges are used. We will mention six reasons
`why a single organization may end up with multiple LAN s. First, many university
`and corporate departments have their own LAN s, primarily to connect their own
`personal computers, workstations, and minicomputers. Since the goals of the vari(cid:173)
`ous departments differ, different departments choose different LANs, without
`regard to what other departments are doing. Sooner or later, there is a need for
`
`Ex.1067.122
`
`DELL
`
`

`

`

`

`

`

`

`

`SEC. 5.4
`
`INTERNETWORKING
`
`329
`
`the configuration, but for the standard 10-Mbps system it is 1518 bytes. For 802.4
`it is fixed at 8191 bytes. For 802.5 there is no upper limit, except that a station may
`not transmit longer than the token holding time. With the default value of 10 msec,
`the maximum frame length is 5000 bytes.
`The obvious problem is what happens when a long frame must be forwarded
`onto a LAN that cannot accept it? Splitting the frame into pieces is out of the ques(cid:173)
`tion in this layer. All the protocols assume that frames either arrive or they do not.
`There is no provision for reassembling frames out of smaller units. This is not to
`say that such protocols could not be devised. They could be and have been. It is
`just that 802 does not provide this feature. Basically, there is no solution. Frames
`that are too large to be forwarded must be discarded. So much for transparency.
`Now let us briefly consider each of the nine cases of 802.x to 802.y bridges to
`see what other problems are lurking in the shadows. From 802.3 to 802.3 is easy.
`The only thing that can go wrong is that the destination LAN is so heavily loaded
`that frames keep pouring into the bridge, but the bridge cannot get rid of them. If
`this situation persists long enough, the bridge might run out of buffer space and
`begin dropping frames. Since this problem is always potentially present when for(cid:173)
`warding onto an 802.3 LAN, we will not mention it further. With the other two
`LANs, each station, including the bridge is guaranteed to acquire the token periodi(cid:173)
`cally, and cannot be shut out for long intervals.
`From 802.4 to 802.3 two problems exist. First, 802.4 frames carry priority bits
`that 802.3 frames do not have. As a result, if two 802.4 LAN s communicate via an
`802.3 LAN, the priority will be lost the intermediate LAN.
`The second problem is caused by a specific feature in 802.4: temporary token
`handoff. It is possible for an 802.4 frame to have a header bit set to 1 to tem(cid:173)
`porarily pass the token to the destination, to let it send an acknowledgement frame.
`However, if such a frame is forwarded by a bridge, what should the bridge do? If it
`sends an acknowledgement frame itself, it is lying because the frame really has not
`been delivered yet. In fact, the destination may be dead.
`On the other hand, if it does not generate the acknowledgement, the sender will
`almost assuredly conclude that the destination is dead and report back failure to its
`superiors. There does not seem to be any way to solve with this problem.
`From 802.5 to 802.3 we have a similar problem. The 802.5 frame format has A
`and C bits in the frame status byte. These bits are set by the destination to tell the
`sender whether the station addressed saw the frame, and whether it copied it.
`Again here, the bridge can lie and say the frame has been copied, but if it later turns
`out that the destination is down, serious problems may arise. In essence, the inser(cid:173)
`tion of a bridge into the network has changed the semantics of the bits.
`From 802.3 to 802.4 we have the problem of what to put in the priority bits. A
`good case can be made for having the bridge retransmit all frames at the highest
`priority, because they have probably suffered enough delay already.
`From 802.4 to 802.4 the only problem is what to do with the temporary token
`handoff. At least here we have the possibility of the bridge managing to forward
`
`Ex.1067.126
`
`DELL
`
`

`

`330
`
`THE NETWORK LA YER
`
`CHAP. 5
`
`the frame fast enough to get the response before the timer runs out. Still it is a
`gamble. By forwarding the frame at the highest priority, the bridge is telling a little
`white lie, but it thereby increases the probability of getting the response in time.
`From 802.5 to 802.4 we have the same problem with the A and C bits as before.
`Also, the definition of the priority bits is different for the two LAN s, but beggars
`can't be choosers. At least the two LANs have the same number of priority bits.
`All the bridge can do is copy the priority bits across and hope for the best.
`From 802.3 to 802.5 the bridge must generate priority bits, but there are no
`other special problems. From 802.4 to 802.5 there is a potential problem with
`frames that are too long and the token handoff problem is present again. Finally,
`from 802.5 to 802.5 the problem is what to do with the A and C bits again. Figure
`5-31 summarizes the various problems we have been discussing.
`Destination LAN
`802.4 (Token bus)
`
`802.5 (Token ring)
`
`802.3(CSMA/CD)
`
`802.3
`
`802.4
`
`Source
`LAN
`
`1,5,9,8,10
`
`1, 4
`
`9
`
`1, 2, 4, 8
`
`1, 2, 3, 8, 9, 10
`
`802.5
`
`1,2,5,6, 7, 10
`
`1, 2, 3, 6, 7
`
`6, 7
`
`Actions:
`1. Reformat the frame and compute new checksum.
`2. Reverse the bit order.
`3. Copy the priority, meaningful or not.
`4. Generate a ficticious priority.
`5. Discard priority.
`6. Drain the ring (somehow).
`7. Set A and C bits (by lying).
`8. Worry about congestion (fast LAN to slow LAN).
`9. Worry about token handoff ACK being delayed or impossible.
`10. Panic if frame is too long for destination LAN.
`
`Parameters assumed:
`802.3:
`1518-byte frames, 10 Mbps (minus collisions)
`802.4:
`8191-byte frames 10 Mbps
`802.5:
`5000-byte frames
`4 Mbps
`
`Fig. 5-31. Problems encountered in building bridges from 802.x to 802.y.
`
`When the IEEE 802 committee set out to come up with a LAN standard, it was
`unable to agree on a single standard, so it produced three incompatible standards, as
`we have just seen in some detail. For this failure, it has been roundly criticized.
`When it was later assigned the job of designing a standard for bridges to intercon(cid:173)
`nect its three incompatible LAN s, it resolved to do better. It did. It came up with
`two incompatible bridge designs. So far nobody has asked it to design a gateway
`standard to connect its two incompatible bridges, but at least the trend is in the right
`direction.
`This section has dealt with the problems encountered in connected two LAN s
`
`Ex.1067.127
`
`DELL
`
`

`

`

`

`332
`
`THE NETWORK LA YER
`
`CHAP. 5
`
`which the bridge is connected except the one it arrived on. As time goes on, the
`bridges learn where destinations are, as described below. Once a destination is
`known, frames destined for it are put on only the proper LAN, and are not flooded.
`The algorithm used by the transparent bridges is Baran' s backward learning.
`As mentioned above, the bridges operate in promiscuous mode, so they see every
`frame sent on any of their LANs. By looking at the source address, they can tell
`which machine is accessible on which LAN. For example, if bridge 1 in Fig. 5-32
`sees a frame on LAN 2 coming from C it knows that C must be reachable via LAN
`2, so it makes an entry in its hash table noting that frames going to C should use
`LAN 2. Any subsequent frame addressed to C coming in on LAN 1 will be for(cid:173)
`warded, but a frame for C coming in on LAN 2 will be discarded.
`The topology of the internetwork can change as machines and bridges are
`powered up and down and moved around. To handle dynamic topologies, when(cid:173)
`ever a hash table entry is made, the arrival time of the frame is noted in the entry.
`Whenever a frame that is already in the table arrives, its entry is updated with the
`current time. Thus the time associated with every entry tells the last time a frame
`from that machine was seen.
`Periodically, a process in the bridge scans the hash table and purges all entries
`more than a few minutes old. In this way, if a computer is unplugged from its
`LAN, moved around the building, and replugged in somewhere else, within a few
`minutes it will be back in normal operation, without any manual intervention. This
`algorithm also means that if a machine is quiet for a few minutes, any traffic sent to
`it will have to be flooded, until it next sends a frame itself.
`The routing procedure for an incoming frame depends on the LAN it arrives on
`(the source LAN) and the LAN its destination is on (the destination LAN), as fol(cid:173)
`lows:
`
`1. If destination and source LAN s are the same, discard the frame.
`
`2. If the destination and source LAN s are different, forward the frame.
`
`3. If the destination LAN is unknown, use flooding.
`
`As each frame arrives, this algorithm must be applied. Special purpose VLSI chips
`exist to do the lookup and update the table entry, all in a few microseconds.
`To increase reliability, some sites use two or more bridges in parallel between
`pairs of LANs, as shown in Fig. 5-33. This arrangement, however, also introduces
`some additional problems because it creates loops in the topology.
`A simple example of these problems can be seen by observing how a frame, F,
`with unknown destination is handled in Fig. 5-33. Each bridge, following the nor(cid:173)
`mal rules for handling unknown destinations, uses flooding, which in this example,
`just means copying it to LAN 2. Shortly thereafter, bridge 1 sees F 2, a frame with
`an unknown destination, which it copies to LAN 1, generating F 3. Similarly, bridge
`
`Ex.1067.129
`
`DELL
`
`

`

`

`

`334
`
`THE NETWORK LA YER
`
`CHAP. 5
`
`much too long to run. An algorithm that can handle large networks by partitioning
`them into multiple communicating spanning trees is described by Sincoskie and
`Cotton (1988).
`
`Source Routing Bridges
`
`Transparent bridges have the advantage of being easy to install. You just plug
`them in and walk away. On the other hand, they do not make optimal use of the
`bandwidth, since they only use a subset of the topology (the spanning tree). The
`relative importance of these two (and other) factors led to a split within the 802
`committees (Pitt, 1988). The CSMNCD and token bus people chose the trans(cid:173)
`parent bridge. The ring people (with encouragement from IBM) preferred a
`scheme called source routing, which we will now describe. For addition details,
`see (Dixon and Pitt, 1988; Hamner and Samsen, 1988; and Pitt and Winkler, 1987).
`Reduced to its barest essentials, source routing assumes that the sender of each
`frame knows whether or not the destination is on its own LAN. When sending a
`frame to a different LAN, the source machine sets the high-order bit of the destina(cid:173)
`tion address to 1, to mark it. Furthermore, it includes in the frame header the exact
`path that the frame is to follow.
`This path is constructed as follows. Each LAN has a unique 12-bit number, and
`each bridge has a 4-bit number that uniquely identifies it in the context of its LAN s.
`Thus, two bridges far apart may both have number 3, but two bridges on the same
`LAN must have different bridge numbers. A route is then a sequence of bridge,
`LAN, bridge, LAN, ... numbers. Referring to Fig. 5-32, the route from A to C
`would be (Bl, L2, B2, L3), where we have added the codes B and L for conve(cid:173)
`nience, to show which items are bridges and which are LAN s.
`A source routing bridge is only interested in those frames with the high-order
`bit of the destination set to 1. For each such frame that it sees, it scans the route
`looking for the number of the LAN on which the frame arrived. If this LAN
`number is followed by its own bridge number, the bridge forwards the frame onto
`the LAN whose number follows its bridge number in the route. If the incoming
`LAN number is followed by the number of some other bridge, it does not forward
`the frame.
`This algorithm lends itself to three possible implementations:
`
`1. Software: the bridge runs in promiscuous mode, copying all frames to
`its memory to see if they have the high-order destination bit set to 1. If
`so, the frame is inspected further, otherwise it is not.
`
`2. Hybrid: the bridge's LAN interface inspects the high-order destination
`bit and only gives it frames with the bit set. This interface is easy to
`build into hardware and greatly reduces the number of frames the
`bridge must inspect.
`
`Ex.1067.131
`
`DELL
`
`

`

`SEC. 5.4
`
`INTERNETWORK.ING
`
`335
`
`3. Hardware: the bridge's LAN interface not only checks the high-order
`destination bit, but it also scans the route to see if this bridge must do
`forwarding. Only frames that must actually be forwarded are given to
`the bridge. This implementation require the most complex hardware,
`but wastes no bridge CPU cycles because all irrelevant frames are
`screened out.
`
`These three implementations vary in their cost and performance. The first one has
`no additional hardware cost for the interface, but may require a very fast CPU to
`handle all the frames. The last one requires a special VLSI chip, but offloads much
`of the processing from the bridge to the chip, so that a slower CPU can be used, or
`alternatively, the bridge can handle more LANs.
`Implicit in the design of source routing is that every machine in1 the internet(cid:173)
`work knows the exact path to every other machine. How these routes are
`discovered is an important part of the source routing algorithm. The basic idea is
`that if a destination is unknown, the source issues a broadcast frame asking where it
`is. This discovery frame is copied by every bridge so that it reaches every LAN on
`the internetwork. When the reply comes back, the bridges record their identity in
`it, so that the original sender can see the exact route taken and ultimately choose the
`best route.
`While this algorithm clearly finds the best route (it finds all routes), it suffers
`from a frame explosion. Consider the configuration of Fig. 5-34, with N LANs
`linearly connected by triple bridges. Each discovery frame sent by machine A is
`copied by each of the three bridges on LAN 1, yielding three discovery frames on
`LAN 2. Each of these is copied by each of the bri;es on LAN 2, resulting in nine
`frame on LAN 3. By the time we reach LANN, 3 -1 frames are circulating. If a
`dozen sets of bridges are traversed, more than half a million discovery frames will
`have to be injected into the last ring, causing severe congestion.
`
`Bridge
`
`LAN
`
`~ ~
`
`A--
`
`2
`
`3
`
`4
`
`N
`
`Fig. 5-34. A series of LANs connected by triple bridges.
`
`A somewhat analogous process happens with the transparent bridge, only not
`nearly so severe. When an unknown frame arrives, it is flooded, but only along the
`spanning tree, so the total volume of frames sent is linear with the size of the net(cid:173)
`work, not exponential.
`
`Ex.1067.132
`
`DELL
`
`

`

`336
`
`THE NETWORK LA YER
`
`CHAP. 5
`
`Once a host has discovered a route to a certain destination, it stores the route in
`a cache, so that the discovery process will not have to be run next time. While this
`approach greatly limits the impact of the frame explosion, it does put some admin(cid:173)
`istrative burden on all the hosts, and the whole algorithm is definitely not trans(cid:173)
`parent.
`
`Comparison of 802 Bridges
`
`The transparent and source routing bridges each have advantages and disadvan(cid:173)
`tages. In this section we will discuss some of the major ones. They are summa(cid:173)
`rized in Fig. 5-35 and covered in more detail in (Soha and Perlman, 1988; and
`Zhang, 1988). Be warned, however, that every one of the points is highly con(cid:173)
`tested.
`
`Issue
`
`Transparent bridge
`
`Source routing bridge
`
`Orientation
`Transparency
`
`Connectionless
`
`Connection-oriented
`
`Fully transparent
`
`Not transparent
`
`I I
`l
`
`Manual
`
`Optimal
`
`Configuration
`
`Automatic
`
`Suboptimal
`
`Routing
`
`Locating
`
`Failures
`
`Backward learning
`
`Discovery frames
`
`Handled by the bridges
`
`Handled by the hosts
`
`Complexity
`
`In the bridges
`
`In the hosts
`
`Fig. 5-35. Comparison of transparent and source routing bridges.
`
`At the heart of the difference between the two bridge types is the distinction
`between connectionless and connection-oriented networking. The transparent
`bridges have no concept of a virtual circuit at all, and route each frame indepen(cid:173)
`dently from all the others. The source routing bridges, in contrast, determine a
`route using discovery frames and then use that route thereafter.
`The transparent bridges are completely invisible to the hosts and are fully com(cid:173)
`patible with all existing 802 products. The source bridges are neither transparent
`nor compatible. To use source routing, hosts must be fully aware of the bridging
`scheme, and must actively participate in it.
`When using transparent bridges, no network management is needed. The
`bridges configure themselves to the topology automatically. With source routing
`bridges, the network manager must manually install the LAN and bridge numbers.
`Mistakes, such as duplicating a LAN or bridge number, can be very difficult to
`detect, as they may cause some frames to loop, but not others on different routes.
`Furthermore, when connecting two previously disjoint internetworks, with trans(cid:173)
`parent bridges there is nothing to do except connect them, whereas with source
`routing, it may be necessary to manually change many LAN numbers to make them
`unique in the combined internetwork.
`
`Ex.1067.133
`
`DELL
`
`

`

`. SEC. 5.4
`
`INTERNETWORK.ING
`
`337
`
`One of the few advantages of source routing is that, in theory, it can use optimal
`routing, whereas transparent bridging is .testricted to the spanning tree. Further(cid:173)
`more, source routing can also make good use of parallel bridges between two LAN s
`to split the load. Whether actual bridges will be clever enough to make use of these
`theoretical advantages is questionable.
`Locating destinations is done using backward learning in the transparent bridge
`and using discovery frames in source routing bridges. The disadvantage of back(cid:173)
`ward learning is that the bridges have to wait until a frame from a particular
`machine happens to come along in order to learn where that machine is. The disad(cid:173)
`vantage of discovery frames is the exponential explosion in moderate to large inter(cid:173)
`networks with parallel bridges.
`Failures handling is quite different in the two schemes. Transparent bridges
`learn about bridge and LAN failures and other topology changes quickly and
`automatically, just from listening to each other's control frames. Hosts do not
`notice these changes at all.
`With source routing, the situation is quite different. When a bridge fails,
`machines that are routing over it initially notice that their frames are no longer
`being acknowledged, so they time out and try over and over. Finally, they conclude
`that something is wrong, but they still do not know if the problem is with the desti(cid:173)
`nation itself, or with the current route. Only by sending another discovery frame
`can they see if the destination is available. Unfortunately, when a major bridge
`fails, a large number of hosts will have to experience timeouts and send new
`discovery frames before the problem is resolved, even if an alternative route is
`available. This greater vulnerability to failures is one of the major weaknesses of
`all connection-oriented systems.
`Finally, we come to complexity and cost, a very controversial topic. H source
`routing bridges have a VLSI chip that reads in only those frames that must be for(cid:173)
`warded, these bridges will experience a lighter frame processing load and deliver a
`better performance for a given investment in hardware. Without this chip they will
`do worse because the amount of processing per frame (searching the route in the
`frame header) is substantially more.
`In addition, source routing puts extra complexity in the hosts: they must store
`routes, send discovery frames, and copy route information into each frame. All of
`these things require memory and CPU cycles. Since there are typically one to two
`orders of magnitude more hosts than bridges, it may be better to put the extra cost
`and complexity into a few bridges, rather than in all the hosts.
`
`5.4.3. Gateways
`
`In contrast to bridges, gateways operate at the network level. This gives them
`more flexibility, for example, in translating addresses between very dissimilar net(cid:173)
`works, but it also makes them slower. As a consequence, gateways are commonly
`
`Ex.1067.134
`
`DELL
`
`

`

`338
`
`THE NETWORK LAYER
`
`CHAP. 5
`
`used in WAN s, where no one expects them to handle more than 10,000 packets/sec,
`a common requirement for LAN bridges.
`Two styles of gateways are common, one for connection-oriented networks and
`one for connectionless networks. We will study both of these in turn below.
`
`Connection-Oriented Gateways
`
`The OSI model permits two styles of internetworking: a connection-oriented
`concatenation of virtual circuit subnets, and a datagram internet style. In this sec(cid:173)
`tion we will look at the virtual circuit approach; in the next one we will examine
`the datagram method.
`The virtual circuit method differs from interconnection using bridges in that it
`happens in the network layer (see Fig. 5-27) rather than the data link layer, but it
`also differs in other ways. One of these differences stems from the nature of a
`bridge. It is a small minicomputer or microcomputer. When the bridge and all the
`LAN s are owned by the same organization, ownership and operation of the bridge
`do not generate any special problems. However, when a gateway is between two
`WAN s run by different organizations, possibly in different countries, the joint
`operation of a small minicomputer can lead to a lot of finger pointing.
`To eliminate these problems, a slightly different approach is taken. The relay
`of Fig. 5-27 is effectively ripped apart in the middle and the two parts of 3c are
`connected with a wire, as shown in Fig. 5-36. Each of the halves is called a half(cid:173)
`gateway and each one is owned and operated by one of the network operators. The
`whole problem of gatewaying then reduces to agreeing to a common protocol to use
`on the wire. As long as both parties use the common protocol on the wire, they can
`arrange their sublayers 3a, 3b, and 3c any way that is convenient for them.
`The protocol that the half-gateways speak over the wire is CCITT's X.75 proto(cid:173)
`col, which is almost identical to X.25 (discussed later in this chapter). The X.75
`model is based on the idea of building up an internetwork connection by con(cid:173)
`catenating a series of intranetwork and half-gateway to half-gateway virtual cir(cid:173)
`cuits. The model is shown in Fig. 5-37(a) The connection between the source host,
`in one network, and the destination host, in another network, is composed of five
`adjacent virtual circuits, marked VC 1-5. VC 1 goes from the source host to a
`half-gateway (called a signaling terminal or STE by CCITT), in its own network.
`VC 2 goes from the half-gateway in the source network to a half-gateway in an
`intermediate network, assuming that there is no direct connection between the
`source and destination networks. VCs 3 and 5 are also intranet, like VC 1, and VC
`4 is internet, like VC 2.
`In this model a connection to a host in a distant network is set up the same way
`normal connections are established. The subnet sees that the destination is remote,
`chooses an appropriate (half-) gateway and builds a virtual circuit to the gateway.
`The first gateway records the existence of the virtual circuit in its tables and
`
`Ex.1067.135
`
`DELL
`
`

`

`

`

`

`

`

`

`

`

`SEC. 5.4
`
`INTERNETWORKING
`
`343
`
`1. HDLC: in principle infinite.
`
`2. 802.4: 65,528 bits.
`
`3. X.25: 32768 bits.
`
`4. ARP A Packet Radio Network: 2032 bits.
`
`5. ARPANET: 1008 bits.
`
`6. University of Hawaii ALOHANET: 640 bits.
`
`An obvious problem appears when a large packet wants to travel through a net(cid:173)
`work whose maximum packet size is too small. This problem has received a great
`deal of attention in the literature and some proposals for solving it have been made.
`One solution is to make sure the problem does not occur in the first place. In
`other words, the internet should use a routing algorithm that avoids sending packets
`through networks that cannot handle them. However, this solution is no solution at
`all. What happens if the original source packet is too large to be handled by the
`destination network? The routing algorithm can hardly bypass the destination.
`Nevertheless, intelligent routing can minimize the extent of the problem.
`Basically, the only solution to the problem is to allow gateways to break pack(cid:173)
`ets up into fragments, sending each fragment as a separate internet packet. How(cid:173)
`ever, as every parent of a small child knows, converting a large object into small
`fragments is considerably easier than the reverse process. (Physicists have even
`given this effect a name: the second law of thermodynamics.) Packet-switching net(cid:173)
`works, too, have trouble putting the fragments back together again.
`Two opposing strategies exist for recombining the fragments back into the orig(cid:173)
`inal packet. The first strategy is to make fragmentation caused by a "small-packet"
`network transparent to any subsequent networks through which the packet must
`pass on its way to the ultimate destination. This option is shown in Fig. 5-40(a).
`When an oversized packet arrives at a gateway, the gateway breaks it up into frag(cid:173)
`ments. Each fragment is addressed to the same exit gateway, where the pieces are
`recombined. In this way passage through the small-packet network has been made
`transparent. Subsequent networks are not even aware that fragmentation has
`occurred.
`Transparent fragmentation is simple but has some problems. For one thing, the
`exit gateway must know when it has received all the pieces, so that either a count
`field or an "end of packet" bit must be included in each packet. For another thing,
`all packets must exit via the same gateway. By not allowing some fragments to fol(cid:173)
`low one route to the ultimate destination, and other fragments a disjoint route, some
`performance may be lost. A third problem is possible reassembly lockup at the exit
`gateway. A last problem is the overhead required to repeatedly reassemble and
`then refragment a large packet passing through a series of small-packet networks.
`The other fragmentation strategy is to refrain from recombining fragments at
`
`Ex.1067.140
`
`DELL
`
`

`

`

`

`SEC. 5.4
`
`INTERNETWORK.ING
`
`345
`
`duplicates generated anywhere, this scheme is sufficient to ensure that all the pieces
`can be correctly reassembled at the destin