Routing Basics

What’s going on the

back …
 Routed Protocols Versus Routing Protocol

03/19/2025
Local Area Networks 2
2
 Inter-domain and Intra-domain Routing
 Routing is done differently within an autonomous
system (intra-domain routing) and between
autonomous system (inter-domain routing).

 An autonomous system is a region of the Internet

that is administered by a single entity.
 Examples of autonomous regions are:
• UVA’s campus network
• MCI’s backbone network
• Regional Internet Service Provider

Local Area Networks 3

 Autonomous Systems (AS)

Ethernet Ethernet Autonomous

System 1

Router Ethernet Router

Router

Router Ethernet

Autonomous
Ethernet
Router System 2 Router
Ethernet

Local Area Networks 4 4

 Inter-domain and Intra-domain Routing
Interdomain
Intradomain Routing
 Routing between
within an AS’s
AS
 Ignores the
Assumes that
Internet
the Internet
outsideconsists
the AS of a collection of
 interconnected AS’s
Protocols for Intradomain routing are also called Interior
 Gateway there
Normally, Protocols
is oneordedicated
IGP’s. router in each AS that
 handles interdomain
Popular protocols aretraffic.
 Protocols for interdomain
 RIP (simple, old) routing are also called Exterior
Gateway Protocols or EGP’s.
 OSPF (better)
 Routing protocols:
 EGP
 BGP (more recent)

Local Area Networks 5 5

  Main function of Network Layer is
– ???????

 In most cases packet requires multiple hops to

make journey.
 The algorithms that chooses the routes is major
area of Network layer design.

Local Area Networks 6

 Properties for desirable Routing Algorithms
 Correctness
 Simplicity
 Robustness
 Stability
 Fairness
 Optimality

Local Area Networks 7

 Performance Criteria
 used for selection of route
 simplest is “minimum hop”
 can be generalized as “least cost”

Local Area Networks 8

 Decision Time and Place
 time
 packet or virtual circuit basis
 fixed or dynamically changing
 place
 distributed - made by each node
 centralized
 source

Local Area Networks 9

 Network Information Source and Update Timing
 routing decisions usually based on
knowledge of network (not always)
 distributed routing
• using local knowledge, info from adjacent nodes, info
from all nodes on a potential route
 central routing
• collect info from all nodes
 issue of update timing
 when is network info held by nodes updated
 fixed - never updated
 adaptive - regular updates

Local Area Networks 10

 Major Classes
 Non-adaptive Algorithms.
• Not based on measurement or estimate of current traffic and topology.
• The choice of route is computed in advance.
• called as Static Routing/Fixed Routing.

 Adaptive Algorithms.
• Change routing decisions to reflect change in topology, and traffic as
well.
• They differ in where they get their information, and what metric is
used for optimization.

Local Area Networks 11

  Non-adaptive Algorithms.
 Direct delivery
 Indirect delivery
 Static routing
 Default routing
 Adaptive Algorithms
 Distance vector routing
 Link state routing

Local Area Networks 12

Local Area Networks 13
 Static Routing

 The process in which Administrator manually

adding routes in Routers table.
 No overhead on Router CPU
 No bandwidth usage between routers
 Security

 IP route, destination N/W, mask, next hop address, AD.

 Functioning???

Local Area Networks 14

 Why Use a Static Route?

03/19/2025
Local Area Networks 15
15
 Shortest Path Routing
 The idea is to build graph of subnet
• Where each node rep: router and each arc communication link.

 There are many ways of measuring path length

• Number of hops.
• Geographical distance.
• Transmission delay.
• Mean queuing.

Note: In general, the label on arcs could be computed as function of

distance, average traffic, measured delay and other factors.

Local Area Networks 16

Local Area Networks 17
Local Area Networks 18
Local Area Networks 19
 Dijkstra Algorithm

B C
7

2 3
A 2 3
E F D
2

2
6 1 2

G 4 H

[Link]

Local Area Networks 20

 Example of Dijkstra’s Algorithm

Local Area Networks 21

 Routing Strategies - Flooding
 packet sent by node to every neighbor
 eventually multiple copies arrive at
destination
 no network info required
 each packet is uniquely numbered so
duplicates can be discarded
 need some way to limit incessant
retransmission
 nodes can remember packets already forwarded
to keep network load in bounds
 or include a hop count in packets

Local Area Networks 22

 Flooding
Example

Local Area Networks 23

 Properties of Flooding
 all possible routes are tried
 very robust
 at least one packet will have taken minimum hop
count route
 can be used to set up virtual circuit
 all nodes are visited
 useful to distribute information (eg. routing)
 disadvantage is high traffic load generated

Local Area Networks 24

 Flow Based Routing
 The previous algorithms do not consider load.

B C

A D

E F

G H

Local Area Networks 25

 Flow Based Routing (cont…)
 In some networks the mean data flow b/w pair of
nodes is stable and predictable.

 Under these conditions, where average traffic b/w i

and j is known in advance, and constant in time, it
is possible to analyze flows.

Local Area Networks 26

 Flow Based Routing (cont…)
 Basic idea behind analysis is
• For a given line if
– Capacity
– And average flow are known
– It is possible to compute mean packet delay on that
line by queuing theory.
 The routing problem than reduces to finding the
routing algorithm that produces minimum average
delay for subnet.

Local Area Networks 27

 Flow Based Routing (cont…)
 Certain info must be known in advance.

• Subnet topology.
• Traffic matrix Fi,j
• Line Capacity Matrix Ci,j
• Tentative Routing algorithm must be chosen.

Local Area Networks 28

 Routing Strategies - Random Routing

 simplicity of flooding with much less load

 node selects one outgoing path for
retransmission of incoming packet
 selection can be random or round robin
 a refinement is to select outgoing path
based on probability calculation
 no network info needed
 but a random route is typically neither
least cost nor minimum hop

Local Area Networks 29

 Dynamic Routing Algorithms

 Distance Vector Routing

 Link State Routing

Local Area Networks 30

 Distance Vector Routing
 Also called as
• Distributed Bellman-Ford Algorithm.
• Ford-Fulkerson Algorithm.
 It operates by maintaining a table(vector),
 Giving best known distance to destination.
 Which line to use to get there.
 These vectors are updated by exchanging
information with neighbors.

Local Area Networks 31

  Each router maintain the routing table
indexed by and containing one entry for each
router in subnet.
 Entry contain two parts:
 The preferred outgoing line.
 The estimate of metric to that destination.
 The router is assumed to know the “distance”
to each of its neighbors.

Local Area Networks 32

 Count-to-Infinity problem

 Distance Vector routing works in theory.

 It has serious drawbacks.
 It reacts rapidly to good news.
 But leisurely to bad news.

 Example ???

Local Area Networks 33

 Link State Routing ????

Local Area Networks 34