Transcript Week 10

About the Final Exam
 Saturday June 11 3:00-6:00PM, 2444 BH
 Material to be covered
 Chapters 2 & 3: 20-30%
 Chapter 4 (4.4-4.8), Chapter 5 (5.1-5.7), Chapter 6 (6.3, 6.5):
70-80%
 Closed book, closed notes
 You can bring 2 (8x11) "cheat sheets" into the final
exam (double-side OK)
 New office hour 10:00AM-1:00PM Saturday 6/11

6/5/05
No office hour Wednesday 6/8
1
CS118/Spring05
A Day in the Life of an HTTP Query
Brower
application
Client/server
paradigm
Web server
application
HTTP
2.DNS query
1.HTTP
Socket interface
3.TCP
multiplexing
demultiplexing
4.IP
5.Ethernet
Socket interface
TCP
IP
Ethernet
Transport
protocols
Switch
IP router
Running routing protocol
6/5/05
2
CS118/Spring05
A Bottom-up Roadmap
 Physical layer: know how to calculate the delay of
sending packets from one node to another
Transmission rate (bandwidth)
 Transmission delay
 Propagation delay

 Link layer: move data between two directly connected
nodes
Error checking schemes: parity, checksum, CRC
 Framing, byte stuffing
 Multi-access protocols: Aloha, Ethernet (CSMA/CD), 802.11
(CSMA/CA, RTS-CTS)
 Switch self-learning scheme

 Network layer
 IP address structure (subnet, CIDR)
 Routing: distance vector, link state; broadcast, multicast, IGMP
 IP header
6/5/05
3
CS118/Spring05
On top of network layer
 Transport layer
 UDP,
TCP: header format
 TCP: connection set-up & tear-down, congestion
control, retransmission timer setting
 reliable data delivery
• Stop-and-go
• Go-back-N
• Selective-repeat
 Application layer protocols
6/5/05
4
CS118/Spring05
Computer Networking: the overall picture
 What is packet switching?
 Cut data into chunks, sent in a "store-and-forward" way
 statistical multiplexing  queueing delay, potential losses
 why packet switching?
Efficient resource
sharing
Flexible delivery
Packet
(carries
destination
address)
Switch 1
Switch 2
 What’s in a packet:
header
data
 header: contains all the information needed for data delivery
 Why layered network protocol architecture?
 Divide and conquer
6/5/05
5
CS118/Spring05
Layered protocol implementation
A protocol defines:
 the format of message exchanged between
peer entities
 the actions taken on receipt of the message
Ethernet frame
DATA
header
What’s in the header:
all the information,and
only the information
that’s needed for the
protocol’s functionality
tail
IP packet
DATA
IP hdr
TCP packet
TCP hdr
DATA
DATA
6/5/05
6
CS118/Spring05
Multi-access protocol
 Aloha/Slotted Aloha
Q: for a network with 3 nodes, what is the probability
that a given node sends successfully without collision?
 Ethernet
 1-persistent
CSMA/CD
Q: Why need collision detection?
 Collision resolution: how exponential backup works
 802.11 wireless LAN
 CSMA/CA
 RTS-CTS
6/5/05
7
CS118/Spring05
Ethernet: Why Collision Detection
t2
t3
Time saved
from
collection
detection
6/5/05
8
CS118/Spring05
Wireless LAN: Collision Avoidance
802.11 sender
1 if sense channel idle for DIFS then
transmit entire data frame (no CD)
2 if sense channel busy: start random
backoff timer
3 timer counts down while channel idle
4 when timer expires: transmit entire frame
- if no ACK, increase random backoff
interval, go to step 3
802.11 receiver
receiver
DIFS
data
SIFS
ACK
if frame received OK
- return ACK after SIFS
Q: How does waiting for a random time
period help collision avoidance?
6/5/05
sender
9
DIFS: distributed inter-frame spacing
SIFS: short inter-frame spacing
CS118/Spring05
MAC Address and ARP
 Compare MAC address with IP address
 The detailed operations of ARP
 How many steps in sending a packet from one host to
another located on a different network?
Find out whether destination on the same network
 ARP if needed
 Encapsulate IP packet in a link layer protocol and send to next
hop

How to connect multiple Ethernets
 Compare hubs, switches, and routers
 Switch self-learning algorithm
6/5/05
10
CS118/Spring05
Switch Learning Example
B3
A
B1
C
B2
Q: Assuming all the switches'
forwarding tables are empty,
show the forwarding tables
for switches B1-B4 after the
following transmissions:
1. A sends to C
B4
D
2. C sends to A
3. D sends to C
Solution:
•When A sends to C, all the switches see the packet and learn where A is.
•When C sends to A, the packet is routed directly to A, and B4 does not
learn where C is.
6/5/05
•When D sends to C, the packet is routed by B2 towards B3, and B1 does
not learn where D is.
11
CS118/Spring05
The picture of the world according to IP
Various application protocols
TCP
UDP
RDP
SCTP
transport
(end-to-end)
IP
internet layer
Various network
technologies
Ethernet wireless FDDI
6/5/05
12
dialup
ATM
CS118/Spring05
The picture of the world according to IP
all hosts connected to physical networks (subnet)
all subnets interconnected by IP routers
receive and forward packets between subnets
at subnet level a router sends/received data in exactly
the same way as a host
IP assigns globally unique addresses to all
reachable interfaces (connecting to either hosts or
routers)
datagram delivery between these interfaces
routers
run routing protocols to figure out the next hop
to forward each IP packet towards its destination
6/5/05
13
CS118/Spring05
IP Packet Header
0
4
8
type-of-service
identification
time-to-live
31
total length
flags
protocol
fragment offset
IP header checksum
source address
destination address
options (variable length)
Basic header
vers. # HLen
16
padding
data
What is the purpose for each header field?
For example, why do we need TTL field?
6/5/05
14
CS118/Spring05
IP and Below
 IP delivers packets from host to host, possibly
through a chain of IP routers
 An
IP address uniquely identifies an attachment
interface
 each IP router looks up the forwarding table to
determine the next subnet to forward the packet to
 physical networks do the real work of getting
packets from one IP node to the next
 packets
are encapsulated and de-capsulated when
crossing physical network boundaries
 To map IP address to network MAC address: ARP
6/5/05
15
CS118/Spring05
Interconnection by encapsulation
 IP packets are wrapped in a network’s protocol to travel
through that network
 A router un-wraps the packet to see its IP destination
address
on the same network: send to destination directly
 on a diff. network: send to next hop router

Router-1
H1
IP
data IP
IP
data IP
ETH
ETH
data
R2
FDDI
IP
FDDI
data IP
PPP
data IP FDDI
IP Eth
Q: a packet traverses 4 routers from source to destination, how many
time does it get encapsulated and de-capsulated along the way?
6/5/05
16
CS118/Spring05
IP packet fragmentation details
 all fragments of the same packet carry the same identifier
 all fragments except the last one have the “MF” bit set
 fragment offset points to the first byte of the fragment
Example:
1st fragment: identifier=8FB3; MF=1; offset=0
2nd fragment: identifier=8FB3; MF=1; offset=64
3rd fragment: identifier=8FB3; MF=0; offset=128
data=1300B
data frag-3 IP Hd
(276B)
data frag-2 IP Hd
(512B)
IP header
data frag-1 IP Hd
(512B)
Rest of IP header
Identifier: 8FB3
6/5/05
DFMF fragment offset (13 bits)
17
CS118/Spring05
IP packet reassembly at destination host
 use identifier and offset to put the pieces back
together
 the
offset plus the packet length tells whether there are
holes missing in the middle
 the last fragment is indicated by MF=0
Ver
TOS
8FB3
276
000 128
rest of IP header
data
Ver
TOS
8FB3
532
001 64
rest of IP header
data
Ver
TOS
8FB3
532
001 0
rest of IP header
data
Destination
host
• Upon receiving the first fragment of an IP packet,
destination host sets a reassembly timer
• when the timer goes off and the destination host still has not
received all the pieces, it drops all the received pieces.
6/5/05
18
CS118/Spring05
IP address structure
 4 bytes
 Hierarchical ! (i.e. not flat, as MAC addresses)
 network ID
 host ID
 What is the boundary between these 2 parts:
 Classful
address: classes A, B, C
 Subnetting
 Classless Inter-Domain Routing (CIDR)
6/5/05
19
CS118/Spring05
Subnetting
 subnetting: Add another (hidden) level to address
hierarchy
 Subnet
is known only at the local site
 Use part of the original host ID portion as netID
4 byte
Network-ID
host-ID
11111111111111111111110000000000
Network ID
 Subnet mask: defines portion of the address
considered as “network ID” by the local site
6/5/05
20
CS118/Spring05
CIDR: Classless InterDomain Routing
assign network addresses by blocks of contiguous
IP addresses, in a form of
<IP address, mask>
mask
identifies block size, must be power of 2
example: SmartDesign Inc. got 4 x 2^8 address blocks
192.4.16.0192.4.19.255,
<192.4.16.0, 255.255.252.0>, or 192.4.16/22
11000000000001000001000000000000 11000000000001000001001111111111
192
4
16
192
0
4
19
255
11111111111111111111110000000000
22 bits of prefix
6/5/05
255
21
255
252
0
CS118/Spring05
CIDR and subnetting example
Global Internet
SmartDesign
Network#
mask
next-hop
192.4.18 255.255.255.128
C
……
………..
M
A
Look up IP addr. 192.4.18.15
B
192.4.18.0/25
Network# next-hop
192.4.16.0
B
192.4.0.0
M
C
11000000000001000001001000001111
11000000000001000001000000000000
11000000000001000000000000000000
192
6/5/05
.
4
.
192.4.18.15
11111111111111111111111110000000
11000000000001000001001000001111
192
.
4
.
18
22
CS118/Spring05
Following an IP packet from source to dest.
Source host A first uses subnet mask M to figure out whether
dest. host is on the same network
1. Dest. = host B: find B's MAC address, send data
2. dest. = host C, A sends packet to its default router
 the
router strips off Ethernet header, consult its IP forwarding table
to find next hop
3. Dest. = D:
data IP
B
A
data IP
D
C
data IP Eth
data IP WAN
router
WAN 78.0.0.0
R2
223.240.129.0
data IP
6/5/05
23
CS118/Spring05
IPv6
 What header fields are available in both IPv4 and IPv6?
 What are the new fields in IPv6 header? Why do we
need them?
 Comparison between IPv4 and IPv6
Q: Does IPv6 support fragmentation? If not, how does
IPv6 handle the case of small-MTU network?
Transition from IPv4 to IPv6
 how does tunneling work?
6/5/05
24
CS118/Spring05
IPv6 header format
Flow Label
Version Priority
Payload Length
Next Header
Hop Limit
Source Address (16 bytes, 128 bits)
Destination Address (16 bytes)
IPv4
Version Hdr Len Prec
header
Identification
Time to Live
TOS
Total Length
Flags
Protocol
Fragment Offset
Header Checksum
Source Address
Destination Address
Options
Padding
32 bits
6/5/05
25
CS118/Spring05
Transition From IPv4 To IPv6
 Not all routers can be upgraded simultaneous
 to allow the Internet operate with mixed IPv4 and IPv6
routers : tunneling
Logical view:
E
F
IPv6
IPv6
A
B
IPv6
IPv6
A
B
C
D
E
F
IPv6
IPv6
IPv4
IPv4
IPv6
IPv6
tunnel
Physical view:
Flow: X
Src: A
Dest: F
data
A-to-B:
IPv6
6/5/05
Src:B
Dest: E
Src:B
Dest: E
Flow: X
Src: A
Dest: F
Flow: X
Src: A
Dest: F
data
data
B-to-C:
IPv6 inside
IPv4
26
B-to-C:
IPv6 inside
IPv4
Flow: X
Src: A
Dest: F
data
E-to-F:
IPv6
CS118/Spring05
Broadcast and Multicasting
 Broadcast
 By building a spanning tree
 By reverse path forwarding
 IP multicast service model
 each group identified by an IP mcast address
 members can be anywhere
 members may join and leave any time
 multicast routing protocols
 Center-based, shared multicast tree
 Distance-Vector Multicast Routing (DVMRP)
• reverse path broadcast: only broadcast over output interfaces if the input
interface is on the shortest path to the source S
• pruning and grafting
Q: after sending a pruning message, why does the router
need to keep the pruning state?
6/5/05
27
CS118/Spring05
IGMP
 A query router on each link
 querier periodically polls the link
 on receipt of query message, a host sets a random timer for
each mcast group it belongs to
 when timer expires, send a membership report to group G
 others in G hear the report and stop the timers
 joining: send reports immediately
 leaving: send a leave msg only if the host answered the last
membership query, and querier router sends group-specific
queries again
Q: Why does the host use a random timer in IGMP?
Q: Does the router know how many receiving hosts for each multicast
group on its local Ethernet?
Q: When the last receiving host leaves the group, but its leave message
is lost, what happens?
6/5/05
28
CS118/Spring05
ON TCP
 How does TCP achieve reliable data delivery?
 What
are the fundamental mechanisms?
 How does TCP perform flow control?
 How does TCP perform congestion control?
 How does TCP estimate its RTT and set the
retransmission timeout (RTO)?
6/5/05
29
CS118/Spring05
TCP header format
0
3
1
1
6
IP header
source port
destination port
Data sequence number
acknowledgment number
Hlen unused
u a p r s F
r c s s y i
g k h t n n
window size
checksum
urgent pointer
Options (viable length)
data
6/5/05
30
CS118/Spring05
"pseudo header" in UCP and TCP
UDP header
 Length: # of bytes (including
both header & data)
 checksum: computed over
0
31
source port #
destination port#
checksum
length
data ......
the pseudo header, and
 UDP datagram (including both header and data)
 if the value is 0: no checksum

UDP pseudo header
source IP address
destination IP address
zero
TCP pseudo header
UDP length
source IP address
destination IP address
zero
6/5/05
protocol
31
protocol
TCP length
CS118/Spring05
More on pseudo headers
 addresses & protocol: copied from IP header
 Length
 UDP: already covered in the UDP header
 TCP: can be calculated from the IP total length
 pseudo header is not carried in the datagram, nor
counted in length field
 why pseudo header: UDP/TCP's self-protection
against mis-delivered IP packets
6/5/05
32
CS118/Spring05
TCP connection: open and close
 Open: the initial seq# is randomly chosen
server
Passive open
client
open request(x)
ack(x+1) + request(y)
ack(y+1)
(now in estab. state)
Close:
enter estab. state
I-finished(M)
ACK (M+1)
I-finished(N)
ack(N+1), wait for
2MSL before
deleting conn. state
6/5/05
Done, delete conn. state
33
CS118/Spring05
TCP Retransmission Timer
 SRTT = EstimatedRTT, rttvar = DevRTT
 When opening a new TCP connection:
 EstimatedRTT = DevRTT = 3 sec
 Upon getting the first RTT sample:
= SampleRTT, DevRTT = EstimatedRTT/2
EstimatedRTT
 Upon getting next SampleRTT:
 difference = SampleRTT - EstimatedRTT
 EstimatedRTT = (1-) x EstimatedRTT +  x SampleRTT
= EstimatedRTT +  x difference
 DevRTT = (1-) x DevRTT +  x |difference|
= DevRTT +  (|difference| - DevRTT)
 Typically:  = 1/8,  = 1/4
 TimeoutInterval (RTO) = EstimatedRTT + 4 x DevRTT
 If timeout: RTO = 2 x RTO
6/5/05
34
CS118/Spring05
TCP Congestion Control
 Basic idea: learn from observations
 when congwin < threshold, increase
congwin exponentially
 when congwin ≥ threshold, increase
congwin linearly
 if packet lost, have gone too far
 threshold = congwin / 2
 If 3 dup. ACKs: network capable of delivering some
packets, congwin cut in half
 If timeout: slow-start again (congwin = 1 mss)
6/5/05
35
CS118/Spring05
TCP Slow-Start & Congestion Avoidance
RTT
initialize:
Congwin = 1 MSS
threshold = RcvWindow
if (CongWin < threshold)
{ for every segment ACKed
Congwin++
} until (loss event)
/* slowstart is over
*/
{ for every w segments ACKed:
Congwin++
} Until (loss event)
time
/* loss detected */
threshold = Congwin/2
If (3 dup. ACKs)
Congwin = threshold
Else
Congwin = 1 MSS
6/5/05
36
CS118/Spring05
Application Protocols
 HTTP
 Persistent vs. non-persistent HTTP
 Parallel HTTP sessions
 DNS: providing name to IP address translation
service
 Generally
speaking, there is no relation between DNS
domains and IP address space
 FTP: uses separate TCP connections for control
exchange and file transfer
 SMTP
6/5/05
37
CS118/Spring05