Electronic Mail Reading: 9.2.1Distributed Hash TablesLocation-Independent NamingStructured Solution: Special NodesUnstructured Solution: RandomCan We Do Better?HashingHash FunctionsConsistent HashingWhere to Store (Key, Value) Pair?How to Find the Nearest Node?Construct Overlay in Clever WayExample: See Section 9.4E-MailGoals of Today’s LectureE-Mail MessageE-Mail Message Format (RFC 822)Limitation: Sending Non-Text DataLimitation: Sending Multiple ItemsMultipurpose Internet Mail ExtensionsExample: E-Mail Message Using MIMEDistribution of Content TypesE-Mail AddressesMail Servers and User AgentsSMTP Store-and-Forward ProtocolExample With Received HeaderMultiple Server HopsElectronic Mailing ListsSimple Mail Transfer ProtocolSimple Mail Transfer Protocol (Cont.)Scenario: Alice Sends Message to BobSample SMTP interactionTry SMTP For YourselfRetrieving E-Mail From the ServerInfluence of PCs on E-Mail RetrievalPost Office Protocol (POP)POP3 ProtocolLimitations of POPInteractive Mail Access Protocol (IMAP)Web-Based E-MailConclusionsApplication-Layer ProtocolsSlide 43Application vs. Application-Layer ProtocolsProtocols Tailored to the ApplicationSlide 46Comparing the ProtocolsComparing the Protocols (Continued)Reflecting on Application-Layer Protocols1Electronic MailReading: 9.2.1COS 461: Computer NetworksSpring 2007 (MW 1:30-2:50 in Friend 004)Jennifer RexfordTeaching Assistant: Ioannis Avramopoulos http://www.cs.princeton.edu/courses/archive/spring07/cos461/2Distributed Hash Tables3Location-Independent Naming•Separate a name from its location–File name is “BritneyHitMe.mp3”–Current location is 12.78.183.2•Look-up problem–Given item’s name, find who has the item–Where item stored at dynamic set of nodes•Two key design decisions–How do we map items on to nodes?–How do we route a request to that node?4Structured Solution: Special Nodes•Central index (Napster)–Central server keeps track of who has each file–Peers publish a list of their content at the server–Peers query the server to locate desired content–Simple and efficient, but not scalable or reliableCan scale through hierarchy (e.g., DNS)5Unstructured Solution: Random•Query flooding (Gnutella)–Peers do not publish information about content–Instead, queries are flooded throughout system–And a peer who has the desired content replies–Reliable, but long delays and poor scalability6Can We Do Better?•Decentralized–No central coordination•Scalable–Run with thousands or millions of nodes•Fault tolerant–Tolerate nodes joining, leaving, failing, …•Two key ideas–Hashing: to map a name to a value–Distributed: for decentralized, self-organization7Hashing•Name-value pairs (or key-value pairs)–E.g., “BritneyHitMe.mp3” and “12.78.183.2”–E.g,. “Jen Rexford” and “[email protected]”•Hash table–Data structure that associates keys with valueslookup(key)valuekey value8Hash Functions•Hashing–Transform the key into a number–And use the number to index an array•Example hash function–Hash(x) = x mod 101, mapping to 0, 1, …, 100•Challenges–What if there are more than 101 nodes? Fewer?–Which nodes correspond to each hash value?–What if nodes come and go over time?9Consistent Hashing•Large, sparse identifier space (e.g., 128 bits)–Hash a set of keys x uniformly to large id space–Hash nodes to the id space as well0 1Hash(name) object_idHash(IP_address) node_idId space represented as a ring.2128-110Where to Store (Key, Value) Pair?•Mapping keys in a load-balanced way–Store the key at one or more nodes–Nodes with identifiers “close” to the key –Where distance is measured in the id space•Advantages–Even distribution–Few changes as nodes come and go…Hash(name) object_idHash(IP_address) node_id11How to Find the Nearest Node?•Need to find the closest node–To determine who should store (key, value) pair–To direct a future lookup(key) query to the node•Strawman solution: central registry–Full list of node ids and IP addresses–Like the central registry in Napster–Not practical in a large system•Alternative solution: route the request–Route the request through other peers–To get ever “closer” to the peer near lookup(key)12Construct Overlay in Clever Way•Requesting node looks at his own id–Hash(IP_address), e.g., 65a1fc in hexadecimal•Requesting node looks at the key’s id–Hash(key), e.g., d46a1c in hexadecimal•Requesting node knows another node–That is “closer”, e.g., starts with hex “d”–Then, forward the query to that node•Keep moving closer, in id space to the key–Until you reach a node that can’t get closer–And you’ve found the node that stores the key!13Example: See Section 9.4 •Each step takes you closer–Till you eventually get there…•Bounded number of hops–Log(N) for N nodes–Better than Gnutella•Skipping details–Adding nodes–Removing nodes–Finding neighbors14E-Mail15Goals of Today’s Lecture•Electronic mail–E-mail messages, and MIME–E-mail addresses, and role of DNS–E-mail servers and user agents•Electronic mail protocols–Transferring e-mail messages between servers (SMTP)–Retrieving e-mail messages (POP, IMAP, and HTTP)•Application-layer protocols (see backup slides)–Applications vs. application-layer protocols–Tailoring the protocol to the application16E-Mail Message•E-mail messages have two parts–A header, in 7-bit U.S. ASCII text–A body, also represented in 7-bit U.S. ASCII text•Header–Lines with “type: value”–“To: [email protected]”–“Subject: Go Tigers!”•Body–The text message–No particular structure or meaningheaderbodyblankline17E-Mail Message Format (RFC 822)•E-mail messages have two parts–A header, in 7-bit U.S. ASCII text–A body, also represented in 7-bit U.S. ASCII text•Header–Series of lines ending in carriage return and line feed–Each line contains a type and value, separated by “:”–E.g., “To: [email protected]” and “Subject: Go Tigers”–Additional blank line before the body begins•Body–Series of text lines with no additional structure/meaning–Conventions arose over time (e.g., e-mail signatures)18Limitation: Sending Non-Text Data•E-mail body is 7-bit U.S. ASCII–What about non-English text?–What about binary files (e.g., images and executables)?•Solution: convert non-ASCII data to ASCII–Base64 encoding: map each group of
View Full Document
Unlocking...