Transcript Slide 1

Lecture 5
TCP/IP Network Layer (3)
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
Outline (Network Layer)
• Principles behind network
layer services:
– Virtual circuit and datagram
networks
– Routing algorithms
•
•
•
•
Link State
Distance Vector
Hierarchical
Routing Tables
• What’s inside a router
• Internet Protocol
–
–
–
–
Datagram format
IPv4 addressing
CIDR
IPv6
Khaled Mahbub, IICT, BUET, 2008
• Routing in the Internet
– RIP
– OSPF
– BGP
• Broadcast and multicast routing
• Miscellaneous protocols and
programs
ICT 6621 : Advanced Networking
Routing Protocols in the Internet
• Internet consists of inter connected Autonomous Systems (ASs).
• ASs typically consists of many networks.
• Datagrams are routed within each AS using Intra-AS routing
protocols, also known as Interior Gateway Protocols (IGP).
• Datagrams among ASs are routed using inter-AS routing protocoal,
also known as Exterior Gateway Protocols (EGP).
• Most common Intra-AS routing protocols:
– RIP: Routing Information Protocol
– OSPF: Open Shortest Path First
• Most common Inter-AS routing protocols:
– BGP: Border Gateway Protocol
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
RIP ( Routing Information Protocol)
• Distance vector algorithm
• Included in BSD-UNIX Distribution in 1982
• Distance metric: # of hops, each hop has cost of 1, (max
= 15 hops)
• 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
u
v
A
z
C
B
D
Khaled Mahbub, IICT, BUET, 2008
w
x
y
destination hops
u
1
v
2
w
2
x
3
y
3
z
2
ICT 6621 : Advanced Networking
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
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
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
--
2
2
7 5
1
Routing table in D
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
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 count to infinity
problem (infinite distance = 16 hops)
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
RIP Table processing
• RIP routing tables
managed by applicationlevel process. (e.g. in
UNIX route-d (daemon))
• advertisements sent in
UDP packets, periodically
repeated
routed
routed
Transprt
(UDP)
network
(IP)
Transprt
(UDP)
forwarding
table
forwarding
table
network
(IP)
link
physical
Khaled Mahbub, IICT, BUET, 2008
link
physical
ICT 6621 : Advanced Networking
RIP Message Format
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
RIP Message Format
• Command—Indicates whether the packet is a request or a
response. The request asks that a router send all or part of its
routing table. The response can be an unsolicited regular routing
update or a reply to a request. Responses contain routing table
entries. Multiple RIP packets are used to convey information from
large routing tables.
• Version Number—Specifies the RIP version used. This field can
signal different potentially incompatible versions.
• Zero—Not used.
• Address-Family Identifier (AFI)—Specifies the address family used.
RIP is designed to carry routing information for several different
protocols. Each entry has an address-family identifier to indicate the
type of address being specified. The AFI for IP is 2.
• Address—Specifies the IP address for the entry.
• Metric—Indicates how many internetwork hops (routers) have been
traversed in the trip to the destination. This value is between 1 and
15 for a valid route, or 16 for an unreachable route.
• Up to 25 occurrences of the AFI, address, and metric fields are
permitted in a single IP RIP packet.
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
RIP Table example (netstat command)
C:\Documents and Settings\Administrator>netstat -r
Route Table
===================================================================
========
Interface List
0x1 ........................... MS TCP Loopback interface
0x2 ...00 12 79 db e6 94 ...... Broadcom NetXtreme Gigabit Ethernet - Packet Scheduler
Miniport
===============================================================
===============================================================
Active Routes:
Network Destination
Netmask
Gateway
Interface Metric
0.0.0.0
0.0.0.0
172.16.20.1 172.16.10.29
30
127.0.0.0
255.0.0.0
127.0.0.1
127.0.0.1
1
169.254.0.0
255.255.0.0 172.16.10.29 172.16.10.29
30
172.16.0.0
255.255.0.0 172.16.10.29 172.16.10.29
30
224.0.0.0
240.0.0.0 172.16.10.29 172.16.10.29
30
Default Gateway:
172.16.20.1
===============================================================
Persistent Routes:
None
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
RIP Message Format (v2)
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
RIP Message Format (v2)
•
•
•
•
•
•
•
•
•
Command—Indicates whether the packet is a request or a response. The request
asks that a router send all or a part of its routing table. The response can be an
unsolicited regular routing update or a reply to a request. Responses contain routingtable entries. Multiple RIP packets are used to convey information from large routing
tables.
Version—Specifies the RIP version used. In a RIP packet implementing any of the
RIP 2 fields or using authentication, this value is set to 2.
Routing Domain: An identifier of the routing daemon, to which this packet belongs.
Address-Family Identifier (AFI)—Specifies the address family used. RIP is designed
to carry routing information for several different protocols. Each entry has an addressfamily identifier to indicate the type of address specified. The address-family identifier
for IP is 2. If the AFI for the first entry in the message is 0xFFFF, the remainder of the
entry contains authentication information. Currently, the only authentication type is
simple password.
Route Tag—Provides a method for distinguishing between internal routes (learned by
RIP) and external routes (learned from other protocols).
IP Address—Specifies the IP address for the entry.
Subnet Mask—Contains the subnet mask for the entry. If this field is zero, no subnet
mask has been specified for the entry.
Next Hop—Indicates the IP address of the next hop to which packets for the entry
should be forwarded.
Metric—Indicates how many internetwork hops (routers) have been traversed in the
trip to the destination. This value is between 1 and 15 for a valid route, or 16 for an
unreachable route.
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
Outline (Network Layer)
• Principles behind network
layer services:
– Virtual circuit and datagram
networks
– Routing algorithms
•
•
•
•
Link State
Distance Vector
Hierarchical
Routing Tables
• What’s inside a router
• Internet Protocol
–
–
–
–
Datagram format
IPv4 addressing
CIDR
IPv6
Khaled Mahbub, IICT, BUET, 2008
• Routing in the Internet
– RIP
– OSPF
– BGP
• Broadcast and multicast routing
• Miscellaneous protocols and
programs
ICT 6621 : Advanced Networking
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
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
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.
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
Hierarchical OSPF
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
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.
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
Outline (Network Layer)
• Principles behind network
layer services:
– Virtual circuit and datagram
networks
– Routing algorithms
•
•
•
•
Link State
Distance Vector
Hierarchical
Routing Tables
• What’s inside a router
• Internet Protocol
–
–
–
–
Datagram format
IPv4 addressing
CIDR
IPv6
Khaled Mahbub, IICT, BUET, 2008
• Routing in the Internet
– RIP
– OSPF
– BGP
• Broadcast and multicast routing
• Miscellaneous protocols and
programs
ICT 6621 : Advanced Networking
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
E.g., Gateway X may send its path to destination. Z:
Path (X,Z) = X,Y1,Y2,Y3,…,Z
•
BGP routes to networks (ASs), not individual hosts
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
BGP
• Suppose: gateway X sends its path, Path (X,Z) =
X,Y1,Y2,Y3,Z, to peer gateway W
• W may or may not select path offered by X
– cost, policy (don’t route via competitors AS), loop
prevention reasons.
• If W selects path advertised by X, then:
– Path (W,Z) = W, Path (X,Z)= W,X,Y1,Y2,Y3,Z
• Note: X can control incoming traffic by
controlling it route advertisements to peers:
– e.g., don’t want to route traffic to Z -> don’t advertise
any routes to Z
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
BGP Routing Policy
• A,B,C are provider networks
• X,W,Y are customer (of provider networks)
• X is dual-homed: attached to two networks
– X does not want to have a route from B to C via X
– .. so X will not advertise to B a route to C
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
BGP Routing Policy
• A advertises to B the path AW
• B advertises to X the path BAW
• Should B advertise to C the path BAW?
– No. B gets no “revenue” for routing CBAW since neither W nor
C are B’s customers
– B wants to force C to route to w via A
– B wants to route only to/from its customers!
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
BGP
• Routers’ responsibility
– Receiving and filtering route advertisements from
directly attached neighbor(s).
– Route selection.
• To route to destination X, which path (of several advertised) will
be taken?
– Sending route advertisements to neighbors.
• BGP Messages:
– BGP messages exchanged using TCP.
– 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 message;
also used to close connection
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
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
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking
Reading Material
• Chapter 4 – text3 (Kurose)
• Chapter 5 – text2 (Tanenbaum)
• Chapter 10 – text1 (Stevens)
Khaled Mahbub, IICT, BUET, 2008
ICT 6621 : Advanced Networking