New User Special Price Expires in

Let's log you in.

Sign in with Facebook


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


Create a StudySoup account

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

Sign up with Facebook


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

Already have a StudySoup account? Login here

Computer Networks

by: Theodora Daniel I

Computer Networks CSE 5231

Theodora Daniel I
Florida Tech
GPA 3.9

Gerald Marin

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

Gerald Marin
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 224 page Class Notes was uploaded by Theodora Daniel I on Monday October 12, 2015. The Class Notes belongs to CSE 5231 at Florida Institute of Technology taught by Gerald Marin in Fall. Since its upload, it has received 39 views. For similar materials see /class/221678/cse-5231-florida-institute-of-technology in ComputerScienence at Florida Institute of Technology.

Similar to CSE 5231 at Florida Tech

Popular in ComputerScienence


Reviews for Computer Networks


Report this Material


What is Karma?


Karma is the currency of StudySoup.

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

Date Created: 10/12/15
End To End Pro rocols This ma rer39ial is provided solely for39 The use of s ruden rs in CSE5231 a r FIT Fur39Ther39 use or39 r39epr39oduc rion may be a viola rion of exis ring copyrigh r pr39o rec rion Network Analysis EndToEnd 51 Transport Layer goals Common Properties CI understand principles CI Guarantees message delivery behind lmnspor39l layer CI Delivers messages in order services D S upports arbitrarily large 0 multIpIeXIngdemultlplex messages ing CI May support synchronization between sender and receiver CI Supports flow control to protect the receiver CI May Support congestion control to Support the network CI Supports multiple application processes on each host 0 reliable data transfer 0 flow control 0 congestion control CI instantiation and implementation in the Internet Network Analysis EndToEnd 52 Recall limi ra rions of bes reffor rquot in rerne rwork CI IT may drop messages CI IT may reorder messages CI IT may deliver duplica re copies of a given message CI IT may limi r message size in some way CI IT may allow arbi rrarily long delay CI IT may allow large variabili ry in delay from packe r To packe r CI End To end pro rocols may need To compensa re for These limi ra rions Ne rwork Analysis EndToEnd 53 TransporT services and proTocols CI provide 0q39ca commum39ca on beTween app39 processes running on differenT hosTs CI TransporT proTocols run in end sysTems CI TransporT vs neTwork layer services CI neTwork ayer3939 daTa Transfer beTween end sysTems CI fransporf ayer daTa Transfer beTween processes 0 relies on enhances neTwork layer services TransporT physical A TransporT physical NeTwork Analysis EndToEnd 54 Transpor rlayer pro rocols In rerne r Transpor r services CI reliable inorder unicas r delivery TCP franspor r dafa link r o congestion V 0 flow conTrol o connecTion seTup CI unreliable bes reffor rquot unordered unicas r or mul ricas r delivery UDP CI services no r available 0 realTime O bandwidTh guaranTees o reliable mulTicasT rranspor r Ne rwork Analysis EndToEnd 55 Mul riplexingdemul riplexing Recall segmenf uni r of da ra exchanged befween Demul riplexmg delivering received segmen rs To Jrr39cmspor r layer enT39T39es correc r app layer processes 0 aka TPDU Transpor r pro rocol da ra uni r receiver P3 applicaTionIayer daTa Segmenf Segmenf Ne rwork Analysis EndToEnd 56 MuI riplexingdemul riplexing Mul riplexing ga rhering da ra from mul riple app processes enveloping da ra wi rh header la rer used for demul riplexing muTipexingdemulTiplexing CI based on sender receiver porT numbers IP addresses 0 source desT porT s in each segmenT o recall wellknown porT numbers for specific applicaTions CI 16 biTs implies 64k ports available source port l desT DorT o rher header fields app I i ca rion daTa message TCPUDP segmen r forma r Ne rwork Analysis EndToEnd 57 Mul riplexinqdemul riplexinq examples source port x Web clien r Desf IP B Desf IP B SOUPCC X por r use simple Telne r app Web DesT IP B server B Web clien r hos rA quot X por r u3e Web server Ne rwork Analysis EndToEnd 58 WELL KNOWN PORT NUMBERS The Well Known Ports are assigned by the IANA and on most systems can only be used by system or root processes or by programs executed by privileged users Ports are used in the TCP RFC793 to name the ends of logical connections which carry long term conversations For the purpose of providing services to unknown callers a service contact port is defined This list specifies the port used by the server process as its contact port The contact port is sometimes called the quotwellknown portquot To the extent possible these same port assignments are used with the UDP RFC768 The range for assigned ports managed by the IANA is 01 Network Analysis EndToEnd 59 Port Examples chargen 19th Character Generator chargen 19udp Character Generator ftpdata 20th File Transfer Default Data ftpdata 20udp File Transfer Default Data ftp 21th File Transfer Control ftp 21udp File Transfer Control ssh 22th SSH Remote Login Protocol ssh 22udp SSH Remote Login Protocol telnet 23th Telnet telnet 23udp Telnet 24th any private mail system 24udp any private mail system smtp 25th Simple Mail Transfer smtp 25udp Simple Mail Transfer 26th Unassigned 26udp UnassigrLeeglwork Analysis EndToEnd 540 UDP User Da ragram Pro rocol RFC 768 CI no frillsquot bare bonesquot In rerne r Transpor r 9 profocol Why is There a UDP CI bes r effor rquot service UDP D 0 conned39on segmems may be es rablishmen r which can 0 los r add delGY O delivered ou r of order D n0 COhheC l39th S l39Cl l39e To app a r sender receiver CI connecfbness CI small segmen r header 0 no handshaking belween CI no conges rion con rrol UDP UDP sender rece39Ver39 can blas r away as fas r as 0 each UDP segmen r desired handled independen rly of o rhers Ne rwork Analysis EndToEnd 511 UDP more CI of ren used for s rreaming mul rimedia apps m 0 loss Toleran r Length in source Dom desT porT o ra re sensi rive byTes of UDPgtIenmh Checksum El rh UDP s 5 segment 0 e u 8 including Why39 header 0 DNS 0 SNMP Applica rion CI reliable Transfer over UDP dam add reliabili ry a r message applica rion layer o applicationspecific error recovery UDP segmenl formal Ne rwork Analysis EndToEnd 512 UDP checksum Op rional v4 Goal de rec r quoterrorsquot eg flipped bi rs in Transmi r red segmen r including UDP header pseudoheader da ra Sender CI frea r segmenf confenfs as sequence of 16bif infegers CI check5um addifion 139s complemenf Sum of segmenf confen rs CI sender pufs check5um value info UDP check5um field Receiver CI compufe checksum of received segmenf CI check if compufed check5um equals check5um field value 0 NO error defec red 0 YES no error defecfed Buf maybe errors nonefhess More la rer Ne rwork Analysis EndToEnd 513 UDP Pseudo header CI Consis rs of Three fields from The IP header 0 Pro rocol number 0 Source IP address 0 Des rina rion IP address CI Plus UDP Leng rh field Ne rwork Analysis EndToEnd 514 Principles of Reliable daTa Transfer CI imporTanT in app TransporT link layers CI Top10 lisT of imporTanT neTworking Topics receiver 0 rocess sen Ing arocess reliable channel applicaTion layer 4 rdtsend reliable daTa deliverdata reliable daTa Transfer DFPTOCOl Transfer proTocol sending Side receiving side udtsend Irdtrcv Ll lunreliable channellltT 0 provided service b service implemenTaTion Tra nspori layer CI characTerisTics of unreliable channel will deTermine complexiTy of reliable daTa Transfer proTocol rdT NeTwork Analysis EndToEnd 515 Reliable daTa Transfer quTinq sTarTed rdtsend called from above eg by app Passed daTa To rdtsend send reliable daTa d Transfer proToool 339 e sending side udtsend deliverdata called by rdt To deliver daTa To upper Tdeliverdata reliable daTa receive Transfer proTocoI Si d e Irdtrcv tpOLinreliable Channel udtsend called by rdT To Transfer packeT over unreliable channel To receiver rdtrcv called when packeT arrives on rcvside of channel NeTwork Analysis EndToEnd 516 TCP Transmission Con rrol Pro rocol CI Offers a reliable connec rionorien red by res rreom service CI Fullduplex one by res rreom in each direcTion CI Suppor rs mul riplexingdemul riplexing among mul riple opplico rions on o hos r CI Implemen rs flow con rrol CI Implemen rs conges rion con rrol Ne rwork Analysis EndToEnd 517 Developmenf of TCPIP CI Early 1970s Vin ron Cerf and Rober r Kohn recognized The impor ronce of creo ring a single profocol for pocke rswifched ne rworks CI Ini riolly They saw if as a single en ri ry Lo rer spli r info TCP and IP CI Published paper in IEEE Tronsoc rions on Communico rions Technology May 1974 El Before The web before LANs before PCs Ne rwork Analysis EndToEnd 518 TCPI Overview RFCs 793 1122 1323 2018 2581 El poin rTopoin r El full duplex da ra 0 one sender one receiver 0 bidirec rional da ra flow El reliable inorder byfe 39 same ConneCl39O sfeam 0 M55 maximum segmen r u ll size 0 no message boundaries El connec rionorien red El pipelined TCP d H O handshaking exchange 0 colngeslrlgndan 039 of con rrol msgs ini r39s Corler gel Wm 0W 53926 sender receiver s ra re El 5870 6 receVe buffers before da ra exchange CI flow con rrolled socket 3 39 socket O m d r overwhelm receiver Ne rwork Analysis EndToEnd 519 TCP segment structure URG urgent data generally not used 32 bits source port I dest port ACK ACK sequence number by of valid C owledgement number PSH push data now generally not used k head not sed PRSF rcvr window size ptr urgent data RST SYN FINz connection estab c OpWKs variable length setup teardown commands Internet checksum as in UDP application data variable length counting bytes data not segments bytes rcvr willing to accept Network Analysis EndToEnd 520 TCP Pseudo Header CI 32bi r source IP address CI 32bi r des rina rion IP address CI 8bi r pro rocol number CI 16bi r TCP headerdaTa leng rh TCP checksum covers The above plus CI TCP header CI TCP da ra Ne rwork Analysis EndToEnd 521 TCP Challenges CI RTTs can be long 1003 of ms and variable CI ConnecTions may be beTween any Two hosTs on The InTer39neT can39T assume much CI PackeTs may arrive ver39y laTe CI HosTs are generally Tuned To Their39 local link and buffer sizes for39 example may vary gr39eale CI Sender39 has no idea where The boTTleneck may be in The neTwor39k and aT whaT max bandwidTh NeTwor39k Analysis EndToEnd 522 TCP seq s and ACKs Seg s o by re s rr39eom number of first by re in segmen r39s doTa ACKs o seq of nex r by re expec red fr39om o rher39 side 0 cumula rive ACK Q how receiver handles ou rofor39der39 segmen rs o A TCP spec doesn39T soy up To implemen ror39 r eceipf of 39C echoes back 39639 Time simple TelneT scenario 1 Network Analysis EndToEnd 523 TCP reliable data Transfer event data received from application above Simplified sender assuming create send segment 0ne way data tronsfer no flow congestion control event timer timeout for segment with seq y retransmit segment event ACK received with ACK y ACK processing Network Analysis EndToEnd 524 TCP ACK generation RFC 1122 RFC 2581 Event TCP Receiver action inorder segment arrival delayed ACK Wait up to 500ms no gaps for next segment If no next segment everything else already ACKed send ACK inorder segment arrival immediately send single no gaps cumulative ACK one delayed ACK pending outoforder segment arrival send duplicate ACK indicating seq higherthanexpect seq of next expected byte gap detected arrival of segment that immediate ACK if segment starts partially or completely fills gap at lower end of gap Network Analysis EndToEnd 525 TCP r39e rr39ansmission scenarios 92 TimeOLi r pl 100 Timeout 1 Seq l4 Seq 4 TimeouT gt r Ti e IosT ACK scenario m PremGTUPC TImBOUT cumulaTive ACKs Time Network Analysis EndToEnd 526 TCP Flow Con rrol flow con rrol receiver explicile sender won39T overrun informs sender of receiver39s buffers by dynamically changing Transmitting 13900 much amoun r of free buffer Too fas r space 0 RcvWindow field in Rchuffer size of TCP Receive Buffer TCP segmen r RcvWindow amoun r of spare room in Buffer sender keeps The amoun r FRWWIMOW of Transmi r red unACKed da ra less Than mos r recenle received data from rap in RcvWindow ll RchuHer l receiver buffering Ne rwork Analysis EndToEnd 527 TCP Round Trip Time and Timeou r Q how To se r TCP Timeou r value CI longer Than RTT o no re RTT will vary CI Too shor r prema rure Timeou r o unnecessary re rransmissions CI Too long slow reac rion To segmen r loss Q how To es rima re RTT CI SampleRTT measured Time from segmen r Transmission un ril ACK receip r o ignore re rransmissions cumula rively ACKed segmen rs CI SampleRTT will vary wan r es rima red RTT smoo rher 0 use several recen r measuremen rs no r jusT curren r SampleRTT Ne rwork Analysis EndToEnd 528 TCP Round Trip Time and Timeou r EstimatedRTT 1 xEstimatedRTT xSampleRTT CI Exponen rial weigh red moving average CI influence of given sample decreases exponen rially fas r CI Typical value of x 01 Se r rinq The Timeou r CI EstimtedRTT plus safe ry marginquot CI lar39ge var39ia rion in EstimatedRTT gt lar39ger39 safe ry mar39gin Timeout EstimatedRTT 4Deviation Deviation l xDeviation xISampleRTT EstimatedRTTl Network Analysis EndToEnd 529 TCP Connec rion Manaqemen r Recall TCP sender receiver es rablish connec rion before exchanging da ra segmen rs CI ini rialize TCP variables 0 seq s o buffers flow con rrol info 69 RcvWindow CI cfem connec rion ini ria ror Socket clientSocket new Socketquothostnamequotquotport numberquot CI server con rac red by clien r Socket connectionSocket welcomeSocketaccept Three way handshake S reg 12 clien r end sys rem sends TCP SYN con rrol segmen r To server 0 specifies ini rial seq S rep 22 server end sys rem receives SYN replies wi rh SYNACK con rrol segmen r o ACKs received SYN o alloca res buffers o specifies servergt receiver ini rial seq Ne rwork Analysis EndToEnd 530 TCP Connection Monoqement cont Closinq a connection client closes socket F clientSocket close quotV Steg 12 client end system AC sends TCP FIN control Close Segment to server Fm Ste 22 server receives 4 FIN replies with ACK g ACK Closes connection sends g FIN g 4 closed Network Analysis EndToEnd 531 TCP Connec rion Monoqemen r cont S reg 32 clien r receives FIN r39eplies wi rh ACK closing Fl 0 En rer39s Timed woi rquot N will respond wi rh ACK To r39eceived FINs A04 closmg N S reg 4 server39 r39eceres a ACK Connec rion closed 4 ACK 8 closed 4 closed Network Analysis EndToEnd 532 TCP Connec rion Managemen r con r m client application initiates aTCP connection wait SD secondsI send SYN I i ml Jihadquot receive FiN send ACK renews SYN HACK A TCP server client application I initiates close connection send FIN l receive ACK TCP clien r semith lifecycle receive ACK and nothing H r M mmquot s server application creates a listen socket Lil quotLii l receive SYN send SW18 ACK receive FiN send ACK receive ACK send nothing Ne rwork Analysis EndToEnd 533 Triggering TCP Transmission 1 Segmen r is sen r as soon as if reaches The max segmen r size MSS CI M55 is The local MTU TCP hdr size IP hdr Slze 2 Segmen r is sen r if applica rion uses push 3 Segmen r is sen r if sending Timer pops CI Avoid The silly window syndromequot in which small segmen rs are i n rroduced via flow con rrol from nearlyfull receiver buffer and never recollec red Ne rwork Analysis EndToEnd 534 Nogle39s Algori rhm CI Send a full segmen r size MSS if window allows CI Send a smaller segmen r if no o rher39 ou rs ronding segmen rs CI If There are segmen rs ou rs ronding Then woi r for39 on ock before sending ono rher39 segmen r unless MSS Network Analysis EndToEnd 535 Principles of Congestion Control Congestion El informally too many sources sending too much data too fast for network to handle El different from flow control El manifestations 0 lost packets buffer overflow at routers 0 long delays queueing in router buffers CI a top10 problem Network Analysis EndToEnd 536 CausesCOSTS of conqesTion scenario 1 H031 A kin original do ro CI Two senders Two receiver39s El one r39ouTer39 infiniTe buffers CI no reTransmission WWW in niTe buffers CI lar39ge delays C2 gt e g when congesTed 3 O o lt0 CI maXImum achievable X 32 ThroughpuT in NeTwor39k Analysis EndToEnd 537 Causescos rs of conqes rion scenario 2 El one rou rer fI39nfe buffers CI sender re rransmission of Ios r packe r HOST A kin original do ro 7Lou r Am 2 OilganI Hos r B re rrons rouTer wi rh fini re buffers Ne rwork Analysis EndToEnd 538 CausesCOSTS of conqes rion scenario 3 CI fourquot Senders Q wha r happens as km S mumhop 393 th and N increase 9 CI Timeoutretransmit In HOST A HOST B Network Analysis EndToEnd 539 Causescos rs of conqes rion scenario 3 Host A HOST B C 2 rnnn IIIIIIIU Hos rD 39 s E E Aou r R3 1 mum 4594 A in Ano rher cos r of conges rion CI when packe r dropped any ups rr39eam Transmission capaci ry used for39 Tha r packe r was was red Network Analysis EndToEnd 540 DefiniTions CI Resource allocaTion is The process by which neTwork elemenTs Try To meeT The compeTing demands ThaT applicaTions have for neTwork resources primarily link bandwidTh and buffer space in rouTers or swiTchesquot 0 Include labels in The case of label swap CI CongesTion conTrol describes The efforTs made by neTwork nodes To prevenT or respond To overload condiTionsquot NeTwork Analysis Resources amp 641 ConqesTion Causes of Congestion Queueing in router for particular outbound line Lost packets because of insuf cient memory Too much memorygtlong delaysgttimeouts Processorsthat are too slow for demand Lines with insuf cient capacity bandwidth NOTE congestion control is an issue involving performance tuning of the entire subnet Flow control is between sender and receiver only Network Analysis Resources amp 642 Conqesfion Resource AllocaTion Taxonomy El RouTer CenTric vs HosT CenTric O RouTer or swiTch cenTric implies mosT work done by neTwork nodes and They inform ouTside hosTs how much Traffic if any They are allowed To send El ReservaTion vs Feedback O ReservaTion means ThaT end hosT requesTs and neTwork nodes seT aside resources or rejecT The call Always coupled wiTh rouTer cenTric o Feedback means hosTs adjusT Their Traffic depending on feedback received Maybe be hosT cenTric or rouTer cenTric El Window vs RaTe Based 0 Window based like TCP O RaTe based means hosT makes reservaTion for specific bandwidTh bps NeTwork Analysis Resources amp 643 ConqesTion Example Congestion Metrics Average queue lengths Percent of packets discarded N umber of packets retransmitted Average number of collisions boadcast Average packet delay and standard deviation of delay Network Analysis Resources amp 644 Conqes rion Q UGUG Server Arrival Rate k Utlization Cl Scheduling discipline FIFO or39 FCFS Dr39op policy Tail dr39op These are pr39evalenT in The InTer39neT Some r39ouTer39s add pr39ior39iTy queuing a separ39aTe queue ThaT suppor39Ts higher39 pr39ior39iTy for conTr39ol messages based on TOS field Network Analysis Resources amp 645 Conqes rion FAIR Queuing CI FIFO queuing is unaware of differen r Traffic flows Tha r could have differen r pr39ior39i ry or39 QoS r39equir39emen rs CI Fair39 queuing FQ is an algor39i rhm based on main raining separ39a re queues for39 each flow cur39r39en rly being handled by r39ou rer39 Rou rer39 Then services These queues in r39oundr39obin 0 When a given queue reaches a par ricular rhr39eshold packe rs for39 rha r flow are discarded 0 Designed To complemen r o rher39 conges rion control mechanisms Network Analysis Resources amp 646 Conqes rion W eighted Fair Queueing Problem hosts respond to choke packets voluntarily Cooperating host gets penalized unfairly if others don39t coorperate Fair Queueing algorithm at each output line router has separate queue corresponding to each source Queues are serviced roundrobin Sill favors source that sends longer packets Improvement simulate bytebybyte round robin WFQ then add weig1ts according to source priority or bandwidth Packet Finishing time C 8 B 16 0 D 17 E 18 A 20 a b Network Analysis Resources amp 647 Congestion Congestion Control in Connectionless Networks Two br39oad approaches towar39ds congestion contr39ol Endend congestion Networkassisted contr39ol congestion contr39ol CI no explicit feedback from El routers provide feedback network to end systems CI congestion inferred from 0 single bit indicating endsystem obser39ved loss congestion SNA delay DECbit TCPIP ECN CI approach taken by TCP ATM o explicit r39ate sender should use Network Analysis EndToEnd 548 Case s rudy ATM ABR conqes rion con rrol ABR available bi r ra re CI elas ric servicequot CI if sender39s pa rh underloaded o sender should use available bandwid rh CI if sender39s pa rh conges red o sender Thro r rled To minimum guaran reed raTe RM resource managemen r cells CI sen r by sender in rerspersed wi rh da ra cells CI bi rs in RM cell se r by swi rches ne fwor39kaSSs fed 0 NI bi r no increase in ra re mild conges rion 0 CI bi r conges rion indica rion CI RM cells re rurned To sender by receiver wi rh bi rs in rac r Ne rwork Analysis EndToEnd 549 Case s rudy ATM ABR conqes rion con rr39ol I RlVl cells source I dole cells des rinolion SWiTCh SWiTCh X X El Twoby re ER explici r r39a re field in RM cell 0 conges red swi rch may lower39 ER value in cell 0 senderquot send r39a re Thus minimum suppor rable rate on pa rh CI EFCI bi r in da ra cells se r To 1 in conges red swi rch o if da ra ce preceding RM cell has EFCI Se r sender39 se rs CI bi r in r39e rur39ned RM cell Network Analysis EndToEnd 550 TCP Conges rion Con rr39ol CI endend control no network assis rance CI Transmission r39a re limi red by conges rion window size Congwin over39 segmen rs sendbase nexfseqnum already I usablelnof ock ed yei sen r IlllllilIlllllllllllli li lilili IiiTaQELd Congwin f El w segmen rs each wi rh MSS by res sen r in one RTT MSS Th h i W r39oug pu RTT By ressec Network Analysis EndToEnd 551 TCP congesTion conTrol El probing for usable bandwidTh o ideally TransmiT as fasT as possible Congwin as large as possible wiThouT loss 0 increase Congwin unTil loss congesTion 0 loss decrease Congwin Then begin probing increasing again CI Two phases 0 slow sTarT exponenTial increase 0 congesTion avoidance linear increase On TimeouT Threshold seT To half congwin and congwin seT To 1 M55 imporTanT variables 0 Congwin 0 threshold defines Threshold beTween Two slow sTarT phases NeTwork Analysis EndToEnd 552 TCP Slows rar r quotSlows rar r algori rhm initialize Congwin 1 for each segment ACKed Congwin until loss event OR CongWin gt threshold f urse ments CI exponen rial increase per RTT in window size no r so slow CI loss even r Timeou r Tahoe TCP andor or Three duplica re ACKs Reno TCP Time Ne rwork Analysis EndToEnd 553 TCP Congestion Avoidance Congestion avoidance slowstart is over 13 Congwin gt threshold Until loss event threshold lllll if E s every w segments ACKed 3 Congwin 7g 6 l3 S 1 19 Z 5 threshold Congwin2 j 1 Illlllllllllll 0 1 2 3 4 5 6 397quot 8 91011121314 Number of transmissions 1 TCP Reno skips slowstart fast recovery after three duplicate ACKs Network Analysis EndToEnd 554 TCP Fas r Re rransmi r CI The Timeou r adjus rmen r mechanism previously s rudied proved To be overly conserva rive CI Fas r re rransmi r in rroduced To enable re rransmission sooner Than Timer pops 0 Upon receip r of 3rd Ack for a given packe r The sender concludes rha r packe r is los r and re rransmi rs 0 This usually happens quickly because of The cumula rive na rure of Acks Ne rwork Analysis Resources amp 655 Conqes rion TCP FasT Recovery CI Idea is To avoid The slow sTar39Tquot oTher39 Than aT The iniTial cr39eaTion of The connecTion CI When packeT is losT The window size is divided by 2 and Then allowed To grow linear39ly CI Thus connecTion always oper39aTes in The addiTive incr39ease range 0 If packeT is losT by TimeouT Then window size r39eTur39ns To 1 NeTwor39k Analysis Resources amp 656 ConqesTion AIMD TCP congestion TCP Fairness avoidance Fair39ness goal if N TCP CI AIMD add ve sessions shar39e same increase bottleneck link each mUfpfcafVe should get 1 N of link decrease CGPGCHY 0 increase window by 1 TCP comedian 1 per39 RTT quot 0 decrease window by factor39 of 2 on loss event bottleneck connection 2 muler capaCIty R Network Analysis EndToEnd 557 Why is TCP fair Two compe ring sessions CI Addi rive increase gives slope of 1 as Throughou r increases CI mul riplica rive decrease decreases Throughpu r propor rionally equal bandwidTh share loss decreaSe window by facTor of 2 congesTion avoidance addi rive increaSe loss decreaSe window by facTor of 2 congesTion avoidance addiTive increaSe Connection 2 Throughput 7U ConnecTion 1 ThroughpuT R Ne rwork Analysis EndToEnd 558 Why TCP Performance is Cr39iTical CI Because of The impor39Tance of IP neTwor39ks TCP is The primary provider of endToend ser39vice CI NeTwor39k funcTions ar39e ofTen implemenTed in hardware while TCP is implemenTed in sofTwar39e CI TCP is complex and inTer39acTs wiTh many elemenTs in The endToend paTh CI TCP has ToTaI conTr39ol over39 The Tr39anspor39T of each byTe of any TCPbased applicaTion NeTwor39k Analysis EndToEnd 559 Measures of TCP Performance CI Delay roundTrip or oneway CI Maximum delay CI Delay variafion or delay ji r rer CI Packef loss rafe CI Effecfive Throughpu r CI Throughpu r varia rion CI File Transfer Time CI Fairness refers To fair alloca rion of a resource such as bandwid rh CI Resource consump rion CPU memory e rc Ne rwork Analysis EndToEnd 560 Simple TCP Model Let Wt be a stochastic process that gives Window size at time t 2 0 We continued to assume the AIMD model for this process Thus Wt increases linearly up to a maX of W While no packets are lost in the network When a packet is lost we have Wt 2 and then a linear increase until maX is again reached W 2 Periodic sawTooth function Network Analysis EndToEnd 561 Model continued Let X t be the the packet transmission rate at time t 2 0 Then the W0 common approximation is that X t Note that this assumes that increasing the transmission rate does NOT increase RT T We also assume that there is a constant probability p that any given packet is lost as it crosses the endtoend connection If L is a random variable giving the number of packets transmitted between two lost packets then L has a geometric distribution and P L k 2 p1 pk 1k 1 00 Thus EL i 19 Network Analysis EndToEnd 562 Model continued 2 Thus i is the expected number of packets transferred during a single P period of WC We now obtain this a second way Let T be the length of the period and notice that the area under one period W 1 WoT 1T W This represents approximately 2 22 2 Z kaTk which represents the period as being divided into intervals kl of length ATk during which the window is of size wk Thus the average AT 1 Window s1ze1sWZwk k 2 WE H T 2 2 Network Analysis EndToEnd 563 Model continued 3 It follows that the average transmission rate is f and the average number of packets transmitted during one period is ET 2 1L W E 2 RT T 2 Because the window increases by one for each roundtrip time during one period we must have T W RTT RTTVZV Thus the above becomes 2 T We now set the two expressions for average packets transmitted to be equal l WK 2i andsolveforW 2 2 2 p 3p Network Analysis EndToEnd 564 Model continued 4 We can now write an expression for the average sending rate of a TCP source as a function of the loss probability aV ackets sent i l 3 mm gquot p W period length RT T 7 RT T 2p This result is called the quotinverse squareroot p lawquot It demonstrates that the transmission rate of a TCP source is inversely related to the roundtrip time and the squareroot of the average packet loss probability Network Analysis EndToEnd 565 Example What is the average sending rate of a TCP source if the average roundtrip time is 350 ms and the probability that a packet is lost anywhere along the TCP connection is 002 Answer Y L 247 pktssec 035 004 Ref M Mathis J Semke J Mahdavi The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm ACM Computer Communications Review July 1997 Network Analysis EndToEnd 566 The effec r of errors on TCP CIWhenever an error is de rec red in The lower layers a packe r is discarded CITCP assumes packe r was los r because of ne rwork conges rion oConges rion window is reduced inappropria rely CITl IiS is par ricularly a problem Today in wireless ne rworks Ne rwork Analysis EndToEnd 567 Effect of error rates 2 o Connection Bandwidth Measured Percent MM Achieved Single 15 Mbps 070 Mbps 47 WLAN WLAN 135 Mbps 031 Mbps 23 15 Wired Links IEEE 20 Mbps 098 Mbps 49 80211 IEEE 11 Mbps 43 Mbps 39 8021 lb NCTWO K HHGIYSIS na IOIZY39IO 5 68 Approaches to Improve TCP over Wireless Nets CI Split TCP connections at gateways between wireless and wired links 0 Any retransmissions cross wireless connection only 0 Connections over wired links are unaware of losses El Snooping inside TCP connections 0 Snooping agent maintains buffer of TCP segments and maintains state 0 Segment resent locally before endtoend TCP connection times out CI Explicit Loss Notification 0 Can be sent by Snooping agent on loss unrelated to congestion o Requires use of ELN bit in TCP header Network Analysis EndToEnd 569 Summary El principles behind Transpor r layer services 0 mul riplexingdemul riplexing o reliable da ra Transfer 0 flow con rrol o conges rion con rrol o fairness CI ins ran ria rion and implemen ra rion in The In rerne r o UDP o TCP Ne rwork Analysis EndToEnd 570 Conges rion Con rrol in Connec rion Orien red or VC Ne rwor39ks Network Analysis Resources amp 671 Conqes rion Congestion Control Principles Open Loop Prevent problems by good design When does net accept new traf c When does net discard packets Which packets get prioritized Closed Loop Monitordetect congestion in network Pass congestion info to where action can be taken feedback loop Adjust operation to correctreact to problem GOOD ARCHITECTURESoften use both approaches Network Analysis Resources amp 672 Conqes rion Admission Control Open Loop Version Use owspec paraneters to assign resourcesto every VC admitted to the network Once ail resources have been committed reject further connections Closed Loop Version When a certain level of congestion has been measured and feedback g39ven to entry nodes of network reject further connections Network Analysis Resources amp 673 Conqes rion Feedback T echniques Router detects congestion from queues or otherwise and sends information to source Info can also be collected with probe packets Which source How quickly to react Note that this control traffic increasesthe load precisely when network already in trouble Bitbits can be reserved in each header Network Analysis Resources amp 674 Conqes rion W hen congestions occurs Increase resources Bring up additona dialup lines Bring up additional routersswitches Dedicate more bandwidth on existing lines Solit traffic along multiples routes Decrease load Don39t allow additional users Remove users with lower priority Give someail users less bandwidth Network Analysis Resources amp 675 Conqes rion Policiesthat Affect Congestion Layer Policies Transport quot0 Retransmission policy Outoforder caching policy 0 Acknowledgement policy 0 Flow control policy Timeout determination Network 0 Virtual circuits versus datagram inside the subnet 9 Packet queueing and service policy Packet discard policy 0 Routing algorithm 39 0 Packet lifetime management Data link 9 Retransmission policy Outoforder caching policy 0 Acknowledgement policy 0 Flow control policy Network Analysis Resources amp 676 Congestion Qualify of Service CI We have previously seen Tha r ATM for example suppor rs several service classes CBR VBR ABR UBR and Tha r each is designed for par ricular Types of applica rions 0 Including realTime applica rions CI Defn Ne rworks Tha r suppor r such differen r levels of service are said To suppor r quali ry of service QoS Ne rwork Analysis Resources amp 677 Conqes rion Real Time Audio Example CI Samples of analog audio ar39e collecTed and digiTized using an AgtD conver39Ter39 CI Typically one sample collecTed each 125m CI To sound accur39aTe They musT be played ouT aT The receiving end aT exachy This r39aTe CI Regardless of packeT neTwor39k ar39chiTecTur39e iT is noT possible To guar39anTee exacT i nTer39ar39r39ivals CI This is handled Thr39ough use of a playback bufferquot NeTwor39k Analysis Resources amp 678 ConqesTion Approaches to QoS Support CI Finegrained approaches provide QoS to individual applications or flows 0 Integrated Services from IETF associated with RSVP 0 ATM when supporting QoS to applications CI Coarsegrained approaches provide QoS to large classes of data or to aggregated Traffic 0 Differentiated Services IETF 0 ATM when used for aggregated backbone traffic Network Analysis Resources amp 679 Congestion Integrated Services Classes El IETF defined service classes and a protocol to support them RSVP in 19951997 CI Guaranteed Q05 this class is provided with fi bounds on queuing delay at a router envisioned for hard realtime applications that are highly sensitive to endtoend delay expectation and variance CI Controlled Load this class is provided a QOS closely approximatinq that provided by an unloaded router envisioned for today39s IP network real time applications which perform well in an unloaded network Network Analysis Resources amp 680 Conqestion InTegraTed Services Mechanisms El To geT specific service musT describe The Traffic To be submiTTed and musT requesT The parTicular service characTerisTics o Flowspec includes TSpec and Rspec El For guaranTeed QoS The source39s Traffic characTerizaTion is essenTially given by a Token buckeTquot wiTh parameTers qC and The requesTed service by a max packeT Transmission raTe M o C is buckeT capaciTy byTes o q is Token arrival raTe byTessec o M max oquuT raTe NeTwork Analysis Resources amp 681 ConqesTion T raffic Shaping Reduces impact of quotburstyquot traffic on network by regulating average RATE Usually occurs in virtual circuit networks like ATM User and subnet agree on traf c characteristics for particular VC Eg average burst length max burst length average rate Sanet monitors VC a1d discards itstraf c when ageement violated if network is congested called quottraffic policing39 Network Analysis Resources amp 682 Conqes rion Leaky Bucket Algorithm 1986 Allows ONLY steady outan rate with bursty input H051 Faucet i g 1 Packet Exanple 1MBytes a39rive D Unregutated ttow in 40 msec burs each sec B We h td packets Interface nta tn tng a leaky bucket 3 Regulated Example output ratels D New Water dr tps out of the 6 2 MBytessec aeady or E hate at a constant rate 1MB in 500 msec Network Network Analysis Resources at 683 Conqesfion Token Bucket Algorithm Allows limited burstiness up to max depth of token bucket Note in both leaky bucket and token 7 bucket versionsavariation is possible Host H St in which a speci c number of bytes is computer 39 computer authorized as output per token or per second instead of one packet or cell Useful with variable packet El One token is added CI The bucket length tra lC to the bucket El holds every AT D tokens 390 o o UDDQDD Networks Networks a b Network Analysis Resources amp 684 Conqestion Congestion thhirur39 W 0 ER 3 8 9 Hal Choose best available endtoend r Eute I eserve required ggr hdmput bursts quotratebasedquot i djust bandWIdth as gti needed I Discard packets if necessary Network Analysis Resources amp 685 Conqes rion Bandwidth allocation guarantee loss requirements use network resources efficiently fff nm equivalent capacity time Equivalent Capacity the amount of bandwidth to guarantee that CLR is below a given maximum eps A function of R m b Buffer size X Maximum CLR eps R Peak Rate m Mean Rate b Mean Burst Length EC the size ofopening to guarantee that overflow ratio is below a given maximum eps Fluid model Network Analysis Resources amp 686 Conqes rion Max Burst Length for Token Bucket Algorithm First thought it isjust max data correspondingto max tokens bucket depthoutput transmission rate Example 1Mbyte25MBytesec 40 msec WRON G because more tokens arrive as data transmitted Let Sburst length secs Let C bucket capacity bytes Let qtoken arrival rate bytessec Let M peak output rate bytessec Output burst oonta39ns CqS bytes until bucket is empty Also whatever Sequals there are MS bytes in the max burst lmplies CqS MSso S CMq Network Analysis Resources Si 687 Conqes rion Exam ple A token bucket supports a network of 003 connections Max capacity of the bucket is 100 megabits and the bucket is filled at a rate of 10 mbps What isthe max burst length in bits C 100x106 M q 155x106 10x106 MaxBurstBitS 069155gtlt106 10696 megabits sec 2 690ms Note also that the worstcase delay for a packet regulated by a token bucket is C M provided qltM Network Analysis Resources amp 688 Conqestion InTegraTed Services Mechanisms ReTurning CI To geT specific service musT describe The Traffic To be submiTTed and musT requesT The parTicular service characTerisTics 0 Flowspec includes TSpec and Rspec CI For guaranfeea Q05 The source39s Traffic characTerizaTion is essenTiaIly given by a Token buckeTquot wiTh parameTers qC and The requesTed service by a max packeT Transmission raTe M NeTwork Analysis Resources amp 689 ConqesTion Flow Specification For thisto work sender subnet receiver must agree to traffic parameters as described in aflow spec describes characteristics of injected traffic describes the desired quaity of service Source describes its traf c and desired QoSto subnet Sanet may accept or negotiate or reject If successful source then works with receiver to get same agreement Network Analysis Resources amp 690 Conqes rion Resource ReservaTion ProTocol RSVP El Signaling proTocol buT designed To operaTe on Top of The connecTionless IP neTworks O SupporTs mulTicasT El Idea clienT requesTs To parTicipaTe in a mulTicasT group say To receive a movie CI The mulTicasT Tree is build wiTh sender aT The rooT El Sender sends TSpec To receiver or clienT o In a PATH message El Receiver geTs PATH message and sends RESV message back To sender wiTh sender Tspec and receiver Rspec 0 Each rouTer along The paTh decides To accepT or rejecT NeTwork Analysis Resources amp 691 ConqesTion Main raining The connec rion CI Receiver sends RESV message each 30 secs CI If RESV messages s rop coming Then rou rers simply freeup Their resources 0 sof r s ra requot CI If rou res change receiver is no rified wi rh new PATH message and sends nex r RESV message along The new pa rh CI Mul ricas r suppor r New RESV reques rs can be aggrega red and Tspec39s may specify for example enough resources for k of n speakers Ne rwork Analysis Resources amp 692 Conqes rion Int Svcs Controlled Load CI Intent is to guarantee service that approximates lightly loaded router 0 Traffic is simply requested to be part of controlled load 0 Weighted Fair Queueing WFQ used to separate controlled load traffic from other 0 Admission control used to guarantee service levels Network Analysis Resources amp 693 Conqestion Scalability of Integrated Services CI RSVP may require that each flow passing Through a router have a reservation 0 Notice there can be 39000 kbps audio streams in a single OC48 connection 0 Information needs to be refreshed 0 Router must classify police and manage queues for each flow 0 Admission control decisions must be made CI Many ISPs avoid because of complexity Network Analysis Resources amp 694 Congestion Differentiated Services CI Intended to address the following difficulties with Intserv and RSVP El Scalability maintaining states by routers in high speed networks is difficult due to the very large number of flows El Flexible Service Models Intserv has only two classes want to provide more qualitative service classes want to provide relative39 service distinction Platinum Gold Silver El Simpler signaling than RSVP many applications and users may only want to specify a more qualitative notion of service Network Analysis Resources amp 695 Conqestion Differen ria red Services CI Approach 0 Only simple func rions in The core and rela rively complex func rions a r edge rou rers or hos rs 0 Do no r define service classes ins read provides func rional componen rs wi rh which service classes can be buil r CI Bo r rom Line In regra red and Differen ria red Services are Rarely Used Ne rwork Analysis Resources amp 696 Conqes rion Chap rer 1 Founda rion Dr39 G A Mar39in Network Analysis Founda rion 11 19708 Business Environment IBM39s SNA Hierarchical orderly reliable Ssdef for Topology and Paths Connectionoriented and guaranteed service at link layer data only Lowspeed unreliable leased lines Research Environment TCPIP Distributed disorderly less reliable Next hop vs fixed paths Connectionless data only Phone Compa1ies European X25 Smdad Connectionoriented SVC and WC with Flow Control Assumes noisy lines Network Analysis Foundation 12 19805 NSFNet Backbone to Interconnect Siper Computers TCPlPof cia protocol of Arpenet in 1983 56 kbps backbone for 6 super computer centers Thousands of researchers connect their subnets Version 2 IBM RSSOOOs and Fiber ran at 448 kbps By 1990 15 Mbps AN Stakes over a1d upgadesto 45 Mbps Merit MCI IBM IBM Develops Advanced PeertoPeer Networking LAN Growth Explosive Ethernet collisions Token Ring no collisions Novell39s Netware IPX based on XNS Network Analysis Foundation 13 19908 Internet 1990 200000 computers and 3000 networks 1995 multiple backbones 100s regional nets 10s of thousands of LAN 8 millions of hosts Doubles yearlyl WWW application CERN brings internet to nonacademics mosaic N REN Gigabit Network funded by ARPA amp NSF Internet Society Founded 1992 Commercidly Cisco uses lPto gow to Billions in revenue Network Analysis Foundation 14 1 990s continuec MIT U Pa IBM Bellcore Research in highspeed paket srvitching Frane Relay Forum evolve X25 concepts for higher speed WAN lines 15Mbps ATM becomes successful in telephony backbones multiples of 155mbps DARPA Funding Next Generation Internet multigigabit per second capabilities Network Analysis Foundation 15 Foundation Goals CI Lay foundation for understanding how to build a network 0 O O O 0 Required connectivity Required services Terminology Layered architecture TCPIP amp OSI Protocols and Applications Socket Interface Performance Metrics Overview CI Applications CI Requirements CI Network Architecture CI Performance CI Channel Multiplexing Network Analysis Foundation 16 Applications CI Distributed processes communicating across network CI Examples world wide web email FTP streaming audio amp video chatrooms CI Use Application Layer Protocols CI User agent implements the application layer protocol 0 Web browser 0 Email mail reader eg outlook O Streaming audiovideo media player Network Analysis Foundation 17 CIien r server paradigm Typical ne rwork app has rwo pieces cI39em and server dafa link physical Clien r CI ini ria res con rac r wi rh server speaks firs rquot CI Typically reques rs service from I I server 3 r 39 re ly CI Web clien r Implemen red In browser email in mail reader m 39 39 lt6 41733303 de ralinlr p ySIca CI provides reques red service To clien r CI eg Web server sends reques red Web page mail server delivers email Ne rwork Analysis Founda rion 18 The Web the http protocol http hypertext transfer protocol CI Web39s application layer protocol CI clientserver model 0 cfem browser that requests receives quotdisplaysquot Web objects 0 server Web server sends objects in response to requests Server running NCSA Web Server Mac running CI http10 RFC 1945 Navigator CI http11 RFC 2068 Network Analysis Foundation 19 The http protocol http TCP transport service CI client initiates TCP connection creates socket to server port 80 CI server accepts TCP connection from client CI http messages application layer protocol messages exchanged between browser http client and Web server http server CI TCP connection closed 1 more http is stateless CI server maintains no information about past client requests aside Protocols that maIntaIn quotstatequot are complex CI past history state must be maintained CI if serverclient crashes their views of quotstatequot may be inconsistent must be reconciled Network Analysis Foundation 110 http example Suppose user enters URL contains text wwwsomeSchooedusomeDepartmenthomeindex references to 1 0 jpeg images 1a http client initiates TCP connection to http server process at wwwsomeSchooledu Port 80 is default for http server 1b http server at host wwwsomeSchooledu waiting for TCP connection at port 80 accepts connection notifying client 2 http client sends http request message containing URL into TCP connection socket 3 http server receives request message forms response message containing requested object someDepartmenthomeindex sends message into socket time 1 Network Analysis Foundation 111 h r rp example cont 4 hTTp server closes TCP connecTion 5 hTTp cienT 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 Ne rwork Analysis Founda rion 112 Elec rronic Mail ougomg messagequeue E u3errnaHbox Three major componen rs CI user agen rs CI mail servers CI simple mail Transfer pro rocol sm rp User Agen r CI aka mail readerquot CI composing edi ring reading mail messages CI eg Eudora Ou rlook elm Ne rscape Messenger agenT CI ou rgoing incoming messages m L s rored on server user agenT Ne rwork Analysis Founda rion 113 Elec rronic Mail mail servers Mail Servers CI mailbox con rains incoming messages ye r To be read for user CI message queue of ou rgoing To be sen r mail messages CI sm rp pro rocol be rween mail servers To send email messages 0 clien r sending mail 096m server air I u u USCIquot 0 server receIVIng maI 096m server Ne rwork Analysis Founda rion 114 ElecTronic Mail smTp RFC 821 CI uses Tcp To reliably Transfer email msg from cienT To server porT 25 CI direcT Transfer sending server To receiving server CI Three phases of Transfer 0 handshaking greeTing 0 Transfer of messages 0 closure CI commandresponse inTeracTion o commands ASCII TexT 0 response sTaTus code and phrase El messages musT be in 7biT ASCII NeTwork Analysis FoundaTion 115 Sample sm rp in rer39ac rion momooowomomomouz 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 quot Do you like ketchup How about pickles quot on a line by itself 250 Message accepted for delivery QUIT 221 hamburgeredu closing connection Network Analysis Founda rion 116 Try sm rp in rerac rion for yourself El telnet servername 25 CI see 220 reply from server El en rer HELO MAIL FROM RCPT TO DATA QUIT commands above le rs you send email wi rhou r using email clien r reader Ne rwork Analysis Founda rion 117 smtp final words D SquotWP U563 Plt quot3i3len r Comparison with http connections h I H CI smtp requires message D HP39IPU header amp body to be in 7 D ema39l39 PUSh bll ASCII CI both have ASCII CI certain character strings commandresponse OT Permllled in quot 59 691 interaction status codes CRLFCRLF Thus msg has to be encoded usually into Cl h r rpi each object either base64 or quoted encap5ulated in its own printable response msg CI smtp server uses CI smtp multiple objects sent CRLFCRLF to determine in multipart msg end of message Network Analysis Foundation 118 Foundation Goals CI Lay foundation for understanding how to build a network 0 O O O 0 Required connectivity Required services Terminology Layered architecture TCPIP amp OSI Protocols and Applications Socket Interface Performance Metrics Overview CI Applications CI Requirements CI Network Architecture CI Network Software CI Performance CI Papers CI Problems Network Analysis Foundation 119 Connectivi ry roufer lserver Ne rwor39k exis rs To connecT compu rer39s May suppor39T a s rr39ic rly limi red number or39 many If suppor39Ts gr39ow rh if is said To quotscalequot 39 u company g 7 network gg Network Analysis Founda rion 120 Links and Nodes CI Ne rworks inlude nodes rou rers swi rches compu rers some of which are direc rly connec red by links CI Links coax cable Twis red pair fiber are ei rher poinTTopoin r or mul riple access CI Coopera ring nodes can provide connec rivi ry across several direc r links 0 Direc rly connec red 0 Indirec rly connec red Ne rwork Analysis Founda rion 121 Mul riple Access Links and Pr39o rocols Thr39ee Types of quotlinksquot El poin r ropoin r single wire eg PPP SLIP El broadcas r shared wire or39 medium eg E rher39ne r Wavelan e rc Blah blah blah 3 ed igN Va 3 l E 2222222222222 I shared wire shared wireless satellite cocktail party eg Ethernet eg Wavelan El swi rched eg swi rched E rher39ne r ATM e rc Network Analysis Founda rion 122 A working network Token Ring ATM 0012 0048 Frame Relay gt Public Data Network X25 X21 gt ATM TCP Sprayer 39XX 374X HPRIP 03A MAE HPRATM RSVPIS IPSEC BUT COMPLEXITY Network Analysis Foundation 123 Terminology CI Swi rched Ne rwork A ne rwork of nodes organized sys rema rically To forward da ra as if moves from source To des rina rion CI Circui r Swi rched es rablishes a circui r from en rry poin r To exi r poin r of ne rwork and analog or digi ral da ra moves along circui r wi rh s rric r Timing CI Packe r Swi rched Nodes in ne rwork send discre re blocks or packe rs of informa rion from one node To nex r un ril des rina rion Ne rwork Analysis Founda rion 124 Terminology El One hop packet moves across a network from one node to a node directly connected Each movement is a hop toward the destination El StoreandForward Packet is received in its entirety is stored and processed in an intermediate node and is then forwarded to an adjacent node El Virtual Circuit A storeandforward network that provides circuitlikequot service by setting up an endtoend connection that guarantees certain quality of servicequot Network Analysis Foundation 125 Basic Concepts Host a node that usesthe network outside the network SNitch a node that implementsthe network inside the network Internetwork A set of independent networksthat are interconnected RouterGateway a node connected to two or more networks Address a byte string that identi es a node Routing a process of forwarding packets across a network based on source and destination addresses Unicast a1d Multicast Addresses addresses assigned to single or multiple destinations Network Analysis Foundation 126 Foundation Goals CI Lay foundation for understanding how to build a network 0 O O O 0 Required connectivity Required services Terminology Layered architecture TCPIP amp OSI Protocols and Applications Socket Interface Performance Metrics Overview CI Applications CI Requirements CI Network Architecture CI Performance CI Papers CI Problems Network Analysis Foundation 127 Ne rwork Archi rec rure El Is The blueprin r rha r guides The design and implementation of a Type of ne rwork CI The blueprin r follows a philosophy rha r falls be rween send and prayquot and guaran reed El Generally includes a layer reference model El Includes The forma rs and flowsquot describing pro rocols and various layers El May include apple rs To be used by userlayer applica rions El Trea rs user designer and service provider perspec rives Differing PerspecTives CI ApplicaTion programmer cares mosle abouT The services ThaT The neTwork provides and The cosT for Those services 0 Loss of daTa 0 Errorfree delivery 0 Delay CI NeTwork designer cares ThaT neTwork resources are used efficienle and allocaTed To users fairly CI NeTwork provider wanTs ease of adminisTraTion and fauT managemenT NeTwork Analysis FoundaTion 129 Network architecture CI Network must provide 0 Connectivity 0 Required service levels 0 Robustness in case of failures 0 Fairness to users 0 Costeffective solutions CI Again A network architecture is a blueprint for a way of building a network that will satisfy all its requirements 0 Philosophy algorithms flows and formats Network Analysis Foundation 130 OSI Reference Model er Protocol Application Lay 5 Application rvice Interface Layer Protocol Presentation Presentation A Layer Protocol 1F ssion Session Transport Layer PmtOCOI r Transport Network Network Network Data Link Data Link Data Link Data Link Physical Physical Physical Physical Network Analysis Foundation 131 Layers Services Protocols Layers offer servicesto higher layers that are requested by paraneters being passed to service access points SAPS Services A set of primitives operations that a layer ca1 perform for its users Protocol is a set of rules governing the format a1d mea1ing of franes packets or msgs excha1ged by peer entities Protocols implement the services Network Analysis Foundation 132 Layer Overview Physical Layer Transmits bits over comm channel How to represent bits and ensure reception Physical medium lies logically below Data Link Layer Takes raw transmission facility and transforms to line free of undetected transmission errors Sends dataframes Retransmits if needed Flow control usually provided Network Layer Gets packetsfrom source to destination across a network Provides routing network congestion control call admission net net if perhaps accounting to support net mgt Transport Layer Accept datafrom session layer segmentation amp reassembly if needed pass to network layer assure all pieces arrive safely at other end First endtoend layer Multiplexing flow control Network Analysis Foundation 133 Layer Overview continued Session Layer Provides enhanced services to certain applications over those provided by transport layer Synchronization as example Presentation Layer Provides additional functions such as translation among different character numerical and bitstring representations Application Layer Sipports protocols needed by applications such as network virtual terminal le format conversions electronic mail remote job entry etc Network Analysis Foundation 134 TCPIIP amp Course Reference Models Application Layer Application Layer Course TCPl P Transport Layer Transport Layer Internet Layer Network Layer Data Link Layer Hosttonetwork Physical Layerr Network Analysis Foundation 135 Nefwor ks Infereonnecfed by IP Rou rer s J E E3 g 487 J g E TCPIIP Application Layer Contains all higher level protocols incl uding Telnet Virtual terminal protocol FI39P le transfer protocol SVITP Smple Ma39l Transfer Protocol DNSDoma39n Name rvice HTTP WorldWide Web page trasfer protocol Network Analysis Foundation 137 TCPIIP Layer Overview Internet Layer Heart of the Internet architecture Hosts insert packets into IP network that travel independently to destination over distinct subnets Implementsthe IP Internet Protocol quotprotocolquot Routing and network congestion avoidmce are key issues Trmsport Layer Endtoend peer protocol as in OS model Two protocols de ned Transmission Control Protocol TCP awd User Datagam Protocol UDP TCP is reliable and connectionoriented SJpports segmentation awd reassemny with sequence no39s aswell as ow control UDP is unreliable and connectionless Used with aosthat do their own thing or voice or video or Network Analysis Foundation 138 Hybrid Model CI The hybrid reference model to be used in this course 39lDl O391 Application layer Transport layer Network layer Data link layer Physical layer Network Analysis Foundation 139 Two major models for layer services CI ConnecTionorienTed service 0 Like The Telephone neTwork 0 EndToend agreemenTs made before user Traffic flows 0 GreaTer complexiTy and greaTer reliabiliTy CI ConnecTionless service 0 Like The posT office neTwork 0 Each leTTer packeT moves independenle Through The neTwork 0 Simpler and reliabiliTy can be improved wiTh higherlayer services like regisTered mail NeTwork Analysis FoundaTion 140 Examples of ConnectionOriented and Connectionless Services Service Example Connection lt Reliable message stream Sequence of pages oriented Reliable byte stream Remote login Unreliable connection Digitized voice f Unreliable datagram Electronic junk mail connecllgsn Acknowledged datagram Registered mail 1 Requestreply Database query Note well that connectionoriented and connectionless are characteristics that can be applied at each layer in the protocol hierarchy Network Analysis Foundation 141 In rerne r Transpor r pro rocols services TCP service UDP service CI connecfbnorenfea se rup g unreliable data Transfer required be rween clien r between sending and server receiving process CI reiabe franspor39f be rween sending and receiving process CI fow confros sender won39T overwhelm receiver CI conges on com r39os Thro r rle sender when ne rwork CI does no r provide connec rion se rup reliabili ry flow con rrol conges rion con rrol Timing or bandwid rh guaran ree overloaded CI does nof provide riming Q Why boTher39 Why is minimum bandwid rh There a UDP guaran rees Ne rwork Analysis Founda rion 142 Exam ple N etworks Sstem Network Architecture SNA IBM39s networking architecture used by 10000 business networks Mainframe model of computinghierachicd Followed by Advanced PeertoPeer Networking APPN architecture Novell Netware Predominant PCbased network architectureclientserver modeldownsizing Proprietary protocol stack derived from XNSsimilaitiesto IP IFX uses 10byte vs 4 byte IR addresses Network Core Protocol N CH for connectionoriented transport Network Analysis Foundation 143 Exam ple N etwor ks continued ARPAN EI39 Funded by Advanced Research Projects Agency ARPA in early 605 as commandcontrol network Introduction of packetswitching vs circuitswitching Hosts connected to subnet of IMPs Interface Msg Processors Incredible growth Led to invention of TCPIP model in 1974 nt Cerf amp Bob Kahn Protocols integrated into Berkeley UN IX by BBN and provided free with UNIX Iicenseexplosive Network Analysis Foundation 144 Exam ple N etworks continued N SFN El39 Designed by National Science Foundation as highspeed successor to ARPAN El39 for university access First connected six supercomputer centers San Diego Boulder Champa39gw Pittsburgh Ithaca Princeton First TCPIPWAN Eventually 20 regional networks connected to backbone In 1990 AN SAdva10ed Networks a1d Services took over and renamed ANSN El3945 mbps links amp first step towards commercialization In 1995 ANSN El39 sold to AOL awd reg39ona networks went to commercial service Network Analysis Foundation 145 Exam ple N etworks Continued Internet In mid80sthis collection of lP based networks began to be viewed as quotthe Internet Growth exponential I Defn Machine on Internet if runs TCPIP has IP and sends leacketsto other internet hosts Internet Society founded in Jan 1992 WWW Wordwide Web application brought millions of nonacademic users to Internet in early 90s web pages links ubiguitous URLs Network Analysis Foundation 146 X 25 N etworks A standard developed by CCITT now ISD in 19703 De nesthe usernetwork or hostnetwork interface Physical layer is X21 mostly analog R3232 used instead Network layer handles addressing owcontrol delivery confirmation User establishes aquotvirtual circuit and sends max 128 byte packets reliably and in order I both permment a1d switched virtual circuits F VCSJC Flow control ensures fast sender does not swamp receiver For nonX25 terminals a Packet assemblerdisassembler is used PAD Terminal X28 PAD X29 stmdads also de ned Note X25 limited to 64 kbps widespread in Europe Network Analysis Foundation 147 Frame Relay Also connectionoriented standaard for moving bits generally across a public network Takes advantage of fact that leased lines are now fast digital reliable gt simple protocols Hedominantly avirtual leased line PVC today Frames can be up to 1600 bytes and carry a number dlci identifying the virtual circuit Contract with carrier for an average service burst alowed as in SVIDS Generally operates at T1 1 5mbps or above FR determines start and end of frame detects some transmission errors discards bad frames No ow control yet de ned only a Cl bit Network Analysis Foundation 148 BI SDN Architecture ATM envisioned for universal networking integrated networking voice video data and image in the same network scaleable in distance LAN MAN WAN scaleable in bandwidth 15 Mbps to several Gbps Asynchronous Transfer Mode Network Analysis Foundation 149 Why connection oriented providing service guarantees require resources to be reserved in the network simpler network management Why xed size cells efficient switching hardware switching Why small size cell mainly for voice Network Analysis Foundation 150 ConnectionO riented vs Connectionless ConnectionOriented Path created fixed from transmission site to destination Intermediate nodes set aside resources for the new connection Connection may be allocated a given transmission rate r bps Each comm link dedicates bandwidth r to this connection if needed for connection type If no path can be found having r bps on all links call is rejected Network Analysis Foundation 151 Connectionless Session setup without reserving ba1dwidth across network Firstcome rstserved a1d no performa1ce guarantees chmg39 ng now No caladmission decision All users accepted if connected Packet waits in queue if needed to be transmitted on next link Advantage is that data ca1 be sent without any connectionsetup protocols Network Analysis Foundation 152 Example Protocol Graph FTP HTTP Video TFTP Ethernet Note One architecture may ride on top of another Network Analysis Foundation 153 Other Net Arch Internet apps application transport protocols Application Underlying Application layer protocol transport protocol email smtp RFC 821 TCP remote terminal access telnet RFC 854 TCP Web http RFC 2068 TCP file transfer ftp RFC 959 TCP streaming multimedia proprietary TCP or UDP eg RealNetworks remote file server NFS TCP or UDP Internet telephony proprietary typically UDP eg Vocaltec Network Analysis Foundation 154 Foundation Goals CI Lay foundation for understanding how to build a network 0 O O O 0 Required connectivity Required services Terminology Layered architecture TCPIP amp OSI Protocols and Applications Socket Interface Performance Metrics Overview CI Applications CI Requirements CI Network Architecture CI Performance CI Channel Multiplexing Network Analysis Foundation 155 Performance bandwidTh CI BandwidTh 0 May imply The widTh of a frequency band eg 3000Hz O BandwidTh of a communicaTion link means The max biTspersecond The link supporTs eg FasT ETherneT is 100 mi llionbiTspersec CI ThroughpuT 0 Usually implies achievable performance for The daTa uniT of i nTeresT user daTapackeTeTc Typical measures are biTssec kassec eTc 0 Depends on inpuT raTe To The channel 0 Influenced by proTocol and proTocol daTa uniT overhead NeTwork Analysis FoundaTion 156 Performance delay CI Delay or laTency is The lapsed Time beTween The sTarT and end of an evenT of i nTeresT 0 ReTrieving daTa from a disk 0 Sending a frame on an eTherneT link 0 Sending an IP daTagram across The InTerneT CI Measured in Time eg 24 milliseconds To send a packeT from US easT To wesT coasT CI May be inTeresTed in oneway or in RTT roundTripTime NeTwork Analysis FoundaTion 157 Link DeayQueueTransmiTPr39opaane Time CI Queue Time is Time a packeTbiT waiTs To begin Transmission from a node CI Tr39ansmiT Time 0 T 2 Size bitsBandwidth bits per sec CI Pr39opagaTion Time 0 5 2 Distance m km feet miles Propagation Speed CI Pr39opagaTion speed 0 3gtlt108 msec in a vacuum 333 C23gtlt108 msec in a cable 435 0 2gtlt108 msee in fiber39 5 NeTwor39k Analysis FoundaTion 158 Simple Performance Example CI How long does iT Take To send a 1000 byTe fr39ame over39 a 1000km 100 Mbps link from The Time Transmission begins To The Time frame is received no queueing delay CI Ans BandwidTh should be bps so we musT conver39T byTes To biTs Then we divide by bandwidTh and add pr39opagaTion delay 1000 bytes X 8 6 Transmission Time is W80X10 Gsec80 sec 1000 x103 meters PPOPOgO I ion is W4348x10 3sec4348ms ToTaI Time is 4428 ms NeTwor39k Analysis FoundaTion 159 Problem Calculate the latency from rst bit sent to last bit received of the following lOMbps Ethernet with a single storeandforward switch in the path and a packet size of 5000 bits Assume that each link introduces a propagation delay of 10 us and that the switch begins retransmitting immediately after it has nished receiving the packet 10Mbps QM 3C El 8 I 10x10396 sec 10x10396 sec 1 Transmit 5 000 bits 2 500 gtlt10 6 sec 10gtlt106 bitec 2 Propagate last bit on first link 10 gtlt10 6 sec 5000 bits 6 bits lOgtltlO AGO 4 Propagate last bit on second link 10 X 10 6 sec 3 Total 2102 ms 3 Transmit 500 gtlt10 6 sec Network Analysis Foundation 160 Problem Two nodes A and B are separated by 2000km and are connected by a fiber 10 Mbps pointtopoint link Suppose that node A transmits 1000 packets per second to node B and that each packet is 1000 bytes long Also assume that each packet is delayed for 1 ms in node A 1 What is the delay that each packet experiences from arrival at A to arrival at B 2 What is the bandwidth of the link What is the throughput of the link The ratio of these two quantities determines link quotutilizationquot usually defined as 0 where 0 is utilization l is throughput bps and c c is capacity or bandwidth bps Find the utilization of the link Network Analysis Foundation 161 Solution The link delay is given by 8 000bits 2 000071 lOMbpS 20gtlt108 80gtlt102 2gtlt106 Wsec2 108sec 00118sec 118ms X X dqtttpdlms 0001sec The bandwidth of the link is lOMbps Node A transmits 1000 pps with each packet 8000 bits gt 80Mbps thus the throughput is 8Mbps The utilization is clearly 08 notice NO dimension Network Analysis Foundation 162 WhaT causes queue delay aT A El SwiTch needs To move packeT or39 aT leasT poinTer39s from enTr39y por39T To exiT por39T on The swiTch CI Some delays are possible due To The communicaTion pr39oTocol being used CI Also There may be a waiTing line forming because The Tr39ansmiTTer39 is busy aT The exacT momenT ThaT a packeT is ready To Tr39ansmiT We39ll consider This IaTer39 NeTwor39k Analysis FoundaTion 163 Bi r Length previous example Propagation Speed 20x108msee gt Bandwidth Propagation Speed 20x108m sec L h engt BandWidth 10x106bpS b This implies that 100 000 bits can be 1 held or quotstoredquot on this link at one time Network Analysis Foundation 164 Deloy Bondwid rh Produc r CI Previous example showed 100000 bi rs of leng rh 20m fi r ring on The 2000 km fiber39 CI This can be dir39ec rly compu red using 6 delay gtlt bandwidth 2 2 X10 meters x 10 gtlt106 bps 2 x10 meters sec 2100 OOObitS Network Analysis Foundation 165 Foundation Goals CI Lay foundation for understanding how to build a network 0 O O O 0 Required connectivity Required services Terminology Layered architecture TCPIP amp OSI Protocols and Applications Socket Interface Performance Metrics Overview CI Applications CI Requirements CI Network Architecture CI Performance CI Channel Multiplexing Network Analysis Foundation 166 Abstract Communication Channel Server Network Analysis Foundation 167 Mul riple Access pro rocols CI single channel shared by mul riple nodes Two or more CI only one node can send successfully of a Time CI mufpe access pro focal o dis rribu red algori rhm rha r de rermines how s ra rions share channel ie de rermine when s ra rion can Transmi r o communica rion abou r channel sharing mus r use channel i rself O wha r To look for in mul riple access pro rocols synchronous or asynchronous informa rion needed abou r o rher s ra rions robus rness eg To channel errors performance Ne rwork Analysis Founda rion 168 Mul riple Access Pro rocols a Taxonomy Three broad classes El Channel Par ri rioning o divide channel in ro smaller quotpiecesquot Time slo rs frequency 0 alloca re piece To node for exclusive use El Random Access 0 allow collisions 0 quotrecoverquot from collisions El Taking turnsquot 0 Tigh rly coordina re shared access To avoid collisions Goal efficien r fair simple decen rralized Ne rwork Analysis Founda rion 169 Channel Partitioninq TDMA TDMA time division multiple access DDD DD D access to channel in quotr39oundsquot each station gets fixed length slot length pkt tr39ans tIme In each round unused slots go idle example 6station LAN 134 have kt slots 256 idle TDM Time Division Multiplexin c annel divided into N time slots one per user39 Ineftg39ICIent wuth low duty cycle users and at light load FD lr39eguency Division Multiplexing frequency sub IVIde Network Analysis Foundation 170 Channel ParTiTioninq FDMA FDMA frequency division mulTiple access CI channel specTrum divided inTo frequency bands CI each sTaTion assigned fixed frequency band CI unused Transmission Time in frequency bands 90 idle CI example 6sTaTion LAN 134 have ka frequenc ands 256 idle Time l L r frequency bands NeTwork Analysis FoundaTion 171 Random Access pro rocols CI When node has packe r To send 0 rr39ansmi r a r full channel da ra rate R o no a pn39orcoor39dina rion among nodes El Two or39 more rr39asnmi r ring nodes gt collision El random access MAC protocol specifies 0 how To de rec r collisions 0 how To recover from collisions eg via delayed r39e rr39ansmissions El Examples of random access MAC pr39o rocols O slo r red ALOHA o ALOHA o CSMA and CSMACD Network Analysis Founda rion 172 Slo r red Aloha El Time is divided in ro equal size slo rs pk r rrans Time El node wi rh new arriving pk r rransmi r a r beginning of nex r slo r CI if collision re rransmi r pk r in fu rure slo rs wi rh probabili ry p un ril successful nude 1 I l nudes I I I l l l l l l l l l l C E C 8 E C E S 8 Success 8 Collision C Empty E slots Ne rwork Analysis Founda rion 173 WhaT channel service does an app need DaTa loss CI some apps eg audio can ToleraTe some loss CI oTher apps eg file Transfer TelneT require 100 reliable daTa Transfer Timing CI some apps eg InTerneT Telephony i nTeracTive games require low delay To be effecTive BandwidTh CI some apps eg mulTimedia require minimum amounT of bandwidTh To be effecTive CI oTher apps elasTic apps make use of whaTever bandwidTh They geT NeTwork Analysis FoundaTion 174 Service requirements of common apps Application Data loss Bandwidth Time Sensitive file transfer no loss elastic no email no loss elastic n0 Web documents losstolerant elastic no realtime audiovideo losstolerant audio 5Kb1Mb yes 100 s msec video10Kb5Mb stored audiovideo losstolerant same as above yes few secs interactive games losstolerant few Kbps up yes 100 s msec financial apps noloss elastic yes and no Network Analysis Foundation 175 Common Failures CI Bi r er39r39or39 CI Bur39s r er39r39or39 CI Pocke r loss CI Link failure CI Node failure Network Analysis Founda rion 176 Failure Example Suppose that two nodes A and B are connected by a communication link and that node A is transmitting packets to node B On each transmission attempt the probability of an error in the packet is f In this case transmission fails and the packet must be retransmitted What is the expected number of transmissions per packet LetX 1 2 to represent the number of the rst successful transmission What do we call X What is the probability thatX 1 Write this as P X 1 What is P X 2 Recall the idea of independent events What is P X k for any positive integer k NOTE Return to this after review of introductory probability Network Analysis Foundation 177 Mul riplexing example con rinues CI Suppose Tha r 10 nodes are connec red in place of node A and are sharing The lOMbps link To B A1 A2 q I B A Network Analysis Founda rion 178 Recall TDMA and FDMA Example FD39V39A 4users IIII frequency 39 39 39 time TDMA frequency time Network Analysis Founda rion 179 Consider node A1 Suppose each lsec interval is divided into 1000 time slots and node Al is assigned each 10th slot beginning with slot 1 If incoming traffic is evenly distributed among all input nodes then each node will use 80 of its assigned 1 Mbps channel and total channel utilization will remain at 08 If all traffic is originating at node Al then no more than 1 Mbps of total traffic can be sent to B even though link utilization would only be 008 Network Analysis Foundation 180 Recall Slo r red Aloha El Time is divided in ro equal size slo rs pk r rrans Time El node wi rh new arriving pk r rransmi r a r beginning of nex r slo r CI if collision re rransmi r pk r in fu rure slo rs wi rh probabili ry p un ril successful El Throughpu r analysis requires probabilis ric me rhods nodal I nod92 ll nodes l I I I I I I I I I I I I I I I I I 39 3390 C E I a E I E s 5 Success 8 Collision C Empty E slots Ne rwork Analysis Founda rion 181 Slotted Aloha Throughput Analysis Recall throughput implies the number of packets per unit time that successfully cross the network To make tractable we assume that each workstartion transmits the same length packet every time and we take the quotslotquot time to be equal to packet transmission time We also take this to be our quotunit time Assume that there are n stations on the network and that the sum of all arrivals at these stations has a Poisson distribution with mean arrival rate of l per unit time or slottime length We make the simplifying assumption that the sum of all arrivals plus retransmissions due to quotcollisionsquot has a Poisson distribution with mean arrival rate of 2 per unit time Network Analysis Foundation 182 Slotted Aloha Continues Suppose any terminal begins transmitting a packet What is the probability that the packet transmits successfully In slotted Aloha success occurs if no other terminal got a packet ready for transmission during the previous slot that is if there are no other arrivals during unit time Let X be a random variable RV that gives the number of arrivals plus retransmissions in unit time X has a Poisson distribution with mean y thus k 7 7 e PXk k the slot prior to our given transmission is P X O 6 7 Because The probability of no quototherquot arrivals during the rate of transmission attempts is y per unit time and the probability of success for a given attempt is 6 7 then the throughput must be 76 7 Network Analysis Foundation 183 Max T hrouput in Pure Aloha S throughput per frame time 040 030 020 010 I Sloited ALOHA s GeG i i I i i Pure ALOHA S Gequot2G i I 0 05 10 15 20 30 G attempts per packet time Ne rwor39k Analysis Founda rion 184 Physical Layer Sec rion 2 Dr39 G A Mar39in Network Analysis Physical 21 Theor39eTical Basis for39 DaTa CommunicaTion CI Think of a Transmission signal being r39epr39esenTed as a funcTion f Ilastsb where The funcTion f gives a volTage value and The par39ameTer39 2 r39epr39esenTs Time CI Recall ThaT a funcTion is periodic wiTh period T if ftTfT for39 all values of l and There is no smaller posiTive value of T for39 which This is True CI NoTice ThaT any signal of finiTe lengTh can be made To be per39iodic by r39epeTiTion NeTwor39k Analysis Physical 22 Fourier Series Early in the 19th century the French mathematician J eanBaptiste Fourier proved that any quotreasonably behaved periodic function gt can be represented as the sum of sines and cosines such as l gt 2 6 2 an s1n27mft Z bncos27mft quot1 n1 1 where f is the fundamental frequency an and bquot are the quots1ne and cosine amplitudes of the nth harmonics terms and C is a constant The above equation gives the Fourier Series representation of the periodic function g We can find the constant and sine and consine amplitudes using an 2 Igt sin27mfdt bquot 1gtcos27mfdt c 1gtdt Network Analysis Physical 23 Fourier Example Tan 21 Compute the Fourier coefficients for the periodic function obtained from gtt forOStSl l T 2 an gtsin21nft dt gt 39lmnlmsh39 J 239quot39 39 Squot39quot 7 0 1t 412 2 T 1 Zcos7n2 1 4TEIlSlIlTIlCOSTEIl 1 bn 2 gtcos Znnft dt gt T 2 2 2 2 2 0 7 n 27 n In MathCad output cos7m2 means T 2 d l 301 T L go H what we usually write as cos27m Note bn a evaluate To 0 Network Analysis Physical 24 Nega rive Coefficien rs c1 Sine Amplitudes T21 31 36 41 46 51 56 61 66 71 76 81 86 91 96 Network Analysis Physical 25 rms ampliTudesab 035 03 025 02 015 01 005 0 15 913172125293337414549535761656973778185899397 Thus we may geT an accepTable r39econsTr39ucTion of The original gTT for example using The firsT 5O har39monics If The comm channel only leTs The firsT 4 har39monics Through The received signal may be badly disTor39Ted NeTwor39k Analysis Physical 26 Transmit an ascii b or39 01100010 1 To find the Fourier coef CIents we write T 8 f and let OfOIOStSI 1f0r1ltt2 1for2ltt3 0for3ltt4 0f0r4ltt5 0for5ltt 6 1f0r6ltt7 0for7ltt8 We can then use the de nitions to obtain the a b and c values n9 n9 g0 Network Analysis Physical 27 Approxima rions of Or39iqinal Siqnal 050 025 I I I I l I I 12 3 4 5 6 7 B 9101112131415 mgzaEm mp Time gt Harmonic number a 1 harmonic b 2 harmonics c 28 Network Analysis Physical Successive Approxima rions con r 4 harmonics 8 harmonics I I 2 3 4 5 6 7 8 Harmonic number gt Network Analysis Physical 29 Analog communicaTion channel CI Diminishes differenT Fourier coefficienTs by differenT amounTs disTorTion CI Usually leTs frequencies from 0 Through a max cuToff frequency fc 0 Frequencies above This value are sTrongly aTTenTuaTed CI TransmiTs a range of frequencies usually measured from 0 up To The fC where half The TransmiTTed power geTs Through The range of frequencies TransmiTTed wiThouT sTrong aTTenuaTion is called The bandwidTh of The channel NeTwork Analysis Physical 210 Maximum DaTa RaTe of Channel CI In 1948 Henry NyquisT proved ThaT if a signal has been run Through a lowpass filTer channel of bandwidTh H The filTered signal can be exachy recovered by by capTuring only 2H samples per second CI If The original signal conTains V discreTe levels Then The maximum daTa raTe is 2Hlog2V biTsec O A noiseless 3kHz channel cannoT TransmiT binary signals aT a raTe fasTer Than 6000 bps NeTwork Analysis Physical 211 Channel Noise CI Every pracTical Transmission channel has some background noise CI We measure noise relaTive To The power of The signal using a signalTonoise raTio S N 0 InsTead of using The power raTio direchy engineers use 10logloSN uniTs called decibels CI In 1948 Claude Shannon dealT wiTh The effecT of such noise by showing ThaT The max daTa raTe of a noise channel wiTh bandwidTh H hz and given SN raTio is Hlog21SN biTssec 0 NoTice ThaT SN is noT in decibels in The equa l39ion NeTworkAnalysis Physical 212 Example A channel in the telephone system has a bandwidth of about 3000 Hz and a signaltonoise ratio of 30 dB What is the max transmission rate in bitssec SN 30 dB implies that lOlog10SN 30 or log10SN 3 the ratio of the signal power to noise power thus SN power 1000 Because log21 1000 99672 the maximum transmission rate is 300099672 z 30000 bps Network Analysis Physical 213 Twis red Pair NoTe The Twisting cuTs down on a Ca l39egor39y 3 unwanTed r39adiaTion anTenna effecT Pairs usually bundled and Ca regor39y 5 would inTer39fer39e wiTh each oTher39 oTher39wise Network Analysis Physical 214 Coaxial Cable A coaxial cable Copper Insulating Braided Protective zsazzctor LSLng WWVWVWquot www a Two Types 50 ohm used Tr39adiTionally for digiTal communicaTion LANs eTc and 75 used by CATV indusTr39y Coax cables have a bandwidTh close To 1 GHz Network Analysis Physical 215 Fiber Op rics I Air AlrSIllca Total Internal boundary B1 32 33 reflection V H g f lA Silica Light source a b a Three examples of a ligh r ray from inside a silica fiber impinging on The airsilica boundary a r differen r angles b Ligh r Trapped by ro ral i n rernal reflec rion C Theore rical limi r Today gt 50000 Gbps bu r limi red ro 106bps by elec rroop rical conversion Ne rwork Analysis Physical 216 Wavelength and Frequency Electrons propagate in electronic quotwavesquot that were predicted by James Clerk Maxwell in 1865 and and rst observed by Heinrich Hertz in 1887 The number of oscillations per second of a wave is called its frequency f and is measured in Hertz Hz The distance between two consecutive maxima or minima is called the wavelengtth The relationship between frequency and wavelength is given by l f c where 6 represents the speed of light 3 gtlt108 meterssec Tannenbaum gives a nice rule of thumb When l is in meters and f is in MHz then xlf z 300 Thus 100 MHZ waves are about 3 meters long and 1000 MHz waves are 03 meters long Network Analysis Physical 217 Signaling Encoding CI Assume firs r Two signal levels vol rages frequencies phase shif rs CI Suppose represen r 1 as High signal and O as Low signal Bits 001o1111o1oooo1o NRzmm a E T Problems 1 Baseline wander deTecT based on delTa from avg 2 Clock recovery need frequenT signal TransiTions Ne rwork Analysis Physical 218 Encod i nq S rm reqies Clock P e T S e In C n G M Differem ial Manchesfer39 Network Analysis Physical 219 Baud ra re vs Bi r ra re CI Baud r39a re is The rare a r which signaling levels change vol rages fr39eqs e rc CI Bi r r39a re is found using BitRate BaudRate gtlt BitsEncoded per SignalLevel CI Manches rer39 requires 2 signaling levels per39 bi r which implies Bi rRa re 05 BaudRa re 0 Manchester efficiency is said To be 50 Network Analysis Physical 220 4B5B Encoding Scheme El Use 5 bi rs ro represen r 4 bi r codes and 5Th bi r is chosen To break up s rrings of 039s El Encoding given in Table 24 O 0000 9 11110 O 0001 9 01001 O O 1111 9 11101 El Only 1 leading zero permi r red amp only 2 Trailing zeroes permi r red implies max of 3 consecu rive zeroes may occur El NRZI is used To solve The consecu rive 139s problem CI Overall efficiency is lt 80 El 5Th bi r allows some con rrol codes line idle e rc Ne rwork Analysis Physical 221 Wireless Transmission The Elec rromagne ric Spec rrum Radio Transmission Microwave Transmission Infrared and Mi ime rer Waves Ligh rwave Transmission Ne rwork Analysis Physical 222 The Elec rromogne ric Spec rrum The elec rr39omogne ric spec rr39um and i rs uses for39 communication fHz10 1o2 104 106 1o8 1010 1012 1014 1o16 1018 1020 1022 1024 Radio Microwave Infrared UV Xray Gamma ray VlSlble light l I fHz1ojl 105 106 107 1o8 109 1010 1011 1012 1o13 1014 10151Q16 39 Twisted pair satelllte ber l 005 X Terrestrial Opt39cs AM FM 4 lllblUW 116 Maritime radio radio lt gt lt gt TV I 1 Band LF MF HF VHF UHF SHF EHF THF Network Analysis Physical 223 Radio Transmission a Sphere NK 0 0 quotF quot x G round wave I x in MT 1 Earth39s surface K Earth39s surface a b a In The VLF LF and MF bands radio waves follow The cur39vaTur39e of The ear39Th b In The HF band They bounce off The ionosphere NeTwor39k Analysis Physical 224 Communica rion Sa reIIi res Geos ra rionar39y SaTeIIi res MediumEar rh Or39bi r Sa reIIi res LowEar rh Or39bi r Sa relli res Sa reIIi res ver39sus Fiber39 Network Analysis Physical 225 Communication Satellites Altitude km Type Latency ms is 35000 l GEO 270 30000 25000 20000 Upper Van Allen belt 15000 10000 tm MEO 35 85 5000 Lower Van Allen belt 0 63 1 7 mum LEO Sats needed 3 50 Communication satellites and some of their properties including altitude above the earth roundtrip delay time and number of satellites needed for global coverage Network Analysis Physical 226 Communication Satellites 2 The principal satellite bands Band Downlink Uplink Bandwidth Problems L 15 GHz 16 GHz 15 MHz Low bandwidth crowded S 19 GHz 22 GHz 70 MHz Low bandwidth crowded C 40 GHz 60 GHz 500 MHz Terrestrial interference Ku 11 GHz 14 GHz 500 MHZ Rain Ka 20 GHz 30 GHz 3500 MHz Rain equipment cost Network Analysis Physical 227 Public Swi rched Telephone Sys rem S rr39uc rur39e of The Telephone Sys rem The Poli rics of Telephones The Local Loop Modems ADSL and Wireless Tr39unks and Mul riplexing Swi rching Network Analysis Physical 228 S rruc rure of The Telephone Sys rem 539 71 b v r A A vsquot V a use 44 In 395 39 394 lt4 I V V a b C a Fullyinferconnec red ne rwork b Cen rralized swi rch c Twolevel hierarchy Ne rwork Analysis Physical 229 Structure of the Telephone System 2 A typical cir39cui r route for39 a mediumdistance call Intermediate Telephone End Toll switching Toll End Telephone H office office offices office office H Very high Local Toll Toll Local bandWIdth loop connecting con nectlng loop Intettoll trunk trunk trunks Network Analysis Physical 230 Major Componen rs of The Telephone Sys rem Local loops Analog fwis red pair39s going ro houses and businesses Tr39unks Digi ral fiber39 op rics connec ring The swi rching offices Swi rching offices Wher39e calls are moved from one rr39unk To ano rher39 Network Analysis Physical 231 The Local Loop Modems ADSL and Wireless The use of bo rh analog and digi ral Transmissions for a compu rer ro compu rer call Conversion is done by The modems and codecs 4 ISP2 Local loop Mediumbandwidth analog trunk twisted pair digital fiber Codec Digital line In Up to 10000 local loops Modem bank End office Highbandwidth trunk digital fiber Nefwork Analysis Physical 232 O 1 0 1 1 0 O 1 O 0 1 O 0 m A mllm ltcgt VVlVVVlWlVlllV a A binary signal b Ampli rude modula rion c Frequency modula rion d Phase modula rion Network Analysis Physical 233 Modems 2 a QPSK b QAM16 c QAM64 90 270 C Network Analysis Physical 234 Time Division Multiplexing ll 193bit frame 125 nsec Channel Channel Channel Channel Channel 4 24 a J Bit 1 is 7 Data Bit 8 is for a framing bits per signaling code channel per sample Network Analysis Physical 235 Wavelength Division Multiplexing Wavelength division multiplexing Fiber 1 Fiber 2 Fiber 3 Fiber 4 Spectrum spectrum spectrum spectrum spectrum on the shared fiber E Equot 5 E 5 ll ll 9 7L 7 9L 9 M Filter Fiber1 I fCZMZ 7V2 Fiber 2 a M7r2k39u4 PM 7V Combiner Splitter Fibers 3 ESE A4 Long haul shared fiber Fiber 4 I M Network Analysis Physical Time Division Multiplexing 5 SONET SDH Data rate Mbps Electrical Optical Optical Gross SPE User STS 1 OC 1 5184 50112 49536 STS3 OC3 STM1 15552 150336 148608 STS 9 OC9 STM3 46656 451008 445824 STS12 OC12 STM4 62208 601344 594432 STS 1 8 00 1 8 STM6 93312 902016 891648 STS 24 OC24 STM8 124416 1202688 1188864 STS 36 OC36 STM12 186624 1804032 1783296 STS48 OC48 STM16 248832 2405376 2377728 STS 192 OC192 STM64 995328 9621504 9510912 Network Analysis Physical 237 Circui r Swi rching iii Oi O m Com p ute r E Physical copper connection set up when call is made ks H WE Packets queued for subsequent transmission K o o o o J F O o a r o o O Gigtlt4C 0 1 L G s s s 7 Os if 740 O o O r a HHj EHZI Eli CH3 m b a Cir39cui r swi rching PaCkeT SWi1pching39Ne rwor39k Analysis Physical Computer Packet Switching Item Circuitswitched Packetswitched Call setup Required Not needed Dedicated physical path Yes No Each packet follows the same route Yes No Packets arrive in order Yes No Is a switch crash fatal Yes No Bandwidth available Fixed Dynamic When can congestion occur At setup time On every packet Potentially wasted bandwidth Yes No Storeandforward transmission No Yes Transparency Yes No Charging Per minute Per packet A comparison of circuit switched and packet switched networks Network Analysis Physical 239 The Mobile Telephone Sys rem Fir39s r Gener39a rion Mobile Phones Analog Voice Second Genera rion Mobile Phones Digi ral Voice Third Genera rion Mobile Phones Digi ral Voice and Da ra Network Analysis Physical 240 Third Genera rion Mobile Phones Digi ral Voice and Da ra Basic services an IMTZOOO ne rwork should provide High qualify voice Transmission Messaging replace e mail fax SMS cha r e rc Mul rimedia music videos films TV e rc In rerne r access web surfing wmul rimedia Ne rwork Analysis Physical 241 Cable Television Communi ry An renna Television In rer39ne r over39 Cable Spec rr39um Alloca rion Cable Modems ADSL ver39sus Cable Network Analysis Physical 242 Communi ry An renno Television An early cable Television sys rem Antenna for picking up distant signals EE SE SE E E EE 3 EE ea EE EE EE BE I I I I D rop cable Tap Coaxial cable Network Analysis Physical 243 Inferne r over39 Cable Cable Television ber SE SE RE I EB T Ea EE I EE ii I EE CoaXIal cable trunk Fibernode EETEE EETEE EETEE WTEE Tap Fiber W W E EE as as a m l l u a Network Analysis Physical 244


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

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

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

Parker Thompson 500 Startups

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

Become an Elite Notetaker and start selling your notes online!

Refund Policy


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


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

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

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

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