Network Layer

Network Layer: Network layer Services, Packet Switching, IPv4

Address, IPv4 Datagram, IPv6
Datagram, Introduction to Routing Algorithms, Unicast Routing
Protocols: DVR, LSR, PVR,
Unicast Routing protocols: RIP, OSPF, BGP, Multicasting
Routing-MOSPF
Unicast Routing
Major Protocols of Unicast Routing
1. Distance Vector Routing: Distance-Vector routers use a distributed
algorithm to compute their routing tables.

2. Link-State Routing: Link-State routing uses link-state routers to

exchange messages that allow each router to learn the entire network
topology.

3. Path-Vector Routing: It is a routing protocol that maintains the path

that is updated dynamically.
Link State Routing
Link state routing is a technique in which each router shares the knowledge of
its neighborhood with every other router i.e. the internet work. The three keys
to understand the link state routing algorithm.
1. Knowledge about the neighborhood : Instead of sending its routing table,
a router sends the information about its neighborhood only. A router
broadcast its identities and cost of the directly attached links to other routers.

2. Flooding: Each router sends the information to every other router on the
internetwork except its neighbors. This process is known as flooding. Every
router that receives the packet sends the copies to all the neighbors. Finally
each and every router receives a copy of the same information.

3. Information Sharing : A router send the information to every other router

only when the change occurs in the information.
Features of Link State Routing Protocols
• Link State Packet: A small packet that contains routing information.

• Link-State Database: A collection of information gathered from the

link-state packet.

• Shortest Path First Algorithm (Dijkstra algorithm): A calculation

performed on the database results in the shortest path

• Routing Table: A list of known paths and interfaces.

Link State Routing with DB
Path-Vector Routing
• Both Link state and distance vector routing are based on Least Cost
Goal.

• Path vector routing is actually used in Internet is mostly designed to

route the packet between IP’s.

• In path vector routing, source can control the path and can prevent the
packet in passing through certain nodes.
Path-Vector Routing
• A path vector protocol is a computer network routing protocol which
maintains the path information that gets updated dynamically.

• Updates which have looped through the network and returned to the
same node are easily detected and discarded.

• This algorithm is sometimes used in Bellman–Ford routing algorithms

to avoid "Count to Infinity" problems.
UNICAST ROUTING PROTOCOLS
Autonomous Systems
• 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
• Hop Count
Forwarding Tables

RIP is implemented as a process that uses the service of UDP on the

well-known port number 520.
RIP runs at the application layer, but creates forwarding tables for IP
at the network later.
RIP Message
• 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 Implementation
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. 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.
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. It is an internal routing protocol
• It uses Dijkstra’s algorithm. Unlimited Hop count and it uses a metric of Hop count.
• 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.
• Generally, OSPF divides an autonomous system into areas which is a collection of N/w, Hosts and
routers.
• Routers inside the area flood the area with the routing information.
• At the border of an area special routers called Area Broader router summarizes the info. about the
area and send it to another areas.
• All the area inside an “AS” must connected to the backbone -> Primary area.
• OSPF operations: Neighbors are discovered by means of sending the Hello Packet and share the
info.
Cost as Metric
Forwarding tables in OSPF
Areas in an autonomous system
Five different LSPs
OSPF Messages
• OSPF is a very complex protocol; it uses five different types of messages.
• 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 linkstate 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).
• 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.
OSPF Implementation
and Message Format
Border Gateway Protocol Version 4 (BGP4)

BGP4 is based on the

The Border Gateway Protocol path-vector algorithm we
version 4 (BGP4) is the only described before, but it is tailored
interdomain routing protocol used to provide information about the
in the Internet today. reachability of networks in the
Internet.
A sample internet with four
ASs
BGP
Messag
e
Flow diagram for route selection
BGP Message types
• BGP uses four types of messages for communication between the BGP speakers across
the ASs and inside an AS: open, update, keepalive, and notification.
• Open Message. To create a neighborhood relationship, a router running BGP opens a TCP
connection with a neighbor and sends an open message.
• Update Message. The update message is the heart of the BGP protocol. It is used by a
router to withdraw destinations that have been advertised previously, to announce a route
to a new destination, or both.
• Keepalive Message. The BGP peers that are running exchange keepalive messages
regularly (before their hold time expires) to tell each other that they are alive.
• Notification. A notification message is sent by a router whenever an error condition is
detected or a router wants to close the session.
eBGP operation
Operation of Internal BGP (iBGP)
Path Attributes
• In both intradomain routing protocols (RIP or OSPF), a destination is normally associated
with two pieces of information: next hop and cost.
• Interdomain routing is more involved and naturally needs more information about how to
reach the final destination. In BGP these pieces are called path attributes.
• BGP allows a destination to be associated with up to seven path attributes.
• Path attributes are divided into two broad categories: well-known and optional.
• A well-known attribute must be recognized by all routers; an optional attribute need not
be.
• A well-known attribute can be mandatory, which means that it must be present in any
BGP update message.
• The first byte in each attribute defines the four attribute flags.

ORIGIN (type 1). This is a well-known mandatory attribute, which defines the source
of the routing information. This attribute can be defined by one of the three values: 1, 2,
and 3. Value 1 means that the information about the path has been taken from an
intradomain protocol (RIP or OSPF). Value 2 means that the information comes from
BGP. Value 3 means that it comes from an unknown source.
• AS-PATH (type 2). This is a well-known mandatory attribute, which defines the list of autonomous
systems through which the destination can be reached.
• NEXT-HOP (type 3). This is a well-known mandatory attribute, which defines the next router to
which the data packet should be forwarded.
• MULT-EXIT-DISC (type 4). The multiple-exit discriminator is an optional intransitive attribute,
which discriminates among multiple exit paths to a destination. The value of this attribute is
normally defined by the metric in the corresponding intradomain protocol (an attribute value of
4-byte unsigned integer).
• LOCAL-PREF (type 5). The local preference attribute is a well-known discretionary attribute. It is
normally set by the administrator, based on the organization policy.
• AGGREGATOR (type 7). This is an optional transitive attribute, which emphasizes hat the
destination prefix is an aggregate. The attribute value gives the number of the last AS that did the
aggregation followed by the IP address of the router that did so.
Multicasting • Unicasting ( for information only)
Routing-MOSPF
Multicasting Multicasting ( for information only)
Routing-MOSPF
• Multicasting versus multiple unicasting ( for
Multicasting information only)
Routing-MOSPF
Multicasting Routing-MOSPF
• Multicast Open Shortest Path First (MOSPF) is the extension of the Open
Shortest Path First (OSPF) protocol, which is used in unicast routing. It also
uses the source based tree approach to multicasting. If the internet is running a
unicast link-state routing algorithm, the idea can be extended to provide a
multicast link-state routing algorithm.

• To extend unicasting to multicasting, each router needs to have another

database, as with the case of unicast distance-vector routing, to show which
interface has an active member in a particular group.
MODPF
• The OSPF link state database provides a complete description of AS
topology.
• MOSPF complements the database with a new tuple of link state
record – group membership.
• A special flag is added in the database for supporting MOSPF
• Therefore MOSPF routers actually can perform RPF and prune
computation “in memory” .
Multicasting Routing-MOSPF
• A router goes through the following steps to forward a multicast packet
received from source S and to be sent to destination G.
• Step1: The router uses the Dijkstra algorithm to create a shortest-path tree with
S as the root and all destinations in the internet as the leaves.
Here, the root of the tree is the source of the packet defined in the source address
of the packet. The router is capable of creating this tree because it has the LSDB,
the whole topology of the internet.
• The router finds itself in the shortest-path tree created in the first step. In other
words, the router creates a shortest-path subtree with itself as the root of the
subtree.
• The shortest-path subtree is actually a broadcast subtree with the router as the
root and all networks as the leaves.
• The router can now forward the received packet out of only those interfaces
that correspond to the branches of the multicast tree.
Multicasting • Example of tree formation in MOSPF
Routing-MOSPF