@article {12378,
	title = {Contention-conscious transaction ordering in multiprocessor DSP systems},
	journal = {IEEE Transactions on Signal Processing},
	volume = {54},
	year = {2006},
	month = {2006/02//},
	pages = {556 - 569},
	abstract = {This paper explores the problem of efficiently ordering interprocessor communication (IPC) operations in statically scheduled multiprocessors for iterative dataflow graphs. In most digital signal processing (DSP) applications, the throughput of the system is significantly affected by communication costs. By explicitly modeling these costs within an effective graph-theoretic analysis framework, we show that ordered transaction schedules can significantly outperform self-timed schedules even when synchronization costs are low. However, we also show that when communication latencies are nonnegligible, finding an optimal transaction order given a static schedule is an NP-complete problem, and that this intractability holds both under iterative and noniterative execution. We develop new heuristics for finding efficient transaction orders, and perform an extensive experimental comparison to gauge the performance of these heuristics.},
	keywords = {contention-conscious transaction ordering, Costs, data flow graphs, Dataflow, Delay, Digital signal processing, digital signal processing chips, Embedded system, graph-theoretic analysis, Instruments, Internet telephony, interprocessor communication, iterative dataflow graphs, iterative methods, Message passing, multiprocessor, multiprocessor DSP systems, NP-complete problem, Processor scheduling, scheduling, Signal processing, synchronization, Throughput},
	isbn = {1053-587X},
	doi = {10.1109/TSP.2005.861074},
	author = {Khandelia,M. and Bambha,N. K and Bhattacharyya, Shuvra S.}
}
@conference {17588,
	title = {Efficient algorithms for location and sizing problems in network design},
	booktitle = {IEEE Global Telecommunications Conference, 2001. GLOBECOM {\textquoteright}01},
	volume = {4},
	year = {2001},
	month = {2001///},
	pages = {2586-2590 vol.4 - 2586-2590 vol.4},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Large-scale location, sizing and homing problems of distributed network elements, have received much attention recently due to the massive deployment of broadband communication networks for services like Internet telephony and Web caching. Key considerations in designing these networks include modularity of capacity, economies of scale in cost, and reliability. We formulate a general class of such network design problems as Mixed-Integer Programs. These problems are computationally intractable in general; under various asymptotic conditions, we show how to compute near-optimal solutions. To deal with arbitrary instances, we develop new algorithms based on linear programming, as well as greedy randomized adaptive search. These algorithms achieved near-optimal solutions with reasonable computation time for our experiments},
	keywords = {Algorithm design and analysis, Broadband communication, broadband communication networks, broadband networks, capacity modularity, Communication networks, computer network reliability, distributed network elements, Economies of scale, greedy randomized adaptive search, homing, integer programming, Intelligent networks, Internet telephony, large-scale location problems, Large-scale systems, Linear programming, mixed-integer programs, near-optimal solutions, network design, Optical switches, randomised algorithms, reliability, search problems, sizing, Technological innovation, telecommunication network planning, Web caching},
	isbn = {0-7803-7206-9},
	doi = {10.1109/GLOCOM.2001.966243},
	author = {Kumaran,K. and Srinivasan, Aravind and Qiong Wang and Lanning,S. and Ramakrishnan,K. G}
}
@conference {17640,
	title = {Optimal design of signaling networks for Internet telephony},
	booktitle = {IEEE INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings},
	volume = {2},
	year = {2000},
	month = {2000///},
	pages = {707-716 vol.2 - 707-716 vol.2},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We present an approach for efficient design of a signaling network for a network of software switches supporting Internet telephony. While one may take an integer programming approach to solve this problem, it quickly becomes intractable even for modest-sized networks. Instead, our topology design uses random graphs that we show to be nearly optimal in cost, highly connected, and computationally efficient even for large networks. We then formulate a quadratic assignment problem (QAP) to map the abstract topology into the physical network to achieve optimal load balancing for given demand forecasts, which we solve using randomized heuristics. Numerical results on several example networks illustrate the performance and computational efficiency of our method. A graphical design tool has been developed based on our algorithms},
	keywords = {bandwidth allocation, Computational efficiency, Computer networks, Cost function, Demand forecasting, demand forecasts, graph theory, graphical design tool, Internet telephony, Linear programming, Load forecasting, Load management, Network topology, optimal design, optimal load balancing, optimisation, performance, quadratic assignment problem, random graphs, randomised algorithms, randomized heuristics, Signal design, signaling networks, Switches, telecommunication signalling, topology design},
	isbn = {0-7803-5880-5},
	doi = {10.1109/INFCOM.2000.832245},
	author = {Srinivasan, Aravind and Ramakrishnan,K. G and Kumaran,K. and Aravamudan,M. and Naqvi,S.}
}
