Hi,
The two main types of routing algorithms used for directing network
traffic are all dynamic in nature in that they are constntly updating
based on new address information. I excerpted some of the content,
but I suggest you visit the linked sites for a good primer on these
algorithms.
The main types of dynamic algorithms are introduced at at:
[ http://computer.howstuffworks.com/routing-algorithm1.htm ]
"Based on how routers gather information about the structure of a
network and their analysis of information to specify the best route,
we have two major routing algorithms: global routing algorithms and
decentralized routing algorithms. In decentralized routing algorithms,
each router has information about the routers it is directly connected
to -- it doesn't know about every router in the network. These
algorithms are also known as DV (distance vector) algorithms. In
global routing algorithms, every router has complete information about
all other routers in the network and the traffic status of the
network. These algorithms are also known as LS (link state)
algorithms."
"Link state" algorithms are further discussed at:
[ http://computer.howstuffworks.com/routing-algorithm2.htm ]
"In LS algorithms, every router has to follow these steps:
Identify the routers that are physically connected to them and get
their IP addresses
When a router starts working, it first sends a "HELLO" packet over
network. Each router that receives this packet replies with a message
that contains its IP address.
Measure the delay time (or any other important parameters of the
network, such as average traffic) for neighbor routers
In order to do that, routers send echo packets over the network. Every
router that receives these packets replies with an echo reply packet.
By dividing round trip time by 2, routers can count the delay time.
(Round trip time is a measure of the current delay on a network, found
by timing a packet bounced off some remote host.) Note that this time
includes both transmission and processing times -- the time it takes
the packets to reach the destination and the time it takes the
receiver to process it and reply.
Broadcast its information over the network for other routers and
receive the other routers' information
In this step, all routers share their knowledge and broadcast their
information to each other. In this way, every router can know the
structure and status of the network.
Using an appropriate algorithm, identify the best route between two
nodes of the network
In this step, routers choose the best route to every node. They do
this using an algorithm, such as the Dijkstra shortest path algorithm.
In this algorithm, a router, based on information that has been
collected from other routers, builds a graph of the network. This
graph shows the location of routers in the network and their links to
each other. Every link is labeled with a number called the weight or
cost. This number is a function of delay time, average traffic, and
sometimes simply the number of hops between nodes. For example, if
there are two links between a node and a destination, the router
chooses the link with the lowest weight. "
Distance vector algorithms are discussed at:
[ http://computer.howstuffworks.com/routing-algorithm4.htm ]
"DV algorithms are also known as Bellman-Ford routing algorithms and
Ford-Fulkerson routing algorithms. In these algorithms, every router
has a routing table that shows it the best route for any destination.
"
"
Here are some other links that you will likely find useful:
Understanding Routing Protocols
[ http://www.oreillynet.com/pub/a/network/2001/05/22/net_2nd_lang.html ]
Routing 101: Routing Algorithms
[ http://www.samspublishing.com/articles/article.asp?p=27267 ]
I trust this has answered your question satisfactorily. If you
require a clarification, please request one, especially before rating
this answer. Thank you for bringing your question to Google Answers!
Regards,
Andrewxmp |
