Persistent detection and recovery of state inconsistencies

Soft-state is a well established approach to designing robust network protocols and applications. However it is unclear how to apply soft-state approach to protocols that must maintain a large amount of state information in a scalable way. For example the Border Gateway Protocol (BGP) is used to maintain the global routing tables at core Internet routers, and the table size is typically above 180,000 entries and continues to grow over time. In this paper, we propose a novel approach, Persistent Detection and Recovery (PDR), to enable large-state protocols and applications to maintain state consistency using a soft-state approach. PDR uses state compression and receiver participation mechanisms to avoid per-state refresh overhead. We evaluate PDR’s effectiveness and scalability by applying its mechanisms to maintain the consistency of BGP routing tables between routers. Our results show that the proposed PDR mechanisms are effective and efficient in detecting and correcting route insertion, modification, and removal errors. Moreover, they eliminate the need for routers to exchange full routing tables after a session reset, thus enabling routers to recover quickly from transient session failures.