Transcript slides - University of California, Berkeley

EECS122
Midterm Review
Department of Electrical Engineering and Computer Sciences
University of California
Berkeley
TOC: Midterm Review
Network
Web Browsing
Layers & Protocols
Inside a Router
Check List
EECS 122 - UCB
2
Review: Network
WAN
MAN
EECS 122 - UCB
3
Review: Network
WAN
MAN
EECS 122 - UCB
LAN
4
Review: Network
WAN
LAN
EECS 122 - UCB
5
Review: Web Browsing
Example
Locating Resource: DNS
Connection
End-to-end
Packets
Bits
Points to remember
EECS 122 - UCB
6
Web: Example
Click Link or URL
 get content from local
or remote computer
URL:
http://www.google.com/string
Specifies
- Protocol: http
- Computer: www.google.com
- String
Computer (server) selects
contents based on string
EECS 122 - UCB
7
Web: Locating Resource
www.google.com is the name of a computer
Network uses IP addresses
To find the IP address, the application uses a
hierarchical directory service called the
Domain Name System
com
www.google.com?
IP = a.b.c.d
www.google.com?
host
EECS 122 - UCB
local
IP = a.b.c.d
8
Web: Connection
The protocol (http) sets up a connection between
the host and cnn.com to transfer the page
The connection transfers the page as a byte stream,
without errors: pacing + error control
cnn.com
Host
connect
OK
get page
page; close
EECS 122 - UCB
9
Web: End-to-end
The byte stream flows
from end to end across
many links and switches:
routing (+ addressing)
That stream is regulated
and controlled by both
ends: retransmission of
erroneous or missing
bytes; flow control
EECS 122 - UCB
www.google.com
End-to-end pacing and
flow control
host
Routing
10
Web: Packets
www.google.com
IP address: A
The network transports
Host
bytes grouped into packets
A | B | # , CKS | bytes
IP
address:
B
The packets are “selfcontained” and routers
handle them one by one
The end hosts worry about
errors and flow control:
 Destination checks
packet for errors (using
C
error detection code
CKS) and sends ACKs
with sequence number #
 Source retransmits
packets that were not
ACKed and adjusts rate
of transmissions
EECS 122 - UCB
Destination
B C
Next Hop
11
Web: Bits
Equipment in each node sends the packets as a
string of bits
That equipment is not aware of the meaning of the
bits
01011...011...110
01011...011...110
Transmitter
Physical Medium
Receiver
Optical
Copper
Wireless
EECS 122 - UCB
12
Review: Layers & Protocols
Application
Application
HTTP, FTP, …
UDP - TCP
Data
Transport
TH
Data
Asynchronous routed path
Network
Data Link
Control
Physical
Interface
PH
Data
IP
Asynchronous reliable bit pipe
FH
Data
Synchronous unreliable bit pipe
Asynchronous routed path
Network
Data Link
Control
Physical
Interface
Physical Link
End Node
EECS 122 - UCB
Transport
PH
Network
Data
Asynchronous reliable bit pipe
FH
Data
Synchronous unreliable bit pipe
Data Link
Control
Physical
Interface
Physical Link
Router
End Node
13
Mapping Layers to Network Devices
Two broad classes of devices


Hosts
Routers
Both sets of devices run applications


Hosts mainly run “user applications”
Routers run “infrastructure applications”
 E.g. Topology discovery, Network Management Protocols,
BGP etc.
Don’t be confused by thinking that routers
don’t run application protocols because they
are layer 3 devices
EECS 122 - UCB
14
Layers: Transport Services
ports
HTTP RA DNS
Application
p1
p2
p1 p2
p3
p1
p2
Transport
IP
A
B
C
[A | B | p1 | p2 | …]
UDP: Not reliable
TCP: Ordered, reliable, well-paced
EECS 122 - UCB
15
Layers - TCP:
MPX, Error, Flow and Congestion Control
65KB
window = min{RAW - OUT, W}
W
0.5
3DA
3DA
0.5
X
X
0.5
X
1
TO
SS
EECS 122 - UCB
3
TO
0.5
X
3
CA
SS
CA
16
TCP Algorithm: AIMD
A
D
C
C
x
B
y
E
y
Limit rates:
x=y
x
EECS 122 - UCB
17
Flow Control
Objective: Avoid saturating destination
Algorithm: Receiver avertizes window RAW
window = min{RAW – OUT, W}
where
OUT = Oustanding = Last sent – last ACKed
W = Cong. Window from AIMD + refinements
RAW
[ACK | RAW | …]
EECS 122 - UCB
18
Layers: IP – Internet Protocol
Addressing


Class-Based
Classless: CIDR
Fixed Prefix – M-tree
LPM-Patricia Trie
Routing
EECS 122 - UCB
19
Class-base Addressing
Addressing reflects internet hierarchy

32 bits divided into 2 parts:
8
0

Class A
0 network

Class B
0

Class C
0
EECS 122 - UCB
10
110
host
16
network
host
24
network
host
~2 million nets
256 hosts
20
Classless Internet Domain Routing
Suppose fifty computers in a network are
assigned IP addresses 128.23.9.0 - 128.23.9.49
 Range is
01111111 00001111 00001001 00000000
01111111 00001111 00001001 00110001



to
They share the first 26 bits of 128.23.9.0:
Convention: 128.23.9.0/26 = prefix
There are 32-27=6 bits for the 50 computers
 26 = 64 addresses
EECS 122 - UCB
21
IP: Routing
Intradomain

44
BGP
5
22
4
RIP
3
3

6
6B
7
IntraDomain
8
6
13
13
11
2
10
IntraDomain
3
1
IGRP
IntraDomain
Interdomain


EECS 122 - UCB

Formulate the routing
problem as a Shortest
Path Problem
Link State v/s
Distance Vector
Both work reasonably
well in a well
engineered network
13
BGP
Path Vector, Policies
12
C
OSPF
22
Route Computation
Dijkstra: Link State


Use a flooding protocol to discover the entire topology
Find the shortest paths in order of increasing path length
from node i.
Bellman Ford: Distance Vector

D(i,d) = minjεN(i) {c(i,j) + D(j,d)}
BGP: Path Vector


Policy routing: Receive and advertise entire routes
AS numbers describe the path to a CIDR address
Routes
received
from
neighbors
EECS 122 - UCB
accept,
deny, set
preferences
Import
Policy
Engine
Choose
best route
Decision
process
BGP table
forward,
not forward
set MEDs
Routes
used by
router
IP Routing
table
Export
Policy
Engine
Routes
sent to
neighbors
23
Review: Inside Router
Input and output
interfaces are connected
through an interconnect
A interconnect can be
implemented by

input interface
output interface
Interconnect
Shared memory
 low capacity routers
(e.g., PC-based
routers)

Shared bus
 Medium capacity
routers

Point-to-point (switched)
bus
 High capacity routers
EECS 122 - UCB
Scheduling
GPS
WFQ
24
Router: GPS/WFQ
Why service disciplines?

Understand GPS and WFQ well
GPS properties
WFQ tracking result

EECS 122 - UCB
No later than one packet transmission
25
Review: Check List
Big Picture




Layers
Network Structure (L2, L3)
Where protocols are implemented
Switching Techniques
Applications


DNS
HTTP
Transport


TCP: Service; Go Back N; Flow Control; Congestion Control; AIMD;
SS; 3DA; Phases
UDP: Service
Network



Class-Based; Classless Addressing
Dijkstra; Bellman-Ford
Hierarchical routing
Inside Router


EECS 122 - UCB
Architecture: Input, Output
Scheduling: Fairness, GPS, WFQ
26