nterconnections
`
`Bridges and Ro
`
`Radia Perl ·
`
`·--
`
`1
`, I
`
`'
`
`....
`~T
`
`)>
`0
`0
`
`CJ)
`
`0
`z I
`~ m
`CJ)
`r-
`m -<
`
`'"'C
`;;;o
`0
`"'T1 m
`
`CJ)
`CJ)
`
`0
`z
`)>
`r-
`n
`0
`~
`'"'C
`C
`
`-I -z
`
`C)
`
`CJ)
`m
`;;;o
`m
`CJ)
`
`I:
`I
`I
`1
`I
`I
`I
`
`I!
`I:
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 1 of 12
`
`

`

`The publisher offers discounts on this book when ordered in quantity for special sales.
`For more information please contact:
`
`Corporate & Professional Publishing Group
`Addison-Wesley Publishing Company
`One Jacob Way
`Reading, Massachusetts 01867
`
`Library of Congress Cataloging-in-Publication Data
`
`Perlman, Radia.
`Interconnections : bridges and routers / Radia Perlman.
`p. cm. -
`(Addison-Wesley professional computing series)
`Includes index.
`ISBN 0-201-56332-0 (hardback)
`1. Computer network protocols. 2. Local area netw•orks (Computer networks)
`I. Title. II Series.
`TK5105.5P474 1992
`004.6'2-dc20
`
`91-37493
`CIP
`
`Copyright© 1992 by Addison-Wesley Publishing Company, Inc.
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval
`system, or transmitted, in any form, or by any means, electronic, mechanical,
`photocopying, recording, or otherwise, without the prior written consent of the publisher.
`Printed in the United States of America. Published simultaneously in Canada.
`
`Cover design by Joyce C. Weston
`Text design by Webster Design, Marblehead, MA
`Set in 11 point Times by Gex, Inc.
`
`ISBN 0-201-56332-0
`Text printed on recycled and acid-free paper.
`3 4 5 6 7 8 9 10 11- MU -96959493
`Third printing February 1993
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 2 of 12
`
`

`

`'REFACE
`
`sion of
`fCP/IP
`nes the
`llltipro-
`
`that are
`1es that
`'of the
`the text
`! desig-rc
`
`ortunity
`~roup at
`h.e most
`for sug-
`!nt for a
`
`include
`an, Paul
`y appre-
`ly since
`1an, Phil
`h.o did a
`Cohan,
`, well.
`- did not
`
`Chapter 1
`Essential Networking Concepts
`
`This chapter introduces some concepts that are essential to understanding the specific
`subfield of computer networking that includes bridges and routers. It covers the
`International Standard Organization's reference model, including layering and service
`models. It also discusses various dimensions along which network designs can differ,
`such as scope, scalability, robustness, and autoconfigurability. Chapter 1 also describes
`the typical techniques involved in providing reliable two-party communication
`because some of the techniques used by routers can interact with techniques used by
`other layers .
`
`,1.1
`
`. ~ayers
`
`Understandii;ig, designing, and building a computer network would be too difficult a
`task unles·s !}le problem were partitioned into smaller subtasks. This has traditionally
`been done by consiclering the problem as being divided into several layers. The idea
`behind layering is that each layer is responsible for providing some service to the layer
`above and does this by using the services of the layer below.
`Each layer communicates with its peer layer in another node through the use of a
`protocol. This communication is accomplished through direct communication with
`the layer below. The communication between layer n and layer n-1 is known as an
`inte,face.
`The OSI (Open Systems Interconnection) Reference Model defines seven layers.
`There is nothing magic about the number seven or the functionality in the layers, how(cid:173)
`ever. The reference model was designed before the protocols themselves, and then com(cid:173)
`mittees were set up to design each of the layers. Many of the layers were subsequently
`subdivided into further layers. The distinction between the layers is not always clear.
`Bridges and routers are a good example of a case in which people should rightfully be
`confused about which layers are which. But semantic arguments about layers are not
`very productive. Instead, the layering should be viewed as a useful framework for dis(cid:173)
`cussion, not as a bible.
`
`1
`
`~-
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 3 of 12
`
`

`

`- -
`
`-
`
`. -
`
`2
`
`application
`
`presentation
`
`t interface
`t interface
`t interface
`t interface
`t interface
`t interface
`
`session
`
`transport
`
`network
`
`data link
`
`physical
`
`I
`
`,
`
`ESSENTIAL NETWORKING CONCEPTS
`
`protocol
`
`application
`
`..
`
`I •
`
`presentation
`
`t
`t
`t
`+ transport
`t '
`
`session
`
`network
`
`data link
`
`t
`t
`
`physical
`
`protocol
`
`protocol
`
`protocol
`
`protocol
`
`protocol
`
`protocol
`
`Figure 1.1
`
`The layers defined by the ISO (International Standards Organization) are:
`
`l. Physical layer: The responsibility of the physical layer is to transmit unstruc(cid:173)
`t11red bits of information across a link. It deals with such problems as size and
`shape of connectors, assignment of functions to pins, conversion of bits to elec(cid:173)
`trical signals, and bit-level synchronization. It is usual for several different types
`of physical layers to exist within a network and even for multiple different types
`of physical layers to exist within a node, because each technology requires its
`own physical layer. For instance, a node with an attachment to FDDI (fiber dis(cid:173)
`tributed data interface) and an attachment to a 56-KB synchronous line will
`have implemented two different physical layers.
`
`-- ~ - - - - - -~ - -~ - -~ - - - · · - ------
`
`- - - - - - - ---~-
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 4 of 12
`
`

`

`r
`
`I
`
`LAYERS
`
`:ONCEPTS
`
`3
`
`2. Data link layer: The responsibility of the data link layer (sometimes called the
`link layer) is to transmit chunks of information across a link. It deals with such
`problems as checksumming to detect data corruption; orderly coordination of
`the use of shared media, as in a LAN (local area network); and addressing when
`multiple systems are reachable, as in a LAN. Again, it is common for different
`links to implement different data link layers and for a node to implement several
`data link layer protocols, one to support each of the different types of links to
`which the node is attached.
`
`3. Network layer: The responsibility of the network layer is to enable any pair of
`systems in the network to communicate with each other. A "fully connected"
`network is one in which every pair of nodes has a direct link between them, but
`this kind of topology does not scale beyond a few nodes. Therefore, in the more
`typical case, the network layer must find a path through a series of connected
`nodes, and nodes along the path must forward packets in the appropriate direc(cid:173)
`tion. The network layer deals with such problems as route calculation, packet
`fragmentation and reassembly (when different links in the network have differ(cid:173)
`ent maximum packet sizes), and congestion control.
`
`4. Transport layer: The responsibility of the transport layer is to establish a reli(cid:173)
`able communication stream between a pair of systems. It deals with errors that
`can be introduced by _the network layer, such as lost packets, duplicated packets,
`packet reordering, and fragmentation and reassembly (so that the user of the
`transport layer can deal with larger-size messages and so that less efficient net(cid:173)
`work layer fragmentation and reassembly might be avoided).
`
`5. Session layer: The responsibility of OSl's session layer is to offer services
`above the simple full-duplex re~iable communication stream provided by trans(cid:173)
`port, such.as dialogue control (enforcing a particular pattern of communication
`between systems) and chaining (combining groups of packets so that either all
`or none in-the group gets delivered).
`
`6. Presentation layer: The responsibility of OSI's presentation layer is to provide a
`means by which OSI applications can agree on representations for data.
`
`7. Application layer: Many OSI applications are currently, or are soon to become,
`standard, such as FTAM (file transfer, access, and management services) and
`VT (virtual terminal services). It is common for multiple applications to be run(cid:173)
`ning concurrently in a node.
`
`In this book, the data link layer is relevant because bridges operate within the data link
`layer and because the service provided by the data link layer is relevant to routers,
`which operate at the network layer, thereby making the network layer obviously rele(cid:173)
`vant as well. The transport layer is somewhat relevant because it is a user of the network
`layer and certain decisions that the network layer might make (such as whether to allow
`traffic to be split among several equivalent paths) affect the transport layer. The layers
`above transport are pretty much irrelevant to the study of bridges and routers.
`
`: unstruc(cid:173)
`: size and
`:s to elec(cid:173)
`rent types
`rent types
`:quires its
`'.fiber dis-
`line will
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 5 of 12
`
`

`

`4
`
`ESSENTIAL NETWORKING CONCEPTS
`
`LAYERS
`
`,.
`
`Typically, the way layer n works is that it receives a chunk of data from layer n+ 1,
`along with additional information (such as the destination address) that might be
`required. Layer n must transmit the data to the layer n process in the destination node,
`which delivers it to the layer n+ 1 process in the destination node. Layer n often needs
`to include with the data certain information-for instance, the address of the destina(cid:173)
`tion-that will be interpreted by other layer n entities. In order to get the information to
`the destination node, layer n hands down a buffer to layer n - 1, including the data
`received from layer n + 1 and the control information added by layer n. Additionally
`layer n might pass other information in the layer n/n-1 interface along with the buffer.
`Now for an example of how layering works. Assume that the physical layer allows a
`stream of bits to pass from one machine to another. The data link layer marks the bit
`stream, so that the beginning and end of a packet can be found, and adds a checksum to
`the packet, so thaJ the receiving machine can detect whether noise on the line introduced
`errors.
`There are various interesting techniques to ensure that the mar.ker indic~ting that the
`packet is starting or ending does not appear inside the data. One technique, is- known as
`bit stuffing. In bit stuffing, the marker is a sequence of six 1 's. To ensure that six consec(cid:173)
`utive l's do not appear in the data portion of a packet, the hardware automatically adds
`an extra 0 after five consecutive l's. The receiving hardware knows that if the next bit
`after five consecutive 1 's is a 0, then the 0 should be removed and ignored. If the next
`bit after five consecutive 1 's is a 1, then it is a signal for the beginning or end of a
`packet. Another technique involves using different physical signals for data bits (l's and
`O's) than for markers.
`The network layer allows communication across multiple hops by cooperating with
`the network layers in all the connected machines to compute routes.
`
`l,
`
`destination
`
`Figure 1.2
`
`When the network layer receives a packet from the transport layer for transmission, the
`network layer adds a header, which includes information such as the destination
`address; chooses an appropriate link on which to dispatch the packet; and hands the
`packet plus the network layer header to the data link layer process responsible for the
`outgoing link.
`
`SH= sei
`TH= tra
`NH= ne1
`DH= da1
`
`When t
`layer, ti
`layer, v
`handed
`the net,
`networ1
`based o
`count),
`outgoin
`In 1
`invente,
`peer la)
`discuss1
`with a
`with otl
`transpo
`Wb
`known
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 6 of 12
`
`

`

`)NCEPTS
`
`!r n+ 1,
`ight be
`n node,
`n needs
`iestina-
`ation to
`he data
`tionally
`mffer.
`11lows a
`; the bit
`ksum to
`roduced
`
`that the
`nown as
`consec-
`Llly adds
`next bit
`the next
`:!nd of a
`(l's and
`
`ing with
`
`ssion, the
`stination
`1ands the
`le for the
`
`LAYERS
`
`5
`
`application
`
`application
`
`presentation
`
`presentation
`
`session
`
`session
`
`transport
`
`transport
`
`network
`
`network
`
`data link
`
`data link
`
`physical
`
`physical
`
`t
`I DH I NH I TH I SH I t
`I DH I NH I TH I SH I t
`
`i
`i
`
`I DH I NH I TH I SH I
`
`I DH I NH I TH I SH I
`
`SH = session header
`TH = transport header
`NH = network header
`DH = data link header
`
`-~ I I
`
`Figure 1.3
`
`When the packet is received by an intermediate node, it is processed by the data link
`layer, the ·data link layer header is removed, and the packet is passed up to the network
`layer, where the pattet looks exactly the way it did when the previous network layer
`handed the packet to the data link layer-i.e., it has everything transport sent down, plus
`the network layer header. The network layer process at the receiving node looks at the
`network layer header, makes a decision as to the direction in which the packet should go
`based on that header, modifies the header as necessary (for instance, incrementing a hop
`count), and gives the modified packet to the data link layer process responsible for the
`outgoing link (see Fig. 1.4).
`In the preceding description, words like packet can be confusing. The ISO has
`invented terminology that makes everything precise. Each layer communicates with its
`peer layer through a protocol data unit, or PDU. To make it clear which layer is being
`discussed, a single-letter prefix is added to 'PDU.' The data link layer communicates
`with a peer data link layer by transmitting LPDUs. The network layer communicates
`with other network layers through NPDUs. The transport layer communicates with other
`transport layers through TPDUs.
`When layer n + 1 gives information to layer n for transmission, the information is
`known as an SDU, or service data unit. As with PDUs, a single-letter prefix is added to
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 7 of 12
`
`

`

`6
`
`ESSENTIAL NETWORKING CONCEPTS
`
`application
`
`application
`
`presentation
`
`presentation
`
`session
`
`session
`
`transport
`
`transport
`
`network
`
`data link
`
`physical
`
`network
`
`data link
`
`--
`
`physical
`
`t
`t
`t
`
`I DH I NH I TH I SH I
`
`I DH I NH I TH I SH I
`
`I DH I NH I TH I SH I
`
`i
`
`application
`
`presentation
`
`session
`
`transport
`
`network
`
`data link
`
`I DH I NH I TH I SH I
`
`physical
`
`DH NH TH SH
`
`Figure 1.4
`
`i
`i
`
`I DH I NH I TH I SH I
`
`I DH I NH I TH I SH I
`
`t
`t
`
`eliminate ambiguity. When the transport layer wishes to transmit a TPDU to another
`transport layer, it must do so by giving the network layer an NSDU. The network layer
`takes the NSDU, adds a header, and transmits it (through the data link layer) as an NPDU.
`
`- - - - - - - - - - - - - - - - - - -
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 8 of 12
`
`

`

`r I
`
`I
`
`ii
`
`·l
`tl
`('
`
`CONCEPTS
`
`I
`
`cS
`~
`~
`~
`~
`6
`
`application
`
`t PSDU
`t SSDU
`
`presentation
`
`session
`
`t TSOU
`t NSDU
`t LSDU
`
`transport
`
`network
`
`data link
`
`SERVICE MODELS
`
`7
`
`APDU
`
`PPDU
`
`SPDU
`
`TPDU
`
`Npou
`
`LPDU
`
`application
`
`presentation
`
`session
`
`transport
`
`network
`
`data link
`
`. t PhSDU
`,.. L __ n 6_ . _' _
`
`.
`
`pnys1ca
`
`__. _____ P_hP_D_LJ _____ ._ __ h_• -'-~
`p ys1ca
`
`Figure 1.5
`
`As a rule, the ISO terminology will not be used in this book, since it is wordy and hard to
`translate "in real time" until one has attended at least three standards meetings. However,
`the ISO terminology will occasionally be used, when it is necessary to be very precise.
`
`1.2 Service Models
`
`to another
`work layer
`anNPDU.
`
`In general, the service provided by layer n-1 for layer n consists of transmitting data.
`Layer n provides layer n-1 with data (an SDU) plus some extra information, such as
`the address of the destination. Layer n must also be able to receive data from a peer
`layer n, which it does by having layer n-1 inform it that data is available.
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 9 of 12
`
`

`

`;SUES
`
`d by
`ht be
`
`802.5
`issue
`sym(cid:173)
`at the
`tgnifi(cid:173)
`group
`ted on
`
`There(cid:173)
`:ant bit
`
`rnit the
`
`rst:
`
`]001
`
`]
`
`rst:
`
`Q1010
`
`:en 802.5
`
`;her-layer
`1hich are
`)t convert
`sage, then
`.out deter-
`1ation that
`
`LANs has
`nstance, at
`link header
`bridges did
`1 the proto(cid:173)
`opt was to
`shuffle the
`
`LLC
`
`33
`
`address bits in the data link header on packets with that protocol type. As a result,
`bridged packets from that protocol will have different addresses than they should. There
`are two major problems that this can cause: (1) the station address-when the bits are in
`the flipped order-might appear on the LAN to be a multicast address, which may in
`turn confuse source routing bridges into misparsing the packet and cause transparent
`bridges to refuse to forward the packet; or (2) the station address with the flipped order
`might turn into an address used by another station.
`
`2.7 LLC
`
`LLC (which stands for logical link control) is described in the specs as if it were a sub(cid:173)
`layer separate from the MAC sublayer. If people had agreed upon a datagram model for
`LANs, the 802 committee might not have felt the ne~d to subdivide the LAN data link
`layer into MAC and LLC.
`As stated earlier in this chapter, three types of LLC are currently defined. Type 1 is
`datagram, type 2 is connection-oriented, and type 3 is semireliable.
`The sublayering defined by the 802 committee has only the data link layer fields
`DSAP, SSAP, and CTL within LLC. The source and destination addresses are actually
`considered part of the MAC. sublayer, which technically means that each individual
`LAN committee (802.3, 802.5, etc.) can define addresses as it chooses. It is lucky that
`addresses across different LANs are pretty much the same. Unfortunately, they are not
`identical, because of bit-ordering issues and problems in 802.5 with arbitrary multicast
`addresses, to be described later in this chapter. In fact, with 802.5, the addresses started
`out being different-they were originally_ hierarchical, with a portion of the 6 bytes indi(cid:173)
`cating the ring number on which a station resided and the remainder of the address indi(cid:173)
`cating the station number with respect to that ring. That has been changed to tie 6 bytes
`of station aodress, as on the other LANs.
`The CTL ("control") field in LLC type 1 (datagrams) is always 1 byte long and is
`always equal to one of three values:
`
`1. UI, which stands for "unnumbered information." (This just means it's a datagram.)
`
`2. X/D, which stands for "exchange identification." There are tio types of XID,
`"response" and "command." Command informs the recipient of the identity of
`the transmitter of the XID command message, and which LLC types the trans(cid:173)
`mitter supports. Response is the required reply to an XID command message. It
`contains the same information as the XID command-i.e., it includes the iden(cid:173)
`tity of the transmitter of the XID response message and which LLC types the
`transmitter supports.
`
`3. TEST. As with XID, there are two types of TEST message, "command" and
`"response." TEST is used to check whether a packet can be sent to the recipient
`and returned. Included in the command is any arbitrary data. The data in the
`TEST response is copied from the data in the TEST command.
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 10 of 12
`
`

`

`34
`
`DATA LINK LA YER ISSUES
`
`Command and response packets in XID and TEST are distinguished based on a bit in
`the SSAP field! The 802.2 committee decided that there was no reason anyone would
`want to transmit a packet from a group SAP, so the bit in the SSAP designated to indi(cid:173)
`cate group or individual actually indicates command or response.
`In LLC type 2, the CTL field is either 1 or 2 bytes long, depending on what type of
`packet it is. The packet types for which the CTL field is 2 bytes contain at least one
`sequence number. These packets are:
`
`l. I (stands for "information") is a data packet. In this case, the CTL field is 2
`bytes long and includes 7 bits of sequence number for the data packets being
`transmitted from source S to destination D, plus 7 bits of sequence number for
`th~ acknowledgments for packets being received from D by S.
`
`2. RR ("receive ready") is an acknowledgment. It contains a sequence number and
`indicates that all packets with sequence numbers lower th~n that have been
`received. It also indicates that the receiver is prepare~ _.!O receive more dlfta.
`3. RNR ("receive not ready") is an acknowledgment for previously transmitted
`packets (with numbers lower than the number in the receive sequence number
`field in the RNR), just like the RR However, it also indicates that the receiver is
`temporarily busy and that further packets should not be transmitted until the
`receiver indicates it can accept new packets, by transmitting an RR.
`
`4. REJ ("reject") indicates that the receiver is requesting retransmission of packets
`starting with the number in the receive sequence number field.
`
`The other LLC type 2 packet types, which use a I-byte CTL field, are:
`
`l. SABME ("set asynchronous balanced mode extended"-aren't you sorry you
`asked?) requests that a connection be started. The bizarre name for the com(cid:173)
`mand is historical.
`
`2. DISC ("disconnect") requests that a connection be ended.
`
`3. DM ("disconnected mode") is transmitted in response to a DISC, indicating that
`the recipient of the DISC has indeed received the DISC.
`
`4. FRMR ("frame reject") indicates receipt of an invalid packet -for example,
`one containing an out-of-order sequence number.
`
`5. UA ("unnumbered acknowledgment") acknowledges a DISC or SABME
`message.
`
`2.8
`
`Issues in 802.3
`
`The 802.3 LAN access is based on contention. The technology is known as CSMAICD,
`which stands for "carrier sense multiple access with collision detection." Carrier sense
`means that a station wishing to transmit first listens, and if another station is transmitting,
`
`.I
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 11 of 12
`
`

`

`'ING
`
`:ea
`ode
`:her
`the
`lto
`the
`
`ow(cid:173)
`tyer
`that
`the
`om(cid:173)
`will
`2 is
`iata
`for-
`
`, the
`
`net(cid:173)
`was
`pur-
`
`,sec-
`
`table
`:ally
`Lters,
`
`ially
`et to
`r E2
`~AN
`and
`mse,
`
`COMPARISON
`
`201
`
`3. El wishes to communicate with E3. In both protocols, if El chooses the "wrong"
`router, RI, that router forwards the packet anyway and sends a redirect. The only
`difference is that in IP, an additional ARP query might be needed to find R2's
`data link layer address.
`
`4. El wishes to communicate with E4. In both protocols, El chooses either router,
`and the packet is forwarded without complaint.
`
`5. RI and R2 are down, and El wishes to communicate with E3. Neither protocol
`will succeed in getting El to converse with E3 because there is no connectivity
`between them. In ISO, El will send the packet to the group address ALL ESs,
`which bothers all the ESs and gets no response. In IP, El will send the packet to
`one of the routers and get no response.
`If at some point some mechanism (similar in functionality to ES-IS) is
`added to IP to inform the endnodes that the routers are down, then El will know
`it cannot reach E3. In the IP mechanism, even in the absence of a means for El
`to know that the routers are down, El's "useless" packet to the router is less
`costly than ISO's "useless" packet multicast to ALL ESs because the IP message
`does not cause software interrupts at all the endnodes on the LAN. (However,
`this situation only occurs when all the LAN routers are down.)
`
`6. RI and R2 are down, and El wishes-to communicate with E2. In ISO, El sends
`the packet to the group address ALL ESs, which bothers all the ESs but does get
`a response from E2, which transmits its ESH to El. El thereupon puts E2 into
`its destination cache, and future transmissions work as desired. In IP, El knows
`that E2 is on the LAN and does an ARP query to get the data link layer address.
`In this case, the ISO and IP schemes are functionally almost identical. The only
`differerice is that in ISO the multicast packet actually carries the data. In IP the
`ARP query and response must be transmitted before the first data packet
`between ·Ei and E2 can be transmitted.
`
`7. R2 has goqe down, but E2's information indicates that traffic for E3 should be
`redirected toward R2. In ISO, lack of receipt of ISHs from R2 will alert E2 that
`R2 has gone down. When E2 notices this, it scans its destination cache for
`entries using R2's network layer address and deletes them. In IP, there is no
`mechanism for E2 to discover that R2 is down.
`
`8.5 Comparison
`
`Both the ISO and TCP/IP schemes require a certain amount of control traffic on a LAN.
`In ISO, the overhead is primarily due to ESHs (there are so few routers that the over(cid:173)
`head due to ISHs is insignificant). In TCP/IP, the overhead is due to ARP queries and
`responses. Evaluating the significance of the bandwidth usage in either scheme is an
`interesting research problem.
`
`I
`
`I
`
`,:
`
`Ex.1018
`CISCO SYSTEMS, INC. / Page 12 of 12
`
`