Transcript William Stallings Data and Computer Communications

Datakommunikasjon
høsten 2002
Forelesning nr 5,
mandag 16. september
Chapter 4, Network Layer and
Routing
Datakom høsten 2002
1
Øvingsoppgaver
 Oppgaver 1 CIDR og subnetting
 IP Address
: 193.69.136.0
 Address Class : Classless /25
 Network Address : 193.69.136.0
 A)
 Du skal dele nettet i to subnett. Hva blir:
 Subnet id-er
 Subnet Mask
 Subnet bit mask
 Subnet Bits
 Host Bits
 Hosts per Subnet
Datakom høsten 2002
2
Øvingsoppgaver
Øvingsoppgave 2
Du skal dele nettet i oppgave 1 I 8 subnett.
Hva blir:
Subnet id-er
Subnet Mask
Subnet bit mask
Subnet Bits
Host Bits
Hosts per Subnet
Datakom høsten 2002
3
Øvingsoppgaver
Oppgave 3
IP Address
: 176.85.36.0
Address Class : Classless /23
Network Address : 176.85.36.0
Du skal dele nettet i 4 subnett. Hva blir:
Subnet id-er
Subnet Mask
Subnet bit mask
Subnet Bits
Host Bits
Hosts per Subnet
Datakom høsten 2002
4
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.
Datakom høsten 2002
5
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
Datakom høsten 2002
6. Receive data application
3. Accept call transport
2. incoming call network
data link
physical
6
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 between same source-dest pair may take different
paths
application
transport
network
data link 1. Send data
physical
application
transport
2. Receive data network
data link
physical
Datakom høsten 2002
7
Network layer service models:
Network
Architecture
Internet
Service
Model
Guarantees ?
Congestion
Bandwidth Loss Order Timing feedback
best effort none
ATM
CBR
ATM
VBR
ATM
ABR
ATM
UBR
constant
rate
guaranteed
rate
guaranteed
minimum
none
no
no
no
yes
yes
yes
yes
yes
yes
no
yes
no
no (inferred
via loss)
no
congestion
no
congestion
yes
no
yes
no
no
Datakom høsten 2002
8
DHCP: Dynamic Host Configuration Protocol
Goal: allow host to dynamically obtain its IP address from
network server when it joins network
Can renew its lease on address in use
Allows reuse of addresses (only hold address while connected an
“on”
Support for mobile users who want to join network (more
shortly)
DHCP overview:
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
Datakom høsten 2002
9
DHCP client-server scenario
A
B
223.1.2.1
DHCP
server
223.1.1.1
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
223.1.3.2
Datakom høsten 2002
E
arriving DHCP
client needs
address in this
network
10
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
Datakom høsten 2002
11
Routing
Routing protocol
5
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
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
Datakom høsten 2002
12
Routing Algorithm classification
Global or decentralized
information?
Static or dynamic?
Global:
 all routers have complete
topology, link cost info
 “link state” algorithms
Decentralized:
 router knows physicallyconnected neighbors, link
costs to neighbors
 iterative process of
computation, exchange of
info with neighbors
 “distance vector” algorithms
Static:
 routes change slowly
over time
Dynamic:
 routes change more
quickly
periodic update
in response to link
cost changes
Datakom høsten 2002
13
Hierarchical Routing
Our routing study thus far - idealization
 all routers identical
 network “flat”
… not true in practice
scale: with 200 million
destinations:
administrative autonomy
 can’t store all dest’s in routing
tables!
 routing table exchange would
swamp links!
 internet = network of
networks
 each network admin may want
to control routing in its own
network
Datakom høsten 2002
14
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
Datakom høsten 2002
15
Intra-AS and Inter-AS routing
C.b
a
C
Gateways:
B.a
A.a
b
A.c
d
A
a
b
a
c
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
Datakom høsten 2002
16
Intra-AS and Inter-AS routing
C.b
a
Host
h1
C
b
A.a
Inter-AS
routing
between
A and B
A.c
a
d
c
b
A
Intra-AS routing
within AS A
B.a
a
c
B
Host
h2
b
Intra-AS routing
within AS B
 We’ll examine specific inter-AS and intra-AS
Internet routing protocols shortly
Datakom høsten 2002
17
Routing in the Internet
 The Global Internet consists of Autonomous Systems
(AS) interconnected with each other:
Stub AS: small corporation: one connection to other AS’s
Multihomed AS: large corporation (no transit): multiple
connections to other AS’s
Transit AS: provider, hooking many AS’s together
 Two-level routing:
Intra-AS: administrator responsible for choice of routing
algorithm within network
Inter-AS: unique standard for inter-AS routing: BGP
Datakom høsten 2002
18
Internet AS Hierarchy
Intra-AS border (exterior gateway) routers
Inter-AS interior (gateway) routers
Datakom høsten 2002
19
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)
Datakom høsten 2002
20
RIP ( Routing Information Protocol)
 Distance vector algorithm
 Included in BSD-UNIX Distribution in 1982
 Distance metric: # of hops (max = 15 hops)
 Can you guess why?
 Distance vectors: exchanged among neighbors every 30
sec via Response Message (also called advertisement)
 Each advertisement: list of up to 25 destination nets
within AS
Datakom høsten 2002
21
RIP: Example
z
w
A
x
D
B
y
C
Destination Network
w
y
z
x
….
Next Router
Num. of hops to dest.
….
....
A
B
B
--
2
2
7
1
Routing table in D
Datakom høsten 2002
22
RIP: Example
Dest
w
x
z
….
Next
C
…
w
hops
4
...
A
Advertisement
from A to D
z
x
Destination Network
w
y
z
x
….
D
B
C
y
Next Router
Num. of hops to dest.
….
....
A
B
B A
--
Routing
table
D
Datakom
høstenin2002
2
2
7 5
1
23
RIP: Link Failure and Recovery
If no advertisement heard after 180 sec --> neighbor/link
declared dead
routes via neighbor invalidated
new advertisements sent to neighbors
neighbors in turn send out new advertisements (if
tables changed)
link failure info quickly propagates to entire net
poison reverse used to prevent ping-pong loops
(infinite distance = 16 hops)
Datakom høsten 2002
24
RIP Table processing
 RIP routing tables managed by application-level
process called route-d (daemon)
 advertisements sent in UDP packets, periodically
repeated
routed
routed
Transprt
(UDP)
network
(IP)
Transprt
(UDP)
forwarding
table
forwarding
table
link
network
(IP)
link
physical
physical
Datakom høsten 2002
25
RIP Table example (continued)
Router: giroflee.eurocom.fr
Destination
-------------------127.0.0.1
192.168.2.
193.55.114.
192.168.3.
224.0.0.0
default





Gateway
Flags Ref
Use
Interface
-------------------- ----- ----- ------ --------127.0.0.1
UH
0 26492 lo0
192.168.2.5
U
2
13 fa0
193.55.114.6
U
3 58503 le0
192.168.3.5
U
2
25 qaa0
193.55.114.6
U
3
0 le0
193.55.114.129
UG
0 143454
Three attached class C networks (LANs)
Router only knows routes to attached LANs
Default router used to “go up”
Route multicast address: 224.0.0.0
Loopback interface (for debugging)
Datakom høsten 2002
26
Route print (netstat –rn)
Active Routes:
Network Destination Netmask
0.0.0.0
0.0.0.0
127.0.0.0
255.0.0.0
192.168.1.0
255.255.255.0
192.168.1.121
255.255.255.255
192.168.1.255
255.255.255.255
193.69.136.0
255.255.255.0
193.69.137.0
255.255.255.0
224.0.0.0
240.0.0.0
255.255.255.255
255.255.255.255
Default Gateway:
Gateway
192.168.1.1
127.0.0.1
192.168.1.121
127.0.0.1
192.168.1.121
192.168.1.1
192.168.1.1
192.168.1.121
192.168.1.121
Interface
192.168.1.121
127.0.0.1
192.168.1.121
127.0.0.1
192.168.1.121
192.168.1.121
192.168.1.121
192.168.1.121
192.168.1.121
Metric
20
1
20
20
20
1
1
20
1
192.168.1.1
Persistent Routes:
None
Datakom høsten 2002
27
OSPF (Open Shortest Path First)
 “open”: publicly available
 Uses Link State algorithm
LS packet dissemination
Topology map at each node
Route computation using Dijkstra’s algorithm
 OSPF advertisement carries one entry per neighbor
router
 Advertisements disseminated to entire AS (via flooding)
Carried in OSPF messages directly over IP (rather than TCP or
UDP
Datakom høsten 2002
28
OSPF “advanced” features (not in RIP)
 Security: all OSPF messages authenticated (to prevent
malicious intrusion)
 Multiple same-cost paths allowed (only one path in RIP)
 For each link, multiple cost metrics for different TOS
(e.g., satellite link cost set “low” for best effort; high for
real time)
 Integrated uni- and multicast support:
Multicast OSPF (MOSPF) uses same topology data
base as OSPF
 Hierarchical OSPF in large domains.
Datakom høsten 2002
29
Hierarchical OSPF
Datakom høsten 2002
30
Hierarchical OSPF
 Two-level hierarchy: local area, backbone.
Link-state advertisements only in area
each nodes has detailed area topology; only know
direction (shortest path) to nets in other areas.
 Area border routers: “summarize” distances to nets
in own area, advertise to other Area Border routers.
 Backbone routers: run OSPF routing limited to
backbone.
 Boundary routers: connect to other AS’s.
Datakom høsten 2002
31
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
Datakom høsten 2002
32
Internet inter-AS routing: BGP
 BGP (Border Gateway Protocol): the de facto standard
 Path Vector protocol:
similar to Distance Vector protocol
each Border Gateway broadcast to neighbors (peers)
entire path (i.e., sequence of AS’s) to destination
BGP routes to networks (ASs), not individual hosts
E.g., Gateway X may send its path to dest. Z:
Path (X,Z) = X,Y1,Y2,Y3,…,Z
Datakom høsten 2002
33
BGP messages
 BGP messages exchanged using TCP.
 BGP messages:
OPEN: opens TCP connection to peer and
authenticates sender
UPDATE: advertises new path (or withdraws old)
KEEPALIVE keeps connection alive in absence of
UPDATES; also ACKs OPEN request
NOTIFICATION: reports errors in previous msg; also
used to close connection
Datakom høsten 2002
34
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
Datakom høsten 2002
35