Network layer (IP)
Download
Report
Transcript Network layer (IP)
Announcement
CTEC code for TA
CS 340
Lin
Code: 322
1
Last class
Network layer - introduction
Virtual circuit and datagram networks
Routing algorithms
Link state
2
Link-state algorithm: example
Step
0
1
2
3
4
5
N'
u
ux
uxy
uxyv
uxyvw
uxyvwz
D(v),p(v) D(w),p(w)
2,u
5,u
2,u
4,x
2,u
3,y
3,y
D(x),p(x)
1,u
D(y),p(y)
∞
2,x
D(z),p(z)
∞
∞
4,y
4,y
4,y
5
2
u
v
2
1
x
3
w
3
1
5
1
y
z
2
3
Overview
Distance vector
IP: Internet Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
4
Distance Vector Algorithm (1)
Bellman-Ford Equation (dynamic programming)
Define
dx(y) := cost of least-cost path from x to y
Then
dx(y) = min {c(x,v) + dv(y) }
where min is taken over all neighbors of x
5
Bellman-Ford example (2)
5
2
u
v
2
3
w
3
Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
5
1
z
B-F equation says:
du(z) = min { c(u,v) + dv(z),
c(u,x) + dx(z),
1
c(u,w) + dw(z) }
= min {2 + 5,
1 + 3,
5 + 3} = 4
Node that achieves minimum is next
hop in shortest path ➜
1
x
y
2
6
Distance Vector Algorithm (3)
Estimates:
Dx(y) = estimate of least cost from x to y
Distance vector: Dx = [Dx(y): y є N ]
Each node x:
Node x knows cost to each neighbor v: c(x,v)
Node x maintains Dx = [Dx(y): y є N ]
Node x also maintains its neighbors’ distance
vectors
• For each neighbor v, x maintains
Dv = [Dv(y): y є N ]
7
Distance vector algorithm (4)
Basic idea:
Each node periodically sends its own distance
vector estimate to neighbors
When a node x receives new DV estimate from
neighbor, it updates its own DV using B-F equation:
Dx(y) ← minv{c(x,v) + Dv(y)}
for each node y ∊ N
Under minor, natural conditions, the estimate Dx(y)
converge the actual least cost dx(y)
8
Distance Vector Algorithm (5)
Iterative, asynchronous:
each local iteration caused
by:
local link cost change
DV update message from
neighbor
Distributed:
Each node:
wait for (change in local link
cost of msg from neighbor)
each node notifies
neighbors only when its DV
changes
neighbors then notify
their neighbors if
necessary
The algorithm doesn’t
know the entire path –
only knows the next hop
recompute estimates
if DV to any dest has
changed, notify neighbors
9
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
node x table
cost to
x y z
x ∞∞ ∞
y ∞∞ ∞
z 71 0
from
from
from
from
x 0 2 7
y 2 0 1
z 7 1 0
cost to
x y z
x 0 2 7
y 2 0 1
z 3 1 0
x 0 2 3
y 2 0 1
z 3 1 0
cost to
x y z
x 0 2 3
y 2 0 1
z 3 1 0
x
2
y
7
1
z
cost to
x y z
from
from
from
x ∞ ∞ ∞
y 2 0 1
z ∞∞ ∞
node z table
cost to
x y z
x 0 2 3
y 2 0 1
z 7 1 0
cost to
x y z
cost to
x y z
from
from
x 0 2 7
y ∞∞ ∞
z ∞∞ ∞
node y table
cost to
x y z
cost to
x y z
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
x 0 2 3
y 2 0 1
z 3 1 0
time
10
Distance Vector: link cost changes
Link cost changes:
node detects local link cost change
updates routing info, recalculates
distance vector
if DV changes, notify neighbors
“good
news
travels
fast”
1
x
4
y
50
1
z
At time t0, y detects the link-cost change, updates its DV,
and informs its neighbors.
At time t1, z receives the update from y and updates its table.
It computes a new least cost to x and sends its neighbors its DV.
At time t2, y receives z’s update and updates its distance table.
y’s least costs do not change and hence y does not send any
message to z.
11
Distance Vector: link cost changes
Link cost changes:
good news travels fast
bad news travels slow -
“count to infinity” problem!
44 iterations before
algorithm stabilizes: see
text
60
x
4
y
50
1
z
Poissoned reverse:
If Z routes through Y to
get to X :
Z tells Y its (Z’s) distance
to X is infinite (so Y won’t
route to X via Z)
will this completely solve
count to infinity problem?
12
Comparison of LS and DV algorithms
Message complexity
LS: with n nodes, E links,
O(nE) msgs sent
DV: exchange between
neighbors only
convergence time varies
Speed of Convergence
LS: O(n2) algorithm requires
O(nE) msgs
may have oscillations
DV: convergence time varies
may be routing loops
count-to-infinity problem
Robustness: what happens
if router malfunctions?
LS:
node can advertise
incorrect link cost
each node computes only
its own table
DV:
DV node can advertise
incorrect path cost
each node’s table used by
others
• error propagate thru
network
13
Overview
Distance vector
IP: Internet Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
14
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
15
IP datagram format
IP protocol version
number
header length
(bytes)
“type” of data
max number
remaining hops
(decremented at
each router)
upper layer protocol
to deliver payload to
how much overhead
with TCP?
20 bytes of TCP
20 bytes of IP
= 40 bytes + app
layer overhead
32 bits
head. type of
length
ver
len service
fragment
16-bit identifier flgs
offset
upper
time to
Internet
layer
live
checksum
total datagram
length (bytes)
for
fragmentation/
reassembly
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
E.g. timestamp,
record route
taken, specify
list of routers
to visit.
16
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
17
IP Fragmentation and Reassembly
Example
4000 byte
datagram
MTU = 1500 bytes
1480 bytes in
data field
offset =
1480/8
length ID fragflag offset
=4000 =x
=0
=0
One large datagram becomes
several smaller datagrams
length ID fragflag offset
=1500 =x
=1
=0
length ID fragflag offset
=1500 =x
=1
=185
length ID fragflag offset
=1040 =x
=0
=370
18
Overview
Distance vector
IP: Internet Protocol
Datagram format
IPv4 addressing
ICMP
IPv6
19
IP Addressing: introduction
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 each
interface
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
20
Subnets
IP address:
subnet part (high
order bits)
host part (low order
bits)
What’s a subnet ?
device interfaces with
same subnet 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 subnets
21
Subnets
Recipe
To determine the
subnets, detach each
interface from its
host or router,
creating islands of
isolated networks.
Each isolated network
is called a subnet.
223.1.1.0/24
223.1.2.0/24
223.1.3.0/24
Subnet mask: /24
22
Subnets
223.1.1.2
Q. How many?
223.1.1.1
A. The IP definition of a
subnet is not
restricted to
Ethernet segments
223.1.1.4
223.1.1.3
223.1.9.2
223.1.7.0
223.1.9.1
223.1.7.1
223.1.8.1
223.1.8.0
223.1.2.6
223.1.2.1
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
23
IP addressing: CIDR
Before CIDR: only 8-, 16-, and 24- bit masks were
available (A, B, and C class networks)
CIDR: Classless InterDomain Routing
subnet portion of address of arbitrary length
address format: a.b.c.d/x, where x is # bits in
subnet portion of address
subnet
part
host
part
11001000 00010111 00010000 00000000
200.23.16.0/23
24
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 from as server
“plug-and-play”
(more in a couple of weeks)
25
IP addresses: how to get one?
Q: How does network get subnet part of IP
addr?
A: gets allocated portion of its provider ISP’s
address space
ISP's block
11001000 00010111 00010000 00000000
200.23.16.0/20
Organization 0
Organization 1
Organization 2
...
11001000 00010111 00010000 00000000
11001000 00010111 00010010 00000000
11001000 00010111 00010100 00000000
…..
….
200.23.16.0/23
200.23.18.0/23
200.23.20.0/23
….
Organization 7
11001000 00010111 00011110 00000000
200.23.30.0/23
26
Hierarchical addressing: route aggregation
Hierarchical addressing allows efficient advertisement of routing
information:
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
“Send me anything
with addresses
beginning
199.31.0.0/16”
27
Hierarchical addressing: more specific
routes
ISPs-R-Us has a more specific route to Organization 1
Organization 0
200.23.16.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
Organization 1
200.23.18.0/23
“Send me anything
with addresses
beginning 199.31.0.0/16
or 200.23.18.0/23”
28
IP addressing: the last word...
Q: How does an ISP get block of addresses?
A: ICANN: Internet Corporation for Assigned
Names and Numbers
allocates addresses
manages DNS
assigns domain names, resolves disputes
29
NAT: Network Address Translation
rest of
Internet
local network
(e.g., home network)
10.0.0/24
10.0.0.4
10.0.0.1
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)
30
NAT: Network Address Translation
Motivation: local network uses just one IP address as
far as outside word is concerned:
no need to be allocated range of addresses from ISP:
- just one IP address is used for all devices
can change addresses of devices in local network
without notifying outside world
can change ISP without changing addresses of
devices in local network
devices inside local net not explicitly addressable,
visible by outside world (a security plus).
31
NAT: Network Address Translation
Implementation: NAT router must:
outgoing datagrams: replace (source IP address, port
#) of every outgoing datagram to (NAT IP address,
new port #)
. . . remote clients/servers will respond using (NAT
IP address, new port #) as destination addr.
remember (in NAT translation table) every (source
IP address, port #) to (NAT IP address, new port #)
translation pair
incoming datagrams: replace (NAT IP address, new
port #) in dest fields of every incoming datagram
with corresponding (source IP address, port #)
stored in NAT table
32
NAT: Network Address Translation
2: NAT router
changes datagram
source addr from
10.0.0.1, 3345 to
138.76.29.7, 5001,
updates table
2
NAT translation table
WAN side addr
LAN side addr
1: host 10.0.0.1
sends datagram to
128.119.40, 80
138.76.29.7, 5001 10.0.0.1, 3345
……
……
S: 10.0.0.1, 3345
D: 128.119.40.186, 80
S: 138.76.29.7, 5001
D: 128.119.40.186, 80
138.76.29.7
S: 128.119.40.186, 80
D: 138.76.29.7, 5001
3: Reply arrives
dest. address:
138.76.29.7, 5001
3
1
10.0.0.4
S: 128.119.40.186, 80
D: 10.0.0.1, 3345
10.0.0.1
10.0.0.2
4
10.0.0.3
4: NAT router
changes datagram
dest addr from
138.76.29.7, 5001 to 10.0.0.1, 3345
33
NAT: Network Address Translation
16-bit port-number field:
60,000 simultaneous connections with a single
LAN-side address!
NAT is controversial:
Port numbers are to address processes – not
hosts
routers should only process up to layer 3
violates end-to-end argument
• NAT possibility must be taken into account by app
designers, eg, P2P applications
address shortage should instead be solved by
IPv6
34