Article

Free access

Efficient routing and scheduling algorithms for optical networks

Authors:

Madhu SudanAuthors Info & Claims

SODA '94: Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms

Pages 412 - 423

Published: 23 January 1994 Publication History

PDF eReader

References

[1]

S. Arora, T. Leighton, and B. Maggs. On-line algorithms for path selection in a nonblocking network. In Proc. of the A CM Syrup. on Theory of Computing, pages 149-158, 1990.

Digital Library

Google Scholar

[2]

V.E. Bene~. Heuristic remarks and mathematical problems regarding the theory of switching systems. Bell System Tech. Journal, 41:1201-1247, 1962.

Google Scholar

[3]

R. A. Barry and P. A. Humblet. Bounds on the number of wavelengths needed in WDM networks. In LEOS'92 Summer Topical Mtg. Digest, pages 21-22, 1992.

Google Scholar

[4]

R. A. Barry and P. A. Humblet. On the number of wavelengths and switches in all-optical networks. To appear in IEEE Trans. on Communications.

Google Scholar

[5]

A. Borodin, P. Raghavan, B. Schieber, and E. Upfal. How much can hardware hdp routing? In Proc. of the 25th A CM Syrup. on Theory of Computing, San Diego, CA, May 1993.

Digital Library

Google Scholar

[6]

N. K. Cheung, K. Nosu and G. Winzer (eds.) IEEE JSAC: Special .Issue on Dense WDM Networks. volume 8, Aug. 1990.

Google Scholar

[7]

P. Feldman, J. Friedman, and N. Pippenger. Widesense nonblocking networks. SlAM Journal on Discrete Math., 1(2):158-173, May 1988.

Digital Library

Google Scholar

[8]

P. E. Green. Fiber-Optic Networks. Prentice Hall, 1992.

Google Scholar

[9]

P. Hall. On the representatives of subsets. Journal of London Mathematical Society, 10(1):26-30, 1935.

Google Scholar

[10]

F. J. Janniello, R. Ramaswami, and D. G. Steinberg. A prototype circuit-switched multi-wavelength optical metropohtan-area network. J. Lightwave Tech., pp. 777-782, May/June 1993.

Google Scholar

[11]

F.T. Leighton. Introduction to parallel algorithms and architectures: arrays, trees, hypercubes. Morgan Kaufmann Publishers, San Mateo, CA, 1992.

Digital Library

Google Scholar

[12]

R.K. Pankaj. Architectures for linear lightwave networks. PhD thesis, Dept. of Electrical Engineering and Computer Science, MIT, Cambridge, MA, September 1992.

Digital Library

Google Scholar

[13]

G. R. Pieris and G. H. Sasaki. A linear lightwave Bene~ network. To appear in 1EEE//ACM Trans. on Networking, Aug. 1993.

Digital Library

Google Scholar

[14]

G. R. Pieris and G. H. Sazaki. Scheduling transmissions in broadcast and select networks. Proc. Allerton Conf. on Commun. Control ~ Computing, 1993.

Google Scholar

[15]

R. Ramazwami. Multi-wavelength lightwave networks for computer communication. 1EEE Communications Magazine, 31(2):78-88, Feb. 1993.

Google Scholar

[16]

A. Wigderson and D. Zuckerman. Expanders that beat the eigenvaJue bound: explicit construction and applications. In Proc. of the 25th A CM Syrup. on Theory of Computing, San Diego, CA, May 1993.

Digital Library

Google Scholar

Cited By

View all

Flier HMihalák MWidmayer PZych AKobayashi YSchöbel A(2015)Selecting vertex disjoint paths in plane graphsNetworks10.1002/net.2161866:2(136-144)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1002/net.21618
Andrews MZhang L(2009)Complexity of wavelength assignment in optical network optimizationIEEE/ACM Transactions on Networking10.1109/TNET.2009.201422617:2(646-657)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1109/TNET.2009.2014226
Blesa MBlum C(2006)A nature-inspired algorithm for the disjoint paths problemProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898699.1898740(239-239)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898699.1898740
Show More Cited By

Index Terms

Efficient routing and scheduling algorithms for optical networks
1. Hardware
  1. Integrated circuits
    1. Interconnect
      1. Photonic and optical interconnect
2. Theory of computation

Recommendations

Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems

Efficient scheduling algorithms based on heuristic functions are developed for scheduling a set of tasks on a multiprocessor system. The tasks are characterized by worst-case computation times, deadlines, and resources requirements. Starting with an ...
Parallel job scheduling algorithms
Efficient burst scheduling algorithms in optical burst-switched networks using geometric techniques

Optical burst switching (OBS) is a promising paradigm for the next-generation Internet. In OBS, a key problem is to schedule bursts on wavelength channels, whose bandwidth may become fragmented with the so-called void (or idle) intervals, using both ...

Comments

Information & Contributors

Information

Published In

SODA '94: Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms

January 1994

735 pages

ISBN:0898713293

Chairman:
Daniel D. Sleator

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 1994

Check for updates

Qualifiers

Article

Conference

SODA94

Sponsor:

SIGACT
SIAM

SODA94: Conference on Discrete Algorithms

January 23 - 25, 1994

Virginia, Arlington, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
679
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)3

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Flier HMihalák MWidmayer PZych AKobayashi YSchöbel A(2015)Selecting vertex disjoint paths in plane graphsNetworks10.1002/net.2161866:2(136-144)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1002/net.21618
Andrews MZhang L(2009)Complexity of wavelength assignment in optical network optimizationIEEE/ACM Transactions on Networking10.1109/TNET.2009.201422617:2(646-657)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1109/TNET.2009.2014226
Blesa MBlum C(2006)A nature-inspired algorithm for the disjoint paths problemProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898699.1898740(239-239)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898699.1898740
Dellamonica DKohayakawa Y(2006)An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routingProceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm10.5555/1109557.1109672(1038-1044)Online publication date: 22-Jan-2006
https://dl.acm.org/doi/10.5555/1109557.1109672
Andrews MZhang L(2006)Minimizing maximum fiber requirement in optical networksJournal of Computer and System Sciences10.1016/j.jcss.2005.08.00172:1(118-131)Online publication date: 1-Feb-2006
https://dl.acm.org/doi/10.1016/j.jcss.2005.08.001
Bagchi AChaudhary AKolman P(2005)Short length Menger's theorem and reliable optical routingTheoretical Computer Science10.1016/j.tcs.2005.03.009339:2(315-332)Online publication date: 12-Jun-2005
https://dl.acm.org/doi/10.1016/j.tcs.2005.03.009
Mohan GVenkatesan GRam Murthy C(2004)Randomized routing and wavelength requirements in wavelength-routed WDM multistage, hypercube, and de Bruijn networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2003.12.00264:3(385-399)Online publication date: 1-Mar-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2003.12.002
Winkler PZhang L(2003)Wavelength assignment and generalized interval graph coloringProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644246(830-831)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644246
Kchikech MTogni O(2003)Paths coloring algorithms in mesh networksProceedings of the 4th international conference on Discrete mathematics and theoretical computer science10.5555/1783712.1783729(193-202)Online publication date: 7-Jul-2003
https://dl.acm.org/doi/10.5555/1783712.1783729
Barcaccia PBonuccelli MDi Ianni M(2000)Complexity of Minimum Length Scheduling for Precedence Constrained Messages in Distributed SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/71.88864711:10(1090-1102)Online publication date: 1-Oct-2000
https://dl.acm.org/doi/10.1109/71.888647
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems

Parallel job scheduling algorithms

Efficient burst scheduling algorithms in optical burst-switched networks using geometric techniques

Comments

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF

eReader

Login options

Full Access

References

Cited By

Index Terms

Recommendations

Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems

Parallel job scheduling algorithms

Efficient burst scheduling algorithms in optical burst-switched networks using geometric techniques

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations