Notes - Routing Algorithms

The following are notes from Computer Networks written by Tanenbaum 5th edition.

• The routing algorithm decides which output line an incoming packet should be transmitted on
• VC if a virtual circuit is set up then it is called session routing
• routing is enforced for entire session
• Router
• Forwarding handles the packets as it arrives sends to outgoing line
• responsible for filling in and updating routing tables
• algorithm should have
• correctness
• simplicity
• robustness
• stability - reaches equilibrium and tries to stay there
• fairness - fairly distributing packets
• efficiency - minimizing traffic, increasing speed
• Nonadaptive algorithms
• do not base their routing decisions on measurements or topology
• choice computed in advanced offline and downloaded to routers when network booted
• Adaptive algorithms
• change to reflect changes in topology
• dynamic routing differ when traffic changes

The Optimality Principle

• creation of sink tree
• tree rooted at destination
• paths from one router I to router K, can be joined be joined with a path from J to K if A and B converge to the same router for example C sometime before reaching router K
• reasoning
• since these two are similar in distance, since I found a path thats optimal to K that loops around close to J, the time/number of hops from J won't be similar in length
• convergence of optimal paths

• DAG(Directed Acyclic Graph)
• allows all paths to be chosen
• other sink trees may exist
• still no looping
• assume paths don't interfere with one another
• does not contain loops
• links and routers can go up and down during operation, current topology in question
• benchmark for routing algorithms

Shortest Path Algorithm

• computing optimal paths with complete picture of network

• path length shortest
• in number of hops
• in physical distance
• bandwidth 
• average traffic
• communication cost
• delay of standardized packet
• all used as "edges" which is the time in between two points/routers
• dijkstra's path algorithm
• idea is to examine all nodes adjacent to a source node
• then find the smallest label and travel to that new node 
• store in a table
• from new node repeat until all nodes are visited, and all distances found

Flooding

• when routing is implemented, router based on local knowledge
• to gain a picture overall, we can use flooding, every incoming packet is sent on every outgoing except the one it arrived on
• this packet generated just goes through the entire system, called flooding
• flooding is not practical, but ensures a packet is sent to every node in a network
• extremely robust, flooding will find a way to get a packet to its destination
• flooding always gets the shortest path but generates many redundant packets, extremely energy and bandwidth inefficient

Distance Vector Routing

• Dynamic routing algorithms are more complex than flooding, but they find shortest paths for current topology
• Distance Vector Routing
• each router maintains a table giving the best known distance to each destination, which outgoing link to use for given destination
• Bellman-Ford routing algorithm
• Original ARPANET routing algorithm
• contains one entry for each router in the network

The Count-to-Infinity Problem

• Settling of routes to best paths is called convergence
• Distance vector routing has issue in that it may converge to right answer, but its slow
• bad news reaction is extremely slow
• if router disconnected, the neighbors that use the disconnected router will not realize
• for example, if c and b are routed through d to connect to e, if d is removed 
• initially
• c will tell its neighbors to route through d
• b will tell its neighbors to route through d
• c discovers that d is missing, asks for an update from neighbors
• b will tell c a route that may pass through d
• the fact that its routing through d is hidden from c
• c updates, but doesn't know there is an error
• b discovers d is missing asks from update from neighbors
• b learns from c new path
• c's current path incorporates b's old broken path, even though it looks updated
• b route is still broken
• this loop can continue indefinitely, to infinity
• solve this by enforcing a limit on the number of hops a packet can take
• instead of infinity replace with longest path length +1
• heuristics in general don't work well, due to entire path information being hidden

Link State Routing

• Distance Vector Routing was primary choice in ARPANET until 1979 until it was replaced by link state routing
• link state routing
• IS-IS (Intermediate System - Intermediate System)
• OSPF (Open Shortest Path First)
• idea is that a router can build a table by
• discovering its neighbors and learning their network addresses
• set the distance between its neighbors
• construct a packet with the information of what it learned
• send and receive this packet
• compute the shortest path to every other router
• complete topology sent to every router, Dijkstra's run at each router
• Learning about the Neighbors
• router first learns who its neighbors are
• sends special Hello packet to each point to point line
• when two or more routers are connect by a broadcast link such as a switch, or ring more complicated
• consider LANs as nodes instead of each point within the LAN
• Setting Link Costs
• costs are inversely proportional to bandwidth of the link
• determine delay with echo packet that is required to be sent back immediately, measure round trip time at senders computer
• Building Link State Packets
• Once information found, send packet with all the data
• identity of sender followed by sequence number and age and list of neighbors
• difficulty is determining when to build these, usually periodically or when a change to topology happens, line or neighbor going up or down
• Distributing the Link State Packets
• distributing the link state packets quickly and reliably
• distribution algorithm
• use flooding algorithm to send packets
• each packet has sequence number that gets incremented, so only forwards new link state packets, not old ones or duplicates
• lower number packets get dropped
• if sequence number wraps around, possibility for confusion
• if router crashes can lose track of sequence number
• corruption can cause deletion
• refinements can make it more robust
• put packets in buffer for small timeframe, for comparison before transmitting
• duplicates are discarded, older ones thrown out
• when new arrives, forward buffer and store new packet in buffer

• Computing the New Routes
• once router has full set of link packets, construct the entire network graph
• Dijkstra's algorithm run locally
• link state routing requires more memory and computation, grows faster than kn where k is neighbors, n is number of routers
• IS-IS or OSPF are protocols that include stabilization
• IS-IS carries information about multiple network layer protocols
• All these rely on processing at routers
• if router fails, or does bad calculations, issues arise
• limite damage of router failures

Hierarchical Routing

• As network grows in size, routing tables grow as well
• Current network size of globe, impossible to calculate in reasonable amount of time before changes to topology occur
• hierarchical routing used, divide routers into regions, shortest path calculations done only within region
• To communicate in between regions
• each region has a main hub
• user sends packet to main hub
• transfer to next main hub
• hubs may have own routing procedure, hub to hub
• check if hub is correct
• if arrived at correct hub, then send packet shortest path from hub to destination

Broadcast Routing

• distribute message to many or all other hosts
• called broadcast
• requires no special features for each destination, its very wasteful in bandwidth
• Multidestination routing
• each packet contains list of destination
• router checks if its a destination, if yes accept
• if not drop and creates a new packet with non visited destinations
• flooding is a broadcast technique
• Reverse Path forwarding
• broadcast packet arrives at router, it checks to see if it arrived at link normally used for sending packet
• if yes then sends packets towards the source of the broadcast, since its using the shortest path to communicate with hub its likely the first to arrive at router
• sends copy to every other line hub has contact with
• if the copy is already visited then drop
• repeats
• end result, steps through from hub to every other point hub connects too one hop at a time
• Spanning Tree
• subset of network that includes all the routers but no loops
• since it has no loops and connects to all nodes, just send along spanning tree
• problem is that each router must know the spanning tree, so possible with link state routing but not distance vector

Multicast Routing

• Multicast routing
• send a packet to multiple receivers
• routing algorithm multicast routing
• requires a way to create and destroy group, and identify which routers are part of a group
• defined by multicast address
• send packets along spanning tree
• Broadcast over multicast
• if group is dense, with receivers making up a good portion of the network efficiently sent
• if group is sparse, inefficient
• also packets may be private to group
• Create a multicast spanning tree specific to the group
• MOSPF(Multicast OSPF)
• Distance Vector Routing
• different pruning strategy
• prune message, instead of creating a tree, have original tree and send a prune packet to remove itself from list for that particular multicast
• DVMRP(Distance Vector Multicast Routing protocol)
• a lot of work for routers
• Core-based tree
• routers agree on route/rendezvous point
• send packet to core, core distributes multicast
• less efficient, but core can be a more powerful computational unit
• core based trees are useful for multicasting in sparse groups
• PIM(Protocol Independent Multicast)

Anycast Routing

• so far above covers unicast/broadcast
• unicast is one destination
• Packet is delivered to nearest member of a group
• sometimes specific nodes provide service
• Both link state, and distance vector already create paths for anycast

Routing for Mobile Hosts

• Mobile hosts
• home location means that routing location doesn't change until power is off
• mobile moves around
• must recompute routes as it moves
• very computation intensive
• find nearby fixed location, route from there
• Laptops
• when move to new location, new network addresses provided, don't care about old address
• this doesn't allow for hosts to send packets to it
• i.e. skype disallowed every time we move location
• better to find host, the home agent to act on behalf of the mobile host
• mobile gets local network address from a nearby hub/access point
• local address called care of address
• sender sends data packet to mobile
• data packet to mobile host by routing to home location, then encapsulates the packet and sends it to local care address
• called tunneling
• mobile host unwraps it and retrieves packet, then sends directly to sender
• overall route is called triangle routing
• there are some purely mobile networks
• inside airplane
• some use remote agent, at forward location
• VLR(Visitor Location Register)
• often not needed now

Routing in Ad Hoc Networks

• Ad Hoc Networks or MANETs(Mobile Ad hoc NETworks)
• nodes can come or go, vanish and appear in different locations
• fastest topology changes
• routing algorithms
• AODV (Ad hoc On-demand Distance Vector)
• Route Discovery
• destination discovered on demand
• use distance vector routing only when somebody wants to send a packet to destination
• if no packet do not update
• Route Request packet
• broadcast to anything in range, send ack to original
• each node packet was sent to sends to everything it can reach, checking to see if anything has been sent to it with same name
• ack to original
• finds new nodes
• once node found Route reply packet sent back reversed along the path that was used to send to it
• these packets have time to live, or count the number of hops until it won't be sent
• that way if destination disconnect, or no longer exists, packets won't continue on forever
• Route Maintenance
• algorithm must account for rapid changes
• hello message, each node sends to its neighbors, if neighbor not available
• updates routing table, purges all routes that depend on that unavailable neighbor
• senders find new routing
• how Distance vector routing is slow to converge
• routes include sequence number controlled by destination, that decrement with fresh route reply
• basic idea only accept fresh route request commands and current information
• old information times itself out
• DSR(Dynamic Source Routing)
• if all nodes know geographic position, simply forward in the geographic direction only

Back to ToC