Protecting routing infrastructures from denial of service using cooperative intrusion detection

We present a solution to the denial of service prob- lem for routing infrastructures. When a network suffers from denial of service, packets cannot reach their destinations. Existing routing protocols are not, well-equipped to deal with denial of service; a misbehaving router-which may be caused by software/hardware faults, misconfiguration, or ma- licious attacks-may be able to disable entire net- works. To protect network infrastructures from routers that incorrectly drop packets and misroute packets, we hypothesize failure models for routers and present protocols that detect and respond to those misbehaving routers. Based on realistic as- sumptions, we prove that our protocols have the fol- lowing properties: (1) A well-behaved router never incorrectly claims another router as a misbehaving router; (2) If a network has misbehaving routers, one or more of them can be located; (3) Misbehav- ing routers will eventually be removed.