DDR: A Deadline-Driven Routing Protocol for Delay Guaranteed Service PDF

DDR: A DEADLINE-DRIVEN ROUTING PROTOCOL FOR DELAY GUARANTEED SERVICE Published in IEEE Conference on Computer Communications FARHANA COMPUTER NETWORKS TERM PROJECT #1 1 Delay Guaranteed Service Many applications require not only data trans...

DDR: A DEADLINE-DRIVEN ROUTING PROTOCOL FOR DELAY GUARANTEED SERVICE Published in IEEE Conference on Computer Communications FARHANA COMPUTER NETWORKS TERM PROJECT #1 1 Delay Guaranteed Service Many applications require not only data transmission but guaranteed timely delivery. This is especially true for real-time services like online gaming, autonomous vehicles, and IoT systems. Why this matters 1) Challenges of traditional routing protocols: lack of deadline-awareness. 2) Increasing reliance on real-time data in modern applications. 2 Routing Protocols in Networking They determine the paths data packets take to reach their destinations, minimizing delays and maximizing throughput. However, in time-sensitive applications, traditional routing protocols fall short because they don't account for the deadline by which data must be delivered. 3 Challenges in Delay-Guaranteed Routing Scalability: May struggle to scale up to handle the size and complexity of modern, large networks with varying traffic patterns. Real-time Decision Making: Require pre-computed paths or are slow in adapting to real-time changes in network conditions So, is DGR not that good? Not necessarily bad, but it's not perfect for all use cases. 4 The Approach of DGR The Cross-Layer Approach Network Layer: Optimal path selection based on topology and real-time conditions. Link Layer: Uses priority queues to manage latency budgets and ensure packet delivery. Result: Ensures that packets meet latency constraints with minimal delay. Decentralized Routing Local Decision-Making: Routers adapt based on local traffic and queue conditions. Scalability: Eliminates the need for centralized control, improving network performance in large-scale systems. Real-Time Adaptation: Ensures timely packet delivery without relying on centralized decision-making. 5 Overview of DDR Protocol DDR is designed to achieve millisecond-level latency guarantees. It combines the strengths of table-based routing and local traffic state adaptation to make real-time routing decisions, ensuring efficient and reliable packet delivery. Key Features: Delay quantization using priority queues. Delay estimation with Markov models. Dynamic route selection based on traffic conditions. 6 DDR's Role in Solving DGR Components of DDR that help ensure packets are delivered within the required delay, even in dynamically changing network conditions. Traffic Condition Database (TCDB) Local Complete FIB (Forwarding Information Base) Adaptive Route Selection DGR Problem: The need to manage varying network traffic conditions and congestion while guaranteeing timely packet delivery, especially for real-time or delay-sensitive applications 7 Traffic Condition Database (TCDB) How? Traffic Management and Delay Estimation A real-time traffic estimator. It helps routers make informed routing decisions by predicting how congested different paths in the network are likely to be. Focuses on collecting and estimating network traffic conditions and dynamically adjusts routing decisions to ensure latency-sensitive packets are delivered on time. Techniques like delay quantization and Markov models. 8 Local Complete FIB (Forwarding Information Base) How? Routing Optimization and Multi-Path Forwarding A database maintained by each router in a network. It stores all the possible paths to reach every destination in the network, along with information like the cost of each path. Optimizing routing by considering multiple alternative paths for packet delivery, not just a single route. Recursively computes feasible path candidates, ensuring spreading traffic across multiple routes. 9 Adaptive Route Selection How? Adaptive Route Selection with Multi-Path Forwarding The process where each router makes a real-time decision about the best path to forward a packet based on current network conditions, particularly congestion. Adapts to real-time traffic conditions and selects the most timely route. Considers both static and dynamic delays and utilizing multiple paths to avoid congestion. 10 Implementation Implemented the DDR protocol in the "ns-3" network simulator. Network Topologies: They chose four well-known network topologies (Abilene, AT&T, CERNET, and GEANT) from the Internet Zoo dataset, a collection of real-world network configurations used for research. The same network topologies and background traffic conditions were used for all protocols to ensure a fair comparison. 11 DDR vs Traditional Routing DDR Traditional Routing Goal Ensure timely delivery Minimize cost, or maximize within latency budget throughput Method Dynamic and Adaptive Pre-determined Delay Management Focus on latency No specific latency guarantees, real-time guarantee congestion management Congestion Handling Dynamic adjustments, traffic No real-time congestion spreading adaptation 12 Benefits of Using DDR Guaranteed Latency: Ensures real-time applications meet their delay requirements. Efficient Traffic Management: Avoids congestion and balances load. Scalability: Efficient use of multiple paths to adapt to changing network conditions. 13 Where DDR Makes a Difference Real-time Communication Scenario: Voice over IP (VoIP), Video Conferencing, Online Gaming Challenge: Require extremely low-latency data transmission to ensure smooth conversations and interactions. Advantage: Ensures that packets are delivered within strict time constraints. ○ Adaptive Route Selection: By selecting paths based on current network conditions and congestion, DDR ensures that even in fluctuating network environments, the communication remains timely and stable. 14 Measuring DDR’s Effectiveness DDR's performance in terms of packet-level on-time delivery against ECMP (Equal-Cost Multipath Routing): A simple protocol that balances traffic across paths with equal costs but doesn’t consider traffic conditions. LFID (Load-Balancing with Fair Delay): A multi-path routing protocol to distribute traffic to reduce congestion. DGRP (Delay-Guaranteed Routing Protocol): A protocol specifically designed for delay guarantees, but it assumes perfect knowledge of neighbor queue status. Was it an ideal network? How was the elephant flows? Or what about burst traffics..! 15 Conclusion Future Directions of DDR: Improved Queue Estimation: Enhance accuracy in predicting future queue states using ML and statistical methods. Optimized Path Selection: Develop algorithms that balance network utility and system stability, considering traffic load and latency constraints. Large-Scale Testing: Build real-world testbeds to validate scalability and performance in diverse network conditions. 16 17