Transcript Chapter 8

Internet Protocol:
Routing IP Datagrams
Chapter 8
Introduction
• All internet services use an underlying,
connectionless packet delivery system and the
basic unit of transfer in TCP/IP is a datagram
• This chapter shows how routers forward
datagrams and deliver them to the final
destinations
Routing in an Internet
• Routing refers to choosing a path over which to
send packets
• A router is the computer making the choice of that
path
• Ideally, to find the best path, routing software
would look at such factors as:
– network load, datagram length, or type of service
• Most routing software is not that sophisticated and
looks at “shortest path”
Routing in an Internet
• Routers have direct connections to two or more
networks
• Both hosts and routers participate in routing a
datagram to its destination
• The source host makes an initial routing decision
as to which router it should forward its datagram
• Sometimes a machine could function as a host or a
router, but distinctions must be made
Figure 8.1
Direct and Indirect Delivery
• Direct delivery
– transmission of a datagram across a single
physical network directly to another
– both machines attach directly to the same
underlying physical transmission system
• Indirect delivery
– the destination is not on a directly attached
network
– the sender passes the datagram to a router for
delivery
Datagram Delivery over a Single
Network
• To transfer an IP datagram, the sender
– encapsulates the datagram in a frame
– maps the destination IP address into a physical
address (eg. using ARP)
– uses the network hardware to deliver it
• How does the sender know if the destination lies
on a directly connected network (this network)?
– by comparing the network portion of the IP @
with its own
Table-Driven IP Routing
• There is an IP routing table on each machine:
router or host
• This table stores information about possible
destinations and how to reach them
• What information is stored in a routing table?
– (N, R) pairs
– where N is the IP @ of a destination network
– and R is the IP @ of the next router on the path
to that network
Next-Hop Routing
• The routing table indicates only the next step
along the path from R to N
• Each entry in the routing table points to a router
that can be reached across a single network
• All routers (R) listed in a machine’s routing table
must be directly connected to this machine
• See Figure 8.2 (next slide)
• The size of a routing table depends on the number
of networks in the internet
Figure 8.2
Next-Hop Routing
• To hide information, routing tables should be kept
small
• IP routing software only keeps information about
destination network addresses, not individual hosts
• Consequences:
– all traffic destined for a network takes same path
– don’t know if destination host is even operational
Default Routes
• If no route appears in the routing table for a
particular network, the datagram could be sent to a
default router
• This is good when a site has a small set of local
addresses and only one connection to the rest of
the internet
• Two tests are done in this case:
– one for hosts on the local network
– a default that points to the only router
Host-Specific Routes
• Most IP routing software allows per-host routes to
be specified
• The ability to specify a special route to one
machine may be useful
The IP Routing Algorithm
Extract destination IP address D from the datagram
Compute the network prefix N
If N matches any directly connected network address
Get D’s hardware address
Encapsulate the datagram in a frame
Send the frame to D
Else If the table contains a host-specific route for D
Build a frame and send it to the next-hop specified
Else If the table contains a route for network N
Build and send a frame to the next-hop specified
Else If the table contains a default route, send it
Else declare a routing error
Routing with IP Addresses
• The original datagram is not altered during routing
• Specifically, the source and destination IP @s are
unchanged
• When IP executes the routing algorithm, it selects
a new IP address, the IP @ of the machine to
which the datagram is to be sent on its next hop
• The network interface software binds the next hop
@ to a hardware @, forms a frame, places the
datagram in the data portion of the frame and
sends it
Routing with IP Addresses
• Why doesn’t the IP software use hardware
addresses when storing and computing routes?
– routes are easier to examine and change
– to hide the details of the underlying networks - this
allows the underlying network architecture to be
changed without having to update tables
• See the address boundary shown in Figure 8.4
– a conceptual division between low-level software that
understands hardware addresses and internet software
that understands high-level addresses
Figure 8.4
Handling Incoming Datagrams
• When an IP datagram arrives at a host:
– the network interface software delivers it to the IP
module for processing
– if the datagram’s destination @ matches the host’s IP
@, IP software on the host accepts the datagram, and
passes it to a higher level protocol software for further
processing
– if no match, the datagram is discarded
Handling Incoming Datagrams
• When an IP datagram arrives at a router:
– the network interface software delivers it to the IP
module for processing
– if the datagram’s destination @ matches the router’s IP
@, IP software on the host accepts the datagram, and
passes it to a higher level protocol software for further
processing - usually for testing and router management
– if not a match, the TTL is decremented, the checksum is
recomputed and the datagram is forwarded, using the
routing table and the routing algorithm
• Hosts should not perform router functions
Summary
• Direct delivery is possible if the destination
machine is on a network to which the sending
machine attaches
• Otherwise, the sender forwards the datagram to a
router
• Datagrams travel from router to router until they
reach their final destination. Or?
• Transmission of a datagram from one machine to
the next requires encapsulating it in a frame
For Next Time
• Read Chapter 9
• Make the equivalent of about 15 slides
outlining Chapters 8 and 9