2006 | Xiaolan Zhang¹, Giovanni Neglia², Jim Kurose¹, and Don Towsley¹
This paper presents a rigorous, unified framework based on Ordinary Differential Equations (ODEs) to study epidemic routing and its variations. The ODEs are derived as limits of Markovian models under a natural scaling as the number of nodes increases. These ODE models yield closed-form expressions for several performance metrics and do not increase in complexity with the number of nodes. The ODE approach is used to investigate how resources such as buffer space and power can be traded for faster delivery, illustrating differences among various epidemic schemes. The effect of buffer management is also considered by complementing forwarding models with Markovian and fluid buffer models.
Epidemic routing uses a "store-carry-forward" paradigm, where nodes pass packets to new nodes they encounter. This is analogous to the spread of infectious diseases. Epidemic routing achieves minimum delivery delay at the expense of increased resource usage. Variations of epidemic routing, such as K-hop, probabilistic forwarding, and spray-and-wait, have been proposed to exploit the trade-off between delivery delay and resource consumption.
The paper develops ODEs as a fluid limit of Markovian models under appropriate scaling. This allows deriving closed-form formulas for performance metrics and modeling the "recovery process" (packet deletion at infected nodes). The ODE framework is used to study more complex epidemic routing variants and buffer management schemes under constraints.
The paper validates the models using simulations and shows that the ODE models accurately predict performance metrics such as delivery delay and buffer occupancy. The results show that the ODE models provide good agreement with simulation results, especially for the IMMUNE recovery scheme. The models also show that the average buffer occupancy is linearly related to the number of copies made when IMMUNE is used.
The paper extends the model to consider three variations of epidemic routing: K-hop forwarding, probabilistic forwarding, and limited-time forwarding. These models are used to study the trade-off between delivery delay and resource consumption. The results show that probabilistic forwarding offers the best performance for power-saving, while limited-time forwarding provides the best performance for buffer occupancy.
The paper also considers epidemic routing under constrained buffer conditions. It examines three buffer management strategies: droptail, drophead, and source-prioritized drophead. The results show that with appropriate buffer management schemes, a much smaller buffer can be used with negligible effect on delivery performance. The paper concludes that the ODE framework provides a powerful tool for analyzing epidemic routing and its variations. Future work includes investigating schemes for deleting anti-packets and the overhead of anti-packets.This paper presents a rigorous, unified framework based on Ordinary Differential Equations (ODEs) to study epidemic routing and its variations. The ODEs are derived as limits of Markovian models under a natural scaling as the number of nodes increases. These ODE models yield closed-form expressions for several performance metrics and do not increase in complexity with the number of nodes. The ODE approach is used to investigate how resources such as buffer space and power can be traded for faster delivery, illustrating differences among various epidemic schemes. The effect of buffer management is also considered by complementing forwarding models with Markovian and fluid buffer models.
Epidemic routing uses a "store-carry-forward" paradigm, where nodes pass packets to new nodes they encounter. This is analogous to the spread of infectious diseases. Epidemic routing achieves minimum delivery delay at the expense of increased resource usage. Variations of epidemic routing, such as K-hop, probabilistic forwarding, and spray-and-wait, have been proposed to exploit the trade-off between delivery delay and resource consumption.
The paper develops ODEs as a fluid limit of Markovian models under appropriate scaling. This allows deriving closed-form formulas for performance metrics and modeling the "recovery process" (packet deletion at infected nodes). The ODE framework is used to study more complex epidemic routing variants and buffer management schemes under constraints.
The paper validates the models using simulations and shows that the ODE models accurately predict performance metrics such as delivery delay and buffer occupancy. The results show that the ODE models provide good agreement with simulation results, especially for the IMMUNE recovery scheme. The models also show that the average buffer occupancy is linearly related to the number of copies made when IMMUNE is used.
The paper extends the model to consider three variations of epidemic routing: K-hop forwarding, probabilistic forwarding, and limited-time forwarding. These models are used to study the trade-off between delivery delay and resource consumption. The results show that probabilistic forwarding offers the best performance for power-saving, while limited-time forwarding provides the best performance for buffer occupancy.
The paper also considers epidemic routing under constrained buffer conditions. It examines three buffer management strategies: droptail, drophead, and source-prioritized drophead. The results show that with appropriate buffer management schemes, a much smaller buffer can be used with negligible effect on delivery performance. The paper concludes that the ODE framework provides a powerful tool for analyzing epidemic routing and its variations. Future work includes investigating schemes for deleting anti-packets and the overhead of anti-packets.