Transcript Fragmentation - Department of Computer Engineering

Datagram Forwarding
Asst. Prof. Chaiporn Jaikaeo, Ph.D.
[email protected]
http://www.cpe.ku.ac.th/~cpj
Computer Engineering Department
Kasetsart University, Bangkok, Thailand
Adapted from the notes by Lami Kaya and lecture slides from Anan Phonphoem
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
© The McGraw-Hill Companies, Inc.
Outline


Datagram forwarding/routing
IP Datagram

Fragmentation
2
Node-to-node delivery
Ethernet
WAN
Token Ring
3
Source-to-destination delivery
4
Forwarding IP Datagram
123.10.0.0/16
A
BKK
Internet
SKL
B
C
X
203.45.98.0/24
Y
Each router maintains routing table
It’s best effort !
5
Routing Table Entries
6
Next-Hop Forwarding
Alaska
New York
Germany
Bangkok
Bangkok  Germany
Bangkok 
 New
Alaska
York  Alaska
Next hop keep changing
7
Source Independence Routing

Next hop depends on


destination network of the packet
Not the source!
 Source Independence
Bangkok  Germany  New York  Alaska
Forwarding packet uses the destination address in the packet
8
Example: IP Routing Table
Router# show ip route
Codes: I - IGRP derived, R - RIP derived, O - OSPF derived,
C - connected, S - static, E - EGP derived, B - BGP derived,
* - candidate default route, IA - OSPF inter area route,
i - IS-IS derived, ia - IS-IS, U - per-user static route,
o - on-demand routing, M - mobile, P - periodic downloaded static route,
D - EIGRP, EX - EIGRP external, E1 - OSPF external type 1 route,
E2 - OSPF external type 2 route, N1 - OSPF NSSA external type 1 route,
N2 - OSPF NSSA external type 2 route
C
C
D
D
D
C
C
162.100.0.0/16 is variably subnetted, 6 subnets, 2 masks
162.100.0.0/29 is directly connected, Ethernet0
162.100.0.8/29 [90/2195456] via 162.100.0.26, 00:03:27, Serial0
162.100.0.16/29 [90/2172416] via 162.100.0.33, 00:03:15, Serial1
162.100.0.28/30 [90/2195456] via 162.100.0.26, 00:03:27, Serial0
162.100.0.24/30 is directly connected, Serial0
162.100.0.32/30 is directly connected, Serial1
9
Packet forwarding (Routing)


Router reads destination IP address
Router finds out the network address


destination IP & Mask  network address
192.4.10.15 & 255.255.255.0  192.4.10.0
192
4
10
15
1100 0000 0000 0100 0000 1010 0000 1111
255 1111 1111 1111 1111 1111 1111 0000 0000
1100 0000 0000 0100 0000 1010 0000 0000

&
Use network add to look for next hop
in routing table
10
Longest Prefix Match

Internet forwarding tables can contain a default
entry


A network manager can specify a host-specific
route


that provides a path for all destinations that are not
explicitly listed
it directs traffic destined to a specific host along a
different path than traffic for other hosts on the same
network
An important feature of an Internet forwarding
table is that address masks can overlap
11
Example: Longest Prefix Match

Router A's routing table contains two entries




128.10.0.0/16 to Router B
128.10.2.0/24 to Router C
Router A receives a packet destined to 128.10.2.3
Both entries match the destination address

Which entry should be used?


The one with the longest prefix
Router A will choose the entry that corresponds to
128.10.2.0/24

The packet is sent out to Router C
12
Dynamic Routing

How is the routing table constructed anyway?



Network admin inputs manually  too much work!
Routers contain special software running a routing
protocol for automatic route computation
Route computation works on a graph that models
the network

Each node corresponds to a packet switch


(individual computers are not part of the graph)
An edge (link) denotes a direct connection between
a pair of packet switches
13
Modeling Network
node
Edge
Network
A Graph representation
14
Routing Table
node
Edge = (u,v)
15
Default Routes
• One default
• Lowest priority
> 1 destination with same next-hop
16
Routing Table Construction

Static Routing




Manual configure
Simple and low overhead
Inflexible
Dynamic Routing



Automatic changing
Change according to network problems
Mostly use
17
Distributed Route Computation

In practice, networks need to perform
distributed route computation

All packet switches must participate in distributed
route computation


No central entity to do computation
There are two general forms:


Link-State Routing (LSR)
Distance-Vector Routing (DVR)
18
Link-State Routing (LSR)




Also known as Shortest Path First (SPF) routing
Dijkstra algorithm used it to characterize the way it works
To use LSR, packet switches periodically send messages
across the network that carry the status of a link
Every switch collects
incoming status messages

and uses them to build
a graph of the network
19
Dijkstra's Algorithm


Uses a greedy
approach to select
the next node into
the shortest path
tree
Assumes nonnegative weight
edges
20
Dijkstra’s Algorithm Animation
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
21
Distance Vector Routing (DVR)




Uses Distributed Bellman-Ford Algorithm
Like LSR, DVR arranges for packet switches to
exchange messages periodically
In DVR, a switch sends a complete list of
destinations and the current cost of reaching each
When it sends a DVR message

a switch is sending a series of individual statements, of
the form:
“I can reach destination X, and its current distance
from me is Y”
22
DVR Concept
23
Hop Count
2 hops
1 hop
24
Routing table distribution
25
Updating routing table

For router A
26
Final routing tables
27
Updating the routing table

Example
28
Routing Problems


In theory, either LSR or DVR will compute shortest paths
Furthermore, each approach will eventually converge


However, problems do occur


meaning that the forwarding tables in all packet switches agree
For example, if LSR messages are lost, two packet switches can
disagree about the shortest path
DVR problems can be more severe

because a link failure can cause two or more packet switches to
create a routing loop


in which each packet switch thinks the next packet switch in the set is
the shortest path to a particular destination
As a result, a packet can circulate among the switches indefinitely
29
IPv4 Datagram
30
IP Datagram (IPv4)
Payload
Overhead
31
IP Datagram


Version
Header Length



Type of Services


unit: 4-byte word
Normally: 5
prioritize, routing
Datagram Length (data + header)

Size limitation
32
IP Datagram

Fragmentation ID


Break/Group
Flag and Offset


Fragmentation
Control
MTU

Maximum Transmission Unit
33
Fragmentation
Ethernet
1,500 bytes
FDDI
4,352 bytes
Token Ring
17,756 bytes
34
Fragmentation
Application Data
IP
Header
IP
Header
Payload
Payload
Smaller MTU
Pay
IP
Header load
IP
Header
IP
Header
Payload
Payload
Pay
IP
Header load
35
IP Datagram

TTL



avoid looping
hop count (not
time count)
TCP (60)
36
IP Datagram

Protocol

identify the protocol in payload
Protocol No.
Protocol Name
RFC
1
2
4
ICMP
IGMP
IP encapsulated
792
1112
2003
6
17
89
TCP
UDP
OSPF
793
768
2328
37
IP Datagram

Header Checksum



for header only  fast speed
How about Data ???
regular checksum detection is not really accurate



1-byte data with 1-byte checksum
add/subtract
IP uses 1’s compliment checksum

Overflow!
38
IP Address
32 bits
32 bits
39