Comp Networks EECS 489
Popular in Course
Popular in Engineering Computer Science
This 86 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 489 at University of Michigan taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/231547/eecs-489-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Comp Networks
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Internet Protocol Stack i ll m r l l u rim n urn opphcq on transport endhostendhost data transfer TCP UDP fransporf a are Um l l ll ll f r w kw w tar v y a 26m x a A ll will Congestion Control What gives rise to congestion When offered load is greater than system capacity too much data for the network as opposed to receiver to handle 20 19 18 17 16 15 l bottleneck 14 13 12 11 l router 1 39 39 router a sender l rece39v d III Se er R3 R4 ack 3 ack 4 ack 5 ack 6 ac l ack 2 ac 7 ac 8 Causes and Implications of Congestion caused by packets arriving faster than a router can forward them routers queue packets that they cannot serve immediately if queue overflows packets are dropped queued packets experience delay Why is congestion bad Consequences of Congestion lf queueing delay gt RTO sender retransmits packets adding to congestion Dropped packets also lead to more retransmissions lf unchecked could result in congestion collapse When packet dropped any upstream transmission capacity used for that packet was wasted What prevention Constraints decentralized control unlike routing no local reaction at routers beyond buffering and dropping long feedback time dynamic network condition connections come and go Congestion Control How can senders preventavoid congestion 20 19 1817 16 15 10 quot bottleneck I router W I router I sender p R1 l 39 I I I R2 gt recemi I I I I I I I I I I I I I I I I I I sender 1 l mfg 39 l l H H r013 lt receiver ack 3 ack 4 ack 5 ack 6 ack l ack 2 ack 7 ack 8 Congestion Control How do senders know what the system capacity is Load vs throughput congestion avoidance operate system at knee congestion control operate system near cliff How do senders discover system capacity and control congestion Load Resp onse time Jain et al Discovering System Capacity Throu How do senders know where the knee is and W how do they know when the system has gone off the cliff Resp What TCP and other congestion control 33 schemes do probe for point right before cliff pipe size l Load Jain et al slow down transmission on detecting cliff congestion Packet fast probing initially dmpped TCP u n gt up to a threshold slow start Tahoe slower probing after threshold is reached linear increase Threshold 0 nd m Threshold TCP Series 1 Tahoe congestion window w J2 I Why not send a large amount 0 Of Clata and then SlOW Clown 0 139 392 5 zl 539 639 l a 9393 13901391 13921393 1394 1395 Transrrission round TCP Slowstart When connection begins increase rate exponentially until rst loss event double cwnol every RTT every ACK received gt initial rate is slow but ramps up exponentially fast 0R r 7 1R b 2n 3 l 3 i L a a l Jacobson and Karels 4 ALLA one Segment two Seginents 739 four segments 77quot time SelfClocking TCP ACK is used for flow control and retransmission TCP also uses ACK for congestion control TCP follows a socalled Law of Packet Conservation Do not inject a new packet into the network until a resident IIII 3 39 I departs ACK recered In IQ SInce packet transmISSIon w is timed by receipt of ACK 2n I TCP is said to be selfclocking 3n 5 139 J 39 Jacobson and Karels TCP Congestion Control Sender maintains a congestion window cwnd Sender does congestion control by expanding and shrinking cwnoI Sender s send window wnd is wnd MINrwnd floorcwnd where rwnd receiver s advertised window initially set cwnd to I increase cwnd if there s no congestion Questions on congestion decrease cwnd 3 How to detect congestion 4 By how much must cwnol be decreased I How to determine that there s no congestion 2 By how much do we increase cwnd TCP Congestion Control packet Variables II dr PPed TCP cwnd congestion window 32 Tahoe init l gli rgsggg ssthresh threshold for 6 quot matad slowing down cwnd increase TCPSeriesiTahoe init 64KB 0 I I I I I I I I I I I I I I I 123456789101112131415 Transrr ission round Recall that TCP uses cumulative ACK ACKs the lastbyte received in order tells sender the nextexpected seq subsequent outof order packets generate the same cumulative ACK Increasing cwnol Probing the pipesize system capacity in two phases I slowstart exponential increase while cwnd lt ssthresh cwnd cwnd for every ACKeol cwnol OR send out 2 packets for every new ACK received 2 congestion avoidance linear increase while cwnd gt ssthresh cwnd 1 for every cwnd full of ACKS OR cwnd lfloor CImoi for every ACK Om RumJ T39lp T rquot gt OH J O39Iu l aau TIIIII I IR IL 2R 3 I I an 4 I 5 I I EEEEl Jacobson amp Karels TCP Congestion Recovery Once congestion is detected by how much do we decrease cwnd how do we recover from congestion which packets do we retransmit how do we increase cwnd again First reset ssthresh cwndZ TCP Tahoe retransmit using GoBack N reset cwnd restart slowstart 7 Threshold congestion window cwnd I l I l I I I I I I 5 6 7 8 9 l0lll213l415 Transrrission round TCP Reno and Fast Recovery cwnd reopening and retransmission of lost packets regulated by returning ACKs duplicate ACK doesn t grow cwnd so TCP must wait at least I RTT for fast retransmitted packet to cause a nonduplicated ACK to be returned if RTT is large Tahoe regrows cwnd very slowly TCP Reno does fast recovery current value of cwnd is the estimated system capacity 0 after congestion is detected want to continue transmitting at half the estimated capacity how each returning ACK signals that an outstanding packet has left the network don t send any new packet until half of the expected number of ACKs have returned Fast Recovery N Aw U1 0 N on congestion retransmit lost segment set sstresh cwndZ remember highest seq sent sndhigh and remember current cwnd let s call it pipe decrease cwnd by half increment cwnd for every returning dupACK incl the 3 used for fast retransmit send new packets above sndhigh only when 39 cwnd gt pipe exit fastrecovery when a nondup ACK is received set cwnd ssthresh l and resum linear increase segment number 52 cwnd byles 50000 30000 mom 5 s cwnd number of bytes unACKed 56 time secs 5 a In secs Summary TCP Congestion Control when cwnd is below ssthresh sender in slowstart phase window grows exponentially when cwnd is above ssthresh sender is in congestion avoidance phase window grows linearly when a 3 dupACK occurs ssthresh set to cwndZ and cwnd set to new ssthresh if more dupACKs return do fast recovery else when RTO occurs ssthresh set to cwndZ and cwnd is set to MSS TCP Congestion Control Examples TCP keeps track of outstanding bytes by two variables 1 sndiuna lowest unACKed seq ie sndiuna records the seq associated with the last ACK 2 sndinext seq to be sent next Amount of outstanding bytes pipe 5nd7next e 5nd7una Scenario 39 1 bytepkt 39 receiverR takes I transmit time to return an ACK 39 sender S sends out the next packet immediately upon receiving an ACK 39 rwnd oo 39 cwnd 21 in linear increase mode 39 pipe 21 TCP Tahoe with Fast Retransmit n 3 Or IE9 z O 9 I ll 3 E E semlll M 39 IE lt ll III I l I w k lama M amiss k lmmma mmm H W Gr llm N K Ema13quot 5 3 all l llll 39 llll El III E its WEEll l k museum o TCP Original 2w s w 393 as 2x 9 9 K lemmas No me tame we 9 39 mm 2 G 9 k lmmmmimmi lmi N K mmmmmmmm mailman n m m to go on n 5 or IE9 2W0 3 IE lt lama M mes k lmmmmmiemm Ma 39 mmmmmmmmm TCP Reno with Fast Recovery 1 9 9 39 9 ml l l El k mammal N k EEE ll Na K EEEE ll mnemmaemaeaEMl E39 la l o lllm l m 1 l K IllI Internet Protocol Stack application supporting network applications HTTP SMTP FTP etc applica on endhostendhost data transfer TCP UDF 39I39ranspor39r A Ir routing of datagrams from source to destination alwork IP routing protocols m data transfer between neighboring link network elements v Ethernet VWFi Phyglcal bits on the wire Principles of Network Applications Our goals conceptual implementation aspects of network application protocols transportlayer service models clientserver paradigm peertopeer paradigm examine some popular applicationlevel protocols HTTP SMTPPOP3IMAP ApplicationLayer Protocols Messages exchanged between applications syntax and semantics of the messages between end hosts tailored to the speci c application eg Web email Messages transferred over transport connection eg TCP Popular applicationlayer protocols HTTP SMTP FTP SSH GEI39 indexhtml HTTP11 Client Server HTTP11 200 OK Some Network Apps and Their Protocols Email SMTP Internet telephone Web HTTP Skype Instant messaging IRC 39 Real me VldeO conference RTP Massively parallel comput39ng Remote login Telnet P2P le sharing Napster Gnutella KaZaa Multiuser network games Streaming stored video clips Adobe s RTMP Gnutella Hierarchical P2P FastTrack used by KaZaA Groskster iMesh Morpheus no centralized Index server hierarchical architecture peers divided into supernodes and ordinary nodes network discovery using ping and pong messages le discovery using query and queryHit messages each supernode keeps an index of all its children s les both ping and query messages are requests are sent to supernodes forwarded using the flooding algorithm forward on all links except incoming one supernodes query each other for les not in their local indices ordinary nodes are promoted to supernodes if they have enough resources and have stayed on network long enough previously seen messages are not further forwarded A39 l U queryHit parallel download of les new version of gnutella uses KaZaA like supernodes eDonkeyeMule also builds a hierarchical network but the supernodes are dedicated servers not just more equal peers Tracker peer Freenet Anonymous P2P BitTorrent no index server D ata request 0 o o requester doesn t connect Requester 339 Datareply Content d39Str39bUt39 n directly to content provider lt 39 12 39Requestfailed 39 content is divided into N instead content passed in a llll ooataholder Pieces Of l6KB eaCh and bucketbrigade fashion from l V sent to N peers provider to requester wig Se the next time content is Figure ITypical request sequenceThe request moves through the Content download network from node to node backing out of a deadend step 3 and requested It 395 Pl39OVlded from G OOP step 7 before Iocatmg the deslred le to download a le a peer must rst register with a Tracker the neareSt caChe Tracker returns a random list of peers who have the le requester cannot differentiate provider from a cache holder or a forwarding peer allow for anonymity peer opens about 5 TCP connections to the provided peers a peer will only upload to peers from whom it can also download titfortat Challenges for P2P Networks I NAT and rewall cannot peer with a host you can t address Solutions Gnutella querier sends PUSH message to responder over the p2p network responder opens a TCP connection to querier and send over the le no luck if both are behind rewalls KaZaA eDonkey Skype supernodes act as proxy if both peers are behind rewalls Standards to circumvent NAT and rewall UPnP STUN 2 Downloadupload bandwidth asymmetry gt needs bandwidth subsidy by content provider or CDN or suffer long download time Application Architectures endhost p2p multicast Modes of Delivery Unicast broadcast multicast 4 Assuming a video conference involving S D2 and D3 unicasting two copies of packets from S are sent over the SR link broadcasting one copy of packet sent from Sto all destinations but packet sent to D1 and D4 unnecessarily multicasting one copy of packets from S is sent over the SR link R then sends one copy each to D2 and D3 Multicast Delivery Uses of multicasting video conferencing distance learning distributed computation p2p delivery multiplayer gaming etc Multicast design goals can support millions of receivers per multicast group receivers can join and leave any group at any time senders don t have to know all receivers senders don t have to be members of a group to send there could be more than one senders per group Multicast Group Management Issues in multicast group management I how to advertisediscover a multicast group 2 how to join a multicast group 3 delivering multicast packets to the group IPv4 multicast use multicast ClassD addresses as anonymous rendezvous point create a wellknown multicast group address to advertisediscover multicast groups multicast data is sent using UDP sender sendto the multicast address receiver recvfrom the multicast address not uniformly deployed throughout the Internet Endhost Multicast Issues in multicast group management I how to advertisediscover a multicast group 2 how to join a multicast group 3 delivering multicast packets to the group Endhost p2p multicast use a wellknown centralized rendezvous server each peer must register with rendezvous server rendezvous server returns a random list of peers each peer can support only a limited number of peers avoid sending duplicate messages and looping if single source construct a shortestpath tree rooted at source or use floodandprune algorithm prefer peers in same subnet Flood and Prune How to ensure that only one copy of packet from S is forwarded by P3 to P4 keep track of sequence number only forward packet that comes from shortest path from to source a How to ensure that only one copy of packet from S reaches P3 only forward if selfis on neighbor39s shortest path 6 from to source prune P3 tellingP2 not to forward pkts from S must be done per source ifthere are multiple sources each source forming its own multicast youp an logically its own multicast tree must periodically flood in case of membership change Application Architectures Clientserver FTP SMTP HTTP cookies web caching CDN Multiplayer games Elements of a Wireless Network Elements of a Wireless Network wireless hosts laptop PDA IP phone run applications may be stationary nonmobile base station typically connected to wired relay responsible for sending packets between wired network and wireless hosts in its area eg cell towers 802l I access points oblle wireless does not always mean mobility Elements of a Wireless Network Elements of a Wireless Network gm 39 infrastructure mode 8 Wirelessllnk typically used to connect mobiles to base station also used as backbone link multiple access protocol coordinates link access various data rates base station connects mobiles into wired network hando quot mobile changes base station providing connection into wi red networ s 8 transmission distance 3 3 B a down or forwardlink 1 base station to wireless host up or reverselink T wireless host to base station Elements of a Wireless Network Ad hoc mode no base stations nodes can only transmit to other nodes within link coverage nodes organize themselves into a network route among themselves Cellular Standards IG and ZG Components of Cellular Network Architecture a Msc 7 cell connects cells to wide area net I manages call setup more later COTem geograph39cal handles mobility more later region base station BS x analogous to 802 AP mobile users attach to network through BS airinterface physical and link layer protocol between mobile and BS a wired network Standard Region Frequency Band Modul Multiple Origin MHz FDD ation Access I97 proposed I G AMPS US I982 approved 800 I I983 launched ana 0g NTT MCS apan I979 400800 supports handoff NMT N rdic 98 450900 FM FDMA 39 PM ETACS UKIEurope 9857 900 39 CNetz Gerlnbny 98 65200 400 RTMS ItaIy I backward 450 RadicommZOOO Fra nce 4 i l compatible 7 m 3 Ebrople I990 900 I GSM Chinsl I993 800 gtti lband GMSK d I IUSHQIZhile I994 I9007I quad 850 IS54 y l USanalog ctl 99 increased ISl 36 39 all digital I994 800 I900 TDMA capacity due to DAMPS digital USTDMA DQPSK compression U DC f PPf r s JaPDC I japan I993 800 500 CircuIt switched data S95A I QPSK and SM Cdmaone US I993 800 I900 OQPSK CDMA piggyback l60char messages to voice traf c ISM Industrial Scienti c and Medical ITU International Telecommunications Union Alphabet Soup JDC Japanese DigitaI Cellular Ix one time R39l39l39 LTE Long Term Evolution aoPP so Partnership Project AMPS Advanced Mobile Phone System 39 ARIB Association of Radio Industries and Businesses JP BPSK Binary Phase Shift Keying 39 CAGR Compound Annual Growth Rate CA I39I39 China Academy Telecommunications Technology CDMA Code Division Multiple Access CSMA Carrier Sense Multiple Access DECT Digital Enhanced European Cordless Telephone DQPSK Differential Quadrature Phase Shift Keying DSSS Direct Sequence Spread Spectrum EDGE Enhanced Datarate for Global GSM Evolution FI39SI European Telecommunications Standard Institute EVDO Evolution Data Optimized 39 EVDV Evolution Data and Voice FDD Frequency Division DupIex MCS Mobile Communication System M55 Mobile Satellite Services NMT Nordic MobiIe Telephony NTT Nippon Telephone and Telegraph OFDM Orthogonal Frequency Division Multiplexing OFDMA Orthogonal Frequency Division Multiple Access PCS Personal Communication System PDC Personal Digital CeIIuIar PHS PersonaI Handyphone System QAM Quadrature Amplitude Modulation QPSK Quadrature Phase Shift Keying RF Radio Frequency RTMS Radio Telephone MobiIe System R39l39l39 Radio Transmission Technology TACS Total Access Cellular System SMS Short Message Service TDD Time Division DupIex TDMA Time Division Multiple Access TDSCDMA Time DivisionSynchronous CDMA TIA Telecommunications Industry Association US FDMA Frequency Division Multiple Access FHSS Frequency Hopped Spread Spectrum FDMA Freedom of Mobile Multimedia Access FPLMTS Future Public Land Mobile Telephone System FSK Frequency Shift Keying GMSK Gaussian Minimum Shift Keying GPRS Global Packet Radio Service GSM Global System MobiIe HSCSD High Speed Circuit Switched Data HSDUPA High Speed Downlink Uplink Packet Access IEEE Institute of Electrical and Electronics Engineers IMS IP Multimedia Subsystem IMT2000 International Mobile Telecommunication 2000 ISri EIectronic Industry Association US Interim Standard n UMTS Universal Mobile Telecommunications System USDC US Digital Cellular UTRAN UniversaI UMTS Terrestrial Radio Access Network UWCC Universal Wireless Communications Consortium WARC World Administrative Radio Conference WCDMA Mdeband CDMA vwn vweiess IideIity VWMAX Woridwide Interoperability for Microwave Access WLAN vweiess LAN WRC2000 ITU U n J Cellular Standards 25G and 2756 Motivation better support for data rate S95A o 96 I44 Kbps PDC 39 GSM protocol 39 lSl36 physical 96 Kbps limited to Japan imode I999 V o 96 Kbps gt33m subs by 602 39339 l 36 GPRS 200i 0 F I user 2030 Kbps avg 39 l3 secs rtt 398i44 Kbps GMSK modulation h d I99 gt280m subs by 05 aunc e in Finland V 2003 a cdmaZOOOIXRTT I999 I44 Kbps 5070 Kbps avg QPSK modulation 0 Release A 384 Kbps launched I02000 in S Korea 0 I50 m subs I204 EDGEEGPRS 2003 o 384 Kbps I user I00I30 Kbps avg 8PSK modulation gt36m subs by 2005 7 dedicated packetswitched network billed by byte not by air time Separate PSN for Data Base Station System 355 Gateway MSC Public telephone network Key Base transceiver station BTS Base station controller BSC Mobile switching center Q Msc Key 9 Public telephone network Public Internet Serving GPRS Gateway GPRS support node support node SGSN GGSN Cellular Standards 3G UN s ITU s plan IMT 2000 aka FPLMTS I990 Motivations 39 single standard to support worldwide roaming l0 leading proposals in 98 5 by Nov 99 now down to 4 39 data peakrate requirements outdoor vehicular 44 Kbps outdoor pedestrian 384 Kbps indoor2 Mbps frequencies allocated UK auctioned off 5 licenses for USD 355b in 42000 DE auctioned off 4 licenses for USD 46b 3 later same yr America lMT2000 Europe Brazil lMT2000UMTS Frequency Spectrum after WRCZOOO 1700 1750 1800 2100 2150 2200 2250 IMT lMTZOOO 2000 lMTZOOO GSM 1800 uwns 3 Under study Under study 3G IS95 gt cdma2000 TIA US UWC l 36 cdma2000 leV Release B 200 l o3GPP2 I999 no EU rep EVDO Rev 0 CDMA with TDM QPSK8PSKI 6QAM modulation peak rate 2 Mbps reverse I50 Kbps avg rate 300700 Kbps reverse 7090 Kbps launched 2002 in S Korea gtI2 m subs by 2005 IS I 36 gt uwcc US PDC GSM TDMA mod gt WCDMA oAmBam UTRA99 oETSI EU 4 TDSCDMA CATT China gt8 m GSM subs per month in late 200 can connect directly to IP network WCDMAUMTS I999 3GPP I998 2 Mbps 220 320 Kbps avg QPSKBPSK 275 ms rtt GSM network and protocol requires new equipments for UTRAN air radio interface Release 99 300 gt26b subs in 2008 NTT DoCoMo 39 launched FOMA based on Release 99 IO200 I 2003 64 Kbps circuit switched 38464 Kbps packetswitched TDSCDMA 2000 o TDSCDMA Forum merged into 3GPP Release 4 30l coexist with GSM RF equipment 384 Kbps data Networking in Games lngame networking networking topology clientserver vs peertopeer computing model distributed object vs message passing which protocol to use tcp udp reliable udp bandwidth limitation latency limitation Machine 1 Machine 2 consistency D1str1buted D1str1buted Cheat prOOf39ng Systems Systems socket programming Networking Networking Network LAN or Internet in game more in EECS 591491 WinSocks in librarykemel EECS 489 Sugih Jamin lamineecsumich edu Consistency Problem statement time How do you differentiate the two cases at both player1 and player2 Sugih Jamin Gamineecsumich edu Synchronization Synchronization order moves by their times of occurence Assume globally synchronized clocks Outof synch worlds are inconsistent Small inconsistencies not corrected can lead to large compounded errors later on deer not speared means one less villager means slower barrack build etc Sugih Jamin lamineecsumich edu When to Render 3 Move How long do you have to wait for the other players moves before rendering them time Sugih Jamin Gamineecsumich edu Lockstep Protocol 0 each player receives all other players moves before rendering next frame time D synchronize moves and Problems render scene Player1 Player2 0 long Internet latency quot 0 variable latencies 0 speed determined by the slowest player Sugih Jamin lamineecsumich edu Bucket Synchronization 0 buffer both local and remote moves 0 play them inthe future 0 each bucket is a turn say for about 200 ms 0 bucket size can be adapted to measured rtt Problems 0 game speed bucket size deter mined by slowest player 0 what if a move is lost or late Player1 time Q Player2 Q synch moves and render scene igt gtk W a player can have multiple moves perturn l K Sugih Jamin lamineecsumich edu Pessimistic Consistency Every player must see the EXACT same world AoEAoKAoM each player simulates its own copy of the world all the worlds must be in sync uses bucket synchronization each player sends moves to all other players dropped packets retransmitted a designated host collect measured rtts from all players and set future bucket sizes Problems variable latencies speed determined by the slowest player Sugih Jamin Gamineecsumich edu Dead Reckoning o aka clientside prediction 0 players can help by sending this 0 extrapolate next move based info along on prior moves 0 obviously only works if ve o compute the velocity and ac locity and acceleration haven t celeration of objects to dead changed reckon move lost or late dead reckoned ltl Sugih Jamin lamineecsumich edu Rollback In case of inconsistency 0 server always have authoritative view 0 when clients correct inconsistent views players may experience warping 0 can players decisions be dead reckoned See httpwwwsiminfethzchprojectsalpsim Sugih Jamin lamineecsumich edu Optimistic Consistency with Rollback Observation dead reckoning doesn t have to be limited to lost packets HalfLife each client plays back its own moves immediately and send the moves to server each client also dead reckons the other players moves server computes world and sends its authoritative version to all clients clients reconcile dead reckoned world with server s version can result in some jerkiness and perception of shooting around corner only need to synchronize important events but must be careful that dead reckoning error doesn t get compounded over time Sugih Jamin lamineecsumich edu Consistency Correctness For consistency ALL user input MUST pass through the synchro nization module Be careful with random number generators Isolate the one used for gamestate updating from other uses ambient noise etc Design for mutipayer from the start Singleplayer becomes a special case of singleclient mutipayer game Initialization gt Overall Game gt Game Session Control 4 control lt Render scene to buffer Copy buffer to display Local Player Input Send Local Input 1 Receive Remote Playe s InPUt Main Logic consistency game AI physics collision I I I ITIme sync 39 Sugih Jamin lamineecsumich edu Consistency Smoothness For smoother playback decouple bucket size from frame rate even AoE does this Immediately render local moves Modify game design to allow for latency and loss eg 0 make players wait for elevator teleportation takes time require multiple hits per kill let bulletmissile have flying time 0 build in inertia don t allow sudden change in facing Sugih Jamin lamineecsumich edu Reducing Consistency Check Do areaof interest management aka relevance filtering 0 aura how far you can be sensed cloaked ships have 0 aura o nimbus how far you can sense use quantumsensor to detect cloaked ships Aura and nimbus are defined for a given set of technology eg cloaking device quantum sensor etc Perform consistency check only when B is within A s nimbus and A is within B s aura Sugih Jamin lamineecsumich edu Cheating AoE doesn t need cheatproofing because each player simulates each move in lock step All moves are simulated not just collisions HalfLife synchronizes only collisions higher probability for cheating Cheats more at megagamescom superhuman cheat autoaim autoposition gamestate editing boost player s profile rule bending seewalk through walls sixthsense cheat lookahead cheat claim to be behind slow link suppresscorrect cheat exploit deadreckoning claim moves were lost then reconstruct advantageous moves based on others moves Sugih Jamin lamineecsumich edu Lookahead Cheat Player C Player H Player C Player H 0 39 0 39 t0 0 50 39 50 39 3950 me ms 100 100 100 150 39 150 39 39150 200 39 200 39 39200 250 39 250 39 39250 a C is an honest player b C is a cheater 150ms from H 50ms from H claiming to be 150ms from H Sugih Jamin Gamineecsumich edu Suppresscorrect Cheat At time 150 C sends out a move consistent with fake moves at time 0 50 100 that were actually computed upon receiving packets from Player H Player C Player H 390 39100 39150 39200 25039 39250 Sugih Jamin lamineecsumich edu Distributed Computing Model Message passing 0 player inputs either button pushes or higherlevel move ments are sent to other players or server 0 all players update their own game state 0 or server updates the global game state and send it out to all players Initialization gt Overall Ga Control Receive Remote Players Input Player inputs sentreceived using sockets me gt Game Session Control Render scene to buffer Copy buffer to display Local Player Input Send 1 Local Input Main Logic update states game AI physics collision I I I ITIme sync 39 Sugih Jamin lamineecsumich edu Distributed Computing Model Distributed objects 0 characters and environment maintained as objects 0 player inputs are applied to ob jects at server 0 changes to objects propagated to all players at end of game loop 0 object update usually imple mented as one or more library calls Initialization gt Overall Game gt Game Session Control 4 Control Render scene to buffer Copy buffer to display Local Player Input 1 Main Logic update objects game AI physics lt gt collision Send amp Receive Object Updates I I I ITIme sync 5a l I Object update library implemented on sockets Sugih Jamin Gamineecsumich edu Socket Programming What is a socket How to use socket for clientserver computing Sugih Jamin Gamineecsumich edu Socket Programming socket a data structure containing connection information Connection identifying information 0 client lP Internet Protocol address 0 client port number 0 source IP address 0 source port number Clientserver connection 0 server creates a socket and listens for connections on a wellknown port number 0 client creates a socket and connects to the server address at the wellknown port number Sugih Jamin lamineecsumich edu buf strlenbuf O closetd Sugih Jamin Gamineecsumich edu clientc int mainint argc char argv struct sockaddrin server struct hostent sp int sd int n char bufBLEN Sd SOCketPFINET SOCKSTREAM IPPROTOTCP memsetchar ampserver 0 sizeofstruct sockaddrin serversinfamily AFINET serversinport htonsushort PORT Sp gethostbynameSERVER memcpyampserversinaddr sp gthaddr sp gthlength connectsd struct sockaddr ampserver sizeofstruct sockaddrin n recvsd buf sizeofbuf 0 while n gt O writel buf n n recvsd buf sizeofbuf O closesd exitO Sugih Jamin Gamineecsumich edu includes and defines To be prepended to both server c and client c include include include include include include include include include define define define define ltstdiohgt ltStdlibhgt ltstringhgt ltunistdhgt ltsystypeshgt ltsyssockethgt ltnetinetinhgt ltarpainethgt ltnetdbhgt SERVER quotlocalhostquot PORT 4897 BLEN 256 QLEN 200 Sugih Jamin Gamineecsumich edu Socket APIs Highlights WinSock APIs httpmsdnmicrosoftcomibrarydefaultaspur ibraryenuswinsockwinsockwinsockfunctionsasp socket creates a socket data structure Then we need to populate the structure with the connection identifying information 0 client IP Internet Protocol address 0 client port number 0 source IP address 0 source port number Sugih Jamin Gamineecsumich edu TCP Socket Addresses In the socket structure bind connect IP address Port match incoming pkts destination copy to outgoing pkts destination bind used by server only gives the server socket an IP address andor port connect 0 TCP initiates connection 0 udp remembers remote address Sugih Jamin Gamineecsumich edu TCP Socket Addresses TCP Server IP address Port INADDR ANY Wellquot known client s address ephem eral TCP Client IP address Port client s address ephem eral server s address well known Sugih Jamin Gamineecsumich edu NAT and Firewalls What are NAT Network Address Translation and firewalls Sugih Jamin lamineecsumich edu Socket APls Hightlights cont listen 0 specifies max of pending TCP connections 0 only useful for connection oriented services 0 TOP SYN denial of service attack accept o waits for client connection a returns a connected socket different from the listening socket Sugih Jamin Gamineecsumich edu Socket APls Hightlights cont send 0 returns how many bytes are actually sent 0 must loop to make sure that all is sent except for blocking lO see UNP Section 62 What is blocking and nonblocking lO Why do you want to use nonblocking lO Sugih Jamin lamineecsumich edu Different Types of HO Synchronous blocks puts process to sleep until lO is ready By default operations on sockets are blocking Waiting for HO 1 wait for device availability 2 wait for lO completion Sugih Jamin lamineecsumich edu Nonblocking lO Nonblocking IIO keeps on checking polling until device is available 0 set socket nonblocking int on l ioctlsocketsocket FIONBIO ampon 0 call select on nonblocking socket Signaldriven IIO process gets a signal when device is available 0 use WSAAsynCSeleCt for signals tied to a window 0 or WSAEventSeleCt for signals not tied to a window Asynchronous IIO process notified when lO completed 0 Not widely supported yet See UNP Section 62 for more info Sugih Jamin lamineecsumich edu Socket APIs Hightlights cont IGCV o returns how many bytes are received 0 0 if connection is closed 1 on error a if nonblocking 1 if no data with errno set to EWOULDBLOCK a must loop to make sure that all is received in TCP case 0 How do you know you have received everything sent fixed size part of protocol definition prior handshake Sugih Jamin Gamineecsumich edu Select selectmaxfd readset writeset acceptset timeout synchronous blocking lO multiplexing maxfd is the maximum file descriptor number 1 so if you have only one descriptor number 5 maxfd is 6 descriptor sets provided as bit mask Use FDZERO FDSET FDISSET and FDCLR to work with the descriptor sets the fourth parameter is usually called the exceptset Sugih Jamin lamineecsumich edu Select cont selectmaxfd readset writeset acceptset timeout o returns as soon as one of the specified socket is ready for O o returns of ready sockets 1 on error 0 if timed out and no device is ready what for Sugih Jamin Gamineecsumich edu rechW lselectVSPOmng Which of the following would you use Why loop select timeout recv till done or loop sleepseconds recv till done Sugih Jamin Gamineecs umichedu Socket APIs Hightlights cont closesocket o marks socket unusable 0 actual tear down depends on TCP ifbind bCh dltWSAGetLastErrorforWSEADDRINUSE Sugih Jamin Gamineecsumich edu Socket Options getsockopt and setsockopt UNP Ch 7 o SOREUSEADDR allows server to restart or multiple servers to bind to the same port with different IP addresses 0 SOLINGER whether close should return immediately or abort connection or wait for termination o SORCVBUF and SOSNDBUFI set buffers sizes 0 SOKEEPALIVE server pings client periodically Sugih Jamin Gamineecsumich edu UDP Socket Programming Server must always call bind but not listen nor accept Client doesn t need to call connect Use sendto instead of send However connect can still be used to tell the system to remember the remote address Then send instead of sendto can be used Call either recv or recvfrom to recv recvfrom also returns the address of the client UDP packets have boundary not a bytestream as in TCP so recv retrieves one message at a time ie no need to call recv in a loop Sugih Jamin lamineecsumich edu UDP Socket Addresses UDP Server bind UDP Client connect IP address 239489 IP address Port 9489 match incoming pkts destination To be filled in with sender s addr by kernel Port 239489 9489 To be filled in with host s IP addr and ephemeral port by kernel copied to outgoing pkts destination Sugih Jamin Gamineecsumich edu Byte Ordering Bigendian Most Significant Byte MSB in low address sentarrives first Sun Sparc HPPA Littleendian MSB in high address sentarrives later Intel x86 P82 PowerPC and Alpha can be set to either mode MMORG servers and backend servers may live on bigendian machines Sugih Jamin lamineecsumich edu Byte Ordering cont Actual Value 1 MSB LSB 00000000 00000001 Al 00000000 MSB A 00000001 LSB little endian sent without 00000000 htons and ntohs 00000001 Al 00000000 LSB big endian A 00000001 MSB Value 2 8 Sugih Jamin Gamineecsumich edu Byte Ordering cont To ensure interoperability ALWAYS translate short long int to from network byte order before after transmission by using these macros htons htonl ntohl host to network short host to network long ntohsk network to host long network to host short Sugih Jamin lamineecsumich edu M Routing Algorithm Classi cation Centralized or decentralized algorithm Global or distributed local information static or dynamic routing Global Info Static routing all routers have complete topology link cost g routes change SIOWIY over time info D namic routin link state algorithms y g e routes change more quickly e periodic update in response to link Local 39nfo39 cost changes outers know of only physicallyconnected neighbors link costs to neighbors iterative process of computation exchange of info with neighbors distance vector algorithms Dynamic Programming Used when a problem can be divided into subproblems that overlap Solves each subproblem once and store the solution in atable ifthe same subproblem is encountered again simply look up its solution in the table reconstruct the solution to the original problem from solutions to the subproblems the more overlap the better as this reduces the number ofsubproblems DP used primarily to solve optimization problem eg nd the shortest longest best way of doing something Requirement an optimal solution to the problem must be a composition of optimal solutions to all subproblems In other words there must not be an optimal solution that contains suboptimal solution to a subproblem Distance Vector Algorithm Origin ofthe name dynamic programming Bellman s shortest path algorithm I957 dynamic multistage timevarying process programming planning decision making by a tabular method Bellman39s shortest path algorithm e centralized distance vector algorithm e route table D encodes shortest path De ne Dxy cost ofleastcost path from x toy Then Dxy mincxv Dvy where v is a neighbor ofx and min is taken over all neighbors ofx De ne two other tables e L link table e H next hop table Bellman s Algorithm lnitial Values L 11 12 I 14 15 I5 17 In I9 IlEI nuuvvxxwwyu mvxxwwyyzzw cnm2123311525 lniti39l val es Initial values D u v w x y H u v w x y z u 0 2 5 I N 14 In 11 I1n I2 39 v 11 In IA I w 11 14 1D Is 17 18 W 5 3 3 39 x 12 I Is In In x Z 3 0 l y I7 In In I9 y N N I I 0 z In In In lo loopback Sockets What exactly are sockets an endpoint of a connection similar to UNIX file lO API provides a le descriptor associated with each endpoint endhost of a connection identi ed by the IP address and port number of both the sender and receiver Berkeley sockets is the most popular network API runs on Linux FreeBSD OS X Windows fedfed off the popularity of TCPIP can build higherlevel interfaces on top of sockets eg Remote Procedure Call RPC Based on C single threaded model does not require multiple threads Useful sample code available at httpwwwkohalacomstardunpv l Ze html Process File Table and Socket Descriptor ptocU 112dg c um W 7 ST e x F e le a 2119 l in Jacki L l I H 7 may l 39 l StevensTCPll lllustmed v 2 p 446 Types of Sockets Different types of sockets implement different service models Stream visa datagram Stream socket aka TCP connectionoriented reliable in order delivery atmostonce delivery no duplicates used by eigi ssh http Datagram socket aka UDP connectionless just datatransfer besteffort delivery possibly lower variance in delay used by eigi IP telephony streaming audio streaming video Internet gaming etci Simplified Email Delivery You want to send email to friendcsuscedu At your end your mailer translates csiusciedu to its IP address l28il25ili45 decides to use TCP as the transport protocol Why creates a socket connects to 28i l 25 l 45 at the wellknown SMTP port 25 parcels out your email Into packets At the receiver smtpd sends the ackets out P 39must make a receiver ahead of time 39creates a socket 39decides on TCP 39binds the socket to smtp s well On the Internet your packets got transmitted routed known port buffered 39listens on the socket forwarded or 39accepts your smtp connection dropped requests 39recves your email packets Sending Data Stream Client inf sendipacketschar buffer mt bufferilen l sentibytes Sendsd buffer bufferilen 0 1f sendibytes lt 0 perror send return 0 returns how many bytes are actually sent must oo to make sure that all is sent except for blocking IIO see UNP Section 62 What is blocking and nonblocking IIO Why do you want to use nonblocking IIO Initialize Server lnl sd lnl optval 1 1f sd scltetAF71NET SOCKisTREAM 0 lt 0 i perror open1ng TCP socketquot abort 1f setsockopt 5d SOL750CKET SOREUSEADDR ampoptval zeofoptval lt0 perror reuse addressquot abort7 SDREUSEADDR allows server to restart or multiple servers to bind to the same port with different IP addresses Initialize Server bind addr struct sockaddriln 51m memsetampsln o slzeof 51m 51nsln7famlly ALINET slnsln7addrs addr ANY DR 5m Slniport Jhtons servezjort 1f b1ndsd struct sockaddr ampsln slzeof sln lt 0 perror b1ndquot7 printfquotCannOt bind socket to addressnquot abort b1nd used only by server to label a socket with an IP address andor port Why do we need to label a socket with a pon Must each service have a wellknown port Why do we need to label a socket with IP address What if we want to receive packets from all network interfaces of the server machine Why not always receive from all interfaces What de nes a connection Initialize Server 1 i s ten 1f llStemsd qlen lt O l perror error listeningquot abort l 39 speci es max number of pending TCP connections waiting to be accepted using accept 39 only useful for connection oriented services but may be used by UDP also 39 TCP SYN denial of service attack API design question why not merge bind and listen Z Establish Server accept int addrilen 5izeofaddr int td td acceptsd struct sockaddr zaddr zaddrilen if td lt O i perror quoterror accepting connectionquot abort 39 waits for incoming client connection 39 returns a connected socket different from the listened to socket API design question why not merge listen and accept Z Socket Connection 3353 i iquot new td l Sim 4 4 mmmFlele mnamnn m iifk Miminil l l l lu lmmimh StevensTCPll illustrated v 2 pp ms Receiving Data Stream Server int receiveipacketsmhar buffer int bufferilen int bytesiread i int left bufferilen 7 bytesiread received recvtd buffer bytesiread left 0 return 0 returns the number of bytes actually received 0 if connection is closed I on error if nonblocking I if no data with errno set to EWOULDB LOCK must loop to ensure all data is received Why doesn t recv return all of the data at once How do you know you have received everything sent Connection close Client and Server close marks socket unusable 39 actual tear down depends on TCP bind Address already in use 39 socket option soiLlNGER can be used to specify whether close should return immediately or abort connection or wait for termination 39 The APls getsockopt and setsockopt are used to query and set socket options see UNP Ch 7 39 Other useful options SOiRchUF and SOisNDBUF used to set buffer sizes SoiKEEPALlVE tells server to ping client periodically How to Handle Multiple lO Streams NonBlocking IO Polling Where do we get incoming data stdln typically keyboardmouse input lnc opts fcntlsock Logan get current 39 sake 1f Opts lt D i socket op on set rigs 4 4 4 quotf 1 F GETE L quot Asynchronous arrival program doesn t know when data Will arrive 0 C i Alternatives 1f fcntlsock 575mm opts l OiNLlllELuCK lt n i quotf 1 F 5mm quot multithreading each thread handles one IIO stream 482 r Cquot t IIO multiplexing a single thread handles multiple IIO streams l Flavors while 1 1f recelveipacketswuffer bufferilen a blocking lO default mytesiread l D lt put processto sleep untli io l5 ready break blockingfor device availability and no compietlon by pulling or use ofseleCt b nomblocklr gvo 1f readiusermseribuffery useribufferileny 39I s e ibytesiread l u only checks or device availability break by pulling or signal driven not covered c asynchronous lO l o ocess ls notlfed when no is completed not covered Blocking IO select Blocking IO select to set read set select maxfd readset writeset exceptset timeout m timgval New whlle l l waits on multiple le descriptorssockets and timeout set u Enjwnolreadiset 4 4 4 4 4 TD SE istdln read set stdln 15 t 1311 El application does not consume CPU cycles while waiting oparameters in read 52 W Y r select 3 39 e 39 maxfd is the maximum le descriptor number Newt era mum NewtWEED D ifyou have only one descriptor number 5 maxfd is 6 run select En 522mmuwmmy 5 l 1 mafia NULL NULL SURE descriptor sets provided as bit mask 1f let El use FDizERO FDisET FDilsSET and FDicLR lt to work with the descriptor sets i perrur l39lseleecquot D l returns as soon as one of the speci ed sockets are ready l 4 4 1f let gt U i to be read or written or they have an error or timeout exceeded f m interpret Tlsd read setH returns of ready sockets on error 0 if timed out and no device is ready what I39SSUquot l recelveipacketsUnuffer bufferilen shytesiread l u for break s lfiiissiTlstdln readis t ls readiuseriuserihuffen userihufferilen suserihytesiread l u break l else tlmEd out l Internet Protocol Stack supporting network applications llTTP SMTP FTP etc transport endhost endhost data transfer TCP UDP routing of datagralns irom source to destination IP i39OlJlleig protocols data transfer between neighboring network elements Ethernet VWFi 1 bits on the wire applicaiion Transport network link phyelcol TCP Transmission Control Protocol Provides reliability on connectionless datagram network Link layer already provides sequencing and error control Why do we need to provide reliability again at the transport layer Need for E2E Reliability E2E Reliability Causes of unreliable delivery rerouted packets bit error droppedlost packets due to congestion system reboots How to achieve reliable delivery Reliable delivery requires tools Sequence Number With ARQ packets must be numbered why Sequence number space is nite Issues I sequence space size 2 sequence number wrap around 3 initial sequence number ISN Sequence Number Space Size Ifwe had only 2 bits to keep track of sequence numbers new or rexmit E El wee MPL Max Pkt Lifetime What prevention Sequence Number Space Size Let A time taken by receiver to ACK packet T time sender continues retransmitting ifACK not received Maximum Seqment Lifetime MSL2MPL TA Want no seq number may be duplicated within an MSL Sequence Number Wrap Around Sequence space is nite and sequence number can wrap around pkt 3 queued delayed Assuming s1 and s2 are not more than N2 apart s1 gt s2 if either I s1gt s2 and lsl eszl ltN2 or 52 51 2 s1lt s2 and ls17s2lgtN2 Required Sequence Number Size Require that if s1 gt s2s1 and s2 are not more than N2 apart ls1 s2 ltN2 within an MSL Let u be the transmission bandwidth ForTCPN 2321 ie seq number size n 31 bits want u lt N2MSL or 2 gt uMSL o l li N Example s2 51 SFNY MPL is 25 msec 0 N l l Let MSL 2 minfor n 31 bits 51 sz u must be lt l78 MBs I43 Mbps Initial Sequence Number ISN In case a connection got reincarnated we must choose an initial sequence number that will not cause packets from the old connection to interfere How can a connection be reincarnated Possible solutions I 2 3 ISN from System Clock Assume clock keeps ticking even when machine is down Want no seq number may be duplicated within an MSL se u wra I MSL orbldde 3 eglon wall for MSL E St 39 x m ssss on s resynchromze 1 l m l l l l l l clock tlck 1 l l m nne ar What to do on hitting forbidden region I wait for MSL before resuming transmission 2 resynchronize sequence number either case connection stalled TCP s Handling of ISN Connection identified by both addresses and port numbers and initial sequence number Connection cannot be reused for MSL time on connection teardown wait for 2MSL TIMEWAIT state bind Address already in use on reboot do not create connection for MSL 2 minutes on reboot starts global ISN from I ISN carried in SYNchronization packet during connection establishment Connection Establishment First try Sender S reboot Destination D Expected Seq ESN x1 ESTABLISHE SYN ISNZZ discard dropped but Connection with ESN X1 still ESTABLISHED Lesson connection request must be ACKed Connection Establishment Second try Sender Destination S D Stray SYN ISNX ESN X1 ESTABLISHED dlScard SYN ISNY ACK X1 Lesson connection ACK must be ACKed or rejected Connection Establishment Threeway handshake Sender S ESN e Y1 ESTABL SHED SYN uses a seq Destnat on D ESN X1 ESTABLSHED ACK Y1 ThreeWal Handshake How threeway handshake solves the original problems Sender Destination Sender Destination S D s D syn ISNX stray syn ISNX 1 0 syn ISNY ESTABLISHED syn ISNZ ACK X discard RST Y RST z Connection Teardown When to release a connection le how do you know the other side is done sending and all sent packets have arrived Use 3way handshake to teardown connection Sender Destination S D ACK Y1 FIN also uses a seq Connection Teardown Ifthe other side still has data to send Sender Destination S D More data pkts from E Why not send ACK Xl along with FIN Y Connection Teardown Still depends on timeout Sender Destination Sender Destination 5 D s D times out and tears down connectio unllaterally Connection Teardown Still depends on timeout Sender Destination S D ACK Xl FIN after n attempts tea rs ACK Xl FIN connection unilaterally nnectlon unilaterally TCP connection teardown depends on timers for correctness but uses 3way handshake for performance improvement TCP Connection Management FSM m initiates a TCP connection send 5am mil iii sFi39nn n lEr Elva Fil l send AMA TCP server client application I cycl e initiates close connection rPFFlVB ii mi iii inn rreemsend FlN receive ACK TCP client sen mining lifecycle server application creates a listen socket receive ACK send noining receive FlN generally not used Header RSTSYN FIN connection establishment setup teardown 32 bits source port dest port counting sequence number by bytes acknowledgement number of data number of head not not se t 39 I U A P R S gmen s 32blt elds Ien used F Window Size in header checksum urg data pointer receiver window URG urgent data options variable length size md in bytes pointer valid end of urgent ACKzACK valid aPP39icatiOquot data eg Ac data PSH Push data now variable length Maximum Segment Size ffl h I 6 Us l negotiationdefault I minimum required required 536 bytes data TCP Header Fields Sequence number data is sent in segments packets with seq sequence numbers count bytes sent ACK may be piggybacked on data packet Checksum checksum computed including pseudo lP header computed with all 0 s in the checksum field l s complement of result stored in checksum field gt when checksum is computed at receiver result is 0 TCP Cumulative ACK ACKs the last byte received inorder tells sender the nextexpected seq ie if bytes 0 to i have been receivedACK says i subsequent outof order packets generate the same cumulative ACK Sensder Destigation 8 bytes seq 0 10 bytes seq 8 10 bytes seq 18 10 bytes seq 28 ack 18 ack l8 Advantage lost ACK can be covered by later ACKs Disadvantage size of gap between two pkts not known to sender TCP Flow Control flow control sender won39t overflow receiver39s buffer by transmitting too much receive side of TCP connection has a receive buffer F Rchfmdow A 7 Rchu er 44 application xXk data from IP e x Receiver advertises buffer space available by including the application process may be slow at current value Of rwnd m TCP reading from the buffer header Sender limits unACKed data to rwnd gtguarantees receiver buffer doesn t overflow TCP Flow Control Problems Two flowcontrol problems I receiver too slow sillywindow syndrome 2 sender s data comes in small amount Nagle s algorithm Sillywindow syndrome receiver window opens only by a small amount hence sender can send only a small amount of data at a time Why is this not good I 2 Sender DeStlnathn S D w 2500 0 srze 1000 2000 500 appllcation reads out 1 byte w1 appllcatlon reads out 1 byte w1 Solution to Sillywindow Syndrome Don t advertise window until it opens signi cantly gt V2MSS or Vz l rwnd Sender Destination 5 D w 2500 Implementation alternatives ACK with rwnd0 sender probes after persistence timer goes off delayed ACK but not more than 500 ms or 1000 1000 000 500 appllcatlon reads out 1 byte w 0 persrst trmer ACK every other segment Why probe 2499 1 w 2000 TCP Delayed ACK Generation Event at Receiver Arrival of inorder segment with expected seq All data up to expected seq alreadyACKed Arrival of inorder segment with expected seq One other segment has ACK pending Arrival of outof order segment higherthanexpect seq Gap detected Arrival of segment that partially or completely lls gap TCP Receiver action Delayed ACK Wait up to 500ms for next segment If no next segment send ACK Immediately send single cumulative ACKACKing both inorder segments Immediately send duplicate ACK indicating seq of next expected byte Immediately send ACK provided that segment starts at lower end of gap Characteristics of Interactive Applications User sends only a small amount of data eg telnet sends one character at a time Problem 40byte header for every byte sent Solution clumping sender clumps data together ie sender waits for a reasonable amount of time before sending How long is reasonable Nagle Algorithm send rst segment immediately accumulate data until ACK returns or 392 sender window or 392 M88 amount of data has been accumulated Advantages bulk transfer is not held up data sent as fast as network can deliver Can be disabled by setsockopt TCELNODELAY Nagle Algorithm Nagle sends data as fast as network can deliver Sender Receiver Sender Receiver R round rip R round up ime r Ime r L w1 bytes 1n Zrtts Retransmission Timeout ARQ depends on retransmission to achieve reliability Retransmission timeout RTO computed from round trip time R39I39r On the Internet R39I39r of a path varies over time due to I Sender Receiver R round rip Varying R39I39r complicates the computation of 2x I retransmission timeout RTO 2 optimal sender s window size 7 7 re ransmission imeou r 0 Estimating RTT Implications of Bad RTO RTO too small RTO too big RTO must adapt to actual AND current R39I39r unnecessary retransm39ss39ons lower throughpun sampleR l r time between when a segment is transmitted and when its ACK is received Sensder R higher D l g t On S nd r RouRter Destlgatlon 1 estimatedR l r computed by exponential weighted average estimatedR l r 06currentR39l39restimate locsampleR39l39r where 06 is the weight OH I each sample changes the estimate only a little bit 06 0 each sample influences the estimate heavily 06 is typically 78 3923 which allows for fast implementation Example RTT Estimation How to Compute RTO R17 yahcsmmassldu la fanhslamunmlmh 55 quot First try RTO R39I39r with typically 2 or 3 Two problems Sender Destination 3130 S D A which packet to associate EM 1 ll l with an ACK in case of 0 pkl 1 M retransmission All tt an 1 r 392 i l ill quotI ll ll l v il llll l ll M W i in l j 150 mmmlawm I 2 R39I39rs spread too wide Routing on the Internet Hierarchical Routing In the beginning there was the ARPANET f ggregate routers In reglons Of route using GGP GatewaytoGateway Protocol aUtonomous SYStems AS a distance vector routing protocol Routers in same AS run same routing protocol intraAS routing protocol Problems needed flaghour to update routing protocol incompatibility across vendors I I I each AS uses Its own IInk metrlc routers in different ASs can run SOIUtIOW hlerarChlcaI FOUtlng different intraAS routing protocol administrative autonomy each network admin can control 0 dest next routing within its own network Gatewayborder router I gtxlt I I 0 internet network of networks 39 dIFECt to router In Other allows the Internet to scale 39 keePS in its routing table 4 2 I with 200 million hosts each router next hop to other A55 32 32 can t store all destinations in its mm septemberwn aII hosts within Its As 39 39 rowing table hosts within an AS onl kee a default 33 33 route updates alone will swamp the links y P 34 34 route to the border router 9f the Internet around I 999 T h e N S I N et I 9 8 9 mm gygg s i Area hierarchy 11333313 backbonecore NSFNet regional networks MichNet cuswmernetworks BARRNET Los Nettos Cerfnet JVCNet NEARNet etc Use Walrand campus networks Boulder CO Sali Lake City UT L39m o39rquot Cham paign N E II San Diego quot39 CA I Houston r TX Halabi 39 Merit Networks CommerCIallzatIon I994 Roughly hierarchical At center Tier I lSPs W m r All l k A flll nl i TIerl ASs are those who have Wu peering relationship with each of Wmma b the other TIerl ASs eg UUNet I BBNGenuity Sprint ATampT Inmmcepmvm quot 39 ma39or ones wi 11 w 39 61 7quot nationalInternational coverage Mmequot 5 3 a 4 a In I I f peers exchange traf c for free customers must pay to have their Wa39rand traf c carried mam TIerl provnders also I r a interconnect at public l g Tier network access l J Kym Providers POlntS NAPS interconnect J 9554 WWW We peer privately y I l 1 4 1m r l 739 3 K A E I U 1 0 Halabi F 4 39 i 39 quot v Tierl lSPI eg SPFth Qwest IP Backbone Late I999 Sprint US backbone network 3 a I 6 d c r fg1396 j 39v 5 39V 1 394 s quot l quot h l a 39 Ir 1 y A quot fl 39 vane r l 7quot 0 4 o III l I i I i A 7 39 4 jft a 39 1quot a 39 h F 39 39 V 4 39739 i 39 I 397 UV gtv I ltquot 21 l v r d I v lp F 7 V39ii p 4 7 L M 39 l v r 1 I39 m39 3921 V vquot 39 I r V h V quotH 1 n 39d u u f 9 r 39 v It 39 l d O t r V94 4 9 M r I 8quot v V 4 Bloating r 1 39 39 y Mugmba 3991 q 39 39 1 J 39 v H I I Exi39bu iflf f an 595 Qty 39 I l quotI I 5 a l r atquot a quot 39 622 i39f i 0012 39 01m 155 mpg 003 o mast Hymn CC C t quotl0 Erase r A 3933 We L 4 0 a v uhcm n w quot L 5 i l r 439 c Q I 5 7 o i h l quot 7 I 5 1 1 v 39 4 A aquot V 3 10 a I 39 g O TeraPOP I I iquot g I VY wlv 27 1QQQC ytetllenters t A K 9 1 1 A 391 an I print Iu12 g 0133 AMERICA UUNET s Global Internet Backbone nnnnn on nnnnnnn on vumnm svnuzv Forrnore information visit wwwuunet I I I I I I Anme Tier2 ISPs Smaller Often Regional ISPs Tier2 ISPs also Connect to one or more tierl peer privately with h th d ISPs pOSSIbly other tier2 ISPs fggrgnjgggt NAPs Tier2 ISP pays tierI ISP for connectivity to rest of Internet tier2 ISP is customer ofTierI provider Tier ISP Tier3 ISPs and local ISPs Last hop access network closest to end systems Local and tier 3 ISPs are customers of higher tier ISPs connecting them to rest of Internet Tier I IS NAP 4quot Tier ISP ISP Backbone Links Categories of links by insideoutside AS backbone links connect routers inside the backbone edge links connect an AS with other Ass Categorization by commercial relationship access links customers to ISP can be multihomed peering links interAS connections Transit flow 39 either direct peering or through NAPS 6 F633 may have multIple peerlng relatlonshlps at gig different geographic locations Categorization by traf c flow 0 i ingress link egress IInk Ingress flow L egress l temal ows access links ISP Backbone Traf c Types of traf c internal traf c between 2 access links transit traf c between 2 peering links inbound traf c ingress at peering link egress at access link outbound traf c vice versa An lSP may choose to carry transit traf c Most traf c on large lSPs Tierl ASs is transit traf c WW Internal J Internet interAS Routing BGP BGP Border Gateway Protocol is the de facto standard for interAS routing BGP provides each AS a means to obtain subnet pre x reachability information from neighboring ASs propagate the reachability information to all routers internal to the AS determine good routes to subnets based on reachability information and policy InterAS routing is policy driven not loadsensitive generally not 205 based When AS2 advertises a pre x to AS I AS2 is promising ASl to forward any datagrams destined to that pre x coming from ASl AS2 can aggregate pre xes in its advertisement Path Attributes amp BGP Routes When advertising a pre x advertisement includes BGP attributes Two important attributes AS PATH the path vector of A55 through which the advertisement for a pre x passed through NEXT HOP the speci c internalAS router to nexthop AS there may be multiple exits from current AS to nexthopAS Sample BGP entry destination NEXT HOP AS PATH 19832163024 20223218 2497 2914 3582 4600 address range l9832 l 63024 is in AS 4600 to get there send to next hop router which has address 202232 l 8 the path there goes through A55 2497 29l4 3582 in order A History of DN S Violence Jon Oberheide jonojonoumiehedu Software Reading Group Volume I DN S Cache Poisoning DNS Translates youtubecom to 20865 153238 Except when Pakistan leaks blackholed routes doh Hierachical distributed database Providing domain name services A PTR MX CNAME whatever you need DNS is pretty simple right Simple Not a Chance Before continuing please read the following RFCs 8058118198818828838979209219739741032103310341035 1101112211231178118313481386146414801535153615371591 1611161216371664170617121713179417981811181618761886 1912195619821995199620102052205320652100213621372142 2146216321682181218222192230224022472276230723082317 2345235223772517253525362537253825392540254125432553 2606267126722673269427662772278228252826283228452870 2874291529162929293029312937297230073008307130903110 3123315231973225322632453254325832633352336333643367 3368340134023403340434053425344534673490349134923596 359736453646365536583675369637553757 Some Basic Terms Zone a particular domain name eg mail googlecom WWWeecsumichedu Resource Record RR a particular zonetypeclass eg I39m querying for umicheduMUIN Authoritative server server that is quotin chargequot and trusted for maintaining information on zones Recursive resolver locates and queries auth servers on behalf of its clients eg your ISPs resolver zipeecsumichedu Example Query N5 Query Recursive by Nmogoam Rum Servers I cum Namespaoe Step 2 Slim 3 ummn where can m we w Answer mm knew hu com an ewer mm ha less a somevwebs an autharilalive Var samewebsewsr com Use s Puma UNS Server Recursion Allowed 5 5 1 Uneshan whalxs he w mil de Addressalsome 9mmquot 5W wahservar no 7 Please reply to My F Addr SS W bsewy Wm Primary ENS Same of sumerwahserver mm Caching Querying the auth server for every request is silly Keep track of responses for better performance Resolver maintains cache Resolver sends out query Gets response from auth server Caches all RRs contained in response Entries evicted when its TTL expires Cache Poisoning DNS cache poisoning the insertion of a malicious entry in the resolver39s cache eg tell resolver that paypalcom redirects to attacker39s IP Effects can be long term Wide spread Entry stays around for whatever TTL the attacker specifies All users that the resolver services think big ISP resolver are affected Why Cache Poisoning Sucks We use DNS for everything When did you last use an IP address or etchosts entry A loss of name service integrity 2 GAME OVER Unless protected by higher level security eg SSL Attacks may vary in severity From harmless rick rolling harmless is debatable To quotOh crap the interwebs are gonequot TXID quotDefensequot quotThe DNS designers were concerned with security when they designed it rightquot Not really This was 1987 Transaction ID TXID 16bit field in DNS header Matches responses to the original request Attacker must know TXID to spoof response TXID is quotsecurity by accidentquot Defeating the TXID Attacker needs to know A request is happening medium The RR being requested easy The authoritative server for that RR easy The TXID of the request hard Spoof response to resolver from auth server with malicious answer to poison cache But how to get TXID Sequential TXIDs BIND used to use sequential TXIDs Trivial for an attacker to poison any RR Issue was discovered in 1997 This is 10 years after DNS was designed Seems obvious but again that was a while back Now they39re randomized