Scheduling of real-time messages in optical broadcast-and-select networks

In this paper, we consider broadcast-and-select networks based on optical p assive stars. In these single-hop networks, communicating pairs can exchang e messages directly, without the need to store information at intermediate nodes for later forwarding. Messages are transmitted in a packetized way, a nd each message has an associated deadline. In order to guarantee the messa ge reception timeliness, we ask that all the messages are received within t heir corresponding deadline. We show that this scheduling problem is strong NP-complete, even in a very restricted case. Then, we turn our attention t o fast approximating heuristics. We present four of them, assess their aver age performance by means of computer simulation, and give their worst-case performance bounds. Such bounds can be effectively used to test the success of the schedule before generating it.