40-Ethernet - distributed packet switching for local computer networks.pdf_第1页
40-Ethernet - distributed packet switching for local computer networks.pdf_第2页
40-Ethernet - distributed packet switching for local computer networks.pdf_第3页
40-Ethernet - distributed packet switching for local computer networks.pdf_第4页
40-Ethernet - distributed packet switching for local computer networks.pdf_第5页
已阅读5页,还剩5页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

ComputerSystemsG.Bell,S.FullerandD.Siewiorek,EditorsEthernet:DistributedPacketSwitchingforLocalComputerNetworksRobertM.MetcalfeandDavidR.BoggsXeroxPaloAltoResearchCenterEthernetisabranchingbroadcastcommunicationsystemforcarryingdigitaldatapacketsamonglocallydistributedcomputingstations.ThepackettransportmechanismprovidedbyEthernethasbeenusedtobuildsystemswhichcanbeviewedaseitherlocalcomputernetworksorlooselycoupledmultiprocessors.AnEther-netssharedcommunicationfacility,itsEther,isapas-sivebroadcastmediumwithnocentralcontrol.Coordi-nationofaccesstotheEtherforpacketbroadcastsisdistributedamongthecontendingtransmittingstationsusingcontrolledstatisticalarbitration.SwitchingofpacketstotheirdestinationsontheEtherisdistributedamongthereceivingstationsusingpacketaddressrecognition.Designprinciplesandimplementationaredescribed,basedonexperiencewithanoperatingEther-netof100nodesalongakilometerofcoaxialcable.Amodelforestimatingperformanceunderheavyloadsandapacketprotocolforerrorcontrolledcommunica-tionareincludedforcompleteness.KeyWordsandPhrases:computernetworks,packetswitching,multiprocessing,distributedcontrol,dis-tributedcomputing,broadcastcommunication,statisti-calarbitrationCRCategories:3.81,4.32,6.35Copyright1976,AssociationforComputingMachinery,Inc.Generalpermissiontorepublish,butnotforprofit,allorpartofthismaterialisgrantedprovidedthatACMscopyrightnoticeisgivenandthatreferenceismadetothepublication,toitsdateofissue,andtothefactthatreprintingprivilegesweregrantedbypermissionoftheAssociationforComputingMachinery.Authorspresentaddresses:R.M.Metcalfe,TransactionTech-nology,Inc.,10880WilshireBoulevard,LosAngeles,CA94304;D.Boggs,XeroxPaloAltoResearchCenter,3333CoyoteHillRoad,PaloAlto,CA94304.3951.BackgroundOnecancharacterizedistributedcomputingasaspectrumofactivitiesvaryingintheirdegreeofdecen-tralization,withoneextremebeingremotecomputernetworkingandtheotherextremebeingmultiprocess-ing.Remotecomputernetworkingisthelooseintercon-nectionofpreviouslyisolated,widelyseparated,andratherlargecomputingsystems.Multiprocessingistheconstructionofpreviouslymonolithicandserialcom-putingsystemsfromincreasinglynumerousandsmallerpiecescomputinginparallel.Nearthemiddleofthisspectrumislocalnetworking,theinterconnectionofcomputerstogaintheresourcesharingofcomputernetworkingandtheparallelismofmultiprocessing.Theseparationbetweencomputersandtheassoci-atedbitrateoftheircommunicationcanbeusedtodi-videthedistributedcomputingspectrumintobroadactivities.Theproductofseparationandbitrate,nowabout1gigabit-meterpersecond(1Gbmps),isanin-dicationofthelimitofcurrentcommunicationtech-nologyandcanbeexpectedtoincreasewithtime:ActivitySeparationBitrateRemotenetworks10km.1MbpsLocalnetworks10-.1km.1-10MbpsMultiprocessors10Mbps1.1RemoteComputerNetworkingComputernetworkingevolvedfromtelecommunica-tionsterminal-computercommunication,wheretheob-jectwastoconnectremoteterminalstoacentralcom-putingfacility.Astheneedforcomputer-computerinterconnectiongrew,computersthemselveswereusedtoprovidecommunication2,4,29.Communicationusingcomputersaspacketswitches15-21,26andcommunicationsamongcomputersforresourcesharingI0,32werebothadvancedbythedevelopmentoftheArpaComputerNetwork.TheAlohaNetworkattheUniversityofHawaiiwasoriginallydevelopedtoapplypacketradiotechniquesforcommunicationbetweenacentralcomputeranditsterminalsscatteredamongtheHawaiianIslands1,2.Manyoftheterminalsarenowminicomputerscom-municatingamongthemselvesusingtheAlohaNet-worksMenehuneasapacketswitch.TheMenehuneandanArpanetImparenowconnected,providingter-minalsontheAlohaNetworkaccesstocomputingresourcesontheU.S.mainland.Justascomputernetworkshavegrownacrosscon-tinentsandoceanstointerconnectmajorcomputingfacilitiesaroundtheworld,theyarenowgrowingdowncorridorsandbetweenbuildingstointerconnectmini-computersinofficesandlaboratories3,12,13,14,35.1.2MultiprocessingMultiprocessingfirsttooktheformofconnectinganI/Ocontrollertoalargecentralcomputer;raMsAspisaCommuaicationsJuly1976ofVolume19theACMNumber7classicexample29.Next,multiplecentralprocessorswereconnectedtoacommonmemorytoprovidemorepowerforcompute-boundapplications33.Forcertainoftheseapplications,moreexoticmultiprocessorarchi-tecturessuchasIlliaeIVwereintroduced5.Morerecentlyminicomputershavebeenconnectedinmultiprocessorconfigurationsforeconomy,relia-bility,andincreasedsystemmodularity24,36.Thetrendhasbeentowarddecentralizationforreliability;looselycoupledmultiprocessorsystemsdependlessonsharedcentralmemoryandmoreonthinwiresforin-terprocesscommunicationwithincreasedcomponentisolation18,26.Withthecontinuedthinningofin-terprocessorcommunicationforreliabilityandthede-velopmentofdistributableapplications,multiprocessingisgraduallyapproachingalocalformofdistributedcomputing.1.3LocalComputerNetworkingEthernetsharesmanyobjectiveswithotherlocalnetworkssuchasMitresMitrix,BellTelephoneLabora-torysSpider,andU.C.IrvinesDistributedComputingSystem(DCS)12,13,14,35.Prototypesofallfourlocalnetworkingschemesoperateatbitratesbetweenoneandthreemegabitspersecond.MitrixandSpiderhaveacentralminicomputerforswitchingandband-widthallocation,whileDCSandEthernetusedistrib-utedcontrol.SpiderandDCSusearingcommunicationpath,Mitrixusesoff-the-shelfCATVtechnologytoimplementtwoone-waybusses,andourexperimentalEthernetusesabranchingtwo-waypassivebus.Differ-encesamongthesesystemsareduetodifferencesamongtheirintendedapplications,differencesamongthecostconstraintsunderwhichtrade-offsweremade,anddifferencesofopinionamongresearchers.BeforegoingintoadetaileddescriptionofEthernet,weofferthefollowingoverview(seeFigure1).2.SystemSummaryEthernetisasystemforlocalcommunicationamongcomputingstations.OurexperimentalEthernetusestappedcoaxialcablestocarryvariablelengthdigitaldatapacketsamong,forexample,personalminicom-puters,printingfacilities,largefilestoragedevices,magnetictapebackupstations,largercentralcomputers,andlonger-haulcommunicationequipment.Thesharedcommunicationfacility,abranchingEther,ispassive.AstationsEthernetinterfacecon-nectsbit-seriallythroughaninterfacecabletoatrans-ceiverwhichinturntapsintothepassingEther.ApacketisbroadcastontotheEther,isheardbyallsta-tions,andiscopiedfromtheEtherbydestinationswhichselectitaccordingtothepacketsleadingaddressbits.Thisisbroadcastpacketswitchingandshouldbedistinguishedfromstore-and-forwardpacketswitching,inwhichroutingisperformedbyintermediateprocess-ingelements.Tohandlethedemandsofgrowth,anEthernetcanbeextendedusingpacketrepeatersforsignalregeneration,packetfiltersfortrafficlocalization,andpacketgatewaysforinternetworkaddressextension.Controliscompletelydistributedamongstations,withpackettransmissionscoordinatedthroughstatisti-calarbitration.Transmissionsinitiatedbyastationde-fertoanywhichmayalreadybeinprogress.Oncestarted,ifinterferencewithotherpacketsisdetected,atransmissionisabortedandrescheduledbyitssourcestation.Afteracertainperiodofinterference-freetrans-mission,apacketisheardbyallstationsandwillruntocompletionwithoutinterference.Ethernetcontrollersincollidingstationseachgeneraterandomretransmis-sionintervalstoavoidrepeatedcollisions.Themeanofapacketsretransmissionintervalsisadjustedasafunc-tionofcollisionhistorytokeepEtherutilizationneartheoptimumwithchangingnetworkload.Evenwhentransmittedwithoutsource-detectedin-terference,apacketmaystillnotreachitsdestinationwithouterror;thus,packetsaredeliveredonlywithhighprobability.StationsrequiringaresidualerrorratelowerthanthatprovidedbythebareEthernetpackettransportmechanismmustfollowmutuallyagreeduponpacketprotocols.3.DesignPrinciplesOurobjectistodesignacommunicationsystemwhichcangrowsmoothlytoaccommodateseveralbuildingsfullofpersonalcomputersandthefacilitiesneededfortheirsupport.Likethecomputingstationstobeconnected,thecommunicationsystemmustbeinexpensive.Wechoosetodistributecontrolofthecommunicationsfacilityamongthecommunicatingcomputerstoeliminatethereliabilityproblemsofanactivecentralcontroller,toavoidcreatingabottleneckinasystemrichinparallel-ism,andtoreducethefixedcostswhichmakesmallsys-temsuneconomical.EthernetdesignstartedwiththebasicideaofpacketcollisionandretransmissiondevelopedintheAlohaNetwork1.Weexpectedthat,liketheAlohaNetwork,Ethernetswouldcarryburstytrafficsothatconven-tionalsynchronoustime-divisionmultiplexing(STDM)wouldbeinefficient1,2,21,26.WesawpromiseintheAlohaapproachtodistributedcontrolofradiochannelmultiplexingandhopedthatitcouldbeappliedeffec-tivelywithmediasuitedtolocalcomputercommunica-tion.Withseveralinnovationsofourown,thepromiseisrealized.Ethernetisnamedforthehistoricalluminiferousetherthroughwhichelectromagneticradiationswereonceallegedtopropagate.LikeanAloharadiotrans-mitter,anEthernettransmitterbroadcastscompletely-addressedtransmitter-synchronousbitsequencescalledpacketsontotheEtherandhopesthattheyareheardby396CommunicationsJuly1976ofVolume19theACMNumber7Fig.1.Atwo-segmentEthernet.TERMINATORTRANS-INTERFACETAPCABLEETIIERENT#lIlclIONNTTERSTATIONROFLALCEERI0NNTTERSTATIONR0FLALCEERSTATIONCONTROLLERwIINTERFACEETHERSEGMENT#2mmtheintendedreceivers.TheEtherisalogicallypassivemediumforthepropagationofdigitalsignalsandcanbeconstructedusing.anynumberofmediaincludingcoaxialcables,twistedpairs,andopticalfibers.3.1TopologyWecannotaffordtheredundantconnectionsanddynamicroutingofstore-and-forwardpacketswitchingtoassurereliablecommunication,sowechoosetoachievereliabilitythroughsimplicity.Wechoosetomakethesharedcommunicationfacilitypassivesothatthefailureofanactiveelementwilltendtoaffectthecommunicationsofonlyasinglestation.Thelayoutandchangingneedsofofficeandlaboratorybuildingsleadsustopickanetworktopologywiththepotentialforconvenientincrementalextentionandreconfigurationwithminimalservicedisruption.ThetopologyoftheEthernetisthatofanunrootedtree.ItisatreesothattheEthercanbranchattheen-trancetoabuildingscorridor,yetavoidmultipathin-terference.TheremustbeonlyonepaththroughtheEtherbetweenanysourceanddestination;ifmorethanonepathweretoexist,atransmissionwouldinterferewithitself,repeatedlyarrivingatitsintendeddestina-tionhavingtravelledbypathsofdifferentlength.TheEtherisunrootedbecauseitcanbeextendedfromanyofitspointsinanydirection.Anystationwishingtojoin397anEthernettapsintotheEtheratthenearestconvenientpoint.Lookingattherelationshipofinterconnectionandcontrol,weseethatEthernetisthedualofastarnet-work.Ratherthandistributedinterconnectionthroughmanyseparatelinksandcentralcontrolinaswitchingnode,asinastarnetwork,theEthernethascentralinter-connectionthroughtheEtheranddistributedcontrolamongitsstations.UnlikeanAlohaNetwork,whichisastarnetworkwithanoutgoingbroadcastchannelandanincomingmulti-accesschannel,anEthernetsupportsmany-to-manycommunicationwithasinglebroadcastmulti-accesschannel.3.2ControlSharingoftheEtheriscontrolledinsuchawaythatitisnotonlypossiblebutprobablethattwoormoresta-tionswillattempttotransmitapacketatroughlythesametime.PacketswhichoverlapintimeontheEtheraresaidtocollide;theyinterferesoastobeunrecogniza-blebyareceiver.Astationrecoversfromadetectedcollisionbyabandoningtheattemptandretransmittingthepacketaftersomedynamicallychosenrandomtimeperiod.Arbitrationofconflictingtransmissiondemandsisbothdistributedandstatistical.WhentheEtherislargelyunused,astationtransmitsitspacketsatwill,thepacketsarereceivedwithouterror,andalliswell.Asmorestationsbegintotransmit,therateofpacketinterferenceincreases.Ethernetcontrollersineachstationarebuilttoadjustthemeanretransmissionintervalinproportiontothefrequencyofcollisons;sharingoftheEtheramongcompetingstation-stationtransmissionsistherebykeptneartheoptimum20,21.Adegreeofcooperationamongthestationsisre-quiredtosharetheEtherequitably.Indemandingap-plicationscertainstationsmightusefullytaketrans-missionprioritythroughsomesystematicviolationofequityrules.AstationcouldusurptheEtherbynotad-justingitsretransmissionintervalwithincreasingtrafficorbysendingverylargepackets.Bothpracticesarenowprohibitedbylow-levelsoftwareineachstation.3.3AddressingEachpackethasasourceanddestination,bothofwhichareidentifiedinthepacketsheader.ApacketplacedontheEthereventuallypropagatestoallsta-tions.AnystationcancopyapacketfromtheEtherintoitslocalmemory,butnormallyonlyanactivedestina-tionstationmatchingitsaddressinthepacketsheaderwilldosoasthepacketpasses.Byconvention,azerodestinationaddressisawildcardandmatchesallad-dresses;apacketwithadestinationofzeroiscalledabroadcastpacket.3.4ReliabilityAnEthernetisprobabilistic.Packetsmaybelostduetointerferencewithotherpackets,impulsenoiseontheCommunicationsJuly1976ofVolume19ethACMNumber7Ether,aninactivereceiveratapacketsintendeddesti-nation,orpurposefuldiscard.Protocolsusedtocom-municatethroughanEthernetmustassumethatpacketswillbereceivedcorrectlyatintendeddestinationsonlywithhighprobability.AnEthernetgivesitsbesteffortstotransmitpacketssuccessfully,butitistheresponsibilityofprocessesinthesourceanddestinationstationstotaketheprecautionsnecessarytoassurereliablecommunicationofthequalitytheythemselvesdesire18,21.Recognizingthecostli-nessanddangersofpromisingerror-freecommuni-cation,werefrainfromguaranteeingreliabledeliveryofanysinglepackettogetbotheconomyoftransmis-sionandhighreliabilityaveragedovermanypackets21.Removingtheresponsibilityforreliablecommuni-cationfromthepackettransportmechanismallowsustotailorreliabilitytotheapplicationandtoplaceerrorre-coverywhereitwilldothemostgood.Thispolicybe-comesmoreimportantasEthernetsareinterconnectedinahierarchyofnetworksthroughwhichpacketsmusttravelfartherandsuffergreaterrisks.3.5MechanismsAstationconnectstotheEtherwithatapandatransceiver.AtapisadeviceforphysicallyconnectingtotheEtherwhiledisturbingitstransmissioncharacteris-ticsaslittleaspossible.Thedesignofthetransceivermustbeanexerciseinparanoia.PrecautionsmustbetakentoinsurethatlikelyfailuresinthetransceiverorstationdonotresultinpollutionoftheEther.Inpar-ticular,removingpowerfromthetransceivershouldcauseittodisconnectfromtheEther.FivemechanismsareprovidedinourexperimentalEthernetforreducingtheprobabilityandcostoflosingapacket.Theseare(1)carrierdetection,(2)interferencedetection,(3)packeterrordetection,(4)truncatedpacketfiltering,and(5)collisionconsensusenforcement.3.5.1Carrierdetection.AsapackersbitsareplacedontheEtherbyastation,theyarephaseencoded(likebitsonamagnetictape),whichguaranteesthatthereisatleastonetransitionontheEtherduringeachbittime.ThepassingofapacketontheEthercanthereforebede-tectedbylisteningforitstransitions.Tousearadioanalogy,wespeakofthepresenceofcarrierasapacketpassesatransceiver.Becauseastationcansensethecar-rierofapassingpacket,itcandelaysendingoneofitsownuntilthedetectedpacketpassessafely.TheAlohaNetworkdoesnothavecarrierdetectionandconse-quentlysuffersasubstantiallyhighercollisionrate.Withoutcarrierdetection,efficientuseoftheEtherwoulddecreasewithincreasingpacketlength.InSection6below,weshowthatwithcarrierdetection,Etherefficiencyincreaseswithincreasingpacketlength.Withcarrierdetectionweareabletoimplementdeference:nostationwillstarttransmittingwhilehearingcarrier.Withdeferencecomesacquisition:onceapackettransmissionhasbeeninprogressforanEtherend-to-endpropagationtime,allstationsarehearingcarrierandaredeferring;theEtherhasbeenacquiredandthetransmissionwillcompletewithoutaninterferingcolli-sion.Withcarrierdetection,collisionsshouldoccuronlywhentwoormorestationsfindtheEthersilentandbe-gintransmittingsimultaneously:withinanEtherend-to-endpropagationtime.Thiswillalmostalwayshappenimmediatelyafterapackettransmissionduringwhichtwoormorestationsweredeferring.Becausestationsdonotnowrandomizeafterdeferring,whenthetrans-missionterminates,thewaitingstationspileontogether,collide,randomize,andretransmit.3.5.2Interferencedetection.Eachtransceiverhasaninterferencedetector.InterferenceisindicatedwhenthetransceivernoticesadifferencebetweenthevalueofthebititisreceivingfromtheEtherandthevalueofthebititisattemptingtotransmit.Interferencedetectionhasthreeadvantages.First,astationdetectingacollisionknowsthatitspackethasbeendamaged.Thepacketcanbescheduledforre-transmissionimmediately,avoidingalongacknowledg-menttimeout.Second,interferenceperiodsontheEtherarelimitedtoamaximumofoneroundtriptime.Collid-ingpacketsintheAlohaNetworkruntocompletion,butthetruncatedpacketsresultingfromEthernetcolli-sionswasteonlyasmallfractionofapackettimeontheEther.Third,thefrequencyofdetectedinterferenceisusedtoestimateEthertrafficforadjustingretrans-missionintervalsandoptimizingchannelefficiency.3.5.3Packeterrordetection.AsapacketisplacedontheEther,achecksumiscomputedandappended.AsthepacketisreadfromtheEther,thechecksumisrecomputed.Packetswhichdonotcarryaconsistentchecksumarediscarded.Inthiswaytransmissionerrors,impulsenoiseerrors,anderrorsduetoundetectedinter-ferencearecaughtatapaeketsdestination.3.5.4Truncatedpacketfiltering.Interferencede-tectionanddeferencecausemostcollisionstoresultintruncatedpacketsofonlyafewbits;collidingstationsdetectinterferenceandaborttransmissionwithinanEtherroundtriptime.Toreducetheprocessingloadthattherejectionofsuchobviouslydamagedpacketswouldplaceonlisteningstationsoftware,truncatedpacketsarefilteredoutinhardware.3.5.5Collisionconsensusenforcement.Whenasta-tiondeterminesthatitstransmissionisexperiencingin-terference,itmomentarilyjamstheEthertoinsurethatallotherparticipantsinthecollisionwilldetectinter-ferenceand,becauseofdeference,willbeforcedtoabort.Withoutthiscollisionconsensusenforcementmechanism,itispossiblethatthetransmittingstationwhichwouldotherwisebethelasttodetectacollisionmightnotdosoastheotherinterferingtransmissionssuccessivelyabortandstopinterfering.Althoughthepacketmaylookgoodtothatlasttransmitter,differentpathlengths398CommunicationsJuly1976ofVolume19theACMNumber7betweenthecollidingtransmittersandtheintendedre-ceiverwillcausethepackettoarrivedamaged.4.ImplementationOurchoicesof1kilometer,3megabitspersecond,and256stationsfortheparametersofanexperimentalEthernetwerebasedoncharacteristicsofthelocallydistributedcomputercommunicationenvironmentandourassessmentsofwhatwouldbemarginallyachiev-able;theywerecertainlynothardrestrictionsessentialtotheEthernetconcept.Weexpectthatareasonablemaximumnetworksizewouldbeontheorderof1kilometerofcable.WeusedthisworkingnumbertochooseamongEthersofvaryingsignalattenuationandtodesigntransceiverswithap-propriatepowerandsensitivity.ThedominantstationonourexperimentalEthernetisaminicomputerforwhich3megabitspersecondisaconvenientdatatransferrate.Bykeepingthepeakratewellbelowthatofthecomputerspathtomainmemory,wereducetheneedforexpensivespecial-purposepacketbufferinginourEthernetinterfaces.Bykeepingthepeakrateashighasisconvenient,weprovideforlargernum-bersofstationsandmoreambitiousmultiprocessingcommunicationsapplications.Toexpeditelow-levelpackethandlingamong256stations,weallocatethefirst8-bitbyteofthepackettobethedestinationaddressfieldandthesecondbytetobethesourceaddressfield(seeFigure2).256isanumbersmallenoughtoalloweachstationtogetanadequateshareoftheavailablebandwidthandapproachesthelimitofwhatwecanachievewithcurrenttechniquesfortappingcables.256isonlyaconvenientnumberforthelowestlevelofprotocol;higherlevelscanaccomodateextendedaddressspaceswithadditionalfieldsinsidethepacketandsoftwaretointerpretthem.OurexperimentalEthernetimplementationhasfourmajorparts:theEther,transceivers,interfaces,andcon-trollers(seeFigure1).4.1EtherWechosetoimplementourexperimentalEtherusinglow-losscoaxialcablewithoff-the-shelfCATVtapsandconnectors.ItispossibletomixEthersonasingleEthernet;weuseasmaller-diametercoaxforconvenientconnectionwithinstationdustersandalarger-diametercoaxforlow-lossrunsbetweenclusters.ThecostofcoaxialcableEtherisinsignificantrelativetothecostofthedistributedcomputingsystemssupportedbyEthernet.4.2TransceiversOurexperimentaltransceiverscandriveakilometerofcoaxialcableEthertappedby256stationstrans-mittingat3megabitspersecond.Thetransceiverscanendure(i.e.workafter)sustaineddirectshorting,im-399properterminationoftheEther,andsimultaneousdrivebyall256stations;theycantolerate(i.e.workduring)grounddifferentialsandeverydayelectricalnoise,fromtypewritersorelectricdrills,encounteredwhenstationsareseparatedbyasmuchasakilometer.AnEthernettransceiverattachesdirectlytotheEtherwhichpassesbyintheceilingorunderthefloor.Itispoweredandcontrolledthroughfivetwistedpairsinaninterfacecablecarryingtransmitdata,receivedata,interferencedetect,andpowersupplyvoltages.Whenunpowered,thetransceiverdisconnectsitselfelectricallyfromtheEther.Hereiswhereourfightforreliabilityiswonorlost;abrokentransceivercan,butshouldnot,bringdownanentireEthernet.AwatchdogtimercircuitineachtransceiverattemptstopreventpollutionoftheEtherbyshuttingdowntheoutputstageifitactssuspiciously.FortransceiversimplicityweusetheEthersbasefrequencyband,butanEthernetcouldbebuilttouseanysuitablysizedbandofafrequencydi-visionmultiplexedEther.Eventhoughourexperimentaltransceiversareverysimpleandcantolerateonlylimitedsignalattenuation,theyhaveprovenquiteadequateandreliable.AmoresophisticatedtransceiverdesignmightpermitpassivebranchingoftheEtherandwiderstationseparation.4.3InterfaceAnEthernetinterfaceserializesanddeserializestheparalleldatausedbyitsstation.ThereareanumberofdifferentstationsonourEthernet;aninterfacemustbebuiltforeachkind.Eachinterfaceisequippedwiththehardwareneces-sarytocomputea16-bitcyclicredundancychecksum(CRC)onserialdataasitistransmittedandreceived.ThischecksumprotectsonlyagainsterrorsintheEtherandspecificallynotagainsterrorsintheparallelpor-tionsoftheinterfacehardwareorstation.Higher-levelsoftwarechecksumsarerecommendedforapplicationsinwhichahigherdegreeofreliabilityisrequired.Atransmittinginterfaceusesapacketbufferaddressandwordcounttoserializeandphaseencodeavariablenumberof16-bitwordswhicharetakenfromthesta-tionsmemoryandpassedtothetransceiver,precededbyastartbit(calledSYNCinFigure2)andfollowedbytheCRC.AreceivinginterfaceusestheappearanceofcarriertodetectthestartofapacketandusestheSYNCbittoacquirebitphase.Aslongascarrierstayson,theinterfacedecodesanddeserializestheincomingbitstreamdepositing16-bitwordsinapacketbufferinthestationsmainmemory.Whencarriergoesaway,theinterfacechecksthatanintegralnumberof16-bitwordshasbeenreceivedandthattheCRCiscorrect.ThelastwordreceivedisassumedtobetheCRCandisnotcopiedintothepacketbuffer.Theseinterfacesordinarilyincludehardwareforacceptingonlythosepacketswithappropriateaddressesintheirheaders.Hardwareaddressfilteringhelpsasta-tionavoidburdensomesoftwarepacketprocessingwhenCommunicationsJuly1976ofVolume19theACMNumber7Fig.2.Ethernetpacketlayout.ACCESSIBLETOSOFIWAREIi-YDESTSOURCEADDRESSDATAII8BITS8BITS4OOOBIPSICIIECKSUMIf16BITStheEtherisverybusycarryingtrafficintendedforotherstations.4.4ControllerAnEthernetcontrolleristhestation-specificlow-levelfirmwareorsoftwareforgettingpacketsontoandoutoftheEther.Whenasource-detectedcollisionoc-curs,itisthesourcecontrollersresponsibilitytogene-rateanewrandomretransmissionintervalbasedontheupdatedcollisioncount.Wehavestudiedanumberofal-gorithmsforcontrollingretransmissionratesinstationstomaintainEtherefficiency20,22.Themostpracticalofthesealgorithmsestimatetrafficloadusingrecentcollisionhistory.Retransmissionintervalsaremultiplesofaslot,themaximumtimebetweenstartingatransmissionandde-tectingacollision,oneend-to-endroundtripdelay.AnEthernetcontrollerbeginstransmissionofeachnewpacketwithameanretransmissionintervalofoneslot.Eachtimeatransmissionattemptendsincollision,thecontrollerdelaysforanintervalofrandomlengthwithameantwicethatofthepreviousinterval,deferstoanypassingpacket,andthenattemptsretransmission.ThisheuristicapproximatesanalgorithmwehavecalledBinaryExponentialBackoff(seeFigure3)22.Whenthenetworkisunloadedandcollisionsarerare,themeanseldomdepartsfromoneandretrans-missionsareprompt.Asthetrafficloadincreases,morecollisionsareexperienced,abacklogofpacketsbuildsupinthestations,retransmissionintervalsincrease,andretransmissiontrafficbacksofftosustainchannelefficiency.5.GrowththeEtherandextendingitssignalcover,thereisatrade-offbetweenusingsophisticatedtransceiversandusingrepeaters.Withincreasedpowerandsensitivity,trans-ceiversbecomemoreexpensiveandlessreliable.TheintroductionofrepeatersintoanEthernetmakesthecentrallyinterconnectingEtheractive.Thefailureofatransceiverwillseverthecommunicationsofitsowner;thefailureofarepeaterpartitionstheEtherseveringmanycommunications.5.2TrafficCoverOnecanexpandanEthernetjustsofarbyaddingEtherandpacketrepeaters.AtsomepointtheEtherwillbesobusythatadditionalstationswilljustdividemorefinelythealreadyinadequatebandwidth.Thetrafficcovercanbeextendedwithanunbufferedtraffic-filteringrepeaterorpacketfilter,whichpassespacketsfromoneEthersegmenttoanotheronlyifthedestinationstationislocatedonthenewsegment.Apacketfilteralsoex-tendsthesignalcover.5.3AddressCoverOnecanexpandanEthernetjustsofarbyaddingEther,repeaters,andtrafficfilters.AtsomepointtherewillbetoomanystationstobeaddressedwiththeEther-nets8-bitaddresses.Theaddresscovercanbeextendedwithpacketgatewaysandthesoftwareaddressingcon-ventionstheyimplement7.Addressescanbeexpandedintwodirections:downintothestationbyaddingfieldstoidentifydestinationportsorprocesseswithinasta-tion,andupintotheinternetworkbyaddingfieldstoidentifydestinationstationsonremotenetworks.Agatewayalsoextendsthetrafficandsignalcovers.Therecanbeonlyonerepeaterorpacketfiltercon-nectingtwoEthersegments;apacketrepeatedontoasegmentbymultiplerepeaterswouldinterferewithitself.However,thereisnolimittothenumberofgatewaysconnectingtwosegments;agatewayonlyrepeatspacketsaddressedtoitselfasanintermediary.Failureofthesinglerepeaterconnectingtwosegmentspartitionsthenetwork;failureofagatewayneednotpartitionthenetittherearepathsthroughothergatewaysbetweenthesegments.5.1SignalCoverOnecanexpandanEthernetjustsofarbyaddingtransceiversandEther.Atsomepoint,thetransceiversandEtherwillbeunabletocarrytherequiredsignals.Thesignalcovercanbeextendedwithasimpleun-bufferedpacketrepeater.InourexperimentalEthernet,wherebecauseoftransceiversimplicitytheEthercannotbebranchedpassively,asimplerepeatermayjoinanynumberofEthersegmentstoenrichthetopologywhileextendingthesignalcover.Weoperateanexperimentaltwo-segmentpacketre-peater,buthopetoavoidrelyingonthem.Inbranching6.PerformanceWepresenthereasimplesetofformulaswithwhichtocharacterizetheperformanceexpectedofanEthernetwhenitisheavilyloaded.Moreelaborateanalysesandseveraldetailedsimulationshavebeendone,butthefollowingsimplemodelhasprovenveryusefulinunderstandingtheEthernetsdistributedcontentionscheme,evenwhenitisloadedbeyondexpectations1,20,21,22,23,27.WedevelopasimplemodeloftheperformanceofaloadedEthernetbyexaminingalternatingEthertimeperiods.Thefirst,calledatransmissioninterval,isthat40OCommunicationsJuly1976ofVolume19theACMNumber7duringwhichtheEtherhasbeenacquiredforasuccess-fulpackettransmission.Thesecond,calledacontentioninterval,isthatcomposedoftheretransmissionslotsofSection4.4,duringwhichstationsattempttoacquirecontroloftheEther.BecausethemodelsEthernetsareloadedandbecausestationsdefertopassingpacketsbe-forestartingtransmission,theslotsaresynchronizedbythetailoftheprecedingacquisitioninterval.Aslotwillbeemptywhennostationchoosestoattempttrans-missioninitanditwillcontainacollisionifmorethanonestationattemptstotransmit.Whenaslotcontainsonlyoneattemptedtransmission,thentheEtherhasbeenacquiredforthedurationofapacket,theconten-tionintervalends,andatransmissionintervalbegins.LetPbethenumberofbitsinanEthernetpacket.LetCbethepeakcapacityinbitspersecond,carriedontheEther.LetTbethetimeinsecondsofaslot,thenumberofsecondsittakestodetectacollisionafterstartingatransmission.LetusassumethatthereareQstationscontinuouslyqueuedtotransmitapacket;eithertheacquiringstationhasanewpacketimmedi-atelyafterasuccessfulacquisitionoranotherstationcomesready.NotethatQalsohappenstogivethetotalofferedloadonthenetworkwhichforthisanalysisisal-ways1orgreater.Weassumethataqueuedstationat-temptstotransmitinthecurrentslotwithprobability1/Q,ordelayswithprobability1-(l/Q);thisisknowntobetheoptimumstatisticaldecisionrule,approxi-matedinEthernetstationsbymeansofourload-esti-matingretransmissioncontrolalgorithms20,21.6.1AcquisitionProbabilityWenowcomputeA,theprobabilitythatexactlyonestationattemptsatransmissioninaslotandthereforeacquirestheEther.AisQ.(1/Q).(1-(l/Q)*(Q-1);thereareQwaysinwhichonestationcanchoosetotransmit(withprobability(l/Q)whileQ-1stationschoosetowait(withprobability1-(l/Q).Simplifying,A=(1-(l/Q)(Q-l).6.2WaitingTimeWenowcomputeIV,themeannumberofslotsofwaitinginacontentionintervalbeforeasuccessfulac-quisitionoftheEtherbyastationstransmission.TheprobabilityofwaitingnotimeatallisjustA,theprob-abilitythatoneandonlyonestationchoosestotrans-mitinthefirstslotfollowingatransmission.Theprob-abilityofwaiting1slotisA,(1-A);theprobabilityofwaitingislotsisA,(l-A)*i).Themeanofthisgeo-metricdistributionisw=(l-A)/A.Fig.3.Collisioncontrolalgorithm.ZEROLOADIESTIMATEFORNEWPACKET.AsLOADESTIMATEYESOVERFLOWED?NOGENERATEIRANDOMNUMBERIINCREASELOADESTIMATECOLLISIONIIA=IWEIGHTEDRANDOMNUMBERIERRORI6.3EfficiencyWenowcomputeE,thatfractionoftimetheEtheriscarryinggoodpackets,theefficiency.TheEtherstimeisdividedbetweentransmissionintervalsandconten-tionintervals.ApackettransmissiontakesP/Cseconds.ThemeantimetoacquisitionisW,T.Therefore,byoursimplemodel,E=(P/C)/(P/C)q-(W,T).TableIpresentsrepresentativeperformancefigures(i.e.E)forourexperimentalEthernetwiththeindicatedpacketsizesandnumberofcontinuouslyqueuedstations.Theefficiencyfiguresgivendonotaccountforinevitablereductionsduetoheadersandcontrolpacketsnorforlossesduetoimprecisecontroloftheretransmissionparameter1/Q;theformerisstraightforwardlyproto-col-dependentandthelatterrequiresanalysisbeyondthescopeofthispaper.Again,wefeelthatalloftheEthernetsinthetableareoverloaded;normallyloadedEthernetswillusuallyhaveaQmuchlessthan1andexhibitbehaviornotcoveredbythismodel.ForourcalculationsweuseaCof3megabitspersecondandaTof16microseconds.TheslotdurationTmustbelongenoughtoallowacollisiontobedetectedoratleasttwicetheEthersroundtriptime.Welimitinsoftwarethemaximumlengthofourpacketstobenear4000bitstokeepthelatencyofnetworkaccessdownandtopermitefficientuseofstationpacketbufferstorage.Forpacketswhosesizeisabove4000bits,theeffi-ciencyofourexperimentalEthernetstayswellabove95401CommunicationsJuly1976ofVolume19theACMNumber7percent.Forpacketswithasizeapproximatingthatofaslot,Ethernetefficiencyapproachesl/e,theasymptoticefficiencyofaslottedAlohanetwork27.7.ProtocolThereismoretotheconstructionofaviablepacketcommunicationsystemthansimplyprovidingthemechanismsforpackettransport.Methodsforerrorcorrection,flowcontrol,processnaming,security,andaccountingmustalsobeprovidedthroughhigher-levelprotocolsimplementedontopoftheEthercontrolpro-tocoldescribedinSections3and4above.7,10,12,21,28,34.Ethercontrolincludespacketframing,errorde-tection,addressingandmulti-accesscontrol;likeotherlinecontrolprocedures,Ethernetisusedtosupportnumerousnetworkandmultiprocessorarchitectures30,31.Hereisabriefdescriptionofonesimpleerror-con-trollingpacketprotocol.TheEFTP(EthernetFileTransferProtocol)isofinterestbothbecauseitisrela-tivelyeasytounderstandandimplementcorrectlyandbecauseithasdutifullycarriedmanyvaluablefilesdur-ingthedevelopmentofmoregeneralandefficientprotocols.7.1.GeneralTerminologyIndiscussingpacketprotocols,weusethefollowinggenerallyusefulterminology.Apacketissaidtohaveasourceandadestination.Aflowofdataissaidtohaveasenderandareceiver,recognizingthattosupportaflowofdatasomepackets(typicallyacknowledgments)willbesourcedatthereceiveranddestinedforthesender.Aconnectionissaidtohavealistenerandaninitiatorandaserviceissaidtohaveaserverandauser.Itisveryusefultotreattheseasorthogonaldescriptorsoftheparticipantsinacommunication.Ofcourse,aserverisusuallyalistenerandthesourceofdata-bearingpacketsisusuallythesender.7.2EFTPThefirst16bitsofallEthernetpacketscontainitsinterface-interpretabledestinationandsourcestationaddresses,abyteeach,inthatorder(seeFigure2).Bysoftwareconvention,thesecond16bitsofallEthernetpacketscontainthepackettype.Differentprotocolsusedisjointsetsofpackettypes.TheEFTPuses5packettypes:data,ack,abort,end,andendreply.Fol-lowingthe16-bittypewordofanEFTPpacketare16bitsofsequencenumber,16bitsoflength,optionallysome16-bitdatawords,andfinallya16-bitsoftwarechecksumword(seeFigure4).TheEthernetshard-warechecksumispresentonlyontheEtherandisnotcountedatthislevelofprotocol.Itshouldbeobviousthatlittlecarehasbeentakentocramcertainfieldsintojusttherightnumberofbits.Theemphasishereisonsimplicityandeaseofpro-gramming.Despitethisdisclaimer,wedofeelthatitismoreadvisabletoerronthesideofspaciousfields;tryasyoumay,onefieldoranotherwillalwaysturnouttobetoosmall.Thesoftwarechecksumwordisusedtolowertheprobabilityofanundetectederror.ItservesnotonlyasabackupfortheexperimentalEthernetsserialhard-ware16-bitcyclicredundancychecksum(inFigure2),butalsoforprotectionagainstfailuresinparalleldatapathswithinstationswhicharenotcheckedbytheCRC.ThechecksumusedbytheEFTPisalscomplementaddandcycleovertheentirepacket,includingheaderandcontentdata.Thechecksumcanbeignoredattheusersperilateitherend;thesendermayputallls(animpossiblevalue)intothechecksumwordtoindicatetothereceiverthatnochecksumwascomputed.7.2.1Datatransfer.The16-bitwordsofafilearecarriedfromsendingstationtoreceivingstationindatapacketsconsecutivelynumberedfrom0.Eachdatapacketisretransmittedperiodicallybythesenderuntilanackpacketwithamatchingsequencenumberisre-turnedfromthereceiver.Thereceiverignoresalldam-agedpackets,packetsfromastationotherthanthesender,andpacketswhosesequencenumberdoesnotmatcheithertheexpectedoneortheonepreceding.Whenapackethastheexpectedsequencenumber,thepacketisacked,itsdataisacceptedaspartofthefile,andthesequencenumberisincremented.Whenapacketarriveswithasequencenumberonelessthanthatex-pected,itisacknowledgedanddiscarded;thepresump-tiortisthatitsackwaslostandneedsretransmissionEnd.Whenallthedatahasbeentransmitted,anendpacketissentwiththenextconsecutivesequencenumberandthanthesenderwaitsforamatchingend-reply.Havingacceptedanendpacketinsequence,thedatareceiverrespondswithamatchingendreplyandthendallysforsomereasonablylongperiodoftime(10seconds).Upongettingtheendreply,thesendingstationtransmitsanechoingendreplyandisfreetogooffwiththeassurancethatthefilehasbeentransferredsuccess-fully.Thedallyingreceiverthengetstheechoedend-replyandittoogoesoffassured.TableI.EthernetEfficiency.QP=4096P=1024P=512P=4811.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.DestinationSourcePacketTypeSequenceNumberLength(inwords)Data(words)SoftwareChecksum-116-bitWordIDataPacketOnlyThecomparativelycomplexend-dallysequenceisintendedtomakeitpracticallycertainthatthesenderandreceiverofafilewillagreeonwhetherthefilehasbeentransmittedcorrectly.Iftheendpacketislost,thedatasendersimplyretransmitsitasit

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论