| Topic : Network Routing and Switching |
|
|
|
||
|
Activity:
1 comments
568 views
last activity : 07 06 2010 20:18:04 +0000
|
||
|
|
Routing Algorithms
Routing algorithms can be differentiated based on several key characteristics. First, the particular goals of the algorithm designer affect the operation of the resulting routing protocol. Second, various types of routing algorithms exist, and each algorithm has a different impact on network and router resources. Finally, routing algorithms use a variety of metrics that affect calculation of optimal routes. The following sections analyze these routing algorithm attributes.Design Goals
Routing algorithms often have one or more of the following design goals: • Optimality • Simplicity and low overhead • Robustness and stability • Rapid convergence • Flexibility Optimality refers to the capability of the routing algorithm to select the best route, which depends on the metrics and metric weightings used to make the calculation. For example, one routing algorithm may use a number of hops and delays, but it may weigh delay more heavily in the calculation. Naturally, routing protocols must define their metric calculation algorithms strictly. Routing algorithms also are designed to be as simple as possible. In other words, the routing algorithm must offer its functionality efficiently, with a minimum of software and utilization overhead. Efficiency is particularly important when the software implementing the routing algorithm must run on a computer with limited physical resources. Routing algorithms must be robust, which means that they should perform correctly inthe face of unusual or unforeseen circumstances, such as hardware failures, high load conditions, and incorrect implementations. Because routers are located at network junction points, they can cause considerable problems when they fail. The best routing algorithms are often those that have withstood the test of time and that have proven stable under a variety of network conditions.
In addition, routing algorithms must converge rapidly. Convergence is the process of agreement, by all routers, on optimal routes. When a network event causes routes to either go down or become available, routers distribute routing update messages that permeate networks, stimulating recalculation of optimal routes and eventually causing all routers to agree on these routes. Routing algorithms that converge slowly can cause routing loops or network outages.
Algorithm Types
Routing algorithms can be classified by type. Key differentiators include these: • Static versus dynamic • Single-path versus multipath • Flat versus hierarchical • Host-intelligent versus router-intelligent • Intradomain versus interdomain • Link-state versus distance vectorStatic Versus Dynamic
Static routing algorithms are hardly algorithms at all, but are table mappings established by the network administrator before the beginning of routing. These mappings do not change unless the network administrator alters them. Algorithms that use static routes are simple to design and work well in environments where network traffic is relatively predictable and where network design is relatively simple. Because static routing systems cannot react to network changes, they generally are considered unsuitable for today's large, constantly changing networks. Most of the dominant routing algorithms today are dynamic routing algorithms, which adjust to changing network circumstances by analyzing incoming routing update messages. If the message indicates that a network change has occurred, the routing software recalculates routes and sends out new routing update messages. These messages permeate the network, stimulating routers to rerun their algorithms and change their routing tables accordingly. Dynamic routing algorithms can be supplemented with static routes where appropriate. A router of last resort (a router to which all unroutable packets are sent), for example, can be designated to act as a repository for all unroutable packets, ensuring that all messages are at least handled in some way.Single-Path Versus Multipath
Some sophisticated routing protocols support multiple paths to the same destination. Unlike single-path algorithms, these multipath algorithms permit traffic multiplexing over multiple lines. The advantages of multipath algorithms are obvious: They can provide substantially better throughput and reliability. This is generally called load sharing.Flat Versus Hierarchical
Some routing algorithms operate in a flat space, while others use routing hierarchies. In a flat routing system, the routers are peers of all others. In a hierarchical routing system, some routers form what amounts to a routing backbone. Packets from nonbackbone routers travel to the backbone routers, where they are sent through the backbone until they reach the general area of the destination. At this point, they travel from the last backbone router through one or more nonbackbone routers to the final destination. Routing systems often designate logical groups of nodes, called domains, autonomous systems, or areas. In hierarchical systems, some routers in a domain can communicate with routers in other domains, while others can communicate only with routers within their domain. In very large networks, additional hierarchical levels may exist, with routers at the highest hierarchical level forming the routing backbone. The primary advantage of hierarchical routing is that it mimics the organization of most companies and therefore supports their traffic patterns well. Most network communication occurs within small company groups (domains). Because intradomain routers need to know only about other routers within their domain, their routing algorithms can be simplified, and, depending on the routing algorithm being used, routing update traffic can be reduced accordingly.Host-Intelligent Versus Router-Intelligent
Some routing algorithms assume that the source end node will determine the entire route. This is usually referred to as source routing. In source-routing systems, routers merely act as store-and-forward devices, mindlessly sending the packet to the next stop. Other algorithms assume that hosts know nothing about routes. In these algorithms, routers determine the path through the internetwork based on their own calculations. In the first system, the hosts have the routing intelligence. In the latter system, routers have the routing intelligence.Intradomain Versus Interdomain
Some routing algorithms work only within domains; others work within and between domains. The nature of these two algorithm types is different. It stands to reason, therefore, that an optimal intradomain-routing algorithm would not necessarily be an optimal interdomain-routing algorithm.Link-State Versus Distance Vector
Link-state algorithms (also known as shortest path first algorithms) flood routing information to all nodes in the internetwork. Each router, however, sends only the portion of the routing table that describes the state of its own links. In link-state algorithms, each router builds a picture of the entire network in its routing tables. Distance vector algorithms (also known as Bellman-Ford algorithms) call for each router to send all or some portion of its routing table, but only to its neighbors. In essence, link-state algorithms send small updates everywhere, while distance vector algorithms send larger updates only to neighboring routers. Distance vector algorithms know only about their neighbors.Because they converge more quickly, link-state algorithms are somewhat less prone to routing loops than distance vector algorithms. On the other hand, link-state algorithms require more CPU power and memory than distance vector algorithms. Link-state algorithms, therefore, can be more expensive to implement and support. Link-state protocols are generally more scalable than distance vector protocols.
1 comments on "Routing Algorithms "
Sort by:
Most Recent
Top Rated
Commented by
Hardik Patel, Team Lead (Staffing and Recruitment), Rishabh Softwares Pvt. Ltd. / Rishi Infotech Pvt. Ltd
| 07 23 2008 07:50:44 +0000
Report Abuse
Not Rated
Found the article
"Routing Algorithms "
interesting ?
Share with your connections and communities
Leaders in Social Media Recruitment
- Create a confidential Career Profile and Resume/C.V. online
- Get advice for planning their career and for marketing of experience and skills
- Maximize awareness of and access to the best career opportunities
Viewers also viewed
|
|
ROUTE MAPS.. TO ANYWHERE,EVERYWHERE. AMAZING ! VERY USEFUL. Hats off to whoever made this. ... |
|
|
851 referals
7 comments,
188 views
|
|
|
There is a new approach that one will be seeing interms of Roads getting developed in the... |
|
|
244 referals
14 arguments,
387 views
|
|
|
"India must focus on quality,ethics" India must concentrate on quality as much as on everything... |
|
|
15 referals
5 arguments,
217 views
|
|
|
|
|
|
|
Recent Knowledge (85)
|
|
|
World IP Day, 26 April: "The Power of Ideas as the seedbed for innovation and creativity" "World... |
|
|
4 referals
1 comments,
217 views
|
|
|
We know that Ecommerce is the most happening trend of the day. After the emergence of ecommrce,... |
|
|
109 referals
1 comments,
53 views
|
|
|
Yes they are going to be here.. and the first destination is Bangalore... Google cars and trikes... |
|
|
1339 referals
12 comments,
443 views
|
|
|
|
|
|
|
Sponsored Jobs
More From Author
it is now became imp in it industry |
Yes! I support your words |