Routing Algorithm
Routing Algorithm
Routing is accomplished by means of routing protocols that establish mutually consistent routing tables in every router in the Network. A routing protocol written in the form of code is routing algorithm. A routing algorithm asynchronously updates routing tables at every router or switch controller. The global information to be maintained by routing tables is voluminous. Routing algorithm summarizes this information to extract only the portions relevant to each node. The heart of routing algorithm does all the chores. The various concepts for discussion are:
· Design goals of Routing Algorithm
· Factors that decide the best Path
· Choices in Routing
Algorithms Used
· Flooding
· Hot-Potato
· Source Routing
· Distance Vector (Bellman-Ford)
· RIP (Routing Information Protocol)
· Link state
· Flooding
Every incoming packet is sent out on every other link by every router. Super simple to implement, but generates lots of redundant packets. Interesting to note that all routes are discovered, including the optimal one, so this is robust and high performance (best path is found without being known ahead of time). Good when topology changes frequently (USENET example).
 |
Some means of controlling the expansion of packets is needed. It could try to ensure that each router only floods any given packet once. Could try to be a little more selective about what is forwarded and where. The station initiating a packet stores the distance of the destination in the submitted packet (or the largest distance in the network). Each node reduces the counter by one, and resubmits the packet to all the adjacent nodes (but not to the node from where it received the packet). Packets with counter 0 are discarded. The destination node doesn't resubmit the packet .
|
 |
| ||||||
| ||||||
| ||||||
 |
|
Hot - Potato Routing
Hot-potato routing, or deflection routing, the nodes of a network have no buffer to store packets in before they are moved on to their final predetermined destination. In normal routing situations, when multiple packets contend for a single outgoing channel, packets that are not buffered are dropped to avoid congestion. But in hot potato routing, each packet that is routed is constantly transferred until it reaches its final destination because the individual communication links can not support more than one packet at a time.
The packet is bounced around like a "hot-potato," sometimes moving further away from its destination because it has to keep moving through the network. This technique allows multiple packets to reach their destinations without being dropped. This is in contrast to "store and forward" routing where the network allows temporary storage at intermediate locations.
This is a simple and effective way to route packets in communication networks. In these networks, nodes have no buffer to store the messages in transit, thus causing the messages to move from node to node each time. In other words, the messages are treated like hot potatoes.
Hot-potato routing is used for the following applications:
Real Networks
Immediate applications
Optical Networks
Hot potato routing has applications in optical networks where messages made from light can not be stored in any medium.
Non-optical networks
We obtain cheaper and easier to build networks, since nodes are simpler without buffers.
Source Routing
Source Routing is a technique whereby the sender of a packet can specify the route that a packet should take through the network. As a packet travels through the network, each router will examine the "destination IP address" and choose the next hop to forward the packet to. In source routing, the "source" (i.e. the sender) makes some or all of these decisions.
In strict source routing, the sender specifies the exact route the packet must take. This is virtually never used.
The more common form is loose source record route (LSRR), in which the sender gives one or more hops that the packet must go through. In high-level terms, it may look like:
To : A
From : D
Via : T
Source routing is used for the following purposes:
Mapping the network
Used with trace route in order to find all the routes between points on the network.
Troubleshooting
Trying to figure out from point "A" why machines "F" and "L" cannot talk with each other.
Performance
A network manager might decide to force an alternate link (such as a satellite connection) that is slower, but avoids congesting the correct routes.
Hacking
LSRR can be used in a number of ways for hacking purposes. Sometimes machines will be on the Internet, but will not be reachable. (It may be using a private address like 10.0.0.1). However, there may be some other machine that is reachable to both sides that forwards packets. Someone can then reach that private machine from the Internet by source routing through that intermediate machine.
Distance Vector
(Also known as Bellman-Ford or Ford-Fulkerson)
The heart of this algorithm is the routing table maintained by each router. The table has an entry for every other router in the subnet, with two pieces of information: the link to take to get to the router, and the estimated distance from the router. For a router A with two outgoing links L1, L2, and a total of four routers in the network, the routing table might look like this:
| Router | Distance | link |
| B | 5 | L1 |
| C | 7 | L1 |
| D | 2 | L2 |
Neighboring nodes in the subnet exchange their tables periodically to update each other on the state of the subnet (which makes this a dynamic algorithm). If a neighbor claims to have a path to a node which is shorter than your path, you start using that neighbor as the route to that node. Notice that you don't actually know the route the neighbor thinks is shorter - you trust his estimate and start sending packets that way.
HARDWARE AND SOFTWARE REQUIREMENTS
HARDWARE REQUIREMENTS
PROCESSOR : Intel 2.0 GHz or above
HARD DISK : 80 GB
RAM : 512 MB RAM.
SOFTWARE REQUIREMENTS
OPERATING SYSTEM : WINDOWS XP with SP2.
LANGUAGE (FRONT END) : JAVA (JDK1.5/1.6)
TECHNOLOGY : APPLETS, EVENT HANDLING, SWINGS.
ARCHITECTURE : 2-TIER ARCHITECTUR
No comments:
Post a Comment