Transcript week4 lecc 1MSEE

Chapter 2
Application Layer
Computer Networking:
A Top Down Approach,
4th edition.
Jim Kurose, Keith Ross
Addison-Wesley, July
2007.
Last Lecture
DNS
Today’s Lecture
P2P architecture
Centralized Index
Decentralized Index
Query Flooding
Limited Query Flooding
Hierarchical Overlay
Chapter 3 Transport Layer
Pure P2P Architecture
 no always-on server
 Arbitrary end systems
directly communicate
 Peers are intermittently
connected and change IP
addresses
 “P2P is a class of applications
that takes advantage of
resources e.g. storage, content,
human presence, available at the
edges of the Internet”
Source: OpenP2P.com, Clay Shirky
peer-peer
Examples of P2P Technologies
File sharing Programs:
Gnutella ,Napster ,LimeWire, Kazaa
etc.
Instant messaging:
ICQ, Jabber etc
Conferencing
Netmeeting, Voice over IP (VoIP) etc
P2P File Sharing
 Alice runs P2P client
application on her
notebook computer
 Intermittently
connects to Internet;
gets new IP address
for each connection
 Registers her content
in P2P system
Asks for some music file
Application displays other peers
that have copy of that file.
 Alice chooses one of the peers,
Bob.
 File is copied from Bob’s PC to
Alice’s notebook: P2P
 While Alice downloads, other
users uploading from Alice.
How a peer determines which peers have the desired content
Three approaches for organizing and searching for contents
Different approaches are used by different P2P file sharing
systems.
P2P: Centralized Index
original “Napster” design
 When peer connects, it informs
central server:
centralized
directory server
 IP address
 Content that it is making
available
 Central Server collects info from
peers that becomes active
 Creates a centralized dynamic
2
database that maps each object
name to a set of IP addresses
 Hybrid of P2P and client-server
 File distribution is P2P
 Search is client-server
Bob
1
peers
1
3
1
1
Alice
File Sharing with Napster
3. Server searches
database. Finds song
on User C’s machine
www.napster.com
Main Server
File List:
UserC song.mp3
UserD another.mp3
…..
1. Construct Database
• Users connect to Napster Server
• Server builds up a list of available
songs and locations
User B
…
2. User A
searches for
song.mp3
4. Server informs
User A of the location
of song.mp3
User D
(Another.mp3)
User C
User A
5. User A connects to
User C and downloads
song.mp3
(Song.mp3)
P2P: Problems with Centralized Directory
 Single Point of Failure
 If directory server crashes, the
entire P2P application crashes.
 Performance Bottleneck
 Thousands of connected users
 Server must maintain a huge
database and must respond to
thousands of queries per second
 Copyright Infringement
 Easy to obtain copyrighted
material for free
 Heavy metal rock group Metallica
sued Napster for copyright
infringement in April 2000.
file transfer is
decentralized, but
locating content is
highly centralized
Decentralized Directory
Query Flooding
 Directory/Index is
fully distributed over
the community of
peers
 No central server
 Used by Gnutella
 Each peer indexes the
files it makes available
for sharing (and no
other files)
Overlay Network:
 Peers form an abstract,




logical network called an
overlay network
Edge between peer X and Y
if there’s a TCP connection
All active peers and edges
form overlay network
edge: virtual (not physical)
link
Overlay network may have
thousands of participating
peers but
 Given peer typically
connected with < 10
overlay neighbors
Query Flooding
 Query message
sent over existing
TCP connections
 Peers forward
Query message
 Query-Hit
message sent over
reverse path
Non-scalable
Significant amount of
traffic among the peers
in the underlying
network connecting the
peers
File transfer
Query
QueryHit
Query Hit
Query
Limited Query Flooding
 A peer-count field in the message is set to specific





limit (say, 7).
Each time the query message reaches a new peer,
the peer decrements the peer-count field before
forwarding the query to its overlay neighbor.
Stops forwarding the query when peer-count field
set to zero
Flooding is localized to a region of the overlay
network
Reduces the query traffic
Peer seeking the content may not be able to locate
that content.
Gnutella: Peer Joining
1.
Joining peer X must find another peer in the overlay
network


2.
3.
4.
5.
Maintain a list of peers (IP addresses ) that are often up
in the overlay network
Peer X can also contact a tracker site that maintains such
a list
Peer X sequentially attempts TCP connections with
candidate peers until connection setup with some peer Y.
Peer X sends Ping message to Peer Y that forwards this
message to his overlay neighbors (who then forward to
their neighbors….)
Peer Z on receiving Ping message respond to Peer X with
Pong message (IP address)
Peer X receives many Pong messages, and can then setup
additional TCP connections

Creating multiple edges from itself into the overlay
network
Hierarchical Overlay
 Between centralized index and query
flooding approaches
 No dedicated server for indexing files
 Super Peers: Peers with high bandwidth
connections into internet and high
availability.
 Ordinary peer is assigned as a child
to super peer.
 A new peer


Establishes a TCP connection with one of
super peers
Informs all the files it is sharing
 Super peer maintains an index of IP
addresses of children holding different
files.
 Significant more peers can be checked
for a match without creating an
excessive quantity of query traffic
ordinary peer
group-leader peer
neighoring relationships
in overlay network
Home Assignment
 What are structured P2P systems? How are they






different from unstructured P2P?
What is a Distributed Hash table? How does it work?
CHORD, PASTRY?
Bit Torrent Protocol?
Anti-Snubbing, Pipelining, Endgame mode, Peer Churn?
http://torrentfreak.com/mininova-deletes-allinfringing-torrents-and-goes-legal-091126/
http://www.brighthub.com/computing/smbsecurity/articles/48875.aspx
Chapter 3: Transport Layer
Our goals:
 Understand principles
behind transport layer
services:




Multiplexing/De-multiplexing
Reliable data transfer
Congestion control
Flow Control
 Learn about transport
layer protocols in the
Internet:





UDP: connectionless
transport
TCP: connection-oriented
transport
TCP congestion control
TCP Flow Control
Datagram Congestion
Control Protocol (DCCP)
Transport Services and Protocols
 Transport layer protocol provide
logical communication between app
processes running on different hosts
 From application’s perspective as
if the host running the process
are directly connected
 Transport protocols run in end
systems
 Not in routers
 Sender side: Breaks app
messages into segments, passes
to network layer
 Receiver side: Reassembles
segments into messages, passes
to application layer
 More than one transport protocol
available to applications
 Internet: TCP and UDP
application
transport
network
data link
physical
application
transport
network
data link
physical
Transport vs. Network layer
 Network layer: logical communication between hosts
 Transport layer: logical communication between
processes
Household Analogy:
 12 kids sending letters to 12 kids
 processes = kids
 app messages = letters in envelopes
 hosts = houses
 transport protocol = Ann and Bill
 network-layer protocol = postal service
 Transport layer relies on Network layer
Internet Transport Layer Protocols
 Internet Protocol (IP)
Best effort delivery service
 No guarantees for segment delivery
 No guarantees for orderly delivery of data
 IP is unreliable service
Extending Host-to-Host delivery to process-to-process delivery.
 Transport layer Multiplexing and De-multiplexing
UDP and TCP also provide integrity checking by including error
detection field in their segment headers.
UDP services

Process to process data delivery

Error checking
TCP Reliable data Transfer
 Congestion Control, sequence numbers, acknowledgements and
timers





Multiplexing/De-Multiplexing
 Every process has a socket which allows

Data to pass from the network to the process

Data to pass from the process to the network
 Receiving host directs an incoming transport layer
segment to appropriate socket.

Uses set of fields in the transport layer segments
 Delivering data in the transport layer segment to the
correct socket is called de-multiplexing.
 Gathering data chunks at the source host from
different sockets ,appending header information and
passing to the network layer is called multiplexing
 Household analogy
Multiplexing/De-multiplexing
Demultiplexing at rcv host:
delivering received segments
to correct socket
= socket
= process
application P3
P1
P1
application
transport
transport
network
network
link
link
physical
physical
host 1
Multiplexing at send host:
gathering data from multiple
sockets, enveloping data with
header (later used for
demultiplexing)
P2
P4
application
transport
network
link
physical
host 2
host 3
How De-multiplexing works
 Sockets have unique
identifier
 Each segment has special
field that indicate the socket
to which the segment is to be
delivered
 Source port number
 Destination port number
 Port is a 16 bit number
0 to 65535
0 to 1023 are well
known port numbers
and are reserved
32 bits
Source Port #
Dest Port #
Other Header Fields
Application
Data
(message)
Transport Layer Segment Format
Connectionless Transport:UDP






Internet transport protocol RFC 768
UDP does just about as little as a transport layer protocol can
do
Multiplexing/De-multiplexing
Error checking
“Best Effort” service, UDP segments may be:
 lost
 delivered out of order to applications
Connectionless:
 No handshaking between UDP sender, receiver
 Each UDP segment handled independently of others
Connectionless Transport:UDP
Why is there a UDP?
 No connection establishment


TCP uses a three way handshake
UDP has no delay to establish a connection
 DNS uses UDP
 No connection state at sender, receiver


TCP maintains connection state
 Congestion control parameters, sequence numbers etc.
UDP maintains no connection state
 Server can support many more active clients with UDP than over TCP
 Small segment header


20 bytes of header in TCP
Only 8 bytes of header in UDP
 No congestion control

UDP can blast away as fast as desired
UDP: Segment Structure
 The application data
occupies the data field of
the UDP segment.
 UDP header has four fields
 Each of two bytes
 Checksum
 Used by receiving host
to check for errors in
the segment
 Length
 Length of the UDP
segment
32 bits
Length, in
bytes of
UDP
segment,
including
header
source port #
dest port #
length
checksum
Application
data
(message)
UDP segment format
Connectionless (UDP) De-multiplexing
P2
SP: 6428
DP: 5775
SP: 6428
DP: 9157
client
IP: A
P1
P1
P3
SP: 9157
DP: 6428
server
IP: C
SP provides “return address”
SP: 5775
DP: 6428
Client
IP:B
UDP Checksum
Checksum is used to determine whether bits within the UDP
segment have been altered e.g. noise in the link.
Sender:
 Treat segment contents
as sequence of 16-bit
word
 Checksum: 1’s complement
of the sum of all the 16bit words.
 Sender puts checksum
value into UDP checksum
field
Receiver:
 All segments are added and
than sum is added with
sender's checksum.
 If no errors are introduced
into the packet, then clearly
the sum at the receiver will
be all 1’s.
 If receiver side checksum
contains any 0 then, error is
detected and the packet is
discarded.
Checksum Example
(16 bits segment) 0110011001100110
0101010101010101
0000111100001111
The sum of first of these 16-bits integer is:
0110011001100110
0101010101010101
1011101110111011
Adding the third one to the above sum gives
1011101110111011
0000111100001111
1100101011001010 (sum of all segments)
The checksum at sender side is : 0011010100110101 (1’s
complement).
 Now at the receiver side, again all segments are added and
sum is added with sender's checksum.
 If no error than check of receiver would be :
1111111111111111
Checksum Example
 Note

When adding numbers, a carryout from the
most significant bit needs to be added to the
result
 Example: Add two 16-bit words
1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
sum 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
checksum 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
Home Assignment
UDP Lite?
Thank You