Question? Leave a message!




Network Services and Applications

Network Services and Applications
Network Services and Applications EECS 489 Computer Networks http://www.eecs.umich.edu/courses/eecs489/w07 Z. Morley Mao Monday Jan 22, 2007 1 Mao W07 Acknowledgement: Some slides taken from Kurose&Ross and Katz&Stoicaƒƒƒ Adminstrivia Homework 1 is due tomorrow – 1/23 PA1 will be available tomorrow as well - A simplified Web server - You need to find a project partner for this assignment Reading assignment for this week - Chapter 3 of the book - You should have read Chapter 1 and 2. 2 Mao W07ƒƒƒƒƒ Recap from last lecture Nagle’s algorithm - By default it is on: combines small packets into larger ones before sending to reduce header overhead - TCP_NODELAY socket option disables it Internet routing is - policy driven, not load-sensitive, generally not QoS- based Email is not secure by default - Using HTTPS Web-based interface only provides one hop security from mail client to the mail server, not end- to-end security Port knocking allows a server to hide its port - Reduces overhead in rejecting illegitimate requests Akamai is a commercial company providing Web caching service - Using DNS-based redirection 3 Mao W07ƒƒƒƒ Nodal delay d=d+d+d+d nodal proc queue trans prop d = processing delay proc - typically a few microsecs or less d = queuing delay queue - depends on congestion d = transmission delay trans - = L/R, significant for low-speed links d = propagation delay prop - a few microsecs to hundreds of msecs 4 Mao W07ƒƒƒ ƒƒƒ Queueing delay (revisited) R=link bandwidth (bps) L=packet length (bits) a=average packet arrival rate traffic intensity = La/R La/R 0: average queueing delay small La/R - 1: delays become large La/R 1: more “work” arriving than can be serviced, average delay infinite 5 Mao W07ƒƒ “Real” Internet delays and routes What do “real” Internet delay & loss look like? Traceroute program: provides delay measurement from source to router along end- end Internet path towards destination. For all i: - sends three packets that will reach router i on path towards destination - router i will return packets to sender - sender times interval between transmission and reply. 3 probes 3 probes 3 probes 6 Mao W07ƒƒ Traceroute: Measuring the Forwarding Path Time-To-Live field in IP packet header - Source sends a packet with a TTL of n - Each router along the path decrements the TTL - “TTL exceeded” sent when TTL reaches 0 Traceroute tool exploits this TTL behavior Time exceeded TTL=1 destination source TTL=2 Send packets with TTL=1, 2, 3, … and record source of “time exceeded” message 7 Mao W07“Real” Internet delays and routes traceroute: gaia.cs.umass.edu to www.eurecom.fr Three delay measements from gaia.cs.umass.edu to cs-gw.cs.umass.edu 1 cs-gw (128.119.240.254) 1 ms 1 ms 2 ms 2 border1-rt-fa5-1-0.gw.umass.edu (128.119.3.145) 1 ms 1 ms 2 ms 3 cht-vbns.gw.umass.edu (128.119.3.130) 6 ms 5 ms 5 ms 4 jn1-at1-0-0-19.wor.vbns.net (204.147.132.129) 16 ms 11 ms 13 ms 5 jn1-so7-0-0-0.wae.vbns.net (204.147.136.136) 21 ms 18 ms 18 ms 6 abilene-vbns.abilene.ucaid.edu (198.32.11.9) 22 ms 18 ms 22 ms 7 nycm-wash.abilene.ucaid.edu (198.32.8.46) 22 ms 22 ms 22 ms trans-oceanic 8 62.40.103.253 (62.40.103.253) 104 ms 109 ms 106 ms link 9 de2-1.de1.de.geant.net (62.40.96.129) 109 ms 102 ms 104 ms 10 de.fr1.fr.geant.net (62.40.96.50) 113 ms 121 ms 114 ms 11 renater-gw.fr1.fr.geant.net (62.40.103.54) 112 ms 114 ms 112 ms 12 nio-n2.cssi.renater.fr (193.51.206.13) 111 ms 114 ms 116 ms 13 nice.cssi.renater.fr (195.220.98.102) 123 ms 125 ms 124 ms 14 r3t2-nice.cssi.renater.fr (195.220.98.110) 126 ms 126 ms 124 ms 15 eurecom-valbonne.r3t2.ft.net (193.48.50.54) 135 ms 128 ms 133 ms 16 194.214.211.25 (194.214.211.25) 126 ms 128 ms 126 ms 17 means no reponse (probe lost, router not replying) 18 19 fantasia.eurecom.fr (193.55.113.142) 132 ms 128 ms 136 ms 8 Mao W07ƒƒƒ Packet loss queue (aka buffer) preceding link in buffer has finite capacity when packet arrives to full queue, packet is dropped (aka lost) lost packet may be retransmitted by previous node, by source end system, or not retransmitted at all 9 Mao W07ƒ Protocol “Layers” Networks are complex many “pieces”: -hosts Question: -routers Is there any hope of organizing structure of - links of various network? media - applications Or at least our discussion -protocols of networks? - hardware, software 10 Mao W07ƒ Organization of air travel ticket (complain) ticket (purchase) baggage (claim) baggage (check) gates (unload) gates (load) runway landing runway takeoff airplane routing airplane routing airplane routing a series of steps 11 Mao W07Layering of airline functionality ticket (purchase) ticket (complain) ticket baggage (check) baggage (claim baggage gate gates (load) gates (unload) takeoff/landing runway (takeoff) runway (land) airplane routing airplane routing airplane routing airplane routing airplane routing departure intermediate air-traffic arrival airport control centers airport Layers: each layer implements a service - via its own internal-layer actions - relying on services provided by layer below 12 Mao W07ƒƒƒ Why layering? Dealing with complex systems: explicit structure allows identification, relationship of complex system’s pieces - layered reference model for discussion modularization eases maintenance, updating of system - change of implementation of layer’s service transparent to rest of system - e.g., change in gate procedure doesn’t affect rest of system layering considered harmful? 13 Mao W07ƒƒƒƒƒ Internet protocol stack application: supporting network applications application - FTP, SMTP, STTP transport: host-host data transfer transport - TCP, UDP network: routing of datagrams from network source to destination - IP, routing protocols link link: data transfer between neighboring network elements physical - PPP, Ethernet physical: bits “on the wire” 14 Mao W07source message M application Encapsulation segment H M transport t datagram H H M network n t H H H frame M link l n t physical H H H M link H H H M l n t l n t physical switch destination H H M H H network M n t n t H H H M H H H link M M l n t l n t application physical H M transport t H H M network n t router H H H M link l n t physical 15 Mao W07IP Packet Structure usually 20 bytes usually IPv4 4-bit 8-bit 4-bit 16-bit Total Length (Bytes) Header Type of Service Version Length (TOS) 3-bit 16-bit Identification 13-bit Fragment Offset Flags 20-byte 8-bit Time to 20-byte fragments 8-bit Protocol 16-bit Header Checksum Header Header Live (TTL) 32-bit Source IP Address 32-bit Destination IP Address Options (if any) error check Payload header 16 Mao W07Layering in the IP Protocols Telnet HTTP FTP DNS RTP Transmission Control User Datagram Protocol (TCP) Protocol (UDP) Internet Protocol Ethernet SONET ATM 17 Mao W07ƒƒ Application-Layer Protocols Messages exchanged between applications - Syntax and semantics of the messages between hosts - Tailored to the specific application (e.g., Web, e-mail) - Messages transferred over transport connection (e.g., TCP) Popular application-layer protocols - Telnet, FTP, SMTP, NNTP, HTTP, … GET /index.html HTTP/1.1 Client Server HTTP/1.1 200 OK 18 Mao W07Example: Many Steps in Web Download st Browser DNS TCP 1 byte Last byte cache resolution open response response Sources of variability of delay • Browser cache hit/miss, need for cache revalidation • DNS cache hit/miss, multiple DNS servers, errors • Packet loss, high RTT, server accept queue • RTT, busy server, CPU overhead (e.g., CGI script) • Response size, receive buffer size, congestion • … downloading embedded image(s) on the page 19 Mao W07ƒƒƒ Domain Name System (DNS) Properties of DNS - Hierarchical name space divided into zones - Translation of names to/from IP addresses - Distributed over a collection of DNS servers Client application - Extract server name (e.g., from the URL) - Invoke system call to trigger DNS resolver code - E.g., gethostbyname() on “www.foo.com” Server application - Extract client IP address from socket - Optionally invoke system call to translate into name - E.g., gethostbyaddr() on “12.34.158.5” 20 Mao W07Domain Name System unnamed root zw arpa com edu org ac uk generic domains country domains in- bar ac addr west east 12 cam foo my 34 usr my.east.bar.edu usr.cam.ac.uk 56 12.34.56.0/24 21 Mao W07DNS Resolver and Local DNS Server Root server 3 4 Application DNS cache 5 Top-level DNS query domain server 1 10 6 Local DNS 2 server DNS resolver 7 9 DNS response 8 Second-level domain server Caching based on a time-to-live (TTL) assigned by the DNS server responsible for the host name to reduce latency in DNS translation. 22 Mao W07ƒƒƒƒƒ Web and HTTP First some jargon Web page consists of objects Object can be HTML file, JPEG image, Java applet, audio file,… Web page consists of base HTML-file which includes several referenced objects Each object is addressable by a URL Example URL: www.someschool.edu/someDept/pic.gif host name path name Have you heard of Google’s “PageRank”? Is it susceptible to spoofing? 23 Mao W07ƒƒƒƒ HTTP request HTTP response HTTP overview HTTP: hypertext transfer protocol Web’s application layer PC running protocol Explorer client/server model - client: browser that requests, receives, “displays” Web objects Server running - server: Web server Apache Web sends objects in server response to requests HTTP 1.0: RFC 1945 Mac running HTTP 1.1: RFC 2068 Navigator 24 Mao W07 HTTP request H TP r s o s T e p n eƒ ƒƒ ƒƒƒƒ HTTP overview (continued) HTTP is “stateless” Uses TCP: server maintains no client initiates TCP information about connection (creates socket) past client requests to server, port 80 server accepts TCP aside connection from client Protocols that maintain “state” are HTTP messages complex (application-layer protocol past history (state) must be messages) exchanged maintained between browser (HTTP if server/client crashes, their client) and Web server views of “state” may be (HTTP server) inconsistent, must be reconciled TCP connection closed Is it better to have a stateful protocol? 25 Mao W07ƒƒ ƒƒ HTTP connections Nonpersistent HTTP Persistent HTTP At most one object is Multiple objects can sent over a TCP be sent over a single connection. TCP connection between client and HTTP/1.0 uses server. nonpersistent HTTP HTTP/1.1 uses persistent connections in default mode What is the advantage of persistent HTTP? Who needs to support this? Server or client? 26 Mao W07Nonpersistent HTTP Suppose user enters URL (contains text, www.someSchool.edu/someDepartment/home.index references to 10 jpeg images) 1a. HTTP client initiates a TCP 1b. HTTP server at host connection to HTTP server www.someSchool.edu waiting (process) at www.someSchool.edu for TCP connection at port 80. on port 80 “accepts” connection, notifying client 2. HTTP client sends HTTP 3. HTTP server receives request request message (containing message, forms response URL) into TCP connection message containing requested socket. Message indicates that object, and sends message into client wants object its socket someDepartment/home.index time 27 Mao W07Nonpersistent HTTP (cont.) 4. HTTP server closes TCP connection. 5. HTTP client receives response message containing html file, displays html. Parsing html file, finds 10 referenced jpeg objects time 6. Steps 1-5 repeated for each of 10 jpeg objects 28 Mao W07ƒƒƒ Response time modeling Definition of RTT: time to send a small packet to travel from client to server initiate TCP and back. connection RTT Response time: request one RTT to initiate TCP file time to connection RTT transmit one RTT for HTTP request file file and first few bytes of received HTTP response to return file transmission time time time total = 2RTT+transmit time 29 Mao W07ƒƒƒƒƒ ƒƒƒƒƒ Persistent HTTP Persistent without pipelining: Nonpersistent HTTP issues: client issues new request requires 2 RTTs per object only when previous OS must work and allocate response has been received host resources for each TCP one RTT for each referenced connection object but browsers often open Persistent with pipelining: parallel TCP connections to fetch referenced objects default in HTTP/1.1 Persistent HTTP client sends requests as soon as it encounters a server leaves connection referenced object open after sending responses as little as one RTT for all subsequent HTTP messages the referenced objects between same client/server are sent over connection Several dimensions to help speed up: Persistent connections, pipelining, parallel connections 30 Mao W07ƒƒ HTTP request message two types of HTTP messages: request, response HTTP request message: - ASCII (human-readable format) request line (GET, POST, GET /somedir/page.html HTTP/1.1 HEAD commands) Host: www.someschool.edu User-agent: Mozilla/4.0 header Connection: close lines Accept-language:fr Carriage return, (extra carriage return, line feed) line feed indicates end of message 31 Mao W07HTTP request message: general format 32 Mao W07ƒƒ ƒƒ Uploading form input Post method: Web page often URL method: includes form input Uses GET method Input is uploaded to server in entity body Input is uploaded in URL field of request line: www.somesite.com/animalsearch?monkeys&banana 33 Mao W07ƒƒƒ ƒƒƒ Method types HTTP/1.0 HTTP/1.1 GET GET, POST, HEAD POST PUT - uploads file in entity body HEAD to path specified in URL - asks server to leave field requested object out of response DELETE - deletes file specified in the URL field 34 Mao W07HTTP response message status line (protocol HTTP/1.1 200 OK status code Connection close status phrase) Date: Thu, 06 Aug 1998 12:00:15 GMT Server: Apache/1.3.0 (Unix) header Last-Modified: Mon, 22 Jun 1998 …... lines Content-Length: 6821 Content-Type: text/html data, e.g., data data data data data ... requested HTML file 35 Mao W07HTTP response status codes In first line in server-client response message. A few sample codes: 200 OK - request succeeded, requested object later in this message 301 Moved Permanently - requested object moved, new location specified later in this message (Location:) 400 Bad Request - request message not understood by server 404 Not Found - requested document not found on this server 505 HTTP Version Not Supported 36 Mao W07User-server state: cookies Many major Web sites Example: use cookies - Susan access Internet always from same PC Four components: - She visits a specific e- 1) cookie header line in commerce site for first the HTTP response time message - When initial HTTP 2) cookie header line in requests arrives at site, HTTP request message site creates a unique 3) cookie file kept on ID and creates an entry user’s host and in backend database managed by user’s for ID browser 4) back-end database at Web site 37 Mao W07entry in backend database Cookies: keeping “state” (cont.) client server usual http request msg Cookie file server usual http response + creates ID ebay: 8734 Set-cookie: 1678 1678 for user Cookie file usual http request msg cookie- amazon: 1678 cookie: 1678 ebay: 8734 specific usual http response msg action one week later: usual http request msg Cookie file cookie- cookie: 1678 amazon: 1678 spectific ebay: 8734 usual http response msg action 38 Mao W07 access accessƒƒƒƒ ƒƒƒƒ Cookies (continued) aside Cookies and privacy: What cookies can bring: cookies permit sites to authorization learn a lot about you shopping carts you may supply name recommendations and e-mail to sites user session state (Web search engines use e-mail) redirection & cookies to learn yet more advertising companies obtain info across sites Do cookies compromise security? Can it be used for authentication? 39 Mao W07ƒƒ HTTP request HTTP response Web caches (proxy server) Goal: satisfy client request without involving origin server user sets browser: origin Web accesses via server cache Proxy browser sends all server HTTP requests to client cache - object in cache: cache returns object - else cache requests object from origin server, then returns object to client client origin server Your Web request may be intercepted 40 Mao W07 using a transparent TCP proxy HTTP request HTTP response HTTP request HTTP responseƒƒƒ ƒƒ More about Web caching Cache acts as both Why Web caching? client and server Reduce response time for client request. Typically cache is Reduce traffic on an installed by ISP institution’s access link. (university, company, Internet dense with caches residential ISP) enables “poor” content providers to effectively deliver content (but so does P2P file sharing) 41 Mao W07ƒƒƒƒƒƒ Caching example Assumptions origin average object size = 100,000 bits servers avg. request rate from institution’s public browsers to origin servers = 15/sec Internet delay from institutional router to any origin server and back to router = 2 sec 1.5 Mbps Consequences access link utilization on LAN = institutional 1.5Mbps/10Mbps = 15% network 10 Mbps LAN utilization on access link = 100% total delay = Internet delay + access delay + LAN delay = 2 sec + minutes + milliseconds institutional cache 42 Mao W07ƒƒƒƒƒ Caching example (cont) origin Possible solution servers increase bandwidth of public access link to, say, 10 Internet Mbps Consequences 10 Mbps utilization on LAN = 15% access link utilization on access link = 15% institutional Total delay = Internet delay + network 10 Mbps LAN access delay + LAN delay = 2 sec + msecs + msecs often a costly upgrade institutional cache 43 Mao W07ƒƒƒƒƒ Caching example (cont) origin servers Install cache suppose hit rate is 0.4 public Internet Consequence 40% requests will be satisfied almost immediately 60% requests satisfied by origin 1.5 Mbps server access link utilization of access link reduced institutional to 60%, resulting in negligible network 10 Mbps LAN delays (say 10 msec) total avg delay = Internet delay + access delay + LAN delay = .6(2.01) secs + milliseconds 1.4 secs institutional cache 44 Mao W07ƒƒƒ Conditional GET server cache Goal: don’t send object if cache has up-to-date cached HTTP request msg version If-modified-since: object date cache: specify date of cached not copy in HTTP request modified If-modified-since: HTTP response HTTP/1.0 date 304 Not Modified server: response contains no object if cached copy is up-to- date: HTTP request msg HTTP/1.0 304 Not If-modified-since: date object Modified modified HTTP response HTTP/1.0 200 OK data 45 Mao W07ƒƒƒƒ FTP: the file transfer protocol file transfer FTP FTP FTP user client server interface user remote file local file at host system system transfer file to/from remote host client/server model - client: side that initiates transfer (either to/from remote) - server: remote host ftp: RFC 959 ftp server: port 21 46 Mao W07ƒƒƒ ƒƒƒƒƒ FTP: separate control, data connections TCP control connection port 21 FTP client contacts FTP server at port 21, specifying TCP as transport protocol TCP data connection Client obtains authorization FTP FTP port 20 over control connection client server Client browses remote directory by sending Server opens a second TCP data commands over control connection to transfer another file. connection. Control connection: “out of band” When server receives a FTP server maintains “state”: command for a file transfer, current directory, earlier the server opens a TCP authentication data connection to client After transferring one file, server closes connection. What’s the advantage of an out-of-band control channel? 47 Mao W07ƒƒƒƒƒ ƒƒƒƒƒƒ FTP commands, responses Sample commands: Sample return codes sent as ASCII text over status code and phrase control channel (as in HTTP) USER username 331 Username OK, password required PASS password 125 data connection LIST return list of file in already open; current directory transfer starting RETR filename 425 Can’t open data retrieves (gets) file connection 452 Error writing STOR filename stores file (puts) file onto remote host 48 Mao W07ƒƒƒƒƒƒƒ outgoing Electronic Mail message queue user mailbox user Three major components: agent user agents mail user server mail servers agent simple mail transfer protocol: SMTP mail SMTP server user agent User Agent SMTP a.k.a. “mail reader” SMTP composing, editing, reading user mail mail messages agent server e.g., Eudora, Outlook, elm, Netscape Messenger user outgoing, incoming messages agent stored on server user agent 49 Mao W07ƒƒƒ Electronic Mail: mail servers user Mail Servers agent mailbox contains incoming mail user messages for user server agent message queue of SMTP mail outgoing (to be sent) mail server user messages agent SMTP SMTP protocol between mail servers to send email SMTP messages user mail agent - client: sending mail server server user - “server”: receiving mail agent server user agent Where can we find out the mail servers for a domain? 50 Mao W07ƒƒƒƒƒ Electronic Mail: SMTP RFC 2821 uses TCP to reliably transfer email message from client to server, port 25 direct transfer: sending server to receiving server three phases of transfer - handshaking (greeting) - transfer of messages -closure command/response interaction - commands: ASCII text - response: status code and phrase messages must be in 7-bit ASCII 51 Mao W07Scenario: Alice sends message to Bob 4) SMTP client sends Alice’s 1) Alice uses UA to compose message over the TCP message and “to” connection bobsomeschool.edu 5) Bob’s mail server places the 2) Alice’s UA sends message to message in Bob’s mailbox her mail server; message 6) Bob invokes his user agent to placed in message queue read message 3) Client side of SMTP opens TCP connection with Bob’s mail server 1 mail mail user server user server agent 2 agent 6 3 4 5 52 Mao W07Sample SMTP interaction S: 220 hamburger.edu C: HELO crepes.fr S: 250 Hello crepes.fr, pleased to meet you C: MAIL FROM: alicecrepes.fr S: 250 alicecrepes.fr... Sender ok C: RCPT TO: bobhamburger.edu S: 250 bobhamburger.edu ... Recipient ok C: DATA S: 354 Enter mail, end with "." on a line by itself C: Do you like ketchup? C: How about pickles? C: . S: 250 Message accepted for delivery C: QUIT S: 221 hamburger.edu closing connection 53 Mao W07ƒƒƒ Try SMTP interaction for yourself: telnet servername 25 see 220 reply from server enter HELO, MAIL FROM, RCPT TO, DATA, QUIT commands above lets you send email without using email client (reader) 54 Mao W07ƒƒƒƒƒ ƒƒƒ SMTP: final words SMTP uses persistent Comparison with HTTP: connections HTTP: pull SMTP requires SMTP: push message (header & both have ASCII body) to be in 7-bit command/response ASCII interaction, status codes SMTP server uses HTTP: each object CRLF.CRLF to encapsulated in its own determine end of response msg message SMTP: multiple objects sent in multipart msg 55 Mao W07ƒƒ Mail message format SMTP: protocol for exchanging email msgs header blank RFC 822: standard for text line message format: header lines, e.g., -To: -From: body -Subject: different from SMTP commands body - the “message”, ASCII characters only 56 Mao W07ƒƒ Message format: multimedia extensions MIME: multimedia mail extension, RFC 2045, 2056 additional lines in msg header declare MIME content type From: alicecrepes.fr MIME version To: bobhamburger.edu Subject: Picture of yummy crepe. method used MIME-Version: 1.0 to encode data Content-Transfer-Encoding: base64 Content-Type: image/jpeg multimedia data type, subtype, base64 encoded data ..... parameter declaration ......................... ......base64 encoded data encoded data 57 Mao W07ƒƒ Mail access protocols SMTP SMTP access user user agent protocol agent receiver’s mail sender’s mail server server SMTP: delivery/storage to receiver’s server Mail access protocol: retrieval from server - POP: Post Office Protocol RFC 1939 • authorization (agent server) and download - IMAP: Internet Mail Access Protocol RFC 1730 • more features (more complex) • manipulation of stored msgs on server - HTTP: Hotmail , Yahoo Mail, etc. 58 Mao W07ƒƒƒƒƒƒ POP3 protocol S: +OK POP3 server ready authorization phase C: user bob client commands: S: +OK - user: declare username C: pass hungry S: +OK user successfully logged on - pass: password server responses C: list S: 1 498 - +OK S: 2 912 - -ERR S: . transaction phase, client: C: retr 1 S: message 1 contents list: list message numbers S: . retr: retrieve message by C: dele 1 number C: retr 2 dele: delete S: message 1 contents quit S: . C: dele 2 C: quit S: +OK POP3 server signing off 59 Mao W07ƒƒƒ ƒƒƒƒ POP3 (more) and IMAP More about POP3 IMAP Previous example uses Keep all messages in “download and delete” one place: the server mode. Allows user to organize Bob cannot re-read e- messages in folders mail if he changes client IMAP keeps user state “Download-and-keep”: across sessions: copies of messages on - names of folders and different clients mappings between message IDs and folder POP3 is stateless name across sessions 60 Mao W07ƒƒ Discussions Why do we have so much spam? - How would you design the email system to prevent spam? How does anonymous email work? 61 Mao W07ƒƒƒ IP Addressing 32-bit number in dotted-quad notation (12.34.158.5) Divided into network & host portions (left and right) 8 12.34.158.0/24 is a 24-bit prefix with 2 addresses 12 34 158 5 00001100 00100010 10011110 00000101 Network (24 bits) Host (8 bits) 62 Mao W07ƒƒ Some History: Why Dotted-Quad Notation? In the olden days… - Class A: 0 • Very large /8 blocks (e.g., MIT has 18.0.0.0/8) - Class B: 10 • Large /16 blocks (e.g,. UM has 141.213.0.0/16) - Class C: 110 • Small /24 blocks (e.g., AT&T Labs has 192.20.225.0/24) - Class D: 1110 • Multicast groups - Class E: 11110 • Reserved for future use (sounds a bit scary…) And then, address space became scarce… 63 Mao W07Classless Inter-Domain Routing (CIDR) Use two 32-bit numbers to represent a network. Network number = IP address + Mask IP Address : 12.4.0.0 IP Mask: 255.254.0.0 Address 00001100 00000100 00000000 00000000 Mask 11111111 11111110 00000000 00000000 Network Prefix for hosts Usually written as 12.4.0.0/15 64 Mao W07ƒ CIDR = Hierarchy in Address Allocation Prefixes are key to Internet scalability - Address allocation by ARIN/RIPE/APNIC and by ISPs - Routing protocols and packet forwarding based on prefixes - Today, routing tables contain 150,000-200,000 prefixes 12.0.0.0/16 : 12.1.0.0/16 12.3.0.0/24 12.2.0.0/16 12.3.1.0/24 : : 12.3.0.0/16 : : : 12.0.0.0/8 12.3.254.0/24 : 12.253.0.0/19 12.253.32.0/19 12.253.64.0/19 : 12.253.0.0/16 12.253.96.0/19 12.254.0.0/16 12.253.128.0/19 12.253.160.0/19 65 Mao W07 12.253.192.0/19ƒƒ Figuring Out Who Owns an Address Address registries - Public record of address allocations - ISPs should update when giving addresses to customers - However, records are notoriously out-of-date Ways to query - UNIX: “whois –h whois.arin.net 128.112.136.35” - http://www.arin.net/whois/ - http://www.geektools.com/whois.php -… 66 Mao W07Example Output for 141.213.4.5 (galileo.eecs.umich.edu) OrgName: University of Michigan OrgID: UNIVER-118 Address: IT Communications Services Address: 4251 Plymouth Road City: Ann Arbor StateProv: MI PostalCode: 48105-2785 Country: US NetRange: 141.213.0.0 - 141.213.255.255 CIDR: 141.213.0.0/16 NetName: UMNET3 NetHandle: NET-141-213-0-0-1 Parent: NET-141-0-0-0-0 NetType: Direct Assignment NameServer: SRVR8.ENGIN.UMICH.EDU NameServer: SRVR7.ENGIN.UMICH.EDU NameServer: DNS2.ITD.UMICH.EDU 67 Mao W07There is more… Comment: Abuse contact for 141.213.128.0/17 is abuseumich.edu. Comment: For DMCA info see http://www.umich.edu/itua/copyright/ RegDate: 1990-08-02 Updated: 2003-03-27 AbuseHandle: CEAC-ARIN AbuseName: College of Engineering Abuse Contact AbusePhone: +1-734-936-2486 AbuseEmail: abuseengin.umich.edu TechHandle: PMK5-ARIN TechName: Killey, Paul M. TechPhone: +1-734-763-4910 TechEmail: paulengin.umich.edu OrgTechHandle: UA11-ORG-ARIN OrgTechName: UMnet Administration OrgTechPhone: +1-734-647-4200 OrgTechEmail: umnet-adminumich.edu 68 Mao W07ƒƒ Longest Prefix Match Forwarding Forwarding tables in IP routers - Maps each IP prefix to next-hop link(s) Destination-based forwarding - Packet has a destination address - Router identifies longest-matching prefix - Cute algorithmic problem: very fast lookups forwarding table 4.0.0.0/8 destination 4.83.128.0/17 12.34.158.5 outgoing link 12.0.0.0/8 Serial0/0.1 12.34.158.0/24 126.255.103.0/24 69 Mao W07ƒƒƒƒ How are packets forwarded? Routers have forwarding tables - Map prefix to outgoing link(s) Entries can be statically configured - E.g., “map 12.34.158.0/24 to Serial0/0.1” But, this doesn’t adapt - To failures - To new equipment - To the need to balance load -… That is where routing protocols come in… more on this in the next lectures 70 Mao W07ƒƒƒƒ Discussions IP address space scarcity - What can we do about it? Increased IP address fragmentation Does an IP address identify the actual user? How does one achieve mobility while maintaining the same IP address? 71 Mao W07ƒƒ DNS: Domain Name System Domain Name System: People: many identifiers: distributed database - SSN, name, passport implemented in hierarchy of Internet hosts, routers: many name servers - IP address (32 bit) - used application-layer protocol host, for addressing routers, name servers to datagrams communicate to resolve names (address/name translation) - “name”, e.g., ww.yahoo.com - used by - note: core Internet function, humans implemented as application- layer protocol - complexity at network’s “edge” 72 Mao W07ƒƒƒƒ ƒƒƒƒ DNS Why not centralize DNS? DNS services single point of failure Hostname to IP address translation traffic volume Host aliasing distant centralized database - Canonical and alias names maintenance Mail server aliasing Load distribution doesn’t scale - Replicated Web servers: set of IP addresses for one canonical name 73 Mao W07ƒƒƒ Distributed, Hierarchical Database Root DNS Servers org DNS servers edu DNS servers com DNS servers poly.edu umass.edu pbs.org yahoo.com amazon.com DNS serversDNS servers DNS servers DNS servers DNS servers st Client wants IP for www.amazon.com; 1 approx: Client queries a root server to find com DNS server Client queries com DNS server to get amazon.com DNS server Client queries amazon.com DNS server to get IP address for www.amazon.com 74 Mao W07ƒƒ DNS: Root name servers contacted by local name server that can not resolve name root name server: - contacts authoritative name server if name mapping not known - gets mapping - returns mapping to local name server a Verisign, Dulles, VA c Cogent, Herndon, VA (also Los Angeles) d U Maryland College Park, MD k RIPE London (also Amsterdam, g US DoD Vienna, VA Frankfurt) i Autonomica, Stockholm (plus 3 h ARL Aberdeen, MD other locations) j Verisign, ( 11 locations) m WIDE Tokyo e NASA Mt View, CA f Internet Software C. Palo Alto, 13 root name servers CA (and 17 other locations) worldwide b USC-ISI Marina del Rey, CA l ICANN Los Angeles, CA 75 Mao W07ƒƒ TLD and Authoritative Servers Top-level domain (TLD) servers: responsible for com, org, net, edu, etc, and all top-level country domains uk, fr, ca, jp. - Network solutions maintains servers for com TLD Authoritative DNS servers: organization’s DNS servers, providing authoritative hostname to IP mappings for organization’s servers (e.g., Web and mail). - Can be maintained by organization or service provider 76 Mao W07ƒƒƒ Local Name Server Does not strictly belong to hierarchy Each ISP (residential ISP, company, university) has one. - Also called “default name server” When a host makes a DNS query, query is sent to its local DNS server - Acts as a proxy, forwards query into hierarchy. 77 Mao W07ƒ root DNS server Example 2 Host at cis.poly.edu wants 3 TLD DNS server IP address for 4 gaia.cs.umass.edu 5 local DNS server dns.poly.edu 6 7 1 8 authoritative DNS server dns.cs.umass.edu requesting host cis.poly.edu gaia.cs.umass.edu 78 Mao W07ƒƒƒƒ Recursive queries root DNS server recursive query: puts burden of name 2 3 resolution on contacted name server 6 7 heavy load? TLD DNS server iterated query: contacted server replies local DNS server with name of server to 4 dns.poly.edu 5 contact “I don’t know this name, 1 8 but ask this server” authoritative DNS server dns.cs.umass.edu requesting host cis.poly.edu gaia.cs.umass.edu 79 Mao W07ƒƒ DNS: caching and updating records once (any) name server learns mapping, it caches mapping - cache entries timeout (disappear) after some time - TLD servers typically cached in local name servers • Thus root name servers not often visited update/notify mechanisms under design by IETF - RFC 2136 - http://www.ietf.org/html.charters/dnsind-charter.html 80 Mao W07ƒ ƒ ƒ ƒ DNS records DNS: distributed db storing resource records (RR) RR format: (name, value, type, ttl) Type=A Type=CNAME - name is hostname - name is alias name for some “cannonical” (the real) name - value is IP address www.ibm.com is really Type=NS servereast.backup2.ibm.com - name is domain (e.g. - value is cannonical name foo.com) - value is IP address of authoritative name server Type=MX for this domain - value is name of mailserver associated with name 81 Mao W07ƒƒ DNS protocol, messages DNS protocol : query and reply messages, both with same message format msg header identification: 16 bit for query, reply to query uses same flags: - query or reply - recursion desired - recursion available - reply is authoritative 82 Mao W07DNS protocol, messages Name, type fields for a query RRs in reponse to query records for authoritative servers additional “helpful” info that may be used 83 Mao W07ƒƒƒƒ Inserting records into DNS Example: just created startup “Network Utopia” Register name networkuptopia.com at a registrar (e.g., Network Solutions) - Need to provide registrar with names and IP addresses of your authoritative name server (primary and secondary) - Registrar inserts two RRs into the com TLD server: (networkutopia.com, dns1.networkutopia.com, NS) (dns1.networkutopia.com, 212.212.212.1, A) Put in authoritative server Type A record for www.networkuptopia.com and Type MX record for networkutopia.com How do people get the IP address of your Web site? 84 Mao W07ƒƒƒƒƒ Discussions Is it easy to attack the DNS system? Why is DNS caching good? Why is DNS caching bad? DNS is “exploited” for server load balancing, how? - Local DNS servers are usually close to local clients If you were to design DNS differently today, how would you? - Any problems with the current DNS system? 85 Mao W07P2P: centralized directory Bob original “Napster” design centralized directory server 1) when peer connects, it 1 peers informs central server: 1 - IP address - content 3 1 2) Alice queries for “Hey 2 1 Jude” 3) Alice requests file from Bob Alice 86 Mao W07ƒƒƒƒ ƒƒƒ Query flooding: Gnutella overlay network: graph fully distributed - no central server edge between peer X and Y if there’s a TCP public domain protocol connection many Gnutella clients all active peers and edges implementing protocol is overlay net Edge is not a physical link Given peer will typically be connected with 10 overlay neighbors 87 Mao W07ˆˆˆ Query Query Gnutella: protocol File transfer: HTTP Query message sent over existing TCP Query connections QueryHit peers forward Query message QueryHit sent over Query reverse QueryHit path Scalability: limited scope flooding 88 Mao W07 QueryHit QueryGnutella: Peer joining 1. Joining peer X must find some other peer in Gnutella network: use list of candidate peers 2. X sequentially attempts to make TCP with peers on list until connection setup with Y 3. X sends Ping message to Y; Y forwards Ping message. 4. All peers receiving Ping message respond with Pong message 5. X receives many Pong messages. It can then setup additional TCP connections 89 Mao W07ƒƒ Exploiting heterogeneity: KaZaA Each peer is either a group leader or assigned to a group leader. - TCP connection between peer and its group leader. - TCP connections between some pairs of group leaders. Group leader tracks the content in all its children. ordinary peer group-leader peer neighoring relationships in overlay network 90 Mao W07ƒƒƒƒƒ KaZaA: Querying Each file has a hash and a descriptor Client sends keyword query to its group leader Group leader responds with matches: - For each match: metadata, hash, IP address If group leader forwards query to other group leaders, they respond with matches Client then selects files for downloading - HTTP requests using hash as identifier sent to peers holding desired file 91 Mao W07ƒƒƒƒ Kazaa tricks Limitations on simultaneous uploads Request queuing Incentive priorities Parallel downloading 92 Mao W07ƒƒ Discussions How would you design a P2P system that is scalable, decentralized, and guarantees the location of the files? One solution: DHT (Distributed Hash Table) - Guarantees that you can find the file - Mapping between the file and the node ID - Consistent hashing function assigns each node and key an m-bit identifier using SHA-1 base hash function. 93 Mao W07ƒƒƒƒ Chord protocol Consistent hashing function assigns each node and key an m-bit identifier using SHA-1 base hash function. Node’s IP address is hashed. Identifiers are ordered on a identifier circle m modulo 2 called a chord ring. succesor(k) = first node whose identifier is = identifier of k in identifier space. 94 Mao W07Chord protocol m = 6 10 nodes 95 Mao W07
Website URL
Comment