4.2BSDNetworkingImplementationNotes RevisedJuly,1983 SamuelJ.Leffler,WilliamN.Joy,RobertS.Fabry ComputerSystemsResearchGroup ComputerScienceDivision DepartmentofElectricalEngineeringandComputerScience UniversityofCalifornia,Berkeley Berkeley,CA94720 (415)642-7780 ABSTRACT Thisreportdescribestheinternalstructureofthenetworkingfacilities developedforthe4.2BSDversionoftheUNIX*operatingsystemfortheVAX†. Thesefacilitiesarebasedonseveralcentralabstractionswhichstructurethe external(user)viewofnetworkcommunicationaswellastheinternal(system) implementation. Thereportdocumentstheinternalstructureofthenetworkingsystem.The ‘‘4.2BSDSystemManual’’providesadescriptionoftheuserinterfacetothenetworkingfacilities. *UNIXisatrademarkofBellLaboratories. †DEC,VAX,DECnet,andUNIBUSaretrademarksofDigitalEquipmentCorporation.

NetworkingImplementation-i- Contents TABLEOFCONTENTS 1.Introduction 2.Overview 3.Goals 4.Internaladdressrepresentation 5.Memorymanagement 6.Internallayering .1.Socketlayer .1.1.Socketstate .1.2.Socketdataqueues .1.3.Socketconnectionqueueing .2.Protocollayer(s) .3.Network-interfacelayer .3.1.UNIBUSinterfaces 7.Socket/protocolinterface 8.Protocol/protocolinterface .1.proutput .2.prinput .3.prctlinput .4.prctloutput 9.Protocol/network-interfaceinterface .1.Packettransmission .2.Packetreception 10.Gatewaysandroutingissues .1.Routingtables .2.Routingtableinterface .3.Userlevelroutingpolicies 11.Rawsockets .1.Controlblocks .2.Inputprocessing .3.Outputprocessing 12.Bufferingandcongestioncontrol .1.Memorymanagement .2.Protocolbufferingpolicies .3.Queuelimiting .4.Packetforwarding 13.Outofbanddata 14.Trailerprotocols Acknowledgements References CSRGTR/6 Leffler,et.al.

NetworkingImplementation-1- Introduction 1.Introduction Thisreportdescribestheinternalstructureoffacilitiesaddedtothe4.2BSDversionofthe UNIXoperatingsystemfortheVAX.Thesystemfacilitiesprovideauniformuserinterfaceto networkingwithinUNIX.Inaddition,theimplementationintroducesastructurefornetwork communicationswhichmaybeusedbysystemimplementorsinaddingnewnetworkingfacilities. Theinternalstructureisnotvisibletotheuser,ratheritisintendedtoaidimplementorsofcommunicationprotocolsandnetworkservicesbyprovidingaframeworkwhichpromotescodesharing andminimizesimplementationeffort. ThereaderisexpectedtobefamiliarwiththeCprogramminglanguageandsysteminterface,asdescribedinthe4.2BSDSystemManual[Joy82a].Basicunderstandingofnetworkcommunicationconceptsisassumed;whererequiredanyadditionalideasareintroduced. Theremainderofthisdocumentprovidesadescriptionofthesysteminternals,avoiding, whenpossible,thoseportionswhichareutilizedonlybytheinterprocesscommunicationfacilities. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-2- Overview 2.Overview IfweconsidertheInternationalStandardsOrganization’s(ISO)OpenSystemInterconnection(OSI)modelofnetworkcommunication[ISO81][Zimmermann80],thenetworkingfacilities describedherecorrespondtoaportionofthesessionlayer(layer3)andallofthetransportand networklayers(layers2and1,respectively). Thenetworklayerprovidespossiblyimperfectdatatransportserviceswithminimaladdressingstructure.Addressingatthislevelisnormallyhosttohost,withimplicitorexplicitrouting optionallysupportedbythecommunicatingagents. Atthetransportlayerthenotionsofreliabletransfer,datasequencing,flowcontrol,andserviceaddressingarenormallyincluded.Reliabilityisusuallymanagedbyexplicitacknowledgementofdatadelivered.Failuretoacknowledgeatransferresultsinretransmissionofthedata. Sequencingmaybehandledbytaggingeachmessagehandedtothenetworklayerbyasequence numberandmaintainingstateattheendpointsofcommunicationtoutilizereceivedsequence numbersinreorderingdatawhicharrivesoutoforder. Thesessionlayerfacilitiesmayprovideformsofaddressingwhicharemappedintoformats requiredbythetransportlayer,serviceauthenticationandclientauthentication,etc.Varioussystemsalsoprovideservicessuchasdataencryptionandaddressandprotocoltranslation. Thefollowingsectionsbeginbydescribingsomeofthecommondatastructuresandutility routines,thenexaminetheinternallayering.Thecontentsofeachlayeranditsinterfaceareconsidered.Certainoftheinterfacesareprotocolimplementationspecific.Forthesecasesexamples havebeendrawnfromtheInternet[Cerf78]protocolfamily.Latersectionscoverroutingissues, thedesignoftherawsocketinterfaceandothermiscellaneoustopics. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-3- Goals 3.Goals Thenetworkingsystemwasdesignedwiththegoalofsupportingmultipleprotocolfamilies andaddressingstyles.Thisrequiredinformationtobe‘‘hidden’’incommondatastructureswhich couldbemanipulatedbyallthepiecesofthesystem,butwhichrequiredinterpretationonlyby theprotocolswhich‘‘controlled’’it.Thesystemdescribedhereattemptstominimizetheuseof shareddatastructurestothosekeptbyasuiteofprotocols(aprotocolfamily),andthoseusedfor rendezvousbetween‘‘synchronous’’and‘‘asynchronous’’portionsofthesystem(e.g.queuesofdata packetsarefilledatinterrupttimeandemptiedbasedonuserrequests). Amajorgoalofthesystemwastoprovideaframeworkwithinwhichnewprotocolsand hardwarecouldbeeasilybesupported.Tothisend,agreatdealofefforthasbeenextendedto createutilityroutineswhichhidemanyofthemorecomplexand/orhardwaredependentchoresof networking.Latersectionsdescribetheutilityroutinesandtheunderlyingdatastructuresthey manipulate. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-4- Addressrepresentation 4.Internaladdressrepresentation Commontoallportionsofthesystemaretwodatastructures.Thesestructuresareusedto representaddressesandvariousdataobjects.Addresses,internallyaredescribedbythesockaddr structure, structsockaddr{ shortsafamily;/*dataformatidentifier*/ charsadata[14];/*address*/ }; Alladdressesbelongtooneormoreaddressfamilieswhichdefinetheirformatandinterpretation. Thesafamilyfieldindicateswhichaddressfamilytheaddressbelongsto,thesadatafieldcontainstheactualdatavalue.Thesizeofthedatafield,14bytes,wasselectedbasedonastudyof currentaddressformats*. *Laterversionsofthesystemsupportvariablelengthaddresses. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-5- Memorymanagement 5.Memorymanagement Asinglemechanismisusedfordatastorage:memorybuffers,ormbuf’s.Anmbufisastructureoftheform: structmbuf{ structmbuf*mnext;/*nextbufferinchain*/ ulongmoff;/*offsetofdata*/ shortmlen;/*amountofdatainthismbuf*/ shortmtype;/*mbuftype(accounting)*/ ucharmdat[MLEN];/*datastorage*/ structmbuf*mact;/*linkinhigher-levelmbuflist*/ }; Themnextfieldisusedtochainmbufstogetheronlinkedlists,whilethemactfieldallowslists ofmbufstobeaccumulated.Byconvention,thembufscommontoasingleobject(forexample,a packet)arechainedtogetherwiththemnextfield,whilegroupsofobjectsarelinkedviathe mactfield(possiblywheninaqueue). Eachmbufhasasmalldataareaforstoringinformation,mdat.Themlenfieldindicates theamountofdata,whilethemofffieldisanoffsettothebeginningofthedatafromthebaseof thembuf.Thus,forexample,themacromtod,whichconvertsapointertoanmbuftoapointer tothedatastoredinthembuf,hastheform #definemtod(x,t)((t)((int)(x)+(x)->moff)) (notethetparameter,aCtypecast,isusedtocasttheresultantpointerforproperassignment). Inadditiontostoringdatadirectlyinthembuf’sdataarea,dataofpagesizemaybealsobe storedinaseparateareaofmemory.Thembufutilityroutinesmaintainapoolofpagesforthis purposeandmanipulateaprivatepagemapforsuchpages.Thevirtualaddressesofthesedata pagesprecedethoseofmbufs,sowhenpagesofdataareseparatedfromanmbuf,thembufdata offsetisanegativevalue.Anarrayofreferencecountsonpagesisalsomaintainedsothatcopies ofpagesmaybemadewithoutcoretocorecopying(copiesarecreatedsimplybyduplicatingthe relevantpagetableentriesinthedatapagemapandincrementingtheassociatedreferencecounts forthepages).Separatedatapagesarecurrentlyusedonlywhencopyingdatafromauserprocessintothekernel,andwhenbringingdatainatthehardwarelevel.Routineswhichmanipulate mbufsarenotnormallyawareifdataisstoreddirectlyinthembufdataarray,orifitiskeptin separatepages. Thefollowingutilityroutinesareavailableformanipulatingmbufchains: m=mcopy(m0,off,len); Themcopyroutinecreateacopyofall,orpart,ofalistofthembufsinm0.Lenbytesof data,startingoffbytesfromthefrontofthechain,arecopied.Wherepossible,reference countsonpagesareusedinsteadofcoretocorecopies.Theoriginalmbufchainmusthave atleastoff+lenbytesofdata.IflenisspecifiedasMCOPYALL,allthedatapresent,offsetasbefore,iscopied. mcat(m,n); Thembufchain,n,isappendedtotheendofm.Wherepossible,compactionisperformed. madj(m,diff); Thembufchain,misadjustedinsizebydiffbytes.Ifdiffisnon-negative,diffbytesare shavedoffthefrontofthembufchain.Ifdiffisnegative,thealterationisperformedfrom backtofront.Nospaceisreclaimedinthisoperation,alterationsareaccomplishedby changingthemlenandmofffieldsofmbufs. m=mpullup(m0,size); Afterasuccessfulcalltompullup,thembufattheheadofthereturnedlist,m,isguaranteedtohaveatleastsizebytesofdataincontiguousmemory(allowingaccessviaapointer, obtainedusingthemtodmacro).Iftheoriginaldatawaslessthansizebyteslong,lenwas CSRGTR/6 Leffler,et.al.

NetworkingImplementation-6- Memorymanagement greaterthanthesizeofanmbufdataarea(112bytes),orrequiredresourceswereunavailable,mis0andtheoriginalmbufchainisdeallocated. Thisroutineisparticularlyusefulwhenverifyingpacketheaderlengthsonreception.For example,ifapacketisreceivedandonly8ofthenecessary16bytesrequiredforavalid packetheaderarepresentattheheadofthelistofmbufsrepresentingthepacket,the remaining8bytesmaybe‘‘pulledup’’withasinglempullupcall.Ifthecallfailsthe invalidpacketwillhavebeendiscarded. Byinsuringmbufsalwaysresideon128byteboundariesitispossibletoalwayslocatethe mbufassociatedwithadataareabymaskingoffthelowbitsofthevirtualaddress.Thisallows modulestostoredatastructuresinmbufsandpassthemaroundwithoutconcernforlocatingthe originalmbufwhenitcomestimetofreethestructure.Thedtommacroisusedtoconverta pointerintoanmbuf’sdataareatoapointertothembuf, #definedtom(x)((structmbuf*)((int)x&˜ (MSIZE-1))) Mbufsareusedfordynamicallyallocateddatastructuressuchassockets,aswellasmemory allocatedforpackets.Statisticsaremaintainedonmbufusageandcanbeviewedbyusersusing thenetstat(1)program. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-7- Internallayering 6.Internallayering Theinternalstructureofthenetworksystemisdividedintothreelayers.Theselayerscorrespondtotheservicesprovidedbythesocketabstraction,thoseprovidedbythecommunication protocols,andthoseprovidedbythehardwareinterfaces.Thecommunicationprotocolsarenormallylayeredintotwoormoreindividualcooperatinglayers,thoughtheyarecollectivelyviewed inthesystemasonelayerprovidingservicessupportiveoftheappropriatesocketabstraction. Thefollowingsectionsdescribethepropertiesofeachlayerinthesystemandtheinterfaces eachmustconformto. 6.1.Socketlayer Thesocketlayerdealswiththeinterprocesscommunicationsfacilitiesprovidedbythesystem.Asocketisabidirectionalendpointofcommunicationwhichis‘‘typed’’bythesemanticsof communicationitsupports.Thesystemcallsdescribedinthe4.2BSDSystemManualareusedto manipulatesockets. Asocketconsistsofthefollowingdatastructure: structsocket{ shortsotype;/*generictype*/ shortsooptions;/*fromsocketcall*/ shortsolinger;/*timetolingerwhileclosing*/ shortsostate;/*internalstateflags*/ caddrtsopcb;/*protocolcontrolblock*/ structprotosw*soproto;/*protocolhandle*/ structsocket*sohead;/*backpointertoacceptsocket*/ structsocket*soq0;/*queueofpartialconnections*/ shortsoq0len;/*partialsonsoq0*/ structsocket*soq;/*queueofincomingconnections*/ shortsoqlen;/*numberofconnectionsonsoq*/ shortsoqlimit;/*maxnumberqueuedconnections*/ structsockbufsosnd;/*sendqueue*/ structsockbufsorcv;/*receivequeue*/ shortsotimeo;/*connectiontimeout*/ ushortsoerror;/*erroraffectingconnection*/ shortsooobmark;/*charstooobmark*/ shortsopgrp;/*pgrpforsignals*/ }; Eachsocketcontainstwodataqueues,sorcvandsosnd,andapointertoroutineswhich providesupportingservices.Thetypeofthesocket,sotypeisdefinedatsocketcreationtimeand usedinselectingthoseserviceswhichareappropriatetosupportit.Thesupportingprotocolis selectedatsocketcreationtimeandrecordedinthesocketdatastructureforlateruse.Protocols aredefinedbyatableofprocedures,theprotoswstructure,whichwillbedescribedindetaillater. Apointertoaprotocolspecificdatastructure,the‘‘protocolcontrolblock’’isalsopresentinthe socketstructure.Protocolscontrolthisdatastructureanditnormallyincludesabackpointerto theparentsocketstructure(s)toalloweasylookupwhenreturninginformationtoauser(for example,placinganerrornumberinthesoerrorfield).Theotherentriesinthesocketstructure areusedinqueueingconnectionrequests,validatinguserrequests,storingsocketcharacteristics (e.g.optionssuppliedatthetimeasocketiscreated),andmaintainingasocket’sstate. Processes‘‘rendezvousatasocket’’inmanyinstances.Forinstance,whenaprocesswishes toextractdatafromasocket’sreceivequeueanditisempty,orlackssufficientdatatosatisfythe request,theprocessblocks,supplyingtheaddressofthereceivequeueasan‘‘waitchannel’tobe usedinnotification.Whendataarrivesfortheprocessandisplacedinthesocket’squeue,the blockedprocessisidentifiedbythefactitiswaiting‘‘onthequeue’’. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-8- Internallayering 6.1.1.Socketstate Asocket’sstateisdefinedfromthefollowing: #defineSSNOFDREF0x001/*nofiletablerefanymore*/ #defineSSISCONNECTED0x002/*socketconnectedtoapeer*/ #defineSSISCONNECTING0x004/*inprocessofconnectingtopeer*/ #defineSSISDISCONNECTING0x008/*inprocessofdisconnecting*/ #defineSSCANTSENDMORE0x010/*can’tsendmoredatatopeer*/ #defineSSCANTRCVMORE0x020/*can’treceivemoredatafrompeer*/ #defineSSCONNAWAITING0x040/*connectionsawaitingacceptance*/ #defineSSRCVATMARK0x080/*atmarkoninput*/ #defineSSPRIV0x100/*privileged*/ #defineSSNBIO0x200/*non-blockingops*/ #defineSSASYNC0x400/*asynci/onotify*/ Thestateofasocketismanipulatedbothbytheprotocolsandtheuser(throughsystem calls).Whenasocketiscreatedthestateisdefinedbasedonthetypeofinput/outputtheuser wishestoperform.‘‘Non-blocking’’I/Oimpliesaprocessshouldneverbeblockedtoawait resources.Instead,anycallwhichwouldblockreturnsprematurelywiththeerrorEWOULD-BLOCK(theservicerequestmaybepartiallyfulfilled,e.g.arequestformoredatathanispre-sent). Ifaprocessrequested‘‘asynchronous’’notificationofeventsrelatedtothesockettheSIGIO signalispostedtotheprocess.Aneventisachangeinthesocket’sstate,examplesofsuchoccurancesare:spacebecomingavailableinthesendqueue,newdataavailableinthereceivequeue, connectionestablishmentordisestablishment,etc. Asocketmaybemarked‘‘priviledged’’ifitwascreatedbythesuper-user.Onlypriviledged socketsmaysendbroadcastpackets,orbindaddressesinpriviledgedportionsofanaddressspace. 6.1.2.Socketdataqueues Asocket’sdataqueuecontainsapointertothedatastoredinthequeueandotherentries relatedtothemanagementofthedata.Thefollowingstructuredefinesadataqueue: structsockbuf{ shortsbcc;/*actualcharsinbuffer*/ shortsbhiwat;/*maxactualcharcount*/ shortsbmbcnt;/*charsofmbufsused*/ shortsbmbmax;/*maxcharsofmbufstouse*/ shortsblowat;/*lowwatermark*/ shortsbtimeo;/*timeout*/ structmbuf*sbmb;/*thembufchain*/ structproc*sbsel;/*processselectingread/write*/ shortsbflags;/*flags,seebelow*/ }; Dataisstoredinaqueueasachainofmbufs.Theactualcountofcharactersaswellashigh andlowwatermarksareusedbytheprotocolsincontrollingtheflowofdata.Thesocketroutinescooperateinimplementingtheflowcontrolpolicybyblockingaprocesswhenitrequeststo senddataandthehighwatermarkhasbeenreached,orwhenitrequeststoreceivedataandless thanthelowwatermarkispresent(assumingnon-blockingI/Ohasnotbeenspecified). Whenasocketiscreated,thesupportingprotocol‘‘reserves’’spaceforthesendandreceive queuesofthesocket.Theactualstorageassociatedwithasocketqueuemayfluctuateduringa socket’slifetime,butisassumedthisreservationwillalwaysallowaprotocoltoacquireenough memorytosatisfythehighwatermarks. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-9- Internallayering Thetimeoutandselectvaluesaremanipulatedbythesocketroutinesinimplementingvariousportionsoftheinterprocesscommunicationsfacilitiesandwillnotbedescribedhere. Asocketqueuehasanumberofflagsusedinsynchronizingaccesstothedataandinacquiringresources; #defineSBLOCK0x01/*lockondataqueue(sorcvonly)*/ #defineSBWANT0x02/*someoneiswaitingtolock*/ #defineSBWAIT0x04/*someoneiswaitingfordata/space*/ #defineSBSEL0x08/*bufferisselected*/ #defineSBCOLL0x10/*collisionselecting*/ Thelasttwoflagsaremanipulatedbythesysteminimplementingtheselectmechanism. 6.1.3.Socketconnectionqueueing Indealingwithconnectionorientedsockets(e.g.SOCKSTREAM)thetwosidesareconsidereddistinct.Onesideistermedactive,andgeneratesconnectionrequests.Theothersideis calledpassiveandacceptsconnectionrequests. Fromthepassiveside,asocketiscreatedwiththeoptionSOACCEPTCONNspecified,creatingtwoqueuesofsockets:soq0forconnectionsinprogressandsoqforconnectionsalready madeandawaitinguseracceptance.Asaprotocolispreparingincomingconnections,itcreatesa socketstructurequeuedonsoq0bycallingtheroutinesonewconn().Whentheconnectionis established,thesocketstructureisthentransferedtosoq,makingitavailableforanaccept. IfanSOACCEPTCONNsocketisclosedwithsocketsoneithersoq0orsoq,thesesockets aredropped. 6.2.Protocollayer(s) Protocolsaredescribedbyasetofentrypointsandcertainsocketvisiblecharacteristics, someofwhichareusedindecidingwhichsockettype(s)theymaysupport. Anentryinthe‘‘protocolswitch’’tableexistsforeachprotocolmoduleconfiguredintothe system.Ithasthefollowingform: structprotosw{ shortprtype;/*sockettypeusedfor*/ shortprfamily;/*protocolfamily*/ shortprprotocol;/*protocolnumber*/ shortprflags;/*socketvisibleattributes*/ /*protocol-protocolhooks*/ int(*prinput)();/*inputtoprotocol(frombelow)*/ int(*proutput)();/*outputtoprotocol(fromabove)*/ int(*prctlinput)();/*controlinput(frombelow)*/ int(*prctloutput)();/*controloutput(fromabove)*/ /*user-protocolhook*/ int(*prusrreq)();/*userrequest*/ /*utilityhooks*/ int(*prinit)();/*initializationroutine*/ int(*prfasttimo)();/*fasttimeout(200ms)*/ int(*prslowtimo)();/*slowtimeout(500ms)*/ int(*prdrain)();/*flushanyexcessspacepossible*/ }; Aprotocoliscalledthroughtheprinitentrybeforeanyother.Thereafteritiscalledevery 200millisecondsthroughtheprfasttimoentryandevery500millisecondsthroughthe prslowtimofortimerbasedactions.Thesystemwillcalltheprdrainentryifitislowonspace andthisshouldthrowawayanynon-criticaldata. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-10- Internallayering Protocolspassdatabetweenthemselvesaschainsofmbufsusingtheprinputandproutput routines.Prinputpassesdataup(towardstheuser)andproutputpassesitdown(towardsthe network);controlinformationpassesupanddownonprctlinputandprctloutput.Theprotocol isresponsibleforthespaceoccupiedbyanytheargumentstotheseentriesandmustdisposeofit. Thepruserreqroutineinterfacesprotocolstothesocketcodeandisdescribedbelow. Theprflagsfieldisconstructedfromthefollowingvalues: #definePRATOMIC0x01/*exchangeatomicmessagesonly*/ #definePRADDR0x02/*addressesgivenwithmessages*/ #definePRCONNREQUIRED0x04/*connectionrequiredbyprotocol*/ #definePRWANTRCVD0x08/*wantPRURCVDcalls*/ #definePRRIGHTS0x10/*passescapabilities*/ Protocolswhichareconnection-basedspecifythePRCONNREQUIREDflagsothatthesocket routineswillneverattempttosenddatabeforeaconnectionhasbeenestablished.Ifthe PRWANTRCVDflagisset,thesocketroutineswillnotfiytheprotocolwhentheuserhas removeddatafromthesocket’sreceivequeue.Thisallowstheprotocoltoimplementacknowledgementonuserreceipt,andalsoupdatewindowinginformationbasedontheamountofspace availableinthereceivequeue.ThePRADDRfieldindicatesanydataplacedinthesocket’s receivequeuewillbeprecededbytheaddressofthesender.ThePRATOMICflagspecifieseach userrequesttosenddatamustbeperformedinasingleprotocolsendrequest;itistheprotocol’s responsibilitytomaintainrecordboundariesondatatobesent.ThePRRIGHTSflagindicates theprotocolsupportsthepassingofcapabilities;thisiscurrentlyusedonlytheprotocolsinthe UNIXprotocolfamily. Whenasocketiscreated,thesocketroutinesscantheprotocoltablelookingforanappropriateprotocoltosupportthetypeofsocketbeingcreated.Theprtypefieldcontainsoneofthe possiblesockettypes(e.g.SOCKSTREAM),whiletheprfamilyfieldindicateswhichprotocol familytheprotocolbelongsto.Theprprotocolfieldcontainstheprotocolnumberoftheprotocol,normallyawellknownvalue. 6.3.Network-interfacelayer Eachnetwork-interfaceconfiguredintoasystemdefinesapaththroughwhichpacketsmay besentandreceived.Normallyahardwaredeviceisassociatedwiththisinterface,thoughthere isnorequirementforthis(forexample,allsystemshaveasoftware‘‘loopback’’interfaceusedfor debuggingandperformanceanalysis).Inadditiontomanipulatingthehardwaredevice,aninterfacemoduleisresponsibleforencapsulationanddeencapsulationofanylowlevelheaderinformationrequiredtodeliveramessagetoit’sdestination.Theselectionofwhichinterfacetousein deliveringpacketsisaroutingdecisioncarriedoutatahigherlevelthanthenetwork-interface layer.Eachinterfacenormallyidentifiesitselfatboottimetotheroutingmodulesothatitmay beselectedforpacketdelivery. Aninterfaceisdefinedbythefollowingstructure, CSRGTR/6 Leffler,et.al.

NetworkingImplementation-11- Internallayering structifnet{ char*ifname;/*name,e.g.‘‘en’’or‘‘lo’’*/ shortifunit;/*sub-unitforlowerleveldriver*/ shortifmtu;/*maximumtransmissionunit*/ intifnet;/*networknumberofinterface*/ shortifflags;/*up/down,broadcast,etc.*/ shortiftimer;/*time’tilifwatchdogcalled*/ intifhost[2];/*localnethostnumber*/ structsockaddrifaddr;/*addressofinterface*/ union{ structsockaddrifubroadaddr; structsockaddrifudstaddr; }ififu; structifqueueifsnd;/*outputqueue*/ int(*ifinit)();/*initroutine*/ int(*ifoutput)();/*outputroutine*/ int(*ifioctl)();/*ioctlroutine*/ int(*ifreset)();/*busresetroutine*/ int(*ifwatchdog)();/*timerroutine*/ intifipackets;/*packetsreceivedoninterface*/ intifierrors;/*inputerrorsoninterface*/ intifopackets;/*packetssentoninterface*/ intifoerrors;/*outputerrorsoninterface*/ intifcollisions;/*collisionsoncsmainterfaces*/ structifnet*ifnext; }; Eachinterfacehasasendqueueandroutinesusedforinitialization,ifinit,andoutput, ifoutput.Iftheinterfaceresidesonasystembus,theroutineifresetwillbecalledafterabus resethasbeenperformed.Aninterfacemayalsospecifyatimerroutine,ifwatchdog,which shouldbecalledeveryiftimerseconds(ifnon-zero). Thestateofaninterfaceandcertaincharacteristicsarestoredintheifflagsfield.Thefollowingvaluesarepossible: #defineIFFUP0x1/*interfaceisup*/ #defineIFFBROADCAST0x2/*broadcastaddressvalid*/ #defineIFFDEBUG0x4/*turnondebugging*/ #defineIFFROUTE0x8/*routingentryinstalled*/ #defineIFFPOINTOPOINT0x10/*interfaceispoint-to-pointlink*/ #defineIFFNOTRAILERS0x20/*avoiduseoftrailers*/ #defineIFFRUNNING0x40/*resourcesallocated*/ #defineIFFNOARP0x80/*noaddressresolutionprotocol*/ Iftheinterfaceisconnectedtoanetworkwhichsupportstransmissionofbroadcastpackets,the IFFBROADCASTflagwillbesetandtheifbroadaddrfieldwillcontaintheaddresstobeused insendingoracceptingabroadcastpacket.Iftheinterfaceisassociatedwithapointtopoint hardwarelink(forexample,aDECDMR-11),theIFFPOINTOPOINTflagwillbesetand ifdstaddrwillcontaintheaddressofthehostontheothersideoftheconnection.These addressesandthelocaladdressoftheinterface,ifaddr,areusedinfilteringincomingpackets. TheinterfacesetsIFFRUNNINGafterithasallocatedsystemresourcesandpostedaninitial readonthedeviceitmanages.Thisstatebitisusedtoavoidmultipleallocationrequestswhen aninterface’saddressischanged.TheIFFNOTRAILERSflagindicatestheinterfaceshould refrainfromusingatrailerencapsulationonoutgoingpackets;trailerprotocolsaredescribedin section14.TheIFFNOARPflagindicatestheinterfaceshouldnotusean‘‘addressresolution protocol’’inmappinginternetworkaddressestolocalnetworkaddresses. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-12- Internallayering Theinformationstoredinanifnetstructureforpointtopointcommunicationdevicesisnot currentlyusedbythesysteminternally.Rather,itisusedbytheuserlevelroutingprocessin determininghostnetworkconnectionsandininitiallydevisingroutes(refertochapter10formore information). Variousstatisticsarealsostoredintheinterfacestructure.Thesemaybeviewedbyusers usingthenetstat(1)program. TheinterfaceaddressandflagsmaybesetwiththeSIOCSIFADDRandSIOCSIFFLAGS ioctls.SIOCSIFADDRisusedtoinitiallydefineeachinterface’saddress;SIOGSIFFLAGScanbe usedtomarkaninterfacedownandperformsite-specificconfiguration. 6.3.1.UNIBUSinterfaces AllhardwarerelatedinterfacescurrentlyresideontheUNIBUS.Consequentlyacommon setofutilityroutinesfordealingwiththeUNIBUShasbeendeveloped.EachUNIBUSinterface utilizesastructureofthefollowingform: structifuba{ shortifuuban;/*ubanumber*/ shortifuhlen;/*localnetheaderlength*/ structubaregs*ifuuba;/*ubaregs,invm*/ structifrw{ caddrtifrwaddr;/*virtaddrofheader*/ intifrwbdp;/*unibusbdp*/ intifrwinfo;/*valuefromubaalloc*/ intifrwproto;/*mapregisterprototype*/ structpte*ifrwmr;/*baseofmapregisters*/ }ifur,ifuw; structpteifuwmap[IFMAXNUBAMR];/*basepagesforoutput*/ shortifuxswapd;/*maskofclustersswapped*/ shortifuflags;/*usedduringuballoc’s*/ structmbuf*ifuxtofree;/*pagesbeingdma’dout*/ }; TheifubastructuredescribesUNIBUSresourcesheldbyaninterface.IFNUBAMRmap registersareheldfordatagramdata,startingatifrmr.UNIBUSmapregisterifrmr[−1]maps thelocalnetworkheaderendingonapageboundary.UNIBUSdatapathsarereservedforread andforwrite,givenbyifrbdp.Theprototypeofthemapregistersforreadandforwriteissaved inifrproto. Whenwritetransfersarenotfullpagesonpageboundariesthedataisjustcopiedintothe pagesmappedontheUNIBUSandthetransferisstarted.Ifawritetransferisofa(1024byte) pagesizeandonapageboundary,UNIBUSpagetableentriesareswappedtoreferencethepages, andthentheinitialpagesareremappedfromifuwmapwhenthetransfercompletes. Whenreadtransfersgivewholepagesofdatatobeinput,pageframesareallocatedfroma networkpagelistandtradedwiththepagesalreadycontainingthedata,mappingtheallocated pagestoreplacetheinputpagesforthenextUNIBUSdatainput. Thefollowingutilityroutinesareavailableforuseinwritingnetworkinterfacedrivers,all usetheifubastructuredescribedabove. ifubainit(ifu,uban,hlen,nmr); ifubainitallocatesresourcesonUNIBUSadaptorubanandstorestheresultantinformation intheifubastructurepointedtobyifu.ItiscalledonlyatboottimeorafteraUNIBUS reset.Twodatapaths(bufferedorunbuffered,dependingontheifuflagsfield)areallocated,oneforreadingandoneforwriting.Thenmrparameterindicatesthenumberof UNIBUSmappingregistersrequiredtomapamaximalsizedpacketontotheUNIBUS, whilehlenspecifiesthesizeofalocalnetworkheader,ifany,whichshouldbemapped CSRGTR/6 Leffler,et.al.

NetworkingImplementation-13- Internallayering separatelyfromthedata(seethedescriptionoftrailerprotocolsinchapter14).Sufficient UNIBUSmappingregistersandpagesofmemoryareallocatedtoinitializetheinputdata pathforaninitialread.Fortheoutputdatapath,mappingregistersandpagesofmemory arealsoallocatedandmappedontotheUNIBUS.Thepagesassociatedwiththeoutput datapathareheldinreserveintheeventawriterequirescopyingnon-page-aligneddata (seeifwubaputbelow).Ififubainitiscalledwithresourcesalreadyallocated,theywillbe usedinsteadofallocatingnewones(thisnormallyoccursafteraUNIBUSreset).A1is returnedwhenallocationandinitializationissuccessful,0otherwise. m=ifrubaget(ifu,totlen,off0); ifrubagetpullsreaddataoffaninterface.totlenspecifiesthelengthofdatatobeobtained, notcountingthelocalnetworkheader.Ifoff0isnon-zero,itindicatesabyteoffsettoa trailinglocalnetworkheaderwhichshouldbecopiedintoaseparatembufandprependedto thefrontoftheresultantmbufchain.Whenpagesizedunitsofdataarepresentandare page-aligned,thepreviouslymappeddatapagesareremappedintothembufsandswapped withfreshpages;thusavoidinganycopying.A0returnvalueindicatesafailuretoallocate resources. ifwubaput(ifu,m); ifwubaputmapsachainofmbufsontoanetworkinterfaceinpreparationforoutput.The chainincludesanylocalnetworkheader,whichiscopiedsothatitresidesinthemapped andalignedI/Ospace.Anyothermbufswhichcontainednonpagesizeddataportionsare alsocopiedtotheI/Ospace.Pagesmappedfromapreviousoutputoperation(nolonger needed)areunmappedandreturnedtothenetworkpagepool. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-14-Socket/protocolinterface 7.Socket/protocolinterface Theinterfacebetweenthesocketroutinesandthecommunicationprotocolsisthroughthe prusrreqroutinedefinedintheprotocolswitchtable.Thefollowingrequeststoaprotocolmodulearepossible: #definePRUATTACH0/*attachprotocol*/ #definePRUDETACH1/*detachprotocol*/ #definePRUBIND2/*bindsockettoaddress*/ #definePRULISTEN3/*listenforconnection*/ #definePRUCONNECT4/*establishconnectiontopeer*/ #definePRUACCEPT5/*acceptconnectionfrompeer*/ #definePRUDISCONNECT6/*disconnectfrompeer*/ #definePRUSHUTDOWN7/*won’tsendanymoredata*/ #definePRURCVD8/*havetakendata;moreroomnow*/ #definePRUSEND9/*sendthisdata*/ #definePRUABORT10/*abort(fastDISCONNECT,DETATCH)*/ #definePRUCONTROL11/*controloperationsonprotocol*/ #definePRUSENSE12/*returnstatusintom*/ #definePRURCVOOB13/*retrieveoutofbanddata*/ #definePRUSENDOOB14/*sendoutofbanddata*/ #definePRUSOCKADDR15/*fetchsocket’saddress*/ #definePRUPEERADDR16/*fetchpeer’saddress*/ #definePRUCONNECT217/*connecttwosockets*/ /*beginforprotocolsinternaluse*/ #definePRUFASTTIMO18/*200mstimeout*/ #definePRUSLOWTIMO19/*500mstimeout*/ #definePRUPROTORCV20/*receivefrombelow*/ #definePRUPROTOSEND21/*sendtobelow*/ Acallontheuserrequestroutineisoftheform, error=(*protosw[].prusrreq)(up,req,m,addr,rights); interror;structsocket*up;intreq;structmbuf*m,*rights;caddrtaddr; Thembufchain,m,andtheaddressareoptionalparameters.Therightsparameterisanoptional pointertoanmbufchaincontaininguserspecifiedcapabilities(seethesendmsgandrecvmsgsystemcalls).Theprotocolisresponsiblefordisposalofbothmbufchains.Anon-zeroreturnvalue givesaUNIXerrornumberwhichshouldbepassedtohigherlevelsoftware.Thefollowingparagraphsdescribeeachoftherequestspossible. PRUATTACH Whenaprotocolisboundtoasocket(withthesocketsystemcall)theprotocolmoduleis calledwiththisrequest.Itistheresponsibilityoftheprotocolmoduletoallocateany resourcesnecessary.The‘‘attach’’requestwillalwaysprecedeanyoftheotherrequests,and shouldnotoccurmorethanonce. PRUDETACH Thisistheantithesisoftheattachrequest,andisusedatthetimeasocketisdeleted.The protocolmodulemaydeallocateanyresourcesassignedtothesocket. PRUBIND Whenasocketisinitiallycreatedithasnoaddressboundtoit.Thisrequestindicatesan addressshouldbeboundtoanexistingsocket.Theprotocolmodulemustverifythe requestedaddressisvalidandavailableforuse. PRULISTEN The‘‘listen’’requestindicatestheuserwishestolistenforincomingconnectionrequestson theassociatedsocket.Theprotocolmoduleshouldperformanystatechangesneededto carryoutthisrequest(ifpossible).A‘‘listen’’requestalwaysprecedesarequesttoaccepta CSRGTR/6 Leffler,et.al.

NetworkingImplementation-15-Socket/protocolinterface connection. PRUCONNECT The‘‘connect’’requestindicatestheuserwantstoaestablishanassociation.Theaddr parametersupplieddescribesthepeertobeconnectedto.Theeffectofaconnectrequest mayvarydependingontheprotocol.Virtualcircuitprotocols,suchasTCP[Postel80b],use thisrequesttoinitiateestablishmentofaTCPconnection.Datagramprotocols,suchas UDP[Postel79],simplyrecordthepeer’saddressinaprivatedatastructureanduseitto tagalloutgoingpackets.Therearenorestrictionsonhowmanytimesaconnectrequest maybeusedafteranattach.Ifaprotocolsupportsthenotionofmulti-casting,itispossible tousemultipleconnectstoestablishamulti-castgroup.Alternatively,anassociationmay bebrokenbyaPRUDISCONNECTrequest,andanewassociationcreatedwithasubsequentconnectrequest;allwithoutdestroyingandcreatinganewsocket. PRUACCEPT FollowingasuccessfulPRULISTENrequestandthearrivalofoneormoreconnections,this requestismadetoindicatetheuserhasacceptedthefirstconnectiononthequeueofpendingconnections.Theprotocolmoduleshouldfillinthesuppliedaddressbufferwiththe addressoftheconnectedparty. PRUDISCONNECT EliminateanassociationcreatedwithaPRUCONNECTrequest. PRUSHUTDOWN Thiscallisusedtoindicatenomoredatawillbesentand/orreceived(theaddrparameter indicatesthedirectionoftheshutdown,asencodedinthesoshutdownsystemcall).The protocolmay,atitsdiscretion,deallocateanydatastructuresrelatedtotheshutdown. PRURCVD Thisrequestismadeonlyiftheprotocolentryintheprotocolswitchtableincludesthe PRWANTRCVDflag.Whenauserremovesdatafromthereceivequeuethisrequestwill besenttotheprotocolmodule.Itmaybeusedtotriggeracknowledgements,refreshwindowinginformation,initiatedatatransfer,etc. PRUSEND EachuserrequesttosenddataistranslatedintooneormorePRUSENDrequests(aprotocolmayindicateasingleusersendrequestmustbetranslatedintoasinglePRUSEND requestbyspecifyingthePRATOMICflaginitsprotocoldescription).Thedatatobesent ispresentedtotheprotocolasalistofmbufsandanaddressis,optionally,suppliedinthe addrparameter.Theprotocolisresponsibleforpreservingthedatainthesocket’ssend queueifitisnotabletosenditimmediately,orifitmayneeditatsomelatertime(e.g.for retransmission). PRUABORT Thisrequestindicatesanabnormalterminationofservice.Theprotocolshoulddeleteany existingassociation(s). PRUCONTROL The‘‘control’’requestisgeneratedwhenauserperformsaUNIXioctlsystemcallona socket(andtheioctlisnotinterceptedbythesocketroutines).Itallowsprotocol-specific operationstobeprovidedoutsidethescopeofthecommonsocketinterface.Theaddr parametercontainsapointertoastatickerneldataareawhererelevantinformationmaybe obtainedorreturned.Themparametercontainstheactualioctlrequestcode(notethe non-standardcallingconvention). PRUSENSE The‘‘sense’’requestisgeneratedwhentheusermakesanfstatsystemcallonasocket;it requestsstatusoftheassociatedsocket.Therecurrentlyisnocommonformatforthestatus returned.Informationwhichmightbereturnedincludesper-connectionstatistics,protocol state,resourcescurrentlyinusebytheconnection,theoptimaltransfersizefortheconnection(basedonwindowinginformationandmaximumpacketsize).Theaddrparameter CSRGTR/6 Leffler,et.al.

NetworkingImplementation-16-Socket/protocolinterface containsapointertoastatickerneldataareawherethestatusbuffershouldbeplaced. PRURCVOOB Any‘‘out-of-band’’datapresentlyavailableistobereturned.Anmbufispassedintothe protocolmoduleandtheprotocolshouldeitherplacedatainthembuforattachnewmbufs totheonesuppliedifthereisinsufficientspaceinthesinglembuf. PRUSENDOOB LikePRUSEND,butforout-of-banddata. PRUSOCKADDR Thelocaladdressofthesocketisreturned,ifanyiscurrentlyboundtotheit.Theaddress format(protocolspecific)isreturnedintheaddrparameter. PRUPEERADDR Theaddressofthepeertowhichthesocketisconnectedisreturned.Thesocketmustbein aSSISCONNECTEDstateforthisrequesttobemadetotheprotocol.Theaddressformat(protocolspecific)isreturnedintheaddrparameter. PRUCONNECT2 Theprotocolmoduleissuppliedtwosocketsandrequestedtoestablishaconnection betweenthetwowithoutbindinganyaddresses,ifpossible.Thiscallisusedinimplementingthesystemcall. Thefollowingrequestsareusedinternallybytheprotocolmodulesandarenevergenerated bythesocketroutines.Incertaininstances,theyarehandedtotheprusrreqroutinesolelyfor convenienceintracingaprotocol’soperation(e.g.PRUSLOWTIMO). PRUFASTTIMO A‘‘fasttimeout’’hasoccured.Thisrequestismadewhenatimeoutoccursintheprotocol’s prfastimoroutine.Theaddrparameterindicateswhichtimerexpired. PRUSLOWTIMO A‘‘slowtimeout’’hasoccured.Thisrequestismadewhenatimeoutoccursintheprotocol’sprslowtimoroutine.Theaddrparameterindicateswhichtimerexpired. PRUPROTORCV Thisrequestisusedintheprotocol-protocolinterface,notbytheroutines.Itrequests receptionofdatadestinedfortheprotocolandnottheuser.Noprotocolscurrentlyusethis facility. PRUPROTOSEND Thisrequestallowsaprotocoltosenddatadestinedforanotherprotocolmodule,notauser. Thedetailsofhowdataismarked‘‘addressedtoprotocol’’insteadof‘‘addressedtouser’’are lefttotheprotocolmodules.Noprotocolscurrentlyusethisfacility. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-17-Protocol/protocolinterface 8.Protocol/protocolinterface Theinterfacebetweenprotocolmodulesisthroughtheprusrreq,prinput,proutput, prctlinput,andprctloutputroutines.Thecallingconventionsforallbuttheprusrreqroutine areexpectedtobespecifictotheprotocolmodulesandarenotguaranteedtobeconsistentacross protocolfamilies.WewillexaminetheconventionsusedforsomeoftheInternetprotocolsinthis sectionasanexample. 8.1.proutput TheInternetprotocolUDPusestheconvention, error=udpoutput(inp,m); interror;structinpcb*inp;structmbuf*m; wheretheinp,‘‘internetprotocolcontrolblock’’,passedbetweenmodulesconveysperconnection stateinformation,andthembufchaincontainsthedatatobesent.UDPperformsconsistency checks,appendsitsheader,calculatesachecksum,etc.beforepassingthepacketontotheIP module: error=ipoutput(m,opt,ro,allowbroadcast); interror;structmbuf*m,*opt;structroute*ro;intallowbroadcast; ThecalltoIP’soutputroutineismorecomplicatedthanthatforUDP,asbefitstheadditionalworktheIPmodulemustdo.Themparameteristhedatatobesent,andtheoptparameterisanoptionallistofIPoptionswhichshouldbeplacedintheIPpacketheader.Thero parameterisisusedinmakingroutingdecisions(andpassingthembacktothecaller).Thefinal parameter,allowbroadcastisaflagindicatingiftheuserisallowedtotransmitabroadcastpacket. Thismaybeinconsequentialiftheunderlyinghardwaredoesnotsupportthenotionofbroadcasting. Alloutputroutinesreturn0onsuccessandaUNIXerrornumberifafailureoccuredwhich couldbeimmediatelydetected(nobufferspaceavailable,noroutetodestination,etc.). 8.2.prinput BothUDPandTCPusethefollowingcallingconvention, (void)(*protosw[].prinput)(m); structmbuf*m; Eachmbuflistpassedisasinglepackettobeprocessedbytheprotocolmodule. TheIPinputroutineisaVAXsoftwareinterruptlevelroutine,andsoisnotcalledwithany parameters.Itinsteadcommunicateswithnetworkinterfacesthroughaqueue,ipintrq,whichis identicalinstructuretothequeuesusedbythenetworkinterfacesforstoringpacketsawaiting transmission. 8.3.prctlinput Thisroutineisusedtoconvey‘‘control’’informationtoaprotocolmodule(i.e.information whichmightbepassedtotheuser,butisnotdata).Thisroutine,andtheprctloutputroutine, havenotbeenextensivelydeveloped,andthussufferfroma‘‘clumsiness’’thatcanonlybe improvedasmoredemandsareplacedonit. Thecommoncallingconventionforthisroutineis, (void)(*protosw[].prctlinput)(req,info); intreq;caddrtinfo; Thereqparameterisoneofthefollowing, CSRGTR/6 Leffler,et.al.

NetworkingImplementation-18-Protocol/protocolinterface #definePRCIFDOWN0/*interfacetransition*/ #definePRCROUTEDEAD1/*selectnewrouteifpossible*/ #definePRCQUENCH4/*somesaidtoslowdown*/ #definePRCHOSTDEAD6/*normallyfromIMP*/ #definePRCHOSTUNREACH7/*ditto*/ #definePRCUNREACHNET8/*noroutetonetwork*/ #definePRCUNREACHHOST9/*noroutetohost*/ #definePRCUNREACHPROTOCOL10/*dstsaysbadprotocol*/ #definePRCUNREACHPORT11/*badport#*/ #definePRCMSGSIZE12/*messagesizeforceddrop*/ #definePRCREDIRECTNET13/*netroutingredirect*/ #definePRCREDIRECTHOST14/*hostroutingredirect*/ #definePRCTIMXCEEDINTRANS17/*packetlifetimeexpiredintransit*/ #definePRCTIMXCEEDREASS18/*lifetimeexpiredonreassq*/ #definePRCPARAMPROB19/*headerincorrect*/ whiletheinfoparameterisa‘‘catchall’’valuewhichisrequestdependent.Manyoftherequests haveobviouslybeenderivedfromICMP(theInternetControlMessageProtocol),andfromerror messagesdefinedinthe1822host/IMPconvention[BBN78].MappingtablesexisttoconvertcontrolrequeststoUNIXerrorcodeswhicharedeliveredtoauser. 8.4.prctloutput Thisroutineisnotcurrentlyusedbyanyprotocolmodules. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-19-Protocol/network-interface 9.Protocol/network-interfaceinterface Thelowestlayerinthesetofprotocolswhichcompriseaprotocolfamilymustinterface itselftooneormorenetworkinterfacesinordertotransmitandreceivepackets.Itisassumed thatanyroutingdecisionshavebeenmadebeforehandingapackettoanetworkinterface,infact thisisabsolutelynecessaryinordertolocateanyinterfaceatall(unless,ofcourse,oneusesasingle‘‘hardwired’’interface).Therearetwocasestobeconcernedwith,transmissionofapacket, andreceiptofapacket;eachwillbeconsideredseparately. 9.1.Packettransmission Assumingaprotocolhasahandleonaninterface,ifp,a(structifnet*),ittransmitsafully formattedpacketwiththefollowingcall, error=(*ifp->ifoutput)(ifp,m,dst) interror;structifnet*ifp;structmbuf*m;structsockaddr*dst; Theoutputroutineforthenetworkinterfacetransmitsthepacketmtothedstaddress,orreturns anerrorindication(aUNIXerrornumber).Inrealitytransmissionmaynotbeimmediate,orsuccessful;normallytheoutputroutinesimplyqueuesthepacketonitssendqueueandprimesan interruptdrivenroutinetoactuallytransmitthepacket.Forunreliablemediums,suchasthe Ethernet,‘‘successful’’transmissionsimplymeansthepackethasbeenplacedonthecablewithout acollision.Ontheotherhand,an1822interfaceguaranteesproperdeliveryoranerrorindication foreachmessagetransmitted.Themodelemployedinthenetworkingsystemattachesno promisesofdeliverytothepacketshandedtoanetworkinterface,andthuscorrespondsmore closelytotheEthernet.Errorsreturnedbytheoutputroutinearenormallytrivialinnature(no bufferspace,addressformatnothandled,etc.). 9.2.Packetreception Eachprotocolfamilymusthaveoneormore‘‘lowestlevel’’protocols.Theseprotocolsdeal withinternetworkaddressingandareresponsibleforthedeliveryofincomingpacketstothe properprotocolprocessingmodules.InthePUPmodel[Boggs78]theseprotocolsaretermed Level1protocols,intheISOmodel,networklayerprotocols.Inoursystemeachsuchprotocol modulehasaninputpacketqueueassignedtoit.IncomingpacketsreceivedbyanetworkinterfacearequeuedupfortheprotocolmoduleandaVAXsoftwareinterruptispostedtoinitiateprocessing. Threemacrosareavailableforqueueinganddequeueingpackets, IFENQUEUE(ifq,m) Thisplacesthepacketmatthetailofthequeueifq. IFDEQUEUE(ifq,m) Thisplacesapointertothepacketattheheadofqueueifqinm.Azerovaluewillbe returnedinmifthequeueisempty. IFPREPEND(ifq,m) Thisplacesthepacketmattheheadofthequeueifq. Eachqueuehasamaximumlengthassociatedwithitasasimpleformofcongestioncontrol. ThemacroIFQFULL(ifq)returns1ifthequeueisfilled,inwhichcasethemacroIFDROP(ifq) shouldbeusedtobumpacountofthenumberofpacketsdroppedandtheoffendingpacket dropped.Forexample,thefollowingcodefragmentiscommonlyfoundinanetworkinterface’s inputroutine, if(IFQFULL(inq)){ IFDROP(inq); mfreem(m); }else IFENQUEUE(inq,m); CSRGTR/6 Leffler,et.al.

NetworkingImplementation-20-Protocol/network-interface 10.Gatewaysandroutingissues Thesystemhasbeendesignedwiththeexpectationthatitwillbeusedinaninternetwork environment.The‘‘canonical’’environmentwasenvisionedtobeacollectionoflocalareanetworksconnectedatoneormorepointsthroughhostswithmultiplenetworkinterfaces(oneon eachlocalareanetwork),andpossiblyaconnectiontoalonghaulnetwork(forexample,the ARPANET).Insuchanenvironment,issuesofgatewayingandpacketroutingbecomevery important.Certainoftheseissues,suchascongestioncontrol,havebeenhandledinasimplistic mannerorspecificallynotaddressed.Instead,wherepossible,thenetworksystemattemptsto providesimplemechanismsuponwhichmoreinvolvedpoliciesmaybeimplemented.Assomeof theseproblemsbecomebetterunderstood,thesolutionsdevelopedwillbeincorporatedintothe system. Thissectionwilldescribethefacilitiesprovidedforpacketrouting.Thesimplisticmechanismsprovidedforcongestioncontrolaredescribedinchapter12. 10.1.Routingtables Thenetworksystemmaintainsasetofroutingtablesforselectinganetworkinterfacetouse indeliveringapackettoitsdestination.Thesetablesareoftheform: structrtentry{ ulongrthash;/*hashkeyforlookups*/ structsockaddrrtdst;/*destinationnetorhost*/ structsockaddrrtgateway;/*forwardingagent*/ shortrtflags;/*seebelow*/ shortrtrefcnt;/*no.ofreferencestostructure*/ ulongrtuse;/*packetssentusingroute*/ structifnet*rtifp;/*interfacetogivepacketto*/ }; Theroutinginformationisorganizedintwoseparatetables,oneforroutestoahostandone forroutestoanetwork.Thedistinctionbetweenhostsandnetworksisnecessarysothatasingle mechanismmaybeusedforbothbroadcastandmulti-droptypenetworks,andalsofornetworks builtfrompoint-to-pointlinks(e.gDECnet[DEC80]). Eachtableisorganizedasahashedsetoflinkedlists.Two32-bithashvaluesarecalculated byroutinesdefinedforeachaddressfamily;onebasedonthedestinationbeingahost,andone assumingthetargetisthenetworkportionoftheaddress.Eachhashvalueisusedtolocatea hashchaintosearch(bytakingthevaluemodulothehashtablesize)andtheentire32-bitvalue isthenusedasakeyinscanningthelistofroutes.Lookupsareappliedfirsttotheroutingtable forhosts,thentotheroutingtablefornetworks.Ifbothlookupsfail,afinallookupismadefora ‘‘wildcard’’route(byconvention,network0).Bydoingthis,routestoaspecifichostonanetwork maybepresentaswellasroutestothenetwork.Thisalsoallowsa‘‘fallback’’networkrouteto bedefinedtoan‘‘smart’’gatewaywhichmaythenperformmoreintelligentrouting. Eachroutingtableentrycontainsadestination(who’sattheotherendoftheroute),agatewaytosendthepacketto,andvariousflagswhichindicatetheroute’sstatusandtype(hostor network).Acountofthenumberofpacketssentusingtherouteiskeptforuseindeciding betweenmultipleroutestothesamedestination(seebelow),andacountof‘‘heldreferences’’to thedynamicallyallocatedstructureismaintainedtoinsurememoryreclamationoccursonlywhen therouteisnotinuse.Finallyapointertotheanetworkinterfaceiskept;packetssentusingthe routeshouldbehandedtothisinterface. Routesaretypedintwoways:eitherashostornetwork,andas‘‘direct’’or‘‘indirect’’.The host/networkdistinctiondetermineshowtocomparethertdstfieldduringlookup.Iftherouteis toanetwork,onlyapacket’sdestinationnetworkiscomparedtothertdstentrystoredinthe table.Iftherouteistoahost,theaddressesmustmatchbitforbit. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-21- Gatewaysandrouting Thedistinctionbetween‘‘direct’’and‘‘indirect’’routesindicateswhetherthedestinationis directlyconnectedtothesource.Thisisneededwhenperforminglocalnetworkencapsulation.If apacketisdestinedforapeeratahostornetworkwhichisnotdirectlyconnectedtothesource, theinternetworkpacketheaderwillindicatetheaddressoftheeventualdestination,whilethe localnetworkheaderwillindicatetheaddressoftheinterveninggateway.Shouldthedestination bedirectlyconnected,theseaddressesarelikelytobeidentical,oramappingbetweenthetwo exists.TheRTFGATEWAYflagindicatestherouteistoan‘‘indirect’’gatewayagentandthe localnetworkheadershouldbefilledinfromthertgatewayfieldinsteadofrtdst,orfromthe internetworkdestinationaddress. Itisassumedmultipleroutestothesamedestinationwillnotbepresentunlesstheyare deemedequalincost(thecurrentroutingpolicyprocessneverinstallsmultipleroutestothesame destination).However,shouldmultipleroutestothesamedestinationexist,arequestforaroute willreturnthe‘‘leastused’’routebasedonthetotalnumberofpacketssentalongthisroute.This canresultina‘‘ping-pong’’effect(alternatepacketstakingalternateroutes),unlessprotocols ‘‘holdonto’’routesuntiltheynolongerfindthemuseful;eitherbecausethedestinationhas changed,orbecausetherouteislossy. Routingredirectcontrolmessagesareusedtodynamicallymodifyexistingroutingtable entriesaswellasdynamicallycreatenewroutingtableentries.Onhostswhereexhaustiverouting informationistooexpensivetomaintain(e.g.workstations),thecombinationofwildcardrouting entriesandroutingredirectmessagescanbeusedtoprovideasimpleroutingmanagementscheme withouttheuseofahigherlevelpolicyprocess.Statisticsarekeptbytheroutingtableroutines ontheuseofroutingredirectmessagesandtheiraffectontheroutingtables.Thesestatistics maybeviewedusing Statusinformationotherthanroutingredirectcontrolmessagesmaybeusedinthefuture, butatpresenttheyareignored.Likewise,moreintelligent‘‘metrics’’maybeusedtodescribe routesinthefuture,possiblybasedonbandwidthandmonetarycosts. 10.2.Routingtableinterface Aprotocolaccessestheroutingtablesthroughthreeroutines,onetoallocatearoute,oneto freearoute,andonetoprocessaroutingredirectcontrolmessage.Theroutinertallocperforms routeallocation;itiscalledwithapointertothefollowingstructure, structroute{ structrtentry*rort; structsockaddrrodst; }; Theroutereturnedisassumed‘‘held’’bythecalleruntildisposedofwithanrtfreecall.Protocols whichimplementvirtualcircuits,suchasTCP,holdontoroutesforthedurationofthecircuit’s lifetime,whileconnection-lessprotocols,suchasUDP,currentlyallocateandfreeroutesoneach transmission. Theroutinertredirectiscalledtoprocessaroutingredirectcontrolmessage.Itiscalled withadestinationaddressandthenewgatewaytothatdestination.Ifanon-wildcardroute existstothedestination,thegatewayentryintherouteismodifiedtopointatthenewgateway supplied.Otherwise,anewroutingtableentryisinsertedreflectingtheinformationsupplied. Routestointerfacesandroutestogatewayswhicharenotdirectlyaccesiblefromthehostare ignored. 10.3.Userlevelroutingpolicies Routingpoliciesimplementedinuserprocessesmanipulatethekernelroutingtablesthrough twoioctlcalls.ThecommandsSIOCADDRTandSIOCDELRTaddanddeleteroutingentries, respectively;thetablesarereadthroughthe/dev/kmemdevice.Thedecisiontoplacepolicy decisionsinauserprocessimpliesroutingtableupdatesmaylagabitbehindtheidentificationof newroutes,orthefailureofexistingroutes,butthisperiodofinstabilityisnormallyverysmall CSRGTR/6 Leffler,et.al.

NetworkingImplementation-22- Gatewaysandrouting withproperimplementationoftheroutingprocess.Advisoryinformation,suchasICMPerror messagesandIMPdiagnosticmessages,maybereadfromrawsockets(describedinthenextsection). Oneroutingpolicyprocesshasalreadybeenimplemented.Thesystemstandard‘‘routing daemon’’usesavariantoftheXeroxNSRoutingInformationProtocol[Xerox82]tomaintainup todateroutingtablesinourlocalenvironment.Interactionwithotherexistingroutingprotocols, suchastheInternetGGP(Gateway-GatewayProtocol),maybeaccomplishedusingasimilarpro-cess. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-23- Rawsockets 11.Rawsockets Arawsocketisamechanismwhichallowsusersdirectaccesstoalowerlevelprotocol.Raw socketsareintendedforknowledgeableprocesseswhichwishtotakeadvantageofsomeprotocol featurenotdirectlyaccessiblethroughthenormalinterface,orforthedevelopmentofnewprotocolsbuiltatopexistinglowerlevelprotocols.Forexample,anewversionofTCPmightbedevelopedattheuserlevelbyutilizingarawIPsocketfordeliveryofpackets.TherawIPsocket interfaceattemptstoprovideanidenticalinterfacetotheoneaprotocolwouldhaveifitwereresidentinthekernel. Therawsocketsupportisbuiltaroundagenericrawsocketinterface,and(possibly)augmentedbyprotocol-specificprocessingroutines.Thissectionwilldescribethecoreoftheraw socketinterface. 11.1.Controlblocks Everyrawsockethasaprotocolcontrolblockofthefollowingform, structrawcb{ structrawcb*rcbnext;/*doublylinkedlist*/ structrawcb*rcbprev; structsocket*rcbsocket;/*backpointertosocket*/ structsockaddrrcbfaddr;/*destinationaddress*/ structsockaddrrcbladdr;/*socket’saddress*/ caddrtrcbpcb;/*protocolspecificstuff*/ shortrcbflags; }; Allthecontrolblocksarekeptonadoublylinkedlistforperforminglookupsduringpacketdispatch.Associationsmayberecordedinthecontrolblockandusedbytheoutputroutinein preparingpacketsfortransmission.Theaddressesarealsousedtofilterpacketsoninput;this willbedescribedinmoredetailshortly.Ifanyprotocolspecificinformationisrequired,itmaybe attachedtothecontrolblockusingthercbpcbfield. Arawsocketinterfaceisdatagramoriented.Thatis,eachsendorreceiveonthesocket requiresadestinationaddress.Thisaddressmaybesuppliedbytheuserorstoredinthecontrol blockandautomaticallyinstalledintheoutgoingpacketbytheoutputroutine.Sinceitisnot possibletodeterminewhetheranaddressispresentornotinthecontrolblock,twoflags, RAWLADDRandRAWFADDR,indicateifalocalandforeignaddressarepresent.Another flag,RAWDONTROUTE,indicatesifroutingshouldbeperformedonoutgoingpackets.Ifitis, arouteisexpectedtobeallocatedforeach‘‘new’’destinationaddress.Thatis,thefirsttimea packetistransmittedarouteisdetermined,andthereaftereachtimethedestinationaddress storedinrcbroutediffersfromrcbfaddr,orrcbroute.rortiszero,theoldrouteisdiscardedand anewoneallocated. 11.2.Inputprocessing Inputpacketsare‘‘assigned’’torawsocketsbasedonasimplepatternmatchingscheme. Eachnetworkinterfaceorprotocolgivespacketstotherawinputroutinewiththecall: rawinput(m,proto,src,dst) structmbuf*m;structsockproto*proto,structsockaddr*src,*dst; Thedatapacketthenhasagenericheaderprependedtoitoftheform structrawheader{ structsockprotorawproto; structsockaddrrawdst; structsockaddrrawsrc; }; CSRGTR/6 Leffler,et.al.

NetworkingImplementation-24- Rawsockets anditisplacedinapacketqueueforthe‘‘rawinputprotocol’’module.Packetstakenfromthis queuearecopiedintoanyrawsocketsthatmatchtheheaderaccordingtothefollowingrules, 1)Theprotocolfamilyofthesocketandheaderagree. 2)Iftheprotocolnumberinthesocketisnon-zero,thenitagreeswiththatfoundinthepacket header. 3)Ifalocaladdressisdefinedforthesocket,theaddressformatofthelocaladdressisthe sameasthedestinationaddress’sandthetwoaddressesagreebitforbit. 4)Therulesof3)areappliedtothesocket’sforeignaddressandthepacket’ssourceaddress. Abasicassumptionisthataddressespresentinthecontrolblockandpacketheader(asconstructedbythenetworkinterfaceandanyrawinputprotocolmodule)areinacanonicalform whichmaybe‘‘blockcompared’’. 11.3.Outputprocessing Onoutputtherawprusrreqroutinepassesthepacketandrawcontrolblocktotherawprotocoloutputroutineforanyprocessingrequiredbeforeitisdeliveredtotheappropriatenetwork interface.Theoutputroutineisnormallytheonlycoderequiredtoimplementarawsocketinterface. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-25-Bufferingandcongestioncontrol 12.Bufferingandcongestioncontrol Oneofthemajorfactorsintheperformanceofaprotocolisthebufferingpolicyused.Lack ofaproperbufferingpolicycanforcepacketstobedropped,causefalsifiedwindowinginformation tobeemittedbyprotocols,fragmenthostmemory,degradetheoverallhostperformance,etc. Duetoproblemssuchasthese,mostsystemsallocateafixedpoolofmemorytothenetworking systemandimposeapolicyoptimizedfor‘‘normal’’networkoperation. ThenetworkingsystemdevelopedforUNIXislittledifferentinthisrespect.Atboottimea fixedamountofmemoryisallocatedbythenetworkingsystem.Atlatertimesmoresystemmemorymayberequestedastheneedarises,butatnotimeismemoryeverreturnedtothesystem. Itispossibletogarbagecollectmemoryfromthenetwork,butdifficult.Inordertoperformthis garbagecollectionproperly,someportionofthenetworkwillhavetobe‘‘turnedoff’’asdata structuresareupdated.Theintervaloverwhichthisoccursmustkeptsmallcomparedtothe averageinter-packetarrivaltime,ortoomuchtrafficmaybelost,impactingotherhostsonthe network,aswellasincreasingloadontheinterconnectingmediums.Inourenvironmentwehave notexperiencedaneedforsuchcompaction,andthushavelefttheproblemunresolved. Thembufstructurewasintroducedinchapter5.Inthissectionabriefdescriptionwillbe givenoftheallocationmechanisms,andpoliciesusedbytheprotocolsinperformingconnection levelbuffering. 12.1.Memorymanagement Thebasicmemoryallocationroutinesplacenorestrictionsontheamountofspacewhich maybeallocated.Anyrequestmadeisfilleduntilthesystemmemoryallocatorstartsrefusingto allocateadditionalmemory.Whenthecurrentquotaofmemoryisinsufficienttosatisfyanmbuf allocationrequest,theallocatorrequestsenoughnewpagesfromthesystemtosatisfythecurrent requestonly.Allmemoryownedbythenetworkisdescribedbyaprivatepagetableusedin remappingpagestobelogicallycontiguousastheneedarises.Inaddition,anarrayofreference countsparallelsthepagetableandisusedwhenmultiplecopiesofapagearepresent. Mbufsare128bytestructures,8fittingina1Kbytepageofmemory.Whendataisplaced inmbufs,ifpossible,itiscopiedorremappedintologicallycontiguouspagesofmemoryfromthe networkpagepool.Datasmallerthanthesizeofapageiscopiedintooneormore112bytembuf dataareas. 12.2.Protocolbufferingpolicies Protocolsreservefixedamountsofbufferingforsendandreceivequeuesatsocketcreation time.Theseamountsdefinethehighandlowwatermarksusedbythesocketroutinesindeciding whentoblockandunblockaprocess.Thereservationofspacedoesnotcurrentlyresultinany actionbythememorymanagementroutines,thoughitisclearifoneimposedanupperboundon thetotalamountofphysicalmemoryallocatedtothenetwork,reservingmemorywouldbecome important. Protocolswhichprovideconnectionlevelflowcontroldothisbasedontheamountofspace intheassociatedsocketqueues.Thatis,sendwindowsarecalculatedbasedontheamountoffree spaceinthesocket’sreceivequeue,whilereceivewindowsareadjustedbasedontheamountof dataawaitingtransmissioninthesendqueue.Carehasbeentakentoavoidthe‘‘sillywindow syndrome’’describedin[Clark82]atboththesendingandreceivingends. 12.3.Queuelimiting Incomingpacketsfromthenetworkarealwaysreceivedunlessmemoryallocationfails. However,eachLevel1protocolinputqueuehasanupperboundonthequeue’slength,andany packetsexceedingthatboundarediscarded.Itispossibleforahosttobeoverwhelmedbyexcessivenetworktraffic(forinstanceahostactingasagatewayfromahighbandwidthnetworktoa lowbandwidthnetwork).Asa‘‘defensive’’mechanismthequeuelimitsmaybeadjustedtothrottlenetworktrafficloadonahost.Considerahostwillingtodevotesomepercentageofits CSRGTR/6 Leffler,et.al.

NetworkingImplementation-26-Bufferingandcongestioncontrol machinetohandlingnetworktraffic.Ifthecostofhandlinganincomingpacketcanbecalculated sothatanacceptable‘‘packethandlingrate’’canbedetermined,theninputqueuelengthsmaybe dynamicallyadjustedbasedonahost’snetworkloadandthenumberofpacketsawaitingprocessing.Obviously,discardingpacketsisnotasatisfactorysolutiontoaproblemsuchasthis(simply droppingpacketsislikelytoincreasetheloadonanetwork);thequeuelengthswereincorporated mainlyasasafeguardmechanism. 12.4.Packetforwarding Whenpacketscannotbeforwardedbecauseofmemorylimitations,thesystemgeneratesa ‘‘sourcequench’’message.Inaddition,anyotherproblemsencounteredduringpacketforwarding arealsoreflectedbacktothesenderintheformofICMPpackets.Thishelpshostsavoid unneededretransmissions. Broadcastpacketsareneverforwardedduetopossibledireconsequences.Inanearlystage ofnetworkdevelopment,broadcastpacketswereforwardedanda‘‘routingloop’’resultedinnetworksaturationandeveryhostonthenetworkcrashing. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-27- Outofbanddata 13.Outofbanddata Outofbanddataisafacilitypeculiartothestreamsocketabstractiondefined.Littleagreementappearstoexistastowhatitssemanticsshouldbe.TCPdefinesthenotionof‘‘urgent data’’asin-line,whiletheNBSprotocols[Burruss81]andnumerousothersprovideafullyinde-pendentlogicaltransmissionchannelalongwhichoutofbanddataistobesent.Inaddition,the amountofthedatawhichmaybesentasanoutofbandmessagevariesfromprotocoltoprotocol; everythingfrom1bitto16bytesormore. Astreamsocket’snotionofoutofbanddatahasbeendefinedasthelowestreasonablecommondenominator(atleastreasonableinourminds);clearlythisissubjecttodebate.Outof banddataisexpectedtobetransmittedoutofthenormalsequencingandflowcontrolconstraints ofthedatastream.Aminimumof1byteofoutofbanddataandoneoutstandingoutofband messageareexpectedtobesupportedbytheprotocolsupportingastreamsocket.Itisaprotocolsperogativetosupportlargersizedmessages,ormorethanoneoutstandingoutofbandmessageatatime. Outofbanddataismaintainedbytheprotocolandusuallynotstoredinthesocket’ssend queue.ThePRUSENDOOBandPRURCVOOBrequeststotheprusrreqroutineareusedin sendingandreceivingdata. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-28- Trailerprotocols 14.Trailerprotocols Coretocorecopiescanbeexpensive.Consequently,agreatdealofeffortwasspentinminimizingsuchoperations.TheVAXarchitectureprovidesvirtualmemoryhardwareorganizedin pageunits.Tocutdownoncopyoperations,dataiskeptinpagesizedunitsonpage-aligned boundarieswheneverpossible.Thisallowsdatatobemovedinmemorysimplybyremappingthe pageinsteadofcopying.Thembufandnetworkinterfaceroutinesperformpagetablemanipulationswhereneeded,hidingthecomplexitiesoftheVAXvirtualmemoryhardwarefromhigher levelcode. Dataentersthesystemintwoways:fromtheuser,orfromthenetwork(hardwareinterface).Whendataiscopiedfromtheuser’saddressspaceintothesystemitisdepositedinpages (ifsufficientdataispresenttofillanentirepage).Thisencouragestheusertotransmitinformationinmessageswhichareamultipleofthesystempagesize. Unfortunately,performingasimilaroperationwhentakingdatafromthenetworkisvery difficult.Considertheformatofanincomingpacket.Apacketusuallycontainsalocalnetwork headerfollowedbyoneormoreheadersusedbythehighlevelprotocols.Finally,thedata,ifany, followstheseheaders.Sincetheheaderinformationmaybevariablelength,DMA’ingtheeventualdatafortheuserintoapagealignedareaofmemoryisimpossiblewithoutaprioriknowledge oftheformat(e.g.supportingonlyasingleprotocolheaderformat). Toallowvariablelengthheaderinformationtobepresentandstillensurepagealignmentof data,aspeciallocalnetworkencapsulationmaybeused.Thisencapsulation,termedatrailerprotocol,placesthevariablelengthheaderinformationafterthedata.Afixedsizelocalnetwork headeristhenprependedtotheresultantpacket.Thelocalnetworkheadercontainsthesizeof thedataportion,andanewtrailerprotocolheader,insertedbeforethevariablelengthinformation,containsthesizeofthevariablelengthheaderinformation.Thefollowingtrailerprotocol headerisusedtostoreinformationregardingthevariablelengthprotocolheader: struct{ shortprotocol;/*originalprotocolno.*/ shortlength;/*lengthoftrailer*/ }; Theprocessingofthetrailerprotocolisverysimple.Onoutput,thelocalnetworkheader indicatesatrailerencapsulationisbeingused.Theprotocolidentifieralsoincludesanindication ofthenumberofdatapagespresent(beforethetrailerprotocolheader).Thetrailerprotocol headerisinitializedtocontaintheactualprotocolandvariablelengthheadersize,andappended tothedataalongwiththevariablelengthheaderinformation. Oninput,theinterfaceroutinesidentifythetrailerencapsulationbytheprotocoltypestored inthelocalnetworkheader,thencalculatethenumberofpagesofdatatofindthebeginningof thetrailer.Thetrailinginformationiscopiedintoaseparatembufandlinkedtothefrontofthe resultantpacket. Clearly,trailerprotocolsrequirecooperationbetweensourceanddestination.Inaddition, theyarenormallycosteffectiveonlywhensizablepacketsareused.Thecurrentschemeworks becausethelocalnetworkencapsulationheaderisafixedsize,allowingDMAoperationstobe performedataknownoffsetfromthefirstdatapagebeingreceived.Shouldthelocalnetwork headerbevariablelengththisschemefails. Statisticscollectedindicateasmuchas200Kb/scanbegainedbyusingatrailerprotocol with1Kbytepackets.Theaveragesizeofthevariablelengthheaderwas40bytes(thesizeofa minimalTCP/IPpacketheader).Ifhardwaresupportslargersizedpackets,evengreatergains mayberealized. CSRGTR/6 Leffler,et.al.

NetworkingImplementation-29- Acknowledgements Acknowledgements TheinternalstructureofthesystemispatternedaftertheXeroxPUParchitecture [Boggs79],whileincertainplacestheInternetprotocolfamilyhashadagreatdealofinfluencein thedesign.Theuseofsoftwareinterruptsforprocessinvocationisbasedonsimilarfacilities foundintheVMSoperatingsystem.Manyoftheideasrelatedtoprotocolmodularity,memory management,andnetworkinterfacesarebasedonRobGurwitz’sTCP/IPimplementationforthe 4.1BSDversionofUNIXontheVAX[Gurwitz81].GregChessonexplainedhisuseoftrailer encapsulationsinDatakit,instigatingtheiruseinoursystem. References [Boggs79]Boggs,D.R.,J.F.Shoch,E.A.Taft,andR.M.Metcalfe;PUP:AnInternetworkArchitecture.ReportCSL-79-10.XEROXPaloAltoResearch Center,July1979. [BBN78]BoltBeranekandNewman;SpecificationfortheInterconnectionofHost andIMP.BBNTechnicalReport1822.May1978. [Cerf78]Cerf,V.G.;TheCatenetModelforInternetworking.InternetWorking Group,IEN48.July1978. [Clark82]Clark,D.D.;WindowandAcknowledgementStrategyinTCP.Internet WorkingGroup,IENDraftClark-2.March1982. [DEC80]DigitalEquipmentCorporation;DECnetDIGITALNetworkArchitecture −GeneralDescription.OrderNo.AA-K179A-TK.October1980. [Gurwitz81]Gurwitz,R.F.;VAX-UNIXNetworkingSupportProject−Implementa-tionDescription.InternetworkWorkingGroup,IEN168.January1981. [ISO81]InternationalOrganizationforStandardization.ISOOpenSystemsInterconnection−BasicReferenceModel.ISO/TC97/SC16N719.August 1981. [Joy82a]Joy,W.;Cooper,E.;Fabry,R.;Leffler,S.;andMcKusick,M.;4.2BSDSystemManual.ComputerSystemsResearchGroup,TechnicalReport5. UniversityofCalifornia,Berkeley.DraftofSeptember1,1982. [Postel79]Postel,J.,ed.DODStandardUserDatagramProtocol.InternetWorking Group,IEN88.May1979. [Postel80a]Postel,J.,ed.DODStandardInternetProtocol.InternetWorkingGroup, IEN128.January1980. [Postel80b]Postel,J.,ed.DODStandardTransmissionControlProtocol.Internet WorkingGroup,IEN129.January1980. [Xerox81]XeroxCorporation.InternetTransportProtocols.XeroxSystemIntegrationStandard028112.December1981. [Zimmermann80]Zimmermann,H.OSIReferenceModel−TheISOModelofArchitecture forOpenSystemsInterconnection.IEEETransactionsonCommunications.Com-28(4);425-432.April1980. CSRGTR/6 Leffler,et.al.