Routes Flashcards
What is routing?
Process of finding a path from a source to every destination in the network.
What does a routing protocol do?
A routing protocol sets up a routing table in routers and switch controllers. This requires reouters knowing something about global state but this is inherently large, dynamic and hard to collect. A routing protocol must intelligently summarize relevant information.
Requirements for a Routing Protocol
Minimize routing table space so it is fast to look up and there’s less to exchange.
Minimize number and frequency of control messages.
Robustness - must avoid black holes, loops and oscillations.
Use optimal path.
Choices in Routing
Centralized vs distributed routing - centralized simpler but failure prone.
Source-based vs. hop-by-hop: how much in packet header?
Stochastic vs deterministric - stochastic speads load, avoiding oscillations but misorders
Single vs multiple pathj
State-deend vs state-independent
Telephone Network Routing Algorithm
If endpoints are within same CO, directly connect.
If call is between COs in same LEC, use one-hop path between COs.
Otherwise send call to one of the cores.
One-hop or two-hop path is taken to destination toll switch. Only decision which two-hop path should be used if one-hop path is full.
Feature of Telephone Nework Routing
Stable load - can predict pairwise load throughout the day and can predict pairwise load throughout the day and choose optimal routes in advance.
Extremely reliable switches so can assume that a chosen route is available.
Single organisation controls entire core so can collect global statistics and implement global changes.
Statistics of telephone network
Poisson call arrival (independence assumption)
Exponential call “holding” time.
Dynamic nonhierachical routing
Divide day into 10-periods in each period each toll switch is assigned a primary one-hop pah and a list of alternatives and can overflow to if needed. Drop only if all alternate paths are busy.
Real-time network routing
No centralised control instead each toll switch maintains a list of lightly loaded links. Intersection of source and destination lists gives sets of lightly loaded paths e.g. at A list is C, D, E => links AC, AD, AE are lightly loaded, AT B list is D, F, G => BD, BF, BG lightly loaded, A asks B for list their intersection is then ADB being lightly loaded so good alternative path.
Dynamic Alternative Routing
Whenever the link (i,j) is saturated, use an alternative (tandem) node. Fixed tandem - use fixed node k as tandem. Inflexible during breakdowns and unexpected tandem traffic plus needs careful traffic analysis and reprogramming.
Sticky Random Tandem
If no free circuit along (i,j) then new call routed through randomly chosen tandem k. k is tandem as long as it does not fail. If k fails for call then call is lost and new tandem selected. Decentralised, flexible, no pre-analysis, friendly tandems are used most of the time.
Trunk Reservation
Unselfishness is good only up to appoint so we need to penalise two links calls when the lines are very busy. Tandem k accepts to forward calls only if it has free capacity more than r.
Extensions to Dynamic Alternative Routing
n-link paths:
Consumes too many resources w/ little benefit.
Multiple Alternatives - M attempts before rejecting a call.
Least-busy alternative
Repacking - allow in-progress call to be rerouted.
Requirements for Intra-AS Routing
Must scale for the size of an autonomous system.
High end - must converge quickly after topology changes. Self-configuring but has operator hooks for control.
Low end - can tolerate some disruptions. Simple and self-configuring.
Requirements for Inter-AS Routing
Must scale to size of global internet.
Reachability > Optimality
Address aggregation techniques minimise core routing table sizes and associated control traffic.
Must allow flexibility in topological structure.
Also allow policy-based routing between ASs. Fully distributed routing is only possibly.
Source Based Routing
Source gets a map of the network and finds route then signals the route setup or encodes route into packets.
Link-state routing
Per-link information. Gets map of network at all nodes and finds next hops locally.
Distance Vector
At every node, set up distance signposts to destination nodes. Setup this by peeking at neighbours signposts.
Consistency Criterion
The subset of a shortest path is also the shortest path between the two intermediate nodes.
Corollary: If the shortest path from node i to node j with distance D(i,j) passes through neighbour k with link cost c(i,k) then D(i,j) = c(i,k) + D(k,j).
Distance Vector
Takes Bellman-Ford algorithm approach and evaluates recursion iteratively.
In the mth iteration, the consistency criterion holds, assuming that each node sees all nodes and links m-hops away from it.
Link State
Look up as revision session.
Minimum Hop Routing
Set all link costs to one.
Capacity Routing
Give links weight proportional to capacity.
Arpanet Dynamic Metric
Cost proportional to length of router queue but independent of link capacity. This causes lots of problem when network is loaded e.g. transient spikes cause major rerouting, queue length assumed to predict future loads when the opposite is in face true, no restriction on successively reported costs, all tables compute simultaneously.
