Cálculo da Distribuição da Banda para Servidores de Vídeo
Resumo
Diversas técnicas de compartilhamento de banda têm sido propostas para aumentar a escalabilidade de servidores de vídeo. A técnica patching tem sido usada por sua simplicidade e eficiência em termos de requisitos de banda média. No entanto, o conhecimento da banda média nem sempre permite alocar banda aos clientes com o objetivo de prover uma certa qualidade. Neste trabalho é então proposto um modelo para obtenção da distribuição do número de fluxos gerados pela técnica patching, ou seja, a distribuição da banda. Além disso, mostramos a utilização desta distribuição para reservar banda de forma a prover uma determinada qualidade, prever a qualidade oferecida caso ocorra uma mudança nos valores dos parâmetros do sistema, e dimensionar o servidor.Referências
C. C. Aggarwal, J. L. Wolf, and P. S. Yu. On optimal piggyback merging policies for video-on-demand systems. In Proc. 1996 ACM SIGMETRICS Conf. On Measurement and Modeling of Computer Systems, pages 200–209, 1996.
Jussara M. Almeida, J. Krueger, Derek L. Eager, and Mary K. Vernon. Analysis of educational media server workloads. In Proc. 11th Int’l Workshop Network and Operating Systems Support for Digital Audio and Video (NOSSDAV’01), pages 21–30, June 2001.
K. C. Almeroth and M. H. Ammar. The use of multicast delivery to provide a scalable and interactive video-on-demand service. IEEE Journal on Selected Areas in Communications, 14(5):1110–22, August 1996.
A. Bar-Noy, G. Goshi, R. E. Ladner, and K. Tam. Comparison of stream merging algorithms for media-on-demand. In Proc. of MMCN 2002, San Jose, CA, Jan 2002.
A. Bar-Noy and R. E. Ladner. Competitive on-line stream merging algorithms for media-on-demand. In Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 364–373, 2001.
A. Bar-Noy and R. E. Ladner. Efficient algorithms for optimal stream merging for media-on-demand. To appear in SIAM Journal on Computing, 2001.
A. Borodin and R. El-Yaniv. On-line computation and competitive Analysis. Cambridge University Press, The Pitt Building, Trumpington Street, Cambridge, United Kingdom, 1998.
M. K. Bradshaw, B. Wang, S. Sen, L. Gao, J. Kurose, P. Shenoy, and D. Towsley. Periodic broadcast and patching services - implementation, measurement and analysis in an internet streaming video testbed. ACM Multimedia Journal SI on Multimedia Distribution, 2003.
E. O. Brigham. The Fast Fourier Transform and its applications. Prentice-Hall, Inc., New Jersey, 1988.
Y. Cai, K. Hua, and K. Vu. Optimizing Patching Performance. In Proc. SPIE/ACM Conference on Multimedia Computing and Networking, 1999.
Y. Cai and K. A. Hua. An efficient bandwidth-sharing technique for true video on demand systems. In Proc. of the 7th ACM Int’l Multimedia Conference (ACM Multimedia’99), pages 211–214, Nov 1999.
R.M.L.R. Carmo, L.R. de Carvalho, E. de Souza e Silva, M.C. Diniz, and R.R. Muntz. Performance/Availability Modeling with the TANGRAM-II Modeling Environment. Performance Evaluation, 33:45–65, 1998.
Y. Chai, K. Hua, and K. Vu. Optimizing patching performance. In Proc. SPIE/ACM Conference on Multimedia Computing and Networking, Jan 1999.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. A 5-competitive on-line scheduler for merging video streams. In Proc. of the 15th Int’l Parallel and Distributed Processing Symposium, 2001.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. Competitive analysis of on-line stream merging algorithms. In Proc. of the 27th Int’l Symposium on Mathematical Foundations of Computer Science (MFCS), pages 188–200, 2002.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. A unified analysis of hot video schedulers. In Proc. of the 34th ACM Symposium on Theory of Computing (STOC), pages 179–188, 2002.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. On-line stream merging in a general setting. Theoretical Computer Science, 296(1):27–46, 2003.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. On-line stream merging, max span, and min coverage. In Proc. of the 5th Conference on Algorithms and Complexity (CIAC), pages 337–346, 2003.
A. L. Chervenak. Tertiary storage: An evaluation of new applications, 1994. Ph.D Thesis, CSD, University of California at Berkeley.
M. Chesire, A. Wolman, G. Voelker, and H. Levy. Measurement and analysis of a streaming-media workload. In USENIX Symposium on Internet Technologies and Systems (USITS), 2001.
E. de Souza e Silva and R.M.M. Leão. Modelagem e Análise de Redes com o Conjunto de Ferramentas TANGRAM II. In XXI Simpósio Brasileiro de Redes de Computadores(Workshop de Ferramentas), pages 897–904, Natal, Brasil, Maio 2003.
Edmundo de Souza e Silva, Rosa M.M. Leão, and Morganna C. Diniz. The Required Capacity Distribution for the Patching Bandwidth Sharing Technique. In Proc. of IEEE ICC2004, May 2004.
D. Eager, M. Vernon, and J. Zahorjan. Bandwidth skimming: A technique for cost-effective video-on-demand. In Proc. 2000 Multimedia Computing and Networking, Jan 2000.
D. Eager, M. Vernon, and J. Zahorjan. Optimal and efficient merging schedules for video-on-demand servers. In Proc. 7th ACM Int’l Multimedia Conference (ACM Multimedia’99), pages 80–87, Nov 1999.
D. Eager, M. Vernon, and J. Zahorjan. Minimizing bandwidth requirements for on-demand data delivery. In Proc. 5th Int’l Workshop on Multimedia Information Systems (MIS’99), Oct 1999.
D. L. Eager, M. C. Ferris, and M. Vernon. Optimized regional caching for on-demand data delivery. In Proc. ISET/SPIE Conf. Multimedia Computing and Networking (MMCN’99), pages 301–316, Jan 1999.
L. Gao and D. Towsley. Supplying instantaneous video-on-demand services using controlled multicast. In Proc. IEEE Multimedia Computing Systems’99, June 1999.
Carsten Griwodz, Michael Liepert, Michael Zink, and Ralf Steinmetz. A two-level patching scheme for video-on-demand delivery. ACM SIGMETRICS Performance Evaluation Review, 27(4):20–26, 2000.
Dongliang Guan and Songyu Yu. A two-level patching scheme for video-on-demand delivery. IEEE Transactions on Broadcasting, 50(1):11–15, March 2004.
Y. Guo, K. Suh, J. Kurose, and D. Towsley. P2cast: peer-to-peer patching scheme for VoD service. In Proc. of the 12th World Wide Web Conference (WWW-03), May 2003.
Ailan Hu. Video-on-demand broadcasting protocols: A comprehensive study. In Proc. IEEE Infocom, pages 508–517, 2001.
K. Hua and S. Sheu. Skyscraper broadcasting: A new broadcasting scheme for metropolitan video-on-demand systems. In Proc. ACM SIGCOMM, Sept 1997.
K. A. Hua, Y. Cai, and S. Sheu. Patching: A multicast technique for true video-on-demand services. In Proc. 6th ACM Int’l Multimedia Conf. (ACM MULTIMEDIA’98), pages 191–200, 1998.
E. G. Coffman Jr., P. Jelenkovic, and P. Momcilovic. Provably efficient stream merging. In Proc. of 6th Int’l Workshop on Web caching and Content Distribution, June 2001.
L. Juhn and L. Tseng. Fast data broadcasting and receiving scheme for popular video service. In IEEE Transactions on Broadcasting, 44(1):100–105, Mar 1998.
L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Transactions on Broadcasting, 43(3):268–271, Sept 1997.
Leonard Kleinrock. Queueing Systems, volume 1: Theory. John Wiley & Sons, New York, 1975.
Huadong Ma and Kang G. Shin. Multicast video-on-demand services. ACM SIGCOMM Computer Communication Review, 32(1), 2002.
J.-F. Paris, S. W. Carter, and D. D. E. Long. A low bandwidth broadcasting protocol for video on demand. In Proc. of IEEE Int’l Conference on Computer Communications and Networks (IC3N’98), 1998.
J.-F. Paris, S. W. Carter, and D. D. E. Long. A hybrid broadcasting protocol for video on demand. In Proc. 1999 Multimedia Computing Networking Conference (MMCN’99), Jan 1999.
J.-F. Paris, S. W. Carter, and D. D. E. Long. A simple low-bandwidth broadcasting protocol for video on demand. In Proc. 8th Int’l Conference on Computer Communications and Networks (IC3N’99), pages 118–123, October 1999.
Carlo K. S. Rodrigues and Rosa M. M. Leão. Bandwidth usage distribution of VoD servers using patching. Technical report, COPPE UFRJ, 2004.
S. Sen, L. Gao, J. Rexford, and D. Towsley. Optimal patching schemes for efficient multimedia streaming. In Proc. 9th Int’l Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV’99), June 1999.
H. Tan, D. Eager, M. Vernon, and H. Guo. Quality of service evaluations of multicast streaming protocols. In Proc. ACM SIMETRICS 2002. Int’l Conference on Measurement and Modeling of Computer Systems, June 2002.
Kishor S. Trivedi. Probability and Statistics with Reliability, Queuing and Computer Science Applications. John Wiley & Sons, Inc., second edition, New York, 2002.
S. Viswanathan and T. Imielinski. Pyramid broadcasting for video-on-demand service. In Proc. of the SPIE Multimedia Computing and Networking Conference, 2417:66–77, Feb 1995.
Y. W. Wong and Jack Y. B. Lee. Recursive Patching - An efficient technique for multicast video streaming. In Proc. 5th International Conference on Enterprise Information Systems (ICEIS) 2003, pages 23–26, Angers, France, April 2003.
R.M. Zafalão, N.L.S. Fonseca, and C.C. de Souza. The Polyharmonic Broadcasting Protocol subject to Bandwidth Constraints. In Brazilian Computer Networks Conference, pages 397–410, 2003. In Portuguese.
G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, Cambridge, MA, 1949.
Jussara M. Almeida, J. Krueger, Derek L. Eager, and Mary K. Vernon. Analysis of educational media server workloads. In Proc. 11th Int’l Workshop Network and Operating Systems Support for Digital Audio and Video (NOSSDAV’01), pages 21–30, June 2001.
K. C. Almeroth and M. H. Ammar. The use of multicast delivery to provide a scalable and interactive video-on-demand service. IEEE Journal on Selected Areas in Communications, 14(5):1110–22, August 1996.
A. Bar-Noy, G. Goshi, R. E. Ladner, and K. Tam. Comparison of stream merging algorithms for media-on-demand. In Proc. of MMCN 2002, San Jose, CA, Jan 2002.
A. Bar-Noy and R. E. Ladner. Competitive on-line stream merging algorithms for media-on-demand. In Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 364–373, 2001.
A. Bar-Noy and R. E. Ladner. Efficient algorithms for optimal stream merging for media-on-demand. To appear in SIAM Journal on Computing, 2001.
A. Borodin and R. El-Yaniv. On-line computation and competitive Analysis. Cambridge University Press, The Pitt Building, Trumpington Street, Cambridge, United Kingdom, 1998.
M. K. Bradshaw, B. Wang, S. Sen, L. Gao, J. Kurose, P. Shenoy, and D. Towsley. Periodic broadcast and patching services - implementation, measurement and analysis in an internet streaming video testbed. ACM Multimedia Journal SI on Multimedia Distribution, 2003.
E. O. Brigham. The Fast Fourier Transform and its applications. Prentice-Hall, Inc., New Jersey, 1988.
Y. Cai, K. Hua, and K. Vu. Optimizing Patching Performance. In Proc. SPIE/ACM Conference on Multimedia Computing and Networking, 1999.
Y. Cai and K. A. Hua. An efficient bandwidth-sharing technique for true video on demand systems. In Proc. of the 7th ACM Int’l Multimedia Conference (ACM Multimedia’99), pages 211–214, Nov 1999.
R.M.L.R. Carmo, L.R. de Carvalho, E. de Souza e Silva, M.C. Diniz, and R.R. Muntz. Performance/Availability Modeling with the TANGRAM-II Modeling Environment. Performance Evaluation, 33:45–65, 1998.
Y. Chai, K. Hua, and K. Vu. Optimizing patching performance. In Proc. SPIE/ACM Conference on Multimedia Computing and Networking, Jan 1999.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. A 5-competitive on-line scheduler for merging video streams. In Proc. of the 15th Int’l Parallel and Distributed Processing Symposium, 2001.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. Competitive analysis of on-line stream merging algorithms. In Proc. of the 27th Int’l Symposium on Mathematical Foundations of Computer Science (MFCS), pages 188–200, 2002.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. A unified analysis of hot video schedulers. In Proc. of the 34th ACM Symposium on Theory of Computing (STOC), pages 179–188, 2002.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. On-line stream merging in a general setting. Theoretical Computer Science, 296(1):27–46, 2003.
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, and Wai-Ha Wong. On-line stream merging, max span, and min coverage. In Proc. of the 5th Conference on Algorithms and Complexity (CIAC), pages 337–346, 2003.
A. L. Chervenak. Tertiary storage: An evaluation of new applications, 1994. Ph.D Thesis, CSD, University of California at Berkeley.
M. Chesire, A. Wolman, G. Voelker, and H. Levy. Measurement and analysis of a streaming-media workload. In USENIX Symposium on Internet Technologies and Systems (USITS), 2001.
E. de Souza e Silva and R.M.M. Leão. Modelagem e Análise de Redes com o Conjunto de Ferramentas TANGRAM II. In XXI Simpósio Brasileiro de Redes de Computadores(Workshop de Ferramentas), pages 897–904, Natal, Brasil, Maio 2003.
Edmundo de Souza e Silva, Rosa M.M. Leão, and Morganna C. Diniz. The Required Capacity Distribution for the Patching Bandwidth Sharing Technique. In Proc. of IEEE ICC2004, May 2004.
D. Eager, M. Vernon, and J. Zahorjan. Bandwidth skimming: A technique for cost-effective video-on-demand. In Proc. 2000 Multimedia Computing and Networking, Jan 2000.
D. Eager, M. Vernon, and J. Zahorjan. Optimal and efficient merging schedules for video-on-demand servers. In Proc. 7th ACM Int’l Multimedia Conference (ACM Multimedia’99), pages 80–87, Nov 1999.
D. Eager, M. Vernon, and J. Zahorjan. Minimizing bandwidth requirements for on-demand data delivery. In Proc. 5th Int’l Workshop on Multimedia Information Systems (MIS’99), Oct 1999.
D. L. Eager, M. C. Ferris, and M. Vernon. Optimized regional caching for on-demand data delivery. In Proc. ISET/SPIE Conf. Multimedia Computing and Networking (MMCN’99), pages 301–316, Jan 1999.
L. Gao and D. Towsley. Supplying instantaneous video-on-demand services using controlled multicast. In Proc. IEEE Multimedia Computing Systems’99, June 1999.
Carsten Griwodz, Michael Liepert, Michael Zink, and Ralf Steinmetz. A two-level patching scheme for video-on-demand delivery. ACM SIGMETRICS Performance Evaluation Review, 27(4):20–26, 2000.
Dongliang Guan and Songyu Yu. A two-level patching scheme for video-on-demand delivery. IEEE Transactions on Broadcasting, 50(1):11–15, March 2004.
Y. Guo, K. Suh, J. Kurose, and D. Towsley. P2cast: peer-to-peer patching scheme for VoD service. In Proc. of the 12th World Wide Web Conference (WWW-03), May 2003.
Ailan Hu. Video-on-demand broadcasting protocols: A comprehensive study. In Proc. IEEE Infocom, pages 508–517, 2001.
K. Hua and S. Sheu. Skyscraper broadcasting: A new broadcasting scheme for metropolitan video-on-demand systems. In Proc. ACM SIGCOMM, Sept 1997.
K. A. Hua, Y. Cai, and S. Sheu. Patching: A multicast technique for true video-on-demand services. In Proc. 6th ACM Int’l Multimedia Conf. (ACM MULTIMEDIA’98), pages 191–200, 1998.
E. G. Coffman Jr., P. Jelenkovic, and P. Momcilovic. Provably efficient stream merging. In Proc. of 6th Int’l Workshop on Web caching and Content Distribution, June 2001.
L. Juhn and L. Tseng. Fast data broadcasting and receiving scheme for popular video service. In IEEE Transactions on Broadcasting, 44(1):100–105, Mar 1998.
L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Transactions on Broadcasting, 43(3):268–271, Sept 1997.
Leonard Kleinrock. Queueing Systems, volume 1: Theory. John Wiley & Sons, New York, 1975.
Huadong Ma and Kang G. Shin. Multicast video-on-demand services. ACM SIGCOMM Computer Communication Review, 32(1), 2002.
J.-F. Paris, S. W. Carter, and D. D. E. Long. A low bandwidth broadcasting protocol for video on demand. In Proc. of IEEE Int’l Conference on Computer Communications and Networks (IC3N’98), 1998.
J.-F. Paris, S. W. Carter, and D. D. E. Long. A hybrid broadcasting protocol for video on demand. In Proc. 1999 Multimedia Computing Networking Conference (MMCN’99), Jan 1999.
J.-F. Paris, S. W. Carter, and D. D. E. Long. A simple low-bandwidth broadcasting protocol for video on demand. In Proc. 8th Int’l Conference on Computer Communications and Networks (IC3N’99), pages 118–123, October 1999.
Carlo K. S. Rodrigues and Rosa M. M. Leão. Bandwidth usage distribution of VoD servers using patching. Technical report, COPPE UFRJ, 2004.
S. Sen, L. Gao, J. Rexford, and D. Towsley. Optimal patching schemes for efficient multimedia streaming. In Proc. 9th Int’l Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV’99), June 1999.
H. Tan, D. Eager, M. Vernon, and H. Guo. Quality of service evaluations of multicast streaming protocols. In Proc. ACM SIMETRICS 2002. Int’l Conference on Measurement and Modeling of Computer Systems, June 2002.
Kishor S. Trivedi. Probability and Statistics with Reliability, Queuing and Computer Science Applications. John Wiley & Sons, Inc., second edition, New York, 2002.
S. Viswanathan and T. Imielinski. Pyramid broadcasting for video-on-demand service. In Proc. of the SPIE Multimedia Computing and Networking Conference, 2417:66–77, Feb 1995.
Y. W. Wong and Jack Y. B. Lee. Recursive Patching - An efficient technique for multicast video streaming. In Proc. 5th International Conference on Enterprise Information Systems (ICEIS) 2003, pages 23–26, Angers, France, April 2003.
R.M. Zafalão, N.L.S. Fonseca, and C.C. de Souza. The Polyharmonic Broadcasting Protocol subject to Bandwidth Constraints. In Brazilian Computer Networks Conference, pages 397–410, 2003. In Portuguese.
G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, Cambridge, MA, 1949.
Publicado
31/07/2004
Como Citar
RODRIGUES, Carlo Kleber da S.; LEÃO, Rosa Maria Meri.
Cálculo da Distribuição da Banda para Servidores de Vídeo. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 3. , 2004, Salvador/BA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2004
.
p. 156-174.
ISSN 2595-6167.
