Exact topology discovery algorithm for the capacity and delay constrained loop network

Exact topology discovery algorithm for the capacity and delay constrained loop network

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

We have developed an exact model and algorithm for the delay-constrained minimum cost loop problem (DC-MCLP) of finding broadcast loops from a source node. While the traditional minimum cost loop problem (MCLP) deals with only the traffic capacity constraint served by a port of source node, the DC-MCLP deals with the mean network delay and traffic capacity constraints simultaneously. The DC-MCLP consists of finding a set of minimum cost loops to link end-user nodes to a source node satisfying the traffic requirements at end-nodes and the required mean delay of the network. In the DC-MCLP, the objective function is to minimise the total link cost. We have formulated the DC-MCLP and proposed an exact algorithm for its solution. The proposed algorithm is composed of two phases: in the first phase, it generates feasible paths to satisfy the traffic capacity constraint; in the second phase it finds the exact loop topology through matching and allocating optimal link capacity to satisfy the mean delay constraint. In addition, we have derived several properties including the memory and time complexity of the proposed algorithm. Performance evaluation shows that the proposed algorithm has good efficiency for networks with less than thirty nodes and light traffic. Our proposed algorithm can be applied to find the broadcast loops for real-time multimedia traffic.


    1. 1)
      • Astic, I., Festor, O.: `A hierarchical topology discovery service for IPv6 networks', IEEE/IFIP Network Operations and Management Symp., 2002, p. 497–510.
    2. 2)
      • Breibart, Y., Garofalakis, M., Martin, C., Seshadri, S., Silberschatz, A.: `Topology discovery in heterogeneous IP networks', INFOCOM, 2000, p. 265–274.
    3. 3)
      • Lin, H., Lai, H., Lai, S.: `Automatic link layer topology discovery of IP networks', ICC'99: 1999 IEEE Int. Conf. on Communications, 1999, p. 1034–1038.
    4. 4)
      • Lin, H., Wang, Y., Wang, C., Chen, C.: `Web-based distributed topology discovery of IP networks', 15thInt. Conf. on Information Networking, 2001, p. 857–862.
    5. 5)
      • Lin, H., Lai, S., Chen, P.: `An algorithm for automatic topology discovery of IP networks', IEEE Int. Conf. on Communication, 1998, p. 1192–1196.
    6. 6)
      • A. Kershenbaum . (1993) , Telecommunication network design algorithm.
    7. 7)
      • Lee, Y., Lee, D.: `Two phase algorithm for the topological design of local access tree networks', Proc. IASTED Int. Conf., 1996, Acta Press, p. 67–70.
    8. 8)
    9. 9)
      • Y. Lee . Minimal cost heuristic algorithm for delay constrained loop network. Int. J. Comput. Syst. Sci. Eng. , 4 , 209 - 219
    10. 10)
      • J. Lenster , R. Kan . Complexity of vehicle routing and scheduling problems. Networks , 221 - 227
    11. 11)
    12. 12)
      • G. Cheng , N. Ansari . Finding all hop(s) shortest path. IEEE Commun. Lett. , 2 , 122 - 124
    13. 13)
    14. 14)
      • Cheng, G., Ansari, N.: `Achieving 100% success ratio in finding the delay constrained least cost path', Proc. IEEE GLOBECOM '04, 3, Dallas, TX, USA, p. 1505–1509.
    15. 15)
      • Juttner, A., Szyiatowszki, , Mecs, I., Rajko, Z.: `Lagrange relaxation based method for the QoS routing problem', Proc. IEEE INFOCOM, 2001, 2, Anchorage, AK, USA, p. 859–869.
    16. 16)
      • T. Magnanti , R. Ahuja , J. Orlin . (1993) Network flows—theory, algorithms, and applications.
    17. 17)
      • K. Altinkemer , B. Gavish . Heuristics for delivery problems with constant error guarantees. Trans. Sci. , 4 , 294 - 297
    18. 18)
    19. 19)
      • M. Haimovich , R. Kan . Bounds and heuristics for capacitated routing problems. Math. Oper. Res. , 4 , 527 - 542
    20. 20)
      • Bejerano, Y., Breitbart, M., Rastogi, R.: `Physical topology discovery for large multi subnet networks', INFOCOM, 2003, 1, San Francisco, CA, USA, p. 342–352.
    21. 21)
      • Huffaker, B., Plummer, D., Moore, D., Claffy, K.: `Topology discovery by active probing', Applications and the Internet (SAINT) Workshops, 2000, Nara City, Nara, Japan, p. 90–96.
    22. 22)
      • D. Reeves , H. Salama . A distributed algorithm for delay-constrained unicast routing. IEEE/ACM Trans. Netw. , 2 , 239 - 250
    23. 23)
    24. 24)
      • Lee, Y., Atiquzzamman, M.: `Optimal delay-constrained minimum cost loop algorithm for local computer network', Proc. 10th IEEE Symp. on Computers and Communications, IEEE Computer Society, 2005, Cantagena, Murcia, Spain, p. 501–506.

Related content

This is a required field
Please enter a valid email address