Dynamic Host Configuration Protocol (DHCP)

We have seen that a large organization or an ISP can receive a block of addresses directly
from ICANN and a small organization can receive a block of addresses from an ISP. After a
block of addresses are assigned to an organization, the network administration can manually
assign addresses to the individual hosts or routers. However, address assignment in an
organization can be done automatically using the Dynamic Host Configuration Protocol
(DHCP). DHCP is an application-layer program, using the client-server paradigm, that
actually helps TCP/IP at the network layer.
DHCP has found such widespread use in the Internet that it is often called a plug- and-play
protocol. In can be used in many situations. A network manager can configure DHCP to assign
permanent IP addresses to the host and routers. DHCP can also be con- figured to provide
temporary, on demand, IP addresses to hosts. The second capability can provide a temporary
IP address to a traveler to connect her laptop to the Internet while she is staying in the hotel.
It also allows an ISP with 1000 granted addresses to provide services to 4000 households,
assuming not more than one-forth of customers use the Internet at the same time.
In addition to its IP address, a computer also needs to know the network prefix (or address
mask). Most computers also need two other pieces of information, such as the address of a
default router to be able to communicate with other networks and the address of a name server
to be able to use names instead of addresses, as we will see in Chapter 26. In other words, four
pieces of information are normally needed: the computer address, the prefix, the address of a
router, and the IP address of a name server. DHCP can be used to provide these pieces of
information to the host.

DHCP Message Format

DHCP is a client-server protocol in which the client sends a request message and the server
returns a response message. Before we discuss the operation of DHCP, let us show the general
format of the DHCP message in Figure Most of the fields are explained in the figure, but we
need to discuss the option field, which plays a very important role in DHCP.
The 64-byte option field has a dual purpose. It can carry either additional information or
some specific vendor information. The server uses a number, called a magic cookie, in the
format of an IP address with the value of [Link]. When the client finishes reading the
message, it looks for this magic cookie. If present, the next 60 bytes are options. An option
is composed of three fields: a 1-byte tag field, a 1-byte length field, and a variable-length
value field. There are several tag fields that are mostly used by vendors. If the tag field is
53, the value field defines one of the 8 message types shown in Figure . We show how these
message types are used by DHCP.

Option format

Operation of DHCP
1)The joining host creates a DHCPDISCOVER message in which only the transaction- ID field
is set to a random number. No other field can be set because the host has no knowledge with
which to do so. This message is encapsulated in a UDP user datagram with the source port set
to 68 and the destination port set to 67. We will discuss the reason for using two well-known
port numbers later. The user datagram is encapsulated in an IP datagram with the source
address set to [Link] (“this host”) and the destination address set to [Link]
(broadcast address). The reason is that the joining host knows neither its own address nor the
server address.

2)The DHCP server or servers (if more than one) responds with a DHCPOFFER message in
which the your address field defines the offered IP address for the joining host and the server
address field includes the IP address of the server. The message also includes the lease time
for which the host can keep the IP address. This message is encapsulated in a user datagram
with the same port numbers, but in the reverse order. The user datagram in turn is encapsulated
in a datagram with the server address as the source IP address, but the destination address is
a broadcast address, in which the server allows other DHCP servers to receive the offer and
give a better offer if they can.

3)The joining host receives one or more offers and selects the best of them. The joining host
then sends a DHCPREQUEST message to the server that has given the best offer. The fields
with known value are set. The message is encapsulated in a user datagram with port numbers
as the first message. The user datagram is encapsulated in an IP datagram with the source
address set to the new client address, but the destination address still is set to the broadcast
address to let the other servers know that their offer was not accepted.

4)Finally, the selected server responds with a DHCPACK message to the client if the
offered IP address is valid. If the server cannot keep its offer (for example, if the address
is offered to another host in between), the server sends a DHCPNACK message and the
client needs to repeat the process. This message is also broadcast to let other servers know
that the request is accepted or rejected.
Two Well-Known Ports
We said that the DHCP uses two well-known ports (68 and 67) instead of one well-known
and one ephemeral. The reason for choosing the well-known port 68 instead of an ephemeral
port for the client is that the response from the server to the client is broadcast. Remember
that an IP datagram with the limited broadcast message is delivered to every host on the
network. Now assume that a DHCP client and a DAYTIME client, for example, are both
waiting to receive a response from their corresponding server and both have accidentally
used the same temporary port number (56017, for example). Both hosts receive the
response message from the DHCP server and deliver the message to their cli- ents. The
DHCP client processes the message; the DAYTIME client is totally confused with a strange
message received. Using a well-known port number prevents this problem from happening.
The response message from the DHCP server is not delivered to the DAYTIME client,
which is running on the port number 56017, not 68. The temporary port numbers are
selected from a different range than the well-known port numbers.
The curious reader may ask what happens if two DHCP clients are running at the same
time. This can happen after a power failure and power restoration. In this case the messages
can be distinguished by the value of the transaction ID, which separates each response
from the other.
Using FTP
The server does not send all of the information that a client may need for joining the net-
work. In the DHCPACK message, the server defines the pathname of a file in which the
client can find complete information such as the address of the DNS server. The client can
then use a file transfer protocol to obtain the rest of the needed information.
Error Control
DHCP uses the service of UDP, which is not reliable. To provide error control, DHCP uses
two strategies. First, DHCP requires that UDP use the checksum. As we will see in Chapter
24, the use of the checksum in UDP is optional. Second, the DHCP client uses timers and
a retransmission policy if it does not receive the DHCP reply to a request. How- ever, to
prevent a traffic jam when several hosts need to retransmit a request (for example, after a
power failure), DHCP forces the client to use a random number to set its timers.
Transition States
The previous scenarios we discussed for the operation of the DHCP were very simple. To provide
dynamic address allocation, the DHCP client acts as a state machine that performs transitions
from one state to another depending on the messages it receives or sends. Figure shows the
transition diagram with the main states.

When the DHCP client first starts, it is in the INIT state (initializing state). The client
broadcasts a discover message. When it receives an offer, the client goes to the SELECTING
state. While it is there, it may receive more offers. After it selects an offer, it sends a request
message and goes to the REQUESTING state. If an ACK arrives while the client is in this state,
it goes to the BOUND state and uses the IP address. When the lease is 50 percent expired, the
client tries to renew it by moving to the RENEWING state. If the server renews the lease, the
client moves to the BOUND state again. If the lease is not renewed and the lease time is 75
percent expired, the client moves to the REBINDING state. If the server agrees with the lease
(ACK message arrives), the client moves to the BOUND state and continues using the IP
address; otherwise, the client moves to the INIT state and requests another IP address. Note that
the client can use the IP address only when it is in the BOUND, RENEWING, or REBINDING
state. The above procedure requires that the client uses three timers: renewal timer (set to 50
percent of the lease time), rebinding timer (set to 75 percent of the lease time), and expiration
timer (set to the lease time).

Network Address Resolution (NAT)

The distribution of addresses through ISPs has created a new problem. Assume that an ISP
has granted a small range of addresses to a small business or a household. If the business
grows or the household needs a larger range, the ISP may not be able to grant the demand
because the addresses before and after the range may have already been allocated to other
networks. In most situations, however, only a portion of computers in
a small network need access to the Internet simultaneously. This means that the number of
allocated addresses does not have to match the number of computers in the network. For
example, assume that in a small business with 20 computers the maximum number of
computers that access the Internet simultaneously is only 4. Most of the computers are
either doing some task that does not need Internet access or communicating with each
other. This small business can use the TCP/IP protocol for both internal and universal
communication. The business can use 20 (or 25) addresses from the private block
addresses (discussed before) for internal communication; five addresses for universal
communication can be assigned by the ISP.

A technology that can provide the mapping between the private and universal
addresses, and at the same time support virtual private networks, which we discuss in
Chapter 32, is Network Address Translation (NAT). The technology allows a site to use
a set of private addresses for internal communication and a set of global Internet addresses
(at least one) for communication with the rest of the world. The site must have only one
connection to the global Internet through a NAT-capable router that runs NAT software.
Figure shows a simple implementation of NAT.

As the figure shows, the private network uses private addresses. The router that
connects the network to the global address uses one private address and one global address.
The private network is invisible to the rest of the Internet; the rest of the Inter- net sees
only the NAT router with the address [Link].
Address Translation
All of the outgoing packets go through the NAT router, which replaces the source address
in the packet with the global NAT address. All incoming packets also pass through the
NAT router, which replaces the destination address in the packet (the NAT router global
address) with the appropriate private address. Figure shows an example of address
translation.
Translation Table
The reader may have noticed that translating the source addresses for an outgoing packet
is straightforward. But how does the NAT router know the destination address for a packet
coming from the Internet? There may be tens or hundreds of private IP addresses, each
belonging to one specific host. The problem is solved if the NAT router has a translation
table.

Using One IP Address

In its simplest form, a translation table has only two columns: the private address and the
external address (destination address of the packet). When the router translates the source
address of the outgoing packet, it also makes note of the destination address— where the
packet is going. When the response comes back from the destination, the router uses the
source address of the packet (as the external address) to find the private address of the packet.
Figure shows the idea.
In this strategy, communication must always be initiated by the private network. The NAT
mechanism described requires that the private network start the communication.
As we will see, NAT is used mostly by ISPs that assign a single address to a customer. The
customer, however, may be a member of a private network that has many private
addresses. In this case, communication with the Internet is always initiated from the
customer site, using a client program such as HTTP, TELNET, or FTP to access the
corresponding server program. For example, when e-mail that originates from outside the
network site is received by the ISP e-mail server, it is stored in the mailbox of the customer
until retrieved with a protocol such as POP.
Using a Pool of IP Addresses
The use of only one global address by the NAT router allows only one private-network
host to access a given external host. To remove this restriction, the NAT router can use a
pool of global addresses. For example, instead of using only one global address
([Link]), the NAT router can use four addresses ([Link], [Link],
[Link], and [Link]). In this case, four private-network hosts can communicate
with the same external host at the same time because each pair of addresses defines a
separate connection. However, there are still some drawbacks. No more than four
connections can be made to the same destination. No private-network host can access two
external server programs (e.g., HTTP and TELNET) at the same time. And, likewise, two
private-network hosts cannot access the same external server program (e.g., HTTP or
TELNET) at the same time.
Using Both IP Addresses and Port Addresses
To allow a many-to-many relationship between private-network hosts and external server
programs, we need more information in the translation table. For example, sup- pose two
hosts inside a private network with addresses [Link] and [Link] need to access the
HTTP server on external host [Link]. If the translation table has five columns, instead of
two, that include the source and destination port addresses and the transport-layer protocol,
the ambiguity is eliminated. Table shows an example of such a table.

Datagram Format
In this section, we begin by discussing the first service provided by IPv4, packetizing. We
show how IPv4 defines the format of a packet in which the data coming from the upper layer
or other protocols are encapsulated. Packets used by the IP are called data- grams. Figure 19.2
shows the IPv4 datagram format. A datagram is a variable-length packet consisting of two
parts: header and payload (data). The header is 20 to 60 bytes in length and contains
information essential to routing and delivery. It is customary in TCP/IP to show the header in
4-bytesections.
 Discussing the meaning and rationale for the existence of each field is essential to
understanding the operation of IPv4; a brief description of each field is in order.
❑ Version Number. The 4-bit version number (VER) field defines the version of the IPv4
protocol, which, obviously, has the value of 4.
❑ Header Length. The 4-bit header length (HLEN) field defines the total length of the datagram
header in 4-byte words. The IPv4 datagram has a variable-length header. When a device
receives a datagram, it needs to know when the header stops and the data, which is
encapsulated in the packet, starts. However, to make the value of the header length (number
of bytes) fit in a 4-bit header length, the total length of the header is calculated as 4-byte
words. The total length is divided by 4 and the value is inserted in the field. The receiver needs
to multiply the value of this field by 4 to find the total length.
❑ Service Type. In the original design of the IP header, this field was referred to as type of
service (TOS), which defined how the datagram should be handled. In the late 1990s, IETF
redefined the field to provide differentiated services (DiffServ).
When we discuss differentiated services in Chapter 30, we will be in a better situation to
define the bits in this field. The use of 4-byte words for the length header is also logical
because the IP header always needs to be aligned in 4-byte boundaries.
❑ Total Length. This 16-bit field defines the total length (header plus data) of the IP datagram
in bytes. A 16-bit number can define a total length of up to 65,535 (when all bits are 1s).
However, the size of the datagram is normally much less than this. This field helps the
receiving device to know when the packet has completely arrived. To find the length of the
data coming from the upper layer, subtract the header length from the total length. The
header length can be found by multiplying the value in the HLEN field by 4.

Length of data total length (HLEN) 4

 Though a size of 65,535 bytes might seem large, the size of the IPv4 datagram may
increase in the near future as the underlying technologies allow even more throughput
(greater bandwidth).
One may ask why we need this field anyway. When a machine (router or host) receives a
frame, it drops the header and the trailer, leaving the datagram. Why include an extra field
that is not needed? The answer is that in many cases we really do not need the value in this
field. However, there are occasions in which the datagram is not the only thing
encapsulated in a frame; it may be that padding has been added. For example, the Ethernet
protocol has a minimum and maximum restriction on the size of data that can be
encapsulated in a frame (46 to 1500 bytes). If the size of an IPv4 datagram is less than 46
bytes, some padding will be added to meet this requirement. In this case, when a machine
decapsulates the datagram, it needs to check the total length field to determine how much
is really data and how much is padding.
❑ Identification, Flags, and Fragmentation Offset. These three fields are related to the
fragmentation of the IP datagram when the size of the datagram is larger than the
underlying network can carry. We discuss the contents and importance of these fields when
we talk about fragmentation in the next section.
❑ Time-to-live. Due to some malfunctioning of routing protocols (discussed later) a data- gram
may be circulating in the Internet, visiting some networks over and over without reaching the
destination. This may create extra traffic in the Internet. The time-to-live (TTL) field is used
to control the maximum number of hops (routers) visited by the datagram. When a source
host sends the datagram, it stores a number in this field. This value is approximately two times
the maximum number of routers between any two hosts. Each router that processes the
datagram decrements this number by one. If this value, after being decremented, is zero, the
router discards the datagram.
❑ Protocol. In TCP/IP, the data section of a packet, called the payload, carries the whole
packet from another protocol. A datagram, for example, can carry a packet belonging to
any transport-layer protocol such as UDP or TCP. A datagram can also carry a packet from
other protocols that directly use the service of the IP, such as some routing protocols or
some auxiliary protocols. The Internet authority has given any protocol that uses the service
of IP a unique 8-bit number which is inserted in the protocol field. When the payload is
encapsulated in a datagram at the source IP, the corresponding protocol number is
inserted in this field; when the datagram arrives at the destination, the value of this field
helps to define to which protocol the payload should be delivered. In other words, this field
provides multiplexing at the source and demultiplexing at the destination, as shown in
Figure 19.3. Note that the protocol fields at the network layer play the same role as the
port numbers at the transport layer (Chapters 23 and 24). However, we need two port
numbers in a transport-layer packet because the port numbers at the source and
destination are different, but we need only one protocol field because this value is the
same for each protocol no matter whether it is located at the source or the destination.
❑ Header checksum. IP is not a reliable protocol; it does not check whether the pay- load carried
by a datagram is corrupted during the transmission. IP puts the burden of error checking of the
payload on the protocol that owns the payload, such as UDP or TCP. The datagram header,
however, is added by IP, and its error-checking is the responsibility of IP. Errors in the IP
header can be a disaster. For example, if the destination IP address is corrupted, the packet
can be delivered to the wrong host. If the protocol field is corrupted, the payload may be
delivered to the wrong protocol. If the fields related to the fragmentation are corrupted, the
datagram can- not be reassembled correctly at the destination, and so on. For these reasons,
IP adds a header checksum field to check the header, but not the payload. We need to
remember that, since the value of some fields, such as TTL, which are related to fragmentation
and options, may change from router to router, the checksum needs to be recalculated at each
router. As we discussed in Chapter 10, checksum in the Internet normally uses a 16-bit field,
which is the complement of the sum of other fields calculated using 1s complement arithmetic.
❑ Source and Destination Addresses. These 32-bit source and destination address fields define
the IP address of the source and destination respectively. The source host should know its IP
address. The destination IP address is either known by the protocol that uses the service of IP
or is provided by the DNS as described in Chapter 26. Note that the value of these fields must
remain unchanged during the time the IP datagram travels from the source host to the
destination host. IP addresses were discussed in Chapter 18.
❑ Options. A datagram header can have up to 40 bytes of options. Options can be used for
network testing and debugging. Although options are not a required part of the IP header,
option processing is required of the IP software. This means that all implementations
must be able to handle options if they are present in the header. The existence of options
in a header creates some burden on the data- gram handling; some options can be changed
by routers, which forces each router to recalculate the header checksum. There are one-
byte and multi-byte options that we will briefly discuss later in the chapter. The complete
discussion is posted at the book website.
❑ Payload. Payload, or data, is the main reason for creating a datagram. Payload is the packet
coming from other protocols that use the service of IP. Comparing a datagram to a postal
package, payload is the content of the package; the header is only the information written
on the package.
 THE IPv6 PROTOCOL
The change of the IPv6 address size requires the change in the IPv4 packet format. The
designer of IPv6 decided to implement remedies for other shortcomings now that a change
is inevitable. The following shows other changes implemented in the protocol in addition
to changing address size and format.
❑ Better header format. IPv6 uses a new header format in which options are separated from
the base header and inserted, when needed, between the base header and the data. This
simplifies and speeds up the routing process because most of the options do not need to be
checked by routers.
❑ New options. IPv6 has new options to allow for additional functionalities.
❑ Allowance for extension. IPv6 is designed to allow the extension of the protocol if required
by new technologies or applications.
❑ Support for resource allocation. In IPv6, the type-of-service field has been removed, but
two new fields, traffic class and flow label, have been added to enable the source to request
special handling of the packet. This mechanism can be used to support traffic such as real-
time audio and video.
❑ Support for more security. The encryption and authentication options in IPv6 provide
confidentiality and integrity of the packet.

Packet Format
The IPv6 packet is shown in Figure Each packet is composed of a base header followed by
the payload. The base header occupies 40 bytes, whereas payload can be up to 65,535
bytes of information. The description of fields follows.

Version. The 4-bit version field defines the version number of the IP. For IPv6, the value is 6.
Traffic class. The 8-bit traffic class field is used to distinguish different payloads with
different delivery requirements. It replaces the type-of-service field in IPv4.
Flow label. The flow label is a 20-bit field that is designed to provide special handling for a
particular flow of data. We will discuss this field later.
Payload length. The 2-byte payload length field defines the length of the IP datagram
excluding the header. Note that IPv4 defines two fields related to the length: header length
and total length. In IPv6, the length of the base header is fixed (40 bytes); only the length of
the payload needs to be defined.
Next header. The next header is an 8-bit field defining the type of the first extension header
(if present) or the type of the data that follows the base header in the datagram. This field is
similar to the protocol field in IPv4, but we talk more about it when we discuss the payload.
Hop limit. The 8-bit hop limit field serves the same purpose as the TTL field in IPv4.
Source and destination addresses. The source address field is a 16-byte (128-bit) Internet
address that identifies the original source of the datagram. The destination address field is a
16-byte (128-bit) Internet address that identifies the destination of the datagram.
Payload. Compared to IPv4, the payload field in IPv6 has a different format and meaning, as
shown in Figure

The payload in IPv6 means a combination of zero or more extension headers (options)
followed by the data from other protocols (UDP, TCP, and so on). In IPv6, options, which are
part of the header in IPv4, are designed as extension headers. The payload can have as many
extension headers as required by the situation. Each extension header has two mandatory
fields, next header and the length,
followed by information related to the particular option. Note that each next header field
value (code) defines the type of the next header (hop-by-hop option, source- routing
option,- - - - - ; the last next header field defines the protocol (UDP, TCP, - - - - ) that is
carried by the datagram.

Concept of Flow and Priority in IPv6

The IP protocol was originally designed as a connectionless protocol. However, the
tendency is to use the IP protocol as a connection-oriented protocol. The MPLS technology
described earlier allows us to encapsulate an IPv4 packet in an MPLS header using a label
field. In version 6, the flow label has been directly added to the format of the IPv6 datagram
to allow us to use IPv6 as a connection-oriented protocol.
To a router, a flow is a sequence of packets that share the same characteristics, such as
traveling the same path, using the same resources, having the same kind of security, and
so on. A router that supports the handling of flow labels has a flow label table. The table
has an entry for each active flow label; each entry defines the services required by the
corresponding flow label. When the router receives a packet, it consults its flow label table
to find the corresponding entry for the flow label value defined in the packet. It then
provides the packet with the services mentioned in the entry. However, note that the flow
label itself does not provide the information for the entries of the flow label table; the
information is provided by other means, such as the hop-by-hop options or other protocols.
In its simplest form, a flow label can be used to speed up the processing of a packet by
a router. When a router receives a packet, instead of consulting the forwarding table and
going through a routing algorithm to define the address of the next hop, it can easily look in
a flow label table for the next hop.
In its more sophisticated form, a flow label can be used to support the transmission of
real-time audio and video. Real-time audio or video, particularly in digital form, requires
resources such as high bandwidth, large buffers, long processing time, and so on. A process
can make a reservation for these resources beforehand to guarantee that real-time data will not
be delayed due to a lack of resources. The use of real-time data and the reservation of these
resources require other protocols such as Real-Time Transport Protocol (RTP) and Resource
Reservation Protocol (RSVP) in addition to IPv6 (see Chapter 28).
Fragmentation and Reassembly
There are still fragmentation and reassembly of datagrams in the IPv6 protocol, but there is
a major difference in this respect. IPv6 datagrams can be fragmented only by the source,
not by the routers; the reassembly takes place at the destination. The fragmentation of
packets at routers is not allowed to speed up the processing of packets in the router. The
fragmentation of a packet in a router needs a lot of processing. The packet needs to be
fragmented, all fields related to the fragmentation need to be recalculated. In IPv6, the
source can check the size of the packet and make the decision to fragment the packet or
not. When a router receives the packet, it can check the size of the packet and drop it if the
size is larger than allowed by the MTU of the network ahead. The router then sends a packet-
too-big ICMPv6 error message (discussed later) to inform the source.

Extension Header
An IPv6 packet is made of a base header and some extension headers. The length of the base
header is fixed at 40 bytes. However, to give more functionality to the IP data- gram, the base
header can be followed by up to six extension headers. Many of these headers are options in
IPv4. Six types of extension headers have been defined. These are hop-by-hop option, source
routing, fragmentation, authentication, encrypted security payload, and destination option
We briefly describe the extension headers in this section, but the complete description is
posted at the book website.
Hop-by-Hop Option
The hop-by-hop option is used when the source needs to pass information to all routers visited
by the datagram. For example, perhaps routers must be informed about certain management,
debugging, or control functions. Or, if the length of the datagram is more than the usual 65,535
bytes, routers must have this information. So far, only three hop- by-hop options have been
defined: Pad1, PadN, and jumbo payload.
Pad1. This option is 1 byte long and is designed for alignment purposes. Some options need
to start at a specific bit of the 32-bit word. If an option falls short of this requirement by
exactly one byte, Pad1 is added.
PadN. PadN is similar in concept to Pad1. The difference is that PadN is used when 2 or more
bytes are needed for alignment.
Jumbo payload. Recall that the length of the payload in the IP datagram can be a maximum
of 65,535 bytes. However, if for any reason a longer payload is required, we can use the jumbo
payload option to define this longer length.
Destination Option
The destination option is used when the source needs to pass information to the destination
only. Intermediate routers are not permitted access to this information. The format of the
destination option is the same as the hop-by-hop option. So far, only the Pad1 and PadN
options have been defined.
Source Routing
The source routing extension header combines the concepts of the strict source route and
the loose source route options of IPv4.
Fragmentation
The concept of fragmentation in IPv6 is the same as that in IPv4. However, the place
where fragmentation occurs differs. In IPv4, the source or a router is required to fragment
if the size of the datagram is larger than the MTU of the network over which the datagram
travels. In IPv6, only the original source can fragment. A source must use a Path MTU
Discovery technique to find the smallest MTU supported by any network on the path. The
source then fragments using this knowledge.
If the source does not use a Path MTU Discovery technique, it fragments the data-
gram to a size of 1280 bytes or smaller. This is the minimum size of MTU required for
each network connected to the Internet.
Authentication
The authentication extension header has a dual purpose: it validates the message sender
and ensures the integrity of data. The former is needed so the receiver can be sure that a
message is from the genuine sender and not from an imposter. The latter is needed to check
that the data is not altered in transition by some hacker. We discuss more about
authentication
Encrypted Security Payload
The encrypted security payload (ESP) is an extension that provides confidentiality and
guards against eavesdropping. Again, we discuss providing more confidentiality for IP
packets .
Comparison of Options between IPv4 and IPv6
The following shows a quick comparison between the options used in IPv4 and the
options used in IPv6 (as extension headers).
❑ The no-operation and end-of-option options in IPv4 are replaced by Pad1
and PadN options in IPv6.
❑ The record route option is not implemented in IPv6 because it was not used.
❑ The timestamp option is not implemented because it was not used.
❑ The source route option is called the source route extension header in IPv6.
❑ The fragmentation fields in the base header section of IPv4 have moved to the
frag- mentation extension header in IPv6.
❑ The authentication extension header is new in IPv6.
❑ The encrypted security payload extension header is new in IPv6.

INTRODUCTION
Unicast routing in the Internet, with a large number of routers and a huge number of hosts,
can be done only by using hierarchical routing: routing in several steps using different
routing algorithms. In this section, we first discuss the general concept of unicast routing
in an internet: an internetwork made of networks connected by routers. After the routing
concepts and algorithms are understood, we show how we can apply them to the Internet
using hierarchical routing.
General Idea
In unicast routing, a packet is routed, hop by hop, from its source to its destination by the
help of forwarding tables. The source host needs no forwarding table because it delivers
its packet to the default router in its local network. The destination host needs no
forwarding table either because it receives the packet from its default router in its local
network. This means that only the routers that glue together the networks in the internet
need forwarding tables. With the above explanation, routing a packet from its source to its
destination means routing the packet from a source router (the default router of the source
host) to a destination router (the router connected to the destination network). Although a
packet needs to visit the source and the destination routers, the question is what other
routers the packet should visit. In other words, there are several routes that a packet can
travel from the source to the destination; what must be deter- mined is which route the
packet should take.
An Internet as a Graph
To find the best route, an internet can be modeled as a graph. A graph in computer science
is a set of nodes and edges (lines) that connect the nodes. To model an internet as a graph,
we can think of each router as a node and each network between a pair of routers as an
edge. An internet is, in fact, modeled as a weighted graph, in which each edge is associated
with a cost. If a weighted graph is used to represent a geographical area, the nodes can be
cities and the edges can be roads connecting the cities; the weights, in this case, are
distances between cities. In routing, however, the cost of an edge has a different
interpretation in different routing protocols, which we discuss in a later section. For the
moment, we assume that there is a cost associated with each edge. If there is no edge
between the nodes, the cost is infinity. Figure shows how an internet can be modeled as a
graph.

Least-Cost Routing
When an internet is modeled as a weighted graph, one of the ways to interpret the best
route from the source router to the destination router is to find the least cost between the
two. In other words, the source router chooses a route to the destination router in such a
way that the total cost for the route is the least cost among all possible routes. In Figure the
best route between A and E is A-B-E, with the cost of 6. This means that each router needs
to find the least-cost route between itself and all the other routers to be able to route a packet
using this criteria.

Least-Cost Trees
If there are N routers in an internet, there are (N - 1) least-cost paths from each router to any
other router. This means we need N  (N - 1) least-cost paths for the whole internet. If we have
only 10 routers in an internet, we need 90 least-cost paths. A better way to see all of these paths
is to combine them in a least-cost tree. A least-cost tree is a tree with the source router as the
root that spans the whole graph (visits all other nodes) and in which the path between the root
and any other node is the shortest. In this way, we can have only one shortest-path tree for each
node; we have N least-cost trees for the whole internet. We show how to create a least-cost tree
for each node later in this section; for the moment, Figure shows the seven least-cost trees for
the internet.

The least-cost trees for a weighted graph can have several properties if they are created
using consistent criteria.
1)The least-cost route from X to Y in X’s tree is the inverse of the least-cost route from Y
to X in Y’s tree; the cost in both directions is the same. For example, in Figure , the route
from A to F in A’s tree is (A → B → E → F), but the route from F to A in F’s tree is (F →E
→B → A), which is the inverse of the first route. The cost is 8 in each case.
2)Instead of travelling from X to Z using X’s tree, we can travel from X to Y using X’s
tree and continue from Y to Z using Y’s tree. For example, in Figure , we can go from A
to G in A’s tree using the route (A → B → E → F → G). We can also go from A to E in A’s
tree (A → B → E) and then continue in E’s tree using the route (E → F → G). The
combination of the two routes in the second case is the same route as in the first case. The
cost in the first case is 9; the cost in the second case is also 9 (6 + 3).

ROUTING ALGORITHMS
After discussing the general idea behind least-cost trees and the forwarding tables that can
be made from them, now we concentrate on the routing algorithms. Several routing
algorithms have been designed in the past. The differences between these methods are in
the way they interpret the least cost and the way they create the least-cost tree for each
node. In this section, we discuss the common algorithms; later we show how a routing
protocol in the Internet implements one of these algorithms.

Distance-Vector Routing
The distance-vector (DV) routing uses the goal we discussed in the introduction, to find
the best route. In distance-vector routing, the first thing each node creates is its own least-
cost tree with the rudimentary information it has about its immediate neighbors. The
incomplete trees are exchanged between immediate neighbors to make the trees more and
more complete and to represent the whole internet. We can say that in distance-vector
routing, a router continuously tells all of its neighbors what it knows about the whole
internet (although the knowledge can be incomplete).
Before we show how incomplete least-cost trees can be combined to make complete
ones, we need to discuss two important topics: the Bellman-Ford equation and the concept
of distance vectors, which we cover next.
Bellman-Ford Equation
The heart of distance-vector routing is the famous Bellman-Ford equation. This equation is
used to find the least cost (shortest distance) between a source node, x, and a destination
node, y, through some intermediary nodes (a, b, c,   ) when the costs between the source
and the intermediary nodes and the least costs between the intermediary nodes and
the destination are given. The following shows the general case in which Dij is the short-
est distance and cij is the cost between nodes i and j.
Dxy = min{(cxa + Day), (cxb + Dby), (cxc + Dcy), }

In distance-vector routing, normally we want to update an existing least cost with a least cost
through an intermediary node, such as z, if the latter is shorter. In this case, the equation becomes

Dxy = min{Dxy, (cxz + Dzy)}

simpler, as shown below:

that the name of the distance vector defines the root, the indexes define the destinations, and the
value of each cell defines the least cost from the root to the destination. A distance vector does
not give the path to the destinations as the least-cost tree does; it gives only the least costs to
the destinations. Later we show how we can change a distance vector to a forwarding table, but
we first need to find We can say that the Bellman-Ford equation enables us to build a new
least-cost path from previously established least-cost paths. In Figure we can think of
(a → y), (b → y), and (c → y) as previously established least-cost paths and (x → y) as the new
least-cost path. We can even think of this equation as the builder of a new least-cost tree from
previously established least-cost trees if we use the equation repeatedly. In other words, the
use of this equation in distance-vector routing is a witness that this method also uses least-
cost trees, but this use may be in the background.
We will shortly show how we use the Bellman-Ford equation and the concept of distance
vectors to build least-cost paths for each node in distance-vector routing, but first we need to
discuss the concept of a distance vector.
Distance Vectors
The concept of a distance vector is the rationale for the name distance-vector routing. A
least-cost tree is a combination of least-cost paths from the root of the tree to all destinations.
These paths are graphically glued together to form the tree. Distance-vector routing unglues
these paths and creates a distance vector, a one-dimensional array to represent the tree. Figure
shows the tree for node A in the internet in Figure and the corresponding distance vector.
Note all distance vectors for an internet.
We know that a distance vector can represent least-cost paths in a least-cost tree, but the
question is how each node in an internet originally creates the corresponding vector. Each
node in an internet, when it is booted, creates a very rudimentary distance vector with the
minimum information the node can obtain from its neighborhood. The node sends some
greeting messages out of its interfaces and discovers the identity of the immediate neighbors
and the distance between itself and each neighbor. It then

makes a simple distance vector by inserting the discovered distances in the corresponding
cells and leaves the value of other cells as infinity. Do these distance vectors represent
least-cost paths? They do, considering the limited information a node has. When we know
only one distance between two nodes, it is the least cost. Figure shows all distance vectors
for our internet. However, we need to mention that these vectors are made asynchronously,
when the corresponding node has been booted; the existence of all of them in a figure does
not mean synchronous creation of them.
These rudimentary vectors cannot help the internet to effectively forward a packet. For
example, node A thinks that it is not connected to node G because the corresponding cell shows
the least cost of infinity. To improve these vectors, the nodes in the internet need to help each
other by exchanging information. After each node has created its vector, it sends a copy of the
vector to all its immediate neighbors. After a node receives a distance vector from a neighbor,
it updates its distance vector using the Bellman-Ford equation (second case). However, we
need to understand that we need to update, not only one least cost, but N of them in which N
is the number of the nodes in the internet. If we are using a program, we can do this using a
loop; if we are showing the concept on paper, we can show the whole vector instead of the N
separate equations. We show the whole vector instead of seven equations for each update in
Figure The figure shows two asynchronous events, happening one after another with some
time in
between. In the first event, node A has sent its vector to node B. Node B updates its vector
using the cost cBA = 2. In the second event, node E has sent its vector to node B. Node B
updates its vector using the cost cEA = 4.
After the first event, node B has one improvement in its vector: its least cost to
node D has changed from infinity to 5 (via node A). After the second event, node B has one
more improvement in its vector; its least cost to node F has changed from infinity to 6 (via
node E). We hope that we have convinced the reader that exchanging vectors eventually
stabilizes the system and allows all nodes to find the ultimate least cost between themselves
and any other node. We need to remember that after updating a node, it immediately sends its
updated vector to all neighbors. Even if its neighbors have received the previous vector, the
updated one may help more.

Distance-Vector Routing Algorithm

information is A, it can replace the distance with infinity as a warning: “Do not use this
value; what I know about this route comes from you.”
Three-Node Instability
The two-node instability can be avoided using split horizon combined with poison
reverse. However, if the instability is between three nodes, stability cannot be guaranteed.

Link-State Routing
A routing algorithm that directly follows our discussion for creating least-cost trees and
forwarding tables is link-state (LS) routing. This method uses the term link-state to define
the characteristic of a link (an edge) that represents a network in the internet. In this
algorithm the cost associated with an edge defines the state of the link. Links with lower
costs are preferred to links with higher costs; if the cost of a link is infinity, it means that
the link does not exist or has been broken.
Link-State Database (LSDB)
To create a least-cost tree with this method, each node needs to have a complete map of the
network, which means it needs to know the state of each link. The collection of states for all
links is called the link-state database (LSDB). There is only one LSDB for the whole
internet; each node needs to have a duplicate of it to be able to create the least-cost tree.
Figure shows an example of an LSDB for the graph in Figure The LSDB can be represented
as a two-dimensional array(matrix) in which the value of each cell defines the cost of the
corresponding link.

Now the question is how each node can create this LSDB that contains information about the
whole internet. This can be done by a process called flooding. Each node can send some
greeting messages to all its immediate neighbors (those nodes to which it is connected
directly) to collect two pieces of information for each neighboring node: the identity of the
node and the cost of the link. The combination of these two pieces of information is called
the LS packet (LSP); the LSP is sent out of each interface, as shown in Figure for our internet
in Figure When a node receives an LSP from one of its interfaces, it compares the LSP with
the copy it may already have. If the newly arrived LSP is older than the one it has (found by
checking the sequence number), it discards the LSP. If it is newer or the first one received, the
node discards the old LSP (if there is one) and keeps the received one. It then sends a copy of
it out of each interface except the one from which the packet arrived. This guarantees that
flooding stops somewhere in the network (where a node has only one interface). We need to
 convince ourselves that, after receiving all new LSPs, each node creates the comprehensive
LSDB as shown in Figure This LSDB is the same for each node and shows the whole map
of the internet. In other words, a node can make the whole map if it needs to, using this LSDB.

We can compare the link-state routing algorithm with the distance-vector routing algorithm.
In the distance-vector routing algorithm, each router tells its neighbors what it knows about
the whole internet; in the link-state routing algorithm, each router tells the whole internet what
it knows about its neighbors.

Formation of least cost tree

To create a least-cost tree for itself, using the shared LSDB, each node needs to run the famous
Dijkstra Algorithm. This iterative algorithm uses the following steps:
1. The node chooses itself as the root of the tree, creating a tree with a single node, and sets the
total cost of each node based on the information in the LSDB.
2. The node selects one node, among all nodes not in the tree, which is closest to the root, and
adds this to the tree. After this node is added to the tree, the cost of all other nodes not in the tree
needs to be updated because the paths may have been changed.
3. The node repeats step 2 until all nodes are added to the tree.
We need to convince ourselves that the above three steps finally create the least-cost tree.
Table shows a simplified version of Dijkstra’s algorithm.
Lines 4 to 13 implement step 1 in the algorithm. Lines 16 to 23 implement step 2 in the
algorithm. Step 2 is repeated until all nodes are added to the tree.
Figure shows the formation of the least-cost tree for the graph in Figure using Dijkstra’s
algorithm. We need to go through an initialization step and six iterations to find the least-
cost tree.

Path-Vector Routing
Both link-state and distance-vector routing are based on the least-cost goal. However, there
are instances where this goal is not the priority. For example, assume that there are some
routers in the internet that a sender wants to prevent its packets from going through. For
example, a router may belong to an organization that does not provide enough secu- rity or
it may belong to a commercial rival of the sender which might inspect the packets for
obtaining information. Least-cost routing does not prevent a packet from passing through
an area when that area is in the least-cost path. In other words, the least-cost goal, applied by
LS or DV routing, does not allow a sender to apply specific policies to the route a packet
may take. Aside from safety and security, there are occasions, as discussed in the next
section, in which the goal of routing is merely reachability: to allow the packet to reach its
destination more efficiently without assigning costs to the route.
To respond to these demands, a third routing algorithm, called path-vector (PV) routing has
been devised. Path-vector routing does not have the drawbacks of LS or DV routing as
described above because it is not based on least-cost routing. The best route is determined by
the source using the policy it imposes on the route. In other words, the source can control the
path. Although path-vector routing is not actually used in an internet, and is mostly designed
to route a packet between ISPs, we discuss the principle of this method in this section as
though applied to an internet. In the next section, we show how it is used in the Internet.
Spanning Trees
In path-vector routing, the path from a source to all destinations is also determined by the
best spanning tree. The best spanning tree, however, is not the least-cost tree; it is the tree
determined by the source when it imposes its own policy. If there is more than one route
to a destination, the source can choose the route that meets its policy best. A source may
apply several policies at the same time. One of the common policies uses the minimum
number of nodes to be visited (something similar to least-cost). Another common policy
is to avoid some nodes as the middle node in a route. Figure shows a small internet with
only five nodes. Each source has created its own spanning tree that meets its policy. The
policy imposed by all sources is to use the minimum number of nodes to reach a
destination. The spanning tree selected by A and E is such that the communication does
not pass through D as a middle node. Similarly, the spanning tree selected by B is such
that the communication does not pass through C as a middle node.

Creation of a spanning tree

Path-vector routing, like distance-vector routing, is an asynchronous and distributed routing

algorithm. The spanning trees are made, gradually and asynchronously, by each node. When a
node is booted, it creates a path vector based on the information it can obtain about its
immediate neighbour. A node sends greeting messages to its immediate neighbours to collect
these pieces of information. Figure shows all of these path vectors for our internet in Figure
Note, however, that we do not mean that all of these tables are created simultaneously; they
are created when each node is booted. The figure also shows how these path vectors are sent
to immediate neighbours after they have been created (arrows)

Each node, after the creation of the initial path vector, sends it to all its immediate
neighbors. Each node, when it receives a path vector from a neighbor, updates its path
vector using an equation similar to the Bellman-Ford, but applying its own policy instead
of looking for the least cost. We can define this equation as
Path(x, y) = best {Path(x, y), [(x + Path(v, y)]} for all v’s in the internet.

In this equation, the operator (+) means to add x to the beginning of the path. We also need
to be cautious to avoid adding a node to an empty path because an empty path means one
that does not exist.
The policy is defined by selecting the best of multiple paths. Path-vector routing also imposes
one more condition on this equation: If Path (v, y) includes x, that path is discarded to avoid
a loop in the path. In other words, x does not want to visit itself when it selects a path to y.
Figure shows the path vector of node C after two events. In the first event, node C receives a
copy of B’s vector, which improves its vector: now it knows how to reach node A. In the
second event, node C receives a copy of D’s vector, which does not change its vector. As a
matter of fact the vector for node C after the first event is stabilized and serves as its
forwarding table.

Path-Vector Algorithm
Based on the initialization process and the equation used in updating each forwarding table
after receiving path vectors from neighbours, we can write a simplified version of the path
vector algorithm as shown in Table
Lines 4 to 12 show the initialization for the node. Lines 17 to 24 show how the node
updates its vector after receiving a vector from the neighbor. The update process is
repeated forever. We can see the similarities between this algorithm and the DV algorithm.
UNICAST ROUTING PROTOCOLS
In the previous section, we discussed unicast routing algorithms; in this section, we dis- cuss
unicast routing protocols used in the Internet. Although three protocols we discuss here are
based on the corresponding algorithms we discussed before, a protocol is more than an
algorithm. A protocol needs to define its domain of operation, the messages exchanged,
communication between routers, and interaction with protocols in other domains. After an
introduction, we discuss three common protocols used in the Internet: Routing Information
Protocol (RIP), based on the distance-vector algorithm, Open Shortest Path First (OSPF),
based on the link-state algorithm, and Border Gateway Protocol (BGP), based on the path-
vector algorithm.

Internet Structure
Before discussing unicast routing protocols, we need to understand the structure of today’s
Internet. The Internet has changed from a tree-like structure, with a single back- bone, to a multi-
backbone structure run by different private corporations today. Although it is difficult to give
a general view of the Internet today, we can say that the Internet has a structure similar

There are several backbones run by private communication companies that provide global
connectivity. These backbones are connected by some peering points that allow connectivity
between backbones. At a lower level, there are some provider networks that use the backbones
for global connectivity but provide services to Internet customers. Finally, there are some
customer networks that use the services provided by the provider networks. Any of these three
entities (backbone, provider network, or customer network) can be called an Internet Service
Provider or ISP. They provide services, but at different levels.
Hierarchical Routing
The Internet today is made of a huge number of networks and routers that connect them.
It is obvious that routing in the Internet cannot be done using a single protocol for two
reasons: a scalability problem and an administrative issue. Scalability problem means that
the size of the forwarding tables becomes huge, searching for a destination in a forwarding
table becomes time-consuming, and updating creates a huge amount of traffic. The
administrative issue is related to the Internet structure described in Figure . As the figure
shows, each ISP is run by an administrative authority. The administrator needs to have
control in its system. The organization must be able to use as many subnets and routers as it
needs, may desire that the routers be from a particular manufacturer, may wish to run a
specific routing algorithm to meet the needs of the organization, and may want to impose
some policy on the traffic passing through its ISP.
Hierarchical routing means considering each ISP as an autonomous system (AS).
Each AS can run a routing protocol that meets its needs, but the global Internet runs a
global protocol to glue all ASs together. The routing protocol run in each AS is referred to
as intra-AS routing protocol, intradomain routing protocol, or interior gateway protocol
(IGP); the global routing protocol is referred to as inter-AS routing protocol, interdomain
routing protocol, or exterior gateway protocol (EGP). We can have several intradomain
routing protocols, and each AS is free to choose one, but it should be clear that we should
have only one interdomain protocol that handles routing between these entities. Presently,
the two common intradomain routing protocols are RIP and OSPF; the only interdomain
routing protocol is BGP. The situation may change when we move to IPv6.
Autonomous Systems
As we said before, each ISP is an autonomous system when it comes to managing net-
works and routers under its control. Although we may have small, medium-size, and large
ASs, each AS is given an autonomous number (ASN) by the ICANN. Each ASN is a 16-
bit unsigned integer that uniquely defines an AS. The autonomous systems, however, are
not categorized according to their size; they are categorized according to the way they are
connected to other ASs. We have stub ASs, multihomed ASs, and transient ASs. The type,
as we see will later, affects the operation of the interdomain routing protocol in relation to
that AS.
Stub AS. A stub AS has only one connection to another AS. The data traffic can be either
initiated or terminated in a stub AS; the data cannot pass through it. A good example of a
stub AS is the customer network, which is either the source or the sink of data.
Multihomed AS. A multihomed AS can have more than one connection to other ASs, but
it does not allow data traffic to pass through it. A good example of such an AS is some of
the customer ASs that may use the services of more than one provider network, but their
policy does not allow data to be passed through them.
Transient AS. A transient AS is connected to more than one other AS and also allows the
traffic to pass through. The provider networks and the backbone are good examples of
transient ASs.

Routing Information Protocol (RIP)

The Routing Information Protocol (RIP) is one of the most widely used intradomain routing
protocols based on the distance-vector routing algorithm we described earlier. RIP was started
as part of the Xerox Network System (XNS), but it was the Berkeley Software Distribution
(BSD) version of UNIX that helped make the use of RIP widespread.
Hop Count
A router in this protocol basically implements the distance-vector routing algorithm shown in
Table. However, the algorithm has been modified as described below. First, since a router in
an AS needs to know how to forward a packet to different net- works (subnets) in an AS, RIP
routers advertise the cost of reaching different networks instead of reaching other nodes in a
theoretical graph. In other words, the cost is defined between a router and the network in
which the destination host is located. Second, to make the implementation of the cost simpler
(independent from performance factors of the routers and links, such as delay, bandwidth,
and so on), the cost is defined as the number of hops, which means the number of networks
(sub- nets) a packet needs to travel through from the source router to the final destination host.
Note that the network in which the source host is connected is not counted in this calculation
because the source host does not use a forwarding table; the packet is delivered to the default
router. Figure shows the concept of hop count advertised by three routers from a source host
to a destination host. In RIP, the maximum cost of a path can be 15, which means 16 is
considered as infinity (no connection). For this reason, RIP can be used only in autonomous
systems in which the diameter of the AS is not more than 15 hops.

Forwarding Tables
Although the distance-vector algorithm we discussed in the previous section is concerned
with exchanging distance vectors between neighboring nodes, the routers in an
autonomous system need to keep forwarding tables to forward packets to their destination
networks. A forwarding table in RIP is a three-column table in which the first column is
the address of the destination network, the second column is the address of the next router
to which the packet should be forwarded, and the third column is the cost (the number of
hops) to reach the destination network. Figure shows the three forwarding tables for the
routers in Figure. Note that the first and the third columns together convey the same
information as does a distance vector, but the cost shows the number of hops to the
destination networks.
Although a forwarding table in RIP defines only the next router in the second column, it
gives the information about the whole least-cost tree based on the second property of these
trees, discussed in the previous section. For example, R1 defines that the next router for
the path to N4 is R2; R2 defines that the next router to N4 is R3; R3 defines that there is
no next router for this path. The tree is then R1 → R2 → R3 → N4.
A question often asked about the forwarding table is what the use of the third column is.
The third column is not needed for forwarding the packet, but it is needed for updating the
forwarding table when there is a change in the route, as we will see shortly.
RIP Implementation
RIP is implemented as a process that uses the service of UDP on the well-known port
number 520. In BSD, RIP is a daemon process (a process running in the background),
named routed (abbreviation for route daemon and pronounced route-dee). This means that,
although RIP is a routing protocol to help IP route its datagrams through the AS, the RIP
messages are encapsulated inside UDP user datagrams, which in turn are encapsulated
inside IP datagrams. In other words, RIP runs at the application layer, but creates
forwarding tables for IP at the network later.
RIP has gone through two versions: RIP-1 and RIP-2. The second version is backward
compatible with the first section; it allows the use of more information in the RIP messages
that were set to 0 in the first version. We discuss only RIP-2 in this section.
RIP Messages
Two RIP processes, a client and a server, like any other processes, need to exchange
messages. RIP-2 defines the format of the message, as shown in Figure Part of the message,
which we call entry, can be repeated as needed in a message. Each entry carries the
information related to one line in the forwarding table of the router that sends the message.
RIP has two types of messages: request and response. A request message is sent by a router that
has just come up or by a router that has some time-out entries. A request message can ask
about specific entries or all entries. A response (or update) message can be either solicited or
unsolicited. A solicited response message is sent only in answer to a request message. It
contains information about the destination specified in the corresponding request message.
An unsolicited response message, on the other hand, is sent periodically, every 30 seconds or
when there is a change in the forwarding table.
RIP Algorithm
RIP implements the same algorithm as the distance-vector routing algorithm we dis- cussed in
the previous section. However, some changes need to be made to the algorithm to enable a
router to update its forwarding table:
❑ Instead of sending only distance vectors, a router needs to send the whole contents of its
forwarding table in a response message.
❑ The receiver adds one hop to each cost and changes the next router field to the address of the
sending router. We call each route in the modified forwarding table the received route and
each route in the old forwarding table the old route. The received router selects the old routes
as the new ones except in the following three cases:
1. If the received route does not exist in the old forwarding table, it should be added to the route.
2. If the cost of the received route is lower than the cost of the old one, the received route should
be selected as the new one.
3. If the cost of the received route is higher than the cost of the old one, but the value of the
next router is the same in both routes, the received route should be selected as the new one.
This is the case where the route was actually advertised
by the same router in the past, but now the situation has been changed. For example, suppose
a neighbor has previously advertised a route to a destination with cost 3, but now there is
no path between this neighbor and that destination. The neighbor advertises this
destination with cost value infinity (16 in RIP). The receiving router must not ignore this
value even though its old route has a lower cost to the same destination.
❑ The new forwarding table needs to be sorted according to the destination route (mostly
using the longest prefix first).
Example
Figure shows a more realistic example of the operation of RIP in an autonomous system.
First, the figure shows all forwarding tables after all routers have been booted. Then we
show changes in some tables when some update messages have been exchanged. Finally,
we show the stabilized forwarding tables when there is no more change.
Timers in RIP
RIP uses three timers to support its operation. The periodic timer controls the advertising
of regular update messages. Each router has one periodic timer that is randomly set to a
number between 25 and 35 seconds (to prevent all routers sending their messages at the
same time and creating excess traffic). The timer counts down; when zero is reached, the
update message is sent, and the timer is randomly set once again. The expiration timer
governs the validity of a route. When a router receives update information for a route, the
expiration timer is set to 180 seconds for that particular route. Every time a new update for
the route is received, the timer is reset. If there is a problem on an internet and no update is
 received within the allotted 180 seconds, the route is considered expired and the hop count
of the route is set to 16, which means the destination is unreachable. Every route has its
own expiration timer. The garbage collection timer is used to purge a route from the
forwarding table. When the information about a route becomes invalid, the router does not
immediately purge that route from its table. Instead, it continues to advertise the route with
a metric value of 16. At the same time, a garbage collection timer is set to 120 seconds for
that route. When the count reaches zero, the route is purged from purging the table. This
timer allows neighbors to become aware of the invalidity of a route prior to.
Performance
Before ending this section, let us briefly discuss the performance of RIP:
❑ Update Messages. The update messages in RIP have a very simple format and are sent
only to neighbors; they are local. They do not normally create traffic because the routers
try to avoid sending them at the same time.
❑ Convergence of Forwarding Tables. RIP uses the distance-vector algorithm, which can
converge slowly if the domain is large, but, since RIP allows only 15 hops in a domain (16
is considered as infinity), there is normally no problem in convergence. The only problems
that may slow down convergence are count-to-infinity and loops created in the domain;
use of poison-reverse and split-horizon strategies added to the RIP extension may alleviate
the situation.
Open Shortest Path First (OSPF)
Open Shortest Path First (OSPF) is also an intradomain routing protocol like RIP, but it
is based on the link-state routing protocol we described earlier in the chapter. OSPF is an
open protocol, which means that the specification is a public document.
Metric
In OSPF, like RIP, the cost of reaching a destination from the host is calculated from the
source router to the destination network. However, each link (network) can be assigned a
weight based on the throughput, round-trip time, reliability, and so on. An administration
can also decide to use the hop count as the cost. An interesting point about the cost in OSPF
is that different service types (TOSs) can have different weights as the cost. Figure shows
the idea of the cost from a router to the destination host network. We can compare the
figure with Figure for the RIP.
Forwarding Tables
Each OSPF router can create a forwarding table after finding the shortest-path tree between
itself and the destination using Dijkstra’s algorithm, described earlier in the chapter. Figure
shows the forwarding tables for the simple AS in Figure . Comparing the forwarding tables
for the OSPF and RIP in the same AS, we find that the only difference is the cost values.
In other words, if we use the hop count for OSPF, the tables will be exactly the same. The
reason for this consistency is that both proto- cols use the shortest-path trees to define the
best route from a source to a destination.
Areas
Compared with RIP, which is normally used in small ASs, OSPF was designed to be able
to handle routing in a small or large autonomous system. However, the formation of
shortest-path trees in OSPF requires that all routers flood the whole AS with their LSPs to
create the global LSDB. Although this may not create a problem in a small AS, it may have
created a huge volume of traffic in a large AS. To prevent this, the AS needs to be divided
into small sections called areas. Each area acts as a small independent domain for flooding
LSPs. In other words, OSPF uses another level of hierarchy in routing: the first level is the
autonomous system, the second is the area.

However, each router in an area needs to know the information about the link states not only
in its area but also in other areas. For this reason, one of the areas in the AS is designated as
the backbone area, responsible for gluing the areas together. The routers in the backbone area
are responsible for passing the information collected by each area to all other areas. In this
 way, a router in an area can receive all LSPs generated in other areas. For the purpose of
communication, each area has an area identification. The area identification of the backbone
is zero. Figure shows an autonomous system and its areas.

OSPF Messages
OSPF is a very complex protocol; it uses five different types of messages. In Figure we
first show the format of the OSPF common header (which is used in all messages) and the
link-state general header (which is used in some messages). We then give the outlines of five
message types used in OSPF. The hello message (type 1) is used by a router to introduce itself
to the neighbors and announce all neighbors that it already knows. The database description
message (type 2) is normally sent in response to the hello message to allow a newly joined
router to acquire the full LSDB. The link- state request message (type 3) is sent by a router
that needs information about a specific LS. The link-state update message (type 4) is the main
OSPF message used for building the LSDB. This message, in fact, has five different versions
(router link, network link, summary link to network, summary link to AS border router, and
external link), as we discussed before. The link-state acknowledgment message (type 5) is
used to create reliability in OSPF; each router that receives a link-state update message needs
to acknowledge it.
Authentication
As Figure shows, the OSPF common header has the provision for authentication of the
message sender. As we will discuss in Chapters 31 and 32, this prevents a malicious entity
from sending OSPF messages to a router and causing the router to become part of the routing
system to which it actually does not belong.
OSPF Algorithm
OSPF implements the link-state routing algorithm we discussed in the previous section.
However, some changes and augmentations need to be added to the algorithm:
❑ After each router has created the shortest-path tree, the algorithm needs to use it to create the
corresponding routing algorithm.
❑ The algorithm needs to be augmented to handle sending and receiving all five types of
messages.
Performance
Before ending this section, let us briefly discuss the performance of OSPF:
❑ Update Messages. The link-state messages in OSPF have a somewhat complex format.
They also are flooded to the whole area. If the area is large, these messages may create
heavy traffic and use a lot of bandwidth.
❑ Convergence of Forwarding Tables. When the flooding of LSPs is completed, each router
can create its own shortest-path tree and forwarding table; convergence is fairly quick.
However, each router needs to run Dijkstra’s algorithm, which may take some time.
❑ Robustness. The OSPF protocol is more robust than RIP because, after receiving the
completed LSDB, each router is independent and does not depend on other routers in the area.
Corruption or failure in one router does not affect other routers as seriously as in RIP.
Border Gateway Protocol Version 4 (BGP4)
The Border Gateway Protocol version 4 (BGP4) is the only interdomain routing protocol
used in the Internet today. BGP4 is based on the path-vector algorithm we described before,
but it is tailored to provide information about the reachability of net- works in the Internet.
Introduction
BGP, and in particular BGP4, is a complex protocol. In this section, we introduce the basics
of BGP and its relationship with intradomain routing protocols (RIP or OSPF). Figure shows
an example of an internet with four autonomous systems. AS2, AS3, and AS4 are stub
autonomous systems; AS1 is a transient one. In our example, data exchange between AS2,
AS3, and AS4 should pass through AS1.

Each autonomous system in this figure uses one of the two common intradomain protocols,
RIP or OSPF. Each router in each AS knows how to reach a network that is in its own AS,
but it does not know how to reach a network in another AS.

To enable each router to route a packet to any network in the internet, we first install a
variation of BGP4, called external BGP (eBGP), on each border router (the one at the edge
of each AS which is connected to a router at another AS). We then install the second variation
of BGP, called internal BGP (iBGP), on all routers. This means that the border routers will
be running three routing protocols (intradomain, eBGP, and iBGP), but other routers are
running two protocols (intradomain and iBGP). We discuss the effect of each BGP variation
separately.

Operation of External BGP (eBGP)

We can say that BGP is a kind of point-to-point protocol. When the software is installed on
two routers, they try to create a TCP connection using the well-known port 179. In other
words, a pair of client and server processes continuously communicate with each other to
exchange messages. The two routers that run the BGP processes are called BGP peers or
BGP speakers. We discuss different types of messages exchanged between two peers, but
 for the moment we are interested in only the update messages (discussed later) that
announce reachability of networks in each AS.
The eBGP variation of BGP allows two physically connected border routers in two different
ASs to form pairs of eBGP speakers and exchange messages. The routers that are eligible in
our example in Figure form three pairs: R1-R5, R2-R6, and R4- R9. The connection between
these pairs is established over three physical WANs (N5, N6, and N7). However, there is a
need for a logical TCP connection to be created over the physical connection to make the
exchange of information possible. Each logical connection in BGP parlance is referred to as
a session. This means that we need three sessions in our example, as shown in Figure

The figure also shows the simplified update messages sent by routers involved in the eBGP
sessions. The circled number defines the sending router in each case. For example,
message number 1 is sent by router R1 and tells router R5 that N1, N2, N3, and N4 can
be reached through router R1 (R1 gets this information from the corresponding
intradomain forwarding table). Router R5 can now add these pieces of information at
the end of its forwarding table. When R5 receives any packet destined for these four
networks, it can use its forwarding table and find that the next router is R1. The reader may
have noticed that the messages exchanged during three eBGP sessions help some routers
know how to route packets to some networks in the internet, but the reachability information
is not complete. There are two problems that need to be addressed:
1).Some border routers do not know how to route a packet destined for non neighbour ASs.
For example, R5 does not know how to route packets destined for networks in AS3 and AS4.
Routers R6 and R9 are in the same situation as R5: R6 does not know about networks in AS2
and AS4; R9 does not know about networks in AS2 and AS3.
2).None of the non border routers know how to route a packet destined for any net- works in
other ASs.
To address the above two problems, we need to allow all pairs of routers (border or non border)
to run the second variation of the BGP protocol, iBGP.
Operation of Internal BGP (iBGP)
The iBGP protocol is similar to the eBGP protocol in that it uses the service of TCP on the
well-known port 179, but it creates a session between any possible pair of routers inside an
autonomous system. However, some points should be made clear. First, if an AS has only one
router, there cannot be an iBGP session. For example, we cannot create an iBGP session inside
AS2 or AS4 in our internet. Second, if there are n routers in an autonomous system, there should
be [n  (n - 1) / 2] iBGP sessions in that autonomous system (a fully connected mesh) to prevent
loops in the system. In other words, each router needs to advertise its own reachability to the
peer in the session instead of flooding what it receives from another peer in another session.
Figure 20.26 shows the combination of eBGP and iBGP sessions in our internet.

Note that we have not shown the physical networks inside ASs because a session is
made on an overlay network (TCP connection), possibly spanning more than one
physical network as determined by the route dictated by intradomain routing
protocol. Also note that in this stage only four messages are exchanged. The first
message (numbered 1) is sent by R1 announcing that networks N8 and N9 are
reachable through the path AS1-AS2, but the next router is R1. This message is sent,
through separate sessions, to R2, R3, and R4. Routers R2, R4, and R6 do the same
thing but send different messages to different destinations. The interesting point is
that, at this stage, R3, R7, and R8 create sessions with their peers, but they actually
have no message to send.
The updating process does not stop here. For example, after R1 receives the
update message from R2, it combines the reachability information about AS3 with
the reach- ability information it already knows about AS1 and sends a new update
message to R5. Now R5 knows how to reach networks in AS1 and AS3. The process
continues when R1 receives the update message from R4. The point is that we need
to make certain that at a point in time there are no changes in the previous updates
and that all information is propagated through all ASs. At this time, each router
combines the information received from eBGP and iBGP and creates what we may
call a path table after applying the criteria for finding the best path, including routing
policies that we discuss later. To demonstrate, we show the path tables in Figure for
the routers in Figure . For example, router R1 now knows that any packet destined
for networks N8 or N9 should go through AS1 and AS2 and the next router to deliver
the packet to is router R5. Similarly, router R4 knows that any packet destined for
networks N10, N11, or N12 should go through AS1 and AS3 and the next router to
deliver this packet to is router R1, and so on.