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

Data Communication And Computer Networks

by: Nick Rowe

Data Communication And Computer Networks CS 53600

Marketplace > Purdue University > ComputerScienence > CS 53600 > Data Communication And Computer Networks
Nick Rowe
GPA 3.68

Ramana Kompella

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

Ramana Kompella
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 76 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 53600 at Purdue University taught by Ramana Kompella in Fall. Since its upload, it has received 69 views. For similar materials see /class/208051/cs-53600-purdue-university in ComputerScienence at Purdue University.

Similar to CS 53600 at Purdue

Popular in ComputerScienence


Reviews for Data Communication And 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: 09/19/15
CS 536 Data Communications and Computer Networks Lecture 16 Routing 11042008 CS 536 Computer Networks 1 Announcements CI HW 2 solu rions pos red Cl HW 2 schedule 0 Curren rly Thursday 6 0 Should nex r Tuesday 11 be useful 9 Cl PA 2 Miles rone A schedule 0 Curren rly Thursday 6 0 Should Monday morning 6am be useful 9 CI Mid rerm schedule 0 Should nex r Thursday 13 be useful 9 CS 536 Compu rer Ne rworks 2 Chapter 4 Network Layer Cl 4 1Introduction CI 42 Virtual circuit and datagram networks CI 43 What39s inside a router CI 44 IP Internet Protocol 0 Datagram format 0 IPv4 addressing o ICMP 0 IPv6 CI 45 Routing algorithms 0 Link state 0 Distance Vector o Hierarchical routing CI 46 Routing in the Internet 0 RIP 0 OSPF O BGP CI 47 Broadcast and multicast routing CS 536 Computer Networks 43 Hierarchical Routing Our r39ou ring s rudy Thus far idealiza rion CI all r39ou rer39s iden rical CI ne rwor39k fla r nor rr39ue in prac rice scale wi rh 200 million adminis rra rive au ronomy des rina rions El in rer39ne r neTwork of El can39T s rore all des r39s in neTWOV kS rouTing Tables El each neTwork admin may would swamp nks own neTwork CS 536 Compu rer Ne rworks 44 Hierarchical Routing CI oggr ego re r39ou rer39s in ro Gafewax rower regions autonomous sysfemsquot AS Cl Dlr39ec r Imk ro r39ou rer39 m ono rher39 AS Cl r39ou rer39s In some AS run some routing protocol 0 in rr39aASquot r39ou ring proTocol o rou rer39s in differenT AS can run differenT in rra AS rouTing pr o rocol CS 536 Compu rer Ne rwor39ks 45 Interconnected ASes Cl forwarding Table configured by bo rh in rra and inferAS I t AS o dering El n2 rou rmg algorl rhm Com a39gm o infraAS se rs en rries for infernal des rs o inferAS amp infraAs se rs en rries for ex rernal des rs CS 536 Compu rer Ne rworks 46 Interconnected ASes CI Consider a packe r arriving of rou rer 2b CI Pocke r is forwarded To 20 ei rher using direc r link or indirec r pa rh Through 2c CI Pocke r even ruolly reaches 20 CS 536 Compu rer Ne rworks 47 InterAS tasks A51 must Cl suppose rou rer in A51 1 learn which des rs are receives do rogram reachable Through des rined ou rside of A52 which Through ASL A53 0 rou rer should 2 propogo re rhis forward packe r ro reochabili ry info To all gateway rou rer bu r rou rers in A51 Wh39Ch one Job of inferA5 rou ring CS 536 Compu rer Ne rworks 48 Example Setting forwarding table in router 1d Cl suppose A51 learns via i nterAS protocol that subnet X reachable via A53 gateway 1c but not via A52 Cl interAS protocol propagates reachability info to all internal routers Cl router 1d determines from i ntraAS routing info that its interface I is on the least cost path to 1c 0 installs forwarding table entry XI CS 536 Computer Networks 49 Example Choosing among multiple ASes Cl now suppose A51 learns from inferA5 profocol rha r subne r x is reachable from A53 and from A52 Cl To configure forwarding fable rou rer 1d mus r defermine Towards which ga reway if should forward packe rs for des r x O This is also job of inferA5 rou ring profocol CS 536 Compu rer Ne rworks 410 Example Choosing among multiple ASes Cl now suppose A51 learns from inTerA5 proTocol ThaT subneT x is reachable from A53 and from A52 Cl To configure forwarding Table rouTer 1d musT deTermine Towards which gaTeway iT should forward packeTs for desT x O This is also job of inTerA5 rouTing proTocol CI hoT poTaTo rouTing send packeT Towards closesT of Two rouTers Learn from interAS Ufsr rTrIOiLr 39rE 1st Hot potato r0Utthi fogvitfdm nteagferthe DFOtOCOI that SUbhet Choose the gateway interface I that leads x is reachable via a ngrfgilnt gt that has the to leastcost gateway multiple gateways costs of Ieastcost smallest least cost EnterXll in paths to each forwarding table of the g t ways CS 536 CompuTer NeTworks 411 Chapter 4 Network Layer Cl 4 1Introduction CI 42 Virtual circuit and datagram networks CI 43 What39s inside a router CI 44 IP Internet Protocol 0 Datagram format 0 IPv4 addressing o ICMP 0 IPv6 CI 45 Routing algorithms 0 Link state 0 Distance Vector o Hierarchical routing CI 46 Routing in the Internet 0 RIP 0 OSPF O BGP CI 47 Broadcast and multicast routing CS 536 Computer Networks 412 IntraAS Routing Cl also known as Interior Gateway Protocols IGP Cl most common IntroAS routing protocols 0 RIP Routing Information Protocol 0 OSPF Open Shortest Path First 0 IGRP Interior Gateway Routing Protocol Cisco proprietary CS 536 Computer Networks 413 Chapter 4 Network Layer Cl 4 1Introduction CI 42 Virtual circuit and datagram networks CI 43 What39s inside a router CI 44 IP Internet Protocol 0 Datagram format 0 IPv4 addressing o ICMP 0 IPv6 CI 45 Routing algorithms 0 Link state 0 Distance Vector o Hierarchical routing CI 46 Routing in the Internet 0 RIP 0 OSPF O BGP CI 47 Broadcast and multicast routing CS 536 Computer Networks 414 RIP Routing Information Protocol Cl distance vector algorithm Cl included in BSDUNIX Distribution in 1982 El distance metric of hops max 15 hops From router A to Subnets destination hops N ltgtlt ltc NwwNNn CS 536 Computer Networks 415 RIP advertisements Cl disfance vecfors exchanged among neighbor39s every 30 sec via Response Message also called adver39Tisemen r CI each adver39Tisemen r lis r of up To 25 des rina rion subne rs wi rhin AS CS 536 Compu rer Ne rwor39ks 416 RIP Example C Destination Network Next Router Num of hops to dest w A 2 y B 2 z B 7 x 1 RoutingForwarding table in D CS 536 Computer Networks 417 RIP Example Dest Next hops w 1 x 1 2 C 4 WW A Advertisement from A to D I C Destination Network Next Router Num of hops to dest w A 2 y B 2 z IKA X5 x 1 ROU ngForwardmg Tablesmg Computer Networks 418 RIP Link Failure and Recovery If no advertisement heard after 180 sec gt neighbor link declared dead 0 routes via neighbor invalidated 0 new advertisements sent to neighbors o neighbors in turn send out new advertisements if tables changed 0 link failure info quickly 9 propagates to entire net 0 poison reverse used to prevent pingpong loops infinite distance 16 hops CS 536 Computer Networks 419 RIP Table processing Cl RIP routing tables managed by applicationlevel process called routed daemon Cl advertisements sent in UDP packets periodically repeated Tl urlapl IL Transprt U DP U DP network forwarding forwarding network IP table Table IP link link ple Icai physical CS 536 Computer Networks 420 CS 536 Data Communications and Computer Networks Lecture 25 Final Review 12112008 CS 536 Computer Networks 1 Layer 1 Physical Layer RECEIVER 1 bits PHYSICAL LAYER Emma 1 SENDE RECEIVER 1 CI A possibly faul ry singlehop bi r pipe rha r connec rs a sender To mulfiple receivers C5536 Campuver Newark 2 Physical Layer Sublayers my 5mm 1n mm ecudinq Snblay r Ended mm Coding Snblayer Media Receptiu ma Transmisaio Sublayer Snblayer mm mm Signal nansmssinn Sublayer 5mm my mum mus C5536 Campuver Newark Sluggishness and Noise CI Mos r channels are sluggish They Take Time To respond 0 They Turn a deaf ear ro higher frequencies in The inpu r signal 0 Lower bandwid rh channels are more sluggish Cl Wha r abou r noise 9 Differen r models for differen r channels 0 Simples r and mos r common is whi re noise 0 Uniformly dis rribu red a r all frequencies and normally dis rribu red wi rhin a frequency 65536 Compu rer Ne rworks 4 Sluggishness and noise nput r 39 Output Signal inertiaanly Rise Time Ilnput I 4 33 mlput Sllgnal inertia plus noisey J 5 Rise Time 65536 Compu rer Networks 5 Sampling bits 1 D 1 nnji IdealSampiirGP f CI Receivers recoveF39e F39lEle bi rs in The inpu r signal by sampling oquuT signal close To middle of bi r per39iod CI Two limi rs To bi r raTe channel bandwidTh NyquisT and noiseShannon 65536 Computer Networks 6 Nyquist Limit CI Signal frequency 1T f CI Maximum signal ra re ZT 2f CI Works only if we have comple rely removed frequency componen rs above Time 65536 Computer Networks 7 The Shannon Bound Maximum Signal Amplitude s u Maximum Noise Amplitude logS2N bits per signal 2 signalssec Nyquist Naive Bound 2 B logS2N Shannon Bound a log1 s2N C5536 CumpuferNeMurks Asynchronous coding START BIT 55 DATA BITS lt7 PLUS PARITV 4 i i i 7 125TOF39 i i i i i i i i i BITS i i i i i i i i i i i i i i i i i i i IDEAL SAMW CI Codes 0 characfer 57 bi rs of a Time Eg ASCII Adds par i ry bif CI Charac rer is framed using a sfar f bi r and one or39 Two sfop bi rs D1 is encoded as low volfage O as high CI S rar r bi r is a O and s rop bi r is a 1 C5536 Cumpuier Neiwurks a Manchester and NRZL u 1 n a 1 5 NRZL 715 1 5 l 7 Manchester 391395I l 1 1 Time CI Manchesfer is selfclocking since every bi r provides an ex rr39a Transi rion C5536 Campuver Newark 1n Link Layer Services Cl framing link access 0 encapsulaTe daTagram inTo frame adding header Trailer 0 channel access if shared medium 0 quotMACquot addresses used in frame headers To iden rify source desT differen r from IP address Cl reliable delivery befween ad jacem nodes 0 we learned how To do This already chap rer 3 o seldom used on low biTerror link fiber some Twis red pair 0 wireless links high error ra res Q why bo rh linklevel and endend reliabiliTy 5 Da raLink Layer 512 Internet checksum review Goal defecf quoterrorsquot eg flipped bifs in fransmiffed packe r no re used a r fransporf layer only Sender Receiver El freaf segmenf confenfs as D compul Checks of sequence of 16bif rece39ve segmen integers El check if compufed checksum D checksum addmon 139s equals checksum field value complemen r sum of o NO error defecfed segmenf confenfs 0 YES no error defecfed El sender pufs checksum BUT maybe errors value info UDP checksum quotmeme655 field 5 DafaLink Layer 513 Checksumming Cyclic Redundancy Check CI view data bits D as a binary number CI chOOSe r1 bit pattern generator 6 CI goal chOOSe r CRC bits R Such that O ltDRgt exactly divisible by G modulo 2 0 receiver knows G divides ltDRgt by G If nonzero remainder error detected 0 can detect all burst errors less Than r1 bi ts CI widely wed in practice Ethernet 80211 WiFi ATM 4 d bits gtlt rbits gt bit I Ddata bits to be sentl R39CRC bits pattern r mathematical D 2 XOR R formula 5 DataLink Layer 514 Multiple Access Links and Protocols Two Types of links Cl poinTTopoin r O PPP for dialup access 0 poin r ropoin r link be rween E rherne r swi rch and hos r CI broadcas r shared wire or medium 0 oldfashioned E rherne r o ups rream HFC 0 80211 wireless LAN g g 5 gm 5 I g B 5 g g Q humans at shared wire eg shared RF Shared RF cocktail party cabled E39l39herne39r 69 80211 WiFi Safellife shared air acousfical 5 Da39raLink Layer 515 Random Access Protocols CI When node has packe r To send 0 TransmiT aT full channel da ra raTe R o no a prior coordinaTion among nodes Cl Two or more Transmi r ring nodes quotcollisionquot Cl random access MAC pro rocol specifies 0 how To deTecT collisions 0 how To recover from collisions eg via delayed re rransmissions Cl Examples of random access MAC pro rocols o slo r red ALOHA o ALOHA o CSMA CSMACD CSMACA 5 Da raLink Layer 516 Slotted ALOHA Assump rions CI all frames same size Cl fime divided info equal size slofs Time To rransmi r 1 frame CI nodes s rar r ro fransmif only slo r beginning CI nodes are synchronized Cl if 2 or more nodes fransmif in slof all nodes defecf collision gram Wm Cl when node obfains fresh frame fransmi rs in nex r slof 0 if no collision node can send new frame in nex r slof C if collision node refransmi rs frame in each subsequenf slo r wifh prob p unfil success 5 DafaLink Layer 517 Slotted ALOHA node39i n m node 2 node 3 l l l l l l 739 slots 3 E C S E C E c 9 Pros Cons D single ac39l39ive node can CI COIIiSionS WGSTing SIOTS con rinuously rr39ansmi r CI idle slo rs a r full rate of channel Cl nodes may be able ro CI highly decenfpanzed de rec r collision in less on 5o5 in nodes rhan Time To rr39ansmi r y packe r need To be in sync CI clock synchr39oniza rion CI simple 5 Da raLink Layer 518 Pure unslotted ALOHA CI unslo r red Aloha simpler no synchroniza rion CI when frame firs r arrives O fransmif immediafely CI collision probabili ry increases 0 frame senf af f0 collides wi rh ofher frames sen r in TO 1f01 willoverlap Willoverlap with start of with end of lt i s frame i s frame gt tl t t1 5 Da raLink Layer 519 Summary of MAC protocols Cl channel parririoning by ri me frequency or code 0 Time Division Frequency Division Cl random access dynamic O ALOHA SALOHA CSMA CSMACD 0 carrier sensing easy in some Technologies wire hard in o rhers wireless 0 CSMACD used in E rherne r o CSMACA used in 80211 Cl faking furns o polling from cen rral si re Token passing 0 BlueTooTh FDDI IBM Token Ring 5 Da raLink Layer 520 Link Layer CI 51 In rr oduc rion and servuces CI 52 Error de rec rion and correction Cl 53Mul riple access pr o rocols CI 54 LinkLayer Addressing CI 55 E rher39ne r CI 56 Linklayer swi rches CI 57 PPP CI 58 Link Vir rualiza rion ATM MPLS 5 Da raLink Layer 5 21 ARP Address Resolution Protocol Ques rion how To de rermine Cl EGCh IP quotOde hOST MAC address of B rou rer on LAN has knowing B39s IP address ARP Table Cl ARP rable IPMAC 137196778 address mappings for 1A2FBB7609AD some LAN nodes 137196114 lt IP address MAC address TTLgt o TTL Time To Live Time afTer which address mapping will be forgo r ren Typically 20 min 137196723 7165F7ZB0853 5823D7FA20BO 137196788 5 Da raLink Layer 522 Switch selflearning ag CI swi rch learns which hos rs can be reached Through which in rerfaces 0 when frame received swi rch quotlearnsquot loca rion of sender incoming LAN segmen r 0 records senderlocation pair in swi rch Table BI MAC addr inferface TTL A 1 60 Switch Table ini rially emp ry 5 DaTaLink Layer 523 Example spanning tree X Spanning Tran 4 x CS 536 Computer Networks 24 Point to Point Data Link Control Cl one sender one receiver one link easier Than broadcas r link 0 no Media Access Con rrol 0 no need for explici r MAC addressing O eg dialup link ISDN line Cl popular poin r ropoin r DLC pro rocols O PPP poi n r ropoin r pro rocol O HDLC High level da ra link con rrol Da ra link used To be considered high layerquot in pro rocol s rack 5 Da raLink Layer 525 Byte Stuf ng CI da ra Transparencyquot r39equir39emen r da ra field mus r be allowed To include flag pa r rer n lt01111110gt O Q is received lt01111110gt da ra or39 flag CI Sender adds s ruffsquot ex rr39a lt 01111110gt by re af rer39 each lt 01111110gt dafa by re CI Receiver 0 Two 01111110 by res in a row discard first by re con rinue da ra reception 0 single 01111110 flag by re 5 Da raLink Layer 526 Byte Stuf ng b5 b1 flag by re b4 b2 pa r rer n inwm g111110 01111110 To send 3934 b 1 b 5 I b5 b4 01111110 01111101 b2 b1 flag by re pa r rer n plus stuffed by re in Transmi r red da ra 5 Da raLink Layer 527 Two Key NetworkLayer Functions Cl forwarding move analogy pocke rs from rou rer39s I inpu r To opproprio re D quotOUT39V Q Pr39ocess 01 planning Trip from rou rer ou rpu r source To des r Cl roufing defermine rou re Taken by 539 fOPWOFdIng Process packe rs from source of ge r roing Through To des r Single In rerchonge O roufing agorifhms Ne rwork Layer 429 Network layer connection and connectionless service CI da ragram ne rwork provides neTworkIayer connec rionless service CI VC ne rwork provides ne rworkIayer connec rion service CI analogous To The Transpor rIayer services but 0 service hos r rohos r 0 no choice ne rwork provides one or The o rher o implemen ra rion in ne rwork core Ne rwork Layer 430 4 billion Forwa rdlng table possible entries Destination Address Range Link Interface 11001000 00010111 00010000 00000000 through 0 11001000 000101110001011111111111 11001000 00010111 00011000 00000000 through 1 11001000 000101110001100011111111 11001000 000101110001100100000000 through 2 11001000000101110001111111111111 otherwise 3 Network Layer 431 Longest pre x matching Pre x Match Link Interface 11001000 00010111 00010 0 110010000001011100011000 1 110010000001011100011 2 otherwise 3 Examples DA 11001000 00010111 NUT Which inTer face Which im erface DA 11001000 00010111 1 L fquot Ne rwork Layer 432 Datagram or VC network why InTerneT daTagram ATM VC Cl Clam exChange among El evolved from Telephony compuTer39S 3 human conversaTion O glClST39C servlce39 no Slr39d O sTricT Timing reliabiliTy T39ml39lng req requiremenTs D smarl end Syslems 0 need for guaranTeed compuTers service 0 can adapT perform conTrol error recovery 0 simple inside neTwork complexiTy aT quotedgequot El many link Types 0 differenT characTerisTics o uniform service difficulT El quotdumbquot end sysTems o Telephones O complexiTy inside neTwork NeTwork Layer 433 Router Architecture Overview Two key router functions CI run routing algorithmsprotocol RIP OSPF BGP CI forwarding datagrams from incoming to outgoing link inpUt port output port 0 switching I O O 0 input port fabr39c output port A routing processor Network Layer 434 7 Output port queueing amp gwggh u Ek w 0 nc V rue 1 r F 4w 4 Er r FF J u One Pocket Time later Output Port Contenaion a Time I Cl buffering when arrival ra re via swi rch exceeds ou rpu r line speed Cl queueing delay and loss due 7 0 oufpuf porf Ne rwork Layer 435 buffer overflow Input Port Queuing El Fabric slower than input ports combined gt queueing may occur at input queues El HeadoftheLine HOL blocking queued datagram at front of queue prevents others in queue from moving forward I queueing delay and loss due to input buffer overflow ET e jl e u u u u u u u u u I n n n n n n u I ll 4lquot l lquot I S llfCl quot i ll switch A fabricvil l fabric Tgt gt w 1quot In output port contention green packet at time t only one red experiences HOL blocking packet can be transferred Network Layer 436 P Addressing introduction 9 IP address 32bit 223111 Iden rlfler39 for39 hos r 2231 223121 r39ou rer39 mfer face Cl inferface connec rion 223122 between hostrouter 223113 2231327 39 L and physical link 0 rouTer39s Typically have mul riple in rerfaces 2231 132 0 hosT Typically has one inTerface 0 IP addresses associated with each 223111 11o11111lpoooooo1900000019000000139 inTerface 223 1 1 1 Network Layer39 437 IP addressing CIDR CIDR Classless In rer39Domain Rou ring O subne r por rion of address of arbitrary leng rh 0 address forma r abcdx where x is bi rs in subne r por rion of address SubneT hosf parf 39 POPT 11001000 00010111 00010000 00000000 2002316023 Ne rwor39k Layer39 438 DHCP Dynamic Host Con guration Protocol Goal allow host to dynamically obtain its IP address from network server when it joins network Can renew its lease on address in use Allows reuse of addresses only hold address while connected an on Support for mobile users who want to Join network more shortly DHCP overview O host broadcasts DHCP discoverquot msg o DHCP server responds with DHCP offerquot msg O host requests IP address DHCP requestquot msg O DHCP server sends address DHCP ackquot msg Network Layer 439 Hierarchical addressing route aggregation Hierarchical addressing allows efficient advertiSement of routing information Send me anything with addresses beginning 2002316020quot i j m ernet Send me anything with addresses beginning 199310016quot Network Layer 440 NAT Network Address Translation lt resT of local neTwork gt Internet eg home neTwork H 100024 i 3quot 10001 10004 f 13876297 All daTagrams leaving local DaTagrams wiTh source or neTwork have same single source desTinaTion in This neTwork NAT IP address 1387629 have 100024 address for differen r source porT numbers source des rina rion as usual Ne rwork Layer 441 Routing Algorithm classi cation Global or decentralized information Global El all routers have complete topology link cost info El link statequot algorithms Decentralized El router knows physically connected neighbors link costs to neighbors El iterative process of computation exchange of info with neighbors El distance vectorquot algorithms Static or dynamic Static Cl routes change slowly over time Dynamic Cl routes change more quickly 0 periodic update 0 in response to link cost changes Network Layer 443 Comparison of LS and DV algorithms Message complexiTy CI Q wiTh n nodes E links OnE msgs senT CI Diexchange beTween neighbors only 0 convergence Time varies Speed of Convergence CI Q Onz algoriThm requires OnE msgs 0 may have oscillaTions El DV convergence Time varies 0 may be rouTing loops 0 counTToinfiniTy problem RobusTness whaT happens if rouTer malfuncTions L5 0 node can adverTise incorrecT link cosT 0 each node compuTes only iTs own Table 0 DV node can adverTise incorrecT par1 cosT 0 each node39s Table used by oThers error propagaTe Thru neTwork NeTwork Layer 444 Hierarchical Routing Our r39ou ring s rudy Thus far idealiza rion CI all r39ou rer39s iden rical CI ne rwor39k fla r nor rr39ue in prac rice scale wi rh 200 million adminis rra rive au ronomy des rina rions El in rer39ne r neTwork of El can39T s rore all des r39s in neTWOV kS rouTing Tables El each neTwork admin may would swamp nks own neTwork Ne rwork Layer 445 Interconnected ASes Cl forwarding Table configured by bo rh in rra and inferAS I t AS o dering El n2 rou rmg algorl rhm Com a39gm o infraAS se rs en rries for infernal des rs o inferAS amp infraAs se rs en rries for ex rernal des rs Ne rwork Layer 446 Broadcast Routing CI deliver packets from source to all other39 nodes Cl sour39ce duplication is inefficient duplicate creationtransmission source innetwork duplication duplication Cl sour39ce duplication how does sour39ce deter39mine r39ecipient addresses Network Layer 447 Shortest Path Tree Cl mcast forwarding tree tree of shortest path routes from source to all receivers O Dijkstra s algorithm LEGEND router with attached group member router with no attached group member link USed for forwarding i indicates order link added by algorithm Reverse Path Forwarding El rely on rou rer39s knowledge of unicas r shor res r pa rh from if To sender CI each rou rer has simple forwarding behavior if mcas r da ragram received on incoming link on shor res r pa rh back To cen rer then flood da ragram on ro all ou rgoing links else ignore da ragram UDP User Datagram Protocol RFC 768 El no frillsquot bare bonesquot In rerne r TransporT proTocol El bes r effor rquot service UDP segmen rs may be 0 los r o delivered ouT of order To app El connecf oness o no handshaking beTween UDP sender receiver 0 each UDP segmenT handled independenle of o rhers Why is There a UDP El no connecTion esTablishmenT which can add delay El simple no connecTion sTaTe aT sender receiver El small segmenT header El no congesTion conTrol UDP can blas r away as fasT as desired Transpor r Layer 351 Pipelining Protocols GobackN biq picture Selective Repeat biq pic CI Sender can have up to CI Sender can have up to N unacked packets in N unacked packets in pipeline pipeline Cl Rcvr only sends CI Rcvr acks individual cumulative acks packets O Does 39l OCk PC Cke r if CI Sender maintains Themes 0 9 timer for each CI Sender has tImer f0quot unacked packe39I39 Q When Timer expires o If timer expires retransmit only unack retransmit all unacked packet packets Transport Layer 352 Selective repeat big picture Cl Sender can have up to N unacked packets in pipeline CI Rcvr acks individual packets CI Sender maintains timer for each unacked packet 0 When timer expires retransmit only unack packet Transport Layer 353 GoBackN Sender El kbi39r seq in pk39r header El window of up To N consecutive unack39ed pk39rs allowed sendbase neXlseqnum dreody usable no r ock39ed ye r sen r l lllllllll lll llllllllll gnawed window size N El ACKn ACKs all ka3 up To including seq n cumula39rive ACKquot 0 may receive duplica39re ACKs see receiver El Timer for each inflighf ka El fimeou n reTransmiT pk39r n and all higher seq kas in window Transpor r Layer 354 Selective Repeat Cl receiver individualy acknowledges all correc rly received kas O buffers pk rs as needed for even rual inorder delivery To upper layer CI sender only resends pk rs for which ACK no r received 0 sender Timer for each unACKed ka Cl sender window 0 N consecuTive seq 3 0 again limi rs seq 3 of sen r unACKed pk rs Transpor r Layer 355 Selective repeat sender receiver windows sendbase nexfseqnum already USObIeInOT OCk39ed ye r sen r lili liliillIlllllllllll legged window size N a sender view of sequence numbers occep roble buffered b wi rhin window already ock ed IIHIIIIIIIIIIHHH Herein window size f N ou r of order I rcvbase b receiver view of sequence numbers Transpor r Layer 356 TCP Round Trip Time and Timeout Se r ring The Timeou r Cl EstimtedRTT plus safeTy marginquot lt3largeva a oninEstimatedRTT gt argersafehmarn Cl firs r es rima re of how much SampleRTT deviaTes fr39om Es rima redRTT DevRTT 1 3DevRTT BISampleRTT EstimatedRTTl typically B 025 Then seT Timeou r in rer39val TimeoutInterval EstimatedRTT 4DevRTT Transport Layer 357 TCP ACK generation RFC 1122 RFC 2581 Event at Receiver TCP Receiver action Arrival of inorder segment with Delayed ACK Wait up to 500ms expected seq All data up to for next segment If no next segment expected seq already ACKed send ACK Arrival of inorder segment with Immediately send single cumulative expected seq One other ACK ACKing both inorder segments segment has ACK pending Arrival of outoforder segment Immediately send duplicate ACK higherthanexpect seq indicating seq of next expected byte Gap detected Arrival of segment that Immediate send ACK provided that partially or completely fills gap segment starts at lower end of gap Transport Layer 358 TCP Flow Control CI receive side of TCP connec rion has a receive buffer FRchfmdow 4 2 data from application D spare room 7 Rchu er 4 CI app process may be slow of reading from buffer flow con rrol sender won39f overflow receiver39s buffer by Transmitting 13900 much 13900 fast CI speedma rching service matching The send ra re To The receiving app s drain ra re Transporf Layer 359 TCP Flow control how it works FRchfmdow 4 CI Rcvr adver rlses spare damn applaud room by including value D of Rclendow In 7 4A segmen rs RcVBu er CI Sender limi rs unACKed Suppose TCP rece39ver da ra 1390 RcvWindow discards ou rofor der O guaramees receive segmen rs buffer doesn39f overflow CI spare room in buffer RcvWindow Rchuffer LastByteRcvd LastByteRead Transporf Layer 360


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

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

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!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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.