On time dependent routing algorithms for open marketplaces of path services with support for in-advance path reservation

Open marketplaces of path services are the next step towards realizing “routing-as-a-service.” Such marketplaces will enable users to select from a set of path services offered by multiple competing network providers so as to construct customized end-to-end paths for their applications. This is analogous to online travel marketplaces that allow users to explore travel options and book their travel. We review the requirements for path planners to assist users in stitching together available path services which are time sensitive. We define the problem of finding multi-criteria time-constrained paths in this context, and present algorithms to construct these paths and also provide support for in-advance path reservation.