Routes

Question 1

What is routing?

Answer 1

Process of finding a path from a source to every destination in the network.

Question 2

What does a routing protocol do?

Answer 2

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.

Question 3

Requirements for a Routing Protocol

Answer 3

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.

Question 4

Choices in Routing

Answer 4

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

Question 5

Telephone Network Routing Algorithm

Answer 5

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.

Question 6

Feature of Telephone Nework Routing

Answer 6

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.

Question 7

Statistics of telephone network

Answer 7

Poisson call arrival (independence assumption)

Exponential call “holding” time.

Question 8

Dynamic nonhierachical routing

Answer 8

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.

Question 9

Real-time network routing

Answer 9

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.

Question 10

Dynamic Alternative Routing

Answer 10

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.

Question 11

Sticky Random Tandem

Answer 11

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.

Question 12

Trunk Reservation

Answer 12

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.

Question 13

Extensions to Dynamic Alternative Routing

Answer 13

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.

Question 14

Requirements for Intra-AS Routing

Answer 14

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.

Question 15

Requirements for Inter-AS Routing

Answer 15

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.

Question 16

Source Based Routing

Answer 16

Source gets a map of the network and finds route then signals the route setup or encodes route into packets.

Question 17

Link-state routing

Answer 17

Per-link information. Gets map of network at all nodes and finds next hops locally.

Question 18

Distance Vector

Answer 18

At every node, set up distance signposts to destination nodes. Setup this by peeking at neighbours signposts.

Question 19

Consistency Criterion

Answer 19

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).

Question 20

Distance Vector

Answer 20

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.

Question 21

Link State

Answer 21

Look up as revision session.

Question 22

Minimum Hop Routing

Answer 22

Set all link costs to one.

Question 23

Capacity Routing

Answer 23

Give links weight proportional to capacity.

Question 24

Arpanet Dynamic Metric

Answer 24

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.

Question 25

Group Management Protocol

Answer 25

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.

Question 26

Simplest solution for Wide Area Multicast

Answer 26

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.

Question 27

Reverse Path Forwarding

Answer 27

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.

Question 28

Clever Addition to RPF

Answer 28

Don’t send packet downstream if you are not on the shortest path from downstream router to the source.

Question 29

Pruning

Answer 29

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.

Question 30

Rejoining

Answer 30

Allows nodes to rejoin after a previous prune.

Question 31

Distance-Vector Multicast Routing Protocol

Answer 31

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.

Question 32

Multicast Extension to Open Shortest Path First

Answer 32

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.

Question 33

Core-based trees

Answer 33

Coordinate multicast with a core router; the host sends request to core router; routers along path mark incoming interface for forward.

Question 34

Pros of CBT approach

Answer 34

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.

Question 35

Cons of CBT approach

Answer 35

All multicast traffic traverses core which is a bottle neck and traffic travels on non-optimal paths.

Question 36

Protocol Independent Multicast

Answer 36

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.