DHT Scaling Formulations

# DHT Scaling Formulations ### DHT Traffic Sources - Node Role Clarification #### Maintenance Traffic - Generated by: All DHT participants (providers, clients) - Purpose: DHT network topology - e.g., routing tables - Scaling: Every node #### Content Traffic - Generated by: Provider nodes only (content pieces, e.g., storing data/parity slots in Codex) - Purpose: "I have CID_X" - Scaling: Proportional to number of providers $P$ and content pieces $C$ #### Query Traffic - Generated by: Any node needing content - Clients: Looking for content pieces to download - Providers: Retrieving content for erasure coding repair/(re)construction - Purpose: "Who has CID_X" - Scaling: Proportional to content demand \(Q) and usage patterns ### Network Topology ``` Total_Keys = N × Keys_per_Node × (1/K) N_min = (Total_Keys × K) / Keys_per_Node ``` where N = number of nodes, K = DHT replication factor ### Node Requirements ``` Churn_Rate ≈ 1 / Average_Node_Lifetime [node churn] Storage_per_Node = (Keys_per_Node × Key_Size) + (log₂(N) × Routing_Entry_Size) DHT_Maintenance_Bandwidth_Per_Node = c₂ × log₂(N) × α × Churn_Rate × Message_Size ``` where c₂ = Base + Retries + Redundancy + Churn_Handling ≈ 2-5 (maintenance factor) - Messages get lost → retransmissions (×1.5-2) - Stale routing info → extra hops (×1.2-1.5) - Parallel lookups for redundancy (×1.5-3) - Periodic maintenance even when stable (×1.2) ### Performance ``` Hops = c₁ × log₂(N) Lookup_Latency = (Hops / α_efficiency) × Network_Delay Query_Parallelism = α (typically 3) ``` where - c₁ = Base + Stale_Routes + Suboptimal_Choices + Bootstrap_Inefficiency + Churn_Recovery ≈ 1.5-2.0 (routing inefficiency factor) - α = 3 (parallel queries per lookup step) - α_efficiency ≈ 2.0 (latency reduction from parallelism) ## Traffic Formulation ### Core Variables - **C** = number of content pieces to index - **P** = average providers per content - **Q** = average queries per content piece per second - **N** = number of DHT nodes - **K** = DHT replication factor (typically 3-20) - **T** = update interval (provider refresh period, seconds) - **λ** = provider churn rate (providers joining/leaving per unit time) ### Content Traffic Components ``` Announcement_Rate = (C × P × λ) + (C × P / T) ``` `[new providers] + [periodic refreshes] = [churn + periodic]` ``` Messages_per_Update = log₂(N) × K ``` `[hops to reach responsible nodes] × [replication] = [routing overhead]` ``` Total_Updates_per_Second = Announcement_Rate × Messages_per_Update = [(C × P × λ) + (C × P / T)] × log₂(N) × K ``` ### Per-Node Load ``` Total_Updates_per_Node = (C × P × log₂(N) × K × α ×(λ + 1/T)) / N [updates/sec/node] Content_Bandwidth_per_Node = Total_Updates_per_Node × Message_Size [bytes/sec/node] Query_Load_per_Node = (C × Q × log₂(N) × α ×(1 + K)) / N [queries/sec/node] Query_Bandwidth_per_Node = Query_Load_per_Node × Message_Size [bytes/sec/node] Total_Bandwidth_per_Node = Content_Bandwidth + Query_Bandwidth + DHT_Maintenance_Bandwidth = (Total_Updates_per_Node × Message_Size) + (Query_Load_per_Node × Message_Size) + (c₂ × log₂(N) × Churn_Rate × Message_Size) ``` ## Practical Parameter Ranges | Parameter | Range | |-----------|-------| | Replication_Factor | 3-20 | | Message_Size | 100-500 bytes | | Churn_Rate | 0.001-0.01 per second | | Refresh_Interval | 1800-7200 seconds (0.5-2 hours) | | Providers_per_Content | 1-20 | | Keys_per_Node | 1K-1M | ## Example Calculation For a DHT with: - C = 10⁹ = 1 billion content pieces - P = 1 provider per piece - Q = 0.001 queries/piece/sec (1 query per piece per 17 minutes) - N = 250K DHT nodes - K = 8 replication factor - T = 3600 seconds (1 hour refresh) - λ = 0.001 churn rate (average provider lifetime ~ 17 min) - α = 3 (parallel queries per lookup step) - Message_Size = 200 bytes - Churn_Rate = 0.01 (Node rate) ``` Content Updates: Updates/sec = 10⁹ × 1 × log₂(250K) × 8 × 3 x (0.001 + 1/3600) = 10⁹ × 1 × 17.9 × 8 × 3 x 0.00128 = 549.9 million updates/sec total network = 2199.6 updates/sec per node Content_Bandwidth = 2199.6 × 200 bytes = 429.6 KiB/sec per node Query Traffic: Query_Load_per_Node = (10⁹ × 0.001 × 17.9 × 3 x 9) / 250K = 1933.2 queries/sec per node Query_Bandwidth = 1933.2 × 200 bytes = 377.57 KB/sec per node Maintenance Traffic: Maintenance_Bandwidth = c₂ × log₂(N) × α x Churn_Rate × Message_Size = 3 × 17.9 × 3 x 0.01 × 200 = 322.2 bytes/sec = 0.3 KB/sec per node Total Bandwidth: Total_Bandwidth = 429.6KiB + 377.57KiB + 0.3KiB = 807.47 KiB/sec per node Component Breakdown: - Content: 53.2% (429.6/807.47) - Query: 46.8% (377.57/807.47) - Maintenance: 0.04% (0.3/807.47) ``` # Codex DHT Bandwidth Analysis with Erasure Coding For Codex's erasure-coded storage system, the total bandwidth per node must include repair operations triggered by storage provider failures. The revised formula becomes: ``` Total_Bandwidth_per_Node = Content_Bandwidth + Query_Bandwidth + DHT_Maintenance_Bandwidth + Repair_Bandwidth ``` where ```Repair_Bandwidth = (C × M × λ × log₂(N) × K × α × Message_Size) / N [bytes/sec/node]``` ### Erasure Coding Configuration ``` P = K_EC + M_EC (total slots per content piece) K_EC = data slots M_EC = parity slots Total_Slots = K_EC + M_EC = providers per content piece ``` ### Modified DHT Parameters for Codex ``` C = 10⁹ content pieces (1 billion) P = K_EC + M_EC (providers per content piece) Q = average queries per content piece per second λ = 0.00005 (weekly contract churn) T = 7200s (2 hour refresh) K = 8 (DHT replication factor) α = 3 (parallelism factor) Message_Size = 200 bytes Churn_Rate = 0.01 ``` ## Complete Erasure Coding Matrices ### Scenario 1: Low Query Rate (Q = 0.0001 queries/piece/sec) *1 query per piece every ~2.8 hours* | Erasure Coding | Providers \(P) | 10K Nodes | 50K Nodes| 100K Nodes| 250K Nodes | 500K Nodes | 750K Nodes | 1M Nodes | |---------------|---------------|------------|------------|------------|------------|------------|------------|----------| | **(K=10, M=2)** | **P=12** | **Content**: 72,285/sec, 14,118.2 KiB/sec **Query**: 3,588/sec, 700.7 KiB/sec **Maintenance**: 1.20/sec, 0.23 KiB/sec **Repair**: 3,189/sec, 622.9 KiB/sec **Total**: 79,063/sec, **15,422.0 KiB/sec**|**Content**: 16,983/sec, 3,317.0 KiB/sec **Query**: 843/sec, 164.6 KiB/sec **Maintenance**: 1.40/sec, 0.27 KiB/sec **Repair**: 749/sec, 146.3 KiB/sec **Total**: 18,577/sec, **3,628.3 KiB/sec**| **Content**: 9.036/sec, 1764.8 KiB/sec **Query**: 448/sec, 87.6 KiB/sec **Maintenance**: 1.50/sec, 0.29 KiB/sec **Repair**: 399/sec, 77.9 KiB/sec **Total**: 9,884/sec, **1,930.5 KiB/sec**| **Content**: 3,900/sec, 744.0 KiB/sec **Query**: 195/sec, 38.1 KiB/sec **Maintenance**: 1.62/sec, 0.3 KiB/sec **Repair**: 215/sec, 42 KiB/sec **Total**: 4,472/sec, **824.4 KiB/sec**| **Content**: 2,064/sec, 392.7 KiB/sec **Query**: 96/sec, 18.9 KiB/sec **Maintenance**: 1.71/sec, 0.3 KiB/sec **Repair**: 114/sec, 22.2 KiB/sec **Total**: 2,445/sec, **434.1 KiB/sec** | **Content**: 1,419/sec, 277.14 KiB/sec **Query**: 66/sec, 12.6 KiB/sec **Maintenance**: 1.77/sec, 0.3 KiB/sec **Repair**: 78/sec, 15.2 KiB/sec **Total**: 1,740/sec, **297.5.7 KiB/sec** | **Content**: 1,086/sec, 208.2 KiB/sec **Query**: 48/sec, 9.3 KiB/sec **Maintenance**: 1.80/sec, 0.3 KiB/sec **Repair**: 60/sec, 11.7 KiB/sec **Total**: 1,374/sec, **229.5 KiB/sec** | **Content**: 3,900/sec, 744.0 KiB/sec **Query**: 195/sec, 38.1 KiB/sec **Maintenance**: 1.62/sec, 0.3 KiB/sec **Repair**: 215/sec, 42 KiB/sec **Total**: 4,472/sec, **824.4 KiB/sec** | | **(K=20, M=4)** | **P=24** | **Content**: 144,570/sec, 28,236.4 KiB/sec **Query**: 3,588/sec, 700.7 KiB/sec **Maintenance**: 1.20/sec, 0.23 KiB/sec **Repair**: 6,378/sec, 1,245.7 KiB/sec **Total**: 154,537/sec, 30,183.1 KiB/sec| **Content**: 33,967/sec, 6,634.1 KiB/sec **Query**: 843/sec, 164.6 KiB/sec **Maintenance**: 1.40/sec, 0.27 KiB/sec **Repair**: 1,499/sec, 292.7 KiB/sec **Total**: 36,309/sec, 7,091.7 KiB/sec| **Content**: 18,071/sec, 3,529.5 KiB/sec **Query**: 448/sec, 87.6 KiB/sec **Maintenance**: 1.49/sec, 0.29 KiB/sec **Repair**: 797/sec, 155.7 KiB/sec **Total**: 19,319/sec, 3,773.1 KiB/sec| **Content**: 7,803/sec, 1,488.2 KiB/sec **Query**: 195/sec, 38.1 KiB/sec **Maintenance**: 1.62/sec, 0.3 KiB/sec **Repair**: 861/sec, 168.1 KiB/sec **Total**: 9,021/sec, **1,694.7 KiB/sec** | **Content**: 4,128/sec, 788.1 KiB/sec **Query**: 96/sec, 18.9 KiB/sec **Maintenance**: 1.71/sec, 0.3 KiB/sec **Repair**: 454/sec, 88.7 KiB/sec **Total**: 4,849/sec, **896.0 KiB/sec** | **Content**: 2,838/sec, 541.2 KiB/sec **Query**: 66/sec, 12.6 KiB/sec **Maintenance**: 1.77/sec, 0.3 KiB/sec **Repair**: 312/sec, 61 KiB/sec **Total**: 3,393/sec, **615.1 KiB/sec** | **Content**: 2,172/sec, 414.1 KiB/sec **Query**: 48/sec, 9.3 KiB/sec **Maintenance**: 1.80/sec, 0.3 KiB/sec **Repair**: 239/sec, 46.7 KiB/sec **Total**: 2,639/sec, **470.4 KiB/sec** | ### Scenario 2: Moderate Query Rate (Q = 0.001 queries/piece/sec) *1 query per piece every ~17 minutes* | Erasure Coding | Providers \(P) | 10K Nodes | 50K Nodes| 100K Nodes| 250K Nodes | 500K Nodes | 750K Nodes | 1M Nodes | |---------------|---------------|---------------|---------------|---------------|------------|------------|------------|----------| | **(K=10, M=2)** | **P=12** | **Content**: 72,285/sec, 14,118.2 KiB/sec **Query**: 35,877/sec, 7,007.2 KiB/sec **Maintenance**: 1.20/sec, 0.23 KiB/sec **Repair**: 3,189/sec, 622.9 KiB/sec **Total**: 111,352/sec, 21,748.5 KiB/sec| **Content**: 16,983/sec, 3,317.0 KiB/sec **Query**: 8,429/sec, 1,646.3 KiB/sec **Maintenance**: 1.40/sec, 0.27 KiB/sec **Repair**: 749/sec, 146.3 KiB/sec **Total**: 26,163/sec, 5,110.0 KiB/sec| **Content**: 9,036/sec, 1,764.8 KiB/sec **Query**: 4,485/sec, 875.9 KiB/sec **Maintenance**: 1.49/sec, 0.29 KiB/sec **Repair**: 399/sec, 77.9 KiB/sec **Total**: 13,920/sec, 2,718.8 KiB/sec| **Content**: 3,900/sec, 744.0 KiB/sec **Query**: 1,944/sec, 372.0 KiB/sec **Maintenance**: 162/sec, 0.3 KiB/sec **Repair**: 215/sec, 42 KiB/sec **Total**: 6,221/sec, **1,158.3 KiB/sec** | **Content**: 2,064/sec, 392.7 KiB/sec **Query**: 972/sec, 184.5 KiB/sec **Maintenance**: 171/sec, 0.3 KiB/sec **Repair**: 114/sec, 22.2 KiB/sec **Total**: 3,321/sec, **599.7 KiB/sec** | **Content**: 1,419/sec, 269.4 KiB/sec **Query**: 648/sec, 123.0 KiB/sec **Maintenance**: 177/sec, 0.3 KiB/sec **Repair**: 78/sec, 15.2 KiB/sec **Total**: 2,322/sec, **407.9 KiB/sec** | **Content**: 1,086/sec, 208.2 KiB/sec **Query**: 486/sec, 93.9 KiB/sec **Maintenance**: 180/sec, 0.3 KiB/sec **Repair**: 60/sec, 11.7 KiB/sec **Total**: 1,812/sec, **314.1 KiB/sec** | | **(K=20, M=4)** | **P=24** | **Content**: 144,570/sec, 28,236.4 KiB/sec **Query**: 35,877/sec, 7,007.2 KiB/sec **Maintenance**: 1.20/sec, 0.23 KiB/sec **Repair**: 6,378/sec, 1,245.7 KiB/sec **Total**: 186,826/sec, 36,489.5 KiB/sec| **Content**: 33,967/sec, 6,634.1 KiB/sec **Query**: 8,429/sec, 1,646.3 KiB/sec **Maintenance**: 1.40/sec, 0.27 KiB/sec **Repair**: 1,499/sec, 292.7 KiB/sec **Total**: 43,896/sec, 8,573.4 KiB/sec| **Content**: 18,071/sec, 3,529.5 KiB/sec **Query**: 4,485/sec, 875.9 KiB/sec **Maintenance**: 1.49/sec, 0.29 KiB/sec **Repair**: 797/sec, 155.7 KiB/sec **Total**: 23,355/sec, 4,561.5 KiB/sec| **Content**: 7,803/sec, 1,488.2 KiB/sec **Query**: 1,944/sec, 372.0 KiB/sec **Maintenance**: 162/sec, 0.3 KiB/sec **Repair**: 861/sec, 168.1 KiB/sec **Total**: 10,770/sec, **2,028.6 KiB/sec** | **Content**: 4,128/sec, 788.1 KiB/sec **Query**: 972/sec, 184.5 KiB/sec **Maintenance**: 171/sec, 0.3 KiB/sec **Repair**: 454/sec, 88.7 KiB/sec **Total**: 5,725/sec, **1,061.6 KiB/sec** | **Content**: 2,838/sec, 541.2 KiB/sec **Query**: 648/sec, 123.0 KiB/sec **Maintenance**: 177/sec, 0.3 KiB/sec **Repair**: 312/sec, 61 KiB/sec **Total**: 3,975/sec, **725.5 KiB/sec** | **Content**: 2,172/sec, 414.1 KiB/sec **Query**: 486/sec, 93.9 KiB/sec **Maintenance**: 180/sec, 0.3 KiB/sec **Repair**: 239/sec, 46.7 KiB/sec **Total**: 3,077/sec, **555.0 KiB/sec** | ### Scenario 3: High Query Rate (Q = 0.01 queries/piece/sec) *1 query per piece every ~1.7 minutes* | Erasure Coding | Providers \(P) | 10K Nodes | 50K Nodes| 100K Nodes| 250K Nodes | 500K Nodes | 750K Nodes | 1M Nodes | |---------------|---------------|---------------|---------------|---------------|------------|------------|------------|----------| | **(K=10, M=2)** | **P=12** | **Content**: 72,285/sec, 14,118.2 KiB/sec **Query**: 358,768/sec, 70,071.9 KiB/sec **Maintenance**: 1.20/sec, 0.23 KiB/sec **Repair**: 3,189/sec, 622.9 KiB/sec **Total**: 434,244/sec, 84,813.2 KiB/sec| **Content**: 16,983/sec, 3,317.0 KiB/sec **Query**: 84,292/sec, 16,463.3 KiB/sec **Maintenance**: 1.40/sec, 0.27 KiB/sec **Repair**: 749/sec, 146.3 KiB/sec **Total**: 102,026/sec, 19,927.0 KiB/sec| **Content**: 9,036/sec, 1,764.8 KiB/sec **Query**: 44,846/sec, 8,759.0 KiB/sec **Maintenance**: 1.49/sec, 0.29 KiB/sec **Repair**: 399/sec, 77.9 KiB/sec **Total**: 54,282/sec, 10,601.9 KiB/sec| **Content**: 3,900/sec, 744.0 KiB/sec **Query**: 19,440/sec, 3,713.4 KiB/sec **Maintenance**: 162/sec, 0.3 KiB/sec **Repair**: 215/sec, 42 KiB/sec **Total**: 23,717/sec, **4,499.7 KiB/sec** | **Content**: 2,064/sec, 392.7 KiB/sec **Query**: 9,720/sec, 1,856.7 KiB/sec **Maintenance**: 171/sec, 0.3 KiB/sec **Repair**: 114/sec, 22.2 KiB/sec **Total**: 12,069/sec, **2,271.9 KiB/sec** | **Content**: 1,419/sec, 269.4 KiB/sec **Query**: 6,480/sec, 1,237.8 KiB/sec **Maintenance**: 177/sec, 0.3 KiB/sec **Repair**: 78/sec, 15.2 KiB/sec **Total**: 8,154/sec, **1,522.7 KiB/sec** | **Content**: 1,086/sec, 208.2 KiB/sec **Query**: 4,860/sec, 928.2 KiB/sec **Maintenance**: 180/sec, 0.3 KiB/sec **Repair**: 60/sec, 11.7 KiB/sec **Total**: 6,186/sec, **1,148.4 KiB/sec** | | **(K=20, M=4)** | **P=24** | **Content**: 144,570/sec, 28,236.4 KiB/sec **Query**: 358,768/sec, 70,071.9 KiB/sec **Maintenance**: 1.20/sec, 0.23 KiB/sec **Repair**: 6,378/sec, 1,245.7 KiB/sec **Total**: 509,718/sec, 99,554.3 KiB/sec | **Content**: 33,967/sec, 6,634.1 KiB/sec **Query**: 84,292/sec, 16,463.3 KiB/sec **Maintenance**: 1.40/sec, 0.27 KiB/sec **Repair**: 1,499/sec, 292.7 KiB/sec **Total**: 119,759/sec, 23,390.3 KiB/sec | **Content**: 18,071/sec, 3,529.5 KiB/sec **Query**: 44,846/sec, 8,759.0 KiB/sec **Maintenance**: 1.49/sec, 0.29 KiB/sec **Repair**: 797/sec, 155.7 KiB/sec **Total**: 63,716/sec, 12,444.5 KiB/sec | **Content**: 7,803/sec, 1,488.2 KiB/sec **Query**: 19,440/sec, 3,713.4 KiB/sec **Maintenance**: 162/sec, 0.3 KiB/sec **Repair**: 861/sec, 168.1 KiB/sec **Total**: 28,266/sec, **5,370.0 KiB/sec** | **Content**: 4,128/sec, 788.1 KiB/sec **Query**: 9,720/sec, 1,856.7 KiB/sec **Maintenance**: 171/sec, 0.3 KiB/sec **Repair**: 454/sec, 88.7 KiB/sec **Total**: 14,473/sec, **2,733.8 KiB/sec** | **Content**: 2,838/sec, 541.2 KiB/sec **Query**: 6,480/sec, 1,237.8 KiB/sec **Maintenance**: 177/sec, 0.3 KiB/sec **Repair**: 312/sec, 61 KiB/sec **Total**: 9,807/sec, **1,840.3 KiB/sec** | **Content**: 2,172/sec, 414.1 KiB/sec **Query**: 4,860/sec, 928.2 KiB/sec **Maintenance**: 180/sec, 0.3 KiB/sec **Repair**: 239/sec, 46.7 KiB/sec **Total**: 7,451/sec, **1,389.3 KiB/sec** | ## Sample Calculation - (K_EC=30, M_EC=2) with 1M Nodes, Q=0.001 ``` Erasure Coding: K_EC=30, M_EC=2 C = 10⁹ = 1B content pieces P = 30 + 2 = 32 providers per content piece Q = 0.001 queries per piece per second N = 1M nodes α = 3 Churn_Rate = 0.01 Content Updates: Updates_per_Node = (10⁹ × 32 × log₂(1M) × 8 × 3 x (0.00005 + 1/7200)) / 1M = (10⁹ × 32 × 19.9 × 8 × 3 x 0.000189) / 1M = 2895 updates/sec per node Content_Bandwidth = 2895 × 200 bytes = 565.5 KiB/sec per node Query Load: Query_Load_per_Node = (10⁹ × 0.001 × 3 x 19.9 × 9) / 1M = 537 million / 1M = 537 queries/sec per node Query_Bandwidth = 537 × 200 bytes = 105.0 KiB/sec per node Maintenance Traffic: Maintenance_Bandwidth = c₂ × log₂(N) × α x Churn_Rate × Message_Size = 3 × 19.9 × 3 x 0.01 × 200 = 358.2 bytes/sec = 0.3 KiB/sec per node Repair Load: Repair_Load_per_Node = (10⁹ × 2 × 0.00005 × 19.9 × 8 x 3) / 1M = 47.8 repair ops/sec per node Repair_Bandwidth = 47.8 × 200 bytes = 9.3 KiB/sec per node Total Bandwidth: Total_Bandwidth = 565.5KiB + 105.0KiB + 0.3KiB + 9.3KiB = 680.1 KiB/sec per node Component Breakdown: - Content: 83.15% (565.5/680.1) - Query: 15.44% (105.0/680.1) - Repair: 1.37% (9.3/680.1) - Maintenance: 0.04% (0.3/680.1) ``` The existing formulations give us baseline steady-state values per node. The primary drivers of traffic variations are two distinct churn rates: provider churn rate (λ) affecting content announcements, and client churn rate affecting DHT maintenance traffic. Both increase during network stress periods as nodes become unstable, fail, leave and rejoin, or new nodes join the network. Additional factors include message loss rates requiring retries and protocol overhead. Parameters like T (refresh interval), K (replication factor), and N (network size) we assume remain constant during peak/stress scenarios, otherwise we can compute the new steady-state values. Provider churn rates are lower and increase modestly (2×, 4×) because storage providers have economic incentives to maintain stable infrastructure. Client churn rates are higher and more volatile because consumer nodes lack persistent economic motivation to stay online. To calculate realistic traffic scenarios: ``` Baseline_Updates = (C × P × log₂(N) × K × (λ_normal + 1/T)) / N Peak_Updates = (C × P × log₂(N) × K × (λ_peak + 1/T)) / N × Message_Loss_Factor Stress_Updates = (C × P × log₂(N) × K × (λ_stress + 1/T)) / N × Message_Loss_Factor ``` Where: - **λ_normal = 0.001, λ_peak = 0.002, λ_stress = 0.004** - **Churn_normal = 0.005, Churn_peak = 0.010, Churn_stress = 0.020** - **Message_Loss_Factor = 1.2-1.5** (retries due to network conditions) The final multipliers are: ``` Peak: 1.89 × 1.2 = 2.3× Stress: 3.68 × 1.5 = 5.5× ``` So far we modeled query traffic under a uniform distribution, where each of the content pieces receives an average query rate of Q queries/sec. However, real-world P2P file-sharing systems, such as Codex, exhibit highly skewed access patterns, where a small fraction of popular content accounts for the majority of queries. To capture this behavior, we adopt Zipf's law, a power-law distribution with exponent \(s = 1), to model query traffic. We analyze the concentration of queries on popular content (e.g., the top 5%) and apply the model to the common DHT example and the Codex DHT example, incorporating repair traffic for the latter. Calculations include the hotspot scenario to quantify the effects of query skew. ### Zipf's Law and it's impact on query traffic Zipf's law states that the frequency of an item is inversely proportional to its rank in a frequency table. For content pieces in a file-sharing system: * If we have C content pieces, ranked by popularity from 1 (most popular) to C (least popular), the query frequency for the $r-th$ ranked piece is proportional to $1 \over r^s$, where $s$ is the Zipf exponent (typically $s \approx 0.8$ to $1.2$ for file sharing systems). * Total query rate across all pieces is $Q_{total} = \sum_{r=1}^{C} \frac{A}{r^s}$, where $A$ is a normalization constant. * The average query rate per piece under uniform distribution is Q, with Zipf's law we redistribute $Q_{total} = C \times Q$ according to the Zipf distribution. For simplicity, the query rate for rank $r$ is: $$ q_r = \frac{Q_{total}/r^s}{\sum_{i=1}^C 1/i^s} = \frac{C \times Q/r^s}{\sum_{i=1}^C 1/i^s}$$ The denominator $H_{C,s} = \sum_{i=1}^C 1/i^s$ is the generalized harmonic number. For large C and when $s \approx 1, H_{C,1} \approx ln(C) + γ$ (where $γ \approx 0.577$ is the Euler-Mascheroni constant). With Zipf's law, the query load depends on the distribution of queries across content pieces. Since the DHT assigns content pieces to nodes randomly, each node handles roughly equal share of content pieces ($C/N$). However, the query rate for each piece varies by rank, which means **hotspots** can occur if certain nodes consistenly handle popular content due to imperfect randomization. ### Hotspot analysis The top $k$ pieces (e.g., top %5 of C) receive a significant fraction of queries. The cumulative query rate for the top $k$ pieces is: $$\text{Fraction of queries} = \frac{\sum_{r=1}^k 1/r^s}{\sum_{r=1}^C 1/r^s}$$ For $s=1$, the top $k=0.05 \times C$ pieces account for: $$\frac{\sum_{r=1}^{{5\times 10^7}} 1/r^s}{\sum_{r=1}^{10^9} 1/r^s} \approx \frac{18.304}{21.3} \approx 0.8596$$ Thus, the top 5% of content pieces receive approximately the 85.96% of the total query load: $$0.8596 \times 10^6 = 859,600 \text{ queries/sec}$$ and the repair total queries are: 85960 repair ops/sec for the top 5% and 14040 repair ops/sec for the rest 95%. #### Recalculation for the common DHT example * Average Zipf query load * Top 5% = 1661.77 queries/sec, 1661.77 x 200 = 324.56 KiB/sec * Remaining 95% = 271.42 queries/sec, 271.42 x 200 = 53.01 KiB/sec * Total: 1661.77 + 271.42 = 1933.2 queries/sec, 324.56 + 53.01 = 377.57 KiB/sec * Hotspot Zipf query load (assume 2x top 5%) * Top 5% = 1661.77 x 2 = 3323.54 queries/sec, 324.56 x 2 = 649.12 KiB/sec * Total: 3324.54 + 271.42 = 3595.96 queries/sec, 649.12 + 52.9 = 702.2 KiB/sec * Total Bandwidth * **Uniform**: Content: 429.6 KiB/sec, Query: 377.57 KiB/sec, Maintenance: 0.3 KiB/sec, Total: 807.47 KiB/sec * **Hotspot**: Content: 429.6 KiB/sec, Query: 702.2 KiB/sec, Maintenance: 0.3 KiB/sec, Total: 1132.1 KiB/sec * **Hotspot breakdown**: Content: 37.95%, Query: 62.02%, Maintenance: 0.03% #### Recalculation for the Codex DHT example * Average Zipf query load * Top 5% = 462.295 queries/sec, 462.295 x 200 = 90.3 KiB/sec * Remaining 95% = 75.275 queries/sec, 75.275 x 200 = 14.7 KiB/sec * Total: 462.295 + 75.275 = 537.57 queries/sec, 90.3 + 14.7 = 105.0 KiB/sec * Average Zipf repair load * Top 5% = 41.1 repair ops/sec, 41.1 x 200 = 8.0 KiB/sec * Remaining 95% = 6.7 repair ops/sec, 6.7 x 200 = 1.3 KiB/sec * Total: 41.1 + 6.7 = 47.8 repair ops/sec, 9.3 KiB/sec * Hotspot Zipf query load (assume 2x top 5%) * Top 5% = 462.295 x 2 queries/sec = 924.59 queries/sec * Total: 924.59 + 75.275 = 999.865 queries/sec, 195.3 KiB/sec * Hotspot Zipf repair load (assume 2x top 5%) * Repair top 5% = 41.1 x 2 = 82.2 repair ops/sec * Total repair: 6.7 + 82.2 = 88.9 repair ops/sec, 17.36 KiB/sec * Total Hotspot Bandwidth * **Uniform**: Content: 565.5 KiB/sec, Query: 105.0 KiB/sec, Repair: 9.3 KiB/sec, Maintenance: 0.3 KiB/sec, Total: 680.1 KiB/sec * **Hotspot**: Content: 565.5 KiB/sec, Query: 195.3 KiB/sec, Repair: 17.36 KiB/sec, Maintenance: 0.3 KiB/sec, Total: 778.46 KiB/sec * **Hotspot breakdown**: Content: 72.64%, Query: 25.08%, Repair: 2.24%, Maintenance: 0.04%