Routing Algorithm & Routing Protocol

Routing Algorithm & Routing Protocol

ASST. PROF. CHENG MICH / 2023-2024
Introduction
• Your friend who is in another city or country.

• Basically, you‟d choose a service that takes the shortest path (takes less time/
delay) or you‟d choose a path that is less expensive

• For communication devices as well have to deal with choosing a path or route to
send information from one node (device) to another.

• Routing, also referred to as forwarding network in the past, is the process to

find the best path (usually shortest path) from a source to destination.

ASST. PROF. CHENG MICH / 2023-2024

Basic routing
• Basically, there are two types of routing:

• Source routing : source collects all the information about the route and then
sends the message (packet) containing the full information

• hop-to-hop routing: Instead it can send the packet to next hop (node) and
the next hope will take care of the hop after that

• Routing process are the routing table, routing protocols and routing
algorithms.

ASST. PROF. CHENG MICH / 2023-2024

Process of routing
• Routing Algorithm: Distance Vector vs. Link State

• Hierarchical routing architectures

• Routing Protocol: Static Route & Default Route

• Routing Protocol: Routing Information Protocol (RIP)

• Interior Gateway Routing Protocol (IGRP)

• Routing Protocol: Enhanced Interior Gateway Routing Protocol (EIGRP)

• Open Shortest Path First (OSPF)

• Routing Protocol: Border Gateway Protocol (BGP)

ASST. PROF. CHENG MICH / 2023-2024

What is routing?
• Routing is a way to get one packet from one destination to the next.

• Routers or software in a computer determines the next network point to

which a packet should be forwarded toward its final destination.

• The router is connected to at least two networks and makes a decision which
way to send each data packet based on its current state of the networks.

ASST. PROF. CHENG MICH / 2023-2024

Algorithm Types of routing
• Static versus dynamic

• Single-path versus multi-path

• Link state versus distance vector

ASST. PROF. CHENG MICH / 2023-2024

Static routing
• Static routing algorithms are hardly algorithms at all, but are table mappings
established by the network administrator prior to the beginning of routing.

• route do not change unless the network administrator alters them

• Static routing Algorithms that use static routes are simple to design and
work well in environments.

ASST. PROF. CHENG MICH / 2023-2024

Link-state algorithms
• Link-state algorithms also known as shortest path first algorithms

• flood routing information to all nodes in the internetwork.

• The portion of the routing table that describes the state of its own links.

ASST. PROF. CHENG MICH / 2023-2024

Distance- vector algorithms
• Distance- vector algorithms also known as Bellman-Ford algorithms, router
to send all or some portion of its routing table, but only to its neighbors.

• link- state algorithms send small updates everywhere, while distance- vector
algorithms send larger updates only to neighboring routers.

• link- state algorithms are somewhat less prone to routing loops than
distance- vector algorithms.

ASST. PROF. CHENG MICH / 2023-2024

Routing Metrics
• Routing algorithms have used many different metrics to determine the best
route.

• Sophisticated routing algorithms can base route selection on multiple

metrics, combining them in a single (hybrid) metric.

• Metrics have been used: Path Length, Reliability, Delay, Bandwidth, Load, and
Communication Cost

ASST. PROF. CHENG MICH / 2023-2024

Why Use Static Routing?
• Static routing provides some advantages over dynamic routing, including:

• Static routes are not advertised over the network, resulting in better security.

• Static routes use less bandwidth than dynamic routing protocols, as routers
do not exchange routes.

• No CPU cycles are used to calculate and communicate routes.

• The path a static route uses to send data is known.

ASST. PROF. CHENG MICH / 2023-2024

Why Use Static Routing?
• Static routing has the following disadvantages:

• Initial configuration and maintenance is time-consuming.

• Configuration can be error-prone, especially in large networks.

• Administrator intervention is required to maintain changing route information.

• Does not scale well with growing networks; maintenance becomes cumbersome.

• Requires complete knowledge of the whole network for proper implementation.

ASST. PROF. CHENG MICH / 2023-2024

Dynamic Routing Versus Static Routing
Dynamic Routing Static Routing
Generally independent of the network
Configuration Complexity Increases with the network size
size
Automatically adapts to topology
Topology Changes Administrator intervention required
changes
Suitable for simple and complex
Scaling Suitable for simple topologies
topologies
Security Less secure More secure
Resource Usage Uses CPU, memory, link bandwidth No extra resources needed
Route to destination is always the
Predictability Route depends on the current topology
same
ASST. PROF. CHENG MICH / 2023-2024
Dynamic Routing protocols
• Routing Information Protocol (RIP)

• Interior Gateway Routing Protocol (IGRP)

• Enhanced Interior Gateway Routing Protocol (EIGRP)

• Open Shortest Path First (OSPF)

• Routing Protocol: Border Gateway Protocol (BGP)

ASST. PROF. CHENG MICH / 2023-2024

RIP
Routing Information Protocol (RIP)
• The Routing Information Protocol(RIP) is a distance-vector protocol that uses hop
count as its metric. The original incarnation of RIP was the Xerox protocol, GWINFO.

• RIP itself evolved as an Internet routing protocol:

• The AppleTalk Routing Table Maintenance Protocol (RTMP)

• Banyan VINES Routing Table Protocol (RTP), RIP Routing Metric

• RIP uses a single routing metric (hop count) to measure the distance between the
source and a destination network.

ASST. PROF. CHENG MICH / 2023-2024

Interior Gateway Routing Protocol (IGRP)
• is a proprietary distance vector routing protocol used to communicate routing information
within a host network.

• It was invented by Cisco.

• Communicate routing information to all connected routers within its boundary or

autonomous system

• Continue updating whenever there is a topological, network or path change that occurs

• IGRP sends a notification of any new changes, and information about its status, to its
neighbors every 90 seconds.

ASST. PROF. CHENG MICH / 2023-2024

Interior Gateway Routing Protocol (IGRP)
• The protocol ensures that every router has routing tables updated with the
best available path.

• The limitations in Routing Information Protocol (RIP), which handles a maximum

hop count of 15.

• IGRP supports a maximum hop count of up to 255.

• IGRP also avoids routing loops by updating itself with the changes occurring
over the network and by error management.

ASST. PROF. CHENG MICH / 2023-2024

Enhanced Interior Gateway Routing Protocol (EIGRP)
• Enhanced Interior Gateway Routing Protocol (EIGRP) is an interior gateway
protocol suited for many different topologies and media.

• In a well designed network, EIGRP scales well and provides extremely quick
convergence times with minimal network traffic.

• A routing protocol used in networks to determine the best path for data
packets to travel.

• adapts to changes in the network topology and avoids routing loops.

ASST. PROF. CHENG MICH / 2023-2024

Features of EIGRP
• Fast convergence: Quickly adapts to network changes, minimizing downtime
and disruptions.

• Loop-free routing: Employs the Diffusing Update Algorithm (DUAL) to prevent

routing loops.

• Flexible metrics: Considers bandwidth, delay, reliability, load, and MTU to choose
the best path.

• Scalability: Efficiently routes traffic in large networks.

• Easy configuration: Relatively simple to set up and manage.

ASST. PROF. CHENG MICH / 2023-2024
Features of EIGRP cont..
• Applications:
• Enterprise networks
• Campus networks
• Data center networks
• Service provider networks
• Limitations:
• Primarily a Cisco proprietary protocol (limited version available for others).
• May not be suitable for very large or complex networks.
Open Shortest Path First (OSPF)
OSPF Overview
• Creates a neighbor relationship by exchanging hello packets
• Propagates LSAs rather than routing table updates
★Link: Router interface
★State: Description of an interface and its relationship to neighboring routers
• Floods LSAs to all OSPF routers in the area, not just directly connected routers
• Pieces together all the LSAs generated by the OSPF routers to create the OSPF link-state
database
• Uses the SPF algorithm to calculate the shortest path to each destination and places it in the
routing table
Summary
• OSPF is a classless, link-state routing protocol that uses an area hierarchy for fast convergence.
• OSPF exchanges hello packets to establish neighbor adjacencies between routers.
• The SPF algorithm uses a cost metric to determine the best path. Lower costs indicate a better
path.
• The router ospf process-id command is used to enable OSPF on the router.
• Use a loopback interface to keep the OSPF router ID consistent.
• The show ip ospf neighbor command displays OSPF neighbor information on a per-interface basis.
• The commands debug ip ospf events and debug ip ospf packets can be used to troubleshoot
OSPF problems.
• OSPF will load-balance across up to four equal-cost metric paths by default.
• There are two types of OSPF authentication: Plaintext and MD5.

46
Routing Protocol: Border Gateway
Protocol (BGP)
BGP (Border Gateway Protocol)
• Terms

• IGP (Interior Gateway Protocol) - RIP, IGRP, EIGRP, OSPF = Routing protocol used to
exchange routing information within an autonomous system.

• EGP (Exterior Gateway Protocol) - BGP = Routing protocol used to exchange routing
information between autonomous systems.

• Autonomous System = (From RFC 1771) "A set of routers under the single technical
administration, using an IGP and common metrics to route packets within the AS, and using
an EGP to route packets to other AS's."

• BGP is a path vector or an advanced distance vector routing protocol.

IGP versus EGP
• Interior gateway protocol (IGP)

• A routing protocol operating within an Autonomous System (AS).

• RIP, OSPF, and EIGRP are IGPs.

• Exterior gateway protocol (EGP)

• A routing protocol operating between different AS.

• BGP is an interdomain routing protocol (IDRP) and is an EGP.

IGP versus EGP
• BGP works differently than IGPs because it does not make routing decisions based on
best path metrics.

• Instead, BGP is a policy-based routing protocol that allows an AS to control traffic

flow using multiple BGP attributes.

• Routers running BGP exchange network attributes including a list of the full path of
BGP AS numbers that a router should take to reach a destination network.

• BGP allows an organization to fully use all of its bandwidth by manipulating these path
attributes.
IGP versus EGP
Protocol
Interior or Exterior Type Hierarchy Required? Metric

Interior Distance vector No Hop count

RIP

Link state
OSPF Interior Yes Cost

IS-IS Interior Link state Yes Metric

Advanced distance
EIGRP Interior vector No Composite

Path vector
BGP Exterior No Path vectors (attributes)
Autonomous Systems (AS)
• An AS is a group of routers that share similar routing policies and operate within a single
administrative domain.

• An AS typically belongs to one organization.

• A single or multiple interior gateway protocols (IGP) may be used within the AS.

• In either case, the outside world views the entire AS as a single entity.

• If an AS connects to the public Internet using an exterior gateway protocol such as BGP, then
it must be assigned a unique AS number which is managed by the Internet Assigned Numbers
Authority (IANA).
AS Numbers
• AS numbers can be between 1 to 65,535.

• RIRs manage the AS numbers between 1 and 64,512.

• The 64,512 - 65,535 numbers are reserved for private use (similar to IP Private addresses).

• The lANA is enforcing a policy whereby organizations that connect to a single provider use an AS number from the
private pool.

• Note:

• The current AS pool of addresses is predicted to run out by 2012.

• For this reason, the IETF has released RFC 4893 and RFC 5398.

• These RFCs describe BGP extensions to increase the AS number from the two-octet (16-bit) field to a four-octet
(32-bits) field, increasing the pool size from 65,536 to 4,294,967,296
Question
• What is static route, dynamic route?

• Compare Static with dynamic

• Compare Single-path with multi-path

• Compare Link state with distance vector

• What is eBGP and iBGP?

• What is AS number?

ASST. PROF. CHENG MICH / 2023-2024

The End
Thank you

ASST. PROF. CHENG MICH / 2023-2024