Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Primary-backup Link Scheduling for Wireless Networks Operating in Hostile Environments

SpeakerAxel Krings

To address reliability, security and survivability concerns in wireless networks, a model is introduced that is based on cross-monitoring. Specifically, principal path and orthogonal monitoring are used to detect and possibly correct diverse faults. Recovery is conditioned on the specific requirements associated with the fault model considered. The network model subscribes to a five-fault hybrid fault model considering transmissive and omissive versions of symmetric and asymmetric faults.

To address the redundancy requirements necessary for recovery in the presence of failing or maliciously compromised nodes, several characteristics can be exploited to reduce redundant packet transmission for cross-monitoring purposes. The broadcast paradigm allows fault detection on the principal communication path. Moreover, in the orthogonal dimension it enables detection and correction. The detection mechanisms can be used for primary-backup scheduling. Traditional backup-backup scheduling was adapted to recover from benign and omission faults. In addition a new paradigm is introduced that is based on primary-backup overloading in conjunction with backup-backup overloading capable of dealing with malicious faults.