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

Introduction to Networks and Data Communications

by: Cassandra Sipes MD

Introduction to Networks and Data Communications ECE 355

Marketplace > Old Dominion University > ELECTRICAL AND COMPUTER ENGINEERING > ECE 355 > Introduction to Networks and Data Communications
Cassandra Sipes MD
GPA 3.53

Sachin Shetty

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

Sachin Shetty
Class Notes
25 ?




Popular in Course


This 258 page Class Notes was uploaded by Cassandra Sipes MD on Monday September 28, 2015. The Class Notes belongs to ECE 355 at Old Dominion University taught by Sachin Shetty in Fall. Since its upload, it has received 25 views. For similar materials see /class/215292/ece-355-old-dominion-university in ELECTRICAL AND COMPUTER ENGINEERING at Old Dominion University.

Similar to ECE 355 at ODU



Reviews for Introduction to Networks and Data Communications


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/28/15
Chap rer39 2 Applica rion Layer Sachin Shetty ECE 355 2 Applica rion Layer 1 Chapter 2 Application Layer W CI learn about protocols CI conceptual by examining popular implementation applicationlevel aspects of network protocols application protocols HTTP z Transportlayer oto SMTP POP3 IMAP service models 4 DNS oz clientserver paradigm oz peertopeer paradigm 2 Application Layer 2 Some ne rwork apps email CI voice over39 IP web I realTime video i ns ran r messaging conferencmg r39emo re ogin 539 grid COmPUTing P2P file sharing mul riuser39 ne rwor39k games s rr39eaming s ror39ed video clips DDDDDD D 2 Applica rion Layer39 3 Crea ring a ne rwork app applica rion wri re programs Tha r oz run on differen r end sysfems communicaTe over neTwork oz eg web server sofTware communicaTes wiTh browser sofTware Ii r rle sof rware wri r ren for devices in ne rwork core ne rwork core devices do no r run user applica rions oz applica rions on end sys rems allows for rapid app developmenT propagaTion 2 Applica rion Layer 4 ChapTer 2 Applica rion layer CI 21 Principles of network applica rions CI 22 Web and HTTP CI 24 Electronic Mail oz SMTP POP3 IMAP CI 25 DNS 2 Applica rion Layer 5 Applica rion architec rures CI CIien rser39ver39 CI PeerTopeer39 P2P CI Hybr39id of clien rser39ver39 and P2P 2 Applica rion Layer 6 Clien r server archi rec rure server ozo alwayson hos r oz permanent IP address oz server farms for scahng chenTs oz communicaTe wiTh server oz may be in rermi r ren rly connecTed oz may have dynamic IP addresses oz do noT communicaTe direchy wiTh each oTher 2 Applica rion Layer 7 Processes communicating Process program running within a host CI within same host two processes communicate using i nterprocess communication defined by 05 CI processes in different hosts communicate by exchanging messages Client process process that initiates communication Server process process that waits to be contacted 2 Application Layer 8 Socke rs host or host or server server CI process sendsreceives messages To from i rs SOC ke39l39 391quot u controlled by app developer CI socke r analogous ro door oz sending process shoves message ouT door oz sending process relies on Transpor r infras rruc rure on oTher side of door which brings message To sockeT aT receiving process buffers if buffers variables variables controlled by OS I API 1 choice of rranspor r pro rocol 2 abili ry To fix a few parame rers Io rs more on This Ia rer 2 Applica rion Layer 9 Socke rs Transport Network Link Physical 2 Applica rion Layer 10 Addressing processes I To receive messages process mus r have iden fer CI hos r device has unique 32bit IP address CI Q does IP address of hos r on which process runs suffice for iden rifying The process 2 Applica rion Layer 11 Addressing processes I To receive messages process mus r have iden fer CI hos r device has unique 32bit IP address CI Q39 does IP address of hos r on which process runs suffice for iden rifying The process oz 4 No many processes can be running on same hos r CI Idenfl39 39er includes bo rh IP address and por r numbers associa red wi rh process on hos r CI Example por r numbers HTTP server 80 Mail server 25 CI To send HTTP message To gaiacsumassedu web server oz IP address 12811924512 PorT number 80 CI more shor rly 2 Applica rion Layer 12 Por r Number Port 80 TCP IP 13811011 2 Applica rion Layer 13 App layer profocol defines CI Types of messages Publicdomai n profocols BXChanged CI defined in RFCs oz eg reques r response D allows for C39 Message Synmx inferoperabilify oz wha r fields in messages amp D 89 HTTP SMTP how fields are delinea red P o T T I CI Message seman rics r39olme Cquot39Y Pr39o 0C0 5 CI eg Skype oz meaning of informa rion in fields CI Rules for when and how processes send amp respond ro messages 2 Applicafion Layer 14 WhaT TransporT service does an app need DaTa loss BandwidTh CI some app3 89 GUdiO CG CI some apps eg TOler39Gle some l 55f mulTimedia require CI O fher ClPPS eg flle minimum amounT of Transfer TelneT require bandwidIh To be 100 reliable daTa effec veu Transfer o 0 CI oTher apps elasTIc T39m39 9 appsquot make use of CI some ClPPs 891 whaTever bandwidTh InTerneT Telephony inTeracTive games require low delay To be effecTive They geT 2 ApplicaTion Layer 15 Transport service requirements of common apps Application Data loss Bandwidth Time sensmve file transfer no loss elastic 0 email no loss elastic 0 Web documents no loss elastic 0 realtime audiovideo losstolerant audio 5kbps1Mbps YES 1005 msec video10kbps 5Mbps stored audiovideo losstolerant same as above YES feW secs interactive games losstolerant few kbps up yes 100 s msec instant messaging noloss elastic yes and 0 2 Application Layer 16 In rerne r Transpor r pro rocols services I TCP service comedianomen fed se rup required beTween clienT and server processes reiabe fransporf beTween sending and receiving process fow com roi sender wo n39T overwhelm receiver congesfon com roi Thro r rle sender when neTwork overloaded does nof provide Timing minimum bandwidTh guaranTees UDP service I unreliable da ra Transfer beTween sending and receiving process I does noT provide connecTion se rup reliabiliTy flow con rrol congesTion con rrol Timing or bandwidTh guaran ree Q why boTher Why is There a UDP 2 Applica rion Layer 17 Internet apps application transport protocols Application Underlying Application layer protocol transport protocol email SMTP RFC 2821 TCP remote terminal access Telnet RFC 854 TCP Web HTTP RFC 2616 TCP file transfer FTP RFC 959 TCP streaming multimedia proprietary TCP or UDP eg RealNetworks Internet telephony proprietary eg VonageDiaIpad typically UDP 2 Application Layer 18 Applica rions and App Layer Pr39o rocols Web Server m Web Browser File HTTP Access N Application Layer 19 Pro rocol S rack UI J HTTP Web Browser Transport Network Link Physical 2 Applica rion Layer 20 ChapTer 2 Applica rion layer CI 21 Principles of network applica rions app ar chi rec rur es oz app requiremen rs CI 22 Web and HTTP CI 24 Electronic Mail oz SMTP POP3 IMAP CI 25 DNS 2 Applica rion Layer 21 Web and HTTP Firs r some iarqon CI Web page consis rs of objec rs CI Objec r can be HTML file JPEG image Java apple r audio file I Web page consis rs of base HTMLfile which includes several referenced objec rs CI Each objec r is addressable by a URL CI Example URL www50meschooledusomeDeptpicgif hos r name PCquotrh name 2 Applica rion Layer 22 HTTP overview HTTP hyper rex r Transfer pro rocol CI Web39s applica rion layer proTocol CI clien rserver model oz cI39em browser ThaT requesTs receives quotdisplaysquot Web objec rs oz server Web server sends objec rs in response To requesTs CI HTTP 10 RFC 1945 El HTTP 11 RFC 2068 PC running Hr Explorer running Apache Web Server Mac running NavigaTor 2 Applica rion Layer 23 HTTP overview con rinued Uses TCP CI clienT iniTiaTes TCP connecTion creaTes sockeT To server por r 80 El server accest TCP connecTion from clienT CI HTTP messages applicaTion layer proTocol messages exchanged beTween browser HTTP clienT and Web server HTTP server I TCP connecTion closed HTTP is s ra reless CI server main rains no informaTion abouT pasT clienT requesTs aside ProTocols ThaT main rain sTaTequot are complex I pasT hisTory sTaTe musT be mainTained El if serverclien r crashes Their views of s ra re may be inconsis ren r mus r be reconcHed 2 Applica rion Layer 24 HTTP connections Nonpersistent HTTP Persistent HTTP I At most one object is El Multiple objects can sent over a TCP be sent over single connection TCP connection g HTTP10 uses between client and nonpersistent HTTP sewer CI HTTP11 uses persistent connections in default mode 2 Application Layer 25 Nonpersistent HTTP Suppose user enters URL wwwsomeSchooledusomeDepartmenthomeindex time 2 HTTP client sends HTTP contains text references to 10 jpeg images 10 HTTP client initiates TCP connection to HTTP server process at wwwsomeSchooedu on port 80 1b HTTP server at host wwwsomeSchooedu waiting for TCP connection at port 80 accepts connection notifying client request message co ntai ni ng URL into TCP connection socket Message indicates that client wants object someDepartmenthomeindex 3 HTTP server receives request message forms response message containing requested object and sends message into its socket 2 Application Layer 26 Nonpersis ren r HTTP cont 4 HTTP server closes TCP connecTion 5 HTTP cliem receives response message conTaining hTml file displays hTmI Parsing hTml file finds 10 referenced jpeg objecTs me 6 STeps 15 repeaTed for each 1 of 10 jpeg objecTs 2 Applica rion Layer 27 NonPersis ren r HTTP Response Time Defini rion of RTT Time 0 V send a small packe r To 57quot Travel from clien r To l server and back inmaie connecTion Response rlme RTT CI one RTT ro i ni ria re TCP request l connec rion f39le Time To RTT CI one RTT for HTTP my reques r and firs r few file by res of HTTP response mew6d ro re rurn lms ti l39ne CI file Transmission rime ro ral 2RTTTransmiT Time 2 Applica rion Layer 28 Persis ren r HTTP Nonpersis ren r HTTP issues I requires 2 RTTs per objec r El 05 overhead for each TCP connecTion CI browsers of ren open parallel TCP connecTions To feTch referenced objec rs Persis ren r HTTP CI server leaves connecTion open offer sending response I subsequenT HTTP messages beTween same clienTserver senT over open connecTion Persis ren r wifhoufpipelininq El clienT issues new requesT only when previous response has been received I one RTT for each referenced objec r Persis ren r wifh pipelininq El defaulT in HTTP11 El clienT sends requesTs as soon as if encounTers a referenced objec r I as li r rle as one RTT for all The referenced objec rs 2 Applica rion Layer 29 HTTP r39eques r message CI rwo Types of HTTP messages requesf response CI HTTP reques r message oz ASCII humanreadable formaT r39eques r line GET POST GET somedirpagehtm1 HTTP 1 1 HEAD commands Host www someschool edu Useragent Mozilla40 header Connection close Imes Acceptlanguage fr Car39r39ia e r39e rur39n ling feed veXtra Carriage return line feed indicaTes end of message 2 Applica rion Layer39 30 HTTP reguesf message general forma l39 header lines request line E w lm E D 2 Application Layer 31 Uploading form inpu r Pos r me rhod CI Web page of ren includes for39m inpu r CI Inpu r is uploaded ro server in en ri ry body URL me rhod CI Uses GET me rhod CI Inpu r is uploaded in URL field of request line wwwsomesitecomanimalsearchmonkeysampbanana 2 Applica rion Layer39 32 Me rhod Types HTTP10 HTTP11 CI GET CI GET POST HEAD CI POST CI PUT g HEAD uploads file in enTiTy bod To aTh s ecified oz asks server To leave y p r39eques red objec r ouT of m URL eld response CI DELETE dele res file specified in The URL field 2 Applica rion Layer 33 HTTP response message sTaTusline roTocol s uscodgtHTTp11 200 OK sn usphrase Connection close Date Thu 06 Aug 1998 120015 GMT header Server Apache130 Unix lines LastModified Mon 22 Jun 1998 m ContentLength 6821 ContentType texthtml k aegn data data data data data requesTed HTMLfHe 2 Application Layer 34 HTTP response sTaTus codes In fir39sT line in servergtclienT response message A few sample codes 200 OK oz r39equesT succeeded r39equesTed objecT IaTer39 in This message 301 Moved Permanently oz r39equesTed objecT moved new locaTion specified IaTer39 in This message LocaTion 400 Bad Request r39equesT message noT under39sTood by server 404 Not Found oz r39equesTed documenT noT found on This server39 505 HTTP Version Not Supported 2 ApplicaTion Layer39 35 Trying ouT HTTP clienT side for yourself 1 TelneT To your fovoriTe Web server telnet cispolyedu so Opens TCP connecTion To porT 80 defoulT HTTP server porT oT cispoyedu AnyThing Typed in senT To porT 80 GT cispoyedu 2 Type in 0 GET HTTP request GET ross HTTP1 1 By Typing This in hiT carriage Host cis poly edu reTurn Twice you send This minimal buT compIeTe GET requesT To HTTP server 3 Look oT response message senT by HTTP server 2 ApplicaTion Layer 36 User server s ra re cookies Many major Web si res Ex ampl e use cookies I Susan always access Four componems In rerne r always from PC 1 cookie header line of CI ViSi l39S specific e HTTP res70 message commerce si re for firs r 2 cookie header line in Time HTTP requesf message o user39s hos r managed by reques rs arrives at Sl l39e user39s browser si re crea res 4 backend daTabase aT Web Sim oz umque ID oz en rry in backend da rabase for ID 2 Applica rion Layer 37 Cookies keepinq s ra re cont clien r server ebay 8734 usual hTTP aqua quot 39 l Amazon server cookie file usuaI h 39p response cr39ea res ID 1 i quot Setcookie 1678 1678 for user cr39eaTe ebay 8734 en l39r39 amazon 1678 s usual hTT r39e uesT ms cooknlllezq1678 g COOkle39 access39 5 4 specific one week later I usual hTTp response msQ action backend daTabase access ebay 8734 usual hTTp r39equesT msg amaz n1673 cookle 1678 cookIe specTific J usual hTTp response msg l action 2 Applica rion Layer39 38 Cookies con rinued Wha r cookies can br inq CI au rhor39iza rion CI shopping car39Ts CI recommendations CI user39 session s ra re Web email How To keep s ra re aside Cookies and privacy CI cookies per39mi r si res To learn a Io r abou r you CI you may supply name and email To si res CI pr39o rocol endpoin rs main rain s ra re a r senderreceiver over39 mul riple rr39ansac rions CI cookies h r rp messages car39r39y s ra re 2 Applica rion Layer39 39 Web caches proxy server Goal saTisfy clienT requesT wiThouT involving origin server I user sets browser origin ser er Web accesses VIa V cache El browser sends a HTTP requesTs To cache 4 objec r in cache cache re rurns objec r 4 else cache reques rs objec r from origin server Then re rurns objec r To clien r o gm server 2 Application Layer 40 More abou r Web caching CI cache ac rs as bo rh Why Web cachinq Clien r Cmd server CI reduce response rime CI Typically cache is for clien r reques r ins ralled by ISP CI reduce Traffic on an Uhiver39si ry company ins ri ru rion39s access residen rial ISP link CI In rerne r dense wi rh caches enables poor con ren r providers To effec rively deliver con ren r bu r so does P2P file sharing 2 Applica rion Layer 41 Caching example Assump rions I I Conseguences I I I origin servers average objec r size 100000 bi rs avg reques r raTe from ins ri ru rion39s browsers To origin servers 15sec delay from insTiTuTional rouTer To any origin server and back To rouTer 2 sec uTilizaTion on LAN 15 uTilizaTion on access link 100 ToTal delay InTerneT delay access delay LAN delay 2 sec minuTes milliseconds insTiTuTional cache 2 Applica rion Layer 42 Caching example con r or39igin pOSSIble SOlU l39th servers I increase bandwidTh of access link To say 10 Mbps conseguence El uTilizaTion on LAN 15 El uTilizaTion on access link 15 El ToTal delay InTer39neT delay access delay LAN delay 2 2 sec msecs msecs El ofTen a cosle upgrade insTiTuTional cache 2 Applica rion Layer39 43 Caching example con r possible solu rion ins rall CI consequence I I I origin servers cache suppose hiT raTe is 04 40 requesTs will be saTisfied almosT immediaTely 60 requesTs saTisfied by origin server uTilizaTion of access link reduced To 60 resulTing in negli ible delays say 10 msecgl ToTal avg delay In rerne r delay access delay LAN dela 6201 secs 4miiseconds lt 4 secs inTiTuTional cache 2 Applica rion Layer 44 Condi rional GET El Goal don39T send objec r if M m cache has upTodaTe cached HTTP requesf msg V r50n Ifmodifiedsince 5 obJeCT CI cache specify daTe of ltdatagt of cached co in HTTP re uesT IfmodifE39Ldsince q HTTP response mOdlfled 4 dategt HTTPl 0 lt 304 Not Modified El server response con rains no ob39ecT if cached co is u Tolldaire W p HTTP requesT msg 39 Ifmodifiedsince HTTP10 304 Not ltdategt object Modified modified HTTP response quot HTTP10 200 OK ltdatagt 2 Applica rion Layer 45 ChapTer 2 Applica rion layer CI 21 Principles of network applica rions CI 22 Web and HTTP CI 23 Electronic Mail oz SMTP POP3 IMAP CI 24 DNS 2 Applica rion Layer 46 Elec rronic Mail Three major componen rs C C C User Agen r C C C ouTgoing message queue E u3errnaHbox user agenTs mail servers simple mail Transfer proTocol SMTP aka mail readerquot composing ediTing reading mail messages eg Eudora Ou rlook elm Mozilla Thunderbird ouTgoing incoming messages sTored on server agenT Elir ii u3er agenT agenT 22Apphca onLayer 47 Elec rronic Mail mail servers Mail Servers El mailbox con rains incoming messages for user I message queue of ou rgoing To be senT mail messages I SMTP pro rocol beTween mail servers To send email messages oz clien r sending mail server 09639 oz quotserverquot receiving mail 7quot 393 USCIquot 2 Applica rion Layer 48 ElecTronic Mail SMTP RFC 2821 El uses TCP To reliably Transfer email message from clienT To server porT 25 El direcT Transfer sending server To receiving server I Three phases of Transfer oz handshaking greeTing oz Transfer of messages 4 closure CI commandresponse inTeracTion oz commands ASCII TexT oz response sTaTus code and phrase CI messages musT be in 7biT ASCII 2 ApplicaTion Layer 49 Scenario Alice sends message To Bob 1 Alice uses UA To compose 4 SMTP clienT sends Alice39s message and To message over The TCP bobsomeschool edu connecTion 2 Alice39s UA sends message 5 Bob39s mail server places The To her mail server message message in Bob39s mailbox Placed in message queue 6 Bob invokes his user agenT 3 Clien r side of SMTP opens To read message TCP connecTion wiTh Bob39s mail server 2 Applica rion Layer 50 Sample SMTP in rer39ac rion 220 hamburgeredu HELO crepesfr 250 Hello crepesfr pleased to meet you MAIL FROM ltalicecrepesfrgt 250 alicecrepesfr Sender ok RCPT TO ltbobhamburgeredugt 250 bobhamburgeredu Recipient ok DATA 354 Enter mail end with quotquot on a line by itself Do you like ketchup How about pickles 250 Message accepted for delivery QUIT 221 hamburgeredu closing connection 2 Application Layer 51 Try SMTP in rerac rion for yourself CI telnet servername 25 CI see 220 reply from server I en rer HELO MAIL FROM RCPT TO DATA QUIT commands above le rs you send email wi rhou r using email clien r reader 2 Applica rion Layer 52 SMTP final words I SMTP uses persis ren r connecTions CI SMTP requires message header amp body To be in 7 D bi r ASCII I I I SMTP server uses CRLF CRLF To de rermine end of message I Comparison wi rh HTTP HTTP pull SMTP push boTh have ASCII command response in rerac rion sTaTus codes HTTP each objec r encapsulaTed in i rs own response msg SMTP mulTiple objec rs sen r in mul ripar r msg 2 Applica rion Layer 53 Mail message for39ma r SMTP pr39o rocol for39 exchanging email msgs RFC 822 sTandard for39 Tex r blicrl relk message forma r CI header lines eg ozo To body ozo Fr39om ozo Subject differer from 5M TP commandsl CI body ozo The message ASCII characTer39s only 2 Applica rion Layer39 54 Message for39ma r mul rimedia ex rensions El MIME mulTimedia mail exTension RFC 2045 2056 El addiTional lines in msg header39 declare MIME con ren r Type From a1icecrepes fr MIME Vers39on To bobhamburgeredu Subject Picture of yummy crepe meThOd used MIMEVersion 1 0 To enCOde dam ContentTransferEncoding base64 mulTimedia daTa 39content39TYPe imagejpeg Type SUbTypel 139ase64 encoded data Parame requot deC39OI OTiOH base64 encoded data encoded daTa 2 Application Layer39 55 Mail access pro rocols SM USCIquot 096m Sender39s mail receiver39s mail Server Server 31 access u3er Lquot pro rocol agen r Bea El SMTP deliverysTorage To receiver39s server I Mail access proTocol reTrieval from server oz POP PosT Office Pro rocol RFC 1939 auThorizaTion agenT ltgtserver and download oz IMAP In rerne r Mail Access Pro rocol RFC 1730 more feaTures more complex manipula rion of s rored msgs on server oz HTTP gmail Honail Yahoo Mail eTc 2 Applica rion Layer 56 POP3 pro rocol au rhoriza rion phase D D rransac rion phasecw D D clienT commands oz user declare username oz pass password server responses OK ERR list lis r message numbers retr re rrieve message by number dele deleTe quit lm O O m m 0 O m m 0 m m m all 9 y 9 9 OK POP3 server ready user bob OK pass hungry OK user successfully logged on list 1 498 2 912 retr 1 ltmessage 1 contentsgt dele 1 retr 2 ltmessage 1 contentsgt dele 2 quit OK POP3 server signing off 22Apphca onLayer 57 POP3 more and IMAP More abou r POP3 CI Previous example uses download and dele requot mode CI Bob canno r reread e mail if he changes clien r CI Downloadandkeepquot copies of messages on differen r clien rs CI POP3 is s ra reless across sessions IMAP CI Keep all messages in one place The server I Allows user To organize messages in folders CI IMAP keeps user s ra re across sessions oz names of folders and mappings be rween message IDs and folder name 2 Applica rion Layer 58 ChapTer 2 Applica rion layer CI 21 Principles of network applica rions CI 22 Web and HTTP CI 23 Electronic Mail oz SMTP POP3 IMAP CI 24 DNS 2 Applica rion Layer 59 DNS Domain Name Sys rem People many iden rifiers Domain Name Sys rem oz SSN name passporT El a isfmbufea dafabase Infernal has rowers implemen red in hierarchy of 4 IP address 32 bi r many quotme sewers used for addressi n9 El appIbafonlayer pro focal hos r rou rers name servers To da ragrams u H commumca re To resove names name 3969quot address name Transla rion nW39yahoo39wm used by oz noTe core In rerne r u ans m func rnon ImplemenTed as 94 quotVIP between IP applicaTionIayer proTocol addresses Grid name complexiTy aT neTwork39s edge 2 Applica rion Layer 60 DNS DNS services CI hos rname ro IP address rransla rion CI hos r aliasing oz Canonical alias names CI mail server aliasing CI load dis rribu rion replica red Web servers se r of IP addresses for one canonical name Why no r cen rralize DNS CI single poin r of failure CI Traffic volume CI dis ran r cen rrali zed da rabase CI main renance does n39T scale 2 Applica rion Layer 61 Dis rribu red Hierarchical Da rabase Root DNS Servers com DNS servers org DNS servers edu DNS servers polyedu umassedu pbsorg DNS serversDNS servers yahoocom amazoncom DNS servers DNS servers DNS servers Clien r wan rs IP for wwwamazoncom 1ST approx CI clien r queries a roof server To find com DNS server I clien r queries com DNS server To ge r amazoncom DNS server CI clien r queries amazoncom DNS server To ge r IP address for wwwamazoncom 2 Applica rion Layer 62 DNS Roo r name servers D con l39ac l39ed by local name server l39ha l39 can no l39 resolve name roo l39 name server con l39ac l39s au l39hori l39a l39ive name server if name mapping no l39 known ge l39s mapping re l39urns mapping l39o local name server a Verisign Dulles ent Herndon VA also LA d U Maryland College Park MD 9 US DoD enna k RIPE London also 16 other locations rdeen MD J Verisign 21 locations e NASA Mt ew CA f Internet Soltware C Palo Alto CA and 36 otherlocation i Autonomica Stockholm plus 8 other locations W m IDE Tokyo also Seoul 39s SF 13 roo l39 name servers worldwide b USCISI Marina del Rey CA ICANN Los Angele 2 Application Layer 63 TLD and Au rhori ra rive Servers CI Toplevel domain TLD servers oz responsible for com org ne r edu e rc and all Toplevel coun rry domains uk fr ca jp oz Ne rwork Solu rions main rains servers for com TLD oz Educause for edu TLD CI Au rhori ra rive DNS servers organiza rion39s DNS servers providing au rhori ra rive hos rname ro IP mappings for organiza rion39s servers eg Web mail oz can be main rained by organiza rion or service provider 2 Applica rion Layer 64 Local Name Server CI does no r s rric rly belong To hierarchy CI each ISP residen rial ISP company universi ry has one oz also called defaul r name serverquot CI when hos r makes DNS query query is sen r To i rs local DNS server oz ac rs as proxy forwards query in ro hierarchy 2 Applica rion Layer 65 DNS name rooT DNS server resolu rion example CI Hos r a r cispoyedu wan rs IP address for gaiacsumassedu i rera red guerx El conTacTed server replies wi rh name of server To con rac r I I don39T know This name buT ask This serverquot TLD DNS server 4 i local DNS serve dnspolIedu auThoriTTie DNS Server dnscsumassedu requesTing hosT cispoyedu gaiacsumassedu 2 Applica rion Layer 66 DNS name PBSOIU I39ion rooT DNS server recursive query CI pu rs burden of name resoluTion on conTacTed name TLD DNS server server 1 I I heavy load local DNS server dnspo edu 4 11 8 auThoriTaTie DNS Server dnscsumassedu requesTing hosT cispoyedu gaiacsumassedu 2 Applica rion Layer 67 DNS caching and upda ring records CI once any name server learns mapping i r caches mapping oz cache en rries rimeou r disappear af rer some rime oz TLD servers Typically cached in local name servers Thus rooT name servers noT ofTen visiTed CI upda reno rify mechanisms under design by IETF oz RFC 2136 ozo hTTpwwwieTforghTmcharTersdnsindcharTerhTm 2 Applica rion Layer 68 DNS records DNS dis rribu red db s roring resource records RR RR forma r name value type ttl CI TypeA CI TypeCNAME 4 name is hOSTnOme oz name is alias name for some oz value is IP address quotcanonicalquot The real name 39b is reall D WW 1 m com y servereastbackup2lbmcom oz name is domain eg oz value is canonical name foocom Q value is hos rname of D TypeMX auThoriTaTive name value is na e o ailserver server for This domain m f m associaTed wiTh name 2 Applica rion Layer 69 DNS protocol messaqes DNS protocol query and repy messages both with same message format nixrum alli39ulil listen T msg header D iden fica on39 16 b qulu39lwl quHIli lAE 411an Mm it llbyteg for query reply to query WM I L uses same El flags o query or reply o recursion desired 439 recursion available o reply is authoritative 2 Application Layer 70 DNS pr39o rocol messaqes Name Type fields for a query RRs in response To query records for au rhori ra rive servers addi rional quothelpfulquot info Tha r may be used 2 Application Layer 71 Inser ring records in ro DNS CI example new s rar rup Ne rwork U ropiaquot CI regis rer name ne rworku ropiacom a r 0N5 regsfrar eg Ne rwork Solu rions oz rovide names IP addresses of au rhori ra rive name server primary and secondary oz regis rrar inser rs Two RRs in ro com TLD server networkutopiacom dnslnetworkut0piacom NS dnslnetworkutopiacom 212212212l A El crea re au rhori ra rive server Type A record for wwwne rworkup ropiacom Type MX record for ne rworku ropiacom CI How do people ge r IP address of your Web si re 2 Applica rion Layer 72 Chapter 2 Summary our study of network apps now complete CI application architectures Cl Specific protocols oz clientserver 4 HTTP CI application service quot SMTP POP IMAP requirements 4 DNS o reliability bandwidth delay CI Internet transport service model oz connectionoriented reliable TCP oz unreliable datagrams UDP 2 Application Layer 73 m In rr39oduc rion To Compu rer39 Ne rwor39ks and Da ra Communica rions Chapter 1 In rr39oduc rion Sachin She r ry In rr39oduc rion 11 ChapTer 1 InTroducTion Our goal El geT quotfeelquot and Terminology El more depTh deTaiI lafer in course El approach oz use InTerneT as example Overview El whaT39s The InTerneT El whaT39s a proTocoI El neTwork edge hosTs access neT physical media El neTwork core packeTcircuiT swiTching InTerneT sTrucTure El performance loss delay ThroughpuT El proTocoI layers service models InTroducTion 12 Chapter 1 roadmap 11 What is the Internet 12 Network edge El end systems access networks links 13 Network core El circuit switching packet switching network structure 14 Delay loss and throughput in packetswitched networks 15 Protocol layers service models Introduction 13 Wha r39s The In rerne r nu rs and bol rsquot view PC El millions of connec red Mobile nework quot quot compu ring devices hosfs end sysfems a running nefwork 39 handheld apps El commum39ca on links cf access oz fiber copper pm radio so relli re quotks oz Transmission ro re bandwdfh El rowers forward mumquot packe rs chunks of do ro In rroduc rion 14 Cool interne r appliances Webenabled toaster weather forecaster IP picture frme httpwwwceivacom r H 77W J World s smal est web server httpwwwccscsumassedushriiPichtm Internet phones Introduction 15 Wha r39s The In rerne r nu rs and bol rsquot view El profocos con rrol sending M blle almrk receiving of mSgs eg TCP IP HTTP Skype ETherneT El Infernef ne rwork of ne rworksquot loosely hierarchical oz public In rerne r versus priva re inTraneT El In rerne r s randards oz RFC Reques r for commen rs oz IETF In rerne r Engineering Task Force Global ISP In rroduc rion 16 What39s the Internet a service view El communication Infrastruc fare enables distributed applications oz Web VoIP email games ecommerce file sharing El communication services provided to apps oz reliable data delivery from source to destination oz best effortquot unreliable data delivery Introduction 17 What39s a protocol human protocols network protocols El what39s the timequot El machines rather than El I have a questionquot humans El introductions El all communication activity in Internet specific msQS sent governed by Pr39OJTOCOIS specific actions taken protocols define format When mSgS Pecelved order of msgs sem and or39 other events received among network en fites and ac ans taken on msg transmission r39ecepf Introduction 18 What39s a protocol a human protocol and a computer network protocol Wm 7 reques 6 TCP connect n Got the quotresponse tune Get htt wwwawcomkur oser39oss ltfiegt Q Other human protocols Introduction 19 Chapter 1 roadmap 11 What is the Internet 12 Network edge El end systems access networks links 13 Network core El circuit switching packet switching network structure 14 Delay loss and throughput in packetswitched networks 15 Protocol layers service models Introduction 110 A closer look at network structure El network edge applications and hosts El access networks physical media wired wireless communication links El network core oz interconnected routers oz network of networks Introduction 111 The ne rwork edge El end sys rems hos rs oz run applica rion programs oz eg Web email aT edge of neTworkquot El clien rserver model clienT hosT requesTs receives service from alwayson server oz eg Web browserserver Chemwar email clienTserver El peerpeer model o minimal or no use of dedicaTed servers oz eg Skype BiTTorrenT peerpeer In rroduc rion 112 NeTwork edge reliable daTa Transfer service 60039 daTa Transfer beTween end sysTems El handshakng seTup prepare for daTa Transfer ahead of Time oz Hello hello back human proTocol oz sef up quot57 a7 e in Two communicaTing hosTs El TCP Transmission ConTrol ProTocol oz InTerneT39s reliable daTa Transfer service TCP service RFC 793 El relable I39nora er byTe sTream daTa Transfer oz loss acknowledgemenTs and reTransmissions El flow cam ror oz sender won39T overwhelm receiver El conges on cam ror oz senders slow down sending raTequot when neTwork congesTed InTroducTion 113 NeTwork edge besT efforT unreliable daTa Transfer service 60 01 daTa Transfer App39s usinq TCP be rween end SYS remS a HTTP Web FTP file oz same as before Transfer Telne l El UDP User DaTagram remoTe login SMTP ProTocol RFC 768 email oz connecTionless oz unreliable daTa App39s usinq UDP Transfer El sTreaming media 1 no flOW CONTr Ol Teleconferencing DNS oz no congesTion conTrol InTerneT Telephony InTroducTion 114 Access networks and physical media Q How 7 0 connect end systems 7 0 edge router El residential access nets El institutional access networks school company El mobile access networks Keep in mind El bandwidth bits per second of access network El shared or dedicated Introduction 115 ResidenTial access poinT To poinT access El Dialup via modem oz up To 56 Kbps dir39ecT access To r39ouTer39 ofTen less oz Can T surf and phone aT same Time can39T be always onquot El digiTal subscriber line oz deploymenT Telephone company Typically oz up To 1 Mbps upsTr39eam Today Typically lt 256 kbps oz up To 8 Mbps downsTr39eam Today Typically lt 1 Mbps oz dedicaTed physical line To Telephone cenTr39al office InTr39oducTion 116 Residential access cable modems El HFC hybrid fiber39 coax oz asymmetric up to 30Mbps downstream 2 Mbps upstream El network of cable and fiber39 attaches homes to ISP router oz homes shar39e access to router El deployment available via cable TV companies Introduction 117 Residential access cable modems Fiber Optic Transport If m x myan Pm hummum m Dwagram munWWWab edatacumnewsumcmmmagram mm Introduction 17 Cable Network Ar39chi39recfur39e Overview Typically 500 ro 5000 homes imWmim cable distribution home network simplified cable headend Infroduc rion 119 Cable Ne rwork Architecture Overview III oable headend T g T cable distribution network In rr39oduc rion 120 Cable Network Ar39chi39recfur39e Overview semop Box Home Environmem Modem PC 313 V ll Mhps Eihamei Spliuer cable distribution home network simplified Infroduc rion 121 Cable Network Ar39chi39recfur39e Overview FDM more shortly W W Y Y Y Y Y Infroduc rion 122 Company access local area networks El componyuniv local area network LAN connects and system to edge router El Ethernet oz 10 Mbs lOOMbps IGbps lOGbps Ethernet oz modern configuration and systems connect into Ethernet switch El LANs chapter 5 Introduction 123 Wireless access ne rworks El shared WIrees39s39 access ne rwork connec rs end sys rem l ro rou rer rower via base sTaTion aka access Co pom rquot base amp El wireless LANs Samarion oz 80211bg WiFi 11 or 54 Mbps El widerarea wireless access oz provided by Telco operaTor oz 1Mbps over cellular sys rem EVDO HSDPA nexT up 9 WiMAX 1039s Mbps over wide area In rroduc rion 124 Home ne rworks Typical home ne rwork componen rs El DSL or cable modem El rou rerfirewallNAT El E rherne r El wireless access poi n r wireless Tofrom lap rops cable rouTer cable headend modem firewall Wireless access E rherne r poim In rroduc rion 125 Physical Media Twisted Pair TP El Bit propagates between a two insulated copper transmitterrcvr pairs wires El phy5ical link what lies 4 category 31 admonai between transmitter amp phone wires 10 Mbps receiver Ethernet El guided media quot calegory 5 IOOMbps Ethernet oz Signals propagate in solid media copper fiber coax El unguided media signals propagate freely eg radio Introduction 126 Physical Media coax fiber Coaxial cable Fiber optic cable D TWO concemric copper El glass fiber carrying light conductors pulses each pulse a bIt El bidirectional El highspeed operation El baseband oz highspeed pointtopoint oz single channel on cable Tra smlsslon eg 1039s legacy Ethernet 1005 Gps a broadband El low error rate repeaters multiple channels on Spaced for aparl immune cable to electromagnetic noise HFC Ev Introduction 127 Physical media radio El signal carried in Radquot l39nk Types electromagnetic El terrestrial microwave spectrum oz eg up to 45 Mbps channels El no physical wire El LAN eg Wifi El bidirectional 4 Mbps 54 Mbps D propaga on El widearea eg cellular environment effects 1 3G cellular quot 1 Mbps oz reflection El satellite oz obstruction by objects oz Kbps to 45Mbps channel or z interference multiple smaller channels 270 msec endend delay geosynchronous versus low altitude Introduction 128 Chapter 1 roadmap 11 What is the Internet 12 Network edge El end systems access networks links 13 Network core El circuit switching packet switching network structure 14 Delay loss and throughput in packetswitched networks 15 Protocol layers service models Introduction 129 The Ne rwork Core El mesh of in rerconnec red routers El iefundomen rol ques rion how is da ra Transferred Through ne r oz circui r swi rching dedico red circui r per call Telephone ne r ozo pocketswi rching do ro sen r rhru ne r in discre re chunks In rroduc rion 130 Network Core Circuit Switching Endend resources reserved for call El link bandwidth switch capacity El dedicated resources no sharing El circuitlike guaranteed performance El ca setup required Introduction 131 Ne rwork Core Circui r Swi rching ne rwork resources a dividing link bandwid rh 89 bondwid rh in ro pieces divided in ro pieces oz frequency division El pieces olloco red To calls ozo Time division El resource piece I39de if no r used by owning call no sharing In rroduc rion 132 Circui r Swi rching FDM and TDM Example 4 users I I FDM frequency jfffj if If j 39 ijj 73 time TDM frequency time In rr39oduc rion 133 Numerical example El How long does i r Take To send a file of 640000 biTs fr39om hos r A To hos r B over39 a cir39cui rswi rched ne rwor39k oz All links are 1536 Mbps oz Each link uses TDM wi rh 24 slo rssec oz 500 msec ro es roblish endToend circui r Le r39s work if ou r In rr39oduc rion 134 Ne rwork Core Packe r Swi rching each endend da ra s rream resource confen rion divided i n ro packefs D aggregafe resource El user A B packe rs share demand can exceed ne rwork resources amoun r available El each packe r uses fu link El conges rion packe rs bandwid rh queue waif for link use El resources used as needed El s rore and forward packe rs move one hop a r a Time ozo Node receives complefe packef before forwarding Infroduc rion 135 Packet Switching Statistical Multiplexing 100 Mbs Ether net sfafllsfica mufpexing 7 15 Mbs queue of packets waiting for output link Sequence of A amp B packets does not have fixed pattern bandwidth shared on demand sfa s ca mufpexing TDM each host gets same slot in revolving TDM frame Introduction 136 Packe r swi rching s rore andforward El rakes L R seconds To Examgle rransmi r push OUT I L 75 Mbi rs acke r of L bi rs on To Fink a r R bps D R 39 1395 Mbps El Transmission delay 15 El sfore and forward sec en rire packe r mus r arrive a r rou rer before if can be rransmi r red on nex r link Cl delay 3LR fissuming more on delay shorle zero propaga rlon delay In rroduc rion 137 PackeT swiTching versus cir39cuiT swiTching Packef swfchng allows more users f0 use ne fworc El 1Mbs link El each user39 100 kbs when acTive oz acTive 10 of Time El circuif swfchhg 10 users El packef swfchng o fb l ie lo ac ve Q how did we geT value 00004 aT same Time is less Than 0004 1Mbps link InTr39oducTion 138 Packe r swi rching versus circui r swi rching Is packe r swi rching a slam dunk winnerquot El grea r for burs ry da ra oz resource sharing oz simpler no call se rup El excessive conges rion packe r delay and loss oz pro rocols needed for reliable da ra Transfer conges rion con rrol El Q How To provide circui rlike behavior oz bandwid rh guaran rees needed for audiovideo apps oz s rill an unsolved problem Q human analogies of reserved resources circuiT swiTching versus ondemand allocaTion packeTswiTching Infroduc on L39 In rerne r s rruc rure ne rwork of ne rworks El roughly hierarchical El a r cen rer Tier1quot ISPs eg Verizon Sprin r ATampT Cable and Wireless na rionalin rerna rional coverage oz rrea r each o rher as equals Tier1 pr OVlde 1 inTerconnecT Pr39vm39y Tier 1ISP Tier 5P In rroduc rion 140 Tier1 ISP eq SprinT POP pointof presence tofrom backbone Infroducfion 141 In rerne r s rruc rure ne rwork of ne rworks El Tier2quot ISPs smaller of ren regional ISPs oz ConnecT To one or more Tier1 ISPs possibly oTher Tier2 ISPs Tier2 ISPs 39 so peer Tier2 ISP pays 0 Tier1 ISP for Egzv zilzenllfh connecTiviTy To resT of InferneT El Tier2 ISP is cusfomerof Tier1 provider 0 Tier 1 ISP In rroduc rion 142 Inter39net structure network of networks El Tier3quot ISPs and local ISPs oz lost hop quotaccessquot network closest to end systems Local and tier 3 ISPs are customers of higher tier39 ISPs connecting them to rest of Internet Introduction 143 In rer39ne r s rr39uc rur39e network of ne rwor39ks El a packe r posses rhr ough many ne rwor39ks In rr39oduc rion 144 Chap rer 1 roadmap 11 Wha r is The In rer ne r 12 Ne rwor39k edge El end sysTems access neTworks links 13 Network cor39e El cir cui r swi rching packeT swiTching ne rwor39k sTrucTure 14 Delay loss and Throughpu r in packe rswi rched ne rwor39ks 15 Protocol layers ser39vice models In rr39oduc rion 145 How do loss and delay occur packe rs queue in rou rer buffers El packe r arrival ra re To link exceeds ou rpu r link capaci ry El packe rs queue wai r for rurn packeT being TransmiTTed delay DC packeTs queueing delay free available buffers arriving packeTs dropped loss if no free buffers In rroduc rion 146 Four sources of packe r delay queueing o Time waiTing aT oquuT link for Transmission oz depends on congesTion level of rouTer oz check bi r errors deTermine oquuT link El 1 nodal processing El 2 x lt pro pagaTion gt nodal processing queueing In rroduc rion 147 Delay in packet switched networks 3 Transmission delay 4 Propagation delay El Rink bandwidth bps El d length of physical link El Lpacket length bits El s propagation speed in a time to send bits into medium 2gtlt108 mSec link LR El propagation delay ds Note s and R are very different quantities a r transnnsion A I lt propaga on 39gtgtC x 4 D nodal processing queueing Introduction 148 Caravan analogy a V 39i en39wquot Toll Toll caravan booTh booTh El cars propagaTe aT 100 km hr El To booTh Takes 12 sec To service car Transmission Time El carbiT caravan packeT El Q How long unTiI caravan is lined up before 2nd Toll booTh El Time To push enTire caravan Through Toll booTh onTo highway 1210 120 sec El Time for asT car To propagaTe from lsT To 2nd To boTh 100km100kmhr 1 hr El A 62 minuTes InTroducTion 149 Caravan analogy more o o o 100 km a V i Tencar 10 COPOVOH booTh El Car39s now propaga re a r 1000 kmhr39 El Toll boo rh now Takes 1 min To service a car39 El Q Will car39s ar39r39ive To 2nd boo rh before all cars ser39viced a r ls r booTh 100 km L A V V Toll booTh El Yes Af rer39 7 min ls r car39 a r 2nd boo rh and 3 cars s rill a r ls r boo rh El ls r bi r of packe r can arrive a r 2nd r39ou rer39 befor39e packe r is fully Transmi r red a r ls r r39ou rer39 oz See E rherne r apple r a r AWL Web si re Introduction 150 Nodal delay d d d d d nodal proc queue trans prop El dpr0C processing delay oz Typically a few microsecs or less El dqueue queuing delay oz depends on congestion El dmns Transmission delay oz LR significant for lowspeed links El lprop propagation delay oz a few microsecs to hundreds of msecs Introduction 151 quotRealquot InTerneT delays and rouTes El WhaT do real InTerneT delay amp loss look like El Traceroute program provides delay measuremenT from source To rouTer along endend InTerneT paTh Towards desTinaTion For all f sends Three packeTs ThaT will reach rouTer ion paTh Towards desTinaTion oz rouTer iwill reTurn packeTs To sender oz sender Times inTerval beTween Transmission and reply InTroducTion 152 quotRealquot In rerne r delays and rou res Tracerou re gaiacsumassedu ro wwweurecomfr Three delay measuremenTs from gaiacsumassedu To csgwcsumassedu csgw128119240254 1 ms 1 ms 2 ms border1rtfa510gwumassedu 1281193145 1 ms 1 ms 2 ms cht vbnsgwumassedu 1281193130 6 ms 5 ms 5 ms jn1at10019worvbnsnet 204147132129 16 ms 11 ms 13 ms jn1so7000waevbnsnet 204147136136 21 ms 18 ms 18 ms abilenevbnsabileneucaidedu 19832119 22 ms 18 ms 22 ms nycmwashabileneucaidedu 19832846 22 ms 22 ms 22 ms Transoceanlc 6240103253 6240103253 104 ms 109 ms 106 ms I k de21de1degeantnet 624096129 109 ms 102 ms 104 ms m 0 defr1frgeantnet 62409650 113 ms 121 ms 114 ms 1 renater gwfr1frgeantnet 624010354 112 ms 114 ms 112 ms 2 nion2cssirenaterfr 1935120613 111 ms 114 ms 116 ms 3 nicecssirenaterfr 19522098102 123 ms 125 ms 124 ms 14 r3t2nicecssirenaterfr 19522098110 126 ms 126 ms 124 ms 15 eurecomvalbonner3t2ftnet 193485054 135 ms 128 ms 133 ms 16 19421421125 19421421125 126 ms 128 ms 126 ms 17 N 18 means no response probe osT rouTer noT replying 19 fantasiaeurecomfr19355113142 132 ms 128 ms 136 ms AAA LOGJNOUCJ IFOONA In rroduc rion 153 PackeTloss El queue aka buffer preceding link in buffer has fini re capaci ry El packe r arriving To full queue dropped aka Ios r CI Ios r packe r may be re rransmi r red by previous node by source end sys rem or no r a r a buffer wamng area packeT being TransmiTTed packef arriving To full buffer is 057 In rroduc rion 154 Throughpu r El fhroughpuf rafe bifsfime unif of which bi rs Transferred be rween sender receiver oz Msfanfaneous ra re a r given poinf in Time oz average ra re over longer period of Time server sends bits pipe fha r can carry pipe fha r can carry fluid info pipe fluid aT ra re fluid aT ra re R3 bi rssec RC bi rssec Infroducfion 155 Throughput more El RS lt RC What is average endend throughput bottleneck link link on endend path that constrains endend throughput Introduction 156 Throuthu r InI39er39ne l39 scenario CI perconnection endend Throughpuf minRCRSR10 CI in prodice RC or Rs is often boT Heneck 10 connections fairly share backbone bo 39leneck link R bi l39sSec In l39r39oduc l39ion 157 Chapter 1 roadmap 11 What is the Internet 12 Network edge El end systems access networks links 13 Network core El circuit switching packet switching network structure 14 Delay loss and throughput in packetswitched networks 15 Protocol layers service models Introduction 158 ProToco Layersquot Ne rwor39ks are complex El many quotpiecesquot 4 hOS rS Ques rion 1 r39OU39fer39S Is There any hope of oz links of various organizing structure of media ne rwor k oz applica rions ozo pr39o rocols Or39 a r eas r our39 discussion 4 hardware Of ne rwor39ks sof rwar39e In rr39oduc rion 159 Organiza rion of air Travel Ticke r purchase Ticke r complain n baggage check baggage claim gaTes load gaTes unload runway Takeoff runway landing airplane rouTing airplane rouTing airplane rouTing El a series of s reps In rroduc rion 160 Layering of airline functionality departure intermediate airtraf c arrival airport control centers airport Layers each layer implements a service oz via its own i nternaIIayer actions oz relying on services provided by layer below Introduction 161 Why layering Dealing with complex systems El explicit structure allows identification relationship of complex system39s pieces oz layered reference model for discussion El modularization eases maintenance updating of system oz change of implementation of layer39s service transparent to rest of system oz eg change in gate procedure doesn39t affect rest of system El layering considered harmful Introduction 162 Internet protocol stack El application supporting network applications applica on oz FTP SMTP HTTP El transport processprocess data Transport transfer TCP UDP network El network routing of datagrams from source to destination link oz IP routing protocols El link data transfer between PhYSlCGl neighboring network elements oz PPP Ethernet El physical bits on the wire Introduction 163 ISOOSI reference model El presentation allow applications to interpret meaning of data eg appica on encryption compression machine specific conventions Presenthquot El session synchronization 535539 checkpointing recovery of data fransporf exchange network El Internet stack missingquot these layers l39nk oz these services if needed must h sical be implemented in application oz needed Introduction 164 SOIPCB meSSage SegmemL Hfl M daTagr39am Hn Hf M frame IHI Hn H M in lphysical 3c switch des m on ne rwor39k pplicaTion H Hn H M link Hn Hf IM H M transport phySIcal ii neTwor39k IFI Hn H M link router In rr39oduc rion 165 Chapter 1 roadmap 11 What is the Internet 12 Network edge El end systems access networks links 13 Network core El circuit switching packet switching network structure 14 Delay loss and throughput in packetswitched networks 15 Protocol layers service models Introduction 166 Chap rer39 4 Ne rwork Layer Ne rwor39k Layer 4 1 Chap rer 4 Ne rwork Layer Chap rer qoals CI unders rand principles behind ne rwork layer S PVIC S O ne rwork layer service models 0 forwarding versus rou ring 0 how a rou rer works 0 rou ring pa rh selec rion O dealing wi rh scale 0 advanced ropics IPv6 mobili ry CI ins ran ria rion implemen ra rion in The In rerne r Ne rwork Layer 42 Chap rer 4 Ne rwork Layer CI 4 1 In rroduc rion CI 44 Rou ring algori rhms CI 42Wha r39s inside a 0 Link sTaTe rou rer O DisTance Vec ror D 43 IP Internal 0 Hierarchical rouTing Protocol CI 45 Rou ring in The O DaTagram forma r In39l39er39he l39 0 IPv4 addressing 0 RIP 0 ICMP 0 IPv6 Ne rwork Layer 43 Ne rwork layer CI rranspor r segmen r from sending ro receiving hos r CI on sending side encapsula res segmen rs in ro da ragrams CI on rcving side delivers segmen rs ro rranspor r layer CI ne rwork layer pro rocols in every hos r rou rer CI rou rer examines header fields in all IP da ragrams passing Through it a lica rion Transor lt ne rwork ne rwork a ne rwork I ne rwork physical ne rwork physical ne rwork i physical physical ne rwork physical ne rwork physical 3 Ne rwork Layer 44 Two Key Ne rwork Layer Func rions CI forward g move analogy packe rs from rou rer39s inpu r To appropria re rou rer ou rpu r CI rou ring process of planning Trip from source To des r CI muff7g de rermine rou re Taken by D forwardlng Pr39OCeSS packe rs from source of geTTing Through To dest snngle In rerchange O muff79 algaquotth Ne rwork Layer 45 In rer39play be rween routing and forwarding routing algorithm local forwarding table header value value in arriving packet s header Ne rwor39k Layer 46 Router Architecture Overview Two key router functions I run routing algorithmsprotocol RIP OSPF BGP El forward g dotogroms from incoming to outgoing link input port output port switching O O O 0 input port 13an output port A routing processor Network Layer 47 Input Port Functions lookup forwarding switch l39 termthTion I decapsmangny queueing fabric data link Physical layer bitlevel reception Data link layer Decentralized switching egl Ethernet El given datagram dest lookup output port see chapter 5 using forwarding table in input port memory I goal complete input port processing at ine speed39 I queuing if datagrams arrive faster than forwarding rate into switch fabric Network Layer 48 Thr39ee Types of swifching fabrics A llIIlgt B IIlllmmlgt C IIlllmml memory bus A IIllmmIlgt B HZDW crossba r C EIEIIJIIJIEP III I NeTwor39k Layer39 49 Switching Vio Memory Firs r generation rou rers CI Traditional computers with switching under direc r control of CPU Clpacke r copied To system39s memory CI speed limi red by memory bandwidth 2 bus crossings per do rogrom Input Memory Output Port Port System Bus Ne rwork Layer 410 SWiTching Via a Bus CI daTagram from inpuT por139 memory I39o output port memory via a shared bus CI bus conTenTion swiTching speed limi l39ed by bus bandwid l39h CI 32 Gbps bus Cisco 5600 sufficien l39 speed for access and en l39erprise rouTers NeTwork Layer 4 11 Switching Via An Interconnection Network CI overcome bus bandwidth limitations CI Banyan networks other interconnection nets initially developed to connect processors in multiprocessor CI advanced design fragmenting datagram into fixed length ces switch cells through the fabric CI Cisco 12000 switches 60 Gbps through the interconnection network Network Layer 412 OquuT PorTs SWItCh queuing data i k processmg fabric buffer protocol line L management x termination decapsulaiion El Buffer g required when daTagrams arrive from fabric fasTer Than The Transmission raTe El SchedUMg dsc439nme chooses among queued daTagrams for Transmission NeTwork Layer 413 Ou rpu r por r queueing 3quot 39 If F D aquot E ne Faekei Time Late r impu Farr Conrerlaian cl Time r CI buffering when arrival ra re via swi rch exceeds ou rpu r line speed CI queueing delay and loss due 7 0 oufpuf pom buffer overflow Ne rwork Layer 414 How much buffering CI RFC 3439 Me of Thumb average buffering equal To quotTypicalquot RTT say 250 msec Times link capaci ry C O eg C 10 Gps link 25 Gbi r buffer CI Recen r recommenda rion wi rh Nflows buffering equal To RTT C N Ne rwor39k Layer39 415 Input Por39l39 Queuing CI Fabric slower Than input ports combined gt queueing may occur at input queues CI Head of I he Line HOL blocking queued datagram at front of queue prevents others in queue from moving forward CI queueing delay and loss due 1390 I39npuf bufferquot 0 ver39fo w bl Ell switch fabric Il gt output port contention green packet at time t only one red experiences HOL blocking packet can be transferred Network Layer 4 16 Chapter 4 Network Layer CI 4 1 Introduction CI 45 Routing algorithms CI 42 Virtual circuit and 0 Link state datagram networks 0 Distance Vector g 43 When395 inside a O Hierarchical routing router CI 46 Routing in the CI 44 IP Internet Infernal Protocol 0 RIP 0 Datagram format 0 OSPF 0 IPv4 addressing O BGP O ICMP CI 47 Broadcast and 0 IPv6 multicast routing Network Layer 417 The In rerne r Ne rwork layer Hos r rou rer ne rwork layer functions Roufing proTocols l paTh SelecTion Network RIP OSPF BGP layer K l Transporl layer TCP UDP IP proTocol addressing convenTions daTagram forma r packeT handling convenTions ICMP proTocol error reporting rouTer quotsignalingquot Link layer physical layer Ne rwork Layer 418 Chapter 4 Network Layer CI 4 1 Introduction CI 45 Routing algorithms CI 42 Virtual circuit and 0 Link state datagram networks 0 Distance Vector g 43 When395 inside a O Hierarchical routing router CI 46 Routing in the CI 44 IP Internet Infernal Protocol 0 RIP 0 Datagram format 0 OSPF 0 IPv4 addressing O BGP O ICMP CI 47 Broadcast and 0 IPv6 multicast routing Network Layer 419 IP daTaqram formaT IP proTocol version number headerlengTh byTes Type of daTa 32 biTs Type of Jar r lservice lenglh ToTal daTagram lengTh byTes for 16biT idenTifier MI fragmenT 3 max number remaining hops lime To upper live layer header checksum decremenTed aT each rouTer 32 biT source IP address ragmenTaTion reassembly upper layer proTocol 32 biT desTinaTion IP address To deliver payload To OpTions if any Eg TimesTamp record rouTe how much overhead wiTh TCP El 20 byTes of TCP El 20 byTes of IP CI 40 byTes app layer overhead daTa variable lengTh Typically a TCP or UDP segmenT Taken specify lisT of rouTers To visiT NeTwork Layer 420 IP Fragmen ra rion amp Reassembly El neTwork links have MTU maxTransfer size largesT possible linklevel frame 0 different link Types differenT MTUs El large IP daTagram divided fragmented wiThin net 0 one daTagram becomes several daTagrams O reassembled only aT final desTinaTion 0 IP header biTs used To idenTify order relaTed fragmenTs one large dafagram 3 smaller dafagrams Ne rwork Layer 421 IP Fragmentation and Reassembly l length ID fragflag offset 3 Examgle 4000 x o 0 El 4000 byte datagram El MTU 1500 bytes One large datagram becomes several smaller datagrams J lengTh ID fragflag offset x 1 0 data field I length ID fragflag offset 15OQx 21 quot2185 offseT 14808 length ID fragflag offset llllll 1040 x O 370 Network Layer 422 Chapter 4 Network Layer CI 4 1 Introduction CI 45 Routing algorithms CI 42 Virtual circuit and 0 Link state datagram networks 0 Distance Vector g 43 When395 inside a O Hierarchical routing router CI 46 Routing in the CI 44 IP Internet Infernal Protocol 0 RIP 0 Datagram format 0 OSPF 0 IPv4 addressing O BGP O ICMP CI 47 Broadcast and 0 IPv6 multicast routing Network Layer 423 CI IP address 32bit identifier for host router interface CI interface connection between hostrouter and physical link 0 router39s Typically have multiple interfaces 0 host Typically has one interface 0 IP addresses associated with each 223111 I11011111Ip0000001lp0000001l p0000001l interface 223 1 1 1 Network Layer 424 Subne rs CI IP address 0 SubneT parT high order bi rs o hos r par r low order bi rs CI Whaffs a subnef 7 0 device in rer39faces wiTh same subne r par r of IP address 0 can physically reach each oTher wi rhou r infervenmg rower neTwork COHSISTlng of 3 subneTs Ne rwork Layer 425 Subne rs M CI To determine The subne rs de rach each i n rer39face from i rs hos r or39 r39ou rer39 cr ea ring islands of isola red ne rwor39ks Each isola red network is called a subne r 22311024 2231 2024 2231 3024 Subne r mask 24 Network Layer 426 Subne rs How many Ne rwor39k Layer 427 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 14 hosT part parT 11001000 00010111 00010000 00000000 2002316023 Ne rwor39k Layer39 428 IP addresses how To ge r one Q How does hosf ge r IP address CI hardcoded by sys rem admin in a file 0 Win rel con rropane gtne rworkgtconfigura rion gtTcpipgtproper ries O UNIX e rcrcconfig CI DHCP Dynamic Hos r Configuration Pro rocol dynamically ge r address from as server 0 plugandplayquot Ne rwork Layer 429 DHCP Dynamic Hos r Confiqura rion Pro rocol Goal allow hos r ro dynamI39cabob rain i rs IP address from ne rwork server when if joins ne rwork Can renew i rs 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 shor rly DHCP overview O hos r broadcas rs DHCP discoverquot msg O DHCP server responds wi rh DHCP offerquot msg O hos r reques rs IP address DHCP reques rquot msg O DHCP server sends address DHCP ackquot msg Ne rwork Layer 430 DHCP clien r ser39ver39 scenario arriving DHCP Client needs address in this network Ne rwor39k Layer 431 DHCP client server scenario DHCP Server 223125 Time DHCP discover arriving client src 0000 68 dest 25525525525567 yiaddr 0000 transaction ID 654 v DHCP offer src 2231 25 67 dest 255255255255 68 yiaddrr 2231 24 transaction ID 654 Lifetime 3600 secs DHCP request src 0000 68 dest 255255255255 67 yiaddrr 2231 24 transaction ID 655 k Lifetime 3600 secs DHCP ACK src 2231 25 67 dest 255255255255 68 yiaddrr 2231 24 transaction ID 655 Lifetime 3600 secs Layer 432 IP addresses how To get one Q How does nefwork get subne r port of IP oddr gets allocated portion of its provider ISP39s address space ISP39s block Organization 0 Organization 1 Organization 2 Organization 7 1 1001000 0001011 1 00010000 00000000 11001000 000101 11 00010000 00000000 11001000 00010111 00010010 00000000 11001000 00010111 00010100 00000000 11001000 00010111 00011110 00000000 2002316020 2002316023 2002318023 2002320023 2002330023 Network Layer 433 Hierarchical addressing route aggregation Hierarchical addressing allows efficient advertisement of routing information Organization 0 Send me anything with addresses beginning 2002316020quot 1L39uernet Send me anything with addresses beginning 199310016quot Network Layer 434 Hierarchical addressing more specific routes ISPsRUs has a more specific route to Organization 1 Organization 0 Send me anything with addresses beginning 2002316020quot Send me anything with addresses beginning 199310016 or 2002318023quot Network Layer 435 IP addressing The las r word Q How does an ISP ge r block of addresses ICANN In rerne r Corpora rion for Assigned Names and Numbers 0 alloca res addresses 0 manages DNS 0 assigns domain names resolves dispu res Ne rwork Layer 436 NAT Ne rwork Address Transla rion lt resT of local neTwork InferneT eg home network 100024 10001 10002 1 13876297 10003 AdaTagrams eav7q 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 por r numbers source des rina rion as usual Ne rwork Layer 437 NAT Ne rwork Address Transla rion CI Mo riva rion local ne rwork uses jus r one IP address as far as ou rside world is concerned 0 range of addresses no r needed from ISP jus r one IP address for all devices 0 can change addresses of devices in local ne rwork wi rhou r no rifying ou rside world 0 can change ISP wi rhou r changing addresses of devices in local ne rwork 0 devices inside local ne r no r explici rly addressable visible by ou rside world a securi ry plus Ne rwork Layer 438 NAT Network Address Translation Implementation NAT router must O outgoing dafagrams repace source IP address port of eveg outgoing datagram to NAT IP address new port remote clientsservers will respond usin NAT IP address new port as destination ad r O remember in NA 739 translation fatal every source IP address port to NAT IP ad ress new port translation pair 0 incoming dafagrams repace NAT IP address new port in dest fields of ever incoming datag ram with corresponding source I address port stored in NAT tab e Network Layer 439 NAT Ne rwork Address Transla rion NAT TranslaTion Table 2 NAT mumquot WAN side addr LAN side addr L hOST 10390390391 changes Clcn gram 13876297 5001 10001 3345 source addr from 39 10001 3345 To 13876297 5001 updaTes Table sends daTagram To 12811940186 8O S 10001 3345 D 12811940186 80 5 1387629 5001 D 12811940186 80 13876297 5 12811940186 30 D 1387629 5001 i Reply amves changes daTagram desT address desT addr from 138762971 5001 138762975001To 10001 3345 4 NAT rouTer Ne rwork Layer 440 NAT Network Address Translation CI 16bit portnumber field 0 60000 simultaneous connections with a single LANside address CI NAT is controversial O routers should only process up to layer 3 O violates endtoend argument NAT possibility must be taken into account by app designers eg P2P applications 0 address shortage should instead be solved by IPv6 Network Layer 441 NAT Traversal problem CI clien r wan r ro connec r ro server wi rh address 10001 0 server address 10001 local To LAN clienT can39T use if as desTinaTion addr 0 only one exTernally visible NATTed address 13876297 CI solu rion 1 s ra rically configure NAT ro forward incoming connec rion reques rs a r given por r ro server 0 eg 12376297 por r 2500 always forwarded To 10001 porT 25000 Ne rwork Layer 442 NAT Traversal problem CI solu rion 2 Universal Plug and Play UPnP In rerne r Gateway Device IGD Pro rocol Allows AT red hos r ro o learn public IP address N oz enumera re exis ring por r oz add remove por r mappings 1U 13876297 NAT rouTer 13876297 mappings wi rh lease Times ie au roma re s ra ric NAT por r map configura rion Ne rwork Layer 443 NAT Traversal problem I soluTion 3 relaying used in Skype O NATed server esTablishes connecTion To relay 0 Ex rernal clienT connecTs To relay 0 relay bridges packeTs beTween To connecTions 2 connection To relay ini lia led 1 connection To relay ini lia led by NAT led hosf 3 relaying esTablished Ne rwork Layer 444 Chapter 4 Network Layer CI 4 1 Introduction CI 45 Routing algorithms CI 42 Virtual circuit and 0 Link state datagram networks 0 Distance Vector g 43 When395 inside a O Hierarchical routing router CI 46 Routing in the CI 44 IP Internet Infernal Protocol 0 RIP 0 Datagram format 0 OSPF 0 IPv4 addressing O BGP O ICMP CI 47 Broadcast and 0 IPv6 multicast routing Network Layer 445 ICMP Internet Control Message Protocol used by hosts amp routers To communicate networklevel information 0 error reporting unreachable host network port protocol 0 echo requestreply used by Ping networklayer above IP 0 ICMP msgs carried in IP datagrams ICMP message Type code plus first 8 bytes of IP datagram causing error Type Code description LOOOOOOOOOOOOO OVCDWM OO 00000 echo reply ping dest network unreachable dest host unreachable dest protocol unreachable dest port unreachable dest network unknown dest host unknown source quench congestion control not used echo request ping route advertisement router discovery TTL expired bad IP header Network Layer 446 TracerouTe and ICMP I Source sends series of I When ICMP message UDP segmenTs To desT arrives source cacuaTes o FirsT has TTL 1 RTT 0 Second has TTL2 eTc CI TracerouTe does This 3 O Unlikely porT number Times I When nTh daTagram arrives W T0 Th FOUTer39i El UDP segmenT evenTually O RouTer discards daTagram arrives 0T desTinaTion hosT 0 And sends T0 Source 0quot El DesTinaTion reTurns ICMP ICMP message Type 1139 hosT unreachablequot packeT C de 0 Type 3 code 3 0 Message includes name of mum IP address I When source geTs This ICMP sTops NeTwork Layer 447 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 QoS IPv6 datagram format 0 fixedlength 40 byte header 0 no fragmentation allowed Network Layer 448 IPv6 Header Con r Pm orfy iden rify pr39ior39i ry among da ragr39ams in flow Fow Labe iden rify da ragr39ams in same flow concep r of fowquot no r well defined Nexf header iden rify upper39 layer39 protocol for39 da ra 32 bits gt Network Layer 449 O rher39 Changes from IPv4 CI theesum removed en rir39ely To reduce processing Time of each hop CI Op ons allowed bu r ou rside of header39 indica red by Nex r Header39quot field CI CAIPv6 new version of ICMP O addi rional message Types eg Packe r Too Big O mul ricas r gr39oup managemen r func rions Ne rwor39k Layer39 450 Transi rion From IPv4 To IPv6 CI No r all r39ou rer39s can be upgraded simul raneous C no flag daysquot 0 How will The ne rwor39k oper a re wi rh mixed IPv4 and IPv6 r39ou rer39s CI TameMg IPv6 car39r39ied as payload in IPv4 da ragr39am among IPv4 r39ou rer39s Ne rwor39k Layer39 451 Tunneling IA Logical view IPv6 Physical view IPv6 B IPv6 B IPv6 E F Tunnel IPv6 IPv6 E F IPv4 IPv4 IPv6 IPv6 Ne rwor39k Layer 452 Tunneling A B E F Lo ical view funnel 9 IPv6 IPv6 IPv6 IPv6 B C D E PhySIcal Vlew IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 gt gt gt gt Flow X Flow X Sr39c A Sr39c A best F Des r F da ra da ra 213 iii IPv6 inside IPv6 inside IPv4 IPv4 Ne rwor39k Layer 453 Chap rer 4 Ne rwork Layer CI 4 1In rroduc rion CI 44 Routing CI 42Wha r39s inside a 03990 th rou rer 0 Link sTaTe D 43 IP Infernal O DisTance VecTor O Hierarchical rouTing CI 45 Rou ring in The ProTocol O DaTagram forma r 0 IPv4 addressing Inferne r o ICMP 0 RIP 0 IPv6 O OSPF Ne rwork Layer 454 In rerploy be rween rou ring forwarding routing algorithm local forwarding table header value value in arriving packet s header Pl Ne rwork Layer 455 Graph abs rrac rion Graph G NE N set of routers u v w x y z E set of links uv ux vx vw Xw xy wy wz yz Remark Graph absTracTion is useful in oTher neTwork conTesz Example P2P where N is seT of peers and E is seT of TCP connecTions Ne39rwork Layer 456 Graph abs rrac rion cos rs cxx39 cosT of link xx39 eg cwz 5 cosT could always be 1 or inversely relaTed To bandwidTh or inversely relaTed To congestion CosT of paTh x1 x2 x3 xp cx1x2 cx2x3 cxp1xp I QuesTion WhaT39s The leasTcosT paTh beTween u and z I I Rou ring algori rhm algori rhm Tha r finds leas rcos r pa rh Ne rwork Layer 457 Rou ring Algori rhm classifica rion Global or39 decen rr alized S la l39ic or39 dynamic lthf l nCl l39th sm c Global I all r39ou rer39s have compleTe Cl rOUTeS Change 5l WlY Topology link cosT info over quot18 I link s ra requot algori rhms DYNGmIC DecenTralized CI r39ou res change more I rouTer knows physically quickly connecTed neighbor39s link d d T cosTs To neighbor39s O pemo lc up a e I i rera rive process of O in response 1390 link compu ra rion exchange of COS I39 changes info wiTh neighbors I disfance vecTor algoriThms Ne rwor39k Layer39 458 A Link S ra re Rou ring Algori rhm Dijkstra s algori rhm No ra rion Cl 3 TOPOlOQY link COSTS CI CXy link cosT from node known To all nodes x To y 2 00 if of dired O accomplished via link neighbors slam broadcasl CI DV currenT value of cosT 0 all nodes have same info of mm from source TO I compuTes leasT cosT paThs desT v from one node source To all oTher nodes 0 gives forwarding Table CI pv predecessor node along paTh from source To v for ThaT node CI N39 seT of nodes whose D Hem ve a er k leasT cosT paTh definiTively known iTeraTions know leasT cosT paTh To k desT39s Ne rwork Layer 459 Dijsktr39a39s Algorithm 1 Initialization 2 N39 u 3 for all nodes v 4 if v adjacent to u 5 then Dv cuv 6 else Dv 7 8 Loop 9 find w not in N39 such that Dw is a minimum 10 add w to N39 11 update Dv for all v adjacent to w and not in N39 12 Dv min Dv Dw cwv 13 new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v 15 until all nodes in N39 Network Layer 460 Dijks rr39a39s algori rhm example Step N39 DVPV DW0W DX0X DY0Y DZ0Z O u 2u 5LLJ1U oo 1 ux lt2 J 4X 2X 2 uxym 4y 3 uxyv 3y 4y 4 uxva 4y 5 uxvaz Ne rwor39k Layer 461 Dijks rr39a39s algori rhm example 2 ResulTinq shorTesTpcn h free from u ResulTinq forwardinq Table in u desTinaTion ink UN ugtlt ugtlt ugtlt ugtlt NEltXlt Ne rwor39k Layer 462 Dijkstra39s algorithm discussion Algorithm complexity n nodes CI each iteration need to check all nodes w not in N CI nn12 comparisons Onz CI more efficient implementations possible Onlogn Oscillations possible CI eg link cost amount of carried traffic recompute recompute recompute routing 6 initially Network Layer 463 Dis rance Vec ror Algori rhm BellmanFord Equa rion dynamic proqramminq Define dxy 2 COST of leas r cos r pa rh from x To y Then dxY mvin CXN dvY where min is Taken over all neighbors v of x Ne rwork Layer 464 Bellman Ford example Clearly dvz 5 dxz 3 dwz 3 BF equa rion says duz min cuv dxz cux dxz cuw dwzgt min 2 5 1 3 5 3 4 Node Tha r achieves minimum is nex r hop in shor res r pa rh D forwarding Table Ne rwork Layer 465 Dis rance Vec ror Algori rhm CI Dxy es rima re of leas r cos r from x To y El Node x knows cos r To each neighbor v cxv CI Node x main rains dis rance vec ror39 Dx Dxy y e N CI Node x also main rains i rs neighbor539 dis rance vec ror39s O For39 each neighbor v x main rains Dv Dvy y e N Ne rwor39k Layer39 466 Dis ronce vec ror olgori rhm 4 Basic idea CI Each node periodically sends i rs own dis ronce vec ror es rimo re ro neighbors CI When a node x receives new DV es rimo re from neighbor i r updo res i rs own DV using BF equo rion DXy lt mnjdx v 439 Dy for each node y 639 N CI Under minor no rurol condi rions rhe es rima re DXy converge 7 0 ve acfua leasf cosfdxy Ne rwork Layer 467 Distance Vector Algorithm 5 Iterative asynchronous Each node each local iteration caused by 3 local link cost change wait for change in local link D DV updaTe message from cost or msg from neighbor neighbor Distributed I each node notifies neighbors onywhen its DV Changes if DV to any dest has 0 neighbors then notify Their neighbors if changed notify neighbors necessary I recompute estimates Network Layer 468 39 D n z 4quot w t39xrggzg 399 W X W min 21 70 3 node x Table cosT To from 7 y 00 z 00 0000 node x Table 3T To X Ev q Z node 2 Table cosT To xyz 000000 from M x Time Ne rwor39k Layer 469 Dxy mincxy Dyy cgtltz Dzy node x Table from Y z cosT To 7 000 node x Table 3T To E o L H node 2 Table from M xl Y z cosT To xyz 000 min20 71 2 0x2 mincxy D 2 cxz 022 min 21 70 3 cosT To x y z cosT To x y z 02 3 2 01 310 cosTTo x y z 027 201 from 023 201 310 cosT To x y 2 Network Layer 470 DisTance VecTor39 link cosT changes lJnkcosTchanges El node deTecTs local link cosT change I updaTes r39ouTing info r39ecalculaTes disTance vecTor39 I if DV changes noTify neighbors AT Time 7 0 ydeTecTs The linkcosT change updaTes iTs DV and informs iTs neighbor39s good news AT Time 7 zr39eceives The updaTe fr39om yand updaTes its Tabb Travels IT compuTes a new leasT cosT To X and sends iTs neighbor39s iTs DVT fClS I39quot AT Time 7 2 yr39eceives is updaTe and updaTes its distance Tabb ys leasT cosTs do noT change and hence y does I707quot send any message To 2 NeTwor39k Layer39 471 DisTance VecTor link cosT changes Link cosT changes I good news Travels fasT El bad news Travels slow counT To infiniTyquot problem I 44 iTeraTions before algoriThm sTabilizes see TexT Poisoned reverse I If Z rouTes Through Y To geT To X 0 Z Tells Y iTs Z39s disTance To X is infiniTe so Y won39T rouTe To X via Z I will This compleTely solve counT To infiniTy problem NeTwork Layer 472 Comparison of LS and DV alqori rhms Message complexi ry I Q wiTh n nodes E links OnE msgs senT CI Diexchange beTween neighbors only 0 convergence Time varies Speed of Convergence I Q Onz algoriThm requires OnE msgs 0 may have oscillaTions I M convergence Time varies 0 may be rouTing loops 0 coun r roinfini ry problem Robus rness wha r happens if rou rer malfunctions L5 0 node can adverTise incorrecT nk cosT 0 each node compuTes only iTs own Table DV 0 DV node can adverTise incorrecT pm h cosT 0 each node39s Table used by oThers error propagaTe Thru neTwork Ne rwork Layer 473 RIP Rou ring Informa rion Pr39o rocol CI dis rance vec ror39 algor39i rhm I included in BSDUNIX Distribution in 1982 El dis rance me rr39ic of hops max 15 hops Fr39om r39ouTer39 A To subseTs destination hops Nltx ltc NwwNNH Ne39rwor39k Layer 474 RIP advertisements CI a fsfance vecfors exchanged among neighbor39s every 30 sec via Response Message also called advertisement CI ech advertisement list of up to 25 destination nets within AS Network Layer39 475 RIP Example I Q A gbc B C Destination Network Next Router Num of hops to dest w A 2 y B 2 z B 7 x 1 Routing table in D Network Layer 476 RIP Example Diff Nf d 2 Advertisement x 1 from A to D 2 C 4 A 393 C Destination Network Next Router Num of hops to dest w A 2 y B 2 z XA X5 x 1 Routing table in D Network Layer 477 RIP Link Failure and Recovery If no advertisement heard after 180 sec gt neighborlink 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 Network Layer 478 Chapter 5 Link Layer and LANs ECE 355 Introduction to Networks and Data Communications Sachin Shetty 5 DataLink Layer 51 Chap rer 5 The Da ra Link Layer M CI unders rand principles behind da ra link layer services 0 error deTecTion correc rion 0 sharing a broadcas r channel mulTiple access 0 link layer addressing O reliable daTa Transfer flow conTrol done CI ins ran ria rion and implemen ra rion of various link layer Technologies 5 DataLink Layer 52 Link Layer CI 51 In rr oduc rion and services CI 52 Error de rec rion and correction CI 53Mul riple access pr o rocols CI 54 Linklayer Addressing CI 55 Ethernet 5 DataLink Layer 53 Link Layer In rroduc rion Some Terminology I I hosTs and rou rers are nodes communicaTion channels ThaT connecT adjacen r nodes along x 5 1 communicaTion paTh are links 3 O wired links l 0 wireless links 3 O LANs layer2 packe r is a frame encapsulaTes daTagram datalink layer has responsibility of Transferring da ragram from one node To adjacen r node over a link 5 DataLink Layer 54 Link layer conTexT CI daTagram Transferred by differenT link proTocols over differenT links 0 eg ETherneT on firsT link frame relay on inTermediaTe links 80211 on lasT link CI each link proTocol provides differenT services 0 eg may or may noT provide rdT over link TransporTaTion analoqy CI Trip from PrinceTon To Lausanne O limo PrinceTon To JFK 0 plane JFK To Geneva 0 Train Geneva To Lausanne CI TourisT daTagram CI TransporT segmenT communicaTion link CI TransporTaTion mode link layer proTocol CI Travel agenT rouTing algoriThm Link Layer Services CI 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 I reliable delivery be fween aq jacenf nodes 0 we learned how To do This already chapTer 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 DataLink Layer 56 Link Layer Services more CI flow confrol o pacing beTween adjacen r sending and receiving nodes CI error a e reefon 0 errors caused by signal a r renua rion noise 0 receiver deTecTs presence of errors signals sender for re rransmission or drops frame CI error correc rion 0 receiver iden rifies and correcfsbi r errors wiThouT resorTing To reTransmission CI halfduplex and fullduplex O wiTh half duplex nodes aT bo rh ends of link can TransmiT buT noT aT same Time 5 DataLink Layer 57 Where is the link layer implemented CI in each and every host CI link layer implemented in quotadaptorquot aka network in ferface card NIC 0 Ethernet card PCMCI card 80211 card 0 implements link physical layer has schemallc attaches into host s system buses combination of elwnrkadapler hardware Software LE card D D firmware 5 DataLinkLayer 5V8 Adap rors Communica ring sending host receiving host gt f rame CI sending side CI receiving side 0 encapsulaTes daTagram in 0 looks for errors rdT flow frame con rrol eTc 0 adds error checking bi rs o ex rrac rs da ragram passes rd r flow conTrol eTc To upper layer 0T receiving side 5 DataLink Layer Link Layer CI 51 In rr oduc rion and services CI 52 Error de rec rion and correction CI 53Mul riple access pr o rocols CI 54 Linklayer Addressing CI 55 Ethernet 5 DataLink Layer 5 10 Er39r39or39 Defec rion EDC Er39r39or39 De l ecfion and Correction bi l39s redundancy D Data protected by error checking may include header fields Er39r39or39 de l39ec139ion no139 100 reliable pr39o139ocol may miss some errors bu l39 r39ar39ely lar39ger39 EDC field yields be H39er39 defection and correction I datagram I gt detected error lt d data bits amp D EDC I D39 EDC39I biterror prone link 5 DataLink Layer 5 11 Pari ry Checkinq Single Bi r Pari rx Defect single bit errors lt d data bits gt quotty 0111000110101011 Two Dimensional Bi r Pari ry Defect and correcf single bit errors rOW parity d1j1 d21 d2 d2j l column parity 1011 110 parity error 1101 l O l 0 no errors Parity er l39O l39 correctable single bit error C J OOlOlO l O 0 5 DataLink Layer 512 In rerne r checksum review Goal de rec r quoterrorsquot eg flipped bi rs in rransmi r red packe r no re used a r rranspor r layer only Sender Receiver El TreaT segmenT conTenTs as D compul Checks of sequence of 16biT rece39ve segmen integers I check if compuTed checksum D checksum addmon 139s equals checksum field value complement sum of O NO error deTecTed segmenT conTenTs 0 YES no error deTecTed El sender puTs checksum BU maybe errors value inTo UDP checksum quotMeme655 field 5 DataLink Layer 513 Checksumminq Cyclic Redundancy Check CI view daTa biTs D as a binary number CI choose r391 biT pa er n generaTor39 6 CI goal choose r39 CRC biTs R such ThaiL O ltDRgt exac rly divisible by G modulo 2 0 receiver knows G divides ltDRgt by G If nonzer39o remainder er39r39or39 de rec redl O can de rec r all bur39s r er39r39or39s less Than r391 bi rs El widely used in pr39acTice 80211 WiFi ATM 4 d bits gtlt rbits gt bit I Ddata bits to be sent I R39CRC bits pattern r mathematical D 2 XOR R formula 5 DataLink Layer 514 CRC Example Wan r Deroppzne 101011 equvaenfy G 1 O O E I 0 l l l OO O E 1001 equivaen y 3 8 S 0 if we divide D2quot by 1 001 11 O G wan l39 remainder R 000 l 100 l 001 r39 1010 l 001 R remainder O l R439 39 5 DataLink Layer 515 Link Layer CI 51 In rr oduc rion and services CI 52 Error de rec rion and correction CI 53Mul riple access pr o rocols CI 54 Linklayer Addressing CI 55 Ethernet 5 DataLink Layer 5 16 Mul riple Access Links and Pr39o rocols Two Types of quotlinksquot CI poin rTopoin r O PPP for dialup access 0 poin rTopoin r link be rween E rher39ne r swi rch and hos r CI br39oadcas r shar39ed wire or39 medium 0 oldfashioned E rher39ne r o ups rr39eam HFC 0 80211 Wireless LAN 39k 1 E Q g humans of a Shared RF cocktail party shared wir39e eg cabled E39lher39ne39l eg 80211 WiFi Safellife shared air39 acousfical 5 DataLink Layer 517 MulTiple Access proTocols CI single shared br39oadcasT channel CI Two or39 more simuITaneous Transmissions by nodes inTer39fer39ence O collision if node r39eceives Two or39 more signals aT The same Time mufbe access pro focal CI disTr39ibuTed algor39iThm ThaT deTer39mines how nodes shar39e channel i e deTer39mine when node can Tr39ansmiT CI communicaTion abouT channel shar39ing musT use channel iTselfl 0 no ouTofband channel for39 coor39dinaTion 5 DataLink Layer 518 Ideal MulTiple 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 decenTraIized o no special node To coordinaTe Transmissions 0 no synchronizaTion of clocks sloTs 4 simple 5 DataLink Layer 519 MAC Pr39o rocols a Taxonomy Thr39ee br39oad classes CI Channel Par ri rioning O divide channel info smaller quotpiecesquot Time sloTs frequency code 0 allocaTe piece To node for39 exclusive use CI Random Access 0 channel noT divided allow collisions 0 recover from collisions CI Taking Turnsquot 0 nodes Take Turns buT nodes wiTh more To send can Take longer39 Turns 5 DataLink Layer 520 Channel Par ri rioning MAC pr39o rocols TDMA TDMA Time division mul riple access CI access ro channel in quotroundsquot CI each s ra rion ge rs fixed leng rh slo r leng rh pk r rr39ans Time in each round CI unused slo rs go idle CI example 6s ra rion LAN 134 have pk r slo rs 256 idle 6sloT 4 frame 39 r 5 DataLink Layer 521 Channel Parfifioning MAC profocols FDMA FDMA frequency division mulfiple access CI channel spec rrum divided info frequency bands CI each s ra rion assigned fixed frequency band CI unused Transmission Time in frequency bands 90 idle CI example 6s ra rion LAN 134 have pk r frequency bands 256 idle Time WW E U 0 gt Q g FDM cable m 5 DataLink Layer 522 Random Access Pro rocols CI When node has packe r To send 0 TransmiT aT full channel daTa raTe R o no aprorcoor39dina rion among nodes CI Two or39 more rr39ansmi r ring nodes D collision CI random access MAC protocol specifies 0 how To deTecT collisions 0 how To recover from collisions eg via delayed re rransmissions CI Examples of random access MAC pr39o rocols O sloTTed ALOHA o ALOHA O CSMA CSMACD CSMACA 5 DataLink Layer 523 Slo r red ALOHA Assumg rions Operation I all frames same size CI when node ob rains fresh CI rime divided in ro equal frame rransmi rs in nex r size slo rs Time To 5390 rransmi r 1 frame 0 if no collision node can CI nodes s rar r ro rransmi r 53nd new frame in he only slo r beginning 539 CI nodes are synchronized O quotf call5 Ode re rransmi rs frame in each subsequen r slo r wi rh prob p un ril success CI if 2 or more nodes rransmi r in slo r all nodes defec r collision 5 DataLink Layer 524 Slo r red ALOHA n nodes l I I I I I I I I I I I I I I I P 3399 m m g singe active node can CI collisions wos ring slo rs con rinuously rr39onsmi r CI idle SlO fS of full rate of channel CI nodes may be able ro CI highly decentranzed de rec r collision in less ony 5o5 in nodes rhon Time To rr39ansmi r pockeT need To be in sync CI clock synchr39onich rion CI sImple 5 DataLink Layer 525 Sloffed Aloha efficiency Efficiency longrun CI max efficiency find frac rion of successful slo rs P Thai mGlelzes many nodes all wi rh many llP139PN391 frames To send CI for many nodes fake limi r of Np1pN391 CI suppose N nodes wi rh as N goes ro i nfini ry many frames To send gives GCh Transmlls ln SlO39l39 Max efficiency le wi rh probabili ry p CI prob fha r given node Af besf channel has success in a slo r used for useful I P1Pquotquot1 Transmissions 37 CI prob fha r any node has of Time a success Np1pN1 5 DataLink Layer 526 Pure unslo r red ALOHA El unslo r red Aloha simpler no synchronization I when frame first arrives O transmit immediately I collision probability increases 0 frame sent at to collides with other frames sent in to1to1 will overlap I will overlap with start of with end of lt i s frame i39s frame tl 5 DataLink Layer 527 Pur39e Aloha efficiency Psuccess by given node Pnode Transmi rs Pno oTher node Tronsmi rs in p01p0 Pno oTher node Tronsmi rs in p01p0 p 1p1 1 p1 p 1p2N1 choosing op rimum p and Then Ie r ring n gt inf ry 12e 18 even worse rhon slo r red Aloha 5 DataLink Layer 528 CSMA Carrier Sense MulTiple Access CSMA IisTen before TransmiT If channel sensed idle TransmiT enTire frame CI If channel sensed busy defer Transmission CI human analogy don39T inTerrupT oThers 5 DataLink Layer 529 CSNlA collisions spaTial layouT of nodes space collisions can sTill occur39 propagaTion delay means Two nodes may noT hear each oTher39s Transmission collision enTir e packeT Transmission Time wasTed noTe role of disTance amp propagaTion delay in deTermining collision probabiIiTy lt Time 5 DataLink Layer 530 CSMACD Collision DeTecTion CSMACD carrier sensing deferral as in CSMA O collisions defecfea 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 received signal sTrengTh overwhelmed by local Transmission sTrengTh CI human analogy The poliTe conversaTionalisT 5 DataLink Layer 531 CSMACD collision de reC rion 4 time collision detectabort time 5 DataLink Layer 532 Taking Turnsquot MAC pro rocols channel par ri rioning MAC pr39o rocols 0 share channel ef cenfyand fairya high load 0 inefficien r a r low load delay in channel access 1N bandwid rh alloca red even if only 1 ac rive node Random access MAC pr39o rocols O efficien r a r low load single node can fully u rilize channel 0 high load collision over39head Taking rur39nsquot pr39o rocols look for39 bes r of bo rh worlds 5 DataLink Layer 533 Taking Turnsquot MAC pro rocols Polling CI master node invi res slave nodes ro rr39ansmi r in mm CI Typically used wi rh dumb slave devices Cl concerns 0 polling overhead 0 la rency slaves 0 single poin r of failure masTer 5 DataLink Layer 534 Taking Turnsquot MAC pro rocols Token passing CI con rrol Token passed from one node ro nex r sequen rially CI roken message noThing CI concerns To send 0 Token overhead Q 0 la rency 0 single poin r of failure Token 5 DataLink Layer 535 Summary of MAC pro rocols CI channepar f omhg by ri me frequency or code 0 Time Division Frequency Division CI 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 ETherneT O CSMACA used in 80211 CI faking farms 0 polling from cen rrol si re Token passing 0 BlueTooTh FDDI IBM Token Ring 5 DataLink Layer 536 LAN Technologies Do ro link layer39 so for 0 services er39r39or39 de rec rioncor r ec rion mul riple access Nex r LAN Technologies 0 addressing 0 Ethernet 0 swi rches O PPP 5 DataLink Layer 537 Link Layer CI 51 In rr oduc rion and services CI 52 Error de rec rion and correction CI 53Mul riple access pr o rocols CI 54 LinkLayer Addressing CI 55 Ethernet 5 DataLink Layer 5 38 MAC Addresses and ARP El 32 bi r IP address 0 nefwor39klayer address 0 used To ge r da ragram ro des rina rion IP subne r El MAC or LAN or physical or E rherne r address 0 function gef frame from one inferface to ma ver physicallycoma fed in ferface same ne fwork O 48 bi r MAC address for mos r LANs burned in NIC ROM also some rimes sofTware se r rable 5 DataLink Layer 539 LAN Addresses and ARP Each adap rer on LAN has unique LAN address 1A2FBB7609AD BroadcasT address FFFFFFFFFFFF I adapTer39 7165F7ZB0853 5823D7FA20BO 0CC4116FE398 5 DataLink Layer 540


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

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

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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


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