Althoughsimpletounderstand,bothSTDMandFDMarelimitedintwoways.First,ifoneoftheflows(hostpairs)
doesnothaveanydatatosend,itsshareofthephysicallink—thatis,itstimequantumoritsfrequency—remainsidle,
evenifoneoftheotherflowshasdatatotransmit.Forexample,S3hadtowaititsturnbehindS1andS2inthe
previousparagraph,evenifS1andS2hadnothingtosend.Forcomputercommunication,theamountoftimethata
linkisidlecanbeverylarge—forexample,considertheamountoftimeyouspendreadingawebpage(leavingthe
linkidle)comparedtothetimeyouspendfetchingthepage.Second,bothSTDMandFDMarelimitedtosituationsin
whichthemaximumnumberofflowsisfixedandknownaheadoftime.Itisnotpracticaltoresizethequantumorto
addadditionalquantainthecaseofSTDMortoaddnewfrequenciesinthecaseofFDM.
Theformofmultiplexingthataddressestheseshortcomings,andofwhichwemakemostuseinthisbook,iscalled
statisticalmultiplexing.Althoughthenameisnotallthathelpfulforunderstandingtheconcept,statisticalmultiplexing
isreallyquitesimple,withtwokeyideas.First,itislikeSTDMinthatthephysicallinkissharedovertime—firstdata
fromoneflowistransmittedoverthephysicallink,thendatafromanotherflowistransmitted,andsoon.Unlike
STDM,however,dataistransmittedfromeachflowondemandratherthanduringapredeterminedtimeslot.Thus,if
onlyoneflowhasdatatosend,itgetstotransmitthatdatawithoutwaitingforitsquantumtocomearoundandthus
withouthavingtowatchthequantaassignedtotheotherflowsgobyunused.Itisthisavoidanceofidletimethat
givespacketswitchingitsefficiency.
Asdefinedsofar,however,statisticalmultiplexinghasnomechanismtoensurethatalltheflowseventuallygettheir
turntotransmitoverthephysicallink.Thatis,onceaflowbeginssendingdata,weneedsomewaytolimitthe
transmission,sothattheotherflowscanhaveaturn.Toaccountforthisneed,statisticalmultiplexingdefinesan
upperboundonthesizeoftheblockofdatathateachflowispermittedtotransmitatagiventime.Thislimited-size
blockofdataistypicallyreferredtoasapacket,todistinguishitfromthearbitrarilylargemessagethatanapplication
programmightwanttotransmit.Becauseapacket-switchednetworklimitsthemaximumsizeofpackets,ahostmay
notbeabletosendacompletemessageinonepacket.Thesourcemayneedtofragmentthemessageintoseveral
packets,withthereceiverreassemblingthepacketsbackintotheoriginalmessage.
Inotherwords,eachflowsendsasequenceofpacketsoverthephysicallink,withadecisionmadeonapacket-by-
packetbasisastowhichflow'spackettosendnext.Noticethat,ifonlyoneflowhasdatatosend,thenitcansenda
sequenceofpacketsback-to-back;however,shouldmorethanoneoftheflowshavedatatosend,thentheirpackets
areinterleavedonthelink.Figure4depictsaswitchmultiplexingpacketsfrommultiplesourcesontoasingleshared
link.
Thedecisionastowhichpackettosendnextonasharedlinkcanbemadeinanumberofdifferentways.For
example,inanetworkconsistingofswitchesinterconnectedbylinkssuchastheoneinFigure4,thedecisionwould
bemadebytheswitchthattransmitspacketsontothesharedlink.(Aswewillseelater,notallpacket-switched
networksactuallyinvolveswitches,andtheymayuseothermechanismstodeterminewhosepacketgoesontothe
linknext.)Eachswitchinapacket-switchednetworkmakesthisdecisionindependently,onapacket-by-packetbasis.
Oneoftheissuesthatfacesanetworkdesignerishowtomakethisdecisioninafairmanner.Forexample,aswitch
couldbedesignedtoservicepacketsonafirst-in,first-out(FIFO)basis.Anotherapproachwouldbetotransmitthe
packetsfromeachofthedifferentflowsthatarecurrentlysendingdatathroughtheswitchinaround-robinmanner.
Thismightbedonetoensurethatcertainflowsreceiveaparticularshareofthelink'sbandwidthorthattheynever
havetheirpacketsdelayedintheswitchformorethanacertainlengthoftime.Anetworkthatattemptstoallocate
bandwidthtoparticularflowsissometimessaidtosupportqualityofservice(QoS).
Also,noticeinFigure4thatsincetheswitchhastomultiplexthreeincomingpacketstreamsontooneoutgoinglink,it
ispossiblethattheswitchwillreceivepacketsfasterthanthesharedlinkcanaccommodate.Inthiscase,theswitchis
forcedtobufferthesepacketsinitsmemory.Shouldaswitchreceivepacketsfasterthanitcansendthemforan
extendedperiodoftime,thentheswitchwilleventuallyrunoutofbufferspace,andsomepacketswillhavetobe
dropped.Whenaswitchisoperatinginthisstate,itissaidtobecongested.
KeyTakeaway