Routing

Front 1

routing vs switching

Back 1

In switching packets are transfered from source to destination using MAC address. Switching is done within the network.Whereas Router routes between the network. Routing is a process which is done between two networks using IP addresses.basically routing is a intelligent switching

Front 2

what do routers do

Back 2

Routers connect networks together at the network layer and are responsiblefor moving datagrams (routing) from one link to another.

Front 3

what is the goal of a routing algorithm ?

Back 3

The goal of a routing algorithm is to figure out a good path, or route,for a datagram to take to get to its destination. By good, we meanan algorithm that will minimize the cost of the overall route. That cost may be eithertime (quickest route) or money (if there are financial costs that differ betweendifferent routes).

Front 4

connected graph,G = (N, E),

Back 4

N is the set of nodes (vertices) (routers, in real life) andE is the set of edges (links between the routers in real life).A connected graph is one where, given two nodes a and b, there is some pathfrom a to b.

Front 5

graph neighbor

Back 5

A node y is considered to bea neighbor of node x if the edge (x, y) exists in the graph. That is,(x, y) ∈ E.

Front 6

each edge has what value ?

Back 6

Each edge has associated with it a value that represents the cost of the link.We represent the cost of an edge between nodes x and y as c(x, y). Ifthere is no edge (x, y) in the graph then the cost c(x, y) is infinite (∞).

Front 7

c(x, y)

Back 7

We represent the cost of an edge between nodes x and y as c(x, y). c(x ,y) = c(y, x)

Front 8

cost of a path

Back 8

the sum of theedge costs. Since there may be multiple paths from one nodeto another, one or more ofthese will be a least-cost path.If all edges have the same cost, that least-cost path will also be the shortest path.

Front 9

two types of routing algorithms

Back 9

global routing algorithm, decentralized routing algorithm

Front 10

decentralized routing algorithm

Back 10

no node has complete knowledge of alllinks in the graph. A node initially knows only about its direct links.Through an iterative process of exchanging lists of nodes and costs with itsneighbors, a node will eventually compute the least-cost path to any destination in the graph.The distance-vector (DV) algorithm is an example of a decentralized routing algorithm.

Front 11

example of decentralized routing algorithm

Back 11

The distance-vector (DV) algorithm is an example of a decentralized routing algorithm.

Front 12

global routing algorithm

Back 12

relies on complete knowledge of the network graph. The algorithm, as input, knowsthe connectivity graph: all the nodes and edges.

Front 13

examples of global routing algorithm

Back 13

Dijkstra’s shortest path algorithm is an example of an LS algorithm

Front 14

global routing algorithm AKA

Back 14

Algorithms in this category are known as link-state (LS)algorithms.

Front 15

In an implementation of Dijkstra’s shortest path algorithm, what will each node need to do ?

Back 15

In an implementation, eachnode will need to broadcast any link change information to every other node so thatall nodes will have an identical and complete view of the network.

Front 16

the Dijkstra's algorithmstores:

Back 16

a list of nodes in the graph. for each node, it stores

D(v): the distance, our current knowledge of the least cost path to get to node v.

p(v): the previous node before node v along the least cost path that we have so far.

Front 17

how to iterate through ijkstra's algorithm

Back 17

see drive

Front 18

what happens in an environment where link costs vary to reflect the current traffic volume on the link?

Back 18

the lowest-cost paths will favor uncongested links.

Front 19

Oscillations

Back 19

When the algorithm is re-run (after finding lowest cost link), lowest-cost routes will now be recomputed to be the formerly high-costroutes since we channeled traffic away from them. As the new routing table is used, we will seethe same phenomenon happen again as traffic is shifted to what used to be low-volume links.This results in oscillations between network routes each time the LS algorithm is re-run.The best approach to avoiding these oscillations is to have routers run their LS algorithm atrandom times rather than all at the same time.

Front 20

how to best avoid oscillations

Back 20

The best approach to avoiding these oscillations is to have routers run their LS algorithm atrandom times rather than all at the same time.

Front 21

distance vector

Back 21

A node n’s distance vector is a list of costs from n that each other node in the graph.Unknown costs are infinity. Each cost is considered to be an estimate as it may be based onincomplete data. Eventually, the algorithm converges and the costs become true least-cost values.In the DV algorithm, a node sends its distance vector to its neighboring nodes.

Front 22

In the DV algorithm, who does each node communicate with ?

Back 22

In the DV algorithm, a node sends its distance vector to its neighboring nodes.

Front 23

distance vector table

Back 23

A node also keeps a distance vector table. This is a set of distance vectors that it has receivedfrom its neighbors. These distance vectors are used to allow a node to check whether it is moreefficient to have a route that goes through a specific neighbor, m, than the node it currentlythinks is the next hop on the shortest path.

Front 24

in the distance vector algorithm what does each node keep ?

Back 24

a distance vector and a distance vector table.

Front 25

how to do Distance Vector algorithm

Back 25

all the nodes have a list (distance vector) of potential distances to other nodes. (a list of [node,distance] tuples).

when node receives a new distance vector from a neighbor, add the distance from the neighbor to the current node and add that to the distance for each node in the new nodes distance vector. if that value is smaller than what is in the current (node, distance) tuple, replace it with new number.