Routing algorithms and switching techniques

《Routing algorithms and switching techniques》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、RoutingalgorithmsandswitchingtechniquesTaxonomyofcommunicationproblemsCommunicationproblemscanbeclassifiedintoseveralclassesaccordingtothenumberofsourceanddestinationnodesandthewayhowthetransferedinformationishandled.One-to-onecommunication:Informationisonlyexchanged(notduplicated)betweenoneorseve

2、ralpairsofnodes.•single-paircommunication:thereisjustoneisolatedcommunicatingpair.Therearenoproblemswithdeadlocks,congestions,andsoon.ThebasicalgorithmsforshortestpathroutinginusualinterconnectionnetworksweredescribedinSection5.Inthissection,wewilldescribebasicswitchingtechniquesfortheseroutingalg

3、orithms.•manyone-to-onecommunications:severalpairsexchangeinformationsimultaneously.Thissectioncoversswitchingtechniquesandflowcontrolmethodsinsuchacase.•permutationrouting:everynodeisasourceofonemessageandadestinationforanothermessageatthesametime.Thiscommunicationpatternimpliesapermutationamongn

4、odes.Sections9and10willdescribealgorithmsforpermutationrouting.One-to-manycommunication:Onenodeisthesenderandseveralorallnodesarereceivers.Ifthesameinformationisdisseminatedinmultiplecopiesamongtheothernodes,thesepatternsareknownasmulticastandone-to-allbroadcastcommunicationoperations.Iftheinforma

5、tionsenttoeachdestinationnodeisdifferent,thepatterniscalledone-to-allscatter.Section11and12aredevotedtothesetwoproblems.All-to-allcommunication:Thiscanbeagainall-to-allbroadcastorscatterandSections13and14willdescribesomealgorithmsforthesepatterns.One-to-manyandall-to-allpatternsarecalledcollective

6、communicationoperations.BacktothebeginningofBacktotheCS838classthepagescheduleBasicconceptsRouterarchitectureprocessingnode:standardbus-basedcomputeraugmentedwitharouter.CAPTION:Genericstructureofaprocessingnoderouter:aHWcoprocessorimplementinglowerlevelsofcommunicationprotocol.Itcomprisesofaswitc

7、h,buffers,androutingandarbitrationunit(seeFigure1).externalchannels:interconnectroutersanddefinethetopologyofaconnecteddirectinterconnectionnetwork.adjacentnodes:nodeswithdirectlyconnectedrouters.internalchannels