Algorithm-based error detection in ATM cell schedulers

We present an algorithm based error detection technique for a real time cell scheduler in ATM switches. The scheduler is designed to realize EDF (earliest deadline first) scheduling to guarantee the end to end delay bounds of real time messages. The algorithm invariants of the scheduler are identified to detect erroneous or out of order cell transmissions due to a malfunctioning scheduler. Since a malfunctioning scheduler is unlikely to produce errors detectable at the host level, an immediate detection and recovery at each switch is highly desirable in order to achieve reliable communication in ATM networks. The hardware overhead for realizing error detection is manageably small. Moreover, error detection can be done locally with negligible time overhead