SLGP Header

Convolution Analysis and Algorithm for Advance Bandwidth Preparation in Devoted Networks

IJEECC Front Page

An increasing number of high-performance networks provision dedicated channels through circuit switching or MPLS/GMPLS techniques to support large data transfer. The link bandwidths in such networks are typically shared by multiple users through advance reservation, resulting in varying bandwidth availability in future time. Developing efficient scheduling algorithms for advance bandwidth reservation has become a critical task to improve the utilization of network resources and meet the transport requirements of application users. We consider an exhaustive combination of different path and bandwidth constraints and formulate four types of advance bandwidth scheduling problems, with the same objective to minimize the data transfer end time for a given transfer request with a prespecified data size: 1) fixed path with fixed bandwidth (FPFB); 2) fixed path with variable bandwidth (FPVB); 3) variable path with fixed bandwidth (VPFB); and 4) variable path with variable bandwidth (VPVB). For VPFB and VPVB, we further consider two subcases where the path switching delay is negligible or nonnegligible. We propose an optimal algorithm for each of these scheduling problems except for FPVB and VPVB with nonnegligible path switching delay, which are proven to be NP-complete and nonapproximable, and then tackled by heuristics. The per-formance superiority of these heuristics is verified by extensive experimental results in a large set of simulated networks in comparison to optimal and greedy strategies.
Index Terms:Bandwidth scheduling, dedicated networks, nonapproximable.
To improve the bandwidth utilization while maintaining the same QoS guaranteed services, our research objective is twofold: 1) the existing bandwidth reservation is not changed to maintain the same QoS guaranteed services. 2) our research work focuses on increasing the bandwidth utilization by utilizing the unused bandwidth. We propose a scheme, named Bandwidth Recycling, which recycles the unused bandwidth while keeping the same QoS guaranteed services without introducing extra delay. The general concept behind our scheme is to allow other SSs to utilize the unused bandwidth left by the current transmitting SS. Since the unused bandwidth is not supposed to occur regularly, our scheme allows SSs with non-real time applications, which have more flexibility of delay requirements, to recycle the unused bandwidth. Consequently, the unused bandwidth in the current frame can be utilized. It is different from the bandwidth adjustment in which the adjusted bandwidth is enforced as early as in the next coming frame. Moreover, the unused bandwidth is likely to be released temporarily (i.e., only in the current frame) and the existing bandwidth reservation does not change. Therefore, our scheme improves the overall throughput while providing the same QoS guaranteed services. There are two types of BRs defined in the IEEE 802.16 standard: incremental and aggregate BRs.
The former allow the SS to indicate the extra bandwidth required for a connection. Thus, the amount of reserved bandwidth can be only increased via incremental BRs. On the other hand, the SS specifies the current state of queue for the particular connection via aggregate request. The BS resets its perception of that service’s needs upon receiving the request. Consequently, the reserved bandwidth may be decreased.
There is not enough bandwidth in use nowadays and it seems that as the more of it could be used. Of course the performance level arises all the time, but with quality of service development the bandwidth that is in hand can be used a lot better and better applications and services can be developed for the customers. Even if everyone knew that in a known period of time, the performance of the communications systems would grow enough for the services that one would like to implement, the developed services could already be developed and tested in the old systems with more optimal usage of the resources in hand. Surely this kind of an approach would lead to an advantage in the field of competition in data communications business, especially for the service providers. Reliability of the transmission media plays an important role in the developed data communications equipment and in the transmission protocols. Reliability is one of the most important things when it comes to the services too. In many services, the low level of reliability makes them unusable. In a way, reliability is a component of quality of service - the more reliable the system, the higher the level of QoS.


  1. TSI, “Terascale Supernova Initiative (TSI),” 2011 [Online].
  2. NLCF, “National Leadership Computing Facility (NLCF),” 2004 [On- line].
  3. N. Rao, Q. Wu, S. Carter, W. Wing, D. G. A. Banerjee, and B. Mukherjee, “Control plane for advance bandwidth scheduling in ultra-high-speed networks,” in Proc. INFOCOM Workshop Terabits Netw., 2006, pp. 1–5.
  4. UCLP, “UCLP: User Controlled LightPath Provisioning,” 2011 [On- line].
  5. N. Rao, W. Wing, S. Carter, and Q. Wu, “Ultrascience net: Network testbedforlarge-scalescienceapplications,”IEEECommun.Mag.vol. 43, no. 11, pp. s12–s17, Nov. 2005 [Online]. Available: http://www.
  6. CHEETAH, “CHEETAH: Circuit-switched High-speed End-to-End Transport ArcHitecture,” 2008 [Online]. Available: http://www.ece.
  7. “Enlightened computing: An architecture for co-allocating network, compute, and other grid resources for high-end applications,” in Proc. IEEE HONET, Dubai, UAE, Nov. 2007, pp. 1–8.
  8. Mid-Atlantic Crossroads, “DRAGON: Dynamic Resource Allo- cation via GMPLS Optical Networks,” 2011
  9. JGN-X, “JGN II: Advanced network testbed for research and develop- ment,” 2011 [Online].
  10. GEANT2, “GEANT2,” 2011 [Online].
  11. ESnet, “OSCARS: On-demand Secure Circuits and Advance Reserva- tion System,” 2011 [Online].
  12. Internet2, “Internet2 Interoperable On-Demand Network (ION) ser- vice,” 2011 [Online]. Available:
  13. Z. Zhang, Z. Duan, and Y. Hou, “Decoupling QoS control from core routers: A novel bandwidth broker architecture for scalable support of guaranteed services,” in Proc. ACM SIGCOMM, 2000.
  14. GENI, “GENI: Global Environment for Network Innovations,” 2011 [Online].