Algorithms to implement snap-shot-based effective-bandwidth routing that best utilizes its excess bandwidth for best effort traffic

Computationally efficient algorithms are developed to implement admission control and explicit routing of label switched paths (LSPs) for individually arriving quality of service (QoS) connection requests in a multiprotocol label switching (MPLS) network domain. A greedy admissions control policy, based on the snap-shot state of the network, is applied to arriving QoS connection requests, i.e., a connection request is admitted whenever there is an available path with sufficient residual capacities along its links to support the connection without re-routing existing LSPs. Although in our novel scenario best effort (BE) traffic flows follow their usual destination-based shortest path routes, in routing QoS connections, our algorithms give consideration to the resultant BE traffic delays. Excess effective bandwidth, the margin by which a QoS connection's effective bandwidth exceeds its average consumed bandwidth, is employed to support BE traffic.