CHAPTER 8 Switching A network is a set of connected devices.Whenever we have multiple devices,we have the problem of how to connect them to make one-to-one communication possible.One solution is to make a point-to-point connection between each pair of devices (a mesh topology)or between a central device and every other device (a star topology).These methods,however,are impractical and wasteful when applied to very large networks. The number and length of the links require too much infrastructure to be cost-efficient, and the majority of those links would be idle most of the time.Other topologies employing multipoint connections,such as a bus,are ruled out because the distances between devices and the total number of devices increase beyond the capacities of the media and equipment. A better solution is switching.A switched network consists of a series ofinterlinked nodes,called switches.Switches are devices capable of creating temporary connections between two or more devices linked to the switch.In a switched network,some of these nodes are connected to the end systems(computers or telephones,for example).Others are used only for routing.Figure 8.1 shows a switched network. Figure 8.1 Switched network B A The end systems (communicating devices)are labeled A,B,C,D,and so on,and the switches are labeled I,II,III,IV,and V.Each switch is connected to multiple links. 213
! ! "#$%$ &! !%'$"! !""(( ""# %'$ ) $#"%((% ' !% *"! %$+,-' $ ,! *%$+,- ! "! &! &"% $ #$!%%$ ,$+ !#"' $+!!$.#"# !# #' ( & !"/,!$#$ ' $"!" )!%$+ "%$,+"#$% &# !'#&#$ #' #! ' !$#"' ', ! % ! " .#%" '$# !+ ! $ & $$ ! 0 ! %'$ +"%, '" $ ! ! 1 ! &"! ! ,"* "%#$%!&2"%$- )! # $,#+ 3+# 4! ! 3+# 4 56789:;<=;86>?@ ! ,"* ""# + -$'$ &A&&B& & ! !$'$ 1&11&111&1C& C ! ! "#$%$$ D4E
214 CHAPTER 8 SWITCHING Traditionally,three methods of switching have been important:circuit switching, packet switching,and message switching.The first two are commonly used today.The third has been phased out in general communications but still has networking applications. We can then divide today's networks into three broad categories:circuit-switched networks, packet-switched networks,and message-switched.Packet-switched networks can funher be divided into two subcategories-virtual-circuit networks and datagram networks- as shown in Figure 8.2. Figure 8.2 Taxonomy ofswitched networks Switched networks Circuit-switched Packet-switched Message-switched networks networks networks Datagram Virtual-circuit networks networks We can say that the virtual-circuit networks have some common characteristics with circuit-switched and datagram networks.Thus,we first discuss circuit-switched networks,then datagram networks,and finally virtual-circuit networks. Today the tendency in packet switching is to combine datagram networks and virtual- circuit networks.Networks route the first packet based on the datagram addressing idea, but then create a virtual-circuit network for the rest of the packets coming from the same source and going to the same destination.We will see some of these networks in future chapters. In message switching,each switch stores the whole message and forwards it to the next switch.Although,we don't see message switching at lower layers,it is still used in some applications like electronic mail (e-mail).We will not discuss this topic in this book. 8.1 CIRCUIT-SWITCHED NETWORKS A circuit-switched network consists of a set of switches connected by physical links. A connection between two stations is a dedicated path made ofone or more links.How- ever,each connection uses only one dedicated channel on each link.Each link is nor- mally divided into n channels by using FDM or TDM as discussed in Chapter 6. A circuit-switched network is made ofa set of switches connected by physical links, in which each link is divided into n channels. Figure 8.3 shows a trivial circuit-switched network with four switches and four links.Each link is divided into n(n is 3 in the figure)channels by using FDM or TDM
!" # $ % &'""( !" # &") !" # # !" #* ! " ( * % & (# " (" %( !)#&&" * + " $ , !) %" # '""(- !" !) &") - !" !) # - !" *.") - !" !) " ( % $ ! (%" # -$(-""( !) # !) - !/#( *0* /#( *0 12343563789:;<=>?4>;93@A8 + " $(-""( !) $ " " " " ! ""(- !" # !) * ( ! "( ""(- !" !) # !) $(-""( !) * "&") !" # " % # !) $(- ""( !) *B !) ( &") % # # %( " $(-""( !) &") " # (" ## *+ ! !) (( " & * C # !" # " !" ! # ! D !" *E (# ! , # !" #! ( &&" ) "" F - G*+ ! "( &" %)* HIJ KLMKNLOPQRLOKSTUVTORWMXQ E""(- !" !)" !" " " %& ") * E" "% ! ! " & ) *Y!- $ " " "( " " " )*Z" ) - $ 4" %( #/[\ [\ "( ] & ^* E""(- !" !) !" " " %& ") ! " " ) $ 4" * /#( *_ ! $""(- !" !)! ( !" ( ) *Z" ) $ `a` _ #( G" %( #/[\ [\*
SECTION 8.1 CIRCUIT-SWITCHED NETWORKS 215 Figure 8.3 A trivial circuit-switched network One link,n channels Path →M We have explicitly shown the multiplexing symbols to emphasize the division of the link into channels even though multiplexing can be implicitly included in the switch fabric. The end systems,such as computers or telephones,are directly connected to a switch.We have shown only two end systems for simplicity.When end system A needs to communicate with end system M,system A needs to request a connection to M that must be accepted by all switches as well as by M itself.This is called the setup phase; a circuit (channel)is reserved on each link,and the combination of circuits or channels defines the dedicated path.After the dedicated path made ofconnected circuits(channels) is established,data transfer can take place.After all data have been transferred,the circuits are tom down. We need to emphasize several points here: D Circuit switching takes place at the physical layer. D Before starting communication,the stations must make a reservation for the resources to be used during the communication.These resources,such as channels (bandwidth in FDM and time slots in TDM),switch buffers,switch processing time,and switch input/output ports,must remain dedicated during the entire duration of data transfer until the teardown phase. D Data transferred between the two stations are not packetized(physical layer transfer of the signal).The data are a continuous flow sent by the source station and received by the destination station,although there may be periods of silence. D There is no addressing involved during data transfer.The switches route the data based on their occupied band(FDM)or time slot(TDM).Of course,there is end-to- end addressing used during the setup phase,as we will see shortly. In circuit switching,the resources need to be reserved during the setup phase; the resources remain dedicated for the entire duration of data transfer until the teardown phase
!"# #$ %& #'()*( &+ , -./.01 234../5 6473 8349:;/27/<53=>.73?/7;/:.5<?@=/57=?;345A73B95=.=C73 /.0.7=234../59.73=3?/7;/:.24.@?;/27/<.2/BB.735>723 C4@2 D3.B5<57?51523452=?;75=7/;3=.514B27/<2=..27B7=4 5>723 834953=>.=./<7>=.B5<57?5C=5?;/27< 83..B5<57?E.B5 7=2=??.247>73.B5<57?F15<57?E.B57=G5742=..27=.7=F 7347 ?57@422;7B@<4//5>723545>//45@<F 75/C D35524//B7357;;345H 4227I234../J559B=.423/.014.B732=?@.47=.=C2275=234../5 BC.573BB247B;473 EC773BB247B;473?4B=C2=..27B2275I234../5J 5574@/53B1B47474.5C24.740;/42 EC74//B474349@.74.5CB173 227547=?B=>. 8.B7=?;345A594/;=.753K L M275>723.7405;/424773;3<524//4< N OC=5747.2=??.247=.1735747=.5?57?4045947=.C=735=25 7=@5BB.732=??.247=. D355=25152345234../5I@4.B>B73 .LF 4.B7?5/=75.DLFJ15>723@CC515>723;=255.7?14.B5>723 .;7P=7;7;=751?57?4.BB247BB.73.7B47=.=CB47474.5C .7/7374B=>.;345 N L47474.5CB@7>.737>=5747=.54.=7;4207ABI;3<524//4<74.5C =C735.4/J D3B474442=.7.=5C/=>5.7@<735=25747=.4.B29B @<73B57.47=.5747=.14/73=373?4<@;=B5=C5/.2 L D35.=4BB55..9=/9BB.B47474.5C D35>7235=773B474 @45B=.73=22;B@4.BILFJ=7?5/=7IDLFJ -C2=51735.BQ7=Q .B4BB55.5BB.7357;;345145>>//553=7/< R.2275>723.1735=25.B7=@59BB.7357;;345H 735=25?4.BB247BC=73.7B47=. =CB47474.5C.7/7374B=>.;345
216 CHAPTER 8 SWITCHING Example 8.1 As a trivial example,let us use a circuit-switched network to connect eight telephones in a small area.Communication is through 4-kHz voice channels.We assume that each link uses FDM to connect a maximum of two voice channels.The bandwidth ofeach link is then 8 kHz.Figure 8.4 shows the situation.Telephone 1 is connected to telephone 7;2 to 5;3 to 8;and 4 to 6.Of course the situation may change when new connections are made.The switch controls the connections. Figure 8.4 Circuit-switched network used in Example 8.1 Circuit-switched network ® 04 6 2® kHz kHz 3③ 4③ 魔金 8 kHz kHz 0 4 kHz kHz 0 -G8 kHz kHz Example 8.2 As another example.consider a circuit-switched network that connects computers in two remote offices of a private company.The offices are connected using a T-l line leased from a communi- cation service provider.There are two 4 X 8(4 inputs and 8 outputs)switches in this network.For each switch,four output ports are folded into the input ports to allow communication between computers in the same office.Four other output ports allow communication between the two offices.Figure 8.5 shows the situation. Figure 8.5 Circuit-switched network used in Example 8.2 Circuit-switched network 4x8 4x8 swltch T-I line with switch 1.544 Mbps
!"# $%!"&!" ''" ( (' )* (+",-" *. / .(.--"( " 0+ "!"%+.-" - $ !! " 12.$$'- ( .- + .'0+3)/45 . ("(+ --"!16" '$" + " (+! -/'"789 . (.--"( $ # $'$.: *. . ("(+ --"!1;+"< -,* , +.:" (+! -/ +"- /4517 0' " 13 +.* +" ' .-1;"!"%+.-"= (.--"( ", . "!"%+.-">?@ .ABC . ? -,3 .D1E:(.' " +" ' .-$ F(+ -0"*+"--"*(.--"( .- "$ ,"1;+"* (+(.- .! +"(.--"( .-1 GHIJKLMNO PQRSPTUVWPTRXYZTW[Q\SVYPZ 2 (' )* (+",-" *. / ] -. +" "# $%!"&(.- ," ( (' )* (+",-" *. / + (.--"( (.$%' " - *. "$. " .:: (".: % "(.$% -F1;+".:: (" "(.--"( ",' -0 ;)!! -"!" ",: .$ (.$$'- ) ( .-" ("% . ," 1;+" " " *.3^ _3 -%' -, .' %' `* (+" - + -" *. /17. " (+* (+&:.' .' %' %. ":.!,", - . +" -%' %. . !!.*(.$$'- ( .-<" *""- (.$%' " - +" $".:: ("17.' . +" .' %' %. !!.*(.$$'- ( .-<" *""- +" *. .:: ("17 0' " 1a+.* +" ' .-1 GHIJKLMNb PQRSPTUVWPTRXYZTW[Q\SVY - ] 2 (' )* (+",-" *. / 3# *c (+ ;)!! -"* + =1a339<% 3# * (+
SECTION 8.1 CIRCUIT-SWITCHED NEIWORKS 217 Three Phases The actual communication in a circuit-switched network requires three phases:connec- tion setup,data transfer,and connection teardown. Setup Phase Before the two parties (or multiple parties in a conference call)can communicate,a dedicated circuit (combination of channels in links)needs to be established.The end sys- tems are normally connected through dedicated lines to the switches,so connection setup means creating dedicated channels between the switches.For example,in Figure 8.3, when system A needs to connect to system M,it sends a setup request that includes the address of system M,to switch I.Switch I finds a channel between itself and switch IV that can be dedicated for this purpose.Switch I then sends the request to switch IV, which finds a dedicated channel between itself and switch III.Switch III informs sys- tem M of system A's intention at this time. In the next step to making a connection,an acknowledgment from system M needs to be sent in the opposite direction to system A.Only after system A receives this acknowledgment is the connection established. Note that end-to-end addressing is required for creating a connection between the two end systems.These can be,for example,the addresses of the computers assigned by the administrator in a TDM network,or telephone numbers in an FDM network. Data Transfer Phase After the establishment ofthe dedicated circuit(channels),the two parties can transfer data. Teardown Phase When one of the parties needs to disconnect,a signal is sent to each switch to release the resources. Efficiency It can be argued that circuit-switched networks are not as efficient as the other two types of networks because resources are allocated during the entire duration ofthe con- nection.These resources are unavailable to other connections.In a telephone network, people normally terminate the communication when they have finished their conversation. However,in computer networks,a computer can be connected to another computer even ifthere is no activity for a long time.In this case,allowing resources to be dedicated means that other connections are deprived. Delay Although a circuit-switched network normally has low efficiency,the delay in this type ofnetwork is minimal.During data transfer the data are not delayed at each switch;the resources are allocated for the duration of the connection.Figure 8.6 shows the idea of delay in a circuit-switched network when only two switches are involved. As Figure 8.6 shows,there is no waiting time at each switch.The total delay is due to the time needed to create the connection,transfer data,and disconnect the circuit.The
!! "# # "#" # # $%# &" % '( # )* "" $ # " )+& ",+"& "" # " & %" -./01234- 5, % ) #6 ! #) ) ##" "," 7 " !! "# + &&# & # # 6 !8#" # " , "" #" #"'7"& 8 8 #& "&9$ !" ! 9 "" & :&&# & #" %# + "" # " ) !" #":&&# & "" 8 %" %# ; <!) +#";#: =+ %"9 !>"& "" 9 !?+# "& )( #" & && ,9 !?+ %# @ A%# @,#"& "" 8 %"# ,"&%# @B "8&&# &, #) ) A%# @ ""& ( %# @B+ %# ,#"&&&# & "" 8 %"# ,"&%# @@@ A%# @@@#", !9$ !? ,9 !>C#" " # " # #! @" "< ) !'#": "" # "+" '" % &:!" , !9 !?"& 8" #" )) # &# # " 9 !> D" 9, 9 !> #E # '" % &:!" # "" # " 8 #& F "&$ $"&&&#":#( #&, #": "" # "8 %" % "&9 ! "8+, <!) + && , !) #:"& 89 &!#"# #"G? " % '+ ) "" !8#"";G? " % ' 3.3H3I4J-H1234- >, 8 #!" , &&# & # # 6 "" 7+ % ) # " ",& -3HKLMI1234- N" " , ) #"& &# "" +#:" #" %# O,,# #" 9 @ "8: & # # $%# &" % '" ,,# #" % 9) ," % '8 && #": " #& # " , "$ " # " "E# 8 "" # " @" ) "" % '+ ) ) " ! 9 !#" !! "# # "%" 9E,#"#& # "E # " P %E+#" !) " % '+ !) "8 "" & " !) E"#, #" #E# 9, ": #! @" # + %#": 8&&# & !" "" # "&)#E& G 9 > : # # $%# &" % '" ! 9 %,,# #" 9+ & 9#" # 9) ," % '#!#"#! G #":& ", & " & 9& %# Q &, & # " , "" # " ;#: R % #& , & 9#" # # $%# &" % '%" " 9 % %# #"E E& >;#: R %+ #" %# #": #! %# & 9#& #!"&& "" # "+ ",& +"&&# "" # #