Transcript ppt - University of South Carolina

CSCE 515:
Computer Network Programming
Chin-Tser Huang
[email protected]
University of South Carolina
Open Shortest Path First (OSPF)




A link-state routing protocol
Each router tests status of all its links
and broadcasts its link status to all
routers on network
Use IP to carry its message
Provide features superior to RIP
2/15/2005
2
OSPF Message Format
1
1
vertype
sion
2
4
4
2
2
8
packet
length
router ID
area ID
checksum
auth
type
authentication
2/15/2005
data
3
Autonomous Systems


A collection of networks administered
by single entity, e.g. a corporation or a
campus
Three categories of AS



Stub AS
Multihomed AS
Transit AS
2/15/2005
4
Example of Autonomous System
Source: Internetworking Technologies
Handbook by Cisco Press
2/15/2005
5
IGP and EGP

Each AS selects its interior gateway
protocol (IGP) for communications
between routers in this AS


E.g. RIP, OSPF
Multiple AS’s use exterior gateway
protocol (EGP) for communications
between routers in different AS’s

E.g. EGP, BGP
2/15/2005
6
Border Gateway Protocol (BGP)




An exterior gateway protocol
Distance-vector protocol but
enumerates route to each destination
Allow policy-based routing
Use TCP to transport its messages
2/15/2005
7
BGP Message Types

BGP uses four message types




Open message
Keepalive message
Update message
Notification message
2/15/2005
8
Classless Interdomain Routing (CIDR)

Solve two problems



Shortage of class B network IDs
Explosion in routing table size due to
allocation of multiple class C network IDs
Summarize multiple IP addresses into a
smaller number of routing table entries
2/15/2005
9
Requirements of CIDR



Multiple IP addresses to be summarized
need to share same high-order bits
Routing decisions need to be based on
32-bit IP address and 32-bit mask
Routing protocols need to carry 32-bit
mask in addition to 32-bit address
2/15/2005
10
Example of CIDR
CIDR Block Prefix
Addresses
/27
/26
/25
/24
/23
…
/15
/14
/13
2/15/2005
# Equivalent Class C # of Host
1/8th of a Class C
1/4th of a Class C
1/2 of a Class C
1 Class C
2 Class C
32 hosts
64 hosts
128 hosts
256 hosts
512 hosts
512 Class C
1,024 Class C
2,048 Class C
131,072 hosts
262,144 hosts
524,288 hosts
11
User Datagram Protocol (UDP)



A datagram-oriented transport layer
protocol
Each output operation by a process
produces exactly one UDP datagram
Provide no reliability
2/15/2005
12
UDP Header
0
15 16
31
source port number destination port number
UDP length
UDP checksum
8 bytes
data (if any)
2/15/2005
13
UDP Checksum




Cover UDP header and UDP data
End-to-end checksum calculated by
sender and verified by receiver
Should always be enabled
16-bit one’s complement sum of header
(including a pseudo header) and data is
calculated
2/15/2005
14
Computation of UDP Checksum
0
15 16
31
source IP address
destination IP address
zero
header
UDP length
protocol(17)
source port number destination port number
UDP length
UDP pseudo
UDP header
UDP checksum
data (if any)
pad byte(0)
2/15/2005
15
Fragmentation



Need to fragment if size of resulting IP
datagram exceeds MTU
Can take place at source or at an
intermediate router
Fragments are reassembled at
destination
2/15/2005
16
Example of UDP Fragmentation
IP
header
UDP
header
20
8
IP
header
UDP
header
20
8
2/15/2005
UDP data
1473
IP
header
1472
20
1
17
ICMP Unreachable Error
(Fragmentation Required)
0
78
type(3)
15 16
code(0-15)
unused (must be 0)
31
checksum
MTU of next-hop network
IP header + first 8 bytes of original datagram data
2/15/2005
18
Next Class




UDP
Broadcasting and multicasting
Class MulticastSocket
Read TI Ch. 11, 12, JNP Ch. 22
2/15/2005
19