In Time-driven Switching (TDS) networks with non-immediate forwarding (NIF) provides scheduling flexibility and consequently, reduces the blocking probability (blocking is defined to take place when transmission capacity is available, but without a feasible schedule). However, it has been shown that with NIF scheduling complexity may grow exponentially. Efficiently finding a schedule from an exponential set of potential schedules is the focus of this paper. The work first presents the mathematical formulation of the NIF scheduling problem, under a wide variety of networking requirements, then introduces an efficient (i.e., having at most polynomial complexity) search algorithm that guarantees to find at least one schedule whenever such a schedule exists. The novel algorithm uses trellis" representations and the well-known survivor-based searching principle."
An Efficient Scheduling Algorithm for Time-Driven Switching Networks / Truong, Thu-Huong; Baldi, Mario; Ofek, Yoram. - ELETTRONICO. - (2007), pp. 1-8.
An Efficient Scheduling Algorithm for Time-Driven Switching Networks
Truong, Thu-Huong;Ofek, Yoram
2007-01-01
Abstract
In Time-driven Switching (TDS) networks with non-immediate forwarding (NIF) provides scheduling flexibility and consequently, reduces the blocking probability (blocking is defined to take place when transmission capacity is available, but without a feasible schedule). However, it has been shown that with NIF scheduling complexity may grow exponentially. Efficiently finding a schedule from an exponential set of potential schedules is the focus of this paper. The work first presents the mathematical formulation of the NIF scheduling problem, under a wide variety of networking requirements, then introduces an efficient (i.e., having at most polynomial complexity) search algorithm that guarantees to find at least one schedule whenever such a schedule exists. The novel algorithm uses trellis" representations and the well-known survivor-based searching principle."File | Dimensione | Formato | |
---|---|---|---|
dtr-07-002.pdf
accesso aperto
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
637.84 kB
Formato
Adobe PDF
|
637.84 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione