File size: 2,900 Bytes
1cdfc83 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | // Application 2: Network Tomography / Packet Loss Counting
// Assign DSS weights to packet sequence numbers in multicast.
// Receiver reports aggregate of received weights.
// Sender determines EXACTLY how many packets arrived from the sum alone.
import { computeGreedySequence, buildCardinalityTable } from './greedy.mjs';
export function runNetworkTomographyDemo() {
console.log('='.repeat(70));
console.log(' NETWORK TOMOGRAPHY via DSS WEIGHTS');
console.log(' Aggregate ACK reveals packet count in O(1)');
console.log('='.repeat(70));
console.log();
const NUM_PACKETS = 15;
const weights = computeGreedySequence(NUM_PACKETS);
const table = buildCardinalityTable(weights);
console.log(`Multicast stream: ${NUM_PACKETS} packets`);
console.log(`DSS weights: [${weights.join(', ')}]`);
console.log(`Total weight (all received): ${weights.reduce((a, b) => a + b, 0)}`);
console.log(`Max weight: ${weights[NUM_PACKETS - 1]} (${Math.ceil(Math.log2(weights[NUM_PACKETS - 1] + 1))} bits per packet tag)`);
console.log();
// Simulate various loss patterns
const scenarios = [
{ name: 'No loss', received: [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14] },
{ name: '3 packets lost', received: [0,1,3,4,5,6,7,8,10,11,12,14] },
{ name: '7 packets lost', received: [0,2,5,6,9,11,13,14] },
{ name: 'Burst loss (middle)', received: [0,1,2,3,4,10,11,12,13,14] },
{ name: 'Only first arrived', received: [0] },
{ name: 'Total loss', received: [] },
];
console.log('RECEIVER REPORTS:');
console.log('-'.repeat(70));
for (const scenario of scenarios) {
const receivedWeights = scenario.received.map(i => weights[i]);
const aggregateACK = receivedWeights.reduce((a, b) => a + b, 0);
const detectedCount = aggregateACK === 0 ? 0 : (table.get(aggregateACK) ?? -1);
console.log(`\n ${scenario.name}:`);
console.log(` Received indices: [${scenario.received.join(',')}]`);
console.log(` Aggregate ACK value: ${aggregateACK}`);
console.log(` DSS Oracle: "${detectedCount} packets received"`);
console.log(` Actual: ${scenario.received.length} packets`);
console.log(` Correct: ${detectedCount === scenario.received.length ? 'YES' : 'NO'}`);
console.log(` Loss rate: ${((1 - scenario.received.length / NUM_PACKETS) * 100).toFixed(1)}%`);
}
console.log('\n' + '-'.repeat(70));
console.log('\nPROTOCOL ADVANTAGE:');
console.log(' Traditional ACK: Send bitmap of received packets (n bits)');
console.log(` DSS ACK: Send single integer (${Math.ceil(Math.log2(weights.reduce((a,b)=>a+b,0) + 1))} bits)`);
console.log(' Savings: Constant-size ACK reveals reception COUNT instantly.');
console.log(' Then targeted NACK for identity recovery within known cardinality.');
console.log();
return { weights, scenarios, table };
}
|