×

Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks. (English) Zbl 1087.68010

Summary: This paper studies the issue of assigning orientations to all links of an undirected network, which is called the Link-Orientation Problem (LOP). First, we describe some practical variations and address some complexity analysis in LOPs for general networks. Then, we design efficient algorithms to solve these LOPs issues. The proposed approach employs the recursive shortest path rules and the efficient cost cores scheme to resolve the LOP issues for some weighted network systems. These classes of networks include multi-square, convex-bipartite, and convex-split networks. Next, we use the cost core algorithm for adjusting LOP and obtain the more efficient LOP for the weighted convex-bipartite and convex-split networks. In general, the LOP scheme can support the actual applications requirements to realize a WFQ (weighted fair queuing) task for multicast routing in real networks. Finally, the findings of this paper can be mainly applied to some network applications, including efficient revision of load balancing in a ATM switch network, quick selection of a firm’s PCS (Proxy Cache Server) on the Web, and dynamic adjusting of link’s changing conditions in a workflow system on the Internet.

MSC:

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bertsekas, D. P.; Pallottino, S.; Scutella, M. G., Polynomial auction algorithms for shortest paths, Computer Optimal Applications Journal, 4, 99-125 (1995) · Zbl 0835.90111
[2] Bhatt, S. N.; Crowcroft, J., QoS sensitive flows: issues in IP packet handling, IEEE Internet Computing Journal, 4, 4, 48-57 (2000)
[3] Bose, I.; Cheng, H. K., Performance models of a firm’s Proxy Cache Server, Decision Support Systems Journal, 29, 1, 47-57 (2000)
[4] Chowdhury, S.; Sengupta, B., Design and performance of a threshold-based load balancing scheme in an ATM switch, Computer Networks and ISDN Systems Journal, 29, 157-164 (1997)
[5] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), The MIT Press: The MIT Press New York, USA · Zbl 1158.68538
[6] Edmond, D.; ter Hofstede, A. H.M., A reflective infrastructure for workflow adaptability, Data and Knowledge Engineering Journal, 34, 3, 271-302 (2000) · Zbl 0947.68577
[7] Feng, W. C.; Kandlur, D. D.; Saha, D.; Shin, K. G., Understanding and improving TCP performance over networks with minimum rate guarantees, IEEEE/ACM Transactions on Networking Journal, 7, 2, 173-187 (1999)
[8] Golumbics, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York, USA
[9] Jia, X., A distributed algorithm for delay bounded multicast routing for multimedia applications in wide area network, IEEE/ACM Transactions on Networking Journal, 6, 6, 828-837 (1998)
[10] Jiang, Y.; Tham, C. K.; Ko, C. C., Challenges and approaches in providing QoS monitoring, International Journal of Network Management, 10, 6, 323-334 (2000)
[11] Lorenz, H.; Orda, A., QoS routing in networks with uncertain parameters, IEEE/ACM Transactions on Networking Journal, 6, 6, 768-778 (1998)
[12] Peng, S.; Stephens, A. B.; Yesha, Y., Algorithms for a core and \(k\)-core of a tree, Journal of Algorithms, 16, 143-169 (1993) · Zbl 0782.68092
[13] Pavan, A.; Jha, R.; Graba, L.; Cooper, S.; Cardei, I., Real-time adaptive resource management, IEEE Computer Journal, 34, 7, 99-103 (2001)
[14] Peterson, L. L.; Davie, B. S., Computer Networks: A Systems Approach (2000), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers CA, USA · Zbl 0973.68004
[15] Marsan, M. A.; Bianco, A.; Giacome, P.; Leonardi, E.; Neri, F., Multicast traffic in input-queued switches: optimal scheduling and maximum throughput, IEEE/ACM Transactions on Networking Journal, 11, 3, 465-477 (2003)
[16] Tham, C. K.; Jiang, Y.; Ko, C. C., Monitoring QoS distribution in distributed multimedia networks, International Journal of Network Management, 10, 2, 75-90 (2000)
[17] Tsichiya, T.; Kikuno, T., Dependable evaluation of the weighted voting system in the presence of node and link facilities, International Journal of Computer Systems Science & Engineering, 15, 3, 181-190 (2000)
[18] S.J. Yang, An approach for finding the efficient cost cores on weighted split networks, in: Proceedings of the ISCA 13th International Conference on Computers and Their Applications, Honolulu, USA, March 1998, pp. 76-81; S.J. Yang, An approach for finding the efficient cost cores on weighted split networks, in: Proceedings of the ISCA 13th International Conference on Computers and Their Applications, Honolulu, USA, March 1998, pp. 76-81
[19] Yang, S. J., A distributed algorithm of efficient cores discipline on weighted bipartite networks, International Journal of Computer Systems Science and Engineering, USA, 17, 1, 13-22 (2002)
[20] W.C.K. Yen, S.J. Yang, The link-orientation on weighted networks, in: Proceedings of the ISCA 16th International Conference on Computer and Their Applications, Seattle, Washington, USA, April 2001, pp. 325-329; W.C.K. Yen, S.J. Yang, The link-orientation on weighted networks, in: Proceedings of the ISCA 16th International Conference on Computer and Their Applications, Seattle, Washington, USA, April 2001, pp. 325-329
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.