Transcript network

Part 1: Networking Review
Goals:
 review key topics
from intro networks
course



equalize backgrounds
identify remedial
work
ease into course
Overview:
 overview
 error control
 flow control
 congestion control
 routing
 LANs
 addressing
 synthesis:


“a day in the life”
control timescales
1-1
What’s a network: “nuts and bolts” view
 network edge: millions of end-
system devices:
 pc’s workstations, servers
 PDA’s, phones, toasters
running network apps
 network core: routers,
switches forwarding data


router
server
workstation
mobile
local net
regional net
packets: packet switching
calls: circuit switching
 communication links

fiber, copper, radio, …
company
net
1-2
What’s a network protocol?
 Means (algorithm) for exchanging information
 “understanding” between two (or more) entitites
about “means” of exchanging information
 shared (agreed upon, standardized) set of rules
for communication


“how” you send/receive stuff (actions)
Format of data exchanged
1-3
What’s a protocol?
a human protocol and a computer network protocol:
Hi
TCP connection
req.
Hi
TCP connection
reply.
Got the
time?
Get http://gaia.cs.umass.edu/index.htm
2:00
<file>
time
1-4
What’s a protocol?
human protocols:
 “what’s the time?”
 “I have a question”
 introductions
… specific msgs sent
… specific actions taken
when msgs received,
or other events
network protocols:
 machines rather than
humans
 all communication
activity in Internet
governed by protocols
protocols define format,
order of msgs sent and
received among network
entities, and actions
taken on msg
transmission, receipt
1-5
A closer look at network structure:
 network edge:
applications and
hosts
 network core:
 routers

network of
networks
 access networks,
physical media:
communication links
1-6
The network edge:
 end systems (hosts):
 run application programs
 e.g., WWW, email
 at “edge of network”
 client/server model
 client host requests, receives
service from server
 e.g., WWW client (browser)/
server; email client/server
 peer-peer model:
 host interaction symmetric
 e.g.: Gnutella, KaZaA
1-7
Network edge: connection-oriented service
Goal: data transfer
between end sys.
 handshaking: setup
(prepare for) data
transfer ahead of time


Hello, hello back human
protocol
set up “state” in two
communicating hosts
 TCP - Transmission
Control Protocol

Internet’s connectionoriented service
TCP service [RFC 793]
 reliable, in-order byte-
stream data transfer

loss: acknowledgements
and retransmissions
 flow control:
 sender won’t overwhelm
receiver
 congestion control:
 senders “slow down sending
rate” when network
congested
1-8
Network edge: connectionless service
Goal: data transfer
between end systems

same as before!
 UDP - User Datagram
Protocol [RFC 768]:
Internet’s
connectionless service
 unreliable data
transfer
 no flow control
 no congestion control
App’s using TCP:
 HTTP (WWW), FTP
(file transfer), Telnet
(remote login), SMTP
(email)
App’s using UDP:
 streaming media,
teleconferencing,
Internet telephony
1-9
The Network Core
 mesh of interconnected
routers
 the fundamental
question: how is data
transferred through net?
 circuit switching:
dedicated circuit per
call: telephone net
 packet-switching: data
sent thru net in
discrete “chunks”
1-10
Network Core: Circuit Switching
End-end resources
reserved for “call”
 link bandwidth, switch
capacity
 dedicated resources:
no sharing
 circuit-like
(guaranteed)
performance
 call setup required
1-11
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
1-12
Network core: routing
Goal: move data among routers from source to dest.
datagram packet network:
circuit-switched network:
 destination address determines
 call allocated time slots
next hop
of bandwidth at each
 routes may change during session
link
 analogy: driving, asking directions
 fixed path (for call)

No notion of call state
virtual circuit network:
 packet carries tag, tag
determines next hop
 fixed path (for call) determined
at call setup time
 routers maintain little per-call
state; resources not allocated

determined at call
setup
switches maintain lots
of per call state
(what?): resource
allocation
1-13
Packet switching vs circuit switching: why?
 “reliability” – no congestion, in order data in
circuit-switching
 packet switching: better bandwidth use
 state, resources: packet switching has less
state


good: less control-plane processing resources along
the way
More dataplane (address lookup) processing
 failure modes (routers/links down):
 packet switching routing reconfigures sub-second
timescale;
 circuit-switching: more complex recovery – need to
involve all (downstream) switches on path
1-14
Access networks and physical media
Q: How to connection end
systems to edge router?
 residential access nets
 institutional access networks
(school, company)
 mobile access networks
Keep in mind:
 bandwidth (bits per second)
of access network?
 shared or dedicated?
1-15
Example access net: home network
Typical home network components:
 ADSL or cable modem
 router/firewall
 Ethernet
 wireless access
point
to/from
cable
headend
cable
modem
router/
firewall
Ethernet
(switched)
wireless
laptops
wireless
access
point
1-16
So we have seen “pieces” of network
 edge, core, links
 protocols
How do we talk about “structure” of network and its
architecture?
 layered architecture



structure allows identification, relationship of complex system’s
pieces: layered reference model for discussion
layer N builds on services provided by layer N-1
Layer N provides service to layer N+1
 physical topology, interconnection
1-17
Internet protocol stack
 application: supporting network
applications

ftp, smtp, http
application
 transport: host-host data transfer
 tcp, udp
transport
 network: routing of datagrams from
network
source to destination

ip, routing protocols
 link: data transfer between
neighboring network elements

link
physical
ppp, ethernet
 physical: bits “on the wire”
1-18
Layering: logical communication
E.g.: transport
 take data from app
 add addressing,
reliability check
info to form
“datagram”
 send datagram to
peer
 wait for peer to
ack receipt
 analogy: post
office
data
application
transport
transport
network
link
physical
application
transport
network
link
physical
ack
data
network
link
physical
application
transport
network
link
physical
data
application
transport
transport
network
link
physical
1-19
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
1-20
Internet structure: network of networks
 roughly hierarchical
 at center: “tier-1” ISPs (e.g., UUNet, BBN/Genuity,
Sprint, AT&T), national/international coverage
 treat each other as equals
Tier-1
providers
interconnect
(peer)
privately
Tier 1 ISP
Tier 1 ISP
NAP
Tier-1 providers
also interconnect
at public network
access points
(NAPs)
Tier 1 ISP
1-21
Internet structure: network of networks
 “Tier-2” ISPs: smaller (often regional) ISPs
 Connect to one or more tier-1 ISPs, possibly other tier-2 ISPs
Tier-2 ISP pays
tier-1 ISP for
connectivity to
rest of Internet
 tier-2 ISP is
customer of
tier-1 provider
Tier-2 ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
NAP
Tier 1 ISP
Tier-2 ISPs
also peer
privately with
each other,
interconnect
at NAP
Tier-2 ISP
Tier-2 ISP
1-22
Internet structure: network of networks
 “Tier-3” ISPs and local ISPs
 last hop (“access”) network (closest to end systems)
local
ISP
Local and tier3 ISPs are
customers of
higher tier
ISPs
connecting
them to rest
of Internet
Tier 3
local
local
ISP
Tier-2 ISP
ISP
ISP
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
local
NAP
Tier 1 ISP
Tier-2 ISP
local
ISP
Tier-2 ISP
local
ISP
1-23
Internet structure: network of networks
 a packet passes through many networks!
local
ISP
Tier 3
local
local
ISP
Tier-2 ISP
ISP
ISP
ISP
Tier-2 ISP
Tier 1 ISP
Try a
traceroute!
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
local
NAP
Tier 1 ISP
Tier-2 ISP
local
ISP
Tier-2 ISP
local
ISP
1-24
Part 0: Networking Review
Goals:
 review key topics
from intro networks
course
 equalize backgrounds
 identify remedial
work
 ease into course
Overview:
 overview
 error control
 flow control
 congestion control
 routing
 LANs
 addressing
 synthesis:


“a day in the life”
control timescales
1-25
Error control
 reliable point-point communication
 A generic problem: application-to-application, over path,
over link
 what’s the error model:
 bits flipped in packet?
 packets “lost?
 packets delayed or reordered?
1-26
Bit level error detection
EDC= Error Detection and Correction bits (redundancy)
D = Data protected by error checking, may include header fields
• Error detection not 100% reliable!
• protocol may miss some errors, but rarely
• larger EDC field yields better detection and correction
1-27
Parity Checking
Single Bit Parity:
Detect single bit errors
Two Dimensional Bit Parity:
Detect and correct single bit errors
Much more powerful error
detection/correction schemes:
Cyclic Redundancy Check (CRC)
0
Simple form of forward
error correction (FEC)
0
1-28
Internet checksum
Goal: detect “errors” (e.g., flipped bits) in transmitted
segment (note: used at transport layer only)
Sender:
 treat segment contents
as sequence of 16-bit
integers
 checksum: addition (1’s
complement sum) of
segment contents
 sender puts checksum
value into UDP checksum
field
Receiver:
 compute checksum of received
segment
 check if computed checksum
equals checksum field value:
 NO - error detected
 YES - no error detected. But
maybe errors nonetheless?
1-29
Recovering from lost packets
 Why are packets lost: at end system, “within”
network



Limited storage, discarded in congestion
outages: eventually reroute around failure (~sec world’s
recovery ties hopefully)
worst
acronym
dropped at end system e.g., on NIC
 ARQ: automatic request repeat
 sender puts sequence numbers on packets (why)
 receiver positively or negatively acknowledges correct
receipt of packet
 sender starts (logical) timer for each packet, timeout
and retransmits
1-30
Reference: section 3.4 in K&R
rdt3.0: channels with errors and loss
Assumption: underlying
channel can also lose
packets (data or ACKs)

checksum, seq. #, ACKs,
retransmissions will be
of help, but not enough
 Why seq #s




detect reordering
ACK, NAKing
Detect missing packet
Duplicate detection due
to retransmissions
Approach: sender waits
“reasonable” amount of
time for ACK
 retransmits if no ACK
received in this time
 if pkt (or ACK) just delayed
(not lost):
 retransmission will be
duplicate, but use of 0,1
seq. #’s already handles
this
 receiver must specify seq
# of pkt being ACKed
 requires countdown timer
1-31
rdt3.0 sender
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
L
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,1)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,0) )
timeout
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
stop_timer
stop_timer
timeout
udt_send(sndpkt)
start_timer
L
Wait
for
ACK0
Wait for
call 0from
above
L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,1) )
Wait
for
ACK1
Wait for
call 1 from
above
rdt_send(data)
rdt_rcv(rcvpkt)
L
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
start_timer
FSM specification of sender (details not important)
1-32
rdt3.0 in action
1-33
rdt3.0 in action
1-34
Part 0: Networking Review
Goals:
 review key topics
from intro networks
course
 equalize backgrounds
 identify remedial
work
 ease into course
Overview:
 overview
 error control
 flow control
 congestion control
 routing
 LANs
 addressing
 synthesis:


“a day in the life”
control timescales
1-35
Flow Control (in TCP)
flow control
sender won’t overrun
receiver’s buffers by
transmitting too much,
too fast
receiver: explicitly informs sender of (dynamically changing)
amount of free buffer space
 RcvWindow field in TCP segment
sender: keeps the amount of transmitted, unACKed data less
than most recently received RcvWindow
RcvBuffer = size or TCP Receive Buffer
receiver buffering
RcvWindow = amount of spare room in Buffer
1-36
Principles of Congestion Control
Congestion:
 informally: “too many sources sending too much
data too fast for network to handle”
 different from flow control!
 manifestations:
 lost packets (buffer overflow at routers)
 long delays (queueing in router buffers)
 a top-10 problem!
1-37
Causes/costs of congestion: scenario 1
Host A
 two senders, two
receivers
 one router,
infinite buffers
 no retransmission
Host B
lout
lin : original data
unlimited shared
output link buffers
 large delays
when congested
 maximum
achievable
throughput
1-38
Causes/costs of congestion: scenario 2
 one router, finite buffers
 sender retransmission of lost packet
Host A
Host B
lin : original
data
l'in : original data, plus
retransmitted data
lout
finite shared output
link buffers
1-39
Causes/costs of congestion: scenario 2
= l
(goodput)
out
in
 “perfect” retransmission only when loss:
 always:

l
l = lout
in
retransmission of delayed (not lost) packet makes l
in
l
(than perfect case) for same
out
larger
“costs” of congestion:
 more work (retrans) for given “goodput”
 unneeded retransmissions: link carries multiple copies of pkt
1-40
Causes/costs of congestion: scenario 3
 four senders
Q: what happens as l
in
and l increase ?
 multihop paths
 timeout/retransmit
in
Host A
lin : original data
lout
l'in : original data, plus
retransmitted data
finite shared output
link buffers
Host B
1-41
Causes/costs of congestion: scenario 3
H
o
s
t
A
l
o
u
t
H
o
s
t
B
Another “cost” of congestion:
 when packet dropped, any “upstream transmission
capacity used for that packet was wasted!
1-42
Approaches towards congestion control
Two broad approaches towards congestion control:
End-end congestion
control:
 no explicit feedback from
network
 congestion inferred from
end-system observed loss,
delay
 approach taken by TCP
Network-assisted
congestion control:
 routers provide feedback
to end systems
 single bit indicating
congestion (SNA,
DECbit, TCP/IP ECN,
ATM)
 explicit rate sender
should send at
1-43
Case study: ATM ABR congestion control
ABR: available bit rate:
 “elastic service”
RM (resource management)
cells:
 if sender’s path
 sent by sender, interspersed
“underloaded”:
 sender should use
available bandwidth
 if sender’s path
congested:
 sender throttled to
minimum guaranteed
rate
with data cells
 bits in RM cell set by switches
(“network-assisted”)
 NI bit: no increase in rate
(mild congestion)
 CI bit: congestion
indication
 RM cells returned to sender by
receiver, with bits intact
1-44
Case study: ATM ABR congestion control
 two-byte ER (explicit rate) field in RM cell
 congested switch may lower ER value in cell
 sender’ send rate thus minimum supportable rate on path
 EFCI bit in data cells: set to 1 in congested switch
 if data cell preceding RM cell has EFCI set, sender sets CI
bit in returned RM cell
1-45
TCP Congestion Control
 end-end control (no network assistance)
 transmission rate limited by congestion window
size, Congwin, over segments:
Congwin
1-46
TCP congestion control:
 “probing” for usable
bandwidth:



ideally: transmit as fast
as possible (Congwin as
large as possible)
without loss
increase Congwin until
loss (congestion)
loss: decrease Congwin,
then begin probing
(increasing) again
 two “phases”
 slow start
 congestion avoidance
 important variables:
 Congwin
 threshold: defines
threshold between two
slow start phase,
congestion control
phase
1-47
TCP Slowstart
Host A
initialize: Congwin = 1
for (each segment ACKed)
Congwin++
until (loss event OR
CongWin > threshold)
RTT
Slowstart algorithm
Host B
 exponential increase (per
RTT) in window size (not so
slow!)
 loss event: timeout (Tahoe
TCP) and/or or three
duplicate ACKs (Reno TCP)
time
1-48
TCP Congestion Avoidance: Tahoe
TCP Tahoe Congestion avoidance
/* slowstart is over
*/
/* Congwin > threshold */
Until (loss event) {
every w segments ACKed:
Congwin++
}
threshold = Congwin/2
Congwin = 1
perform slowstart
Numerous improvements: TCP Reno, SACK
1-49
Part 0: Networking Review
Goals:
 review key topics
from intro networks
course
 equalize backgrounds
 identify remedial
work
 ease into course
Overview:
 overview
 error control
 flow control
 congestion control
 routing (and network
layer services)
 LANs
 addressing
 synthesis:


“a day in the life”
control timescales
1-50
Network layer functions
 transport packet from
application
transport
network
data link
physical
sending to receiving hosts
 network layer protocols in
every host, router
three important functions:
 path determination: route
taken by packets from source
we won’t
to dest. Routing algorithms
consider this
 switching: move packets from
router’s input to appropriate
router output
 call setup: some network
architectures require router
call setup along path before
data flows
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
our focus in 653 later
1-51
Network service model
Q: What service model
for “channel”
transporting packets
from sender to
receiver?
 guaranteed bandwidth?
 preservation of inter-packet
timing (no jitter)?
 loss-free delivery?
 in-order delivery?
 congestion feedback to
sender?
CRUCIAL
question!
The most important
abstraction provided
by network layer:
? ?
?
virtual circuit
or
datagram?
1-52
Virtual circuits
“source-to-dest path behaves much like telephone
circuit”


performance-wise
network actions along source-to-dest path
 call setup, teardown for each call before data can flow
 each packet carries VC identifier (not destination host ID)
 every router on source-dest path maintains “state” for
each passing connection

transport-layer connection only involved two end systems
 link, router resources (bandwidth, buffers) may be
allocated to VC

to get circuit-like perf.
1-53
Virtual circuits: signaling protocols
 used to setup, maintain teardown VC
 used in ATM, frame-relay, X.25
 not used in today’s Internet
application
transport 5. Data flow begins
network 4. Call connected
data link 1. Initiate call
physical
6. Receive data application
3. Accept call
2. incoming call
transport
network
data link
physical
1-54
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 typically routed using destination host ID
 packets between same source-dest pair may take
different paths
application
transport
network
data link 1. Send data
physical
application
transport
network
2. Receive data
data link
physical
1-55
Datagram or VC network: why?
Internet
 data exchange among
ATM
 evolved from telephony
computers
 human conversation:
 “elastic” service, no strict
 strict timing, reliability
timing req.
requirements
 “smart” end systems
 need for guaranteed
(computers)
service
 can adapt, perform
 “dumb” end systems
control, error recovery
 telephones
 simple inside network,
 complexity inside
complexity at “edge”
network
 many link types
 different characteristics
 uniform service difficult
1-56
Routing
Routing protocol
Goal: determine “good” path
(sequence of routers) thru
network from source to dest.
Graph abstraction for
routing algorithms:
 graph nodes are
routers
 graph edges are
physical links

link cost: delay, $ cost,
or congestion level
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
 “good” path:
 typically means minimum
cost path
 other def’s possible
1-57
Routing: only two approaches used in practice
Global:
 all routers have complete topology, link cost info
 “link state” algorithms: use Dijkstra’s algorithm to find
shortest path from given router to all destinations
Decentralized:
 router knows physically-connected neighbors, link costs
to neighbors
 iterative process of computation, exchange of info with
neighbors
 “distance vector” algorithms
 a ‘self-stabilizing algorithm’ (we’ll see these later)
1-58
Distance Vector Routing Algorithm
iterative:
 continues until no
nodes exchange info.
 self-terminating: no
“signal” to stop
asynchronous:
 nodes need not
exchange info/iterate
in lock step!
distributed:
 each node
communicates only with
directly-attached
neighbors
Each node:
wait for (change in local link
cost of msg from neighbor)
recompute distance table
if least cost path to any dest
has changed, notify
neighbors
1-59
Hierarchical Routing
Our routing review thus far - idealization
 all routers identical
 network “flat”
… not true in practice
scale: with 200 million
destinations:
 can’t store all dest’s in
routing tables!
 routing table exchange
would swamp links!
administrative autonomy
 internet = network of
networks
 each network admin may
want to control routing in its
own network
1-60
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 intraAS 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
1-61
Intra-AS and Inter-AS routing
C.b
a
C
Gateways:
B.a
A.a
b
A.c
d
A
a
b
c
a
c
B
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
1-62
Intra-AS and Inter-AS routing
C.b
a
Host
h1
C
b
A.a
a
Inter-AS Internet: BGP
routing
between
B.a
A and B
Host
h2
c
A.c
a
b
B
d
c
b
A
Intra-AS routing
within AS A
Intra-AS routing
within AS B
Internet: OSPF, IS-IS, RIP
1-63
Addressing
 What’s an address?

identifier that differentiates between me and
someone else, and also helps route data to/from
me
 Real world examples of addressing?
 mailing address
 office #, floor, etc
 different “levels of addressing”

Phone#
1-64
Addressing: network layer
 IP address: 32-bit
identifier for host,
router interface
 interface: connection
between host, router
and physical link



router’s typically have
multiple interfaces
host may have multiple
interfaces
IP addresses
associated with
interface, not host,
router
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
223.1.3.2
223.1.3.1
223.1.1.1 = 11011111 00000001 00000001 00000001
223
1
1
1
1-65
IP Addressing
 IP address:
 network part (high
order bits)
 host part (low order
bits)
 What’s a network ?
(from IP address
perspective)
 device interfaces with
same network part of
IP address
 can physically reach
each other without
intervening router
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
LAN
223.1.3.1
223.1.3.2
network consisting of 3 IP networks
(for IP addresses starting with 223,
first 24 bits are network address)
1-66
IP addresses: how to get one?
Q: How does host get IP address?
 hard-coded by system admin in a file
 Wintel: control-panel->network->configuration->tcp/ip->properties

UNIX: /etc/rc.config
 DHCP: Dynamic Host Configuration Protocol:
dynamically get address: “plug-and-play”
 host broadcasts “DHCP discover” msg
 DHCP server responds with “DHCP offer” msg
 host requests IP address: “DHCP request” msg
 DHCP server sends address: “DHCP ack” msg
1-67
Part 0: Networking Review
Goals:
 review key topics
from intro networks
course
 equalize backgrounds
 identify remedial
work
 ease into course
Overview:
 overview
 error control
 flow control
 congestion control
 routing
 LANs
 addressing (cont.)
 synthesis:


“a day in the life”
control timescales
1-68
Link Layer: setting the context
1-69
Link Layer: setting the context
 two physically connected devices:
 host-router, router-router, host-host
 unit of data: frame
M
Ht M
Hn Ht M
Hl Hn Ht M
application
transport
network
link
physical
data link
protocol
phys. link
network
link
physical
Hl Hn Ht M
frame
adapter card
1-70
Link Layer Services
 Framing, link access:



encapsulate datagram into frame, adding header, trailer
implement channel access if shared medium (e.g., Ethernet)
‘physical addresses’ used in frame headers to identify
source, dest
• different from IP address!
 reliable delivery between two physically connected
devices
 flow control
 error detection/congestion
1-71
LAN Addresses and ARP
32-bit IP address:
 network-layer address
 used to get datagram to destination network
(recall IP network definition)
LAN (or MAC or physical) address:
 used to get frame from one interface to another
physically-connected interface (same network)
 48 bit MAC address (for most LANs)
burned in the adapter ROM
 WHY MAC and Internet addresses separate?


IP addresses depend on network that you’re on
MAC address in hardware makes it faster
1-72
LAN Addresses
Each adapter on LAN has unique LAN address
LAN (or MAC or physical) address:
 used to get datagram from one
interface to another physicallyconnected interface (same
network)
 48 bit MAC address (for most
LANs)
burned in the adapter ROM
1-73
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 network to which one attaches
1-74
From IP to MAC addresses
Starting at A, given IP
datagram addressed to B:
A
223.1.1.1
223.1.2.1
 look up net. address of B, find B
on same net. as A
 link layer send datagram to B
inside link-layer frame
frame source,
dest address
B’s MAC A’s MAC
addr
addr
223.1.1.2
223.1.1.4 223.1.2.9
B
223.1.1.3
datagram source,
dest address
A’s IP
addr
B’s IP
addr
223.1.3.27
223.1.3.1
223.1.2.2
E
223.1.3.2
IP payload
datagram
frame
1-75
ARP protocol
 A knows B's IP address, wants to learn physical
address of B
 A broadcasts ARP query pkt, containing B's IP
address
 all machines on LAN receive ARP query
 B receives ARP packet, replies to A with its (B's)
physical layer address
 A caches (saves) IP-to-physical address pairs until
information becomes old (times out)
 soft state: information that times out (goes
away) unless refreshed
1-76
Part 0: Networking Review
Goals:
 review key topics
from intro networks
course
 equalize backgrounds
 identify remedial
work
 ease into course
Overview:
 overview
 error control
 flow control
 congestion control
 routing
 LANs
 addressing (cont.)
 synthesis:


“a day in the life”
control timescales
1-77
Synthesis: which protocols involved?
www browser downloads page
1-78
Protocols involved in http GET
 User types ina URL, what happens?
 DNS: translate hostname to IP address
 Via DHCP, source has IP address of DNS server (suppose
DNS server is on same network segment)
 Create DNS query, pass to UDP, create UDP segment
containing DNS query, pass to IP on host
 Look in routing table (DHCP gave me default router),
recognize that DNS server is on same network.
 Use ARP to determine MAC address of DNS server
 Ethernet used to send frame to DNS server on physically
connected “wire” (network segment, ethernet “cable”)
 On DNS machine ethernet->IP->UDP. UDP looks at dest
port #, sees it is DNS, passes DNS query to DNS
application. (assume dns knows IP addresses of hostname
in original URL - address found!)
 DNS server sends UDP reply back to orginating machine
1-79
Protocols involved in http GET
 So: browser now has IP address of GET destination server
 Need to establish TCP connection to server, TCP connection
establishment sends SYN packet (will get an SYNACK back,
eventuallly….)
 SYN packet down to network layer, with IP address of server.
Since server destined “off my network”, SYN packet will need
to go through router.
 Look in routing table, see that destined off network, need to
send to “default gateway” (to get off my net)
 Use ARP to get MAC address of default gateway, create
Ethernet frame with gateway MAC address, containing IP
packet containing TCP segment, containing SYN
 It is IMPORTANT to realize that while the Ethernet frame
containing the IP datagram that contains the TCP SYN has as
its destination address the MAC address of the router, the IP
datagram (still) has as its destination address the IP address
of the remote www server
1-80
Protocols involved in http GET

Router receives Ethernet frame (frame is addressed to router), looks at IP
datagram and sees that IP datagram is not addressed to itself (IP datagram
is addressed to server). So router knows that it must forward the IP
datagram to the next hop router along the path to the eventual destination.
 Router checks routing tables (table values populated using intra,






possibly inter-, domain routing protocols like OSPF, RIP, IS-IS,
BGP (inter). Get IP address of next hop router.
Router puts IP packets in Ethernet frame, Ethernet frame
addressed to next hop router. MAC address of next hope router
determined by ARP. Frame sent to next hop router.
Network management shoehorn: arriving packets at interface
cause SNMP MIB variable for # arriving IP datagrams to be
incremented
…. This forwarding continues until IP datagram contain TCP SYN
eventually arrives at destination, gaia.cs.umass.edu (128.119.30.30)
Up to IP, demultiplex from Ethernet to IP using Ethernet TYPE
field to identify IP as upper layer protocol
From IP to TCP using protocol field of IP datagram,
SYN packet arrives at gaia TCP (FINALLY)
1-81
Protocols involved in http GET
 So …. SYN has arrived at gaia. Gaia sends back SYNACK to
intial sender
 Gaia gets synack, ready to send data.
 HTTP GET message now sent to gaia.cs.umass.edu in a TCP
segment, in IP datagram, Ethernet frame, along hops to
gaia.cs.umass.edu
 GET arrives! REPLY formulated by http server … and sent
1-82