`
`THIRD EDITION THIRD EDITION
`
`
`
`MPUTER NETWORKS MPUTER NETWORKS
`
`
`
`ANDREW S. TANENBAUM ANDREW S. TANENBAUM
`
`Broadcasting
`Broadcasting
`
`Bridge
`Bridge
`
`Congestion
`Congestion
`
`
`SHALL I COMPARE THEE SHALL I COMPARE THEE
`
`TO A SUMMER'S DAY? TO A SUMMER'S DAY?
`
`oLeaky
`Leaky
`bucket
`bucket
`
`
`WELCOME WELCOME
`
`TO THE TO THE
`
`INFORMATION INFORMATION
`
`SUPER SUPER
`
`HIGHWAY HIGHWAY
`
`
`
`1 1
`
`Collisio
`Collisio
`
`
`
`1000100110 5 1000100110 5
`
`
`
`1100110110 4 1100110110 4
`
`
`
`0110110011 2 0110110011 2
`
`
`
`NFLE 1015 - Page 1
`
`

`

`Library of Congress Cataloging in Publication Data
`Library of Congress Cataloging in Publication Data
`
`
`Tanenbaum, Andrew S. 1944-. Tanenbaum, Andrew S. 1944-.
`
`Computer networks / Andrew S. Tanenbaum. -- 3rd ed. Computer networks / Andrew S. Tanenbaum. -- 3rd ed.
`p.
`cm.
`p.
`cm.
`
`Includes bibliographical references and index. Includes bibliographical references and index.
`
`ISBN 0-13-349945-6 ISBN 0-13-349945-6
`
`1.Computer networks. I. Title. 1.Computer networks. I. Title.
`
`TK5105.5.T36 1996 TK5105.5.T36 1996
`
`004.6--dc20 004.6--dc20
`
`96-4121
`96-4121
`
`CIP CIP
`
`
`Editorial/production manager: Camille Trentacoste Editorial/production manager: Camille Trentacoste
`
`Interior design and composition: Andrew S. Tanenbaum Interior design and composition: Andrew S. Tanenbaum
`Cover design director: Jerry Votta
`Cover design director: Jerry Votta
`
`Cover designer: Don Martinetti, DM Graphics, Inc. Cover designer: Don Martinetti, DM Graphics, Inc.
`Cover concept: Andrew S. Tanenbaum, from an idea by Marilyn Tremaine
`Cover concept: Andrew S. Tanenbaum, from an idea by Marilyn Tremaine
`
`Interior graphics: Hadel Studio Interior graphics: Hadel Studio
`
`Manufacturing manager: Alexis R. Heydt Manufacturing manager: Alexis R. Heydt
`
`Acquisitions editor: Mary Franz Acquisitions editor: Mary Franz
`
`Editorial Assistant: Noreen Regina Editorial Assistant: Noreen Regina
`
`
`1996 by Prentice Hall PTR 1996 by Prentice Hall PTR
`
`Prentice-Hall, Inc. Prentice-Hall, Inc.
`A Simon & Schuster Company
`A Simon & Schuster Company
`
`Upper Saddle River, New Jersey 07458 Upper Saddle River, New Jersey 07458
`
`
`The publisher offers discounts on this book when ordered in bulk quantities. For more information, The publisher offers discounts on this book when ordered in bulk quantities. For more information,
`contact:
`contact:
`
`Corporate Sales Department, Prentice Hall PTR, One Lake Street, Upper Saddle River, NJ 07458. Corporate Sales Department, Prentice Hall PTR, One Lake Street, Upper Saddle River, NJ 07458.
`
`Phone: (800) 382-3419; Fax: (201) 236-7141. E-mail: corpsales@prenhall.com Phone: (800) 382-3419; Fax: (201) 236-7141. E-mail: corpsales@prenhall.com
`
`
`All rights reserved. No part of this book may be reproduced, in any form or by any means, without All rights reserved. No part of this book may be reproduced, in any form or by any means, without
`
`permission in writing from the publisher. permission in writing from the publisher.
`
`All product names mentioned herein are the trademarks of their respective owners.
`All product names mentioned herein are the trademarks of their respective owners.
`
`
`Printed in the United States of America Printed in the United States of America
`
`10 9 8 7 6 5 4 10 9 8 7 6 5 4
`
`
`
`ISBN 0-13-349945-6 ISBN 0-13-349945-6
`
`
`Prentice-Hall International (UK) Limited, London Prentice-Hall International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall of Australia Pty. Limited, Sydney
`
`Prentice-Hall Canada Inc., Toronto Prentice-Hall Canada Inc., Toronto
`
`Prentice-Hall Hispanoamericana, S.A., Mexico Prentice-Hall Hispanoamericana, S.A., Mexico
`
`Prentice-Hall of India Private Limited, New Delhi Prentice-Hall of India Private Limited, New Delhi
`
`Prentice-Hall of Japan, Inc., Tokyo Prentice-Hall of Japan, Inc., Tokyo
`
`Simon & Schuster Asia Pte. Ltd., Singapore Simon & Schuster Asia Pte. Ltd., Singapore
`
`Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`
`
`NFLE Ex. 1015 - Page 2
`
`
`
`
`
`NFLE 1015 - Page 2
`
`

`

`
`
`SEC. 2.4 SEC. 2.4
`
`
`
`THE TELEPHONE SYSTEM THE TELEPHONE SYSTEM
`
`
`
`131 131
`
`
`town, and the other one's wife was the town telephone operator. He quickly saw town, and the other one's wife was the town telephone operator. He quickly saw
`
`that either he was going to have to invent automatic telephone switching equip-that either he was going to have to invent automatic telephone switching equip-
`
`ment or he was going to go out of business. He chose the first option. For nearly ment or he was going to go out of business. He chose the first option. For nearly
`
`100 years, the circuit switching equipment used worldwide was known as 100 years, the circuit switching equipment used worldwide was known as
`
`Strowger gear. (History does not record whether the now-unemployed switch-Strowger gear. (History does not record whether the now-unemployed switch-
`
`board operator got a job as an information operator, answering questions such as: board operator got a job as an information operator, answering questions such as:
`
`What is the phone number of an undertaker? What is the phone number of an undertaker?
`
`The model shown in Fig. 2-34(a) is highly simplified of course, because parts The model shown in Fig. 2-34(a) is highly simplified of course, because parts
`
`of the "copper" path between the two telephones may, in fact, be microwave of the "copper" path between the two telephones may, in fact, be microwave
`
`links onto which thousands of calls are multiplexed. Nevertheless, the basic idea links onto which thousands of calls are multiplexed. Nevertheless, the basic idea
`
`is valid: once a call has been set up, a dedicated path between both ends exists and is valid: once a call has been set up, a dedicated path between both ends exists and
`
`will continue to exist until the call is finished. will continue to exist until the call is finished.
`
`
`Physical copper Physical copper
`
`connection set up connection set up
`
`when call is made when call is made
`
`
`
`L L
`
`
`
`Computer Computer
`
`
`
`Switching office Switching office
`
`
`
`/ /
`
`
`Packets queued up Packets queued up
`
`for subsequent for subsequent
`
`transmission transmission
`
`
`
`(a) (a)
`
`
`
`(b) (b)
`
`Fig. 2-34. (a) Circuit switching. (b) Packet switching.
`Fig. 2-34. (a) Circuit switching. (b) Packet switching.
`
`
`An important property of circuit switching is the need to set up an end-to-end An important property of circuit switching is the need to set up an end-to-end
`
`path before any data can be sent. The elapsed time between the end of dialing and path before any data can be sent. The elapsed time between the end of dialing and
`
`the start of ringing can easily be 10 sec, more on long-distance or international the start of ringing can easily be 10 sec, more on long-distance or international
`
`calls. During this time interval, the telephone system is hunting for a copper path, calls. During this time interval, the telephone system is hunting for a copper path,
`
`as shown in Fig. 2-35(a). Note that before data transmission can even begin, the as shown in Fig. 2-35(a). Note that before data transmission can even begin, the
`
`call request signal must propagate all the way to the destination, and be call request signal must propagate all the way to the destination, and be
`
`NFLE Ex. 1015 - Page 3
`
`
`
`NFLE 1015 - Page 3
`
`

`

`
`
`SEC. 2.4 SEC. 2.4
`
`
`
`THE TELEPHONE SYSTEM THE TELEPHONE SYSTEM
`
`
`
`131 131
`
`
`town, and the other one's wife was the town telephone operator. He quickly saw town, and the other one's wife was the town telephone operator. He quickly saw
`
`that either he was going to have to invent automatic telephone switching equip-that either he was going to have to invent automatic telephone switching equip-
`
`ment or he was going to go out of business. He chose the first option. For nearly ment or he was going to go out of business. He chose the first option. For nearly
`
`100 years, the circuit switching equipment used worldwide was known as 100 years, the circuit switching equipment used worldwide was known as
`
`Strowger gear. (History does not record whether the now-unemployed switch-Strowger gear. (History does not record whether the now-unemployed switch-
`
`board operator got a job as an information operator, answering questions such as: board operator got a job as an information operator, answering questions such as:
`
`What is the phone number of an undertaker? What is the phone number of an undertaker?
`
`The model shown in Fig. 2-34(a) is highly simplified of course, because parts The model shown in Fig. 2-34(a) is highly simplified of course, because parts
`
`of the "copper" path between the two telephones may, in fact, be microwave of the "copper" path between the two telephones may, in fact, be microwave
`
`links onto which thousands of calls are multiplexed. Nevertheless, the basic idea links onto which thousands of calls are multiplexed. Nevertheless, the basic idea
`
`is valid: once a call has been set up, a dedicated path between both ends exists and is valid: once a call has been set up, a dedicated path between both ends exists and
`
`will continue to exist until the call is finished. will continue to exist until the call is finished.
`
`Lr
`Lr
`
`
`
`Computer Computer
`
`
`Physical copper Physical copper
`
`connection set up connection set up
`
`when call is made when call is made
`
`
`
`Ci Ci
`
`LJ
`
`
`
`Switching office Switching office
`
`
`Packets queued up Packets queued up
`
`for subsequent for subsequent
`
`transmission transmission
`
`
`
`III III III III
`
`
`
`q q
`
`Computer
`Computer
`
`
`
`(a) (a)
`
`
`
`(b) (b)
`
`Fig. 2-34. (a) Circuit switching. (b) Packet switching.
`Fig. 2-34. (a) Circuit switching. (b) Packet switching.
`
`
`An important property of circuit switching is the need to set up an end-to-end An important property of circuit switching is the need to set up an end-to-end
`
`path before any data can be sent. The elapsed time between the end of dialing and path before any data can be sent. The elapsed time between the end of dialing and
`
`the start of ringing can easily be 10 sec, more on long-distance or international the start of ringing can easily be 10 sec, more on long-distance or international
`
`calls. During this time interval, the telephone system is hunting for a copper path, calls. During this time interval, the telephone system is hunting for a copper path,
`
`as shown in Fig. 2-35(a). Note that before data transmission can even begin, the as shown in Fig. 2-35(a). Note that before data transmission can even begin, the
`
`call request signal must propagate all the way to the destination, and be call request signal must propagate all the way to the destination, and be
`
`NFLE Ex. 1015 - Page 4
`
`
`
`
`
`
`NFLE 1015 - Page 4
`
`

`

`132
`132
`
`
`
`THE PHYSICAL LAYER THE PHYSICAL LAYER
`
`CHAP. 2
`CHAP. 2
`
`acknowledged. For many computer applications (e.g., point-of-sale credit verifi-
`acknowledged. For many computer applications (e.g., point-of-sale credit verifi-
`cation), long setup times are undesirable.
`cation), long setup times are undesirable.
`
`Call request signal
`Call request signal
`
`Propagation
`Propagation
`delay
`delay
`
`Msg
`Msg
`
`I
`I
`
`Msg
`Msg
`
`Queuing
`Queuing
`delay
`delay
`
`Msg
`Msg
`
`Time
`Time
`spent
`spent
`hunting
`hunting
`for an
`for an
`outgoing
`outgoing
`trunk
`trunk
`
`Data
`Data
`
` Call
` Call
` accept
` accept
`signal
`- signal
`
`AB
`AB
`trunk
`trunk
`
`BC
`BC
`trunk
`trunk
`
`CD
`CD
`trunk
`trunk
`
`Pkt 1
`Pkt 1
`
`Pkt 2
`Pkt 2
`
`Pkt 3
`Pkt 3
`
`Pkt 1
`Pkt 1
`
`Pkt 2
`Pkt 2
`
`Pkt 3
`Pkt 3
`
`
`
`Pkt 1 Pkt 1
`
`
`
`Pkt 2 Pkt 2
`
`Pkt 3
`Pkt 3
`
`A
`A
`
`B
`B
`
`C
`C
`
`D
`D
`
`
`
`A A
`
`B
`B
`
`C
`C
`
`D
`D
`
`A
`A
`
`(a)
`(a)
`
`(b)
`(b)
`
`(c)
`(c)
`
`Fig. 2-35. Timing of events in (a) circuit switching, (b) message switching,
`Fig. 2-35. Timing of events in (a) circuit switching, (b) message switching,
`
`(c) packet switching. (c) packet switching.
`
`As a consequence of the copper path between the calling parties, once the
`As a consequence of the copper path between the calling parties, once the
`
`setup has been completed, the only delay for data is the propagation time for the setup has been completed, the only delay for data is the propagation time for the
`
`electromagnetic signal, about 5 msec per 1000 km. Also as a consequence of the electromagnetic signal, about 5 msec per 1000 km. Also as a consequence of the
`established path, there is no danger of congestion—that is, once the call has been
`established path, there is no danger of congestion—that is, once the call has been
`put through, you never get busy signals, although you might get one before the
`put through, you never get busy signals, although you might get one before the
`connection has been established due to lack of switching or trunk capacity.
`connection has been established due to lack of switching or trunk capacity.
`An alternative switching strategy is message switching, shown in Fig. 2-
`An alternative switching strategy is message switching, shown in Fig. 2-
`35(b). When this form of switching is used, no physical copper path is established
`35(b). When this form of switching is used, no physical copper path is established
`in advance between sender and receiver. Instead, when the sender has a block of
`in advance between sender and receiver. Instead, when the sender has a block of
`data to be sent, it is stored in the first switching office (i.e., router) and then for-
`data to be sent, it is stored in the first switching office (i.e., router) and then for-
`warded later, one hop at a time. Each block is received in its entirety, inspected
`warded later, one hop at a time. Each block is received in its entirety, inspected
`
`NFLE Ex. 1015 - Page 5
`
`
`
`
`
`
`
`
`NFLE 1015 - Page 5
`
`

`

`SEC. 2.4
`SEC. 2.4
`
`THE TELEPHONE SYSTEM
`THE TELEPHONE SYSTEM
`
`133
`133
`
`for errors, and then retransmitted. A network using this technique is called a
`for errors, and then retransmitted. A network using this technique is called a
`store-and-forward network, as mentioned in Chap. 1.
`store-and-forward network, as mentioned in Chap. 1.
`The first electromechanical telecommunication systems used message switch-
`The first electromechanical telecommunication systems used message switch-
`ing, namely for telegrams. The message was punched on paper tape off-line at the
`ing, namely for telegrams. The message was punched on paper tape off-line at the
`sending office, and then read in and transmitted over a communication line to the
`sending office, and then read in and transmitted over a communication line to the
`next office along the way, where it was punched out on paper tape. An operator
`next office along the way, where it was punched out on paper tape. An operator
`
`there tore the tape off and read it in on one of the many tape readers, one per out-there tore the tape off and read it in on one of the many tape readers, one per out-
`going trunk. Such a switching office was called a torn tape office.
`going trunk. Such a switching office was called a torn tape office.
`
`With message switching, there is no limit on block size, which means that With message switching, there is no limit on block size, which means that
`routers (in a modern system) must have disks to buffer long blocks. It also means
`routers (in a modern system) must have disks to buffer long blocks. It also means
`that a single block may tie up a router-router line for minutes, rendering message
`that a single block may tie up a router-router line for minutes, rendering message
`
`switching useless for interactive traffic. To get around these problems, packet switching useless for interactive traffic. To get around these problems, packet
`
`switching was invented. Packet-switching networks place a tight upper limit on switching was invented. Packet-switching networks place a tight upper limit on
`
`block size, allowing packets to be buffered in router main memory instead of on block size, allowing packets to be buffered in router main memory instead of on
`disk. By making sure that no user can monopolize any transmission line very long
`disk. By making sure that no user can monopolize any transmission line very long
`(milliseconds), packet-switching networks are well suited to handling interactive
`(milliseconds), packet-switching networks are well suited to handling interactive
`traffic. A further advantage of packet switching over message switching is shown
`traffic. A further advantage of packet switching over message switching is shown
`
`in Fig. 2-35(b) and (c): the first packet of a multipacket message can be forwarded in Fig. 2-35(b) and (c): the first packet of a multipacket message can be forwarded
`before the second one has fully arrived, reducing delay and improving throughput.
`before the second one has fully arrived, reducing delay and improving throughput.
`For these reasons, computer networks are usually packet switched, occasionally
`For these reasons, computer networks are usually packet switched, occasionally
`circuit switched, but never message switched.
`circuit switched, but never message switched.
`Circuit switching and packet switching differ in many respects. The key
`Circuit switching and packet switching differ in many respects. The key
`difference is that circuit switching statically reserves the required bandwidth in
`difference is that circuit switching statically reserves the required bandwidth in
`advance, whereas packet switching acquires and releases it as it is needed. With
`advance, whereas packet switching acquires and releases it as it is needed. With
`circuit switching, any unused bandwidth on an allocated circuit is just wasted.
`circuit switching, any unused bandwidth on an allocated circuit is just wasted.
`With packet switching it may be utilized by other packets from unrelated sources
`With packet switching it may be utilized by other packets from unrelated sources
`going to unrelated destinations, because circuits are never dedicated. However,
`going to unrelated destinations, because circuits are never dedicated. However,
`just because no circuits are dedicated, a sudden surge of input traffic may
`just because no circuits are dedicated, a sudden surge of input traffic may
`overwhelm a router, exceeding its storage capacity and causing it to lose packets.
`overwhelm a router, exceeding its storage capacity and causing it to lose packets.
`
`In contrast, with circuit switching, when packet switching is used, it is In contrast, with circuit switching, when packet switching is used, it is
`straightforward for the routers to provide speed and code conversion. Also, they
`straightforward for the routers to provide speed and code conversion. Also, they
`can provide error correction to some extent. In some packet-switched networks,
`can provide error correction to some extent. In some packet-switched networks,
`however, packets may be delivered in the wrong order to the destination. Reor-
`however, packets may be delivered in the wrong order to the destination. Reor-
`dering of packets can never happen with circuit switching.
`dering of packets can never happen with circuit switching.
`Another difference is that circuit switching is completely transparent. The
`Another difference is that circuit switching is completely transparent. The
`sender and receiver can use any bit rate, format, or framing method they want to.
`sender and receiver can use any bit rate, format, or framing method they want to.
`
`The carrier does not know or care. With packet switching, the carrier determines The carrier does not know or care. With packet switching, the carrier determines
`the basic parameters. A rough analogy is a road versus a railroad. In the former,
`the basic parameters. A rough analogy is a road versus a railroad. In the former,
`the user determines the size, speed, and nature of the vehicle; in the latter, the car-
`the user determines the size, speed, and nature of the vehicle; in the latter, the car-
`rier does. It is this transparency that allows voice, data, and fax to coexist within
`rier does. It is this transparency that allows voice, data, and fax to coexist within
`the phone system.
`the phone system.
`A final difference between circuit and packet switching is the charging algo-
`A final difference between circuit and packet switching is the charging algo-
`rithm. Packet carriers usually base their charge on both the number of bytes (or
`rithm. Packet carriers usually base their charge on both the number of bytes (or
`
`NFLE Ex. 1015 - Page 6
`
`
`
`
`
`
`
`
`NFLE 1015 - Page 6
`
`

`

`134
`134
`
`THE PHYSICAL LAYER
`THE PHYSICAL LAYER
`
`CHAP. 2
`CHAP. 2
`
`
`packets) carried and the connect time. Furthermore, transmission distance usually packets) carried and the connect time. Furthermore, transmission distance usually
`
`does not matter, except perhaps internationally. With circuit switching, the does not matter, except perhaps internationally. With circuit switching, the
`
`charge is based on the distance and time only, not the traffic. The differences are charge is based on the distance and time only, not the traffic. The differences are
`
`summarized in Fig. 2-36. summarized in Fig. 2-36.
`
`
`
`Item Item
`
`
`
`Circuit-switched Packet-switched Circuit-switched Packet-switched
`
`Dedicated "copper" path Dedicated "copper" path
`
`
`Bandwidth available Bandwidth available
`
`Potentially wasted bandwidth Potentially wasted bandwidth
`
`Store-and-forward transmission Store-and-forward transmission
`
`
`
`Each packet follows the same route Each packet follows the same route
`
`
`
`Yes Yes
`
`
`
`Fixed Fixed
`
`
`
`Yes Yes
`
`
`
`No No
`
`
`
`Yes Yes
`
`
`
`No No
`
`
`
`Dynamic Dynamic
`
`
`
`No No
`
`
`
`Yes Yes
`
`
`
`No No
`
`
`
`Call setup Call setup
`
`
`
`When can congestion occur When can congestion occur
`
`
`
`--, --,
`
`
`
`Required Required
`
`
`
`Not needed Not needed
`
`
`
`At setup time At setup time
`
`
`
`On every packet On every packet
`
`
`
`Charging Charging
`
`
`
`Per minute Per minute
`
`
`
`Per packet Per packet
`
`Fig. 2-36. A comparison of circuit-switched and packet-switched networks.
`Fig. 2-36. A comparison of circuit-switched and packet-switched networks.
`
`Both circuit switching and packet switching are so important, we will come Both circuit switching and packet switching are so important, we will come
`
`back to them shortly and describe the various technologies used in detail. back to them shortly and describe the various technologies used in detail.
`
`
`
`The Switch Hierarchy The Switch Hierarchy
`
`
`It is worth saying a few words about how the routing between switches is It is worth saying a few words about how the routing between switches is
`
`done within the current circuit-switched telephone system. We will describe the done within the current circuit-switched telephone system. We will describe the
`
`AT&T system here, but other companies and countries use the same general prin-AT&T system here, but other companies and countries use the same general prin-
`
`ciples. The telephone system has five classes of switching offices, as illustrated ciples. The telephone system has five classes of switching offices, as illustrated
`
`in Fig. 2-37. There are 10 regional switching offices, and these are fully intercon-in Fig. 2-37. There are 10 regional switching offices, and these are fully intercon-
`
`nected by 45 high-bandwidth fiber optic trunks. Below the regional offices are 67 nected by 45 high-bandwidth fiber optic trunks. Below the regional offices are 67
`
`sectional offices, 230 primary offices, 1300 toll offices, and 19,000 end offices. sectional offices, 230 primary offices, 1300 toll offices, and 19,000 end offices.
`
`The lower four levels were originally connected as a tree. The lower four levels were originally connected as a tree.
`
`Calls are generally connected at the lowest possible level. Thus if a sub-Calls are generally connected at the lowest possible level. Thus if a sub-
`
`scriber connected to end office 1 calls another subscriber connected to end office scriber connected to end office 1 calls another subscriber connected to end office
`
`1, the call will be completed in that office. However, a call from a customer 1, the call will be completed in that office. However, a call from a customer
`
`attached to end office 1 in Fig. 2-37 to a customer attached to end office 2 will attached to end office 1 in Fig. 2-37 to a customer attached to end office 2 will
`
`have to go toll office 1. However, a call from end office 1 to end office 4 will have to go toll office 1. However, a call from end office 1 to end office 4 will
`
`have to go up to primary office 1, and so on. With a pure tree, there is only one have to go up to primary office 1, and so on. With a pure tree, there is only one
`
`minimal route, and that would normally be taken. minimal route, and that would normally be taken.
`
`During years of operation, the telephone companies noticed that some routes During years of operation, the telephone companies noticed that some routes
`
`were busier than others. For example, there were many calls from New York to were busier than others. For example, there were many calls from New York to
`
`Los Angeles. Rather than go all the way up the hierarchy, they simply installed Los Angeles. Rather than go all the way up the hierarchy, they simply installed
`
`direct trunks for the busy routes. A few of these are shown in Fig. 2-37 as direct trunks for the busy routes. A few of these are shown in Fig. 2-37 as
`
`NFLE Ex. 1015 - Page 7
`
`
`
`NFLE 1015 - Page 7
`
`

`

`
`
`SEC. 2.4 SEC. 2.4
`
`THE TELEPHONE SYSTEM
`THE TELEPHONE SYSTEM
`
`135
`135
`
`10 Regional
`10 Regional
`offices
`offices
`(fully
`(fully
`interconnected)
`interconnected)
`
`67 Sectional
`67 Sectional
`offices
`offices
`
`230 Primary
`230 Primary
`offices
`offices
`
`1300 Toll
`1300 Toll
`offices
`offices
`
`19,000 End
`19,000 End
`offices
`offices
`
`0 0 0
`000
`o • \
`• • • • •
`
`2 3 4 5
`2 3 4 5
`
`
`
`200 Million telephone& 200 Million telephones_
`
`19,000
`19,000
`
`Fig. 2-37. The AT&T telephone hierarchy. The dashed lines are direct trunks.
`Fig. 2-37. The AT&T telephone hierarchy. The dashed lines are direct trunks.
`
`
`dashed lines. As a consequence, many calls can now be routed along many paths. dashed lines. As a consequence, many calls can now be routed along many paths.
`The actual route chosen is generally the most direct one, but if the necessary
`The actual route chosen is generally the most direct one, but if the necessary
`trunks along it are full, an alternative is chosen. This complex routing is now pos-
`trunks along it are full, an alternative is chosen. This complex routing is now pos-
`
`sible because a switching machine, like the AT&T 5 ESS, is in fact just a general sible because a switching machine, like the AT&T 5 ESS, is in fact just a general
`purpose computer with a large amount of very specialized I/O equipment.
`purpose computer with a large amount of very specialized I/O equipment.
`
`
`
`Crossbar Switches Crossbar Switches
`
`Let us now turn from how calls are routed among switches to how individual
`Let us now turn from how calls are routed among switches to how individual
`
`switches actually work inside. Several kinds of switches are (or were) common switches actually work inside. Several kinds of switches are (or were) common
`within the telephone system. The simplest kind is the crossbar switch (also
`within the telephone system. The simplest kind is the crossbar switch (also
`
`called a crosspoint switch), shown in Fig. 2-38. In a switch with n input lines called a crosspoint switch), shown in Fig. 2-38. In a switch with n input lines
`and n output lines (i.e., n full duplex lines), the crossbar switch has n 2
`and n output lines (i.e., n full duplex lines), the crossbar switch has n 2
`
`NFLE Ex. 1015 - Page 8
`
`
`
`
`
`
`
`NFLE 1015 - Page 8
`
`

`

`
`
`136 136
`
`
`
`THE PHYSICAL LAYER THE PHYSICAL LAYER
`
`
`
`CHAP. 2 CHAP. 2
`
`
`intersections, called crosspoints, where an input and an output line may be con-intersections, called crosspoints, where an input and an output line may be con-
`
`nected by a semiconductor switch, as shown in Fig. 2-38(a). In Fig. 2-38(b) we nected by a semiconductor switch, as shown in Fig. 2-38(a). In Fig. 2-38(b) we
`
`see an example in which line 0 is connected to line 4, line 1 is connected to line 7, see an example in which line 0 is connected to line 4, line 1 is connected to line 7,
`
`and line 2 is connected to line 6. Lines 3 and 5 are not connected. All the bits and line 2 is connected to line 6. Lines 3 and 5 are not connected. All the bits
`
`that arrive at the switch from line 4, for example, are immediately sent out of the that arrive at the switch from line 4, for example, are immediately sent out of the
`
`switch on line 0. Thus the crossbar switch implements circuit switching by mak-switch on line 0. Thus the crossbar switch implements circuit switching by mak-
`
`ing a direct electrical connection, just like the jumper cables in the first-generation ing a direct electrical connection, just like the jumper cables in the first-generation
`
`switches, only automatically and within microseconds. switches, only automatically and within microseconds.
`
`Potential connection
`Potential connection
`
`Actual connection
`Actual connection
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`0
`0
`
`
`
`1 1
`
`2 3 4 5
`2 3 4 5
`Outputs
`Outputs
`
`6 7
`6 7
`
`(a)
`(a)
`
`0
`0
`
`2 3 4 5 6 7
`2 3 4 5
`6 7
`Outputs
`Outputs
`
`(b)
`(b)
`
`Fig. 2-38. (a) A crossbar switch with no connections. (b) A crossbar switch
`Fig. 2-38. (a) A crossbar switch with no connections. (b) A crossbar switch
`with three connections set up: 0 with 4, 1 with 7, and 2 with 6.
`with three connections set up: 0 with 4, 1 with 7, and 2 with 6.
`
`The problem with a crossbar switch is that the number of crossbars grows as The problem with a crossbar switch is that the number of crossbars grows as
`
`the square of the number of lines into the switch. If we assume that all lines are the square of the number of lines into the switch. If we assume that all lines are
`
`full duplex and that there are no self-connections, only the crosspoints above the full duplex and that there are no self-connections, only the crosspoints above the
`
`diagonal are needed. Still, n(n — 1)/2 crosspoints are needed. For n = 1000, we diagonal are needed. Still, n(n — 1)/2 crosspoints are needed. For n = 1000, we
`
`need 499,500 crosspoints. While building a VLSI chip with this number of need 499,500 crosspoints. While building a VLSI chip with this number of
`
`transistor switches is possible, having 1000 pins on the chip is not. Thus a single transistor switches is possible, having 1000 pins on the chip is not. Thus a single
`
`crossbar switch is only useful for relatively small end offices. crossbar switch is only useful for relatively small end offices.
`
`
`
`Space Division Switches Space Division Switches
`
`
`By splitting the crossbar switch into small chunks and interconnecting them, it By splitting the crossbar switch into small chunks and interconnecting them, it
`
`is possible to build multistage switches with many fewer crosspoints. These are is possible to build multistage switches with many fewer crosspoints. These are
`
`called space division switches. Two configurations are illustrated in Fig. 2-39. called space division switches. Two configurations are illustrated in Fig. 2-39.
`
`To keep our example simple, we will consider only three-stage switches, but To keep our example simple, we will consider only three-stage switches, but
`
`NFLE Ex. 1015 - Page 9
`
`
`
`NFLE 1015 - Page 9
`
`

`

`SEC. 2.4
`SEC. 2.4
`
`
`
`THE TELEPHONE SYSTEM THE TELEPHONE SYSTEM
`
`137
`137
`
`
`
`N= 16,n= 4,k= 2 N= 16,n= 4,k= 2
`
`
`
`N= 16,n= 4,k= 3 N= 16,n= 4,k= 3
`
`—n Crossbars
`—n Crossbars
`
`N
`
`—n Crossbars —n Crossbars
`
`—n Crossbars
`—n Crossbars
`
`
`
`—n Crossbars —n Crossbars
`
`k
`k
`Crossbars
`Crossbars
`
`nxk
`
`nxk
`
`nxk
`
`nxk
`
`N Inputs
`N Inputs
`
`N outputs
`N outputs
`
`N Inputs
`N Inputs
`
`(a)
`(a)
`
`k
`k
`Crossbars
`Crossbars
`N N
`x
`n n
`
`N N
`x—
`n n
`
`N N
`— x—
`n n
`
`
`
`(b) (b)
`
`kxn
`
`kxn
`
`kxn
`
`kxn
`
`N outputs
`N outputs
`
`Fig. 2-39. Two space division switches with different parameters.
`Fig. 2-39. Two space division switches with different parameters.
`
`switches with more stages are also possible. In these examples, we have a total of
`switches with more stages are also possible. In these examples, we have a total of
`
`N inputs and N outputs. Instead of building a single N x N crossbar, we build the N inputs and N outputs. Instead of building a single N x N crossbar, we build the
`
`switch out of smaller rectangular crossbars. In the first stage, each crossbar has n switch out of smaller rectangula