Routing Principles - Revision history

Rscheffler at 16:35, 30 July 2007

2007-07-30T16:35:38Z

← Older revision		Revision as of 16:35, 30 July 2007
Line 170:		Line 170:
	Using distance vector routing in ad-hoc networks is problematic because of the rapid topology changes and the fact that mobile networks use a broadcast instead of a point-to-point medium, so the standard loop-prevention techniques cannot be used.		Using distance vector routing in ad-hoc networks is problematic because of the rapid topology changes and the fact that mobile networks use a broadcast instead of a point-to-point medium, so the standard loop-prevention techniques cannot be used.
	The idea in DSDV is then to let each node number it's outgoing update packets to differentiate between new and stale routes. These '''sequence numbers''' get propagated through the route. Nodes can therefore discard updates with older numbers they receive.		The idea in DSDV is then to let each node number it's outgoing update packets to differentiate between new and stale routes. These '''sequence numbers''' get propagated through the route. Nodes can therefore discard updates with older numbers they receive.

			= Sources =
			* McQuillan, John M. et al. "The New Routing Algorithm for the ARPANET" (1980)
			* Perkins, Charles E. and Bhagwat, Pravin. "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers" (1994)
			* Distance Vector Routing: RIPv1 (RFC1058), RIPv2 (RFC2453)
			* [http://en.wikipedia.org/wiki/Bellman-ford Bellman-Ford algorithm at wikipedia.org]

Rscheffler: /* Distance Vector Routing */

2007-07-30T16:26:27Z

Distance Vector Routing

← Older revision		Revision as of 16:26, 30 July 2007
Line 68:		Line 68:

	= Distance Vector Routing =		= Distance Vector Routing =

			Distance Vector routing protocols use the Bellman-Ford algorithm to calculate the paths in the network. The first implementation was used in the ARPANET as early as 1969.

			Each node keeps a routing table with an entry for each destination in the network. This entry consists of the distance to the destination and the first hop on the path to the destination.
			Nodes inform their neighbours of their routing tables, so that they can update their own entries.

			== Bellman-Ford Algorithm ==

			The Bellman-Ford algorithm computes single-source shortest paths in a directed graph. Unlike Dijkstra's algorithm it is compatible with negative edge-weights.

			The basic idea is to repeatedly check each edge of the graph to determine if there is a shorter path (than the one already found) to the edge's destination by using the edge. Of course this has to be done often enough, so that the shortest path is found.

			The input of the Algorithm is a directed weighted graph G and a vertex of this graph as source. The algorithm computes the distances to all other vertices in three steps.

			'''procedure''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source)
			''// This implementation takes in a graph, represented as lists of vertices''
			''// and edges, and modifies the vertices so that their ''distance'' and''
			''//'' predecessor ''attributes store the shortest paths.''

			''// Step 1: Initialize graph''
			'''for each''' vertex v in vertices:
			'''if''' v '''is''' source '''then''' v.distance := 0
			'''else''' v.distance := '''infinity'''
			v.predecessor := '''null'''

			''// Step 2: relax edges repeatedly''
			'''for''' i '''from''' 1 '''to''' size(vertices):
			'''for each''' edge uv in edges:
			u := uv.source
			v := uv.destination ''// uv is the edge from u to v''
			'''if''' v.distance > u.distance + uv.weight:
			v.distance := u.distance + uv.weight
			v.predecessor := u

			''// Step 3: check for negative-weight cycles''
			'''for each''' edge uv in edges:
			u := uv.source
			v := uv.destination
			'''if''' v.distance > u.distance + uv.weight:
			'''error''' "Graph contains a negative-weight cycle"

			It can be proven that the algorithm always finds the shortest paths from the source to each node of the graph. The time needed is bound by O(n*m) where n is the number of vertices and m is the number of edges in the graph.

			== Routing Information Protocol ==

			RIP is an implementation of a distance vector routing protocol that was proposed in 1988 (RFC 1058). Later revisions include RIP2 (1994) and RIPng(1997).

			RIP uses a basic metric to measure the distance between nodes: The number of links to traverse (i.e. hops).

			The routing table entries in RIP consist of
			* Address: destination IP
			* Gateway: first hop on the path to the destination
			* Interface: hardware interface to use
			* Metric: number of hops to the destination
			* Timer: time of last update

			Each node of the network has to relay it's full routing table to each of it's neighbours regularly. If a node recieves an update it will compare the contained metric plus one to it's own stored metric and update the routing table if needed. If a node wants to send a packet to a destination it looks up the gateway in the routing table. The node has no need of full information about the topology of the network as it only cares about the first hop, i.e. who to send the packet to. The recieving gateway then refers to it's own routing table to determine the next hop and so on.

			=== Network Failures ===

			If a link or node in the network goes down, no further updates are send. After three update cycles have completed, without receiving routing information from another node it is considered dead. The routing table is updated to the metric ∞ (implemented by RIP as 16).
			Consider the case of three nodes in a line

			A ----- B ----- C

			The routing entries for C in the tables of A and B are as follows:

			Node Gateway to C #hops to C
			------------------------------
			A B 2
			B C 1

			If C goes down, B will update it's routing table accordingly.

			Node Gateway to C #hops to C
			------------------------------
			A B 2
			B ~ 16

			But at the same time A offers a route to C with the metric 2 that is clearly shorter than 16. B will therefore update it's entry to metric 3.

			Node Gateway to C #hops to C
			------------------------------
			A B 2
			B A 3

			This will cause A to update the metric to 4 and so on, until both nodes reach the maximum of 16. This problem is called '''Counting to Infinity''' and it is the reason for choosing 16 as the representation of ∞ in RIP. While A and B are counting to 16, packets are routed in a loop.


			To avoid this problem RIP implements '''Split Horizon'''. This means that nodes do not advertise routes to the nodes they have stored as gateways. '''Poisoned Reverse''' is an extension that causes nodes to advertise routes to the gateways with the metric ∞. This helps resolving loops in complex situations faster. But routing loops cannot be avoided altogether by RIP.

			== Border Gateway Protocol ==

			BGP is the de facto standard for routing between autonomous systems in the Internet. It is often referred to as a path vector protocol as the routing table entries contain the whole path to the destination and not only the first hop as in "true" distance vector routing protocols.
			The advantage is loop detection on the one hand and the possibility to implement policies at the nodes (meaning a node will prefer paths using certain nodes over others).

			== Destination-Sequenced Distance-Vector Routing ==

			DSDV is a proposition by C. Perkins and P. Bhagwat for using distance vector routing in mobile ad-hoc networks. The algorithm was presented in 1994, but it was never implemented.

			Using distance vector routing in ad-hoc networks is problematic because of the rapid topology changes and the fact that mobile networks use a broadcast instead of a point-to-point medium, so the standard loop-prevention techniques cannot be used.
			The idea in DSDV is then to let each node number it's outgoing update packets to differentiate between new and stale routes. These '''sequence numbers''' get propagated through the route. Nodes can therefore discard updates with older numbers they receive.

Elisa at 22:44, 21 July 2007

2007-07-21T22:44:42Z

@@ Line 33: / Line 33: @@
-Obviously the shortest path from A to D in this graph would be via C.
+Obviously the shortest path from A to D in this graph would be via C. Following the algorithm we would compute that as follows:
 == OSPF ==
 = Distance Vector Routing =

Elisa at 22:26, 21 July 2007

2007-07-21T22:26:46Z

← Older revision		Revision as of 22:26, 21 July 2007
Line 33:		Line 33:
	1		1

	Obviously the		Obviously the shortest path from A to D in this graph would be via C.

	== OSPF ==		== OSPF ==

Elisa at 21:54, 21 July 2007

2007-07-21T21:54:06Z

← Older revision		Revision as of 21:54, 21 July 2007
Line 1:		Line 1:
	= Networking =		= Networking Basics =

	Routing can be compared with the kind of routing we would do when we try to travel to another city by car. We need to figure out which way to take, we need to get a new route when something on our normal route is blocked, etc.		Routing can be compared with the kind of routing we would do when we try to travel to another city by car. We need to figure out which way to take, we need to get a new route when something on our normal route is blocked, etc.
Line 19:		Line 19:
	Every link between two nodes has costs, these can be configured as any metric at choice (eg. delay). Link state algorithms are based on global information, that means that every node knows all the other nodes (the whole network topology) and the link costs to them. Using Dijkstra's algorithm it then computes the least cost paths to all nodes other and store that information in the routing table.		Every link between two nodes has costs, these can be configured as any metric at choice (eg. delay). Link state algorithms are based on global information, that means that every node knows all the other nodes (the whole network topology) and the link costs to them. Using Dijkstra's algorithm it then computes the least cost paths to all nodes other and store that information in the routing table.

	To build the whole topology map each node first checks the links to its directly connected neighbors. Then it sends a so called '''link state advertisements''' through the network. ~~With~~ all the received advertisements each node can now compute the topology.		To build the whole topology map each node first checks the links to its directly connected neighbors. Then it sends a so called '''link state advertisements''' through the network with all the information about its neighbors. From all the received advertisements each node can now compute the topology.

	== Dijkstra's Algorithm ==		== Dijkstra's Algorithm ==

	To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.		To calculate the routing table from the computed topology map, link state protocols perform Dijkstra's '''shortest path first''' algorithm. In small graphs the shortest path (the one with the least costs) is easy to see, like in the graph below, but in more complex networks an algorithm is needed to compute it.

	3		3
Line 32:		Line 32:
	C-----D		C-----D
	1		1

			Obviously the

	== OSPF ==		== OSPF ==

Elisa at 00:10, 20 July 2007

2007-07-20T00:10:45Z

← Older revision		Revision as of 00:10, 20 July 2007
Line 1:		Line 1:
		⚫	= Networking =
	= Routing Principles =

⚫	== Networking ==

	Routing can be compared with the kind of routing we would do when we try to travel to another city by car. We need to figure out which way to take, we need to get a new route when something on our normal route is blocked, etc.		Routing can be compared with the kind of routing we would do when we try to travel to another city by car. We need to figure out which way to take, we need to get a new route when something on our normal route is blocked, etc.
Line 15:		Line 13:
	* Decentralized information, where the routers only know their directly connected neighbors and calculate their routing tables with a '''distance vector algorithm'''.		* Decentralized information, where the routers only know their directly connected neighbors and calculate their routing tables with a '''distance vector algorithm'''.

	== Link State Routing ==		= Link State Routing =

	Link state routing was invented by John McQuillan in 1978 and used in the early days of the ARPANET. Known protocols that implement link stare algorithms are OSPF or ISIS.		Link state routing was invented by John McQuillan in 1978 and used in the early days of the ARPANET. Known protocols that implement link stare algorithms are OSPF or ISIS.
Line 23:		Line 21:
	To build the whole topology map each node first checks the links to its directly connected neighbors. Then it sends a so called '''link state advertisements''' through the network. With all the received advertisements each node can now compute the topology.		To build the whole topology map each node first checks the links to its directly connected neighbors. Then it sends a so called '''link state advertisements''' through the network. With all the received advertisements each node can now compute the topology.

	=== Dijkstra's Algorithm ===		== Dijkstra's Algorithm ==

	To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.		To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.
Line 35:		Line 33:
	1		1

	=== OSPF ===		== OSPF ==

	== Distance Vector Routing ==		= Distance Vector Routing =

Elisa at 00:09, 20 July 2007

2007-07-20T00:09:38Z

← Older revision		Revision as of 00:09, 20 July 2007
Line 1:		Line 1:
	~~[[Image:Example.jpg]]~~= Routing Principles =		= Routing Principles =

	== Networking ==		== Networking ==
Line 26:		Line 26:

	To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.		To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.

			3
			A-----B
			\| \|
			2 \| \| 4
			\| \|
			C-----D
			1

	=== OSPF ===		=== OSPF ===

Elisa at 00:04, 20 July 2007

2007-07-20T00:04:06Z

← Older revision		Revision as of 00:04, 20 July 2007
Line 1:		Line 1:
	= Routing Principles =		[[Image:Example.jpg]]= Routing Principles =

	== Networking ==		== Networking ==
Line 26:		Line 26:

	To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.		To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.

	[[Image:Dijkstra.jpg]]

	=== OSPF ===		=== OSPF ===

Elisa at 00:02, 20 July 2007

2007-07-20T00:02:19Z

← Older revision		Revision as of 00:02, 20 July 2007
Line 26:		Line 26:

	To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.		To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.

			[[Image:Dijkstra.jpg]]

	=== OSPF ===		=== OSPF ===

Elisa at 23:45, 19 July 2007

2007-07-19T23:45:35Z

← Older revision		Revision as of 23:45, 19 July 2007
Line 5:		Line 5:
	Routing can be compared with the kind of routing we would do when we try to travel to another city by car. We need to figure out which way to take, we need to get a new route when something on our normal route is blocked, etc.		Routing can be compared with the kind of routing we would do when we try to travel to another city by car. We need to figure out which way to take, we need to get a new route when something on our normal route is blocked, etc.

	In computer networks routing is needed in lots of different situation. For example in a circuit switched network (like the phone network) a connection needs to be established at the beginning and it remains static till the end of the conversation. In a packed switched network (like the internet), each packet (chunk of information) gets routed seperately, so the decision which way to take needs to be performed way more often.		In computer networks routing is needed in lots of different situation. For example in a circuit switched network (like the phone network) a connection needs to be established at the beginning and it remains static till the end of the conversation. In a packed switched network (like the internet), each packet (chunk of information) gets routed seperately, so the decision which way to take needs to be performed way more often. This decision happens on special hardware, so called routers.

	Nodes in the network can be added or removed, therefore the routing needs to adjust dynamically to changes of the network topology. '''Routing algorithms''' calculate the ways we can take through a network on demand and save or update them to '''routing tables'''.		The routers build a topology map of the network where each router represents a node. Nodes in the network can be added or removed, therefore the routing needs to adjust dynamically to changes of the network topology. '''Routing algorithms''' calculate the ways we can take through a network on demand and save or update them to '''routing tables'''.

			Common routing protocols are based on two algorithms:
	We distinguish between 2 different types of routing:

	* Global information, where all routers know the whole topology of the network and calculate the routing tables with a '''link state algorithm'''.		* Global information, where all routers know the whole topology of the network and calculate the routing tables with a '''link state algorithm'''.

	* Decentralized information, where the routers only know their directly connected neighbors and calculate their routing tables with a '''distance vector algorithm'''.		* Decentralized information, where the routers only know their directly connected neighbors and calculate their routing tables with a '''distance vector algorithm'''.


	== Link State Routing ==		== Link State Routing ==

	Link state routing was invented by John McQuillan in 1978 and used in the early days of the ARPANET. Known protocols that implement link stare ~~routing~~ are OSPF or ISIS.		Link state routing was invented by John McQuillan in 1978 and used in the early days of the ARPANET. Known protocols that implement link stare algorithms are OSPF or ISIS.

	Link state algorithms are based on global information, that means that every node knows all the other nodes (the whole network topology) and the link costs to them. Using Dijkstra's algorithm it then computes the least cost paths to all nodes other and store that information in the routing table.		Every link between two nodes has costs, these can be configured as any metric at choice (eg. delay). Link state algorithms are based on global information, that means that every node knows all the other nodes (the whole network topology) and the link costs to them. Using Dijkstra's algorithm it then computes the least cost paths to all nodes other and store that information in the routing table.

			To build the whole topology map each node first checks the links to its directly connected neighbors. Then it sends a so called '''link state advertisements''' through the network. With all the received advertisements each node can now compute the topology.
	=== Dijkstra's algorithm ===

	=== ~~OSPF~~ ===		=== Dijkstra's Algorithm ===

			To calculate the routing table from the computed topology map link state protocols perform Dijkstra's '''shortest path first''' algorithm.

			=== OSPF ===

	== Distance Vector Routing ==		== Distance Vector Routing ==