PPF: Link-State Routing Protocol on Multiple Optimality Criteria

Routing is central to meeting the stringent, heterogeneous quality-of-service (QoS) demands of modern Internet applications. Multi-criteria routing, which computes Pareto-optimal paths over metrics such as delay and bandwidth, offers a promising solution, yet current proposals are confined to SDN designs or vector protocols. Enabling multi-criteria optimality within widely deployed link-state protocols is still an open challenge. We fill this gap with PPF (Pareto-optimal Path First), a link-state protocol supporting multi-criteria optimality with provable guarantees. PPF contributes an efficient Dijkstra-Pareto algorithm and a tag-based forwarding scheme that rides atop existing data planes (e.g., MPLS). We formally derive the algebraic conditions ensuring path- and attribute-completeness and prove routing consistency. We implement and evaluate PPF on real-world topologies using Mininet. The results show that PPF converges 95% faster while incurring up to 100× lower communication overhead than vector-based protocols. PPF also sustains lower latency and higher throughput compared to state-of-the-art QoS schemes. These results highlight PPF’s viability as a scalable, efficient, and QoS-aware multi-criteria routing solution for real-world networks.