Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

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
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

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
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
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.

© The Institution of Engineering and Technology
Published

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.

Inspec keywords: telecommunication network topology; multimedia communication; computer networks; broadcasting

Other keywords: traffic capacity; exact topology discovery algorithm; capacity constrained loop network; multimedia traffic; delay constrained loop network; DC-MCLP; source node; broadcast loops; traffic capacity constraint

Subjects: Multimedia; Communication network design, planning and routing; Computer communications; Computer networks and techniques; Multimedia communications

References

    1. 1)
      • 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.
    2. 2)
      • 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.
    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)
      • Breibart, Y., Garofalakis, M., Martin, C., Seshadri, S., Silberschatz, A.: `Topology discovery in heterogeneous IP networks', INFOCOM, 2000, p. 265–274.
    5. 5)
      • A. Kershenbaum . (1993) , Telecommunication network design algorithm.
    6. 6)
    7. 7)
      • Astic, I., Festor, O.: `A hierarchical topology discovery service for IPv6 networks', IEEE/IFIP Network Operations and Management Symp., 2002, p. 497–510.
    8. 8)
    9. 9)
      • D. Reeves , H. Salama . A distributed algorithm for delay-constrained unicast routing. IEEE/ACM Trans. Netw. , 2 , 239 - 250
    10. 10)
      • Lin, H., Lai, S., Chen, P.: `An algorithm for automatic topology discovery of IP networks', IEEE Int. Conf. on Communication, 1998, p. 1192–1196.
    11. 11)
      • Bejerano, Y., Breitbart, M., Rastogi, R.: `Physical topology discovery for large multi subnet networks', INFOCOM, 2003, 1, San Francisco, CA, USA, p. 342–352.
    12. 12)
      • 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.
    13. 13)
      • J. Lenster , R. Kan . Complexity of vehicle routing and scheduling problems. Networks , 221 - 227
    14. 14)
    15. 15)
    16. 16)
      • Y. Lee . Minimal cost heuristic algorithm for delay constrained loop network. Int. J. Comput. Syst. Sci. Eng. , 4 , 209 - 219
    17. 17)
    18. 18)
      • T. Magnanti , R. Ahuja , J. Orlin . (1993) Network flows—theory, algorithms, and applications.
    19. 19)
      • M. Haimovich , R. Kan . Bounds and heuristics for capacitated routing problems. Math. Oper. Res. , 4 , 527 - 542
    20. 20)
      • K. Altinkemer , B. Gavish . Heuristics for delivery problems with constant error guarantees. Trans. Sci. , 4 , 294 - 297
    21. 21)
      • 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.
    22. 22)
      • G. Cheng , N. Ansari . Finding all hop(s) shortest path. IEEE Commun. Lett. , 2 , 122 - 124
    23. 23)
      • 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.
    24. 24)
      • 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.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com_20050063
Loading

Related content

content/journals/10.1049/iet-com_20050063
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address