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.
Group Management Protocol
Detects if a LAN has any members for a particular group if not then prune shortest path tree for that group by telling parent. Router periodically broadcasts a query message which hosts reply to with the list of groups that they are interested in. To surpress traffic: reply after random timeout, broadcast reply, if someone else has expressed interest in a group, drop out. In order to receive multicast packs: translate from class D to MAC and configure adapter.
Simplest solution for Wide Area Multicast
Flood packets from source to entire network. If router has not seen packet before then forward to all interfaces except incoming one. Pros - simply & always works (big plus)
Cons - routers receive duplicate packets, detecting that a packet is a duplicate requires storage which can be expensive for long muliticast sessions.
Reverse Path Forwarding
Forward packet from S to all interfaces iff packet arrives on interface that corresponds to the shortest path to S, then no need to remember past packets. Inefficient tandem routes then not sent down = win.
Clever Addition to RPF
Don’t send packet downstream if you are not on the shortest path from downstream router to the source.
Pruning
RPF doesn’t completely eliminate unnecessary transmissions. Pruning allows routers to tell parents in tree to stop forwarding. Can be associated with either a multicast group or with both a source and group.
Rejoining
Allows nodes to rejoin after a previous prune.
Distance-Vector Multicast Routing Protocol
Uses hop count distance vector routing to find shortest paths only taking multicast-capable routers into account. Uses flood-and prune to determine memberships, reverse-path forward to decide where to forward a packet and explicit join messages to reduce join latency.
Multicast Extension to Open Shortest Path First
Routers flood group membership information with link state packets. Each router independently computes shortest-path tree that only includes multicast-capable routers so no need to flood and prune. But complex as needs interaction with external and summary records, needs storage per group and per link. Additionally, need to compute shortest path tree per source and group.
Core-based trees
Coordinate multicast with a core router; the host sends request to core router; routers along path mark incoming interface for forward.
Pros of CBT approach
Routers not part of a group are not involved in routing.
Explicit join/leave makes membership changes faster.
Router only needs to store one record per group.
Cons of CBT approach
All multicast traffic traverses core which is a bottle neck and traffic travels on non-optimal paths.
Protocol Independent Multicast
Choose different strategies depending on whether multicast tree is dense or sparse. Flood and prune is good for dense groups as only needs a few prunes whole CBT needs explicit join per source/group. Dense Mode PIM == DVMRP. Sparse mode PIM like CBT but receivers can switch from CBT to a shortest-path tree.
