New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Computer Networks

by: Michele Herzog

Computer Networks CS 336

Michele Herzog
GPA 3.7


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 33 page Class Notes was uploaded by Michele Herzog on Thursday October 29, 2015. The Class Notes belongs to CS 336 at University of San Francisco taught by Staff in Fall. Since its upload, it has received 25 views. For similar materials see /class/231244/cs-336-university-of-san-francisco in ComputerScienence at University of San Francisco.

Similar to CS 336 at USF

Popular in ComputerScienence


Reviews for Computer Networks


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15
Socket Programming 2 Applimliari LCMer i Socket programming usmg TCP Socket 0 door between application process and end endtransport protocol UCP or TCP servic reliable Transfer of bytes from one process to another cuntrulled by applicaliurit aeyeiaper cuntrulled by WWW internet system host or server 2 Appitsattan Layer 2 Socket programming with TCP client must contact server a Wimpy mmamd by cm a server process must first be server TCP creates new socket running tor server process to communicate wttn client 0 allows server to talk with multiple citents 0 source port numbers used 39 to distinguish clients more a creatingclientrlocalTCP MW 3 socket El server mus have created socket door that welcomes citent39s contact Client contacts server by u specttytng I address port number of server process application v ewpoi TL39 nt prawdes reliable in arder trans tzr afbyres ppa between client ansserver e connection to server TCP 2 Appitmttan LCMer 3 Stream 39argon D A stream is a sequence of characters that flow into or out of a process D An input stream is attached to some input source for the process eg keyboard or socket D An output stream is attached to an output source eg monitor or socket 2 Application Layer Socket programming With TCP Example clientserver app staner input inFromleer stream sends to server via socket outToServer stream 2 server reads line from socket 3serverconverts 39 uppercase sends back to cl out 4 client reads prints modified lne from socket inFroniServer stream 2 Applimliari LCMer s Clientserver socket interactio 39 TCP Server running on hnsdd Client TCP i cannediansacket diEMSDEkel read reaues wont clienlsockel connedionsockel nu mnne ionsockel pmad replvworii diemsockel sass ernnsmmsrera sass l stemsrersr 2 Appitsattan Layer 5 Example Java clien139TCP impuniava in impuniava net i eiass TCPCiienu pubh static VEHd mainsmng argv thmvvs Exceptiun string sentences 5an meditiedSemenee Dani p Eu erEdREadermFrumUser mp mm new EuneredReadennew nputStrEamREadErSystem in CPZGVZ ciieni socket Bucket ciientSuckEt new Seekewesinarne x E789 CONVch V0 SEN27 Crea i DataOutputStrEam uutTuSEnE 20m new DataDutputStrEamchEntSuckEt getOutputStrEamO output sir i aiiacned io socket 2 Apphmhanlaver 7 Example Java clien r TCP con r 02W Eu eredReader inFrumSENEr inpui sireain new EunereeReaeennew amican no com inputStrEamREaderiherituiket get nputSIrEaMD sentence inFrumUsErreadLin 52nd iine 0 WW uutTuSEnEr vvritEBytEssEntEnce t ri Rzad iine mudifiEdSEntEnce inFrumSENErrEadLin from server Ss em nut printn FR OM SERVER mudi1ied82m2n52 dientSuckEt iusEO 2 Apphcmian Layer 2 Example Java server TCP impeniava in 2 impeniava net eiassTcPSeweii pubhc staticvuid mamSmng avgv iniews Exceptiun suing EMEMSEMEHEE Create suing capitahzedSemence WE CWMQ mm Seweiseiekeiweiemneseiekei new SevvevSucketU EB ai pom 6789 Wait onweiconin Wienva 506 m wad seekei eunneeiiunseiekeiweiemneseiekei enema by ciieni u evedR eadevianumChem 2 mp new Eu evedR eadev new W20 Wacth inputStveamR eadevcunnectiun8ucket geiinpuisuearno i to sockz 2 Apphm ion Wei 9 Exam e Java server TCP con r Create ouipu WW WOW DataOutputSIrEam uutTuChEnt to sow new DataOutputStrEamcunnectiunSucket getompmSheamo Dead in iine eiieniSenienee inFrumChEnt readLinEO from sockz apitahzedSEntEnce eiieniSenienee tuUppErCasEO t ri WNB 39 quot2 uutTuChEnt WritEEyIEsapitahzedSEntEnce V0 SOCRZV End of we ioop ioop back and wan for anorner ciieni connecnon 2 Apphcmmn Layer in Socke r ro rammln wn h UDP UDP no connection between ci ent an n no handshaking a sender 12pr citiy attaches PP39 m quot w 39f n u n of x afyraups orbytes quotdarayrmns emeen client and server destination to each packet from received packet UDP transmitted data may be received out of order orIost 2 Aooiimt ion Wei ii CIienfserver sockef inferacfion39 UDP Server running on hns d Clienf ev ate ken cveatesacket pan x i S eiientsmei ineonineieaoe as Yam oe e smegma o i e s r to eteerensmeio c mEiaddvess wstxd pnn i send datagvam request read mum m osne cieMSacK21 et sevveriack wnie vm seweiSoexei speemnoeiieni reemepivnon hasladdvess diemsacket pa a eiose chemSackeI 2 Apphcmian Layer i2 Link Layer Error Defec rionCorrec rion and MAC 5 DataLinkLayer 5r El hosts and rou i39ers are nodes El commun cation channels fhaf connecf adjacent nodes along commun cafion pafh are links 0 w red links 0 w reless links 0 LANS layer2 packe l is a frame encapsulafes dafagram D data link layer has responsibility of To adjacent node over a link 5 DataLinkLayer 572 Adap rors Communicatinq dafagram I rcvn n swine 9 node node adapfer adapfer CI link layer implemen red CI receiving side in adap ror aka NIC 0 looks for errors rd l flow 0 Ethernet card PCMCI C mr lv an card 80211 card 0 exfracfs dafagram D sending Side passes To rcving node 0 encapsulafes dafagram n D adapter is semi a frame aufonomous 0 adds error check ng bifs 3 link amp physical H 573 rdf flow control efc y Error Defec rion EDC Error Defecfion and Correction bifs redundancy D Dafa profecfed by error checking may include header fields Error defecfion not 100 reliable profocol may miss some errors but rarely larger DC field yields beffer defec ion and correction datagram Y I a gt detected d data bits l D EDC I D39 EDC39I ll 5 DataLink Layer 5V4 Purify Checking Single Bi r Purim Two Dimensional Bi r Purify Detect single bit errors Detect and correct single bif errors ddata bits E my 1 21 0111000110101011n H oolumnl d paw Gum no errors correctable single bit error 5 DataLinkLayer 5V5 In rerne r checksum Goal defec r quoterrorsquot 6 g flipped bi rs in Transmi r red segmen r no re used of Transpor r layer an Sande Receiyer El T h k f 39 d El freaf segmenf contents 2 C CC sum 0 recewe stsecluence of 1643 El check if compufed checksum m age equals checksum feld value Cl checksum addifion 139s complemem sum of 0 YES no error defecfed segmem c mems Buf maybe errors nonefheess More lafer o NO error defecfed D sender pufs checksum value info UDP checksum field 5 DataLinkLayer 576 Checksumn g Cyclic Redundancy Check view daTa biTs D as a binary number D choose r1 biT paTTern generaTor 6 goal choose r CRC biTs R such ThaT o ltDRgt exachy divisible by G modulo 2 0 receiver knows G divides ltDRgt by G If nonzero remainder error deTecTe CID o can deTecT all bursT errors less Than r1 biTs widely used n pracTice ATM HDCL lt d bits lt rbits gt bit D data bits to be sent RCRC bits pattern mathematical D 02r XOR R 5 DataLinkLayer 5V7 CRC Example WanT 101011 D2r XOR R n6 0 0 0 1 1 1 0 0 0 0 equivalenTy G 21 WD 02r n6 XOR R 85 equivalenTy TEE if we divide D2r by 58 6 wanT remainder R 1 1 00 1001 1010 R rema nder Der l O O l G 0 1 1 5 DataLink Layer MulTiple Access Links and ProTocols Two Types of quotlinksquot El po nTTo poinT o PPP for dialup access 0 po nTTopo nT l nk beTween ETherneT swiTch and hosT El broadcasT shared w re or medium 0 TradiTional ETherneT o upsTream HFC 0 80211 w reless LAN g d Blal l bll1 blah fr 777 l ZZZzzzzzzzzzz Q 15 1 91 a shared wire snared Wireless saieiirie cocktail party e Ethernel e Wavean 9 l l g 5 DataLinkLayer 579 MulTiple Access proTocols CI single shared broadcasT channel CI Two or more simulTaneous Transmissions by nodes inTerference o collision if node receives Two or more signals aT The same T me muTige access Qro focal CI disTribuTed algoriThm ThaT deTermines how nodes share channel ie deTermine when node can TransmiT CI communicaTion abouT channel sharing musT use channel iTselfl o no ouTofband channel for coordinaTion 5 DataLinkLayer 54D Ideal MuliTple Access ProTocol BroadcasT channel of raTe R bps 1 When one node wanTs To TransmiT iT can send aT raTe R 2 When M nodes wanT To TransmiT each can send aT average raTe R M 3 Fully decenTralized o no special node To coord naTe Transmissions 0 no synchronizaTion of clocks sloTs 4 Simple 5 DataLinkLayer 57M MAC ProTocols a Taxonomy Three broad classes CI Channel ParTiTioning o divide channel inTo smaller pieces Time sloTs frequency code 0 allocaTe piece To node for exclusive use CI Random Access 0 channel noT divided allow collisions 0 quotrecoverquot from collisions CI Taking Turnsquot 0 Nodes Take Turns buT nodes wiTh more To send can Take longer Turns 5 DataLinkLayer 542 Channel Par il lonlng MAC proTocols TDMA TDMA Time division multiple access El access to channel in quotroundsquot a each station gets fixed length slot length pkt trans time in each round a unused slots go idle El example 6 station LAN 13 4 have pkt slots 5 Dmaunkuvlr 5 3 Channel Par il lonlng MAC proTocols FDMA FDMA frequency division leI riple access a channel spectrum divided into frequency bands a each station assigned fixed frequency band El unused transmission time in frequency bands go idle El example 6 station LAN 13 4 have pkt frequency bands256idlem tne E 4 x g a is 9 it 4 5 oeoiinxieyer 5 M Random Access Pro i39ocols in When node has packet to send 0 transmit at full channel datarate R o no aprtortcoordination among nodes we or more transmitting nodes gt colllslon n n e a g g gt r owto recoyer from collisions e gyia delayed refransmlssluns n Examples of random access MAC protocols o slotted ALOHA o ALOHA o CSMA csMACD CSMACA 5 Dmaunkuvlr 5 l5 Slo r red ALOHA tion Operation El when node oblalns fresh n time is diyided nto equal f ame it transmits in next slot 5 22 5 039Si quotW 390 quotWW n no collision node can send new 1 frame frame ti nexl slol A mp El allframes same 3 ze n nodes start to transmit msz my a bag M quotg of in if collision node retransmits SicS frame n each subsequent slot mm W wwwzzd With prob p until success if 2 or more nodes transmit in slot all nodes detect COlliSiOYl an 5 oeoiinxieyer 5 io Slo ed ALOHA noose g g on Prus n s 5 quot9 2 NW quotEde mquot in collisions wasting slots continuously transmit at full d rate of channel 3 2 3 W a highly decentralized only 5 slots in nodes need to be n sync D smple Pat 239 a clocx synchronization 5 Dmaunkuvlr 5 ii SIo r red Aloha foICIZricx Efficiency is the longerun D For max efflmo Wlm N nodes find p that maximizes NPLP quot 1 For many nodes take l mit of Npmepww as N goes to infinity giyes le 37 n SuppuseN nudeswlfh many framesto send each transmits n slot With probabiltty p n probthat noael has success quot W PM Afbes channel a probthat any nude has a success motlepw 5 DlenkD H 5 ix Pur39e unsloTTed ALOHA CI unsloTTed Aloha simpler no synchronizaTion CI when frame firsT arrives o TransmiT immediaTely CI collision probabiliTy increases 0 frame senT aT To collides wiTh oTher frames senT n To1T01 Willoveilap Willoverlap With slartof With and of ilt i s frame rlt i s rams ri i tOl To t01 5 DataLinkLayer 549 CSMA Carrier SenSe MulTiple Access CSMA lisTen before TransmiT If channel sensed idle TransmiT enTire frame CI If channel sensed busy defer Transmission CI Human analogy don T inTerrupT oThers 5 DataLinkLayer 52D CSMA collisions spaTial layauT of nodes space e collisions can sTill occur A 5quot propagaTion delay means Two nodes may noT hear each oTher39s Transmission collision enT re packeT Transmission Time wasTed noTe role of disTance Sl propagaTion delay in deTermin ng collision probabiliTy lt time 5 DataLinkLayer 5er CSMACD Collision DeTecTion CSMACD carrier sensing deferral as in CSMA o collisions defecfed wiThin shorT Time 0 colliding Transmissions aborTed reducing channel wasTage CI collision deTecTion 0 easy in wired LANs measure signal sTrengThs compare TransmiTTed received signals 0 difficulT in wireless LANs receiver shuT off while TransmiTTing CI human analogy The poliTe conversaTionalisT 5 DataLinkLayer 5722 CSMACD collision deTecTion space gt A lquot C D time collision detectabort Time 5 DataLinkLayer 523 Takinq Turnsquot MAC pr39oTocols channel parTiTioning MAC proTocols 0 share channel eff cienle and fa rly aT high load 0 inefficienT aT low load delay n channel access lN bandwidTh allocaTed even if only 1 acTive node Random access MAC proTocols O efficienT aT low load s ngle node can fully uTilize channel 0 high load collision overhead Tak ng Turnsquot proTocols look for besT of boTh worlds 5 DataLinkLayer 524 Ne rwork Overview Int mducticn l7 A closer look a r ne l39work s139ruc139ure El nefwork edge applicafions and hosfs El nefwork core a routers 0 network of networks El access nefworks physical media communicafion links Innaductmn 172 The ne rwork edge El end sys iems hosts 0 run appl cation programs 0 eg Web email 0 at edge of network Int mducticn 173 The ne rwork edge El clienTserver model 0 client liost requests receives serv ce from always on server 0 eg Web browserserver email cl entserver El why such a popular model Innaductmn M The ne rwork edge El peerpeer model 0 minimal orno use of dedicated servers 0 eg snutella KaZaA o saTleliome Int mducticn LS Im erne r Services Models DConnecTionorien ied service DConnecTionless service El Applica l ions o FTP Infernef Phone Web Infernef radio email Innaductmn 16 ConnecTionorienTed service in coal datatransfer between end systems in handshaking setup prepare for data transfer ahead of t me D TCP Transmission Control Protocol r0 nder wun i uverW eim receiver 0 congestion coniroi senders slaw duwn sending rate when network eungesied Introduction L7 ConnecTionless service M daTa Transfer beTween end sysTems 0 same as before D UDP User DaTagram ProTocoI RFC 768 o connecTionless o unreliable daTa Transfer 0 no flow conTroI o no congesTion conTroI EIWhaT39s iT good for Introduction LE A Comparison A 39s usin TCP D HTTP Web FTP file Transfer TelneT remoTe ogin SMTP email App39s using UDP D sTreaming media Teleconferencing DNS InTerneT Telephony Introduction is The NeTwork Core D mesh of interconnected routers D m fundamental u sTion how is daTa Transferred Through net a circuit switching dedicaTed circuiT per call Telephone neT o packetswitching daTa senT Thru neT in discreTe quotchunksquot Introduction i7 NeTwork Core CircuiT 5 ching Endend resources reserved for call Ink bandwidth switch capacity D D dedicated resources no sharing in circuitlike guaranteed performance in call setup required in must divide Ink bin nto pieces Introduction CircuiT SwiTchinq FDM and TDM Example I 4 users time 39equency Introduction Ne iwork Core Packe r Swi iching each endend data stream divided nio packers in user A 3 packets share network resources El each packet uses full nk bandwidth ll resources used as need resource contention in aggregate resource demand can exceed arnount available 0 whai happens if bandWidih is hai available7 in congestion packets queue wait for I nkuse in s ore and roniiar packei ove one hop at atirne Nude receives eonpleie packei before furwardlrig Int ioouei ion Packe i Swi i chinq ltn39 iml 3939 39 10 Mbs emet stayistisalmhiplaxing l WED B i 15 Mbs queue of packeis wailing for auipui 69 link by a E Sequence of A at B packets does no have fixed paH39ern statistical multblexing Iniiooueiion L o Packe i swi i39chin versus circui i39 swi i39chin Packef swifching allows more users To use network El 1Mbs link El each user 0 100 kbs when active 0 active 10 of time lt x D N users 1 b l39 k El clrculTswn39chlng I M PS Iquot o 10 users El packef swifching o with 35 user39s probability gt 10 active less than 0004 Im ioouei ion Packe i swi i39ching versus circuii39 swi i39ching Is packef swifching a slarn dunk winnerquot El Great for bursfy dafa a resource sharing a simpler no call sefup El Excessive congesfion packef delay and loss 0 profocols needed for reliable dafa Transfer congesi39ion confrol El Circuit Swifching Guaranfeed behavior 0 good for which apps Ini ioouei ion Packetswi ichinq s i39oreandforward l Takes LR seconds To Example Transmii push ouf D 75 Mbits packef of L bii39s on To B R 15 Mbps link or R bps El delay 15 sec D Enflre packef must arrive af roufer before if can be Transmi 39ed on nexf link si ore and forward a delay 3LR Inhoducilari Packe i wi i39ched ne i39works forwarding ii 50a move packets through routers from source to destination 0 we llsiudv several paih seleciian ie rauiingalgariihms chapier 4 datagram n t D e work 0 dZSfliafDi address in packei deiermihes hexi hop 0 rauies may change during session 0 analogy driving asking direciions E v rtual circuit netwoi 0 each packei carries lag Viriual circuii ID lag deiermihes hexi he 0 fixed paih deier mmed analsetup Mme remains fixed ihru call 0 raurers main fali perrcaH sfafe Iniiooueiion L z NeTwork Taxonomy 39 DaTagram neTwork is naf eiTher connecTion orienTed or connecTionless 39 InTerneT provides boTh connecTion orienTed TCP and connecTionless serv ces UDP To apps Introduction 119 Access neTworks and physical media Q How 1390 canned end sys ems fa edge r0uTer residenTial access neTs D insTiTuTional access neTworks school company E El mobile access neTworks Keep in mind El bandwidTh biTs per second of access neTwork El shared or dedicaTed Introduction 120 ResidenTial access poinT To DoinT access El Dialup via modem 0 up To 56Kbps direcT access T0 r0uTer 0fTen less o Can39T surf and phone aT same Time can39T be alwa s onquot El ADSL asymmeTric digiTal subscriber line 0 up To 1 Mbps upsTream Today Typically lt 256 kbps 0 up To 8 Mbps d0wnsTream Today Typically lt 1 Mbps 0 FDM 50 kHz 1 MHz for d0wnsTream 4 kHz 50 kHz for upsTream 0 kHz 4 kHz for ord nary Telephone Introduction 121 ResidenTial access cable modems El HFC hybrid fiber coax o asymmeTric up To 30Mbps d0wnsTream 2 Mbps upsTream El neTwork of cable and fiber aTTaches homes T0 ISP r0uTer 0 homes share access T0 r0uTer El deploymenT available via cable TV companies Introduction 122 Cable NeTwork ArchiTecTure Overview Typically 500 T0 5 000 homes cable headend cable distribution network simpli ed Introduction 123 Cable NeTwork ArchiTecTure Overview swap W Home Environment a cable headend cable distribution network simpli ed Introduction 124 Corn an acces local area networks a companyuniv local area network LAN connects e Wireless access nefwor ks a shared wireless access network connects end system d system to edge router to router router D Efllemel i oslmrvzd or dedicated 99 0 vlcl bclse slclllurl clkcl access be ulnl link conne P 52 J a wireless LANs 5 cts end system and router o 10 Mb i n z o EOZIIb WlFl 11 Mbps 93 99 u widerarea wiieless access o pruvlded byteleo operator 0 N 384 kbps u LANs chapter 5 mobile hosts wllllt ha en77 In raduz lan 115 WAPBPRS quot Emu In raduz lan m Home networks Physmcll Media Typical home network components Tw u ADSL r39cable modem a Bit propagates WWquot a two insulated copper t mitterrcvr pairs u routerfirewallNAT wires D mum D Pl39YS39C l l39quot39 Wh quot3925 o Calegury a traditional between lransmill r39 phone wlres 10 Mbps a wireless access eiver Ethernet P iquot l u uided media 0 Caleeurt 5 In W quot2 s 9 lOOMbps Ethernet lufrum We mm WW 0 slgnals propagate ln sulld m eable M m WM media cupperfbercuclgtlt headend Ethernet u unguided media o signals propagate freely e g radio innooucnon I21 innooucnon 12x Phys cal Med coax f be Coaxial cable F39be39WP 539 a signal carried in hadio linkt st W mm a cuppa D glass f bequot WWW 9N eleetroinagnet e speetruin a terrestrial m or wave mdwm U est ac Pulse a it u no phys cal Wire a eg uptotattopschannels u bldreclluncll D My Pe39m uquot u bldreclluncll a LAN eg Wl l a i 7322 alnllaralm u bclsebarld insyf ssmmeg 5 u pmpagclllunenvlrunmem a 2m s HM s i Sin imamimabig effecls u wlderclrecmegmellulclr 9 u luwerrurrale re eaters H 39 h d d M Diem we re eclan aeg 5 unieso ps 9 Y spaeed fclr apart minune to b39 39 b b B 39 H39 u bmadbcmd eleclrumagnellcnulse D S W D 5 2 l2 a multiple channel micable mm mm a up to anihlopschanneltor 3 HF nulhplesnallerchannels a 27m cendrerld delay E a geosynchronousyeisus law altitude iniioowmn m iniioownon no Internet structure network of networks a roughly hierarchical u at center tier1quotISP5 e g UUNet BBNGenuity Sprint AMT nationalinternational coverage a treat each other as equals Tierel pruvlders Immductlm L3 Tier 1ISP39 e 9 Sprint Sprint US backbone network A Immdudlan m Internet structure network of networks El Tier2quot ISPs smaller often regional ISPs 0 Connect to one or more tlerel ISPs possibly other t ere2ISPs Tierezlsp pays lnlercurmecl NAP Immductlm L33 Internet structure network of networks ll Tier3quot ISPs and local ISPs 0 last nop access network closest to end systems Luccll and llert ier 1 1w 5quot Tier 1 ISP 39 at Internet Immdudlan L34 Internet structure network of networks a a packet passes through many networks Immductlm L35 How do loss and del occu 9 packets queue in router buffers ll packet arrival rate to link exceeds output link capacity ll packets queue wait for turn packet beng transmltted delay packets queueng delay free cwclllclble buffers clr r lvlrlg packets ers drupped lass trnu free buff WWWquot HS Four sources of packeT delay El 1 nodal processing El 2 queueing 0 check bit errors 0 Time waiT ng aT output 0 deTermine output link link for Transmission 0 depends on congesTion level of rouTer lransniis ion 7 t 4 propaga ion lt gt nodal processing QUEUE WQ Int roduci ion Delay in packeT swiTched neTworks 3 Transmission delay 4 PropagaTion delay El Rlink bandwidTh bps El d lengTh of physical link El LpackeT lengTh biTs El 5 propagaTion speed in El Time To send biTs inTo madlum quotZX1OE mSEC link LR El propagaTion delay ds NoTe s and R are very iransniis ion requot 1quot lt7 4 propagaiion nodal processing queueing Ini roduci ion Nodal delay 1pm dqme d d trans pmp dpm processing delay 0 Typically a few microsecs or less El dqum queuing delay 0 depends on congestion El dwms Transmission delay 0 Llz signifcanT for lowspeed links El dPmp propagaTion delay 0 a few microsecs To hundrvzds of msecs Int roduci ion Rea InTerneT delays and rouTes El WhaT do real InTerneT delaydt loss look like ll Traceroute program provides delay measuremenT from source To rouTer along end end InTerneT paTh Towards desTinaTion For all i 0 sends Three packeTs ThaT will reach rouTer ion paTh Towards desT naTion o rouTer iwill reTurn packeTs to sender a sender t mes nTerval between Transmission and reply probe 3 pro es probe Ini roduci ion I Real InTerneT delays and rouTes TracerouTe gaia cs umass edu To www eurecom fr Three delay measernenis from m gaia is umass edu lo csng cs umass edu l2a lla 24m 254 ms ms ms rnria rir owurnasseou l2a llaa l45 l ms l ms 2 ms ms l as w 2 por el 3 chlrvbns wumasseoull2all93 3g orns5rn 5 2 22 ms 22 ms 39 AD lua 253 52 AD iEICi 253 iEIA m5 lu rnsl WSW trans oceanic 3 u m5 lu2 rnsl 4 m5 link l l2 llu l2o ms l2o ms l24 ms l5 eulecumva onner3i2 neliB ESEI 54 l35 ms l2a ms lad ms lg 1343142112509421421125 25 ms l2a ms l2o ms 18 means no reponse probe losi rouier noi replying la ianiasia eureeornirllaa 55 ll3 l42 l32 ins l2a ms lao ms Int roduci ion Lb PackeTloss El queue aka buffer preceding link in buffer has finiTe capaciTy El when packeT arrives To full queue packeT is dropped aka losT El losT packeT may be reTransmiTTed by previous node by source end sysTem or noT reTransmiTTed aT all Ini roduci ion I Ne rwork Layer Overview and IP Nelwmk Wei 4r Ne l39wor39k layer a transport segment from sending to receiving host a on sending side encapsuiates segments into datagrams u ottrcvmgside delivers a networh layer protocois in every host router Router examines header fields m all IP datagrams passing through it Nelwutk Layer 472 Key Ne rwork ayer Func rions El farwardirig move packets from rou ier39s lanl l39 To appropria ie rou ier ou ipu i El rau39l irig determine rou ie Taken by packets from source To des i 0 Routing algorithms Newark Wei 473 Inferplay be i39ween rou i inq and forwardin mmmg uiuontnn mm 3 EMU 2 mt 2 mm t value in amvmg cke pa tsheadei Netwutk Layer M Ne rwork service model Example services for individual da iagrams El guaran ieed delivery El Guaran ieed delivery wiTh less Than 40 msec delay Example services for a flow of da iagrams El Inorder da iagram delivery El Guaran ieed minimum bandwid ih To flow El Restrictions on changes in inferpacker spact rig Netwoiptapei es Vir rual circui rs sourcefodesf path behaves much like teiephone circuit 0 pertorinance rWiSB 0 network actions along sourcertordest path n can setup teardown for each can befam data can ow a each packet carries vc identifier not dest nation host address 1 every router on sourcedest path mainta ns state for each passing connecton a link router resources bandwidth buffers may be allocatedto vc Nelwutk Layer 47o Da rag ram ne l39works 11 no 6011 setup at network 1ayer El routers no state about endtorend COVMZCHOHS 0 hr ne39wurkr1eve1 ehheepr EIf CEInn2C11EIn 11 packets forwarded hshg deshhahoh hosr address 0 packers berweeh some suurcerde phr may rake d1fferem phrhs 11 Why1s 1h1s OK for the Imerhen Newark mm m 4 billi Forwarding Table quot P05511312 enfrles Desuheuoh Address Range Lrhk memos 11001000 0001011100010000 00000000 hhrough 0 11001000000101110001011111111111 11001000 0001011100011000 00000000 hhrough 1 11001000000101110001100011111111 11001000 000101110001100100000000 hhrough 2 11001000000101110001111111111111 ohherwrse 3 Newark Layer ea Longes r prefix ma rching Pre x Match L1n1lt Interface 110010000001011100010 0 11001000 0001011100011000 1 110010000001011100011 2 othenmse 3 Examp1es DA11001000 00010111 00010110 10100001 wh1ch1merface7 DA 11001000 00010111 00011000 10101010 whmh wer1acegt Newark mm 479 Dafagram or VC nefwork why Internet 11 data exchange among computers 0 1 ATM 11 2v01vedfr0m 1212ph0w e1as11c serv1ce hostrm D h man cohversah a wrung req quot39 mar 2nd 3W2 o s1r1c1 wrung re11ab1111y compums reqmremems o cahadapr perform comr01 o heed for guarameed error recwery servme o s1mp1e 1hs1de network a dumb and swam comp1ex11y ar edge 2 Wsz many 1m types 0 d1fferem charactemsncs o umform senme d1f cu11 a o comp1egtlt11y ms1de network Newark Layer em The Inferne r Ne l39work layer Hosf roufer nefwork layer funcfions Transporv mer T61 1101 Network layer Newark 1am e11 IP da l39agram forma r 1ppro1oco1v2rs10r 7 32b11s 4 yom1damgram hhmher header 1eng1h 1ehgrh hyres MS 1ehgrh for 1yp2 0f dara fra me gtfr agrhemanoh ss humb2r1 Imerher rea emb1y remammg hops h h 1 11202020121 039 32 bh source IP address 2 P001 32 bh dBSHYvaHOYv IP address upper 1ayer pr010c01 10 dehver pay1oad10 Op ons or any 7 7E g Hmesmmp how much overhead data Ziggdsrgifw 1h To M7 var1able length W of Wm 11 20 bytes of TCP typrcally a TCP 3 11 20 bytes 0fIP or Ustegmem 11 40 bytes p 10 er overhead Newark Layer e12 IP Fragmen ra rion amp Reassemblx El network llYllKS have MTU max iransfer size 7 larg2s1 possible linkrlevel frame 0 differenr link 1ypes different M s a large IP daiagram awed fragmented Wiinin nei reas idenm order reiaied fragmems Newark Layer 4713 IP Fragmen i39crrion and Reassemblx Exam e One large daiagmm becomes several smaller daiagrams dafagram El MTU 1500 bytes 1430 byies m V data field offset MEDE Neiwmk Layer in IP Addressin in rroduc rion 1 IP address 3Zbif 331 ideni ifier for has 223127 3i 23 roufer interface 2 El infzrfaczi connecfion 2231 13 2231327 223i ggw befween hosTroufer and physical link 2231 31 2231 32 o router39s typ cally have multiple nierfaces a host mayhave nun ple 39quotl39zrfac39zs 2231 1 111n11111unnnnnn1nnnnnnn1nnnnnnn1 IP addresses associated with each infer ace 223 1 1 Newark Layer 4715 Subne rs 1 IP address 0 subnei part high orderbif a host part low order bits 1 Whaf s asubnef 7 o dev ce interfaces with same subnef pm of network consisnng of 3 subweis intervening router Neiwmk Layer 4716 M Re 39pe 1 To defermine The subnefs defach each inferface from ifs has or roufer creating islands of isolafed nefworks Each isolafed nefwork is called asubnei 223 1 3n24 Subnef mask 24 Newark Layer 4717 M How many 3132 Neiwmk Layer 47m Classful Addressing class A 39 my 127255255255 3 128000 i 191255 255 255 o o o in C 110 nelwork liosl 223 255 255 255 muliicasraddrzss 2240mm D 1110 239255 255 255 7 32 bits 4 Nelwmk lei2i my IP addressing CIDR CIDR Classless InferDomain Rou i ing o subnef portion of address of arbifrary lengfh 0 address formaf ab c dx where x is bifs in subnef portion of address subnel i ari P0quot 11001000 0 010111 00010000 00000000 200 23 16023 Nelwmk Layer Mu IP addresses how To get one Q How does hasf ge i IP address El hardcoded by system admin in a file 0 eTch osfs El DHCP Dynamic Host Configurafion Profocol dynamically 921 address from as server 0 plugandplay39 more in nexf chapfer Nelwmk lei2i Mi IP addresses how To get one Q How does nefwark ge i subne i part of IP addr 5 gets alloca ied portion of i is provider ISP39s address space lSFquot bluek EIEIEIEI EIEIEIEIEIEIEIEI ZEIEI 231B ElZEI Organlzatlun El 11DE1EEE ElElEllEllll ElElEllElElElEl EIEIEIEIEIEIEIEI ZEIEI 231B ElZS Organlzatlunl 11DE1EEE ElElEllEllll ElElEllElEllEl EIEIEIEIEIEIEIEI ZEIEI 2318 EUR Organlzatlun Z llElEllElElEl ElElEllEllll ElElEllEllElEl EIEIEIEIEIEIEIEI ZEIEI 23 ZEI ElZS Organlzatlun7 um um Bun B nun El EIEIEIEIEIEIEIEI ZEIEI 23 3D EIZa Nelwmk Layer 422 Hierarchical addressinq rou i e aqqreqa i ion l lizrarcliical addresslng allows efficizm adverllsemenl of rouiirig lnformallon Send me anylhlng Wiin addrexxe nnng is emel Send me anylhlng Wiin addrexxe Nelwmk lei2i 423 Hierarchical addressing more spec39 39c rou i es ISPsrRrUs has a more speclflc roule l0 Organlzallon 1 Oiigiian u Send me anyVhlng Wiin addresxe heglnnlng I99 31 CID16 m 2cm man23 Langexl pierix malchl Nelwmk Layer 424 IP addressing the last wor Q How does an ISP get block of addresses ICANN Internet Corporation for Assigned Names and Numbers 0 allocates addresses 0 manages DNS 0 assigns domain names resolves disputes Network layer 25 NAT Network Address Translation lt7 resl of Inlernel lt7 local network 4gt 2 1 1387o2 Datagrams with source or network have same single source dest nation n this network AT IP address 1387629 liave 100024 address for different source port numbers source destination as usual Alldatagrams leaving local Network layer we NAT Network Address Translation El Motivation local network uses just one IP address as far as outside word is concerned 0 no need to be allocated range of addresses from ISP just one IP address is used for all devices 0 can change addresses of devices in local network without notifying outside world 0 can change ISP without changing addresses of devices in local network 0 devices inside local net not explicitly addressable visible by outside world a security plus Network layer 427 NAT Network Address Translation Implementation NAT routerrnust o outgoing datagrams repace source IP address port of every outgoing datagran to NAT IP address new port renote clientsservers will respond us ng NAT IP address new port as dest nation addr o remember in NAT translation tobleevery source IP address port 2 to NAT IP address new port 2 translation pair 0 incoming datagrarns repace NAT IP address new port in dest fields of every ncorning datagran witl corresponding source IP address port stored n NAT table Network layer 425 NAT39 Network Address Translation NAT translation lable laa7o297 5001 100m 13th A 2 NAT rower u host ll Otil source addr rom ve 138 7b 29 7 Ems iaoiirwoloo m3 l V 4 MT desl address 138 70 29 7 500i 10003 xx e f addr from laa 7o 29 7 5001 lo lot i l 3345 Network layer 29 NAT Network Address Translation El 16bit portnumber field 0 60 000 simultaneous connections with a single LANside address D NAT is controversial o routers should only process up to layer 3 o violates endtoend argument NAT possibilityrnust be taken into account by app designers eg P2P appl cations 0 address shortage should instead be solved by IPv6 Network layer Mu ICMP Internet Control Message Protocol El used byhosts amp routers to m 2 communicate networklevel 0 0 echo reply ping informalion 3 0 dest network unreachable 0 error reporting 3 1 dest host unreachable unreachable has 3 2 dest protocol unreachable 3 3 dest port unreachable quotElwork POM Prolocol 3 6 dest network unknown 0 echo requestreply used 3 7 dest host unknown by ping 4 0 source quench congestion control not used El networklayer above IP 8 0 echo request ping o ICMP msgs carried in IP 9 0 route advertisement datagrams 10 0 router discovery 11 0 TTL expired El ICMP message type code 12 0 bad IP header plus first 8 bytes of IP datagram causing error Network Layer 431 Traceroute and ICMP El Source sends series of El When ICMP message UDP segments to dest arrives source calculates 0 First has TTL 1 RTT 0 Second has TTL 2 etc El Traceroute does this 3 O Unlikely port number 139 165 El When nth datagram W arrives to nth router g UDP segment evenmany G Router discards datagram arrives at dest nation host 0 And sends 0 50394quot 1quot El Destination returns ICMP ICMP message TYPE 11 host unreachablequot packet co e0 type 3 code 3 El When source gets this ICMP stops 0 Message includes name of routeramp IP address Network Layer 432 IPv6 CI Initial motivation 32bit address space soon to be completely allocated CI Additional motivation o header format helps speed processingforwarding o header changes to facilitate Q05 IPv6 datagram format 0 fixedlength 40 byte header 0 no fragmentation allowed Network Layer 433 IPv6 Header Cont Priority identify priority among datagrams in flow Flow Label identify datagrams in same quotflow quot concept of fowquot not well defined Next header identify upper layer protocol for data lt 32 bits gt Network Layer 434 Other Changes from IPv4 CI Checksum removed entirely to reduce processing time at each hop CI Options allowed but outside of header indicated by Next Headerquot field CI ICMPV6 new version of ICMP 0 additional message types e 9 Packet Too Bigquot o multicast group management functions Network Layer 435 Transition From IPv4 To IPv6 CI Not all routers can be upgraded simultaneous o no flag daysquot 0 How will the network operate with mixed IPv4 and IPv6 routers CI Dualstack CI Tunneing IPv6 carried as payload in IPv4 datagram among IPv4 routers Network Layer 436 Principles of Reliable daTa Transfer El imporTanT in app TransporT link layers D Eon 10 lisT of imDorTanT neTworkinq ToD cs 9 8 a serving receiver Reliable DaTa Transfer amp9 c 1 rellablechannel itsend delive edata 8 a reliable dqla u gt 89 rig e t udtisendO Izdtzcv Ll unreliable channel 1 a prowded service b service lmplemenTcilion El characTerisT cs of unreliable channel will deTermine complexiTy of reliable daTa Transfer proTocol rdT Transport Layer 34 Transport Layer 3 2 Reliable daTa Transfer geTTinq sTarTed Reliable daTa Transfer geTTinq sTarTed dtsend called from above eg deliver datao cuned We39ll l3Y aPP P055 do 0 b rdt To deliver daTa To CI incremenTally develop sender receiver sides deliver To receiver u er la er Ll Elquot PP of reliable daTa Transfer proTocol rdT dt d r sen 0 dehverdata CI consider only unidirecTional daTa Transfer reliable daTa send Transfer protocol side sending sldel Wit send l ll rdtrcv l sender receiver Ll lunreliable Channel sfcife when in This enable dam FCCClVe o buT conTrol info will flow on boTh d recTions Transfer protocol receiviri side Slde CI use finiTe sTaTe machines FSM To specify evenT causing sTaTe Transi ion acTions Taken on sTaTe TransiTion udtsend callzd l3Y N rdtrcv called when packeT uniquely deTermined 0 quotMSTquot P sz W arrives on rcvside of channel Y quotEXT 5V5 unreliable channel To receiver Transport Layer 373 Transport Layer 34 Rd l 1039 reliable Transfer over a reliable channel RdT20 Channel Wi l39l l bl l errors CI underlying channel perfechy reliable CI underlying channel may flip biTs in packeT o no biT errors 0 checksum To deTecT biT errors 0 quot0 39055 01 PGCkeTS CI The quesTion how To recover from errors CI separaTe FSMS for sender receiver 0 acknowledgemenfs ACKs receiver expl cile Tells sender o sender sends daTa nTo underlying channel mm P quot5 3le OK 0 receiver read data from undemying Channd o negafive acknowledgemenfs NA Ks receiver explicile Tells sender ThaT ka had errors rdtsenddata rdtrcvpacket extract packetdata deliverdatadata CI new mechanisms in rdtz 0 beyond rdtl o o sender reTransmiTs ka on rece pT of NAK packet makepktdata udtsendpacket 0 error deTecTion SCHdClquot receiver 0 receiver feedback conTrol msgs ACKNA K rcvr gtsender Transport Layer 375 Transport Layer 36 rd39l2 FSM speclflca l lon vdlisendmala Wakeipmdala checksum ndpkl receiver udl send 5 vlechwpkl amp lsNA vcv kl N p vdlivcvvcvpkampamp unlisennsnupn cm vuplUwpkl a isend NA vlechwpkl m lSACKUkal A sender mummpn m nummmpmwpkg 3 man quotNp L al delwev dalamala unlisenmcm mmm Layer 377 rd r2 opercmon wrrh no errors m send 7 dale W p l makeipk dala an udlse lt ecksum mummpn m lsNAKUcvp n muwnwpm m cunupmcvpkl udL e a N dlisen sndpkt a vwvw nulcunup mm We vcv a a Tranipml Layer sea rd r2 0 error scenario vdlisendmala 5W p eke pkl dala checksum ml vvvakl ampamplSACKVkal Trmxpml Layer as rd rZ0 has a fa ral flaw El Sfop and Wei 0 Sender sends one packet rnen Walls for recelver response El Whaf happens if ACKNAK corrupfed o sender doesn t know what happened at recelverl can lJusl relransmll posslble dupllcale El Handling duplicafes o sender adds sequence number to each m o sender relransmlls current pk n ACKNAK garbled o recelver dlscards doesn t dellver up dupllcale pm nangpan Layer 34m sender handles qarbled ACKNAKs misenumala W p m 2 pl ala c ecksum y a unlisennsnupn nu quotNp cunupmcvpkl u lSN mva u l g 39wmpk muwnwpm ampampnulcunuplvcvpkl nulcuvmpmwpkl MCKWW A al uv vlechpr ampamp CELLS c nupmcvpn u lsNAKvcvpk V LsendWala um SEMWM sndpk makeipkl dala cnecksum udlisen sndpkt mmm Layer m rd l 21 receiver handles qarbled ACKNAKs mucvmpm as nutmullmeva as naueqmmvpm enm cvpkl dala delwevjmamma sndpkl MBKEJHKKACK EWSW um sendsndpk0 mucvnwpm as ca um wpkl vaDvak as canummpn mum makeJnmNAK cnksm amisen sndpkl mum makekNAKnksum amisen sndpkl mucvmpm as nm canummvpm as nagsem mm mum makeJWACK cnksum amisen sndpkl ml quotMyMM as nm canummvpm as nassequmvpn sndpk nanemklmcmnksm udLsen mdpkl ymnvmpm as nmmnumnwpn as nauemmvnm ex vadmvpkl dma delwewmamma mum makeJWACK cnksum amisen sndpkl Tranipml Layer 342 rdT21 discussion Sender CI seq added To ka CI Two seq s O 1 will suffice Why CI musT check if received ACKNAK corrupTed Receiver CI musT check i duplicaTe CI Twice as many sTaTes o sTaTe musT remember39 wheTher currenT ka has 0 or 1 seq ACKNAK re 1 received pac keT is o sTaTe ind caTes wheTher O or 1 is expecTed ka seq CI noTe receiver can nof know if iTs lasT ceived OK aT sender Transport Layer 34 3 rdT22 0 NA Kfree proTocol CI same funcTionaliTy as rdT21 using ACKs only El insTead of NAK receiver sends ACK for lasT ka received OK 0 receiver musT expicify nclude seq of ka being ACKed El duplicaTe ACK aT sender resulTs in same acTion as NA K refransmif currem ka Transport Layer 344 rdT22 sender receiver fra menTs rdtsenddata sn p ma ep udtsendsndpkt ata 0 so sum rdtrcvrcvpkt ampamp corTuptrcvpkt isACKsrchkM udt sendsndpkt fragm gm rdtrcvrcvpkt x ampamp notcorruptrcvpkt rdtrcvrcvpkt ampamp vampamp IsACKrcvpkt0 corruptrcvpkt A has seq quot Vpk receiver FSM udt sendsndpkt fragmem rdtrcvrcvpkt ampamp notcorTuptrcvpkt ampamp hasseq1rcvpkt extractrcvpktdata deliverdatadata sndpkt make pktACK1 chksum udtsendsndpkt Transport Layer 34 5 rdT30 channels wiTh errors and loss Aggroach sender waiTs quotreasonablequot amounT of Time New assumpTi on underlying channel can for ACK also lose paCkelS El reTransmiTs if no ACK received daTa or ACKs in This Time D o checksum seq AFKS39 re lr ansmlSSlonS o reTransmission will be W39ll be 01 helP bU l39 quot0139 dup icaTe buT use of seq 39s enough already handles This 0 receiver musT specify seq of ka being ACKed if ka or ACK jusT delayed noT losT rdT30 Sender rdtisendwata Endpkt makeipkuoydalachecksum udtisendGndpkt rdljchopkl ampamp corrupmcvpki H isAcwmpwn T rdtircwrcvpkt 5 5 Jim 9 T timeout udtisendGndpkt rdthvavpkt Slam me rdlirchopkl noicormpumypki ampamp nolcorruptrcvplltl ampamp isACKUcvpkLO C rdlirchopkt ampamp timeout udtisendGndpkt starlitim er rdtisendwata udtisendGndpkt corruptrcvplltl H WNW pm startilim er Wait for call 1 from above sndpkt makeipkl data checksum Stopitim er rdljchopkl A Transport Layer 34 7 El requires couanown Timer Transport Layer 346 rdT30 In acTIon sender receiver sender receiver y 7 k 7 send m icv we saw pm ray pkio c seng ACKO C K t Send ACKO N K 7 rev ACKO rcv SCK send pm sen OK i 085 rcv pm Send ACKi erACKi send pkiD Timeout my Ar rcv pno mam Dk39l rev pm send ACKO ACK send ACK ichCKI send piltIU a operoiion wiih no loss lcv pklU y send ACKD b losl packet Transport Layer 34 8 rdT30 in acTion Sender receiver sender receiver 59 PW 39cv pm Send pm rev okra ACK send ACKD ACK send ACKO rcv ACKO r I rcv ACKU amp send pm send pm rcv pkti rcv pkii AC K send ACKl send ACKl loss x ir ul limeOUl r to y resend pkli esem pm rcv pkll rcv pm e K detect duplrcoie rCVACKl detect duplicale mm L send ACKi send 13le Send ACKT rcv rcv pno Sew pm 39CV pm send ACKO send ACKG c lost ACK d premature timeout Transport Layer 34 9 Performance of rdT30 CI rd r3 0 works buT performance s i39inks CI Why Transport Layer 3720 rdT30 sTopandwaiT opera rion sender receiver 39 n l last packet bit transmitted t L RI rst packet bit arrives R39I39I39 last packet bit arrives send ACK ACK arrives send nex packet t R I39I39 LR Transport Layer 3721 Pipelined proTocols Pipel ning sender allows mulTiple in fligh rquot yeT To be acknowledged kas 0 range of sequence numbers must be increased 0 buffering at sender andor receiver ACX Dockets El Two generic forms of pipelined proTocols gaBack N selecfive repeaf Transport Layer 3722 Pipelininq increaSed uTilizaTion sender receiver rst packet bit transmitted t 0 l 391 rst packet bit arrives last packet bit arrives send ACK last bit of 2quotd packet arrives send ACK 39 last bit of 339 packet arrives send ACK ACK arrives send nex packett R I39I39 LR Transport Layer 3723 GoBackN Sender El k biT seq in pk r header El w ndowquot of up To N consecu rive unack39ed pk rs allowed sendbase nexrseqnum ock e 39l V sent not It by yet ack ed quotO m e L window size T N already usable not at ye t sent El ACKn ACKs all ka5 up To including seq n cumula rive ACKquot 0 may deceive duplica re ACKs see receiver CI T mer for each n flighT pk r CI fimeau n reTransmiT ka n and all higher seq kas in window Transport Layer 3724 GBN receiver ACKonly always send ACK for correc rly received pk r wi rh highes r ITorder seq 0 may generaTe duplicaTe ACKs 0 need only remember expectedseqnum CI ou roforder pk r o discard don39T buffer gt isn39T This bad 0 ReACK ka wiTh highesT inorder seq Transport Layer 25 G n sender receiver send ka0 OCTlon send pkH lesr lilgm send ka2 loss lcv pkll x send ACKi send 3le we ll rcv p163 discard send AC l rev ACKO send pk l rev k r4discord SEWARES sengACKi k rS d d ka2 Tirgeig lscevng ACKlSCQr sen p send ka3 rev ka2 dellver send ka4 send ACK2 send ka5 rev pm eliver send ACKS Transport Layer 3726 SelecTive RepeaT El receiver individualy acknowledges all correcTIy received kas o buffers kas as needed for eventual in order delivery To upper layer CI sender only resends kas for which ACK noT received 0 sender Timer for each LInACKed ka CI sender window 0 N consecLITive seq 5 0 again limiTs seq 5 of senT LInACKed kas Transport Layer 27 SelecTive re eaT sender receiver windows sendibase nexfseqnum alreqdv usqb e net V l cxck ed y llllllllllIllllllllllllllllllllllll Imam f 39 f window size a N a sender View of sequence numbers OUl of order accepmbye i I bU eled b9 wilhin WlndOW already do e llllllllllllllllllllllllllllllll a yet received L window size f N rcvbase b receiver view of sequence numbers Transport Layer 3728 SelecTive repea r gt5 de receiver data from above ka n in rcvbasercvbase Nl El if nexT available seq n D Send ACKn window send ka El outoforder buffer TimeouTn El inorder deliver also deliver buffered inorder pkfs advance window To nexf noT in sendbase sendbaseN yetreceived pk El resend ka n resTarT Timer CI mark ka n as received pk l n in rcvbaseNrcvbase1 El if n smallesT LInACKed ka g ACKn advance window base To nexT LInACKed seq OlherWlse El ignore Transport Layer 349 SelecTive repea r in acTion PkLU Sent pkusenz a WESNW sacrum m2 n12 a U El 5 6 7 s Q 12103 rcvd buggered ACKJ sent ms 7 as U pkm rcvd buffered Acre sent mo rcvd pkl5 sent u 15 7 a 9 o 1 2 3 4 gt 7 s s N n 1 4 5 39 7 a pnz TIMEOUT pnz xesenc D B pkLZ rcvd pktlpkt3pkt4pkt5 dellvered ACK t s nothing sent u 1 2 z 4 5 5 t3 7 a 9 quot t tLayer 3730 TCP rrmsoort Layer 4 OVCF Vi 6W leCs793112213232013 2531 n pointtopont n fullduplex data 0 onzsznd onwzczwr o brdlrecllonaldala ow m some connection a reliable lnor der byte 0 M55 maximum segment steam 3 22 0 no mzssagzbourldarlzs D commiwo i2 E PiPelined o handshaklrlg2gtltcharl cor co rol msgs inns sender o TCPcongzsllonand ow control 32 window size u 52nd amp receive buffer a flow controlled 0 sender will not overwhelm M M receiver Transport Layer 32 TCP segmen r s rr39uc ru r39e lt7 32 bits 4 coummg source rt desf or P P by bytes we urgent data generally not used sequence number of data not segmenlsl rcvr WlHlYlg RST SVN FIN 0 variable length connection ZS b s p l ardown mand appl cation Internet ata checksum variable lengtl as Vi UDP rrmsoort Layer 3 5e TCP seg s and ACKs 0 we stream number Q HWA H m BE urrirstbyrein User ss 2 segment saata types W ACKS 0 nust ACKs o seq at ufnexl byte expected frum utner slde o cumulmlve ACK 0 plggybacklng 5 MKS Q nuwreeewer nonales nutrus mew sew ufec ue ems n d k r segm TCPspecduesn l scly 7 up to lmplememur lime simple telnet scenario Transport Layer 3 TCP Round Trip Time and Timeou r 9L how To set TCP 9 how To estimate RTT Timeout value D SanlpleRTT measured t me from segment transmission until ACK mcei f o ignore retransmissions a longer than lzTT but RTT varies ll too short premature 39 out ll SanlpleRTT will vary want 25 mated IITT smoother o unnecessary r 0 average several recent etransmissions measurements not 39ust in too long slow reaction 39 J h 529mm loss current SampleRTT rrmsoort Layer 5 Example RTT es h mafia m Illum lu mannamn Transport Layer 5 TCP reliable data transfer ll TCP creates rdt service on top of IP39s unreliable service ll Retransmissions are Triggered by a t meout events a duplicate acks El Initially consider simplified TCP sender o ignore dupl cate acks o ignore flow control congestion control B Pipelined segments ll Cumulative acks ll TCP uses single retransmission timer Ttmxpott Laer 377 TCP sender events data rcvd from app timeout ll Create segment with El retransmit segment that caused timeout D seq is bytestream number of first data byte in segment ll start timer if not already running think ll restart timer Ack rcv D If acknowledges previoust unacked segments of timer as for oldest o quotPdme who is knowquot unacked segment to be acked ll expiration interval a start timer iftliere Timeoutlnte rVal are outstan i segments quot9 Transport Layer are pass segmenttu lP NenSeoNum NenSeoNum lengtntoata event timertim ut etacknuwleogeo segmentWitn if end utluup tureverv Ttmspott Layer as Comment SendBasecl last eu cumulativelv retransmit nulcy ackizd by smalles1 sequence numbel starttirner m SendBaserl 71 event ACKvecelved WllnAEKileldvalueuiy y 73 SO mg mp it v gt SendEase swam y wants 73 it inere are cullenlly nulcyelcacknuwledged segments v gt SendBase so 513quot WW that new data lS l acked NexlSeqNu lnitialSegNum Senuuase itialSegNum I TCP TCP retransmissmn scenarios luup tureveril svienevem sender mm A Hot BE eveni data received trum applicatiun abuve create TCP segmentWitn sequence numbel NenSegNum itttimer cullenlly nut running 5 quot ed 5137 lime premature timeout time lost ACK scenario Transport Layer MEI TCP retransmisswn scenarios more SendBase 120 e Cumulative ACK scenario Ttmxpott Layer Mi TCP ACK generation RFC 1122 RFC 2581 Event at Receiver TCP Receiver action Arrival cit lrlrurdEr segment vntn expected seg All data up tu expected seg alreauv ACKed Delaveu ACK Wait up tu suums tur next segment lt nu next segment senu ACK Arrival ur incurder segment vntri expecteu seg r One utner segment nasAcn penuing immeuiatelv senu single cumulative ACK ACKlng butn incurder segments immeuiatelv senu uuplicate Arrival ur nutcufcurder segment ACK r inuicating seg r ur next expected byte higherctnancexpem seg Gap uetecteu Arrival ur segment tnat immeuiate senu ACK pruviueu tnat partiallv ur cumpletelv rills gap segment startsat luwer enu ur gap Transport Layer 342 FasT ReTransmiT CI If sender receives 3 ACKs for The same daTa iT supposes ThaT segmenT afTer ACKed El DeTecT osT segmenTs daTa was IosT via duplicaTe ACKS o fasT reTransmiT resend o Sender ofTen sends segrnen l before limequot many segmenTs back To ZXP39FCS back 0 If segmenT is losT There will likely be many duplicaTe ACKs CI TimeouT period ofTen reaTivey long 0 long delay before resending losT packeT Transport Layer 34 3 TCP Flow ConTr39ol flow conTroI sender won39T overflow CI receive side of TCP connecTion has a receive buffer PRU inan 44 receiver39s buffer by TransmiTTing Too much CI speedmaTching service maTching The send raTe To The llma 39om AC 7 npplimhon m T process llnln t39rtnntt er it pursuant 4 receivtng app s drain CI app process may be raTe slow aT reading from buffer Transport Layer 344 TCP Flow conTr39ol how iT works FRKVVVHHIOW 4 CI Rcvr adverTises spare a slica39 n 39 39 edge room by Including value of RcvWindow in p7 Rchqur 44 segmenTs CI Sender limiTs unACKed daTa To RcvWindow data from m Suppose TCP receiver discards ouToforder segmenTs O guaranTees receive b d 39T l CI spare room In buffer ff 065quot Nerf W Rcvwindow Rchuffer LastByteRcvd LastByteRead Transport Layer 34 5 TCP ConnecTion ManagemenT Recall TCP sender receiver esTainsh quotconnecTionquot before exchanging daTa segmenTs CI iniTiaIize TCP variables 0 seq s o buffers flow conTro info e g RcvWindow CI cliem connecTion iniTiaTor Socket clientSocket new Socketquothostnamequotquotport numberquot CI server conTacTed by cienT Socket quot39 r r anf 0 Transport Layer 34 s TCP ConnecTion ManagemenT Three way handshake STeg 1 cienT hosT sends TCP SYN segmenT To server 0 specifies niTial seq o no daTa STeg 2 server hosT receives SYN replies wiTh SVNACK segmenT 0 server allocaTes buffers o specifies server iniTial seq Tep 3 cl enT receives SVNACK repl es wiTh ACK segmenT which may conTa n daTa Transport Layer 34 7 TCP ConnecTion ManagmenT cont Closing a connecTion Q 5quot MFQ l clIenT closes sockeT C 055 FIN clientSocket close 0 STep 1 cl enT end sysTem close sends TCP FIN conTrol segmenT To server STe 2 server receives FIN replies wiTh ACK Closes connecTion sends FIN 3 Timed waiT close Transport Layer 34 8 FTP SMTP and DNS 2 Appilmtlml Laer i FTP separate control data connections D FITCH comms F TCPcunlrulcunnecllun i 21 server at port 21 specifying P TCP as transport protocol a Client obtains authorization prp T5 4rf ggecquotaquot F overcontrolconne ti n dim mm D Client browses remote d mien Md quotg n Server opens asecond TCP mmands over control data connection to transfer connection another file D hen server receives a in Control connection out of command for a file transfer my the server opens aTCP data connection to client a After transferring one file server closes connection 2 WWW WW 2 Electronic Mail uuigu message queue user malibux Three major components in user agents in mail servers a simple mail transfer protocol SMTP gen El allta mail reade ll r compos ng editing read ng mail mess es El eg Eudora Outlook elm Netscape Messenger outgoing incom ng messages stored on server a 2 Applimiion Lwer 3 Electronic Mail mail servers Mail Servers a mailbox contains incom ng or user D message queue of outgoing to be sent mail messages a sMTP protocol between 39I to send email messages a client sending mail server 0 server receiv ng mail server 2 Application Layer A Electronic Mal SMTP RFC 2821 u uses TCPto reliably transfer email message from client to server port a direct transfer sending serverto receiv ng server a three phases oftransfer o handshak ng greet ng a transfer of messages a closure in commandresponse nteraction o commands ASCII text a response status code and phrase ll messages must be in 7bit ASCII 2 Appilmtlml Laer s Scenario Alice sends messaqe to Bob 1 AI ce uses UA to compose 4 SMTP client sends AI ce39s message and to message over t e TCP bobGSOmeschool edu connection 2 Al ce39s UA sends message 5 Bob39s mail server places to her mail server the message n Bob39s message placed in message mailbox queue 6 Bob nvokes his useragent 3 Client side of SMTP opens to read message onnection with Bob39s mail server 2 Application Layer 5 Mail access profocols g cm SMTP 1 I pr010c0 1 i sender s mail receiver s mail server server El SMTP deliverys rorage To receiver39s server El Mail access protocol re1r eval from server 0 POP Post Office Pro rocol RFC 1939 39 au1horiza1ionagen1 lt gtserver and download 0 IMAP Internet Mail Access Protocol RFC 1730 39 more features more complex 39 manipulation of stored msgs on server 0 HTTP Ho rmail Yahoo Mail etc 2 Application Layer 7 DNS Domain Name SysTem Domain Name System El disfribufed dafabase mplemen red in hierarchy of In139erne1 hos rs r0u139ers many name servers 0 IP address 32 bi1 used for addressing People many iden1ifiers o SSN name passpor r D appicafianlayer prafaca os1 rou1ers name servers To commun care To resolve names addressname 1ransla1ion da1agrams 0 quotnamequot eg WW39yahoo39Com 39 56d by 0 note core In1erne1 func1ionimplemen1ed as applica rion layer pro rocol humans Q map be139ween IP addresses and name 9 o complexi iy a1 ne1work39s I edge 2 Application Layer 8 DNS and Applica ons CI Which applica1ions use DNS CI HTTP 0 Browser ex139rac1s h0s1name o Sends h0s1name 1390 DNS 0 DNS does l00kup and re139urns IP address 0 Browser sends HTTP GET 1390 IP address 2 Application Layer 9 DNS Why n01 cenTralize DNS CI single poin1 of failure CI 1raffic volume CI dis1an1 cen1ralized da1abase CI main1enance doesn391 scae 2 Application Layer 10 DisTribuTed Hierarchical DaTabaSe Root DNS Servers com DNS sewers org DNS servers edu DNS servers 0 edu umassedu yahoo00m am zoncom prorg p DNS servers DNS servers DNs servers DNS serversDNS servers Clien1 wan rs IP or www amazon com39 13 approx CI Clien1 queries a r001 server 1390 find com DNS server CI Clien1 queries com DNS server 1390 ge r amazon com DNS server CI Clien1 queries amazon com DNS server 1390 ge1 IP address for www amazon com 2 Applimimmer n DNS R001 name Server39s El contacted by local name server That can n01 resolve name CI r001 name server 0 contacts au1hori1a1ive name server if name mapping n01 known 0 gets mapp ng ni Hemdun vA aim Lus o re1urns ma ning To local name server even E Du SVA c Cage Ari eleS mpg London aim Amsa nami Flalllgmhn mlca siacmaim muss ainai iacaiiansi m WlDE TENU s Wiew CA 1 lnlemel gamma Alla CAarvd 7 13 roo r name servers worldwide p useisi Manna del Ravi cA i lCANN LasAnaaias cA 2 Application Layer 12 Congestion Control Transport Layer 34 Principles of Congestion Control Congestion CI informally too many sources sending too much data too fast for network to handlequot CI different from flow control CI manifestations 0 lost packets buffer overflow at routers 0 long delays queueing in router buffers CI a top10 problem Scenario 1 Queuing Delays HaaA m aiginai ale CI two senders two receivers Has a uniiiniisa siaisa output iiiiilt puttsis CI one router infinite buffers CI no retransmission C2 gt El large delays U 3 g when congested lt CI maximum i l i d2 C72 7LIn km throughput Transport Layer 373 Transport Layer 372 Scenario 2 Retransmits CI one router finite buffers El sender retransmission of lost packet H 5tA A origiiiai Mn N originaldata plus retransmitted data nite shared output 39 kbu ers Transport Layer 34 Scenario 3 Congestion Near Receiver four senders D Q what39happens as Am and quotincrease D mult hop paths D timeoutretransm it nu An originaldata M original data plus retransmitted data nite shared Transport Layer 375 Approaches towards congestion control Two broad approaches towards congestion control Endend congestion Networkassisted control congestion control El no explicit feedback from El routers provide feedback network to end systems El congestion inferred from 0 single bit ind cating end system observed loss congestion SNA delay DECbi l TCPIF ECN El approach taken by TCP ATM o explicit rate sender should send at Transport Layer 376 TCP ConggsTion ConTrol CI endend conTrol no neTwork assisTance How does sender perceive congesTion39 El loss evenT TimeouT or 3 dupl caTe acks El sender limiTs Transmission LastByteSent LastByteAcked s CongWin El TCP sender reduces raTe D Roughly CongWin afTer loss evenT Three mechanisms CongWin o AIMD quotGT6 B Tessec RTT y 0 slow sTarT o conservative afTer CI CongWin is dynamic funcTion TimeouT evenTs of perceived neTwork congesTIon Transport Layer 34 TCP AIMD diTive increase mulTiplicaTive decrease ad cuT CongWin in half afTer loss evenT Wmde 2 Kbyles 1E Kbyles a Kbyles increase CongWin by 1 M55 every RTT in The absence of loss evenTs probing tyne Long lived TCP connecTion Transport Layer 378 TCP Slow STarT CI When connecTion El Wh n C nnec on begins CongWin 1 begins Increase raTe I M55 exponenTIally fasT unTIl 0 Example M55 2 500 fIrsT loss evenT byTes amp RTT 200 msec o iniTial raTe 20 kbps CI available bandwidTh may be gtgt MSSRTT o des rable To quickly ramp up To respecTable raTe Transport Layer are TCP Slow STarT more CI When connecTion r begins increase raTe exponenTially unTil firsT loss evenT 0 double CongWin every 0 done by incremenT ng CongWin for every ACK received CI Summary iniTial raTe is slow buT ramps up exponenTially fasT Transport Layer 34 0 Refi nemenT Philosophy El AfTer 3 dup ACKs 3 dup ACKs indicaTes o CongWin is cuT in half neTwork capable of 0 window Then grows delivering some linearly segmenTs TimeouT before 3 dup ACKs is more alarming39 CI M afTer TimeouT evenT o CongWin insTead seT 39 To 1 M55 0 window Then grows exponenTially 0 To a Threshold Then grows linearly Transport Layer 3m RefinemenT morel Q When should The exponenTial W I 39 TCPS rte ZR n Increase sthch Tr t1 E s e c 9 lDr l near 31ntssitgu f A When CongWin a geTs To 12 of iTs value before lvammtsston tour 7 2 TimeouT l l ImplemenTaTIon El Variable Threshold D AT loss evenT Threshold is seT To 12 of CongWin jusT before loss evenT r 7er Series t Tnlvoe 1 i2345678 quot quotfm snan l l l l lilil 9 to ii t2 1 4 t5 Ttanw sston vuuuu Transport Layer 34 2 Transport Overview and UDP rrmsporl layer 34 Goals El Understand transport services 0 Multiplexing and Demultiplexing a Reliable data Transfer 0 Flow control 0 Congestion control El TCP and UDP rransporr Layer 32 Transport services and protocols ll provide Iagicalcammunicarian between app processes running on different hosts in transport protocols run n e ms 0 send side breaks app messages ntose ments passes to network layer 0 rev side reassem bles m tli one sport protocol available to apps 0 Internet TCP and UDP Trargporl LCMer a Transport vs network layer a network layer logical quotquotl 39d quot 39 12 kids sending letters to 12 kids communication etween osfs in processes kids D transport layer ll app messages letters in logical communication Wk between processes D h 5ls 39 mus ll transport protocol Ann 0 relies on enhances d Bi quotMWquot 39 Y 5quotquot 5 n networklayer protocol postal service rransporr Layer 3 Internet transDo rtlaver Drotoco ls ll reliable inorder delivery o congestion control 0 flow centre a connection setup ll unreliable unordered delivery UDP o nofrills extension of besteffort IP ll services not available a delay guarante s e a bandwidth guarantees rrmorr layer 35 Multiplexingdemultiplexing Multiplexing at send liost Demu t delivering received segments ket to correct soc lieader later used for i sucker 0 process nelwurk WWW W link host 1 host 2 l 3 rransporr Layer 35 How demultiplexing works a host receives IP datagrams a each datagram has source 7 32 bits IP address dest nation IP mm W l m W 2 address each datagram carries 1 otherheader felds transportlayer segment dest nation port number appI cation recall wellknown port data or specifc numbers r message TCPUDP segment format I segment to appropriate socket rrmsporr Layer 377 Connectionless demultiplexing El When host receives UDP segment mm o checks destination port eaeagmmaackeqssmr number in segmen Datagram ucket my ucketZ 7 new Datagram ucket99222 El Create sockets with port 0 directs UDP segment to socket with that port El UDP socket identified by number Two39 Ple El IP datagrams with deerP address desi port number different source IP directed to same socket Sport Layer Connectionless demux lcontl Datagramsocket serversocket new Datagramsocket6428 SP prov es return address Trmxpmt Layer as Connectionoriented demux El TCP socket identified El Server host may by 4tuple support many a source IP address simultaneous TCP a source port number sockets o dest IP address 0 each socket identified by a dest port number its own 4 uplrz El recv host uses all four 5 WEb SEFVEFS have values to di act different sockets for segment ta appropriate each connecting client socket o nonpersistent HTTP will have different socket for each mques rrmsporr Layer 34m Connectionoriented demux cont Client IF B Trmxpmt Layer m Connectionoriented demux Threaded Web Server Client IF B Transport Layer 342


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.