2.1 Principles of app layer protocols

• some network apps
  • ex) Web, text messaging, e-mail, social networking, multi-user network games, streaming stored video(youtube, netflix), p2p file sharing, voice over IP(Skype), real-time video conferencing(Zoom), Internet search, remote login
• creating a network app
  • Write programs tahta
    • 다른 종단 시스템에서 동작
    • 네트워크를 통해 서로 통신
    • ex) Web: Web server software communicates with browser software
    • 네트워크 코어 장비에서 동작하는 소프트웨어를 만들 필요는 없음
    • Network core devices do not function at app layer
    • applications on end systems allows for rapid app development, propagation

Application architectures

client-server paradigm

• Typical network app has two pieces: client and server
• 서버
  • 클라이언트에게 요청된 서비스를 제공
  • always-on host, 고정 IP
  • ex) Web server sends requested Web page, mail server delivers e-mail
• 클라이언트
  • 서버와 접속을 개시(”speaks first”)
  • 서버로부터 서비스를 요청(request)
  • may be intermittently connected
  • may have dynamic IP addresses
  • Web: client implemented in browser; e-mailI in mail reader

Pure P2P architecture

• no always on server
• arbitrary end systems directly communicate
• peers request service from other peers, provide service in return to other peers
  • self scalability - new peers bring new service capacity, as well as new service demands
• peers are intermittently connected and change IP addresses
• example: Gnutella
• 확장성이 높지만 관리하기 어려움

Hybrid of client-server and P2P

• Napster
  • File transfer P2P
  • File search centralized
    • Peers register content at central server
    • Peers query same central server to locate content
• Instant messaging
  • chatting between two users is P2P
  • Presence detection/location centralized:
    • User registers its IP address with central server when it comes online
    • User contacts central server to find IP addresses of buddies
• 서버가 peer들의 정보를 관리하고 통신은 peer to peer
• Skype
  • voice-over-IP P2P application
  • centralized server: finding address of remote party:
  • client-client connection: direct(not through server)

Process communicating

• 프로세스: 호스트에서 동작하는 프로그램
  • 동일 호스트 내에서 두 프로세스는 inter-process communication(defined by OS)을 사용하여 통신
  • 다른 호스트에서 수행되는 프로세스들은 응용계층 프로토콜로 통신
    • 네트워크를 통한 메시지 교환으로 통신
• Sockets
  • 프로세스는 소켓을 통해 메시지를 송/수신함
    • 소켓: 호스트내의 응용 계층과 전송 계층 사이의 인터페이스
    • 어플리케이션과 네트워크 간의 API
  • socket analogous to door
    • sending process shoves message out door
    • sending process assumes transport infrastructure on other side of door which brings message to socket at receiving process
  • 어플리케이션 개발자가 전송 계층에 대해 가지는 제어
    • choice of transport protocol
    • ability to fix a few parameters(버퍼, 세그먼트 크기 등)
• Addressing processes
  • For a process to receive messages, it must have an identifier
  • A host has a unique32-bit IP address
  • Identifier includes both the IP address and port numbers associated with the process on the host
  • Example port numbers
    • HTTP server: 80
    • Mail server: 25
  • to send HTTP message to gaia.cs.umass.edu web
    • IP address: 128.119.245.12
    • port number: 80

2.2 Web and HTTP

• 몇가지 용어들
  • 웹 페이지(Web page)는 객체(object)들로 구성
  • 객체는 URL(Uniform Resource Locator)로 지정할 수 있는 하나의 파일 -HTML 파일, JPEG 이미지, Java applet, 오디오 파일 등 -이다.
  • 웹 페이지는 기본 HTML파일과 URL에 의해 주소 지정되는 여러개의 참조 객체들로 구성됨
  • URL의 예: http://www.someschool.edu/someDept/pic.gif

HTTP 개요

• HTTP: hypertext transfer protocol
  • 웹의 응용 계층 프로토콜
  • 클라이언트/서버 모델
    • client: browser that requests, receives and “displays” Web objects
    • server: Web server sends objects in response to requests
  • HTTP 1.0: RFC: 1945
  • HTTP 1.1: RFC 2068
  • HTTP/2: RFC 7540
• Uses TCP
  • client initiates TCP connection(creates socket) to server, port 80
  • server accepts TCP connection from client
  • HTTP messages(application-layer protocol messages) exchanged between browser(HTTP client) and Web server(HTTP server)
  • TCP connection closed
• HTTP is stateless
  • server maintains no information about past client requests

HTTP 연결(connection)

• 비지속(Nonpersistent) HTTP
  • at most one object sent over TCP connection
    • connection then closed
  • downloading multiple objects required multiple connections
  • HTTP/1.0 uses nonpersistent HTTP
• 지속(Persistent) HTTP
  • Multiple objects can be sent over single TCP connection between client and server
  • HTTP/1.1 uses persistent connections in default mode

응답 시간 모델링

Nonpersistent HTTP

• RTT(Round-Trip-Time) time to send a small packet to travel from client to server and back
  • RTT는 전파지연, 큐잉지연, 처리지연 등을 포함
• HTTP response time(per object)
  • TCP 연결 초기화를 위해 하나의 RTT
  • HTTP request와 HTTP response를 위해 하나의 RTT
  • 파일 전송 시간
  • total response time = 2RTT + file transmission time

Persistent HTTP

• Nonpersistent HTTP의 단점
  • 각 객체 당 2RTT를 요구
  • OS가 각 TCP 연결 설정을 해야 하고 호스트 자원을 할당해야 한다.
    • 수많은 클라이언트로부터 동시에 요청을 받는 웹 서버에 심각한 부담을 줌
• Persistent HTTP
  • 서버는 응답을 보낸 후에 연결을 그대로 유지
  • 동일한 클라이언트/서버간의 이후 요청과 응답은 같은 연결을 통해 전송됨
  • 서버는 연결이 일정기간(timeout 기간)동안 사용되지 않으면 연결을 닫음
• Persistent without pipelining
  • 클라이언트는 이전 요청에 대한 응답을 수신한 후에만 새로운 요청을 보냄
  • 각 참조된 객체에 대해 하나의 RTT
• Persistent with pipelining
  • HTTP/1.1의 기본 모드
  • 클라이언트는 참조를 만나자마자 요청을 발생
  • 모든 요청들이 연속적으로 보내지고 응답들이 연속적으로 보내진다면, 모든 참조 객체에 대해 단지 하나의 RTT만 필요

HTTP request message

• two types of HTTP messages: request, response
• HTTP request message
  • ASCII(human-readable format)

Uploading form input

• Post method
  • Web page often includes form input
  • User input is uploaded to server in entity body
• GET method
  • include user data in URL of HTTP GET request message(following a ‘?’)

Method types

• HTTP/1.0
  • GET
  • POST
  • HEAD
    • Get 방식과 유사
    • 서버가 HEAD 방식 요청을 받으면 HTTP 메시지로 응답을 하는데 요청 객체를 보내지 않음
    • 어플리케이션 개발자들이 주로 디버깅을 위해 사용
• HTTP/1.1
  • GET, POST, HEAD
  • PUT
    • uploads file in entity body to path specified in URL field
  • DELETE
    • deletes file specified in the URL field

HTTP 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

Maintaing user/server state: cookies

• Recall: HTTP GET/response interaction is stateless
• no notion of multi-step exhcanges of HTTP messages to complete a Web “transaction”
  • no need for client/server to track “state” of multi-step exchange
  • all HTTP requests are independent of each other
  • no need for clinet/server to “revcover” from a partially-completed-but-never completely-completed transaction

cookies: keeping: “state”

• Web sites and client browser use cookies to maintain some state between transactions
• 쿠키 기술의 4가지 요소:
  1. cookie header line in the HTTP response message
  2. cookie header in HTTP request message
  3. cookie file kept on user’s host and managed by user’s browser
  4. back-end database at Web site
• Example
  • Susan access Internet always from same PC
  • she visits a specific e-commerce site for first time
  • When initial HTTP requests arrives at site, stite creates a unique ID and creates an entry in backend database for ID
• what cookies can bring
  • quthorization
  • shopping carts ⇒ 상태유지 됐다는 증거
  • recommendations
  • user session state(Web e-mail)

Web caches(proxy server)

• Goal: satisfy client request without involving origin server
• user sets browser: Web accesses cache
  • if object in cache: cache returns object
  • else cache requests object from origin server, then returns object to client
• Cache acts as both client and server
• Cache can do up-to-date check using If-modified-since HTTP header
  • Issue: should cache take risk and deliver cached object without checking?
  • Heuristics are used
• Typically cache is installed by ISP(university, company, residential ISP)
• server tells cache about object’s allowable caching in response header
• Why Web caching
  • Reduce response time for client request
  • Reduce traffic on an institution’s access link
  • Internet is dense with caches: enables poor content providers to effectively deliver content

Conditional GET: client-side-caching

• Goal: don’t send object if client has up-to-date cached version
• clinet: specify date of cached copy in HTTP request
  • If-modified-since:
• server: response contains no object if cached copy is up-to-date:
  • HTTP/1.0 304 Not modified

(참고) FTP: the file transfer protocol

• 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

FTP: separate control, data connections

• FTP 클라이언트는 전송 프로토콜로 TCP를 명시하고 port 21로 FTP 서버에 접속
• 클라이언트는 제어연결상으로 authorization을 획득
• 클라이언트는 제어 연결 상으로 명령을 보내어 원격 디렉토리를 브라우징
• 서버가 파일 전송을 위한 명령을 수신하면 서버는 클라이언트에게 TCP 데이터 연결을 초기화
• 하나의 파일 전송 후에, 서버는 연결을 닫는다.
• 서버는 또다른 파일 전송을 위해 두번째 TCP 데이터 연결을 개통
• control connection: out of band
• FTP server maintains “state”: current directory, earlier authentication

2.3 Electronic Mail(SMTP, POP3, IMAP)

• 3가지 주요 요소
  • 사용자 에이전트
  • 메일 서버
  • SMTP(simple mail transfer protocol
• 사용자 에이전트(UA)
  • a.k.a “mail reader”
  • composing, editing, reading mail messages
  • ex) outlook, thunderbrid, iphone mail client
  • outgoing, incoming messages stored on server
• mail severs
  • 각 수신자들은 메일 서버 내에 메일 박스를 가짐
  • 메일 박스는 사용자에 대한 수신 메일 메시지를 유지 관리
  • 송신 메일 메시지의 메시지 큐
• SMTP protocol
  • 인터넷 전자 우편을 위한 응용 계층 프로토콜
  • 메일 서버들간에 메일 메시지 송수신을 위한 프로토콜
  • client: sending mail server
  • server: receiving mail server
• SMTP RFC(5321)
  • Uses Tcp to reliably transfer email message from client(mail server initiating connection) to server, sport 25
    • direct ransfer: sending server (acting like client) to receiving server
  • three phases of transfer
    • SMTP handshaking (greeting)
    • SMTP transfer of messages
    • SMTP closure
  • command/response interaction(like HTTP)
  • commands: ASCII text
  • response: status code nad phrase
• SMTP: final words
  • SMTP는 지속 연결을 사용
  • SMTP는 7-bit ASCII로 표현된 메시지( ehader&body)를 요구
  • SMTP 서버는 메시지의 끝을 결정하기 위해 CRLF.CRLF를 사용
• HTTP와 비교
  • HTTP: pull ⇒ 서버의 컨텐츠를 당겨오는것
  • SMTP: push ⇒ 메일 서버에게 보내는 방식
  • both have ASCII command/response interaction, status codes
  • HTTP: each object encapsulated in its own response msg
  • SMTP: multiple objects sent in multipart msg

Message format: multimedia extensions

• MIME(multipurpose internet mail extension): 멀티미디어 메일 확장, RFC 2045, 2056
• additional lines in msg header declare MIME content type
• MIME types(Content-Type: type/subtype; parameters
  • Text
    • example subtypes: plain, html
      • text/plain, text/html
  • Image
    • example subtypes: jpeg, gif
      • image/gif, image/jpeg
  • Audio
    • example subtypes: basic(8-bit mu-law encoded), 32kadpcm( 32kbps coding)
  • Video
    • example subtypes:mpeg, quicktime
      • video/mpeg
  • Application
    • other data that must be processed by reader before “viewable”
      • example subtypes:msword, octet-stream
        • application/msword
• Multipart Type
  • HTTP는 각각의 객체들을 독립된 HTTP 응답 메시지로 전송
  • SMTP는 모든 객체를 같은 메시지에 넣어 전송
    • 멀티미디어 메시지가 하나 이상의 객체를 포함할 경우, Content-type: multipart/mixed
      • 수신 UA에게 메시지가 여러 객체를 가지고 있음을 알려줌
      • 수신 UA는 각 객체의 시작과 끝, non-ASCII 객체들의 encoding, 각 메시지의 content-type을 결정하는 수단을 필요로함
      • 각 객체 사이에 경계 문자를 위치시키고 메시지 각 객체 앞에 Content-type과 Content-Transfer-Encoding 헤더 라인을 위치시켜 수행

Mail access protocols

• SMTP: delivery/storage to receiver’s server
• 수신측 UA가 메일 메시지를 얻기 위해 SMTP를 사용할 수 없음
  • SMTP는 push 프로토콜, 메일 메시지를 얻는 것은 pull 동작
• Mail access protocol: retrieval from server
  • POP: Post Office Protocol[RFC 1939]
    • authorization(agent↔server) and download
  • IMAP: Internet Mail Acess Protocol [RFC 1730, RFC 3501]
    • more features (more complex)
    • manipulation of stored msgs on server
    • Keep all messages in one place: the server
    • Allows user to organize messages in folders
    • IMAP keeps user state across sessions
      • names of folders and mappings between message IDs and folder name
  • HTTP: Gmail, Hotmail, Yahoo! Mail, etc.
  • POP3 protocol
    • UA가 메일 서버와 포트 110번으로 TCP 연결
    • authorization phase
      • client commands
        • user: declare username
        • pass: password
      • server resposnses
        • +OK
        • -ERR
    • transaction phase
      • client commands
        • list: list message numbers
        • retr: retrieve message by number
        • dele: delete
        • quit
    • More about POP3
      • download and delete mode
        • Bob cannot re-read e-mail if he changes client
      • download-and-keep: copies of messages on different clients
      • POP3 is stateless across sessions

2.4 DNS(Domain Name System)

• People: many identifiers
  • SSN, name, passport #
• Internet hosts, routers:
  • IP address(32bit) - used for addressing datagrams
  • “name”, e.g., itcae.pknu.ac.kr - used by humans
• Domain Name System
  • distributed database implemented in hierarchy of many name servers
  • application-layer protocol/ host, routers, name servers to communicate to resolve names(address/name translation)
    • note: core Internet function, implemented as application-layer protocol
  • complexity at network’s “edge”
  • UDP, 포트 53이용 ⇒ 전송계층
• DNS의 서비스
  • Hostname to IP address translation
  • 호스트 앨리아싱(aliasing)
    • 복잡한 호스트 이름을 가진 호스트는 하나 이상의 별명을 가질 수 있음
    • ex) relay1.west.coast.enterprise.com/ enterprise.com과 coast.enterprise.com (별칭 호스트 이름)
  • 메일 서버 앨리아싱
    • 메일 서버 호스트 이름에 대한 별칭 호스트 이름 허용
  • 부하 분산(load distribution)
    • 중복 웹 서버와 같은 여러 중복 서버들 사이에 부하를 분산하기 위해서도 사용 가능
    • 클라이언트가 주소 집합으로 매핑되어 있는 호스트 이름에 대한 DNS 질의를 하면, 서버는 IP주소 집합 전체를 응답
    • 이때 각 응답 내에서의 주소 순서를 회전시킴
    • 일반적으로 클라이언트는 주소 집합 내의 첫번째 주소로 요청
    • 따라서 DNS 회전은 여러 중복 서버들 사이에 트래픽 분산 효과를 나타냄
• 많은 네임 서버를 가진 계층 형태로 구성
  • 로컬 네임서버
  • 책임 네임 서버(authoritative name server)
  • 루트 네임서버
  • Top-level domain servers
• Local Name Server(기관이나 조직)
  • Does not strictly belong to hierarchy
  • Each ISP (residential ISP, company, university) has one.
    • Also called “default name server”
      • Windows: >ipconfig /all
  • When a host makes a DNS query, query is sent to its local DNS server
    • Local DNS server returns reply, answering
      • from its local cache of recent name-to-address translation pairs(possibly out of date!)
      • forwarding request into DNS hierarchy for resolution
• Root name servers(local이 IP주소 모를때 Root에게)
  • official, contact-of-last-resort by name servers that cannot resolve name
  • incredibly important Internet function
    • Internet couldn’t function without it!
    • DNSSEC - provides security(authentication, message integrity)
  • ICANN(Internet Corporation for Assigned Names and Numbers) manages root DNS domain
• TLD and Authoritative Servers
  • Top-level domain(TLD) servers
    • responsible for com, org, net, edu, etc, and all top-level country domains, e.g.: .uk, .fr, .ca, .kr
      • Network solutions maintains servers for .com, .net TLD
      • Educause for .edu TLD
• Authoritative DNS servers: organization’s own DNS servers, providing authoritative hostname to IP mappings for organization servers (e.g. Web and mail)
  • can be maintained by organization or service provider
• DNS name resolution example
  • Host at cis.poly.edu wants IP address for gaia.cs.umass.edu
    • 반복적 질의(iterated query)
  • contacted server replies with name of server to contact
  • “I don’t know this name, but ask this server”
  • 재귀적 질의
    • puts burden of name resolution on caontacted name server
    • Root에게 부하 집중 ⇒ 대부분 반복적 질의 사용
• DNS: caching and updating records
  • 지연 성능 향상과 DNS 메시지 수를 줄이기 위해 DNS 캐싱을 사용
  • once (any) name server learns mapping, it caches mapping
    • 네임서버가 호스트 이름에 대한 DNS 매핑을 수신하면, 그 메시지를 네임서버 체인에 따라 전송함과 동시에 로컬 메모리에 그 매핑을 캐싱
    • TLD servers typically cached in local name servers
      • thus root name servers not often visited
    • cache entries timeout(disappear) after some time
  • cached entries may be out-of-date
    • if named host changes IP address. may not be known Internet-wide until all TTLs expire!
    • best-effort name-to-address translation!
• DNS records
  • DNS: distributed DB storing resource records
    • 호스트 이름을 IP 주소로 매핑하기 위해 사용
    • RR format: (name, value, type, ttl(RR 생존기간. 자원이 캐시에 보관될 수 있는 시간을 제한))
    • Type=A
      • name is hostname
      • value is IP address
    • Type=NS
      • name is domain(e.g. foo.com)
      • value is IP address of authoritative name server for this domain
    • Type=CNAME(별칭)
      • name is alias name for some “canonical” (the real) name
      • www.ibm.com is really servereast.backup2.ibm.com
      • value is canonical name
    • Type=MX
      • value is canonical name of mailserver associated with name(alias name)
• DNS protocol, messages
  • DNS protocol: query and reply messages, both with same message format
  • message header
    • identification: 16 bit # for query, reply to query uses same #
    • flags
      • query or reply
      • recursion desired
      • recursion available
      • reply is authoritative
• Attacking DNS
  • DDos attacks
    • Bombard root servers with traffic
      • Not successful to date
      • Traffic Filtering
      • Local DNS servers cache IPs of TLD servers, allowing root server bypass
    • Bombard TLD servers
      • Potentially more dangerous
  • Redirect attacks
    • Man-in-middle
      • Intercept queries
    • DNS poisoning
      • Send bogus relies to DNS server, which caches
  • Exploit DNS for DDoS
    • Send queries with spoofed source address: target IP
    • Requires amplification

2.5 P2P file sharing

Pure P2P architecture

• no always-on server
• arbitrary end systems directly communicate
• peers are intermittently connected and change IP addresses
  • self scalability - new peers bring new service capacity, and new service demands
  • complex management
• examples: P2P file sharing(BitTorrent), streaming (KanKan), VoIP(Skype)

File Distribution: Server-client vs P2P

• client-server
  • server transmission
    • must sequentially send(upload) N files copies
      • time to send one copy: F/u_s
      • time to send N copies: NF/u_s
  • client: each client mush download file copy
    • d_min = min client download rate ⇒ 대역폭이 가장 낮은 client
    • min client download time: F/d_min
  • D_c-s ≥ max{NF/u_s, F/d_min}
• P2P
  • server transmission: must upload at least one copy
    • time to send one copy: F/u_s
  • client: each client mush download file copy
    • min client download time: F/d_min
  • clients: as aggregate must download NF bits
    • max upload rate( limiting max download rate) is U_s + Σu_i
  • D_p2 ≥ max{F/u_s, F/d_min, NF/(u_s + Σu_i)}

File distribution: BitTorrent

• file divided into 256kb chunks
• peers in torrent send/receive file chunks
  • tracker tracks peers participating in torrent
  • torrent group of peers exchanging chunks of a file
• peer joining torrent:
  • has no chunks, but will accumulate them over time
  • registers with tracker to get list of peers, connects to subset of peers(”neighbors”)
• while downloading, peer uploads chunks to other peers
• churn: peers may come and go (peer들의 상태가 나갔다 들어왔다)
• once peer has entire file, it may (selfishly) leave or (altruistically) remain
• requesting chunks
  • at any given time, different peers have different subsets of file chunks
  • periodically, a peer(Alice) asks each neighbor for list of chucks that they have
  • Alice sends requests for her missing chunks, rarest first
    • 이웃들 중에서 가장 적은 복사본을 가진 chunk를 요구
    • 토렌트에서 각 chunk의 수가 대략적으로 동일하게 함
• sending chunks: tit-for-tat
  • Alice sends chunks to four neighbors currently sending her chunks at the highest rate
    • re-evaluate top 4 every 10 secs
  • every 30 secs: randomly select another peer, starts sending chunks
    • “optimistically unchoke” this peer
    • newly chosen peer may join top 4
• searching for information
  • index in P2P system: maps information to peer location(location = IP address & port number).
  • File sharing(eg e-mule)
    • Index dynamically tracks the locations of files that peers share
    • peers need to tell index what they have
    • Peers search index to determine where files can be found
  • Instatnt messaging
    • Index maps user names to locations(IP address)
    • When user starts IM application, it nees to inform index of its location
    • Peers search index to determine IP address of user
• centralized index
  • original Napster design
    1. when peer connects, it informs central server
       1. IP address
       2. content
    2. Alice queries for “Hey Jude”
    3. Alice requests file from Bob
  • problems with centralized directory
    • single point of failure
    • performance bottlenect
    • copyright infringement
    • 피어들간의 파일 전송은 분산화되어 있지만, 컨텐츠를 찾는 과정은 매우 중앙집중화되어 있음

Query flooding: Gnutella

• Pure P2P
• fully distributed
  • no central server
• public domain protocol
• many Gnutella clients implementing protocol
• overlay network: graph
  • edge between peer X and Y if there’s a TCP connection (물리적x, 가상 연결)
• all active peers and edges is overlay net
• Edge is not a physical link
• Given peer will typically be connected with < 10 overlay neighbors

Gnutella: protocol

• Send query to neighbors
  • Query message sent over existing TCP connections
• Neighbors forward Query message
• QueryHit sent over reverse path

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

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 seome pairs of group leaders
• Group leader tracks the content in all its children
• Peer queries group leader; group leader may query other group leaders

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

P2P Case study: Skype

• inherently P2P: pairs of users communicate.
• proprietary application-layer protocol (inferred via reverse engineering)
• hierarchical overlay with SNs
• Index maps usernames to IP addresses; distributed over SNs

Distributed Hash Table(DHT)

• DHT: a distributed P2P database
• Database has (key, value) pairs
  • ex) key: human name; value: social security number
• Hash Table
  • More convenient to store and search on numerical representation of key
  • key = hash(original key)
• Distribute the (key, value)pairs over the (milions of peers)
  • pairs are evenly distributed over peers
• a pper queries DHT with key
  • DHT returns value that match the key
• Peers can also insert(key, value) pairs
• Each peer only knows about a small number of other peers
• Robust to peers coming and going (churn)

How to assign keys to peers

• 어떤 n에 대해 [0,2^n-1]범위 내의 정수 식별자를 각 peer에게 할당
  • 각 식별자는 n bits로 표현됨
• 각 key는 같은 범위 내의 ㅈ어수일 것을 요구
• 정수 key를 얻기 위해 original key를 해쉬
• 가장 가까운 ID를 가진 peer에게 key를 할당
• convention in lecture: 가장 가까운의 의미는 바로 다음 후임자
• eg) n=4; peers:1, 3, 4, 5, 8, 10 ,12, 14
  • key = 13, then successor peer = 14
  • key = 15, then successor peer = 1

Circular DHT

• 각 peer는 바로 다음 후임자와 바로 직전의 전임자만을 알고 있다.
• O(N) messages on average to resolve query, when there are N peers

Circular DHT with shortcuts

• 각 peer는 전임자, 후임자, 지름길의 IP 주소들을 계속 알고 있다.
• reduced from 6 to 2 messages
• possible to design shortcuts so 0(log N) neighbors, 0(log N) message in query

Peer churn

• handling peer churn
  • peers may come and go (churn)
  • each peer knows address of its two successors
  • each peer periodically pings its two successors to check aliveness
  • if immediate successor leaves, choose next successor as new immediate successor

2.6 video streaming and content distribution networks

Multimedia: video

• video: sequence of images displayed at constant rate
  • eg) 24 images/sec
• digital image: array of pixels
  • each pixel represented by bits
• coding: use redundancy within and between images to decrease #bits used to encode image
  • spatial (within image): 다 보내기는 하는데 중복되는 색깔과 중복되는 색깔의 숫자만 보냄
  • temporal (from one image to next): 바뀌는 부분만 보냄
• CBR(constant bit rate): video encoding rate fixed
• VBR(variable bit rate): video encoding rate changes as amount of spatial, temporal coding changes
• examples
  • MPEG 1 (CD-ROM) 1.5 Mbps
  • MPEG2 (DVD) 3-6 Mbps
  • MPEG4 (often used in Internet, 64Kbps ~ 12Mbps)
  • H.264 (→MPEG-4 part10, AVC)

Streaming stored video

• challenges
  • continuous playout constraint: during client video playout, playout timing must match orginal timing
    • but network delays are variable (jitter), so will need client-side buffer to match continuous playout constraint
  • other challenges
    • client interactivity: pause, fast-forward, rewind, jump through video
    • vido packets may be lost, retransmitted

Streaming multimedia: DASH

• server
  • divides video file into multiple chunks
  • each chunk encoded at multiple different rates
  • different rate encodings stored in different files
  • files replicated in various CDN nodes
  • manifest file provides URLs for different chunks\
• client
  • periodically estimates server-to-client bandwidth
  • consulting manifest, requests one chunk at a time
    • chooses maximum coding rate sustainable given current bandwidth
    • can choose different coding rates at different points in time (depending on available bandwidth at time), and from different servers
• intelligence at client determines
  • when to request chunk(so that buffer starvation, or over flow does not occur)
  • what encoding rate to request(higher quality when more bandwidth available)
  • where to request chunk(can request from URL server that is “close” to client or has high available bandwidth)
• Streaming video = encoding + DASH + playout buffering

Content distribution networks

• challenge: how to stream content to hundreds of thousands of simultaneous users?
• option 1: single, large “mega-server”
  • single point of failure
  • point of network congestion
  • long path to distant clients
  • multiple copies of video sent over outgoing link
• option 2: store/serve multiple copies of videos at multiple geographically distributed sites CDN
  • enter deep: push CDN servers deep into many access networks
    • close to users
    • used by Akamai, 240,000 servers deployed in > 120 countries(2015)
  • bring home: smaller number(10’s)of larger clusters in POPs near (but not within) access networks
    • used by Limelight
• CDN: stores copies of content at CDN nodes
  • e.g. Netflix stores copies of MadMen
• subscriber requests content from CDN
  • directed to nearby copy, retrieves content
  • may choose different copy if network path congested

2.7 Socket programming with TCP and UDP

• Socket: a door between application process and end-transport protocol (UDP or TCP)

Socket programming with UDP

• UDP: no “connection” between client and server
  • no handshaking
  • Sender는 각 패킷에 명시적으로 목적지 호스트의 IP 주소와 포트번호를 붙여야 한다.
  • Server는 수신된 패킷으로부터 sender의 IP 주소와 포트번호를 추출해야 한다.
  • transmitted data may be lost or received out-of-order

Socket programming with TCP

• 클라이언트는 서버에 접속해야 한다
  • 서버 프로세스는 먼저 수행되고 있어야 한다
  • 서버는 클라이언트 접속을 처리하는 소켓을 생성해야 한다.
• 클라이언트는 다음에 의해 서버에 접속한다
  • client-local TCP 소켓을 생성
  • 서버 프로세스의 IP주소, 포트 번호를 명시
  • 클라이언트가 소켓을 생성하면 클라이언트 TCP가 서버 TCP와 연결을 설정
  • 클라이언트가 접속하면, 서버 TCP는 클라이언트와 통신하기 위해 서버 프로세스를 위한 새로운 소켓을 생성한다.
    • 서버는 다수의 클라이언트와 통신하는 것이 허용됨
    • 클라이언트를 구별하기 위해 소스 포트 번호가 사용됨

Summary

Application architectures

• client-server
• P2P
• hybrid

application service requirements

• reliability, bandwidth, delay

Internet transport service model

• connection-oriented, reliable: TCP
• unreliable, datagrams: UDP

specific protocols

• HTTP
• FTP
• SMTP, POP, IMAP
• DNS
• P2P: BitTorrent

video streaming, CDNs

socket programming