CPSC 3600 - DAY 15
MARCH 27, 2017

================================================================================

			WAN TECHNOLOGIES AND DYNAMIC ROUTING
			------------------------------------

A WAN can be formed by interconnecting packet switch among sites.  

The interconnection and the capacity can be chosen to accommodate the expected
traffic and provide redundancy in the case of failure.

WAN addresses follow hierarchial addressing.

Conceptual hierarchial addressing divides each address into two-level hierarchy
(site, computer at the site)

In practice, one packet switch per site and K connections for local computers
means the address hierarchy is:
(packet switch, local connection on the switch)

Although we think of the address as a pair of integers, an address is
represented as a single binary value.

Initial bits represent a packet switch number and the remaining bits identify a
computer.

NEXT-HOP FORWARDING
-------------------

Each packet contains a destination address

Forwarding uses only the packet switch portion of an address, while delivery
uses the rest of the address.

If packet has reached the destination packet switch, it will be delivered to 
locally-connected computer

Otherwise, it will be forwarded to another packet switch closer to the
destination site.

To make the computation efficient, packet switches use table lookup.

Forwarding table lists all possible packet switches and gives a next hop for
each.

CONSTRUCTING A FORWARDING TABLE
-------------------------------

Static routing - entries inserted when system boots and do not change.

Dynamic routing - initial entries inserted when system boots. Routing software
continually monitors network, computes shortest paths, and updates the 
forwarding table.

ROUTING SOFTWARE
----------------

Runs on each packet switch or router

Computes shortest path and installs entries in local forwarding table

Models the network as a graph

DYNAMIC ROUTING
---------------

Goals:
	consistent, optimal routes
	automatic route changes to accommodate failures.

Each node (packet switch or router) participates.

Routing software on a node exchanges information with routing software on other
nodes.

Distributed computation.

LINK STATE ROUTING (LSR)
------------------------

Each node:
	Sends link status information across the network
	Computes shortest paths independently.
	Does not rely on computation performed by others

Name:
	Formal name is Link-State or Link-Status Routing
	Also called Shortest Path First (SPF), a somewhate misleading term
	derived from the underlying algorithm.

Each pair of directly-connected nodes periodically:

	Test connection between them.
	Broadcast one of the following messages across the network:
		The link between X and Y is up
		or
		The link between X and Y is down.
	Each node:
		collects incoming broadcast messages and creates a graph.
		Uses Dijkstra's SPF algorithm to compute a forwarding table.

DISTANCE-VECTOR ROUTING (DVR)
-----------------------------

Also known as Bellman Ford.

Unlike LSR, DVR arranges for a packet switch to send a complete list of 
destination and the current cost of reaching each.

Node:
	Receives information from neighbors.
	Combines information from all neighbors with local information.
	Sends copy of processed information to all neighbors.

A participant periodically sends route advertisement to each neighbor.

Each message contains pairs of (destination, distance).

Advertisement specifies reachable sites and distance to each.
	I can reach site X, and its distance from me is Y.
	I can reach site Z, and its distance from me is W.

Neighbor receives advertisement and updates its forwarding table.

The forwarding table maintains distance for each destination.

In the next round, neighbors send advertisements to their neighbors.

Examine ach item in advertiesement:
	If neighbor can reach site X and I cannot, add an entry to my	
	forwarding table for X with the neighbor as the next hop.

	If I already have a route to X with the neighbor as the next hop,
	replace the distance in the route with the advertised distance.

	If I have a route to X that is more expensive than going through the 
	neighbor, change the next hop to the neighbor.

	DVR will send everything in its table!