Cheating Sheet

TCP: uses 1’s complement for their  checksums. UDP: preserves meg  boundaries TCP: does not! Byte­ stream oriented)

P2P architecture: no always-on server, arbitrary end systems directly communicate, peers are intermittently connected and change IP addresses, highly scalable

Components of web searching: Crawler(gather content, depth first), Index (organize), Rank (take query), 4 laws: show ID, obey robot exclusion standard, not hog resources, report errors

Response time: 2*RTT (one to initiate TCP con. + one for HTTP request and first few bytes of response) + transmit time RTT: EstRTT = (1­α)EstRTT + α  SampRTT

Out-of-Band Control: FTP sends its control information, which includes user identification, password, and put/get commands, on one connection, and sends data files on a separate parallel connection. Because it uses a separate connection for the control information, FTP uses out-of-band control. FTP: is application layer protocol, uses more than one port at server, Messages “in­band” control & data messages may be  interleaved (HTTP, DNS, SMTP)  “out­of­bound”  control and data  messages carried in separate  connections (FTP) TCP/IP model: application (Telnet, FTP, SMTP,DNS) – Transport( TCP, UDP) – Internet (IP, ARP,DHCP)—Network Access (Data Link—Physical) (Ethernet, ADSL)

HTTP: web’s appl. protocol, uses TCP, port 80, “stateless” (no info maintained) non-persistent: at most one object send over one TCP connection (1.0) 1) initiate 2) accept 3) send ‘request’ msg 4) forms ‘response’ msg persitent: multiple objects over single connection, server leaves conn. open after sending response (1.1) Reliable data transfer (rdt): 1)rdt_send() 2) udt_send() 3) rdt_rcv() 4) deliver_data() rdt2.1 seq# added (0,1) to check whether ACK, NAK is corrupted, check for duplicates rdt3.0 timeout to check for loss, 4 stages: 1)send pkt0 2)rcv pkt0, send ACK0 3) rcv ACK0, send pkt1 4)rcv pkt1, send ACK1, after timeoutresend Performance: T= L/R Utilization: U=T/RTT+L/R Pipelining: increment seq#, buffer at sender/receiver, increase utilization

Propagation delay d/s = length of phys link/pop.speed (2x108m/sec Transmission delay: R=link bandwidth (bps) L=packet length (bits) time to send bits into link = L/R Maximum no of bits in the link: max {no of bits sent in dprop, file size} Nodal delay: dproc + dqueue + dtransm + dprop Queue delay: L * a/R or [NL+(L-X)]/R withN:packets already in queue, x:bits of current transmitted pkt

Packet switching: data sent  through net in discrete chunks,  each end­to­end data stream  divided into packets, packets  share network resources, each  packet uses full link BW  Congestion: packets queue and  wait  asynchr. Stat.  multiplexing: sequence of  packets does not have to have  fixed pattern, shared on demand  Store&Forward: entire packets  must arrive at router before it can  be transmitted to next link  

Client-Server: distr. Time dcs = max{N*F/Us, F /min(di)} where N: no. of peers, Us: upload time, F: file, di:download BW

DNS: distributed DB, appl. layer protocol, maps IP address to name(resolve names), root name servers (.com/.org/.edu)  TLD (top level domain) servers: responsible for .com/.org, authoritative DNS servers: organizations, UDP

Socket: host-local, appl. created, OS controlled interface into which app. processes can both send and receive messages Multiplexing (at sender): gathering data from multiple sockets, enveloping with header De-multiplexing (at receiver): delivering received segments to correct socket, each datagram has source IP +dest IP, each segment has source port + dest port,

Information used in UDP for de­ multiplexing Destination IP add,  Dest port no.; information used in  TCP for de­multiplexing  source  IP, Source port no, dest IP, dest port  no.

Go-back-N (GBN): window for up to N conseq. unACKed packets, timer Selective repeat: individually ACKs for all corr. Received packets , only resend packets w/o ACKs, timeout buffer if out-of-order seq# >= 2n+1 because: receiver waits for packet m window[m,m+n-1] (leading edge), received packet m-1 & n1 packets before, none of n ACKs yet received ACK message with [m-n,m1]still propagating, none received window:[m-n,m-1](lower edge)to avoid overlap seq# space must be big enough to accommodate 2n seq# Delay modeling: R: rate/BW S: MSS(bits) O: Object size(bits) W: window Congestion Control: sender limits transmission: rate: congWin/RTT AIMD:  size/segments P: number of idle times Q: object infinite size K: no.of windows increase by 1 after RTT until loss, cut CongWin half after loss Slow start:  cover the object P=min{Q,K-1} K=[log2 (O/S +1)] Latency =2RTT + O/R + CongWin=1MSS, double every RTT (increase CongWin for every ACK  P[RTT+ S/R] – (2P-1)S/R rcvd), after 3 dup ACKs (loss)  cut in half, then linear growth, but after  Q=[log2(1+RTT/S/R)]+1 Slow start: fixed window WS/R>RTT+S/R  timeout: set back to 1MSS  grow exp until threshold, then linear,  delay=2RTT+O/R , WS/R
Exercise: n DNS servers have to be visit, one base HTML file + two small objects on server A, three small objects on server B  initially for all DNS contact to obtain addresse = RTT1 + RTT2+…+RTTN = Σ RTTi a)non-persistent HTTP no parallel con: time = Σ RTTi + Σ RTTi +2RTT_A+2*2RTT_A+3*2RTT_B b)non-persistent with parallel con: time = Σ RTTi + Σ RTTi + 2RTT_A (base file) +2RTT_A (for parallel con of 2 objects) + 2RTT_B (for parallel con for 3objects) c) persistent w/o pipelining: time= Σ RTTi + Σ RTTi + 2RTT_A + 2RTT_A + 4RTT_B d)persistent with pipelining: time= Σ RTTi + Σ RTTi + 2RTT_A + 1RTT_A + 2RTT_B Exercise: sending 700bytes over TCP connection MSS=200bytes, org. window size 200byte, slow start, timeout 700ms, it takes all pkts 200ms to arrive