Synchronous bandwidth allocation for real-time communications with the timed-token MAC protocol

One of the key issues in tailoring the timed-token MAC protocol for real-ti me applications is synchronous bandwidth allocation (SBA), whose objective is to meet both the protocol and deadline constraints. The former constrain t requires that the total time:allocated to all nodes for transmitting sync hronous messages should not exceed the target token rotation time. The latt er constraint requires that the minimum time available for a node to transm it its synchronous messages before their deadlines should be no less than t he maximum message transmission time. Several nonoptimal local SEA schemes and an optimal global SEA scheme have been proposed [1], [2], [3], [8], [17 ], [29]. Local SEA schemes use only information available locally to each n ode and are thus preferred to global schemes because of their lower network -management overhead. If optimal local SEA schemes, ii any, can be devised, they will be superior to their global counterparts both in performance and in ease of network management. In this paper, we formally prove that there does not exist any optimal local SEA scheme. We also propose an optimal gl obal SEA scheme which has an O(nM) polynomial-time worst-case complexity, w here n is the number of synchronous message streams in the system and M is the time complexity for solving a linear programming problem with 3n constr aints and n variables.