Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
146 Cards in this Set
- Front
- Back
|
What's Internet - Nuts and Bolts |
-Hosts = end systems running network apps -Comm. links = fiber, copper radio, satellite, transmission rate = bandwidth -routers: forward packets -protocols: control sending/receiving msgs -"Network of Networks" -> hierarchical |
|
|
What's Internet - Service View |
-comm. infrastructure enables distributed apps -comm. services provided to apps 1) reliable data delivery 2) "best effort" |
|
|
What's a protocl? |
-define format, order of msgs sent and received among network entities, actions taken on transmission, receipt -govern internet activity |
|
|
Network Structure |
-edge: apps and hosts
-access networks, phys. media: wired/less comm. links -network core: routers, network of networks |
|
|
Network Edge |
End System (hosts) -> run app programs Models: Client/Server, P2P |
|
|
Client-Server Model |
-client hosts requests, receives service from always-on server |
|
|
P2P model |
minimal (or no) use of dedicated servers |
|
|
Access Networks/Phys. Media - How to Connect? |
-residential access nets
-institutional access networks -mobile access networks |
|
|
Residential Access: Point to Point |
-Dialup via modem - can't always be on -DSL: Digital Subscriber Line ->thru telephone company ->dedicated line to central office -HFC: hybrid fiber coax: asymmetric ->network of cable and fiber attaches homes to ISP router thru cable companies |
|
|
Company Access |
Local area networks (LAN) - connects end system to router Ethernet -> end systems connect to Ethernet switch |
|
|
Wireless Access Networks |
-shared wireless access network connects end system to router -> via base station "access point" -wireless LAN -> Wifi -wider-area wireless access -> telco operator |
|
|
Home Networks |
-DSL/Cable -router/firewall/NAT -Ethernet -wireless access point |
|
|
Physical Media |
-bit: propagates -physical link: what lies between -guided media: solids; copper, fiber, coax -unguided media: freely propagate (radio) Twisted Pair (TP): two insulated copper wires Coax: concentric copper conductors Fiber optic: glass fiber carries light pulses radio: EM spectrum, bidirectional ->microwave, LAN, cellular, satellite |
|
|
Network Core + Fundamental Question |
-mesh of interconnected routers -HOw to transfer? 1) circuit switching, dedicated circuit per call 2) packet switching: data sent w/ discrete chunks |
|
|
Circuit Switching |
End-end resources reserved for "call" -bandwidth, switch capacity -dedicated resources -> no sharing -circuit-like -> guaranteed performance -call setup required -resources divided into pieces -> idle if not in use |
|
|
Types of Circuit Switching Division |
Frequency Division Time Division |
|
|
Packet Switching |
each end-end data stream divided into packets -packets share resources -packet uses full bandwidth -resources as needed Resource contention |
|
|
Packet Resource Contention |
-aggregate resource demand can exceed amount availabe -congestion: packets queue, wait for link use -store and forward: packets move one hop at a time -> receives complete packet |
|
|
Statistical Multiplexing |
Sequence of packets from different hosts doesn't have fixed pattern, bandwidth shared on demand |
|
|
Store-and-forward |
L = packet size (bits) R = bandwidth (bps) Push out in L/R time -entire packet must arrive at router before transmission |
|
|
Packet Switching vs Circuit Switching |
Packet switching allows more users to use network 1 Mb/s link, 1- users, 10% of time each is active circuit: 10 users, 100 kb/s each Packet: 35 users has roughly same ability Packets -> great for bursty data, Congestion: packet delay and loss |
|
|
Network of Networks -> Structure |
Roughly Hierarchical -Tier 1 ISPs -> Verizon, AT&T -Tier 2 -> often regional ISPs -Tier 3 -> smaller -Local ISPs |
|
|
Why Network of Networks? |
Internet -better scaling -> heterogeneity, incremental expnasion/deployment -Decentralized management -> no single entity controls Telephone -operator owns own network, harder to interoperate |
|
|
Network Performance Metrics |
Throughput Delay Loss |
|
|
How do loss and delay occur? |
-packets queue in router buffers, arrival rate can exceed link capactiy -> queue fills |
|
|
Four Sources of Delay |
1) Nodal processing -> checking bit errors, determining output link 2) queueing -> waiting at output link for transmission, depends on router 3) Transmission Delay -> L/R 4) Propagation Delay -> constrained by speed of light -> d/s |
|
|
Nodal Delay |
d(proc) + d(queue) + d(trans) + d(prop) few us depends L/R few us to 100s of ms |
|
|
Queuing Delay |
R = bandwidth L = packet length a = average arrival rate Traffic Intensity = La/R ~0 : small delay ->1 : large delay >1: Infinite delay |
|
|
Traceroute |
Provides delay measurement from source to router along end-end path towards destination -sneds three packets that will be returned by ith router |
|
|
Packet Loss |
-Queue preceding link in buffer has finite capacity -packets arriving at full queue are lost -lost packet may be retransmitted by previous node, end system, or not at all |
|
|
Throughput |
Rate (bits/time) at which bits transferred between sender/receiver -instantaneous and average Lower R in two links -> constrains throughput = Bottleneck Link |
|
|
Protocol Layers -> Why? |
-explicit structure allows identification, relationship of complex system's pieces -> reference model -modularization eases maintenance |
|
|
Internet Protocol Stack |
Application: network apps Transport: process-process data transfer Network: routing datagrams from sources to dest Link: Data transfer between neighboring network elements: Ethernet Physical: bits on wire |
|
|
ISO/OSI Model |
Adds Presentation and Session between app and transport Presentation -> apps interpret meaning of data Session: synchronization, checkpointing, recovery of data exchange |
|
|
Network Security |
-about attacks, defense, architectures to avoid attacks -Internet designed w/ security in mind |
|
|
Malware |
-virus: receive and open attachment -worm: passively received object trojan horse: hidden in otherwise useful software -spyware -< record keystrokes, other info -infected host can be used for DDoS -often self-replicating |
|
|
Denial of Service |
make resources unavailable to legitimate traffic by overwhelming with bogus traffic |
|
|
Packet Sniffing |
broadcast media (Ethernet, wireless) -reads/records all packets passing by |
|
|
IP Spoofing |
send packet w/ false source address |
|
|
Record and Playback |
sniff sensitive info for later use |
|
|
History |
60s -> packet switching principles 70s -> internetworking, tests 80s -> new protocols, proliferation 90s, 00s -> commercialization, Web, apps |
|
|
Application ARchitecutres |
-Client-Server -P2P -Hybrid |
|
|
Client-Server |
Server: always on, permanent IP, farms for scaling Clients: comm. w/ server, intermittently connected, dynamic IP add, no comm. directly w/ each other |
|
|
Pure P2P architecture |
-no always on server -arbitrary end systems comm. directly -peers intermittently connected and change IP add -scalable, hard to manage |
|
|
Hybrid |
-centralized server -Skype: find address -IM: client presence detection |
|
|
Prcoesses Communicating |
Process -> program running in a host -communicate with messages Client vs Server process -> initiate vs wait for contact |
|
|
Sockets |
process sends/receives msgs to/from its socket -like a door |
|
|
Addressing Processes |
-identifer includes IP address and port numbers |
|
|
App-layer protocol defines |
-types of messages -syntax -semantics -rules for sending/responding Public Domain: HTTP, SMTP, FTP Proprietary: Skype |
|
|
What transport service does app need? |
Loss Timing Throughput Security |
|
|
Transport Protocols |
TCP: connection oriented, reliable, flow control, congestion control, no timing/throughput/security guarantees UDP: unreliable, no setup/reliability/flow control/congestion control/timing/throughput/security |
|
|
HTTP |
Hypertext transfer protocol Client: browser that request, receives, displays objects Server: sends objects in response to requests Uses TCP -> Port 80 Stateless |
|
|
Types of HTTP Connections |
-Nonpersistent: at most one object per connection -Persistent: multiple objects sent over single connection |
|
|
Non-Persistent HTTP: Response Time |
RTT -> time for small packet to go from client to server and back Response time: One RTT initiate, one RTT for request, transmission time (2 RTTs for objects, connection overhead) |
|
|
Persistent HTTP |
-server leaves connection open after sending response -subsequent messages use same connection -client sends requests as soon as it encounters ref. object -as little as one RTT for all objects |
|
|
HTTP Request Message |
Method URL Version Header: Value \n Body POST: input uploaded in entity body URL method: uses GET, input uploaded in URL field Also HEAD - asks server to leave requested object out of response DELETE - deletes file in URL field PUT - uploads file in entity body |
|
|
HTTP Response Message |
Protocol Status Code Status Phrase Headers \n Data |
|
|
HTTP Status Codes |
200 OK 301 Moved Permanently (Location: header) 400 Bad Request (not understood) 404 Not Found (doc not on serever) 505 HTTP Version not supported |
|
|
Cookies |
Four COmponents 1) cookie header line in HTTP response 2) cookie header line in request message 3) cookie file kept on host, managed by browser 4) back end database at website Bring: authorization, shopping carts/recommendations, session state |
|
|
Web Caches (Proxy Server) |
-satisfy client request w/o involving origin server -keeps cache, responds if object found, forwards request if not -acts as client/server -placed with institutional network |
|
|
Why Web caching? |
-reduce response time for request -reduce traffic on access link -enables "poor" providers to deliver content effectively |
|
|
Conditional GET |
-for proxy servers -don't send object if cache is up to date -cache: specify date of cached copy in HTTP request -server: response contains no object if cached copy is up-to-date |
|
|
FTP |
File transfer protocol port 21 Uses separate control, data connections (TCP) -> called "out of band" Only one file Holds state info |
|
|
FTP Commands |
USER PASS LIST RETR STOR |
|
|
FTP Return Codes |
331 Username OK 125 data connection open, transfer starting 425 Can't open connecton 452 Error writing file |
|
|
Electronic Mail |
Three Components 1) User agents -> mail reader, composes, edit, read, messages stored on server 2) mail servers -> mailbox for incoming messages, message queue for outgoing msgs 3) SMTP -> between mail servers |
|
|
SMTP |
-uses TCP port 25 -direct transfer -> sending server to receiving server -Three phases 1) handshake 2) transfer 3) closure Persistent connections, 7-bit ASCII HELO, MAIL FROM, RCPT TO, DATA, QUIT |
|
|
SMTP vs HTTP |
Push vs Pull -both use ASCII Comand/Response interaction, status codes HTTP: object encapsulated in own message SMTP: mutliple objects sent in multipart msg |
|
|
Mail Message Format |
Header -> To:, From:, Subject: -> different from SMTP commands BlankLine Body Multimedia extension: MIME, add lines in header |
|
|
Mail Access Protcols |
Retrieval from server POP Post Office Protocl-> auth and download IMAP Inet Mail Access Prto-> more complex, manipultte stored messages HTTP |
|
|
POP3 |
auth phase, transaction phase user, pass commands +OK, -ERR response list, retr, dele, quit (all by number) -download and delete vs download and keep |
|
|
IMAP |
keep all messages in server -organize in folders -keeps state across sessions |
|
|
DNS |
Domain Name System -distributed datbase -> name servers -app layer protocol ->host, routers, name servers comm to resolve names(address/name translation UDP |
|
|
DNS services |
-hostname to IP addr trans -host aliasing -> canonical vs alias -mail server alias -load distribution -> multiple IP add for one name |
|
|
Why distribute DNS |
-no single failure point -traffic volume -don't want to be distant from places -maintenance ->doesn't scale |
|
|
DNS Hierarchy |
Root Servers - contacted by local name server Top Level Domain - com, org, net etc Authoritative Servers - organization DNS servers, hostname to IP mappings for org's servers |
|
|
Local Name Server |
Not strictly in hierarchy All ISPs have one -> residential, company Query sent here from host |
|
|
DNS Queries |
Iterated: contact server, give you different server to ask REcursive: contact server, server contacts another to find mapping |
|
|
DNS: Caching/Updating |
-once name server learns a mapping, it caches it -> entries timeout after some time ->TLD servers usually cached in local name servers ->update under design by IETF |
|
|
DNS REcords |
Distributed DB stores RRs (Resource Records) (name, value, type, ttl) Type A -> name is hostname, value is IP address Type NS -> name domain, value authoritative name for domain Type CNAME -> name alias, value canonical Type MX -> name mailserver, value name of server |
|
|
DNS protocol |
Query/reply messages w/ same format Header ID 16bit #, reply same as query Flags (recursion) Fields for query, RRs in response, records for authoritative servers, helpful add. info |
|
|
Inserting Records |
-register name w/ registrar (name, IP add, authoritative name server) Type NS for name -> hostname Type A for hostname -> IP |
|
|
Pure P2P Architecture |
-no always-on server -arbitrary end systems comm -peers are intermittently connected and change IP adds |
|
|
Server-Client File Dist. Time |
N copies, F size, us is upload speed, di is download speed of each client TIme = max(NF/us, F/min(di)) |
|
|
P2P File dist time |
N copies, F size, us upload speed, F/di for each client to download, NF total bits uploaded Time = max(F/us, F/min(di), NF/us + Sum(ui) |
|
|
BitTorrent |
tracker: tracks peers in torrent Torrent: group of peers exchanging file chunks 256 kb chunks peer joining has no chunks, registers w/ tracker to get peers and connects to "neighbors" Pull from different subjects of chunks Requests rarest first Send chunks to top 4 neighbors (unchoked), one random every 30s (optimistically unchoked) |
|
|
P2P searching for info |
Index: maps info to peer location (IP/port) File sharing -> tracks loc of files peers share IM -> user names to locations |
|
|
P2P Centralized Index |
Napster Central server gets IP/content of each peer Issues: single point of failure bottleneck copyright laws |
|
|
Query Flooding |
fully distributed peers index files it makes available overlay network: graph -> edge between X and Y if conn. active peers form overlay net -edge virtual link query message sent over TCP, peers forward, limited scope |
|
|
Hierarchical Overlay |
between centralized, query flooding -each peer is either super node or assigned to super node -> super node tracks content in children |
|
|
Skype |
P2P App layer proprietary protocol -hierarchical overlay w/ SNs -Index maps usernames to IP, distributed over SN Peers can go through relay if NATs prevent initiating a call between them |
|
|
Distributed Hash Table (DHT) |
-distributed P2P database -has (key, value) pairs -Distribute pairs over peers -Peer queries DHT w/ key, receives value -Peer can also insert pairs |
|
|
How to Assign Keys to Peers |
-convert key to int -assign int to each peer -put pair in peer closest (immediate successor) to key -each peer gets [0, 2^n-1] |
|
|
Circular DHT |
peer only aware of immediate successor/predecessor -"overlay network" -O(N) to resolve query Add shortcuts to get O(log N) neighbors/query time |
|
|
Socket Programming |
build client/server apps to comm w/ sockets Socket: host-local, app created, OS-controlled interface wher app processes can send/rcv msgs |
|
|
Sockets w/ TCP |
-reliable transfer -Client must contact server by creating local socket, specifying IP, port number of server, establish TCP connection -Server creates new socket for each client process |
|
|
Stream Jargon |
Stream is sequence of characters into/out of process Input stream -> attached to some input source for the process (keyboard/socket) Output steam -> attached to output sources (monitor/socket) |
|
|
UDP Socket Programming |
-no connection/handshaking -sender attaches IP add and port of dest to each packet, server extracts IP add/port from received |
|
|
Transport Services and Protocols |
-logical comm. between app process on diff hosts -run in send systems: sender breaks msg into segments, passes to nework layer, receiver reassembles message, passes to app layer |
|
|
Transport vs Network Layer |
Network: logical comm between hosts transport: logical comm between processes |
|
|
Internet Transport-layer protcols |
TCP -> reliable, in-order, congestion/flow control, conn setup UDP -> unreliable, unordered, best-effort extension of IP -no delay/bandwidth guarantees |
|
|
Multiplexing/Demultiplexing |
Demultiplexing - receiver delivers segments to right socket Multiplexing - sender gathers data from sockets, envelops w/ header |
|
|
Demultiplexing |
-host receives IP datagrams w/ source IP, dest IP with transport-layer segment for source/dest port number -uses this to direct to right socket |
|
|
Connectionless Demultiplexing |
-UDP sockets w/ port no created, identified by two-tuple (dest IP, dest port) -host checks portno when it receives, directs to that socket (source IP/portno dont make diff) |
|
|
Connection-Oriented Demux |
-TCP socket identified by (source IP, source portno, dest IP, dest portno) -receiver needs all 4 -server can host multiple TCP sockets, diff for each client |
|
|
UDP |
User Datagram Protocol -no frills/bare bones -best effort: may be lost or out of order -no connection/handshake, simple, smaller header -no congestion control -streaming, SMTP, DNS |
|
|
UDP Checksum |
-detects error -sender adds 16-bit ints of content, wraps overflow, takes one's complement -receiver checks against checksum |
|
|
RDT 1.0 |
-assume underlying channel reliable FSM for sender/receiver -> wait for call and thats it |
|
|
RDT 2.0 |
Adds bit errors -ACKs and NAKs -can't deal w/ corrupted ACKs/NAKs, needs addition Stop and Wait -> sender sends one packet, waits for response |
|
|
RDT 2.1 |
sender adds seq # to pkt, twice as many states Receiver checks if packet is duplicate |
|
|
RDT 2.2 |
No NAKs, send ACK for last good packet received |
|
|
RDT 3.0 |
-assume channel can lose packets -timeout if no ACK received in time |
|
|
Stop-and-Wait + Performance |
Sends one packet at a time dtrans = L/R Utilization U = L/R ----------------- RTT + L/R .00027 in example |
|
|
Pipelined Protocols |
Sender allows multiple "in-flight" yet-to-be-ACKed packets Go-Back-N, Selective Repeat |
|
|
Selective Repeat |
Sender can have N unACKed packets Receiver acks indiv. packets Sender has timer for each unacked packet -> only retransmits that at timeout Sender movies base to next unACKed seq # when it receives an ACK Buffers out of order Send_base, nextseqnum, rcv_base |
|
|
Go-Back-N |
Sender has window size N of consecutive unACKed packets -cumulative ACK -timer for oldest packet -> timeout resend all unACKed packets -discards out of order, reACKS last ACKS |
|
|
TCP Overview |
-point to point (one sender/receiver) -reliable, in-order -pipelined -send/rcv buffers -full duplex -> bi directional, MSS (max segment size) -connection oriented -> handshake flow control -> sender won't overwhelm receiver |
|
|
TCP Seq #s and ACKS |
Seq #: byte stram # of first byte in segment's data ACK: seq # of next expected byte, cumulative Out-of-order up to implementor |
|
|
TCP RTT/ Timeout |
-> Estimated RTT, DevRTT, Timeout Interval -use SampleRTT for initial transmission to ACK receipt -> too short = premature timeout -> too long = slow reaction to segment loss |
|
|
EstimatedRTT |
(1-a)*EstimatedRTT + a*SampleRTT EWMA (Exponential Weighted Moving Average) a = .125 usually |
|
|
DevRTT |
(1-B)*DevRTT + B*abs(SampleRTT - Estimated RTT) estimate of how much Sample differs from Estimated B = .25 typically |
|
|
Timeout Interval |
EstimatedRTT + 4*DevRTT |
|
|
TCP RDT |
-pipelined segments -cumulative ACK -single retrans timer -> timeout, duplicate ACKs Timeout: retransmit segment that caused Receive ACK: update what has been ACKed |
|
|
TCP ACK generation |
In-order, all data already ACKed up to n -> delayed ACK, wait 500 ms for next seg, if none, send ACK In-order while other segment has ACK pending -> send both at once Out-of-order segment -> send duplicate ACK FIlls Gap segment -> send ACK immediately |
|
|
Fast Retransmit |
Timeout period can be long Detect lost segments w/ 3 duplicated ACKS -resend before timer expires |
|
|
TCP Flow Control |
sender won't overflow receivers buffer -receiver has buffer, spare room = receive window rwnd = RcvBuffer - [LastByteRcvd - LastByteRead] Sender limits unAcked data to RcvWindow |
|
|
TCP Connection Management - Open |
Three Way Handshake to initialize TCP vars -> seq #s/buffers/flow control 1) client sends SYN segment w/ initial seq # 2) server replies w/ SYNACK, allocates buffers, specifies own initial seq# 3) Client replies w/ ACK, which may contain data |
|
|
TCP Connection Management - Close |
1) Client closes socket, sends TCP FIN control 2) Server sends ACK, closes socket and sends own FIN control segment 3) Client replies to server FIN w/ ACK -> timed wait 4) Server receives ACK, connection is closed |
|
|
Principles of Congestion Control |
Congestion: too many sources sending too much data too fast for network to handle -lost packets, long delays |
|
|
Causes/Costs of Congestion -> 1st Scenario |
two senders, two receivers, one router, infinite buffers, link capacity R no retransmission at most R/2 throughput per connection, large delays as arrival rate approaches capacity |
|
|
Causes/Costs of Congestion -> 2nd Scenario |
one router, finite buffers -retransmission of timed-out packet -> lambda(in) = lambda(out) ->w/ retransmissions lambda'(in) >= lambda(in) Idealiziation: known loss of packets Realistic: duplicates -> more work for "goodput" |
|
|
Causes/Costs of Congestion -> 3rd Scenario |
four senders, multihop path, timeout/retransmit As lambda(in) and lambda'(in) increase, other packets in queue are dropped, other throughput -> 0 |
|
|
Approaches to Congestion Control |
End-end -> no network feedback, infer from observed loss/delay, TCP network-assisted -> routers provide feedback and explicit rate (ATM) |
|
|
ATM ABR |
ABR: Available bit rate -elastic service -Resource Management (RM) cells: ->send by sender between data cells ->set bits by switches (No Increase (NI) for mild, Congestion INdication (CI) for severe) Two-byte ER (explicit rate) field in RM |
|
|
TCP Congestion Control |
-adds congestion window -effective window is smaller of rwnd (flow control) and cwnd (congestion control) -changes in congestion window size -> slow increase, quick decrease LastByteSent - LastByteACked <= window Rate = cwnd/RTT |
|
|
TCP Congestion Control Mechanisms |
AIMD -> grow cwnd slow start -> startup Conservative after timeouts |
|
|
AIMD |
Additive Increase, Multiplicative Decrease -increase cwnd probing for usable bandwidth until loss -increase cwnd by 1 MSS every RTT -cut cwnd by 50% after loss |
|
|
Why AIMD? |
Fairness -> K sessions share same link, each should have rate R/K |
|
|
TCP Congestion Control Algorithms |
slow start congestion avoidance fast retransmit/recovery retransmission upon timeout |
|
|
Slow Start |
cwnd starts at 1MSS increase exponentially until cwnd reaches slow-start-threshold ssthresh (double every RTT) |
|
|
Congestion Avoidance |
increase cwnd by 1 MSS per RTT until loss cwnd > ssthresh |
|
|
Detecting Loss |
through duplicate ACKs -> fast retransmit/recovery (mult. decrease) through retransmission timeout (reset everything) |
|
|
Fast Retransmit/Fast Recovery |
Fast retransmit -> detect loss at 3 dup. ACKS, sshtrhesh = Max(2*MSS, cwnd/2 ), cwnd = ssthresh + 3*MSS, retransmit lost packet Fast Recovery: increased cwnd 1 MSS every dup. ACK At new ACK, cwnd = ssthresh |
|
|
Retransmission Timeout |
ssthresh = max(cwnd/2, 2*MSS) cwnd = 1 MSS retransmit Reset because a heavy loss was detected |
|
|
TCP throughpt |
Window size W where loss occurs avg size is 3/4 W avg throughput is 3/4 W/RTT |
|
|
TCP futures |
1500 byte segments, 100 ms RTT, 10 GBps throughput, needs W = 83,333 in-flight segments TCP Throughput in terms of loss prob = 1.22 * MSS --------------------- RTT sqrt(L) |
