Unit –III NETWORK LAYER

Concept of Routing
in Network Layer,
IPV6 Addressing

1
Network Layer II (routing)
Routing Styles:
 Static vs. Dynamic Routing
Routing Protocols/Algorithms
 Routing Table
 Routing Information Protocol (RIP) & Distance Vector Routing
(DVR)
 Open Shortest Path First (OSPF) & Link State Routing (LSR)
 Dijkstra’s “Shortest Path” Algorithm
 Border Gateway Protocol (BGP) and Path Vector Routing (PVR)

2
3
Routing Protocol & Routing Algorithm
 A Routing Protocol is a combination of rules and
procedures that lets routers in an internet inform
each other of changes. It allows routers to share
whatever they know about the internet or their
neighbourhood.

 A Routing Algorithm is that part of network layer

software responsible fro deciding which output
line and incoming packet should be transmitted
on.
4
5
6
Routing
a) Routing requires a host or a router to have a routing table.
b) Usually when a host has a packet to send or when a router has
received a packet to be forwarded, it looks at this table to find the
route to the final destination.
c) However, this simple solution is impossible in today’s Internet
world because the number of entries in the routing table makes the
table lookups inefficient.
d) Need to make the size of table manageable and handles issues such
security at the same time. The key question is how to design the
routing table.
e) Next-hop routing, Network-specific routing, host specific routing
f) Static versus Dynamic Routing
g) Routing Protocols: RIP, OSPF, BGP
h) Routing Algorithms: DVR, LSR, PVR
7
Next-hop routing

Next-hop routing holds only the information that leads to the

next hop instead of complete route. 8
9
Network-specific & host-specific routing

The destination host address Instead of having an entry for every host
is given in the routing table; connected to the same network, only one entry
to have greater control over is needed to defined the address of the network
routing. itself. All host connected to the same network
as one single entity. 10
11
12
Default routing

R1 is used to route packets to hosts

connected to N2.

However, R2 is used to as default to

route other packets to the rest of
Internet without listing all the
networks involved
Only one default routing is allowed
with network address 0.0.0.0
13
Routing table
a) Generally, a routing table needs a minimum of 4
columns: mask, destination network address, next hop
address and interface.
b) When a packet arrives, the router applies the mask to the
destination address it receives (one-by-one until a match
is found) in order to find the corresponding destination
network address.
c) So, the mask serves as essential tool to match destination
address in routing table and the address it receives.
d) If found, the packet is sent out from the corresponding
interface in the table. If not found, the packet is delivered
to the default interface which carries the packet to
default router.
14
15
Note

In classless addressing, we need at

least four columns in a routing table.

16
Make a routing table for router R1, using the
Example 7a configuration in Figure below

m3

Solution Routing table for router R1 in Figure above

The table is sorted from the longest mask to the shortest mask. 17
Example 7b Show the forwarding process if a packet arrives at
R1 with the destination address 180.70.65.140.

Solution
The router performs the following steps:
1. The first mask (/26) is applied to the destination address.
The result is 180.70.65.128, which does not match the
corresponding network address.
2. The second mask (/25) is applied to the destination
address. The result is 180.70.65.128, which matches the
corresponding network address. The next-hop address
and the interface number m0 are passed on for
further processing. 18
Show the forwarding process if a packet arrives at
Example 7c R1 with the destination address 201.4.22.35.

Solution

The router performs the following steps:

1. The first mask (/26) is applied to the destination address. The
result is 201.4.22.0, which does not match the corresponding
network address.
2. The second mask (/25) is applied to the destination address. The
result is 201.4.22.0, which does not match the corresponding
network address (row 2).
3. The third mask (/24) is applied to the destination address. The
result is 201.4.22.0, which matches the corresponding network
address.. 19
20
21
22
Unicast Routing
a) Unicast = one source and one destination. (1-to-1 relationship).
b) In Unicast routing, when a router receives a packet, it forwards the
packet thru only one of its ports as defined in the routing table. The
router may discard the packet if it cannot find the destination
address
c) Questions: In dynamic routing, how does the router decides to
which network should it pass the packet next? What routing
algorithm is the routing based on? The decision is based on
optimisation: which of the available pathways is the best/optimum
path?
d) But how to measure? A metric is a cost assigned for passing thru a
network and the total metric of a particular route is equal to the sum
of the metrics of networks that comprise the route.
e) Simple protocols such as Routing Information Protocol (RIP), treat
all network equally; cost of passing each network is the same as one
hop count per network. 23
24
Routing Protocol:
Interior Vs Exterior

25
Static versus Dynamic Routing

A static routing table

contains information entered manually
Usually remained unchanged.

A dynamic routing table is updated

periodically or whenever necessarily
using one of the dynamic routing protocols
such as RIP, OSPF, or BGP.
26
27
Interior Routing Protocol 1:
Routing Information Protocol
(RIP)

28
29
30
31
32
33
34
35
36
37
38
39
40
Routing Information Protocol (RIP)
a) RIP is based on distance vector routing, which uses the Bellman-
Ford algorithm for calculating the routing table.
b) RIP treats all network equals; the cost of passing thru a network
is the same: one hop count per network.
c) Each router/node maintains a vector (table) of minimum
distances to every node. (the least-cost route btw any nodes is the
route with the minimum number of hop-count).
d) The hop-count is the number of networks that a packet
encounters to reach its destination. Path costs are based on
number of hops.
e) In distance vector routing, each router periodically shares its
knowledge about the entire internet with its neighbour.
f) Each router keeps a routing table that has one entry for each
destination network of which the router is aware.
g) The entry consists of Destination Network Address/id, Hop- 41
Count and Next-Router.
42
43
44
Distance Vector Routing (DVR)
a) 3 keys to understand how this algorithm works:
• Sharing knowledge about the entire AS. Each router
shares its knowledge about the entire AS with
neighbours. It sends whatever it has.
• Sharing only with immediate neighbours. Each
router sends whatever knowledge it has thru all its
interface.
• Sharing at regular intervals. sends at fixed intervals,
e.g. every 30 sec.

b) Problems: Tedious comparing/updating process, slow

response to infinite loop problem, huge list to be
maintained!!
45
Initialization of tables in distance vector routing (DVR)

46
Updating in distance vector routing example: C to A

From C From A

A to A via C: ACA = AC+ CA = 2+2

A to B via C: ACB = AC + CB = 2+4

A to D via C: ACD = AC + CD = 2+ inf.

A to E via C: ACD = AC + CE = 2+4

A to C via C: ACB = AC + CC = 2+0

47
Final Distance vector routing tables

48
Example of Initial routing tables (RIP)
in a small autonomous system

49
Example of Final routing tables

50
Example of a domain using RIP

51
Link State Routing (LSR)
a) Like RIP, in link state routing, each router also shares its knowledge
about its neighbourhood with every routers in the area.
b) However, in LSR, the link-state packet (LSP) defines the best known
network topology (of an area) is sent to every routers (of other area)
after it is constructed locally. Whereas RIP slowly converge to final
routing list based information received from immediate neighbours.
c) 3 keys to understand how this algorithm works:
• Sharing knowledge about the neighbourhood. Each router sends the state of
its neighbourhood to every other router in the area.
• Sharing with every other routers. Thru process of flooding. each router sends
the state of its neighbourhood thr all its output ports and each neighbour sends
to every other neighbours and so on until all routers received same full
information eventually.
• Sharing when there is a change. Each router share its state of its neighbour
only when there is a change; contrasting DVR results in lower traffic.
d) From the received LSPs and knowledge of entire topology, a router
can then calculate the shortest path between itself and each network.52
53
54
55
56
57
58
59
60
61
62
63
64
Open Shortest Path First (OSPF)
a) OSPF uses link state routing to update the routing table in an area;
OSPF divides an AS into different areas (depending on their
type).
b) Unlike RIP, OSPF treats the entire network within differently with
different philosophy; depending on the types, cost (metric) and
condition of each link: to define the ‘state’ of a link.
c) OSPF allows the administrator to (only) assign a cost for passing
through a network based on the type of service required. e.g.
minimum delay, maximum throughput. (but not stating exact path)
d) Each router should have the exact topology of the AS network(a
picture of entire AS network) at every moment. The topology is a
graph consisting of nodes and edges.
e) Each router needs to advertise to the neighbourhood of every
other routers involved in an Area. (flood)
65
Link State Advertisement (LSA)
To share information about the neighbourhood, each entity
distribute link state advertisements (LSAs).

5 Types of LSAs

Info exchange Info exchange Info exchange

Info. exchange within between different outside across to external
inside an Area Areas inside an AS different AS internet 66
Router link

A router link advertisement defines the links of a true router.

A true router uses this advertisement to announce information about all
its links and what is at the other side of the link (neighbour).
67
Network link

A network link advertisement defines the links of a network.

A designated router on behalf of the transient network distributes this
types of LSA packet. The packet announces the existence of all the
routers connected to the network.
68
Summary link to network

area border area border

router R1 router R2

Backbone network

Router and network link advertisements flood each area with info about the router
links and network links within/inside an area. But a router must also know about the
networks outside its area, and the area border routers can provide this information.
An area border router is active in more than one area. It receives router link and
network link advertisements and creates a routing table for each area.
69
Summary link to AS boundary router

The previous advertisement lets every router know the cost to reach all networks
within/inside an AS. But what about the network outside the AS? If a router inside an
area wants to send a packet outside the autonomous system, it should first know the
route to an AS boundary router; the summary link to AS boundary router provides
this information. The border routers can then flood their areas with this information.
70
External link

Although the previous advertisement lets each router know the route to different AS
boundary router, this information is not enough. A router inside an AS also wants to
know which networks are available outside the AS; i.e. the external internet.
The external link advertisement provide this information. The AS boundary router
floods the AS with cost of each network outside the AS, using a routing table created
by an exterior routing table protocol. Each advertisement announces one single 71
network. If there is more than one network. Separate announcements are made.
Example In the figure below, which router(s) sends out
router link LSAs? and which router(s) sends out
network link LSAs?

Solution

All routers advertise router link LSAs.

R1 has two links, Net1 and Net2.
R2 has one link, Net2 in this AS.
R3 has two links, Net2 and Net3. 72
Solution Continue

All three network must advertise network link LSAs:

Advertisement for Net1 is done by R1 because it is the only router
and therefore the designated router.
Advertisement for Net2 can be done by either R1, R2, or R3,
depending on which one is chosen as the designated router.
Advertisement for Net3 is done by R3 because it is the only router
and therefore the designated router.

73
In OSPF, all routers have
the same Link State database.
• Every router in an area receives the router link and network link
LSAs and form a link state database.
• Every router in the same area has the same link state database.
• A link state database is a tabular representation of the topology of
the internet inside an area. It shows the relationship between each
router and its neighbors including the metrics used.
• To calculate its next-route in the routing table, each router applies
the Dijkstra algorithm to its state database, to find the shortest path
between 2 points on a network, using a graph (nodes and edges).
• The algorithm divides the nodes into two sets: tentative and
permanent. It chooses nodes, makes them tentative, examines them,
74
and if they pass the criteria, makes permanent.
Shortest Path Search
Dijkstra’s Algorithm
1. Start with the local node (router): the root of the tree.
2. Assign a cost of 0 to this node and make it the first permanent node.
3. Examine each neighbour node of the node that was the last
permanent node.
4. Assign a cumulative cost to each node and make it tentative.
5. Among the list of tentative nodes
a. Find the node with the smallest cumulative cost and make it permanent.
b. If a node can be reached from more than one direction
i. Select the direction with the shortest cumulative cost.
6. Repeat steps 3 to 5 until every node becomes permanent.

75
Dijkstra algorithm

76
Example of formation of shortest path tree

77
Link State Routing (LSR)
Idea Behind LSR: Each router must do the following:
1. Discover its neighbors, learn their network address. ( Send HELLO
packet)
2. Measure the delay or cost to each of its neighbors. (Send ECHO packet)
3. Building Link State packet telling all it has just learned. (ACK flag)
4. Distribute/Send this packet to all other routers (Flooding – SEND flag).
5. Compute the shortest path to every other router. (Dijkstra’s algorithm)
In effect the complete topology and all the delays are experimentally
measured and distributed to every router, then Dijkstra’s algorithm can
be run to find the shortest path to every other router.

HELLO packet can be acknowledged by a reply to signal its present.

ECHO packet requires instant response to know the round-trip-time.

78
OSPF Packets

• Based on Link State Routing

• OSPF messages are transported directly
in IP packets
• OSPF standard supports novel concepts
such as type of service routing, load
balancing and authentication

79
Exterior Routing Protocol:
Border Gateway Protocol
(BGP)

80
BGP & Path Vector Routing (PVR)
a) Border Gateway Protocol (BGP) is an inter-domain or inter-
autonomous system routing protocol: routing between different ASs.
b) BGP uses path vector routing to update the routing table in an area.
c) DVR and LSR are not suitable candidates for inter-AS routing :
• DVR: there are occasions in which the route with the smallest hop count is not
the preferred route; non-secure path although the shortest route taken.
• LSR: internet is too big for this routing method to require each router to have a
huge link state database. Taking very long time to calculate the routing table.
d) PVR defines the exact paths as an ordered list of ASs that a packet
should travel thru to reach the destination (besides having the
destination network and next router info.) in its routing table.
e) Security and Political issues involved: more desired to avoid
‘unsaved’ paths/routes/ASs than to take a shorter route.
f) The AS boundary router that participate in PVR advertise the routes
of the networks in their own AS to neighbour AS boundary routers.
g) Solve the count-to-infinity problem 81
Path vector packets

• Each AS has its ‘speaker’ router/node that acts on behalves of the AS. Only
speaker router can communicate with other speaker routers.
• R1 send a path vector message advertising its reachability of N1. R2
receives the message, updates its routing table and after adding its AS to the
path and inserting itself as next router, send message to R3. R3 receives the
message, updates its routing table, make changes and sends the message to
82
R4.
Path Vector Routing Policy
a) Policy routing can be easily implemented through path vector routing.
b) When a router receives a message from its neighbour, the speaker
node or AS boundary router can check the path with its approved list
of ASs.
c) If one of the ASs listed in the path is against its policy, the router can
ignore that path entirely and that destination.
d) For any unapproved paths, the router does not update its routing table
with this path, and it does not send the PV message to its neighbours.
e) This means that the routing table in path vector routing are not based
on the smallest hop count (as in distance vector routing) or the
minimum delay metric (as in open shortest path first routing); they are
based on the policy imposed on the router by the administrator.
f) The path was presented as a list of ASs, but is in fact, a list of
attributes. Each attributes gives some information about the path. The
list of attributes helps the receiving router make a better decision
when applying its policy. (Well-known & Optional) 83
Types of BGP messages

a) Open: To create a relationship, a router running BGP opens a

connection with a neighbouring AS and sends an open message. If the
neighbour accepted, it responds with a Keep-alive message to
establish relationship between the two routers.
b) Update: The heart of BGP protocol used by router to withdraw
destination that have been advertised previously, announce a route to
a new destination or do both. (Withdraw several but advertise only
one).
84
c) Notification: sent by a router whenever an error condition is detected
Initial routing tables in path vector routing

Stabilized tables for three autonomous systems

85
19-2 IPv6 ADDRESSES
Despite all short-term solutions, address depletion is
still a long-term problem for the Internet. This and
other problems in the IP protocol itself have been the
motivation for IPv6.

Topics discussed in this section:

Structure
Address Space

19.86
Note

An IPv6 address is 128 bits long.

19.87
Figure 19.14 IPv6 address in binary and hexadecimal colon notation

19.88
Figure 19.15 Abbreviated IPv6 addresses

19.89
Example 19.11
Expand the address 0:15::1:12:1213 to its original.

Solution
We first need to align the left side of the double colon to
the left of the original pattern and the right side of the
double colon to the right of the original pattern to find
how many 0s we need to replace the double colon.

This means that the original address is.

19.90
IPv4 Addressing Concepts and
Their IPv6 Equivalents
IPv4 Address IPv6 Address
Address Length – 32 bits 128 bits

Address Representation - decimal hexadecimal

Internet address classes Not applicable in IPv6

Multicast addresses (224.0.0.0/4) IPv6 multicast addresses (FF00::/8)

Broadcast addresses Not applicable in IPv6

Unspecified address is 0.0.0.0 Unspecified address is ::

Loopback address is 127.0.0.1 Loopback address is ::1

Public IP addresses Global unicast addresses

Private IP addresses (10.0.0.0/8, Site-local addresses (FEC0::/10)

172.16.0.0/12, and 192.168.0.0/16)
Autoconfigured addresses (169.254.0.0/16) Link-local addresses (FE80::/64)
IPv6 Packet Format 91
IPv4 Header Structure

a) basic IPv4 header contains 12 fields.

b) each field of the IPv4 header has a specific use.
c) Shaded field are removed in IPv6.
IPv4 Header - Review
IPv4 Header - Review
a) Version (4 bits)
– Indicates the version of IP and is set to 4.
b) Internet Header Length (4 bits)
– Indicates the number of 4-byte blocks in the IPv4 header.
– Because an IPv4 header is a minimum of 20 bytes in size, the
smallest value of the Internet Header Length (IHL) field is 5.
c) Type of Service (4 bits)
– Indicates the desired service expected by this packet for delivery
through routers across the IPv4 internetwork.

IPv6 Packet Format 94

IPv4 Header - Review
a) Total Length (16 bits)
– Indicates the total length of the IPv4 packet (IPv4 header + IPv4 payload) and does not
include link layer framing.
b) Identification (16 bits)
– Identifies this specific IPv4 packet.
– The Identification field is selected by the originating source of the IPv4 packet. If the IPv4
packet is fragmented, all of the fragments retain the Identification field value so that the
destination node can group the fragments for reassembly.
c) Flags (3 bits)
– Identifies flags for the fragmentation process.
– There are two flags—one to indicate whether the IPv4 packet might be fragmented and
another to indicate whether more fragments follow the current fragment.
d) Fragment Offset (13 bits)
– Indicates the position of the fragment relative to the original IPv4 payload.

IPv6 Packet Format 95

IPv4 Header - Review
a) Time to Live ( 8 bits)
– Indicate the maximum number of links on which an IPv4 packet can travel before being
discarded.
– Originally used as a time count with which an IPv4 router determined the length of time
required (in seconds) to forward the IPv4 packet, decrementing the TTL accordingly. When
the TTL equals 0,an ICMP Time Expired-TTL Expired in Transit message is sent to the
source IPv4 address and the packet is discarded.
b) Protocol (8 bits)
– Identifies the upper layer protocol.
– For example, TCP uses a Protocol of 6, UDP uses a Protocol of 17, and ICMP uses a
Protocol of 1.
– The Protocol field is used to demultiplex an IPv4 packet to the upper layer protocol.

IPv6 Packet Format 96

IPv4 Header - Review
a) Header Checksum (16 Bits)
– Provides a checksum on the IPv4 header only.
– The IPv4 payload is not included in the checksum calculation as the IPv4 payload and
usually contains its own checksum..
b) Source Address ( 32 bits)
– Stores the IPv4 address of the originating host.
c) Destination Address (32 bits)
– Stores the IPv4 address of the destination host.
d) Options (multiple of 32 bits)
– Stores one or more IPv4 options.

IPv6 Packet Format 97

IPv4 vs IPv6 Header

IPv6 Packet Format

IPv6 Header

IPv6 Packet Format 99

IPv6 Header Fields
a) Based on these rules, RFC 2460 defines the following IPv6 header fields:

1. Version (4 bits)
• 4 bits are used to indicate the version of IP and is set to 6

– Traffic Class (8 bits)

• same function as the Type of Service field in the IPv4 header.

1. Flow Label (20 bits)

• identifies a flow and it is intended to enable the router to identify packets
that should be treated in a similar way without the need for deep lookups
within those packets.
• set by the source and should not be changed by routers along the path to
destination.
IPv6 Header Fields
4. Payload Length (16 bits)
– With the header length fixed at 40 bytes, it is enough to indicate the length of
the payload to determine the length of the entire packet.

5. Next Header (8 bits)

– Indicates either the first extension header (if present) or the protocol in the
upper layer PDU (such as TCP, UDP, or ICMPv6).

6. Hop Limit (8 bits)

– In IPv6, the IPv4 TTL was appropriately renamed Hop Limit because it is a
variable that is decremented at each hop, and it does not have a temporal
dimension.

IPv6 Packet Format 101

IPv6 Header Fields
7. Source IPv6 Address (128 bits)
• Stores the IPv6 address of the originating host.
8. Destination IPv6 Address (128 bits)
– Stores the IPv6 address of the current destination host.

IPv6 Packet Format 102

Values of the Next Header Field

IPv6 Packet Format 103