Routing Algorithms : Shortest Path Algorithm, Flodding, Distance Vector Routing, Link State Routing ; Protocols : ARP, RARP, IP, ICMP

Shortest Path Algorithm

Shortest path algorithm finds the shortest paths between routers/node in a graph. The widely used shortest path algorithm is Dijkstra's shortest path algorithm. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined.

Flooding

Flooding is a static routing algorithm, in which every incoming packet is sent out on every outgoing line except the one it arrived on. Flooding obviously generates vast numbers of duplicate packets, in fact, an infinite number unless some measures are taken to dump the process.

Distance Vector Routing

Distance vector routing operates by having each router maintain a table (i.e. a vector) giving the best-known distance to each destination and which line to use to get there. The distance vector routing algorithm passes periodic copies of a routing table from router to router. These regular updates between routers communicate topology changes. These tables are updated by exchanging information with the neighbors. The router is assumed to know the ''distance'' to each of its neighbors. If the metric is hops, the distance is just one hop. Metric may be delay time. It is also called Bellman-Ford routing algorithm.

Link State Routing

The link-state routing algorithm maintains a complex database of topology information. The routing algorithm maintains full knowledge of distant routers and how they interconnect. Each node maintains the full graph by collecting the updates from all other nodes. Each node then independently calculates the next best logical path from it to every possible destination in the network. Router's receive topology information from their neighbor router via link state advertisements(LSA).

ARP

Address Resolution Protocol (ARP) protocol is used to map the IP address to the MAC address. Sometimes it may happen that the source knows the IP address but not the Physical Address i.e. MAC address of the router. To find the destination address the router broadcast the IP address by asking what is the physical address of the router having this IP address ? Then the router matching the IP address reply back to the source by sending the MAC address.

RARP

Reverse Address Resolution Protocol (RARP) is used to map the MAC address to the IP address. It is just the reverse of the ARP. To find the destination address the router broadcast the MAC address by asking what is the logical address of the router having this MAC address ? Then the router matching the MAC address reply back to the source by sending the IP address.

IP

Internet Protocol (IP) is the principle protocol in the internet communication.It is the set of rules/method by which the data is transfer from one computer to the other computer through the internet.

ICMP

ICMP (Internet Control Message Protocol) is the widely used network protocol. It is used to send the error message for example, that a requested service is not available or that a host or router could not be reached. It can also be used to relay query messages.ICMP differs from transport protocols such as TCP and UDP in that it is not typically used to exchange data between systems, nor is it regularly employed by end-user network applications (with the exception of some diagnostic tools like ping and traceroute).

Reference :

1. Tanenbaum, WetherRall, Andrew S. David J. Computer Networks. 5th ed. Boston : Pearson Education, Inc.
2. http://www.csee.umbc.edu/~zhan/Sp97/481/notes/5.html
3. http://www.slideshare.net/ergauravrawat/computer-network-30833122
4. W. Stallings, “Data and Computer Communication”, Macmillan Press, 1989.
5. Kurose Ross, “Computer Networking: A top-down approach”, 2nd Edition, Pearson Education
6. Larry L. Peterson, Bruce S. Davie, “Computer Networks: A Systems Approach”, 3rd Edition, Morgan Kaufmann Publishers