---
id: wiki-2026-0508-network-coordinate-systems
title: Network Coordinate Systems
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [NCS, Vivaldi, network coordinates, latency embedding]
duplicate_of: none
source_trust_level: A
confidence_score: 0.9
verification_status: applied
tags: [networking, distributed-systems, latency, p2p]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: Go/Rust
  framework: HashiCorp Serf, libp2p
---

# Network Coordinate Systems

## 매 한 줄
> **"매 host 를 매 low-dim Euclidean space 의 점으로 embed 하여 매 RTT 를 매 distance 로 predict"**. 매 2004 MIT Vivaldi paper 가 매 seminal — 매 N×N RTT measurement 의 O(N²) 폭발 의 회피. 매 2026 service mesh / CDN edge selection / P2P overlay 의 매 building block.

## 매 핵심

### 매 motivation
- 매 N node 매 mesh 의 매 N² RTT probe = 매 1000 node = 1M probe.
- 매 NCS: 매 O(N) coordinate update 로 매 any pair 의 RTT predict.
- 매 update 매 lazy — 매 gossip / piggyback 매 existing message.

### 매 Vivaldi (대표 algorithm)
- 매 spring relaxation: 매 measured RTT 와 매 predicted distance 의 error 가 매 force.
- 매 height vector h: 매 access link latency 의 capture (Euclidean 의 X 인 매 last-mile).
- 매 dim 5-7 차 + height 1 차: 매 internet topology 의 충분한 fit.

### 매 응용
1. CDN edge selection (Cloudflare Argo).
2. Service mesh locality routing (HashiCorp Consul).
3. P2P overlay neighbor selection (libp2p).
4. Cluster placement (Kubernetes topology-aware).

## 💻 패턴

### 1. Vivaldi update step (Go-style)
```go
type Coord struct {
    Vec    []float64 // 8-dim
    Height float64
    Error  float64   // local confidence
}

const Cc, Ce = 0.25, 0.25

func (a *Coord) Update(b *Coord, rttSeconds float64) {
    predicted := dist(a, b)
    relErr := math.Abs(predicted-rttSeconds) / rttSeconds
    w := a.Error / (a.Error + b.Error)
    a.Error = relErr*Ce*w + a.Error*(1-Ce*w)

    delta := Cc * w
    direction := unitVec(sub(a.Vec, b.Vec))
    force := (rttSeconds - predicted) * delta
    for i := range a.Vec {
        a.Vec[i] += direction[i] * force
    }
    a.Height = math.Max(0.001, a.Height+(rttSeconds-predicted)*delta*0.5)
}
```

### 2. Distance prediction
```go
func dist(a, b *Coord) float64 {
    sumSq := 0.0
    for i := range a.Vec {
        d := a.Vec[i] - b.Vec[i]
        sumSq += d * d
    }
    return math.Sqrt(sumSq) + a.Height + b.Height
}
```

### 3. Gossip-based update (Serf-style)
```go
// On every gossip message exchange:
func (s *Serf) onPing(peer Node, rtt time.Duration) {
    s.coord.Update(peer.Coord, rtt.Seconds())
    s.broadcast(s.coord)
}
```

### 4. Edge selection (CDN)
```go
func nearestEdge(client *Coord, edges []Edge) Edge {
    best := edges[0]
    bestDist := dist(client, best.Coord)
    for _, e := range edges[1:] {
        if d := dist(client, e.Coord); d < bestDist {
            best, bestDist = e, d
        }
    }
    return best
}
```

### 5. Confidence-weighted query
```go
func predictRTT(a, b *Coord) (float64, float64) {
    rtt := dist(a, b)
    confidence := 1.0 - math.Min(a.Error+b.Error, 1.0)
    return rtt, confidence
}
```

### 6. Pharos (hierarchical NCS)
```go
// Two-tier: global coord + cluster-local coord
type PharosCoord struct {
    Global  Coord  // inter-cluster
    Local   Coord  // intra-cluster
    Cluster string
}
```

## 매 결정 기준
| 상황 | Approach |
|---|---|
| < 50 nodes | Direct N² probe — NCS overkill |
| 50-10k nodes (mesh) | Vivaldi (HashiCorp Serf 매 default) |
| > 10k geo-distributed | Pharos (hierarchical) or HTRAE |
| Adversarial / Byzantine | Newton (outlier-resistant) |
| Edge selection only | Anycast + GeoIP 매 simpler |

**기본값**: Vivaldi 8-dim + height (Serf-compatible).

## 🔗 Graph
- 부모: [[Distributed Systems]]
- 응용: [[Service Mesh]]

## 🤖 LLM 활용
**언제**: 매 100+ node mesh 매 latency-aware routing/placement 가 필요. 매 RTT measurement 의 O(N²) 폭발 회피.
**언제 X**: 매 small cluster (< 50). 매 BGP anycast 매 충분한 단순 edge selection. 매 Byzantine adversary present.

## ❌ 안티패턴
- **Triangle inequality 의 violation 무시**: 매 internet 의 매 routing asymmetry 매 strict triangle 위반 — 매 height vector 매 partial 해결.
- **High-dim 매 사용**: 매 16+ dim 매 overfitting + 매 update cost 증가. 매 8 dim 매 sweet spot.
- **Cold start 매 0 vector**: 매 random init 매 collapse 회피.
- **Confidence 무시**: 매 fresh node 의 coord 매 unreliable — 매 Error field 매 weight 사용.

## 🧪 검증 / 중복
- Verified (Vivaldi: Dabek et al., SIGCOMM 2004; HashiCorp Serf source 2026-05).
- 신뢰도 A.

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 |
| 2026-05-10 | Manual cleanup — Vivaldi spring-relaxation + Serf 의 production usage |
