Transcript Part I: Introduction

Networking Overview
Introduction
1-1
Introduction
Introduction
1-2
What’s a protocol?
a human protocol and a computer network protocol:
Hi
TCP connection
req
Hi
TCP connection
response
Got the
time?
Get http://www.awl.com/kurose-ross
2:00
<file>
time
Q: Other human protocols?
Introduction
1-3
The network edge:
 end systems (hosts):



run application programs
e.g. Web, email
at “edge of network”
 client/server model


client host requests, receives
service from always-on server
e.g. Web browser/server; email
client/server
 peer-peer model:


minimal (or no) use of
dedicated servers
e.g. Gnutella, KaZaA
Introduction
1-4
The Network Core
 mesh of interconnected
routers
 the fundamental question:
how is data transferred
through net?
 circuit switching:
dedicated circuit per
call (telephone call)
 packet-switching: data
sent thru net in discrete
“chunks” (internet)
Introduction
1-5
Network Core: Packet Switching
each end-end data stream divided into
packets
 user A, B packets share network
resources
 each packet uses full link bandwidth
 resources used as needed
Bandwidth division into “pieces”
Dedicated allocation
Resource reservation
resource contention:
 aggregate resource
demand can exceed
amount available
 congestion: packets
queue, wait for link use
 store and forward:
packets move one hop
at a time
 transmit over link
 wait turn at next link
Introduction
1-6
Internet protocol stack
 application: supporting network applications

FTP, SMTP, HTTP
 transport: host-host data transfer

TCP, UDP
 network: routing of datagrams from source to
destination

application
IP, routing protocols
 link: data transfer between neighboring network
transport
network
elements

PPP, Ethernet
 physical: bits “on the wire”
link
physical
Introduction
1-7
Layering: physical communication
data
application
transport
network
link
physical
application
transport
network
link
physical
network
link
physical
application
transport
network
link
physical
data
application
transport
network
link
physical
Introduction
1-8
Application Layer
Introduction
1-9
Network applications: some jargon
Process: program running
user agent: interfaces with
within a host.
user “above” and
network “below”.
 within same host, two
processes communicate  implements user
using interprocess
interface & applicationcommunication (defined
level protocol
by OS)
 Web: browser
 E-mail: mail reader
 processes running in
 streaming audio/video:
different hosts
media player
communicate with an
application-layer protocol
Introduction
1-10
Applications and application-layer protocols
Application: communicating, distributed
processes



e.g., e-mail, Web, P2P file sharing,
instant messaging
running in end systems (hosts)
exchange messages to implement
application
application
transport
network
data link
physical
Application-layer protocols




one “piece” of an app
define messages exchanged by
apps and actions taken
use communication services
provided by lower layer protocols
(TCP, UDP)
For example, SMTP
application
transport
network
data link
physical
application
transport
network
data link
physical
Introduction
1-11
Client-server paradigm (“usual” approach)
Typical network app has two
pieces: client and server
application
transport
network
data link
physical
Client:
request
 initiates contact with server
(“speaks first”)
 typically requests service from
server,
 Web: client implemented in
browser; e-mail: in mail reader
Server:
reply
application
transport
network
data link
physical
 provides requested service to client
 e.g., Web server sends requested Web
page, mail server delivers e-mail
Hosts: both clients and servers
Introduction
1-12
Addressing processes:
 For a process to receive
messages, it must have
an identifier
 Every host has a unique
32-bit IP address
 Q: does the IP address
of the host on which the
process runs suffice for
identifying the process?
 A: No, many processes
can be running on same
host
 Identifier includes both
the IP address and port
numbers associated
with the process on the
host.
 “Well-known” port
number examples:


HTTP server: 80
Mail server: 25
 More on this later
Introduction
1-13
Internet transport protocols services
TCP service:
 connection-oriented: setup





required between client and server
processes
reliable transport between sending
and receiving process
flow control: sender won’t
overwhelm receiver
congestion control: throttle sender
when network overloaded
full duplex: simultaneous 2-way
communication
does not provide: timing, minimum
bandwidth guarantees
UDP service:
 unreliable data transfer
between sending and
receiving process
 does not provide:
connection setup,
reliability, flow control,
congestion control,
timing, or bandwidth
guarantee
Q: Why is there a UDP?
Introduction
1-14
HTTP overview
HTTP: HyperText Transfer
Protocol
 Web’s application layer
protocol
 client/server model
 client: browser that
requests, receives,
“displays” Web objects
 server: Web server
sends objects in
response to requests
 HTTP 1.0: RFC 1945
 HTTP 1.1: RFC 2068
(backward compatible)
PC running
Navigator
Server
running
Apache Web
server
Mac running
Explorer
Introduction
1-15
Cookies: keeping “state”
client
Cookie file
server
usual http request msg
usual http response +
ebay: 8734
Cookie file
amazon: 1678
ebay: 8734
Set-cookie: 1678
usual http request msg
cookie: 1678
usual http response msg
server
creates ID
1678 for user
cookiespecific
action
one week later:
Cookie file
amazon: 1678
ebay: 8734
usual http request msg
cookie: 1678
usual http response msg
cookiespectific
action
Introduction
1-16
Cookies (continued)
aside
What cookies can bring:
 authorization
 shopping carts
 recommendations
 user session state (Web
e-mail)
Cookies and privacy:
 cookies permit sites to
learn a lot about you
 you may supply name
and e-mail to sites
 search engines use
redirection & cookies to
learn yet more
 advertising companies
obtain info across sites
Introduction
1-17
Mail access protocols
SMTP
SMTP
user
agent
sender’s mail
server
access
protocol
user
agent
receiver’s mail
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.

Introduction
1-18
Sample SMTP interaction
S:
C:
S:
C:
S:
C:
S:
C:
S:
C:
C:
C:
S:
C:
S:
220 hamburger.edu
HELO ca.gov
250 Hello ca.gov, pleased to meet you
MAIL FROM: <[email protected]>
250 [email protected]... Sender ok
RCPT TO: <[email protected]>
250 [email protected] ... Recipient ok
DATA
354 Enter mail, end with "." on a line by itself
It is my pleasure to inform you that
you are terminated
.
250 Message accepted for delivery
QUIT
221 hamburger.edu closing connection
Introduction
1-19
DNS: Domain Name System
People: many identifiers:

SSN, name, passport #
Internet hosts, routers:


IP address (32 bit) - used
for addressing datagrams
“name”, e.g.,
gaia.cs.umass.edu used by humans
Q: map between IP
addresses and name ?
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 applicationlayer protocol
 complexity at network’s “edge”
Introduction
1-20
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 NSI Herndon, VA
c PSInet Herndon, VA
d U Maryland College Park, MD
g DISA Vienna, VA
h ARL Aberdeen, MD
j NSI (TBD) Herndon, VA
k RIPE London
i NORDUnet Stockholm
m WIDE Tokyo
e NASA Mt View, CA
f Internet Software C. Palo Alto,
CA
b USC-ISI Marina del Rey, CA
l ICANN Marina del Rey, CA
13 root name
servers worldwide
Introduction
1-21
P2P file sharing
 Alice chooses one of
Example
 Alice runs P2P client
application on her notebook
computer
 Intermittently connects to
Internet; gets new IP
address for each connection
 Asks for “Hey Jude”
 Application displays other
peers that have copy of Hey
Jude.
the peers, Bob.
 File is copied from
Bob’s PC to Alice’s
notebook: HTTP
 While Alice downloads,
other users uploading
from Alice.
 Alice’s peer is both a
Web client and a
transient Web server.
All peers are servers =
highly scalable!
Introduction
1-22
P2P: centralized directory
original “Napster” design
1) when peer connects, it
informs central server:


Bob
centralized
directory server
1
peers
1
IP address
content
2) Alice queries for “Hey
Jude”
3) Alice requests file from
Bob
3
1
2
1
Alice
Introduction
1-23
P2P: decentralized directory
Each peer is either a
group leader or
assigned to a group
leader.
 Group leader tracks the
content in all its
children.
 Peer queries group
leader; group leader
may query other group
leaders.
 KaZaA uses this idea
ordinary peer
group-leader peer
neighoring relationships
in overlay network
Introduction
1-24
P2P: Query flooding
 Gnutella
 Send query to neighbors
 no hierarchy
 Neighbors forward query
 use bootstrap node to learn
 If queried peer has object,
about others
 join message
it sends message back to
querying peer
join
Gnutella network visualization:
http://www.ececs.uc.edu/~mjovanov/Research/gnutella.html
Introduction
1-25
Transport Layer
Introduction
1-26
Internet transport-layer protocols
 reliable, in-order delivery
(TCP)



congestion control
flow control
connection setup
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
 unreliable, unordered
delivery: UDP

no-frills extension of “besteffort” IP
 services not available:
 delay guarantees
 bandwidth guarantees
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
Introduction
1-27
TCP: Overview
 point-to-point
 one sender, one receiver
RFCs: 793, 1122, 1323, 2018, 2581
 full duplex data

 reliable, in-order byte
steam

no “message boundaries”
 pipelined
 TCP congestion and flow
control set window size

 connection-oriented

socket
door
application
reads data
TCP
send buffer
TCP
receive buffer
handshaking (exchange of
control msgs) init’s sender,
receiver state before data
exchange
 flow control
 send & receive buffers
application
writes data
bi-directional data flow in
same connection
MSS: maximum segment
size

sender will not overwhelm
receiver
 congestion control
socket
door

network will not be
overwhelmed (fairness)
segment
Introduction
1-28
TCP 3-way handshake
Server must maintain state…
SYN
SYNACK
Get http://www.awl.com/kurose-ross
<file>
time
Introduction
1-29
Network Layer
Introduction
1-30
Network layer functions
 transport packet from sending to
receiving hosts
 network layer protocols in every
host and router
three important functions:
 path determination: route taken by
packets from source to dest.
routing algorithms
 forwarding: move packets from
router’s input to appropriate router
output
 call setup: some network
architectures require router call
setup along path before data flows
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
Introduction
1-31
Datagram networks: the Internet model
 no call setup at network layer
 routers: no state about end-to-end connections

no network-level concept of “connection”
 packets forwarded using destination host address

Packets in same “transmission” may take different paths
 best effort
application
transport
network
data link 1. Send data
physical
application
transport
2. Receive data network
data link
physical
Introduction
1-32
Hierarchical Routing
 aggregate routers into
regions, “autonomous
systems” (AS)
 routers in same AS run
same routing protocol


“intra-AS” routing
protocol
routers in different AS
can run different intra-AS
routing protocol
gateway routers
 special routers in AS
 run intra-AS routing protocol
with all other routers in AS
 also responsible for routing
to destinations outside AS
 run inter-AS routing
protocol with other
gateway routers
Introduction
1-33
Intra-AS and Inter-AS routing
C.b
Gateway routers
B.a
A.a
a
b
A.c
C
a
d
A
b
c
a
B
c
b
•perform inter-AS
routing amongst
themselves
•perform intra-AS
routers with other
routers in their AS
network layer
inter-AS, intra-AS
routing in
gateway A.c
link layer
physical layer
Introduction
1-34
The Internet Network layer
Host, router network layer functions:
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
forwarding
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
Introduction
1-35
IP Addressing: introduction
 IP address: 32-bit
identifier for host,
router interface
 interface: connection
between host/router
and physical link



223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
router’s typically have
223.1.3.2
223.1.3.1
multiple interfaces
host may have multiple
interfaces
IP addresses associated
223.1.1.1 = 11011111 00000001 00000001 00000001
with each interface
223
1
1
Introduction
1
1-36
Getting a datagram from source to dest.
forwarding table in A
Dest. Net. next router Nhops
misc
data
fields 223.1.1.1 223.1.2.2
223.1.1
223.1.2
223.1.3
Starting at A, dest. E:
 look up network address of E in





forwarding table
E on different network
 A, E not directly attached
routing table: next hop router to
E is 223.1.1.4
link layer sends datagram to
router 223.1.1.4 inside linklayer frame
datagram arrives at 223.1.1.4
continued…..
A
223.1.1.4
223.1.1.4
1
2
2
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
B
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
Introduction
1-37
Getting a datagram from source to dest.
forwarding table in router
misc
data
fields 223.1.1.1 223.1.2.2
Arriving at 223.1.1.4,
destined for 223.1.2.2
 look up network address of E in
router’s forwarding table
 E on same network as router’s
interface 223.1.2.9
 router, E directly attached
 link layer sends datagram to
223.1.2.2 inside link-layer frame
via interface 223.1.2.9
 datagram arrives at 223.1.2.2
Dest. Net router Nhops interface
223.1.1
223.1.2
223.1.3
A
-
1
1
1
223.1.1.4
223.1.2.9
223.1.3.27
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
B
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
E
223.1.3.2
Introduction
1-38
IP Fragmentation & Reassembly
 network links have MTU
(max.transfer size) - largest
possible link-level frame.
 different link types,
different MTUs
 large IP datagram divided
(“fragmented”) within net
 one datagram becomes
several datagrams
 “reassembled” only at
final destination
 IP header bits used to
identify, order related
fragments
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
Introduction
1-39
IP Fragmentation and Reassembly
Example
 4000 byte datagram
 MTU = 1500 bytes
length ID fragflag
=4000 =x
=0
offset
=0
One large datagram becomes
several smaller datagrams
length ID fragflag
=1500 =x
=1
offset
=0
length ID fragflag offset
=1500 =x
=1
=1480
length ID fragflag offset
=1040 =x
=0
=2960
Introduction
1-40
ICMP: Internet Control Message Protocol
 used by hosts, routers,
gateways to communication
network-level information
 error reporting:
unreachable host,
network, port, protocol
 echo request/reply (used
by ping)
 network-layer “above” IP:
 ICMP msgs carried in IP
datagrams
 ICMP message: type, code
plus first 8 bytes of IP
datagram causing error
Type
0
3
3
3
3
3
3
4
Code
0
0
1
2
3
6
7
0
8
9
10
11
12
0
0
0
0
0
description
echo reply (ping)
dest. network unreachable
dest host unreachable
dest protocol unreachable
dest port unreachable
dest network unknown
dest host unknown
source quench (congestion
control - not used)
echo request (ping)
route advertisement
router discovery
TTL expired
bad IP header
Introduction
1-41
DHCP client-server scenario
DHCP server: 223.1.2.5
DHCP discover
arriving
client
src : 0.0.0.0, 68
dest.: 255.255.255.255,67
yiaddr: 0.0.0.0
transaction ID: 654
DHCP offer
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 654
Lifetime: 3600 secs
DHCP request
time
src: 0.0.0.0, 68
dest:: 255.255.255.255, 67
yiaddrr: 223.1.2.4
transaction ID: 655
Lifetime: 3600 secs
DHCP ACK
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 655
Lifetime: 3600 secs
Introduction
1-42
NAT: Network Address Translation
rest of
Internet
local network
(e.g., home network)
10.0.0/24
10.0.0.1
10.0.0.4
10.0.0.2
138.76.29.7
10.0.0.3
All datagrams leaving local
network have same single source
NAT IP address: 138.76.29.7,
different source port numbers
Datagrams with source or
destination in this network
have 10.0.0/24 address for
source, destination (as usual)
Introduction
1-43
Intra-AS Routing
 Also known as Interior Gateway Protocols (IGP)
 Most common Intra-AS routing protocols:

RIP: Routing Information Protocol

OSPF: Open Shortest Path First

IGRP: Interior Gateway Routing Protocol (Cisco
proprietary)
Introduction
1-44
Inter-AS routing in the Internet: BGP
R4
R5
R3
BGP
AS1
AS2
(RIP intra-AS
routing)
(OSPF
intra-AS
routing)
BGP
R1
R2
AS3
(OSPF intra-AS
routing)
Figure 4.5.2-new2: BGP use for inter-domain routing
Introduction
1-45
Why different Intra- and Inter-AS routing ?
Policy:
 Inter-AS: admin wants control over how its traffic routed, who routes
through its net.
 Intra-AS: single admin, so no policy decisions needed
Scale:
 Hierarchical routing saves table size, reduced update traffic
Performance:
 Intra-AS: can focus on performance
 Inter-AS: policy may dominate over performance
Introduction
1-46
Link Layer
Introduction
1-47
Link Layer: Introduction
“link”
Some terminology:
 hosts and routers are nodes
(bridges and switches too)
 communication channels that
connect adjacent nodes along
communication path are links



wired links
wireless links
LANs
 2-PDU is a frame, encapsulates
datagram
data-link layer has responsibility of
transferring datagram from one node
to adjacent node over a link
Introduction
1-48
Adaptors Communicating
datagram
rcving
node
link layer protocol
sending
node
frame
frame
adapter
adapter
 receiving side
“adaptor” (aka NIC)
 looks for errors, rdt, flow
control, etc
 Ethernet card, PCMCI card,
 extracts datagram, passes
802.11 card
to rcving node
 sending side:
 encapsulates datagram in a  adapter is semiautonomous
frame
 adds error checking bits,
 link & physical layers
rdt, flow control, etc.
 link layer implemented in
Introduction
1-49
Multiple Access protocols
 single shared broadcast channel
 two or more simultaneous transmissions by nodes:
interference

only one node can send successfully at a time
multiple access protocol
 distributed algorithm that determines how nodes share
channel, i.e., determine when node can transmit
 communication about channel sharing must use channel
itself (in-band signalling)
Introduction
1-50
MAC Protocols: a taxonomy
Three broad classes:
 Channel Partitioning


divide channel into smaller “pieces” (time slots, frequency,
code)
allocate piece to node for exclusive use
 Random Access
 channel not divided, allow collisions (data ruined)
 “recover” from collisions
 Taking turns
 tightly coordinate shared access to avoid collisions
Introduction
1-51
Random Access Protocols
 When node has packet to send


transmit at full channel data rate R.
no a priori coordination among nodes
 two or more transmitting nodes -> collision (data lost)
 Random multiple access protocol specifies


how to detect collisions
how to recover from collisions (e.g., via delayed retransmissions)
 Examples of random multiple access protocols



slotted ALOHA
ALOHA
CSMA, CSMA/CD, CSMA/CA (used in Ethernet)
Introduction
1-52
CSMA
Carrier Sense Mulitple Access (CSMA): listen before
transmitting
 If channel is idle, transmit entire frame
 If channel is busy, wait
 Human analogy: don’t interrupt others!
Introduction
1-53
CSMA collisions
spatial layout of nodes
collisions can still occur:
propagation delay means
two nodes may not hear
each other’s transmission
collision: entire packet
transmission time wasted
note: distance and propagation
delay in determining collision
probability
Introduction
1-54
CSMA/CD (Collision Detection)
CSMA/CD: carrier sensing, deferral as in CSMA
collisions detected within short time
 colliding transmissions aborted, reducing channel
wastage

 collision detection
 easy in wired LANs: measure signal strengths,
compare transmitted, received signals
 difficult in wireless LANs: receiver shut off while
transmitting
 human analogy: the polite conversationalist
Introduction
1-55
CSMA/CD collision detection
Introduction
1-56
Ethernet uses CSMA/CD
 No slots
 adapter doesn’t transmit if
it senses that some other
adapter is transmitting, that
is, carrier sense
 transmitting adapter aborts
when it senses that
another adapter is
transmitting, that is,
collision detection
 Before attempting a
retransmission, adapter
waits a random time,
that is, random access
Introduction
1-57
LAN Addresses and ARP
Each adapter on LAN has unique LAN address
Introduction
1-58
LAN Address (more)
 MAC address allocation administered by IEEE
 manufacturer buys portion of MAC address space (to assure
uniqueness)
 Analogy:
(a) MAC address: like Social Security Number
(b) IP address: like postal address
 MAC flat address => portability

can move LAN card from one LAN to another
 IP hierarchical address NOT portable

depends on IP network to which node is attached
Introduction
1-59
ARP: Address Resolution Protocol
Question: how to determine
MAC address of node
knowing node’s IP address?
 Each IP node (host or router)
on LAN has ARP table
 ARP Table: IP/MAC address
mappings for some LAN
nodes
< IP address; MAC address; TTL>

TTL (Time To Live): time after
which address mapping will
be forgotten (typically 20 min)
Introduction
1-60
ARP protocol
 A wants to send datagram to B,
and A knows B’s IP address.
 Suppose B’s MAC address is
not in A’s ARP table.
 A broadcasts ARP query packet,
containing B's IP address
 all machines on LAN
receive ARP query
 B receives ARP packet, replies
to A with its (B's) MAC address

frame sent to A’s MAC address
(unicast)
 A caches (saves) IP-to-MAC
address pair in its ARP table
until information becomes
old (times out)
 soft state: information
times out (goes away)
unless refreshed
 ARP is “plug-and-play”:
 nodes create their ARP
tables without
intervention from net
administrator
Introduction
1-61
ARP cache poisoning
 ARP is stateless
 ARP table is updated whenever ARP reply
received, even if no ARP request was sent
111.111.111.001
AA-AA-AA-AA-AAAA
111.111.111.002
BB-BB-BB-BB-BB-BB
ARP cache
111.111.111.002
LAN
BB-BB-BB-BB-BBBB
111.111.111.001
AA-AA-AA-AA-AA-AA
ARP cache
Introduction
1-62
ARP Poisoning (continued)
111.111.111.003
CC-CC-CC-CC-CC-CC
LAN
111.111.111.001
111.111.111.002
AA-AA-AA-AA-AAAA
CC-CC-CC-CC-CC-CC
111.111.111.002
BB-BB-BB-BB-BBBB
111.111.111.001
CC-CC-CC-CC-CC-CC
Introduction
1-63
Summary comparison
hubs
bridges switches routers
Collision
isolation
no
yes
yes
yes
Broadcast
isolation
no
no
no
yes
plug & play
yes
yes
yes
no
optimal
routing
cut
through
no
no
no
yes
yes
no
yes
no
Introduction
1-64