Scheduling Network Traffic for Grid Purposes

Mette Gamst

    Research output: Book/ReportPh.D. thesis

    263 Downloads (Pure)


    This thesis concerns scheduling of network traffic in grid context. Grid computing consists of a number of geographically distributed computers, which work together for solving large problems. The computers are connected through a network. When scheduling job execution in grid computing, data transmission has so far not been taken into account. This causes stability problems, because data transmission takes time and thus causes delays to the execution plan. This thesis proposes the integration of job scheduling and network routing. The scientific contribution is based on methods from operations research and consists of six papers. The first four considers data transmission in grid context. The last two solves the data transmission problem, where the number of paths per data connection is bounded from above. The thesis shows that it is possible to solve the integrated job scheduling and network routing problem to optimality for a grid, where computers are connected through a packet-switched network. When the network topology is optical, the routing problem becomes significantly more complex and the problem should thus be solved heuristically. Furthermore, the thesis proposes a number of new exact methods for the data transmission problem, where the number of paths is bounded from above. The new exact solution methods outperform existing methods from the literature.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages248
    ISBN (Print)978-87-90855-83-3
    Publication statusPublished - Jun 2010
    SeriesPhD thesis


    • Network Routing
    • Heuristics
    • Branch-and-Price
    • Grid Computing
    • Scheduling
    • Multicommodity Flow
    • k-splittable Flow
    • Dantzig-Wolfe Decomposition
    • Routing and Wavelength Assignment


    Dive into the research topics of 'Scheduling Network Traffic for Grid Purposes'. Together they form a unique fingerprint.

    Cite this