Module-3

Chapter 4
Network Layer
• Introduction
• Virtual Circuit and Datagram Networks
• What’s inside a Router?
• Internet Protocol (IP): Datagram Format, IPv4 Addressing,
ICMP, IPv6
• Routing Algorithms: Link state, Distance vector, Hierarchical
routing
• Routing in the Internet: RIP, OSPF, BGP
• Broadcast and Multicast routing
 Network Layer Services
 Host-to-Host transmission of messages (Transport
segments) from sending to receiving host
 Sending side - encapsulates segments into datagrams and
send to DLL
 Receiving side - decapsulate datagrams and deliver segments
to transport layer
 Network Layer Protocols in Routers
 Router examines header fields in all IP datagrams
passing through it
 Routing: Determine route to be taken by packets
from source to destination
 Forwarding: Move packets from router’s input to
appropriate router output
 Network Layer Service Models
Two fundamental classes of Computer Networks
Datagram Network: Provides connectionless service
 Internet
Virtual-Circuit Network: Provides connection service
 ATM, Frame Relay

Datagram Network – Does not guarantee

1.Delivery of transmitted packets
2.In order delivery of packets
3.Constant Timing between packets
E.g. Internet’s Network Layer - provides a single service, known
as best-effort service
 Datagram Network
 No call setup at network layer
 Routers: No state about end-to-end connections
 No network-level concept of “connection”
 Packets forwarded using destination host address
4 billion IP addresses -
so rather than list
routing algorithm
individual destination
address list range of
local forwarding table addresses (aggregate
dest address output link table entries)
address-range 1 3
address-range 2 2
address-range 3 2
address-range 4 1

IP destination address in
arriving packet’s header
1
3 2
 Datagram Network - Forwarding
Destination Address Range Link Interface
11001000 00010111 00010000 00000000
through 0
11001000 00010111 00010111 11111111

11001000 00010111 00011000 00000000 When looking for

through 1 Forwarding Table
11001000 00010111 00011000 11111111 entry for given
destination address,
use longest
11001000 00010111 00011001 00000000 address prefix that
through 2 matches destination
11001000 00010111 00011111 11111111 address.

otherwise 3
Destination Address Range Link interface
11001000 00010111 00010*** ********* 0
11001000 00010111 00011000 ********* 1
11001000 00010111 00011*** ********* 2
otherwise 3
 Network Layer Service Models
Virtual-Circuit Network
Guaranteed delivery
Guaranteed delivery with bounded delay
In-order packet delivery
Guaranteed minimal bandwidth
Guaranteed maximum jitter
Security services
 E.g. ATM, Frame Relay
 Virtual-Circuit Networks
 A VC consists of
1. Path from source to destination
2. VC numbers, one number for each link along path
3. Entries in forwarding tables in routers along path
 Packet carry VC number (rather than destination address)
 VC number is changed on each link - new VC number
comes from Forwarding Table
 Phases: VC Setup, Data Transfer, VC Teardown

VC Signaling Protocols
• Used to Setup, Maintain, Teardown VC
• Used in ATM, Frame-Relay, X.25
• Not used in today’s Internet
 Virtual-Circuit Networks
• Routers along the path between the two end systems are
involved in VC setup
• Each router is fully aware of all the VCs passing through it
• VC routers maintain connection state information!
12 22 32

1 3
2
VC number
interface
number
Forwarding Table
Incoming interface Incoming VC # Outgoing interface Outgoing VC #

1 12 3 22
2 63 1 18
3 7 2 17
1 97 3 87
… … … …
 Router

Forwarding tables computed, Routing

pushed to input ports
Processor Routing, Management
Control plane (Software)

Forwarding
Data plane (Hardware)

High-seed
Switching
Fabric

Router Input Ports Router Output Ports

 Router
Four Components: Input Ports, Switching Fabric, Output
Ports, Routing Processor

1.Input Ports
• Performs the physical layer function of terminating an incoming
physical link - leftmost box
• Performs link-layer functions needed to interoperate with the link
layer at the other side of the incoming link - middle box
• Lookup function is also performed - rightmost box
• Control packets (packets carrying routing protocol information) are
forwarded to the routing processor
 Router
2. Switching Fabric
• Connects the router’s input ports to its output ports
• Completely contained within the router— a Network inside of a
network router!

3. Output Ports
• Store packets received from the switching fabric and transmits them
on the outgoing link by performing the necessary Link-layer and
Physical-layer functions
• Performs Link-layer functions needed to interoperate with the link layer at
the other side of the incoming link - middle box
• Performs the Physical layer function of terminating an incoming physical
link - rightmost box
 Router
4. Routing Processor
• Executes the routing protocols
• Maintains routing tables and attached link state information,
• Computes the forwarding table for the router
• Performs the network management functions

All these, together implement the forwarding function and

are almost always implemented in hardware
 Router – Input Port Processing

Lookup,
Link Forwarding
Line Layer Switch
Termination Protocol Fabric
(Receive)
Queueing

Physical Layer:
Bit-level reception
Decentralized Switching:
Data Link Layer
• Given datagram destination, lookup output
port using Forwarding Table in input port
memory (“match plus action”)
• Goal: Complete input port processing at ‘line
speed’
• Queuing: If datagrams arrive faster than
forwarding rate into switch fabric
 Router – Switching via Memory
• Switching can be accomplished in 3 ways:
Via Memory/ Via Bus/ Via an Interconnection Network
1. Switching via Memory
• First generation routers - Computers with switching
under control of CPU
• Packet is copied to system’s memory. Routing
processor extracts the destination address from the
header, looks up the appropriate output port in the
Forwarding Table - copies the packet to the output
port’s buffers
• Speed limited by memory bandwidth (2 bus crossings
per datagram)
memory
 Router – Switching via Bus
2. Switching via Bus
• Input port pre-pends a Label (Header) to the packet
indicating the output port to which this packet is being
transferred and transmits onto the bus
• The packet is received by all output ports, but only the
port that matches the label will keep the packet
• The Label is then removed at the output port
• Every packet must cross the single bus - switching
speed is limited to the bus speed
 Router – Switching via network
2. Switching via interconnection network
• A Crossbar Switch that connects N input ports to N
output ports is used
• Forwarding is done by closing the appropriate cross-
point switch
• Multiple packets can be forwarded in parallel (except
when the destinations are same)
 Router – Output Processing
Queueing
(Buffer) Data Link
Switch Management) Layer Line
Fabric Protocol Termination
(Encapsulation)

• Takes packets in the output port’s memory and transmits

them over the output link
• Includes selecting and de-queueing packets, and
performing the Link Layer and Physical Layer functions

Amount of buffering needed: B = RTT . C/√N

N - number of TCP flows
C – Link capacity
RTT – Average Round Trip Time
 Router – Output Processing
• A Packet Scheduler at the output port chooses one
packet among those queued for transmission
• FCFS, Weighted Fair Queueing…
• If there is not enough memory to buffer an incoming
packet, a decision must be made to:
• Drop the arriving packet - Drop-Tail or
• Remove one or more already-queued packets -
Random Early Detection (RED) algorithm (if the queue
is full or the average queue length is greater than a
Maximum Threshold (maxth), the packet is marked or
dropped)
 Queueing at Switch Fabric
• If the switch fabric is not fast enough (relative to the input
line speeds) - packet queuing can occur at the input
ports
• If a packet at the front of the queue has to wait (as its
destination is the same as one more packet on a different
input line), a packet behind it, even for a different
destination, for which there is no contention, will also
have to wait - Head-of-the-Line (HOL) Blocking
 Internet Protocol - IP

Transport Layer: TCP, UDP

Routing Protocols IP
• Path Selection • Addressing Conventions
• RIP, OSPF, BGP • Datagram Format
• Packet Handling Conventions
Network
Layer Forwarding
ICMP
Table
• Error Reporting
• Router “Signaling”

Link Layer
Physical Layer
 IPv4 Datagram Format

4 Bits 4 Bits 8 Bits 16 Bits

3 Bits

8 Bits 8 Bits 16 Bits

E.g. Time Stamp, Record Route

List of routers to visit

Variable length - TCP or UDP segment

 IPv4…
1. VER (Version): 4 bits: Value = 4
2. HLEN (Header Length): 4 bits: Specifies the header
size in 4-byte words (value can be 5-15)
3. Service Type: 8 bits: Originally - Type Of Service
(TOS). Later redefined to provide Differential Services –
DiffServ
4. Total Length: 16 bits: Length of (Header+Data) in
bytes – Maximum = 65535
• Length of Payload= (Total length – 4 X HLEN value)
5. Identification: 16 bits:
6. Flags: 3 bits: 0 - DF - MF Used in fragmentation

7. Fragmentation offset: 13 bits

 IPv4…
8. Time-to-Live: 8 bits: Number of hops for a datagram.
• Set to approximately double the number of hops needed.
Each router that processes decrements it by 1. If 0 after
decrementing, the datagram is discarded
• If the routing tables are corrupted, some datagrams may
simply move around without reaching the destination
9. Protocol: 8 bits: Specifies the higher level protocol that to
which the data belongs to – TCP/UDP/ICMP/ IGMP.
E.g. ICMP-1, IGMP-2, TCP-6, UPD-17, OSPF-89
10. Header Checksum: 16 bits: IP Checksum – only for header
11. Source Address: 32 bits
12. Destination Address: 32 bits
13. Options: Up to 40 bytes – Used for testing and debugging
Payload: Data
 Datagram Fragmentation
• Each of the links along a route between sender and
destination can use:
• Different Link-Layer protocols, and
• Each of these protocols can have different Maximum
Transmission Unit (MTU). Eg. Ethernet – 1500 bytes

• If the outgoing link has smaller MTU than the length of

the IP datagram, the datagram has to be divided into
smaller IP datagrams and encapsulated in separate link
layer frames – Fragmentation

• IP at the destination host will reassemble them

• Identifier, Flag, and Fragmentation-offset fields are

used when fragmentation is required
 Datagram Fragmentation
length ID fragflag offset
=4000 =x =0 =0
example:
 4000 byte datagram
 MTU = 1500 bytes one large datagram becomes
several smaller datagrams

1480 bytes in length ID fragflag offset

data field =1500 =x =1 =0

offset = length ID fragflag offset

1480/8 =1500 =x =1 =185

length ID fragflag offset

=1040 =x =0 =370
 IPv6
• Developed to respond to the need for a large IP
address space
• Opportunity used - to tweak and augment other
aspects of IPv4
• IPv6 - Features
• Fixed-length 40 byte header
• Expanded address space – 2128
• Less fields in the header – Faster Processing
• Anycast Addresses: To send to the nearest of a group of hosts
• No fragmentation/ reassembly at the routers – Routers
will drop if larger datagram - Packet too big message sent
by ICMP
• No Header Checksum
 IPv6

32 bits

Version Traffic
4 Class 8 Flow Label 20

Payload Length 16 Next Header 8 Hop Limit 8

Header Source Address 128

16 Bytes

Destination Address 128

16 Bytes

Data
 IPv6
1. Version: 4-bits - Identifies the IP version number – 0110
2. Traffic Class: 8-bits - Similar to the TOS in IPv4
3. Flow Label: 20-bits is used to identify a flow of datagrams
4. Payload Length: 16-bits - Treated as an unsigned integer
giving the number of bytes of data after the header
5. Next Header: 8-bits - Identifies the protocol to which the
contents (data field) of this datagram will be delivered
(TCP / UDP) - Same as the Protocol field in IPv4
6. Hop Limit: 8-bits – Value decremented by one by each
router that forwards the datagram. If it reaches zero, the
datagram is discarded – Same as TTL of IPv4
7 & 8. Source and Destination Addresses: 128-bits – 8
groups of 16 bits - denoted as Hexadecimal Number –
separated by colons
 Transition from IPv4 to IPv6
• Abrupt transition (declaring a Flag Day) is not
feasible. Hence two solutions:
1. Dual-Stack Approach
• Nodes will have both IPv4 and IPv6 protocols and
addresses
• To determine if another node is IPv6 enables – DNS must
give the information while returning address
• Problem: IPv6 to IPv4 can be correctly done and the
reverse will not be correct as some fields of IPv6 are not
present in IPv4
 Transition from IPv4 to IPv6
2. Tunneling
• If two IPv6 nodes are interconnected by an IPv4 node, the
sender encapsulates IPv6 datagram in an IPv4 datagram
and sends it to the intermediate node. This is then
forwarded to the next IPv6 node

• Solves the problem in Dual Stack.

 IPsecurity
• IPv4 was designed (1970s) when the Internet was
primarily used among mutually-trusted researchers
• Security is a major concern today
• IPsec - Popular secure Network-Layer Protocol -
widely deployed in Virtual Private Networks (VPNs) -
backward compatible with IPv4 and IPv6
• IPsec’s Transport Mode:
• Two hosts first establish an IPsec session between them
• IPsec encrypts the segment, appends additional security
fields to the segment, and encapsulates the resulting
payload in an ordinary IP datagram – Authentication is also
provided
 IPsecurity
Services provided by an IPsec session
•Cryptographic Agreement: Mechanisms that allow hosts to
agree on Cryptographic Algorithms and Keys
•Encryption of IP Datagram Payloads: Sender IPsec
encrypts the payload – receiver IPsec decrypts it
•Data Integrity: Receiving host can verify that the
datagram’s header fields and encrypted payload were not
modified while the datagram was en route
•Origin Authentication: When a host receives an IPsec
datagram from a trusted source the host is assured that the
source is genuine
IPsec if desired, has to be installed on Servers and Clients
 Routing Algorithms
• A host is attached directly to one router - the Default
Router / First-hop Router/ Source Router
• Routing: Determining a ‘Least Cost’/ Shortest path from
Source Router to Destination Router
• To formulate routing problems, a graph is used. A graph
G = (N,E) is a set N of nodes and a collection E of edges.
N – Nodes are Routers and Edges are Links
Each edge - a pair of nodes has a value representing the cost c
• If an edge (x,y) does not belong to E, c(x,y) = ∞
• c(x,y) = c(y,x)
• A node y is said to be a neighbor
of node x if (x,y) belongs to E
 Routing Algorithms - Classification
• Centralized/ Global Routing Algorithm: Least-cost path is about
the network - Link-State (LS) Algorithms computed using complete,
global knowledge
• Decentralized/ Distributed Routing Algorithm: No node has
complete information about the costs of all network links - through
iterative process of exchange of information with neighbors least-
cost path is computed - Distance-Vector (DV) Algorithm
• Static Routing Algorithms: routes change as a result of human
intervention
• Dynamic Routing Algorithms: Paths change as the network
traffic or topology change - algorithm can be run either periodically
or in response to topology or link cost changes
• Load-Sensitive Algorithm: Link costs vary dynamically to reflect
the level of congestion in the underlying link
• Load-Insensitive Algorithm: Link costs do not explicitly reflect the
level of congestion - RIP, OSPF, and BGP
 Link State Routing Algorithm
• Each node broadcasts Link-State Packets (LSPs) to all
other nodes in the network and share link costs – Open
Shortest Path First (OSPF) Protocol
• All nodes then run the LS Algorithm - Dijkstra’s
Algorithm - and computes the same set of least-cost
paths
• Dijkstra’s Algorithm computes the least-cost path from a
source node - u - to all other nodes in the network -
Iterative algorithm - after the kth iteration, least-cost paths
to k destination nodes will be available. Notations:
• c(x,y): Link cost from node x to y; = ∞ if not direct neighbors
• D(v): Current value of least cost of path from source to dest. v
• p(v): Predecessor node along least cost path from source to v
• N': Set of nodes whose least cost path is known
 Link State Routing Algorithm
Step-1: Initialization: Currently known paths to immediate
neighbours are recorded. N’ is initialized to the source node

Step-2: Until all nodes are in N’

• A node, w from N, not in N’ that has the minimum cost
is found and is added to N’
• Distance from source node to all other nodes via w is
calculated, compared with the available cost and the
minimum is recorded along with the previous node
 Link State Routing Algorithm
1 Initialization:
2 N' = {u}
3 for all nodes v
4 if v is a neighbor of u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find w not in N' such that D(w) is a minimum
10 add w to N'
11 update D(v) for each neighbor v of w and not in N' :
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until N' = N
 Link State Routing Algorithm
5
3 Least-cost paths from u
v w 5
2 to all possible destinations
u 2 1 z
3
1 2
x 1
y
Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5 uxyvwz
destination link
v (u,v)
Forwarding table in u x (u,x)
y (u,x)
w (u,x)
Shortest-path tree from u z (u,x)
 Link State Routing Algorithm
Algorithm Complexity: n nodes (not counting the source)
•First iteration searches through all n nodes to determine the
node, w, not in N that has the minimum cost
•Second iteration checks (n-1) nodes to determine the
minimum cost
•Third iteration checks (n–2) nodes, and so on ….
•Total number of nodes to be searched = n(n + 1)/2
•Hence, Worst-case complexity = O(n2)
•More efficient implementations possible: O(n log n)

•Problem: When the link costs are not symmetric,

oscillations in successively computed routes may result
•Solution: Ensure that not all routers run the LS algorithm
at the same time
 Distance Vector Routing Algorithm
• Distributed, Iterative, Asynchronous, and Self-terminating
• Each node receives information from its direct neighbors,
performs a calculation, and shares with its neighbors

• Works on the principle of Bellman-Ford - Least cost from

x to y is the minimum of taken over all neighbors v

• Let dx(y) be the cost of the least-cost path from node x to

node y.
• Bellman-Ford equation: dx(y) = minv {c(x,v) + dv(y)}
• minv in the equation is taken over all of x’s neighbors
 Distance Vector Routing Algorithm
Bellman-Ford Equation
5

3
v w
2 5
u 2 1 z
3
1
2
x y
1
•v, x, and w are the neighbours to u
•dv(z) = 5, dx(z) = 3, dw(z) = 3
•B-F equation:
du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z),c(u,w) + dw(z) }
= min { 2 + 5, 1 + 3, 5 +3
}
= 4
 Distance Vector Routing Algorithm
1 Initialization:
2 for all destinations y in N:
3 Dx(y) = c(x,y) /* if y is not a neighbor then c(x,y) = ∞ */
4 for each neighbor w
5 Dw(y) = ? for all destinations y in N
6 for each neighbor w
7 send distance vector Dx = [Dx(y): y in N] to w
8
9 loop
10 wait (until there is a link cost change to some neighbor w or
11 until a distance vector from some neighbor w is received)
12
13 for each y in N:
14 Dx(y) = minv{c(x,v) + Dv(y)}
15
16 if Dx(y) changed for any destination y
17 send distance vector Dx = [Dx(y): y in N] to all neighbors
18
19 forever
 Distance Vector Routing Algorithm
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
Each Node: = min{2+0 , 7+1} = 2

wait for (change in local node x cost to cost to

link cost or msg from table x y z x y z
neighbor) x 0 2 7 x 0 2 3

from
y ∞∞ ∞ y 2 0 1

from
recompute estimates
z ∞∞ ∞ z 7 1 0
if DV to any dest has
node y cost to
changed, notify table x y z Dx(z) = min{c(x,y) +
neighbors
x ∞ ∞ ∞ Dy(z), c(x,z) + Dz(z)}
from

y 2 0 1 = min{2+1 , 7+0} = 3
z ∞∞ ∞

node z cost to
table x y z
x ∞∞ ∞
from

y ∞∞ ∞
z 7 1 0
 Distance Vector Routing Algorithm
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} Dx(z) = min{c(x,y) +
= min{2+0 , 7+1} = 2
Dy(z), c(x,z) + Dz(z)}
node x cost to cost to = min{2+1 , 7+0} = 3
cost to
table x y z x y z x y z
x 0 2 7 x 0 2 3 x 0 2 3

from
y ∞∞ ∞ y 2 0 1
from

y 2 0 1

from
z ∞∞ ∞ z 7 1 0 z 3 1 0
node y cost to cost to cost to
table x y z x y z x y z
x ∞ ∞ ∞ x 0 2 7 x 0 2 3
from

y 2 0 1 y 2 0 1
from

y 2 0 1

from
z ∞∞ ∞ z 7 1 0 z 3 1 0

node z cost to cost to cost to

table x y z x y z x y z
x ∞∞ ∞ x 0 2 7 x 0 2 3
from

from

y 2 0 1 y 2 0 1
from

y ∞∞ ∞
z 7 1 0 z 3 1 0 z 3 1 0
time
 Distance Vector Routing Algorithm
Link-Cost Changes and Link Failure
•Good news about the decreased cost between nodes
propagates quickly through the network
•when a link cost (x,y) increases:

y computes its new minimum-cost path to x to via z as:

Dy(x) = min{c(y,x) + Dx(x), c(y,z) + Dz(x)} = min{60 + 0, 1 + 5} = 6
•in order to get to x, y routes through z, and z routes through y -
routing loop !
•Now, Node y informs the updated value to z and x
•z will update its new cost to x as 1 + 6 = 7. This will be informed to
y, y will update its cost to x as 1+7=8 and so on… After 44 iterations
like this, z computes the cost via y to be greater than 50 and will
prefer direct link to x! – Count to Infinity Problem
•Bad news about the increase in link cost travels slowly!
 Distance Vector Routing Algorithm
Solution to routing loop - Poisoned Reverse
•if z routes through y to destination x, then z will advertise to
y that its distance to x is infinity

•Refer text for solution to the case discussed previously…

•Poisoned Reverse solves if looping is due to two

neighbouring nodes
•If the problem is due to 3 or more nodes poisoned
reverse technique can not solve it
 Comparison
LSR DVR
Message complexity Requires O(|N| |E|) Propagates changed
messages to be sent link cost only if It
results in a changed
cost for any node
Speed of O(|N|2) Can converge slowly
convergence and can have routing
loops while the
algorithm is converging

Problems No Problem Count-to-infinity

Robustness A router could broadcast An incorrect node
an incorrect cost for one of calculation spreads
its attached links through the entire
Each node computes only network
its own forwarding
table
 Hierarchical Routing
• As the number of routers becomes large, sharing routing
information, computing paths and storing routing information
become complex, time consuming and demands large amounts
of memory
• Also, an organization should be able to run and administer its
own network while being able to connect to other networks
• Hence networks are organized into Autonomous Systems (ASs)
with each AS consisting of a group of routers that are typically
under the same administrative control
• Routers within the same AS all run the same routing algorithm
– LSR or DVR – Intra AS Routing Protocols – Interior
Gateway Protocols (IGP) - RIP & OSPF
• To connect ASs to each other – Inter AS Routing - one or more
of the routers in an AS will have additional task of forwarding
packets to destinations outside the AS - Gateway Routers -
Exterior Gateway Protocol (EGP) - BGP
 Hierarchical Routing

Adding an outside-AS destination

in a router’s Forwarding Table – Hot Potato Routing
 Routing Information Protocol - RIP
• Distance Vector Routing
• Uses hop count as a cost metric
- each link has a cost of 1
• Maximum cost of a path is limited to 15 - limits the use of RIP
to ASs that are fewer than 15 hops in diameter
• Routing updates - exchanged between neighbors approx.
every 30 seconds using a RIP Response Message – RIP
Advertisements
• Each router maintains Routing Table - includes both the
router’s Distance Vector and the router’s Forwarding Table
(has 3 columns)
Routing Table in router D
 Routing Information Protocol - RIP
• If a router does not hear from its neighbor at least once every
180 seconds, that neighbor is considered to be no longer
reachable
• A router can also request information about its neighbor’s cost
to a given destination using RIP Request Message
• Routers send RIP messages over UDP using Port Number 520
• In a UNIX system, RIP is implemented by a process called
routed (pronounced “route dee”)
 Open Shortest Path First- OSPF
• OSPF - typically deployed in upper-tier ISPs
• RIP is deployed in lower-tier ISPs and enterprise networks
• Using flooding of Link-State Information - a router constructs
a graph of the AS - runs Dijkstra’s algorithm to determine a
shortest-path tree to all subnets, with itself as the root node
• A router broadcasts link-state information whenever there is
a change in a link or once every 30 minutes
• OSPF advertisements are carried directly by IP
• Advanced features:
• Security - only trusted routers can participate
• Multiple same-cost paths - OSPF allows multiple paths with same cost
• Support for multicast routing- Multicast OSPF (MOSPF)
• Support for hierarchy within a single routing domain
 Border Gateway Protocol - BGP
• Critical protocol for the Internet
• Version 4 - de facto standard inter-AS routing protocol
• Allows each subnet to advertise its existence to the
Internet
• Each AS can:
1. Obtain subnet reachability information from neighboring ASs.
2. Propagate the reachability information to all routers internal to the AS.
3. Determine “good” routes to subnets based on the reachability
information and on AS policy

• Two routers in two different ASs are connected by a

permanent TCP connection
• Pairs of routers within an AS exchange routing information
over semi-permanent TCP connections
 Border Gateway Protocol - BGP
• BGP session between routers in the same AS is called an
internal BGP (iBGP) session
• BGP session that spans two ASs - external BGP (eBGP)
session
 Border Gateway Protocol - BGP
• In BGP, an autonomous system is identified by its globally
unique Autonomous System Number (ASN) - assigned by
ICANN registries
• A router advertises a prefix along with its attributes called
a route – important ones AS-PATH and NEXT-HOP
• When a gateway router receives a route advertisement, it
uses its import policy to decide whether to accept or filter
the route and whether to set certain attributes
• BGP uses eBGP and iBGP sessions to distribute routes
to all the routers within ASs
• If there are two or more routes to the same prefix, then
BGP sequentially invokes the elimination rules until one
route remains
 Broadcast Routing
• N-way unicast - Send a separate copy of the packet to
each destination - simple – but inefficient
• It would efficient for the network nodes to create copies
of a packet

• Flooding (Uncontrolled) : Most obvious technique - Source

sends copies of the packet to all neighbors - Every node
duplicates the packet and forwards a copy to its neighbors
(except the neighbor from which it received the packet)
• Simple and Elegant – But - if the graph has cycles,
one or more copies of packets will cycle indefinitely -
broadcast storm
 Broadcast Routing
Controlled Flooding - Judiciously choose when to flood
1.Sequence-Number-Controlled Flooding
•Source node puts its address and a Sequence Number into a
broadcast packet. Each node maintains this data from packets it
has already processed
•When broadcast packet is received, if its data is in the list, the
packet is dropped
2.Reverse Path Forwarding (RPF)
•A router transmits the packet on all of its outgoing links only if that
link is on its shortest unicast path to the source
The above two methods do not completely avoid the transmission of redundant broadcast packets

3.Spanning Tree Broadcast

•Packets are forwarded only along links in a minimum spanning
tree of the source for unicasting
 Broadcast Routing
Minimum Spanning Tree
•Cost of a tree is the sum of the link costs
•Of all the spanning trees of a graph, one whose cost is minimum
- Minimum Spanning Tree
•A node needs to know which of its neighbors in the graph are
spanning-tree neighbors
Creation and Maintenance of MST– Center-based Approach
1.One Center node is defined – Rendezvous node – Core
2.Other nodes will unicast tree-join messages to the center node
3.Message is forwarded until it either arrives at a node that
already belongs to the spanning tree or arrives at the center
4.Path that the message follows is a branch of the MST – New
branch grafted into the existing tree
 Broadcast Routing
Node E is the selected center of the tree

Nodes joining the Tree in order: F, B, A, C, G …….Refer Text

 Multicast Routing
• A multicast packet is delivered to only a subset (group) of
nodes
• E.g. Software upgrade to selected users, Streaming
continuous media to a set of distributed participants,
Teleconferencing among selected participants…
• Two problems – Identification of receivers, Addressing the
receivers in a group
• Multicast in the Internet - Two Components: Internet Group
Management Protocol (IGMPv3) and Multicast Routing
Protocols
• Using IGMP a host can inform its attached router that an
application wants to join a specific multicast group
• IGMP messages are carried within an IP datagram
 Multicast Routing
• A multicast packet is delivered to only a subset (group) of
nodes
• E.g. Software upgrade to selected users, Streaming
continuous media to a set of distributed participants,
Teleconferencing among selected participants…
• Two problems – Identification of receivers, Addressing the
receivers in a group
• Two Components: Internet Group Management Protocol
(IGMPv3) and Multicast Routing Protocols
• Using IGMP a host can inform its attached router that an
application wants to join a specific multicast group
• IGMP messages are carried within an IP datagram
 Multicast Routing
IGMP Messages
•membership_query : Sent by a router to all hosts on an
interface to determine the set of all multicast groups that
have been joined by the hosts on that interface
•membership_report: response of a host to a
membership_query message/ generated by a host when an
application first joins a multicast group
•leave_group: optional (Alternatively, If membership is not
confirmed on periodical enquiry, the host is assumed to have left)

Multicast Routing: Finds a tree that connects all the

routers that have attached hosts belonging to a multicast
group. Multicast packets will be routed along it
 Multicast Routing
Approaches for determining the multicast routing tree:

•Using a Group-Shared tree: Constructs a single, shared

routing tree to route packets from all senders

•Using a Source-Based tree: Constructs a multicast routing

tree for each source in the multicast group.
• Reverse Path Forwarding (RPF) technique with Pruning is
used
• A multicast router that has no attached hosts of a group -
sends a prune message to its upstream router. If a router
receives prune messages from each of its downstream
routers, then it will forward a prune message upstream
 Multicast Routing - DVMRP
• First multicast routing protocol in the Internet -
Implements source-based tree with reverse path
forwarding and pruning
• Most widely used protocol - Protocol-Independent
Multicast (PIM) routing protocol. Two modes:
o Dense Mode: Group members are densely located- flood-
and-prune reverse path forwarding technique (similar to
DVMRP)
o Sparse Mode: Number of routers with attached group
membersis small - group members are widely dispersed -
uses rendezvous points to set up the multicast distribution
tree
Multicast equivalent of Inter-Domain BGP: Multicast
Source Discovery Protocol (MSDP) connects together
rendezvous points in different PIM sparse mode domains