Meaning and Objectives
Routing is the process of moving packets across a network from one host to another. It is usually performed by dedicated devices called routers. Using this process router select best path for sending data to destination.
Routing is a process by which an information, packet is sent from one location to another location. This process is performed by a hardware device called Router. Routers thus route traffic to all the networks in your Internet work.
Routing is a process by which an information, packet is sent from one location to another location. This process is performed by a hardware device called Router. Routers thus route traffic to all the networks in your Internet work.
In order to route packets containing information, a router
needs to know the following key information:
- Destination
address
- Information
sources
- Possible
routes
- Best
routes
- Routing
information maintenance and verification- A way of verifying that the
known paths to destination are valid and are the most current.
Given below are the two ways to tell the router where to
forward packets that are not directly connected:
Static Routes
|
Dynamic Routes
|
Administrator manually establishes the route &the
router learns the routes.
|
Administrator configures the routing protocol and the
router automatically learns the routes.
|
Administrator manually update static route entry, whenever
an internet work topology requires a change or during link failure.
|
Route knowledge cum change is automatically updated,
whenever new topology information is received from routers within the
internet work.
|
Static Routing
Static routes are administratively defined routes. An
administrator manually adds routes in each router’s routing table.
Following are the benefits and disadvantages of static routing:
Following are the benefits and disadvantages of static routing:
Benefits of static Routing:
- No
overhead on the CPU
- No
bandwidth usage between routers.
- High
security (because administrator only allows routing to certain networks).
- Administrator needs to understand Internet work carefully and how each router is connected to configure the routes correctly.
- If one additional network is added to the already existing network, the administrator must add a router to it on all routers.
- It is not feasible in large networks because it would be a full-time job.
The syntax used to add a static route to a routing table is:
Iproute <destination network address>
<mask> <next_hop_address | interface> [administrative
distance] [permanent]
Administrative distance-By default static routes have
an administrative distance of 1.You can change the default value by adding an
administrative weight at the end of the command.
Permanent –is an optional parameter that specifies
that the route will not be removed, even if the interface shuts down.
A default route is a special type of static route
used for situations in which the route from a source to a destination is not known
or when it is unfeasible for the routing table to store sufficient information
about all the possible routes. The default route is also known as gateway of
last resort.
Syntax for the default route is given below:
Router(config)#iproute 0.0.0.0 0.0.0.0
<next_hop_address>
Dynamic Routing
Dynamic routing is the process of using protocols to find
and update routing tables on routers. The protocols used in dynamic routing are
called routing protocols.
A routing protocol is a network layer protocol that
determines routing paths and maintains routing tables. Here under it becomes
important to distinguish between routing protocols and routed protocols. The
table given below distinguishes between the two:
Routing Protocol
|
Routed Protocol
|
It intercepts packets from other participants in order to
learn and maintain a routing table.
|
It defines the format and use of the field within a packet
to provide a transport mechanism for user traffic.
|
It fills up routing table with valid, loopfree routes.
|
It uses the routing protocols to define logical addressing
and routing
|
Example: RIP, IGRP, EIGRP, BGP, OSPF
|
Example: TCP/IP, IPX
|
It must be noted that: -as soon as the routing protocol
determines a valid path between routers, the router can route a routed
protocol.
Routing Protocol
|
Interior Gateway
Protocol
|
Exterior Gateway
Protocol
|
Exchange routing information within an autonomous
system.
E.g. RIP, IGRP
|
Exchange routing information between autonomous
systems.
E.g. BGP
|
An Autonomous System –is a collection of networks under a
common administrative domain. The Internet Assigned Numbers Authority (IANA) is
the umbrella organization responsible for allocating autonomous system numbers.
Administrative Distances
Administrative distances are used to rate the
trustworthiness of routing information .An administrative distance is an
integer from 0 to 255,where 0 is the most trusted and 255 means no traffic will
be passed via this route. In nutshell, a routing protocol with a lower
administrative distance has a more chances of being used.
Table given below shows different administrative distances
of different protocols:
Fig.
Default Administrative Distance Values
Route Source
|
Default Distance
|
Connected interface
|
0
|
Static route address
|
1
|
EIGRP
|
90
|
IGRP
|
100
|
OSPF
|
110
|
RIP
|
120
|
External EIGRP
|
170
|
Unknown/Unbelievable
|
255(will not be used to pass traffic)
|
Classes of Routing Protocol
Within an autonomous system, most IGP routing protocols can
be classified under any of the following three algorithms:
Distance Vector
|
Link-State
|
Balanced Hybrid
|
It determines the direction (vector) and distance to any
link.
|
Also called shortest path first. These protocols builds a
routing table based on topology database.
|
It uses aspects of both distance vectors as well as link
state.
|
E.g.RIP, IGRP
|
Link state routers have best information about the n/w.
E.g.OSPF
|
E.g.EIGRP
|
Distance Vector Routing Protocols
Distance vector routing protocol performs the following
functions in order to transmit the data:
- Identify
sources of information.
- Discover
routes
- Select
the best route.
- Maintaining
routing information.
It refers to process of getting the route information from
neighboring routers.
Discover route
After collecting the information and keeping them in it’s
routing table, a router then discloses the various alternate routes to the
destination.
Select the best route
After updating the routing table, routing protocol has to
select the best path to each network. Each distance vector routing protocol
uses different algorithm (called metric) to determine the best route. It is
assumed that the smaller metric gives us the shortest path to the destination.
Given below is the table of different metrics used by different routing
protocols:
Protocol
|
Metric
|
RIP
|
Hop count
|
IGRP
|
Bandwidth, Delay, Load, Realiability, MTU
|
IPX
|
Ticks, Hopcount
|
Routing Metrics
•
Metrics are
cost values used by routers to determine the best path to a destination
network. Several factors help dynamic routing protocols decide which is
the preferred or shortest path to a particular destination. These factors are
known as metrics and algorithms.
•
Hop
count -The upper path to network X
is preferred because it involves only three hops.
•
Bandwidth-
The lower path is longer (in terms of hops), but preferred because the
bandwidth capacity end to end is greater than the upper path.
Delay - Delay is measured in tens of microseconds (the symbol μ is used to indicate this). Delay represents the amount of time it takes for a router to process, queue, and transmit a data-gram out an interface. Protocols that use this metric must determine the delay values for all links along the path end to end, considering the path with the lowest (cumulative) delay to be a better route.
Reliability -Although this metric may be configured as a fixed value by an administrator, it is generally measured dynamically over a specific time frame, such as five seconds. Routers observe attached links, reporting problems, such as link failures, interface errors, lost data-grams and so on. Links experiencing more problems would be considered less reliable than others making them less desirable paths—the higher the reliability the better the path. Because network conditions are constantly changing, link reliability will change. This value is generally measured as a percentage of 255, with 255 being the most reliable and 1 being least reliable
Load -Load is a variable value, generally measured over a five-second window indicating the traffic load over a specific link. Load measures the amount of traffic occupying the link over this time frame as a percentage of the link's total capacity. The value 255 is equivalent to 100% utilization or load—the higher the value the higher the traffic load (bandwidth utilization) across this link. As traffic increases, this value increases. Values approaching 255 indicate congestion, while lower values indicate moderate traffic loads—the lower the value, the less congested the path, the more preferred.
ROUTING PROTOCOLS
• Allow
routers to dynamically advertise and learn routes.
• Determine
which routes are available and which are the most efficient routes to a
destination.
RIP I, RIP II, IGRP, EIGRP, IS-IS, OSPF, BGP
ROUTED
PROTOCOLS
• Data
packet define by routed protocol which are going to send on network. Like –
rapping of data, format of data.
Internet protocol
DECnet
Novell IPX
Appletalk
Administrative distance
• Administrative
distance is the feature that routers use in order to select the best path
when there are two or more different routes to the same destination from two
different routing protocols. Administrative distance defines the
reliability of a routing protocol
RIP Routing
• The Routing
Information Protocol (RIP) is one of the oldest
distance-vector routing protocols which employ the hop count as
a routing metric. RIP prevents routing loops
by implementing limit on the number of hops allowed in a path from source to
destination.
• Developed
for smaller network.
• RIP
uses UDP port 520 route updates.
• RIP
calculate the route based on hope count.
• Open
standard version RIP, sometimes referred to as IP RIP.
• The
maximum number of hops allowed for RIP is 15.
• A
hope count of 16 is considered an infinite distance and used to discourage
inaccessible, inactive, or undesirable routes.
• Periodic-RIP
uses a 30-sec update interval by default.
• Full
updates- The routers send full updates every time instead of just sending
new or changed routing information.
RIP Convergence
• RIP
takes some time to converge.
• While
RIP requires less CPU power and RAM than some other routing protocols.
RIP Working
• Router
using RIP advertise information about each subnet to their neighbors.
• Their
neighbors in turn advertise the information to their neighbors , and so on,
until all routers have learned the information.
RIP VERSIONS
RIP TIMERS
• The
update interval is the interval at which routes that are learned by RIP are
advertised to neighbors. This timer controls the interval
between routing updates. The update interval is set to 30 seconds, by default.
• RIP
uses a couple of timers to do its work:
• Update:
this is how often we send routing updates, the default is 30 seconds.
• Invalid:
the number of seconds since we received the last valid update, once this timer
expires the route goes into holddown, the default is 180 seconds.
• Holddown:
the number of seconds that we wait before we accept any new updates for the
route that is in holddown, the default is 180 seconds,
• Flush:
how many seconds since we received the last valid update until we throw the
route away, the default is 240 seconds.
ROUTER(CONFIG-ROUTER)#TIMERS$BASIC$(UPDATE_TIME)$(INVALID)$(HOLD)$(FLUSH)
ROUTING LOOPS
• Occur
when the routers forward packet such that the same signal packet ends up back
at the same routers repeatedly.
• Never
delivering the packet.
• Wasting
bandwidth
RIP Loop Prevention
• Route
Poisoning
• Split
Horizon
• Poison
Reverse and Triggered Updates
• Holddown
timers
Route Poisoning
• The
practice of advertising a route, but with a special metric value called
infinity. (Like update of any down network. Send updates to neighbor as 16th
hops (infinity).
Loop Prevention
• Triggered
update
When a route fails, do not wait for the next periodic
update. Instead send immediate triggered update listing the poisoned route.
• Poison
reverse
When learning of a failed route, suspend split-horizon rule
for that route, and advertise the poisoned route.s
• Hold down
timer
As soon as the route is considered to be down. Hold it down
for while. To give the routers time to make sure every router knows that the
route has failed.
EIGRP
• Enhanced
Interior Gateway Routing Protocol (EIGRP) is an advanced distance-vector
routing protocol that is used on a computer network for automating routing decisions
and configuration. The protocol was designed by Cisco Systems as a proprietary
protocol, available only on Cisco routers.
• CISCO
proprietary
• Successor
of IGRP
• Hybrid
routing protocol
• Metric
• Bandwidth
• Delay
(We can also configure Load and
reliability)
• Uses
DUAL – Diffusing – update Algorithm to determine the most efficient route to a
destination.
• RTP-
Reliable Transport Protocol
• Reliable
Multicast on the multicast address 224.0.0.10
• EIGRP
uses IP protocol number 88.
• Support
Classless routing
• Support
VLSM
• Neighbor
table (Neighbor Discovery)
• Pass
the authentication process (if used)
• Same
AS no.
• Both
Interface IP address must be in same network.
• EIGRP
K values must match
• Topology
table
After neighbor process
• EIGRP
sends update message (First time full topology updates, but in future if any
link become down than it send only partial updates. May be never send full
updates in future.)
• Uses
224.0.0.10 to multicast the info to many neighbor. But if router want send info
to one neighbor than it uses unicast address of interface.
• Router
assure that the info received by receiver using RTP. If receiver unable to
receive info than router send it again.
• Routing
table
• Multiple
Metric Inputs.
• K1-
Bandwidth
• K2-
Delay
• K3-
Load
• K4-
Reliability
• Open
Shortest Path First (OSPF) is a routing protocol for Internet Protocol
(IP) networks. It uses a link state routing (LSR) algorithm and falls into the
group of interior routing protocols, operating within a single autonomous
system (AS). It is defined as OSPF Version 2 in RFC 2328 (1998) for
IPv4.
• Uses
transport IP, protocol type 89.
• Support
VLSM/Classless
• Select
the best routes by finding the lowest cost paths
• Work
with wild card mask.
• An
OSPF network can be divided into sub-domains called areas. An area
is a logical collection of OSPF networks, routers, and links that have
the same area identification. A router within an area must
maintain a topological database for the area to which it belongs
• A
logical collection of OSPF
• Routers
• Networks
• Links
• Have
the same Area identification
• Each
OSPF router must keep the LSA of every other routers in its LSDB.
• Each
router in a large OSPF AS has large LSDB.
• Must
Maintain a Topologies Database for the Area to which it belongs.
• Doesn’t
have detailed information about network topology outside of its area.
• Reducing
the size of its Database.
• Each
OSPF network that is divided into different areas must follow some rules.
• Each
non-backbone area must be directly connected to the backbone area.
• The
backbone area must not be partitioned or divided into smaller pieces – under
any failure conditions, such as links or router downs.
The link-state advertisement (LSA)
is a basic communication means of the OSPF routing protocol for the
IP. It communicates the router's local routing topology to all other local
routers in the same OSPF area.
LSAs are held in memory in the LSDB.
LSAs are identified by-
>>
OSPF Router-ID of advertising router
>>
LSA sequence number.
>>
An age in seconds- how much old is this LSA.
Types of LSA
• Router
LSA
• Network
LSA
• Area
summery LSA
• ASBR
LSA
• External
LSA type 1
• External
LSA type 2
The name of OSPF data base. LSDB store all links information
to reach in any network and also network state like a map in same AS.
LSU (Link State Updates)
Link State Update (LSU) packets are OSPF packet
Type 4. These packets implement the flooding of LSAs. Each LSA contains
routing, metric and topology information to describe a portion of OSPF network.
The local router advertises one or more LSAs within an LSU packet
to its neighboring routers.
OSPF Working and operation
• Neighbor
relationship
• OSPF
First establish neighbor relationship with that router which also have OSPF
configured. Provide foundation for all continuing OSPF communications.
• Must
match before of Routers Become neighbor
• Same
subnet number and subnet mask used
• Hello
interval
• Dead
interval
• Same
OSPF area ID
• Must
pass authentication checks
• Database
exchange
• Once
neighbor relationship establish than router exchange their LSDBs.
• Route
calculation
• Router
uses the Dijkstra Shortest Path First (SPF) algorithm to calculate best routes.
Add those to the routing table.
• In
this message these all info are share with neighbor router.
• Routers
add their neighbor Router ID in List of Neighbor.
• Using
this info all router knows that they are now neighbors.
• After
this routers start next process like exchange LSAs and define best route.
• Hello
messages send regularly according to hello interval.
• Using
hello process routers find new route if they not receive hello messages from
neighbor. (In any failure condition).
• Used
by ISPs
• An
exterior Routing protocol.
• Routing
between AS.
• Routing
protocol of Internet.
• Very
big organizations can use BGP.
• Having
two or more internet connections (known as multi homing).
• Upgrade
version of EGP.
• BGPv4
since 1994 which support CIDR.
• It
is a path vector routing protocol which
work like Distance vector. Path vector decisions based on Path, Network
policies, Rules.
• It
has very complex & Big metric.
• Slowest
but reliable.
BGP terminology
Ø BGP
peers and peering
Ø BGP
neighbors are known as BGP peers.
Ø When
BGP router exchange routes with another BGP speaking device (BGP peering).
Ø Established
by manual configuration
Ø BGB
AS
Ø Group
of routers
Ø Share
similar routing policies
Ø Operates
within a single administrative domain
Ø Typically
belongs to one organization
Ø It
can be between 1 to 65535
Ø IANA
& RIRs (Regional Internet Registries-AfriNIC, APNIC (Network Information
Centre, RIPE…)
• iBGP
• Neighbor
that belong to same AS
• These
neighbors need not to be directly connected.
• eBGP
• Neighbors
that belong to different AS.
• Neighbor
need to be directly connected.
• There
is 128 bit address means
• = 340,282,366,920,938,463,374,607,431,770,000,000
address
• Written
in hexadecimal
• Where
are first 64bit for different type of network and last 64bit for host
(interface ID).
fe80:0000:0000:0000:8110:6757:a147:78a1
Or fe80::8110:6757:a147:78a1
• 8
group of hexadecimal character.
There are two rule for IPv6
• All
0 (zero) can present by “::” as above.
But we can use :: only once.
• Starting
all 0 (zero) of every group.
fe80:0000:0000:0000:8110:0007:0005:78a1
Or fe80::8110:7:5:78a1
• Unicast
(site local/one to one) three types-
Ø Global
address (like public IP of IPv4)
Start with 2 or 3.
Ø Link
local (Similar to APIPA)
Start with fe80:: (Device always get link local even DHCP
provide IP)
Ø Unique
local address (Similar to private address of IPv4)
Always start with FD00::
• Multicast
(one to many)
Always start with FF
• Any
cast (One to any)
Nearest one that not predefine.
Note: loopback address
::1(only One Ip reserve)
#ipv6 enable
#ipv6 address 2000::1/64
Ticks-delay on a data link using IBM PC clock ticks
(approximately 55 milliseconds or 1/18 sec.)
Load- Amount of activity on a network resource, such as
router or link.
Reliability- usually refers to the bit-error rate of each
network link.
Maintaining Routing Information
Routing information is required to be maintained whenever
there is a change in the topology. In such a case routing table updates must
occur. The fig, given below shows how routers maintain them with the topology
change.
Problems during Routers
Maintenance
- Routing
loops
- In-consistence
routing-due to slow convergence
- Inconsistent
path
- Counting
to infinity
- Existence
of alternate routes
- Slow
convergence of information
Figure given below helps us to understand this concept more
clearly:
In the figure given, Network 1 goes
down. Just before the failure of Network 1,all the routers (A, B, C, D, E) have
consistent knowledge and correct routing table. The network is said to have
converged. The metric used here is hop count. Router E is directly connected to
Network 1 with a hop count of 0.Router C’s path to the Network is through
Router E via Router B or Router D and then Router A and E, with a hop count of 3.
When Network 1 fails, Router E detects
the failure and stops routing packets out its interface E0. Router E informs
Router A for failure. Router A also sends the failure message to Router B and D.
Before failure notification could reach router C, router C informs router D
that Network 1 is accessible with a hop count of 4.Router A now informs router
E that Network 1 is accessible via router D with a hop count of 5.
Because routers A, B, C, D and E
believe that best path to Network 1is through each other, the packet destined
to Network 1 continue to bounce between the five routers.
Thus the invalid updates about the
Network 1 continue to loop. This condition, called counting to infinity,
continuously loops packets around the network, despite the fundamental fact that
Network 1 is down.
The figure given below shows that,
the distance vector of hop count increments each times the packet passes
through another router. These packets loop through the network because of wrong
information in the routing tables.
After seeing the problem of routing
loop we come to the solutions of it. Given below is the counter measures used
by distance vector routing protocols to prevent routing loops from running
indefinitely.
Solution 1 Maximum Metric Settings
Routing loops occur due to counting
to infinity. We can solve this problem by defining a maximum hop count.
Distance vector routing protocol (RIP) permits a hop count of up to 15 hops,
therefore any packet requiring 16 hop counts will be considered unreachable.
Solution 2 Split Horizon
The simple rule of split horizon is
that the interface receiving the information is not allowed to send back the
information out from the same interface
Thus this could prevent Router A from
sending update message back to Router E
Solution 3 Route Poisoning
With the help of route poisoning,
router keeps an entry for the network down state. Route poisoning is used with
hold down timer to prevent routing loops.
Solution 4 Hold-Down Timer
Hold down timer prevent regular
update message from reinstating a route that has gone down. Thus, when
hold-down timer is set routers ignore network update information for some
period.
Solution 5 Triggered Update
As the name suggest, triggered update
is a method of sending a new routing table immediately as soon as topology
change is noticed .Not only the detecting route but all the adjacent routers
generate triggered updates notifying their neighbors of the change.
Link state routing Protocol
Link state protocol builds a routing
table based on topology database. This database is build from link state
packets that are passed between all the routers to describe the state of a
network. The database is finally used by shortest path first algorithm to build
the routing table.
The figure given below shows how
routing table is prepared using topology database.
Using link state routing protocols,
routers exchange topology database in parallel and each router prepares its own
routing table using SPF algorithm.
Balanced Hybrid
Balanced hybrid routing protocol uses
distance vectors with more accurate metrics to determine the best path to
destination networks.
The balanced hybrid protocol
converges more rapidally, like the link state protocol. These protocols are
more economical to use, as they consume less memory, bandwidth and processor.
E.g. Cisco’s Enhanced Interior
Gateway Routing Protocol(EIGRP)
Following are the features of RIP:
·
Type of protocol-Distance vector
·
Metric-hop count
·
Maximum allowable hop count-15
·
Broadcast of routing update-30 sec.
·
Load-balance-can load balance over as many as
six equal-cost paths (four paths by default)
Configuration steps:
Router(config)#router rip
Router(config-router)#network
<network address>
Commands to verify RIP information
Router#sh ip protocol
Router#sh ip route
Router#sh running-config
Router#debug ip rip
IGRP
IGRP is an advanced distance-vector
routing protocol developed by cisco in the mid-1980s. Following is the features
of IGRP:
·
Increased scalability
RIP has 15-hop limit. Whereas IGRP
has a default maximum hop count of 100 hops, which can be configured to a
maximum of 255 hops.
·
Sophisticated metrics
IGRP uses composite metric. Delay and
bandwidth are the default metric. Optionally; reliability, load and MTU can be
included in the metric.
·
Multiple path support
IGRP can maintain up to six unequal
cost paths between a network source and destination. Multiple paths can be used
to increase available bandwidth or for route redundancy.
Configuration Steps:
Router(config)#router igrp
<autonomous-system>
Router(config-router)#network
<network address>
Autonomous System-
IGRP requires an autonomous system
number. The autonomous system number does not have to be registered. However,
all routers within an autonomous system must use the same autonomous system
number.
Command to verify IGRP routing
information
Router#sh ip protocols
Router#sh ip route
Router#debug ip igrp transactions
Router#debug ip igrp events
0 Comments