Testing the feasibility of synchronous bandwidth allocation for time-critical communication in FDDI networks

One of the key issues related to deadline guarantees of synchronous messages in FDDI networks is the feasibility test of synchronous bandwidth allocation (SBA). Much work has been done on how to allocate synchronous bandwidth properly in order to guarantee synchronous messages transmission before their deadlines, and as a result quite a few SBA schemes have been proposed. In contrast, limited research has been done on how to effectively test the feasibility of a given allocation of synchronous bandwidths (i.e., whether or not a given allocation can guarantee the synchronous message set considered), and the existing approach cannot always give an effective test and may even produce wrong testing results. This paper presents an algorithm of polynomial time worst-case complexity which ensures the correctness and effectiveness of the testing for any given synchronous message set with message deadlines equal to periods.