Source Routing and Scheduling in Packet Networks

Title: Source Routing and Scheduling in Packet Networks

Research Question: How can we design an efficient routing and scheduling system for packet-switched networks, especially when dealing with an adversary that controls the injection time, source, and destination for each packet?

Methodology: The researchers proposed a source routing algorithm that finds a set of admissible paths for packets. This algorithm calculates a path for each packet as soon as it is injected at its source, using a simple shortest path computation. They also presented a scheduling protocol that guarantees a polynomial end-to-end delay for every packet.

Results: The researchers showed that their online routing algorithm can find a set of (W,R)-admissible routes for packets, where R is of their choice and W is determined by the choice of R. They also presented a deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet.

Implications: The researchers' work has significant implications for the field of packet-switched networks. Their source routing algorithm and scheduling protocol can lead to more efficient and stable networks, especially when dealing with an adversary that controls the injection of packets. This work also contributes to the understanding of the stability of scheduling protocols in the Adversarial Queueing Model.

Link to Article: https://arxiv.org/abs/0203030v2 Authors: arXiv ID: 0203030v2