Diamond-Miner: Comprehensive Discovery of the Internet’s Topology Diamonds

0 Abstract

本論文提出可以高速probing的multipath discovery system
- multipath: 拓樸中有load-balanced paths也可以偵測
透過實驗發現網路的拓樸改變，有不少部分是因為load balancer remapping造成，而不是像以往認為的都是routing path改變所導致

由於high probing load/runtime, 現有的probing只能獲得比較high-level的網路拓樸
- 因為傳統作法是stateful的，透過BFS找multipath，所以probing overhead很高
D-Miner透過統計推論load-balancer的output-degree
- probing: stateless, high-speed
- 推論: stateful, 存resolved/unresolved nodes

Load Balancing
- Determistic LB
  - per-flow / per-dest.
  - 輸出路徑： packet header(src/dst ip/port)給router hash func.計算
- Non-determistic LB (少見)
  - per-packet
  - 輸出路徑： switch round-robin
Multipath Detection Algorithm(MDA)
- traceroute 的multipath版，可以走遍所有的load-balanced path
- Stopping point: 用統計的方法，推論一個node該送多少個不同packet，才能決定該node的outgoing edges #
  - e.g. 若送$n_1=6$個header不同的packet，他的next hop都送到相同node，就可說有95%的機率這個node只有一條outgoing edge
- 問題： Sequential execution, 無法直接用在Internet上，僅能作為performance參考
Yarrp
- 高速且隨機probing的系統, stateless

1st round probe: 看Architecture流程
- D-Miner要自己另外紀錄node state
  - D-Miner extracts the data from each Yarrp reply
- sends $n_1 = 6$ probes per /24, each with a different flow identifier
  - 6 first destinations in the /24
  - per-destination-prefix load balanced paths
Subsequent probing round
- 計算還需要幾個probing，才能滿足每個node的statistical guarantees
- - $h:$ TTL
  - $R_h:$ Set of nodes discovered at TTL h that have not been resolved yet
  - $D_h:$ Probability distribution of nodes responding for TTL h after the current probing round
  - $k_v:$ number of successors for node v
  - $t_h:$ number of probes already sent at TTL h
  - $n_k:$ MDA stopping point
- addtional probes: 增加上一輪last destination IP addr
- Group the additional probes by flow
Per-packet LB
- D-Miner sends 2 back-to-back probes per flow, until it reaches a defined threshold probability that the branching point is NOT a per packet LB

Probe Changes
- 很多都是因load balancer remapping, 不一定是routing path changes
Load-Balancer Remapping
- 至少一條通往子孫的edge仍在set中:
  - $E_i ∩ E_{i+1} \neq 0$
  - 經驗，無法證明