student will be able to understand the detailed
path determination process. Web Links Routing Basics
http://www.ictglobal.com/ICT009/ routing_basics.html
Content 10.2 IP Routing Protocols
10.2.5 Routing tables Routers use routing
protocols to build and maintain routing tables that contain
route information. This aids in the process of path
determination. Routing protocols fill routing tables with a
variety of route information. This information varies depending
on the routing protocol used. Routing tables contain the
information necessary to forward data packets across connected
networks. Layer 3 devices interconnect broadcast domains or
LANs. A hierarchical addressing scheme is required for data
transfer to occur. Routers keep track of important information
in their routing tables, including the following:
- Protocol type The type of routing protocol that
created the routing table entry
- Destination/next-hop associations These
associations tell a router that a particular destination is
either directly connected to the router, or that it can be
reached using another router called the next-hop on the way
to the final destination. When a router receives an incoming
packet, it checks the destination address and attempts to match
this address with a routing table entry.
- Routing
metric Different routing protocols use different routing
metrics. Routing metrics are used to determine the desirability
of a route. For example, the Routing Information Protocol (RIP)
uses hop count as its only routing metric. Interior Gateway
Routing Protocol (IGRP) uses a combination of bandwidth, load,
delay, and reliability metrics to create a composite metric
value.
- Outbound interfaces The interface
that the data must be sent out on, in order to reach the final
destination.
Routers communicate with one another
to maintain their routing tables through the transmission of
routing update messages. Some routing protocols transmit update
messages periodically, while others send them only when there
are changes in the network topology. Some protocols transmit
the entire routing table in each update message, and some
transmit only routes that have changed. By analyzing the
routing updates from the neighboring routers, a router builds
and maintains its routing table. Web Links Routing
Tables http://www.pku.edu.cn/academic/research/
computer-center/ tc/html/ TC0310.html
Content
10.2 IP Routing Protocols
10.2.6 Routing algorithms and metrics An algorithm
is a detailed solution to a problem. In the case of routing
packets, different routing protocols use different algorithms
to decide which port an incoming packet should be sent to.
Routing algorithms depend on metrics to make these decisions.
Routing protocols often have one or more of the following
design goals: - Optimization Optimization
describes the capability of the routing algorithm to select the
best route. The route will depend on the metrics and metric
weightings used in the calculation. For example, one algorithm
may use both hop count and delay metrics, but may consider
delay metrics as more important in the calculation.
- Simplicity and low overhead The simpler the
algorithm, the more efficiently it will be processed by the CPU
and memory in the router. This is important so that the network
can scale to large proportions, such as the Internet.
- Robustness and stability A routing algorithm
should perform correctly when confronted by unusual or
unforeseen circumstances, such as hardware failures, high load
conditions, and implementation errors.
- Flexibility A routing algorithm should quickly
adapt to a variety of network changes. These changes include
router availability, router memory, changes in bandwidth, and
network delay.
- Rapid convergence Convergence
is the process of agreement by all routers on available routes.
When a network event causes changes in router availability,
updates are needed to reestablish network connectivity. Routing
algorithms that converge slowly can cause data to be
undeliverable.
Routing algorithms use different
metrics to determine the best route. Each routing algorithm
interprets what is best in its own way. The routing algorithm
generates a number, called the metric value, for each path
through the network. Sophisticated routing algorithms base
route selection on multiple metrics, combining them in a single
composite metric value. Typically, smaller metric values
indicate preferred paths. Metrics can be based on a single
characteristic of a path, or can be calculated based on several
characteristics. The following are the metrics that are most
commonly used by routing protocols: - Bandwidth
The data capacity of a link. Normally, a 10-Mbps Ethernet link
is preferable to a 64-kbps leased line.
- Delay
The length of time required to move a packet along each link
from source to destination. Delay depends on the bandwidth of
intermediate links, the amount of data that can be temporarily
stored at each router, network congestion, and physical
distance.
- Load The amount of activity on a
network resource such as a router or a link.
- Reliability Usually a reference to the error rate
of each network link.
- Hop count The number
of routers that a packet must travel through before reaching
its destination. Each router the data must pass through is
equal to one hop. A path that has a hop count of four indicates
that data traveling along that path would have to pass through
four routers before reaching its final destination. If multiple
paths are available to a destination, the path with the least
number of hops is preferred.
- Ticks The delay
on a data link using IBM PC clock ticks. One tick is
approximately 1/18 second.
- Cost An arbitrary
value, usually based on bandwidth, monetary expense, or other
measurement, that is assigned by a network administrator.
Web Links Routing Algorithms
http://www.cisco.com/univercd/cc/td/doc/ cisintwk/ito_doc/
routing.htm#xtocid6
Content 10.2
IP Routing Protocols 10.2.7 IGP and EGP An
autonomous system is a network or set of networks under common
administrative control, such as the cisco.com domain. An
autonomous system consists of routers that present a consistent
view of routing to the external world. Two families of routing
protocols are Interior Gateway Protocols (IGPs) and Exterior
Gateway Protocols (EGPs). IGPs route data within an autonomous
system. - Routing Information Protocol (RIP) and (RIPv2)
- Interior Gateway Routing Protocol (IGRP)
- Enhanced Interior Gateway Routing Protocol (EIGRP)
- Open Shortest Path First (OSPF)
- Intermediate
System-to-Intermediate System protocol (IS-IS)
EGPs
route data between autonomous systems. An example of an EGP is
Border Gateway Protocol (BGP). Web Links What IP Routing
Protocol Should I Use? http://www.faqs.org/faqs/
cisco-networking-faq/ section-28.html
Content
10.2 IP Routing Protocols
10.2.8 Link state and distance vector Routing
protocols can be classified as either IGPs or EGPs, which
describes whether a group of routers is under a single
administration or not. IGPs can be further categorized as
either distance-vector or link-state protocols. The
distance-vector routing approach determines the distance and
direction, vector, to any link in the internetwork. The
distance may be the hop count to the link. Routers using
distance-vector algorithms send all or part of their routing
table entries to adjacent routers on a periodic basis. This
happens even if there are no changes in the network. By
receiving a routing update, a router can verify all the known
routes and make changes to its routing table. This process is