© The Institution of Engineering and Technology
We have developed an exact model and algorithm for the delayconstrained minimum cost loop problem (DCMCLP) 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 DCMCLP deals with the mean network delay and traffic capacity constraints simultaneously. The DCMCLP consists of finding a set of minimum cost loops to link enduser nodes to a source node satisfying the traffic requirements at endnodes and the required mean delay of the network. In the DCMCLP, the objective function is to minimise the total link cost. We have formulated the DCMCLP 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 realtime multimedia traffic.
References


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)

Breibart, Y., Garofalakis, M., Martin, C., Seshadri, S., Silberschatz, A.: `Topology discovery in heterogeneous IP networks', INFOCOM, 2000, p. 265–274.

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)

Lin, H., Wang, Y., Wang, C., Chen, C.: `Webbased distributed topology discovery of IP networks', 15thInt. Conf. on Information Networking, 2001, p. 857–862.

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)

A. Kershenbaum
.
(1993)
, Telecommunication network design algorithm.

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)

B. Gavish
.
Topological design of telecommunication networkslocal access design methods.
Ann. Oper. Res.
,
17 
71

9)

Y. Lee
.
Minimal cost heuristic algorithm for delay constrained loop network.
Int. J. Comput. Syst. Sci. Eng.
,
4 ,
209 
219

10)

J. Lenster ,
R. Kan
.
Complexity of vehicle routing and scheduling problems.
Networks
,
221 
227

11)

G. Cheng ,
N. Ansari
.
On multiple additively constrained path selection.
IEE Proc., Commun.
,
5 ,
237 
241

12)

G. Cheng ,
N. Ansari
.
Finding all hop(s) shortest path.
IEEE Commun. Lett.
,
2 ,
122 
124

13)

S. Chen ,
K. Nahrstedt
.
An overview of quality of service routing for nextgeneration highspeed networks: problems and solutions.
IEEE Netw.
,
6 ,
64 
79

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)

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)

T. Magnanti ,
R. Ahuja ,
J. Orlin
.
(1993)
Network flows—theory, algorithms, and applications.

17)

K. Altinkemer ,
B. Gavish
.
Heuristics for delivery problems with constant error guarantees.
Trans. Sci.
,
4 ,
294 
297

18)

N. Christofides ,
A. Mingozzi ,
P. Toth
.
Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxations.
Math. Program.
,
255 
282

19)

M. Haimovich ,
R. Kan
.
Bounds and heuristics for capacitated routing problems.
Math. Oper. Res.
,
4 ,
527 
542

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)

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)

D. Reeves ,
H. Salama
.
A distributed algorithm for delayconstrained unicast routing.
IEEE/ACM Trans. Netw.
,
2 ,
239 
250

23)

W. Zhengying ,
S. Bingxin ,
Z. Ling
.
A delayconstrained leastcost multicast routing heuristic for dynamic multicast groups.
Electron. Commer. Res.
,
323 
335

24)

Lee, Y., Atiquzzamman, M.: `Optimal delayconstrained 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.
http://iet.metastore.ingenta.com/content/journals/10.1049/ietcom_20050063
Related content
content/journals/10.1049/ietcom_20050063
pub_keyword,iet_inspecKeyword,pub_concept
6
6