Abstract | ||
---|---|---|
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. |
Year | Venue | Keywords |
---|---|---|
2007 | 2007 15TH IEEE WORKSHOP ON LOCAL & METROPOLITAN AREA NETWORKS | scheduling, search algorithms, time-driven switching, pipeline forwarding, optical networks |
Field | DocType | ISSN |
Time-driven switching,Search algorithm,Job shop scheduling,Fair-share scheduling,Computer science,Scheduling (computing),Computer network,Capacity planning,Schedule,Distributed computing,Computational complexity theory | Conference | 1944-0367 |
Citations | PageRank | References |
3 | 0.56 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Thu-Huong Truong | 1 | 39 | 6.28 |
Mario Baldi | 2 | 12 | 1.87 |
Yoram Ofek | 3 | 608 | 81.68 |