会员注册 | 登录 | 微信快捷登录 支付宝快捷登录 QQ登录 微博登录 | 帮助中心 人人文库renrendoc.com美如初恋!
站内搜索 百度文库

热门搜索: 直缝焊接机 矿井提升机 循环球式转向器图纸 机器人手爪发展史 管道机器人dwg 动平衡试验台设计

   首页 人人文库网 > 资源分类 > PDF文档下载

40-Ethernet - distributed packet switching for local computer networks.pdf

  • 资源星级:
  • 资源大小:1.05MB   全文页数:10页
  • 资源格式: PDF        下载权限:注册会员/VIP会员
您还没有登陆,请先登录。登陆后即可下载此文档。
  合作网站登录: 微信快捷登录 支付宝快捷登录   QQ登录   微博登录
友情提示
2:本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3:本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

40-Ethernet - distributed packet switching for local computer networks.pdf

ComputerSystemsG.Bell,S.FullerandD.Siewiorek,EditorsEthernetDistributedPacketSwitchingforLocalComputerNetworksRobertM.MetcalfeandDavidR.BoggsXeroxPaloAltoResearchCenterEthernetisabranchingbroadcastcommunicationsystemforcarryingdigitaldatapacketsamonglocallydistributedcomputingstations.ThepackettransportmechanismprovidedbyEthernethasbeenusedtobuildsystemswhichcanbeviewedaseitherlocalcomputernetworksorlooselycoupledmultiprocessors.AnEthernetssharedcommunicationfacility,itsEther,isapassivebroadcastmediumwithnocentralcontrol.CoordinationofaccesstotheEtherforpacketbroadcastsisdistributedamongthecontendingtransmittingstationsusingcontrolledstatisticalarbitration.SwitchingofpacketstotheirdestinationsontheEtherisdistributedamongthereceivingstationsusingpacketaddressrecognition.Designprinciplesandimplementationaredescribed,basedonexperiencewithanoperatingEthernetof100nodesalongakilometerofcoaxialcable.Amodelforestimatingperformanceunderheavyloadsandapacketprotocolforerrorcontrolledcommunicationareincludedforcompleteness.KeyWordsandPhrasescomputernetworks,packetswitching,multiprocessing,distributedcontrol,distributedcomputing,broadcastcommunication,statisticalarbitrationCRCategories3.81,4.32,6.35Copyright©1976,AssociationforComputingMachinery,Inc.Generalpermissiontorepublish,butnotforprofit,allorpartofthismaterialisgrantedprovidedthatACMscopyrightnoticeisgivenandthatreferenceismadetothepublication,toitsdateofissue,andtothefactthatreprintingprivilegesweregrantedbypermissionoftheAssociationforComputingMachinery.AuthorspresentaddressesR.M.Metcalfe,TransactionTechnology,Inc.,10880WilshireBoulevard,LosAngeles,CA94304D.Boggs,XeroxPaloAltoResearchCenter,3333CoyoteHillRoad,PaloAlto,CA94304.3951.BackgroundOnecancharacterizedistributedcomputingasaspectrumofactivitiesvaryingintheirdegreeofdecentralization,withoneextremebeingremotecomputernetworkingandtheotherextremebeingmultiprocessing.Remotecomputernetworkingisthelooseinterconnectionofpreviouslyisolated,widelyseparated,andratherlargecomputingsystems.Multiprocessingistheconstructionofpreviouslymonolithicandserialcomputingsystemsfromincreasinglynumerousandsmallerpiecescomputinginparallel.Nearthemiddleofthisspectrumislocalnetworking,theinterconnectionofcomputerstogaintheresourcesharingofcomputernetworkingandtheparallelismofmultiprocessing.Theseparationbetweencomputersandtheassociatedbitrateoftheircommunicationcanbeusedtodividethedistributedcomputingspectrumintobroadactivities.Theproductofseparationandbitrate,nowabout1gigabitmeterpersecond1Gbmps,isanindicationofthelimitofcurrentcommunicationtechnologyandcanbeexpectedtoincreasewithtimeActivitySeparationBitrateRemotenetworks10km10Mbps1.1RemoteComputerNetworkingComputernetworkingevolvedfromtelecommunicationsterminalcomputercommunication,wheretheobjectwastoconnectremoteterminalstoacentralcomputingfacility.Astheneedforcomputercomputerinterconnectiongrew,computersthemselveswereusedtoprovidecommunication2,4,29.Communicationusingcomputersaspacketswitches1521,26andcommunicationsamongcomputersforresourcesharingI0,32werebothadvancedbythedevelopmentoftheArpaComputerNetwork.TheAlohaNetworkattheUniversityofHawaiiwasoriginallydevelopedtoapplypacketradiotechniquesforcommunicationbetweenacentralcomputeranditsterminalsscatteredamongtheHawaiianIslands1,2.ManyoftheterminalsarenowminicomputerscommunicatingamongthemselvesusingtheAlohaNetworksMenehuneasapacketswitch.TheMenehuneandanArpanetImparenowconnected,providingterminalsontheAlohaNetworkaccesstocomputingresourcesontheU.S.mainland.Justascomputernetworkshavegrownacrosscontinentsandoceanstointerconnectmajorcomputingfacilitiesaroundtheworld,theyarenowgrowingdowncorridorsandbetweenbuildingstointerconnectminicomputersinofficesandlaboratories3,12,13,14,35.1.2MultiprocessingMultiprocessingfirsttooktheformofconnectinganI/OcontrollertoalargecentralcomputerraMsAspisaCommuaicationsJuly1976ofVolume19theACMNumber7classicexample\29\.Next,multiplecentralprocessorswereconnectedtoacommonmemorytoprovidemorepowerforcomputeboundapplications\33\.Forcertainoftheseapplications,moreexoticmultiprocessorarchitecturessuchasIlliaeIVwereintroduced\5\.Morerecentlyminicomputershavebeenconnectedinmultiprocessorconfigurationsforeconomy,reliability,andincreasedsystemmodularity\24,36\.Thetrendhasbeentowarddecentralizationforreliabilitylooselycoupledmultiprocessorsystemsdependlessonsharedcentralmemoryandmoreonthinwiresforinterprocesscommunicationwithincreasedcomponentisolation\18,26\.Withthecontinuedthinningofinterprocessorcommunicationforreliabilityandthedevelopmentofdistributableapplications,multiprocessingisgraduallyapproachingalocalformofdistributedcomputing.1.3LocalComputerNetworkingEthernetsharesmanyobjectiveswithotherlocalnetworkssuchasMitresMitrix,BellTelephoneLaboratorysSpider,andU.C.IrvinesDistributedComputingSystemDCS\12,13,14,35\.Prototypesofallfourlocalnetworkingschemesoperateatbitratesbetweenoneandthreemegabitspersecond.MitrixandSpiderhaveacentralminicomputerforswitchingandbandwidthallocation,whileDCSandEthernetusedistributedcontrol.SpiderandDCSusearingcommunicationpath,MitrixusesofftheshelfCATVtechnologytoimplementtwoonewaybusses,andourexperimentalEthernetusesabranchingtwowaypassivebus.Differencesamongthesesystemsareduetodifferencesamongtheirintendedapplications,differencesamongthecostconstraintsunderwhichtradeoffsweremade,anddifferencesofopinionamongresearchers.BeforegoingintoadetaileddescriptionofEthernet,weofferthefollowingoverviewseeFigure1.2.SystemSummaryEthernetisasystemforlocalcommunicationamongcomputingstations.OurexperimentalEthernetusestappedcoaxialcablestocarryvariablelengthdigitaldatapacketsamong,forexample,personalminicomputers,printingfacilities,largefilestoragedevices,magnetictapebackupstations,largercentralcomputers,andlongerhaulcommunicationequipment.Thesharedcommunicationfacility,abranchingEther,ispassive.AstationsEthernetinterfaceconnectsbitseriallythroughaninterfacecabletoatransceiverwhichinturntapsintothepassingEther.ApacketisbroadcastontotheEther,isheardbyallstations,andiscopiedfromtheEtherbydestinationswhichselectitaccordingtothepacketsleadingaddressbits.Thisisbroadcastpacketswitchingandshouldbedistinguishedfromstoreandforwardpacketswitching,inwhichroutingisperformedbyintermediateprocessingelements.Tohandlethedemandsofgrowth,anEthernetcanbeextendedusingpacketrepeatersforsignalregeneration,packetfiltersfortrafficlocalization,andpacketgatewaysforinternetworkaddressextension.Controliscompletelydistributedamongstations,withpackettransmissionscoordinatedthroughstatisticalarbitration.Transmissionsinitiatedbyastationdefertoanywhichmayalreadybeinprogress.Oncestarted,ifinterferencewithotherpacketsisdetected,atransmissionisabortedandrescheduledbyitssourcestation.Afteracertainperiodofinterferencefreetransmission,apacketisheardbyallstationsandwillruntocompletionwithoutinterference.Ethernetcontrollersincollidingstationseachgeneraterandomretransmissionintervalstoavoidrepeatedcollisions.ThemeanofapacketsretransmissionintervalsisadjustedasafunctionofcollisionhistorytokeepEtherutilizationneartheoptimumwithchangingnetworkload.Evenwhentransmittedwithoutsourcedetectedinterference,apacketmaystillnotreachitsdestinationwithouterrorthus,packetsaredeliveredonlywithhighprobability.StationsrequiringaresidualerrorratelowerthanthatprovidedbythebareEthernetpackettransportmechanismmustfollowmutuallyagreeduponpacketprotocols.3.DesignPrinciplesOurobjectistodesignacommunicationsystemwhichcangrowsmoothlytoaccommodateseveralbuildingsfullofpersonalcomputersandthefacilitiesneededfortheirsupport.Likethecomputingstationstobeconnected,thecommunicationsystemmustbeinexpensive.Wechoosetodistributecontrolofthecommunicationsfacilityamongthecommunicatingcomputerstoeliminatethereliabilityproblemsofanactivecentralcontroller,toavoidcreatingabottleneckinasystemrichinparallelism,andtoreducethefixedcostswhichmakesmallsystemsuneconomical.EthernetdesignstartedwiththebasicideaofpacketcollisionandretransmissiondevelopedintheAlohaNetwork\1\.Weexpectedthat,liketheAlohaNetwork,EthernetswouldcarryburstytrafficsothatconventionalsynchronoustimedivisionmultiplexingSTDMwouldbeinefficient\1,2,21,26\.WesawpromiseintheAlohaapproachtodistributedcontrolofradiochannelmultiplexingandhopedthatitcouldbeappliedeffectivelywithmediasuitedtolocalcomputercommunication.Withseveralinnovationsofourown,thepromiseisrealized.Ethernetisnamedforthehistoricalluminiferousetherthroughwhichelectromagneticradiationswereonceallegedtopropagate.LikeanAloharadiotransmitter,anEthernettransmitterbroadcastscompletelyaddressedtransmittersynchronousbitsequencescalledpacketsontotheEtherandhopesthattheyareheardby396CommunicationsJuly1976ofVolume19theACMNumber7Fig.1.AtwosegmentEthernet.TERMINATORTRANSINTERFACETAPCABLEETIIERENTlIlclIONNTTERSTATIONROFLALCEERI0NNTTERSTATIONR0FLALCEERSTATIONCONTROLLERwIINTERFACEETHERSEGMENT2mmtheintendedreceivers.TheEtherisalogicallypassivemediumforthepropagationofdigitalsignalsandcanbeconstructedusing.anynumberofmediaincludingcoaxialcables,twistedpairs,andopticalfibers.3.1TopologyWecannotaffordtheredundantconnectionsanddynamicroutingofstoreandforwardpacketswitchingtoassurereliablecommunication,sowechoosetoachievereliabilitythroughsimplicity.Wechoosetomakethesharedcommunicationfacilitypassivesothatthefailureofanactiveelementwilltendtoaffectthecommunicationsofonlyasinglestation.Thelayoutandchangingneedsofofficeandlaboratorybuildingsleadsustopickanetworktopologywiththepotentialforconvenientincrementalextentionandreconfigurationwithminimalservicedisruption.ThetopologyoftheEthernetisthatofanunrootedtree.ItisatreesothattheEthercanbranchattheentrancetoabuildingscorridor,yetavoidmultipathinterference.TheremustbeonlyonepaththroughtheEtherbetweenanysourceanddestinationifmorethanonepathweretoexist,atransmissionwouldinterferewithitself,repeatedlyarrivingatitsintendeddestinationhavingtravelledbypathsofdifferentlength.TheEtherisunrootedbecauseitcanbeextendedfromanyofitspointsinanydirection.Anystationwishingtojoin397anEthernettapsintotheEtheratthenearestconvenientpoint.Lookingattherelationshipofinterconnectionandcontrol,weseethatEthernetisthedualofastarnetwork.Ratherthandistributedinterconnectionthroughmanyseparatelinksandcentralcontrolinaswitchingnode,asinastarnetwork,theEthernethascentralinterconnectionthroughtheEtheranddistributedcontrolamongitsstations.UnlikeanAlohaNetwork,whichisastarnetworkwithanoutgoingbroadcastchannelandanincomingmultiaccesschannel,anEthernetsupportsmanytomanycommunicationwithasinglebroadcastmultiaccesschannel.3.2ControlSharingoftheEtheriscontrolledinsuchawaythatitisnotonlypossiblebutprobablethattwoormorestationswillattempttotransmitapacketatroughlythesametime.PacketswhichoverlapintimeontheEtheraresaidtocollidetheyinterferesoastobeunrecognizablebyareceiver.Astationrecoversfromadetectedcollisionbyabandoningtheattemptandretransmittingthepacketaftersomedynamicallychosenrandomtimeperiod.Arbitrationofconflictingtransmissiondemandsisbothdistributedandstatistical.WhentheEtherislargelyunused,astationtransmitsitspacketsatwill,thepacketsarereceivedwithouterror,andalliswell.Asmorestationsbegintotransmit,therateofpacketinterferenceincreases.EthernetcontrollersineachstationarebuilttoadjustthemeanretransmissionintervalinproportiontothefrequencyofcollisonssharingoftheEtheramongcompetingstationstationtransmissionsistherebykeptneartheoptimum\20,21\.AdegreeofcooperationamongthestationsisrequiredtosharetheEtherequitably.Indemandingapplicationscertainstationsmightusefullytaketransmissionprioritythroughsomesystematicviolationofequityrules.AstationcouldusurptheEtherbynotadjustingitsretransmissionintervalwithincreasingtrafficorbysendingverylargepackets.Bothpracticesarenowprohibitedbylowlevelsoftwareineachstation.3.3AddressingEachpackethasasourceanddestination,bothofwhichareidentifiedinthepacketsheader.ApacketplacedontheEthereventuallypropagatestoallstations.AnystationcancopyapacketfromtheEtherintoitslocalmemory,butnormallyonlyanactivedestinationstationmatchingitsaddressinthepacketsheaderwilldosoasthepacketpasses.Byconvention,azerodestinationaddressisawildcardandmatchesalladdressesapacketwithadestinationofzeroiscalledabroadcastpacket.3.4ReliabilityAnEthernetisprobabilistic.Packetsmaybelostduetointerferencewithotherpackets,impulsenoiseontheCommunicationsJuly1976ofVolume19ethACMNumber7Ether,aninactivereceiveratapacketsintendeddestination,orpurposefuldiscard.ProtocolsusedtocommunicatethroughanEthernetmustassumethatpacketswillbereceivedcorrectlyatintendeddestinationsonlywithhighprobability.AnEthernetgivesitsbesteffortstotransmitpacketssuccessfully,butitistheresponsibilityofprocessesinthesourceanddestinationstationstotaketheprecautionsnecessarytoassurereliablecommunicationofthequalitytheythemselvesdesire\18,21\.Recognizingthecostlinessanddangersofpromisingerrorfreecommunication,werefrainfromguaranteeingreliabledeliveryofanysinglepackettogetbotheconomyoftransmissionandhighreliabilityaveragedovermanypackets\21\.Removingtheresponsibilityforreliablecommunicationfromthepackettransportmechanismallowsustotailorreliabilitytotheapplicationandtoplaceerrorrecoverywhereitwilldothemostgood.ThispolicybecomesmoreimportantasEthernetsareinterconnectedinahierarchyofnetworksthroughwhichpacketsmusttravelfartherandsuffergreaterrisks.3.5MechanismsAstationconnectstotheEtherwithatapandatransceiver.AtapisadeviceforphysicallyconnectingtotheEtherwhiledisturbingitstransmissioncharacteristicsaslittleaspossible.Thedesignofthetransceivermustbeanexerciseinparanoia.PrecautionsmustbetakentoinsurethatlikelyfailuresinthetransceiverorstationdonotresultinpollutionoftheEther.Inparticular,removingpowerfromthetransceivershouldcauseittodisconnectfromtheEther.FivemechanismsareprovidedinourexperimentalEthernetforreducingtheprobabilityandcostoflosingapacket.Theseare1carrierdetection,2interferencedetection,3packeterrordetection,4truncatedpacketfiltering,and5collisionconsensusenforcement.3.5.1Carrierdetection.AsapackersbitsareplacedontheEtherbyastation,theyarephaseencodedlikebitsonamagnetictape,whichguaranteesthatthereisatleastonetransitionontheEtherduringeachbittime.ThepassingofapacketontheEthercanthereforebedetectedbylisteningforitstransitions.Tousearadioanalogy,wespeakofthepresenceofcarrierasapacketpassesatransceiver.Becauseastationcansensethecarrierofapassingpacket,itcandelaysendingoneofitsownuntilthedetectedpacketpassessafely.TheAlohaNetworkdoesnothavecarrierdetectionandconsequentlysuffersasubstantiallyhighercollisionrate.Withoutcarrierdetection,efficientuseoftheEtherwoulddecreasewithincreasingpacketlength.InSection6below,weshowthatwithcarrierdetection,Etherefficiencyincreaseswithincreasingpacketlength.Withcarrierdetectionweareabletoimplementdeferencenostationwillstarttransmittingwhilehearingcarrier.WithdeferencecomesacquisitiononceapackettransmissionhasbeeninprogressforanEtherendtoendpropagationtime,allstationsarehearingcarrierandaredeferringtheEtherhasbeenacquiredandthetransmissionwillcompletewithoutaninterferingcollision.Withcarrierdetection,collisionsshouldoccuronlywhentwoormorestationsfindtheEthersilentandbegintransmittingsimultaneouslywithinanEtherendtoendpropagationtime.Thiswillalmostalwayshappenimmediatelyafterapackettransmissionduringwhichtwoormorestationsweredeferring.Becausestationsdonotnowrandomizeafterdeferring,whenthetransmissionterminates,thewaitingstationspileontogether,collide,randomize,andretransmit.3.5.2Interferencedetection.Eachtransceiverhasaninterferencedetector.InterferenceisindicatedwhenthetransceivernoticesadifferencebetweenthevalueofthebititisreceivingfromtheEtherandthevalueofthebititisattemptingtotransmit.Interferencedetectionhasthreeadvantages.First,astationdetectingacollisionknowsthatitspackethasbeendamaged.Thepacketcanbescheduledforretransmissionimmediately,avoidingalongacknowledgmenttimeout.Second,interferenceperiodsontheEtherarelimitedtoamaximumofoneroundtriptime.CollidingpacketsintheAlohaNetworkruntocompletion,butthetruncatedpacketsresultingfromEthernetcollisionswasteonlyasmallfractionofapackettimeontheEther.Third,thefrequencyofdetectedinterferenceisusedtoestimateEthertrafficforadjustingretransmissionintervalsandoptimizingchannelefficiency.3.5.3Packeterrordetection.AsapacketisplacedontheEther,achecksumiscomputedandappended.AsthepacketisreadfromtheEther,thechecksumisrecomputed.Packetswhichdonotcarryaconsistentchecksumarediscarded.Inthiswaytransmissionerrors,impulsenoiseerrors,anderrorsduetoundetectedinterferencearecaughtatapaeketsdestination.3.5.4Truncatedpacketfiltering.InterferencedetectionanddeferencecausemostcollisionstoresultintruncatedpacketsofonlyafewbitscollidingstationsdetectinterferenceandaborttransmissionwithinanEtherroundtriptime.Toreducetheprocessingloadthattherejectionofsuchobviouslydamagedpacketswouldplaceonlisteningstationsoftware,truncatedpacketsarefilteredoutinhardware.3.5.5Collisionconsensusenforcement.Whenastationdeterminesthatitstransmissionisexperiencinginterference,itmomentarilyjamstheEthertoinsurethatallotherparticipantsinthecollisionwilldetectinterferenceand,becauseofdeference,willbeforcedtoabort.Withoutthiscollisionconsensusenforcementmechanism,itispossiblethatthetransmittingstationwhichwouldotherwisebethelasttodetectacollisionmightnotdosoastheotherinterferingtransmissionssuccessivelyabortandstopinterfering.Althoughthepacketmaylookgoodtothatlasttransmitter,differentpathlengths398CommunicationsJuly1976ofVolume19theACMNumber7betweenthecollidingtransmittersandtheintendedreceiverwillcausethepackettoarrivedamaged.4.ImplementationOurchoicesof1kilometer,3megabitspersecond,and256stationsfortheparametersofanexperimentalEthernetwerebasedoncharacteristicsofthelocallydistributedcomputercommunicationenvironmentandourassessmentsofwhatwouldbemarginallyachievabletheywerecertainlynothardrestrictionsessentialtotheEthernetconcept.Weexpectthatareasonablemaximumnetworksizewouldbeontheorderof1kilometerofcable.WeusedthisworkingnumbertochooseamongEthersofvaryingsignalattenuationandtodesigntransceiverswithappropriatepowerandsensitivity.ThedominantstationonourexperimentalEthernetisaminicomputerforwhich3megabitspersecondisaconvenientdatatransferrate.Bykeepingthepeakratewellbelowthatofthecomputerspathtomainmemory,wereducetheneedforexpensivespecialpurposepacketbufferinginourEthernetinterfaces.Bykeepingthepeakrateashighasisconvenient,weprovideforlargernumbersofstationsandmoreambitiousmultiprocessingcommunicationsapplications.Toexpeditelowlevelpackethandlingamong256stations,weallocatethefirst8bitbyteofthepackettobethedestinationaddressfieldandthesecondbytetobethesourceaddressfieldseeFigure2.256isanumbersmallenoughtoalloweachstationtogetanadequateshareoftheavailablebandwidthandapproachesthelimitofwhatwecanachievewithcurrenttechniquesfortappingcables.256isonlyaconvenientnumberforthelowestlevelofprotocolhigherlevelscanaccomodateextendedaddressspaceswithadditionalfieldsinsidethepacketandsoftwaretointerpretthem.OurexperimentalEthernetimplementationhasfourmajorpartstheEther,transceivers,interfaces,andcontrollersseeFigure1.4.1EtherWechosetoimplementourexperimentalEtherusinglowlosscoaxialcablewithofftheshelfCATVtapsandconnectors.ItispossibletomixEthersonasingleEthernetweuseasmallerdiametercoaxforconvenientconnectionwithinstationdustersandalargerdiametercoaxforlowlossrunsbetweenclusters.ThecostofcoaxialcableEtherisinsignificantrelativetothecostofthedistributedcomputingsystemssupportedbyEthernet.4.2TransceiversOurexperimentaltransceiverscandriveakilometerofcoaxialcableEthertappedby256stationstransmittingat3megabitspersecond.Thetransceiverscanendurei.e.workaftersustaineddirectshorting,im399properterminationoftheEther,andsimultaneousdrivebyall256stationstheycantoleratei.e.workduringgrounddifferentialsandeverydayelectricalnoise,fromtypewritersorelectricdrills,encounteredwhenstationsareseparatedbyasmuchasakilometer.AnEthernettransceiverattachesdirectlytotheEtherwhichpassesbyintheceilingorunderthefloor.Itispoweredandcontrolledthroughfivetwistedpairsinaninterfacecablecarryingtransmitdata,receivedata,interferencedetect,andpowersupplyvoltages.Whenunpowered,thetransceiverdisconnectsitselfelectricallyfromtheEther.Hereiswhereourfightforreliabilityiswonorlostabrokentransceivercan,butshouldnot,bringdownanentireEthernet.AwatchdogtimercircuitineachtransceiverattemptstopreventpollutionoftheEtherbyshuttingdowntheoutputstageifitactssuspiciously.FortransceiversimplicityweusetheEthersbasefrequencyband,butanEthernetcouldbebuilttouseanysuitablysizedbandofafrequencydivisionmultiplexedEther.Eventhoughourexperimentaltransceiversareverysimpleandcantolerateonlylimitedsignalattenuation,theyhaveprovenquiteadequateandreliable.AmoresophisticatedtransceiverdesignmightpermitpassivebranchingoftheEtherandwiderstationseparation.4.3InterfaceAnEthernetinterfaceserializesanddeserializestheparalleldatausedbyitsstation.ThereareanumberofdifferentstationsonourEthernetaninterfacemustbebuiltforeachkind.Eachinterfaceisequippedwiththehardwarenecessarytocomputea16bitcyclicredundancychecksumCRConserialdataasitistransmittedandreceived.ThischecksumprotectsonlyagainsterrorsintheEtherandspecificallynotagainsterrorsintheparallelportionsoftheinterfacehardwareorstation.Higherlevelsoftwarechecksumsarerecommendedforapplicationsinwhichahigherdegreeofreliabilityisrequired.Atransmittinginterfaceusesapacketbufferaddressandwordcounttoserializeandphaseencodeavariablenumberof16bitwordswhicharetakenfromthestationsmemoryandpassedtothetransceiver,precededbyastartbitcalledSYNCinFigure2andfollowedbytheCRC.AreceivinginterfaceusestheappearanceofcarriertodetectthestartofapacketandusestheSYNCbittoacquirebitphase.Aslongascarrierstayson,theinterfacedecodesanddeserializestheincomingbitstreamdepositing16bitwordsinapacketbufferinthestationsmainmemory.Whencarriergoesaway,theinterfacechecksthatanintegralnumberof16bitwordshasbeenreceivedandthattheCRCiscorrect.ThelastwordreceivedisassumedtobetheCRCandisnotcopiedintothepacketbuffer.Theseinterfacesordinarilyincludehardwareforacceptingonlythosepacketswithappropriateaddressesintheirheaders.HardwareaddressfilteringhelpsastationavoidburdensomesoftwarepacketprocessingwhenCommunicationsJuly1976ofVolume19theACMNumber7Fig.2.Ethernetpacketlayout.ACCESSIBLETOSOFIWAREIiYDESTSOURCEADDRESSDATAII8BITS8BITS4OOOBIPSICIIECKSUM\If16BITStheEtherisverybusycarryingtrafficintendedforotherstations.4.4ControllerAnEthernetcontrolleristhestationspecificlowlevelfirmwareorsoftwareforgettingpacketsontoandoutoftheEther.Whenasourcedetectedcollisionoccurs,itisthesourcecontrollersresponsibilitytogenerateanewrandomretransmissionintervalbasedontheupdatedcollisioncount.WehavestudiedanumberofalgorithmsforcontrollingretransmissionratesinstationstomaintainEtherefficiency\20,22\.Themostpracticalofthesealgorithmsestimatetrafficloadusingrecentcollisionhistory.Retransmissionintervalsaremultiplesofaslot,themaximumtimebetweenstartingatransmissionanddetectingacollision,oneendtoendroundtripdelay.AnEthernetcontrollerbeginstransmissionofeachnewpacketwithameanretransmissionintervalofoneslot.Eachtimeatransmissionattemptendsincollision,thecontrollerdelaysforanintervalofrandomlengthwithameantwicethatofthepreviousinterval,deferstoanypassingpacket,andthenattemptsretransmission.ThisheuristicapproximatesanalgorithmwehavecalledBinaryExponentialBackoffseeFigure3\22\.Whenthenetworkisunloadedandcollisionsarerare,themeanseldomdepartsfromoneandretransmissionsareprompt.Asthetrafficloadincreases,morecollisionsareexperienced,abacklogofpacketsbuildsupinthestations,retransmissionintervalsincrease,andretransmissiontrafficbacksofftosustainchannelefficiency.5.GrowththeEtherandextendingitssignalcover,thereisatradeoffbetweenusingsophisticatedtransceiversandusingrepeaters.Withincreasedpowerandsensitivity,transceiversbecomemoreexpensiveandlessreliable.TheintroductionofrepeatersintoanEthernetmakesthecentrallyinterconnectingEtheractive.ThefailureofatransceiverwillseverthecommunicationsofitsownerthefailureofarepeaterpartitionstheEtherseveringmanycommunications.5.2TrafficCoverOnecanexpandanEthernetjustsofarbyaddingEtherandpacketrepeaters.AtsomepointtheEtherwillbesobusythatadditionalstationswilljustdividemorefinelythealreadyinadequatebandwidth.Thetrafficcovercanbeextendedwithanunbufferedtrafficfilteringrepeaterorpacketfilter,whichpassespacketsfromoneEthersegmenttoanotheronlyifthedestinationstationislocatedonthenewsegment.Apacketfilteralsoextendsthesignalcover.5.3AddressCoverOnecanexpandanEthernetjustsofarbyaddingEther,repeaters,andtrafficfilters.AtsomepointtherewillbetoomanystationstobeaddressedwiththeEthernets8bitaddresses.Theaddresscovercanbeextendedwithpacketgatewaysandthesoftwareaddressingconventionstheyimplement\7\.Addressescanbeexpandedintwodirectionsdownintothestationbyaddingfieldstoidentifydestinationportsorprocesseswithinastation,andupintotheinternetworkbyaddingfieldstoidentifydestinationstationsonremotenetworks.Agatewayalsoextendsthetrafficandsignalcovers.TherecanbeonlyonerepeaterorpacketfilterconnectingtwoEthersegmentsapacketrepeatedontoasegmentbymultiplerepeaterswouldinterferewithitself.However,thereisnolimittothenumberofgatewaysconnectingtwosegmentsagatewayonlyrepeatspacketsaddressedtoitselfasanintermediary.Failureofthesinglerepeaterconnectingtwosegmentspartitionsthenetworkfailureofagatewayneednotpartitionthenetittherearepathsthroughothergatewaysbetweenthesegments.5.1SignalCoverOnecanexpandanEthernetjustsofarbyaddingtransceiversandEther.Atsomepoint,thetransceiversandEtherwillbeunabletocarrytherequiredsignals.Thesignalcovercanbeextendedwithasimpleunbufferedpacketrepeater.InourexperimentalEthernet,wherebecauseoftransceiversimplicitytheEthercannotbebranchedpassively,asimplerepeatermayjoinanynumberofEthersegmentstoenrichthetopologywhileextendingthesignalcover.Weoperateanexperimentaltwosegmentpacketrepeater,buthopetoavoidrelyingonthem.Inbranching6.PerformanceWepresenthereasimplesetofformulaswithwhichtocharacterizetheperformanceexpectedofanEthernetwhenitisheavilyloaded.Moreelaborateanalysesandseveraldetailedsimulationshavebeendone,butthefollowingsimplemodelhasprovenveryusefulinunderstandingtheEthernetsdistributedcontentionscheme,evenwhenitisloadedbeyondexpectations\1,20,21,22,23,27\.WedevelopasimplemodeloftheperformanceofaloadedEthernetbyexaminingalternatingEthertimeperiods.Thefirst,calledatransmissioninterval,isthat40OCommunicationsJuly1976ofVolume19theACMNumber7duringwhichtheEtherhasbeenacquiredforasuccessfulpackettransmission.Thesecond,calledacontentioninterval,isthatcomposedoftheretransmissionslotsofSection4.4,duringwhichstationsattempttoacquirecontroloftheEther.BecausethemodelsEthernetsareloadedandbecausestationsdefertopassingpacketsbeforestartingtransmission,theslotsaresynchronizedbythetailoftheprecedingacquisitioninterval.Aslotwillbeemptywhennostationchoosestoattempttransmissioninitanditwillcontainacollisionifmorethanonestationattemptstotransmit.Whenaslotcontainsonlyoneattemptedtransmission,thentheEtherhasbeenacquiredforthedurationofapacket,thecontentionintervalends,andatransmissionintervalbegins.LetPbethenumberofbitsinanEthernetpacket.LetCbethepeakcapacityinbitspersecond,carriedontheEther.LetTbethetimeinsecondsofaslot,thenumberofsecondsittakestodetectacollisionafterstartingatransmission.LetusassumethatthereareQstationscontinuouslyqueuedtotransmitapacketeithertheacquiringstationhasanewpacketimmediatelyafterasuccessfulacquisitionoranotherstationcomesready.NotethatQalsohappenstogivethetotalofferedloadonthenetworkwhichforthisanalysisisalways1orgreater.Weassumethataqueuedstationattemptstotransmitinthecurrentslotwithprobability1/Q,ordelayswithprobability1l/Qthisisknowntobetheoptimumstatisticaldecisionrule,approximatedinEthernetstationsbymeansofourloadestimatingretransmissioncontrolalgorithms\20,21\.6.1AcquisitionProbabilityWenowcomputeA,theprobabilitythatexactlyonestationattemptsatransmissioninaslotandthereforeacquirestheEther.AisQ.1/Q.1l/QQ1thereareQwaysinwhichonestationcanchoosetotransmitwithprobabilityl/QwhileQ1stationschoosetowaitwithprobability1l/Q.Simplifying,A1l/QQl.6.2WaitingTimeWenowcomputeIV,themeannumberofslotsofwaitinginacontentionintervalbeforeasuccessfulacquisitionoftheEtherbyastationstransmission.TheprobabilityofwaitingnotimeatallisjustA,theprobabilitythatoneandonlyonestationchoosestotransmitinthefirstslotfollowingatransmission.Theprobabilityofwaiting1slotisA,1AtheprobabilityofwaitingislotsisA,lAi.ThemeanofthisgeometricdistributioniswlA/A.Fig.3.Collisioncontrolalgorithm.ZEROLOADIESTIMATEFORNEWPACKET.As\LOADESTIMATEYESOVERFLOWEDNOGENERATEIRANDOMNUMBERIINCREASELOADESTIMATECOLLISIONII°AIWEIGHTEDRANDOMNUMBERIERRORI6.3EfficiencyWenowcomputeE,thatfractionoftimetheEtheriscarryinggoodpackets,theefficiency.TheEtherstimeisdividedbetweentransmissionintervalsandcontentionintervals.ApackettransmissiontakesP/Cseconds.ThemeantimetoacquisitionisW,T.Therefore,byoursimplemodel,EP/C/P/CqW,T.TableIpresentsrepresentativeperformancefiguresi.e.EforourexperimentalEthernetwiththeindicatedpacketsizesandnumberofcontinuouslyqueuedstations.Theefficiencyfiguresgivendonotaccountforinevitablereductionsduetoheadersandcontrolpacketsnorforlossesduetoimprecisecontroloftheretransmissionparameter1/Qtheformerisstraightforwardlyprotocoldependentandthelatterrequiresanalysisbeyondthescopeofthispaper.Again,wefeelthatalloftheEthernetsinthetableareoverloadednormallyloadedEthernetswillusuallyhaveaQmuchlessthan1andexhibitbehaviornotcoveredbythismodel.ForourcalculationsweuseaCof3megabitspersecondandaTof16microseconds.TheslotdurationTmustbelongenoughtoallowacollisiontobedetectedoratleasttwicetheEthersroundtriptime.Welimitinsoftwarethemaximumlengthofourpacketstobenear4000bitstokeepthelatencyofnetworkaccessdownandtopermitefficientuseofstationpacketbufferstorage.Forpacketswhosesizeisabove4000bits,theefficiencyofourexperimentalEthernetstayswellabove95401CommunicationsJuly1976ofVolume19theACMNumber7percent.Forpacketswithasizeapproximatingthatofaslot,Ethernetefficiencyapproachesl/e,theasymptoticefficiencyofaslottedAlohanetwork\27\.7.ProtocolThereismoretotheconstructionofaviablepacketcommunicationsystemthansimplyprovidingthemechanismsforpackettransport.Methodsforerrorcorrection,flowcontrol,processnaming,security,andaccountingmustalsobeprovidedthroughhigherlevelprotocolsimplementedontopoftheEthercontrolprotocoldescribedinSections3and4above.\7,10,12,21,28,34\.Ethercontrolincludespacketframing,errordetection,addressingandmultiaccesscontrollikeotherlinecontrolprocedures,Ethernetisusedtosupportnumerousnetworkandmultiprocessorarchitectures\30,31\.Hereisabriefdescriptionofonesimpleerrorcontrollingpacketprotocol.TheEFTPEthernetFileTransferProtocolisofinterestbothbecauseitisrelativelyeasytounderstandandimplementcorrectlyandbecauseithasdutifullycarriedmanyvaluablefilesduringthedevelopmentofmoregeneralandefficientprotocols.7.1.GeneralTerminologyIndiscussingpacketprotocols,weusethefollowinggenerallyusefulterminology.Apacketissaidtohaveasourceandadestination.Aflowofdataissaidtohaveasenderandareceiver,recognizingthattosupportaflowofdatasomepacketstypicallyacknowledgmentswillbesourcedatthereceiveranddestinedforthesender.Aconnectionissaidtohavealistenerandaninitiatorandaserviceissaidtohaveaserverandauser.Itisveryusefultotreattheseasorthogonaldescriptorsoftheparticipantsinacommunication.Ofcourse,aserverisusuallyalistenerandthesourceofdatabearingpacketsisusuallythesender.7.2EFTPThefirst16bitsofallEthernetpacketscontainitsinterfaceinterpretabledestinationandsourcestationaddresses,abyteeach,inthatorderseeFigure2.Bysoftwareconvention,thesecond16bitsofallEthernetpacketscontainthepackettype.Differentprotocolsusedisjointsetsofpackettypes.TheEFTPuses5packettypesdata,ack,abort,end,andendreply.Followingthe16bittypewordofanEFTPpacketare16bitsofsequencenumber,16bitsoflength,optionallysome16bitdatawords,andfinallya16bitsoftwarechecksumwordseeFigure4.TheEthernetshardwarechecksumispresentonlyontheEtherandisnotcountedatthislevelofprotocol.Itshouldbeobviousthatlittlecarehasbeentakentocramcertainfieldsintojusttherightnumberofbits.Theemphasishereisonsimplicityandeaseofprogramming.Despitethisdisclaimer,wedofeelthatitismoreadvisabletoerronthesideofspaciousfieldstryasyoumay,onefieldoranotherwillalwaysturnouttobetoosmall.Thesoftwarechecksumwordisusedtolowertheprobabilityofanundetectederror.ItservesnotonlyasabackupfortheexperimentalEthernetsserialhardware16bitcyclicredundancychecksuminFigure2,butalsoforprotectionagainstfailuresinparalleldatapathswithinstationswhicharenotcheckedbytheCRC.ThechecksumusedbytheEFTPisalscomplementaddandcycleovertheentirepacket,includingheaderandcontentdata.Thechecksumcanbeignoredattheusersperilateitherendthesendermayputalllsanimpossiblevalueintothechecksumwordtoindicatetothereceiverthatnochecksumwascomputed.7.2.1Datatransfer.The16bitwordsofafilearecarriedfromsendingstationtoreceivingstationindatapacketsconsecutivelynumberedfrom0.Eachdatapacketisretransmittedperiodicallybythesenderuntilanackpacketwithamatchingsequencenumberisreturnedfromthereceiver.Thereceiverignoresalldamagedpackets,packetsfromastationotherthanthesender,andpacketswhosesequencenumberdoesnotmatcheithertheexpectedoneortheonepreceding.Whenapackethastheexpectedsequencenumber,thepacketisacked,itsdataisacceptedaspartofthefile,andthesequencenumberisincremented.Whenapacketarriveswithasequencenumberonelessthanthatexpected,itisacknowledgedanddiscardedthepresumptiortisthatitsackwaslostandneedsretransmission\21\.7.2.2End.Whenallthedatahasbeentransmitted,anendpacketissentwiththenextconsecutivesequencenumberandthanthesenderwaitsforamatchingendreply.Havingacceptedanendpacketinsequence,thedatareceiverrespondswithamatchingendreplyandthendallysforsomereasonablylongperiodoftime10seconds.Upongettingtheendreply,thesendingstationtransmitsanechoingendreplyandisfreetogooffwiththeassurancethatthefilehasbeentransferredsuccessfully.Thedallyingreceiverthengetstheechoedendreplyandittoogoesoffassured.TableI.EthernetEfficiency.QP4096P1024P512P4811.00001.00001.00001.000020.98840.95520.91430.500030.98570.94470.89510,444440.98420.93960.880.421950.98340.93670.88100.4096100.98180.93100.87090.3874320.980.92720.86420.3737640.98050.92630.86270.37081280.98040.92590.86200,332560.98030.920.86160.36402CommunicationsJuly1976ofVolume19theACMNumber7Fig.4.EFFPpacketlayout.DestinationSourcePacketTypeSequenceNumberLengthinwordsDatawordsSoftwareChecksum116bitWordIDataPacketOnlyThecomparativelycomplexenddallysequenceisintendedtomakeitpracticallycertainthatthesenderandreceiverofafilewillagreeonwhetherthefilehasbeentransmittedcorrectly.Iftheendpacketislost,thedatasendersimplyretransmitsitasitwouldanypacketwithanoverdueacknowledgement.Iftheendreplyfromthedatareceiverislost,thedatasenderwilltimeoutinthesamewayandretransmittheendpacketwhichwillinturnbeacknowledgedbythedallyingreceiver.Iftheechoedendreplyislost,thedallyingreceiverwillbeinconveniencedhavingtowaitforit,butwhenithastimedout,thereceivercanneverthelessbeassuredofsuccessfultransferofthefilebecausetheendpackethasbeenreceived.Atanytimeduringallofthis,eithersideisfreetodecidecommunicationhasfailedandjustgiveup,itisconsideredpolitetosendanabortpackettoendthecommunicationpromptlyintheeventof,say,auserinitiatedabortorafilesystemerror.7.2.3EFTPshortcomings.TheEFTPhasbeenveryuseful,butitsshortcomingsaremany.First,theprotocolprovidesonlyforfiletransferfromstationtostationinasinglenetworkandspecificallynotfromprocesstoprocesswithinstationseitheronthesamenetworkorthroughagateway.Second,processrendezvousisdegenerateinthattherearenomechanismsforfindingprocessesbynameorforconvenienthandlingofmultipleusersbyasingleserver.Third,thereisnorealflowcontrol.Ifdataarrivesatareceiverunabletoacceptitintoitsbuffers,thedatacansimplybethrownawaywithcompleteassurancethatitwillberetransmittedeventually.Thereisnowayforareceivertoquenchtheflowofsuchwastedtransmissionsortoexpediteretransmission.Fourth,dataistransmittedinintegralnumbersof16bit403wordsbelongingtounnamedfilesandthustheEFTPiseitherterriblyrestrictiveordemandssomenestedfiletransferformatsinternaltoitsdatawords.Andfifth,functionalgeneralityislostbecausethereceiverisalsothelistenerandserver.8.ConclusionOurexperiencewithanoperatingEthernetleadsustoconcludethatouremphasisondistributedcontrolwaswellplaced.Bykeepingthesharedcomponentsofthecommunicationsystemtoaminimumandpassive,wehaveachievedaveryhighlevelofreliability.InstallationandmaintenanceofourexperimentalEthernethasbeenmorethansatisfactory.Theflexibilityofstationinterconnectionprovidedbybroadcastpacketswitchinghasencouragedthedevelopmentofnumerouscomputernetworkingandmultiprocessingapplications.Acknowledgments.OurcolleaguesattheXeroxPaloAltoResearchCenter,especiallyTatC.Lam,ButlerW.Lampson,JohnF.Shoch,andCharlesP.Thacker,havecontributedinmanywaystotheevolutionofEthernetideasandtotheconstructionoftheexperimentalsystemwithoutwhichsuchideaswouldbejustsomuchspeculation.ReceivedMay1975revisedDecember1975References1.Abramson,N.TheAlohasystem.AFIPSConf.Proc.,Vol.37,1970FJCC,AFIPSPress,Montvale,N.J.,1970,pp.281285.2.Abramson,N.andKuo,F.F.ComputerCommunicationNetworks.PrenticeHall,EnglewoodCliffs,N.J.,1975.3.Ashenhurst,R.L.,andVonderohe,R.H.Ahierarchicalnetwork.Datamation21,2Feb.1975,4044.4.Baran,P.Ondistributedcommunications.RandCorp.MemoRM3420PR,Aug.1964.5.Barnes,G.H.,Brown,R.M.,Kato,M.,Kuck,D.J.,Slotaick,D.L.,andStokes,R.A.TheIlliacIVComputer.IEEETrans.ComputersC17,8Aug.1968,758770.6.Binder,R.,Abramson,N.,Kuo,F.,Okinaka,A.,andWax,D.Alohapacketbroadcastingaretrospect.AFIPSConf.Proc.,Vol.44,1975NCC,AFIPSPress,Montvale,N.J.,1975.7.Cerf,V.G.,andKahn,R.E.Aprotocolforpacketnetworkintercommunication.IEEETrans.Comm.COMM22,5May1974,637648.8.Theshrinkingworldcomputernetworksandcommunications.Computer7,2Feb.1974.9.Distributedfunctioncomputerarchitectures.Computer7,3March1974.10.Crocker,S.D.,Heafner,J.F.,Metcalfe,R.M.,andPostel,J.B.FunctionorientedprotocolsfortheArpacomputernetwork.AFIPSConf.Proc.,Vol.40,1972SJCC,AFIPSPress,Montvale,N.J.,1972,pp.271279.11.Crowther,W.R.,Heart,F.E.,McKenzie,A.A.,McQuillan,J.M.,andWalden,D.C.Issuesinpacketswitchingnetworkdesign.AFIPSConf.Proc.,Vol.44,1975NCC,AFIPSPress,Montvale,N.J.,1975,pp.161175.12.Farber,D.J.,etal.Thedistributedcomputingsystem.Proc.7thAnn.IEEEComputerSoc.InternationalConf.,Feb.1973,pp.3134.13.Farber,D.J.,Aringnetwork.Datamation21,2Feb.1975,4446.14.Fraser,A.G.Avirtualchannelnetwork.Datamation21,2Feb.1975,5153.CommunicationsJuly1976ofVolume19theACMNumber7

注意事项

本文(40-Ethernet - distributed packet switching for local computer networks.pdf)为本站会员(baixue100)主动上传,人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知人人文库网([email protected]),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。

copyright@ 2015-2017 人人文库网网站版权所有
苏ICP备12009002号-5