{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:39:35Z","timestamp":1750307975379,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["___amp___num;313083___amp___num;344619"],"award-info":[{"award-number":["___amp___num;313083___amp___num;344619"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Multimedia Comput. Commun. Appl."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>\n            We present optimal schemes for allocating bits of fine-grained scalable video sequences among multiple senders streaming to a single receiver. This allocation problem is critical in optimizing the perceived quality in peer-to-peer and distributed multi-server streaming environments. Senders in such environments are heterogeneous in their outgoing bandwidth and they hold different portions of the video stream. We first formulate and optimally solve the problem for individual frames, then we generalize to the multiple frame case. Specifically, we formulate the allocation problem as an optimization problem, which is nonlinear in general. We use rate-distortion models in the formulation to achieve the minimum distortion in the rendered video, constrained by the outgoing bandwidth of senders, availability of video data at senders, and incoming bandwidth of receiver. We show how the adopted rate-distortion models transform the nonlinear problem to an integer linear programming (ILP) problem. We then design a simple rounding scheme that transforms the ILP problem to a linear programming (LP) one, which can be solved efficiently using common optimization techniques such as the Simplex method. We prove that our rounding scheme always produces a feasible solution, and the solution is within a negligible margin from the optimal solution. We also propose a new algorithm (FGSAssign) for the single-frame allocation problem that runs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) steps, where\n            <jats:italic>n<\/jats:italic>\n            is the number of senders. We prove that FGSAssign is optimal. Furthermore, we propose a heuristic algorithm (mFGSAssign) that produces near-optimal solutions for the multiple-frame case, and runs an order of magnitude faster than the optimal one. Because of its short running time, mFGSAssign can be used in real time. Our experimental study validates our analytical analysis and shows the effectiveness of our allocation algorithms in improving the video quality.\n          <\/jats:p>","DOI":"10.1145\/1324287.1324289","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Rate-distortion optimized streaming of fine-grained scalable video sequences"],"prefix":"10.1145","volume":"4","author":[{"given":"Mohamed","family":"Hefeeda","sequence":"first","affiliation":[{"name":"Simon Fraser University, Surrey BC, Canada"}]},{"given":"Cheng-Hsin","family":"Hsu","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Surrey BC, Canada"}]}],"member":"320","published-online":{"date-parts":[[2008,2,11]]},"reference":[{"volume-title":"Proceedings of the IEEE International Conference on Image Processing (ICIP'03)","author":"Begen A.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the Data Compression Conference (DCC'03)","author":"Chakareski J.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2005.864313"},{"key":"e_1_2_1_4_1","unstructured":"Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms 2nd ed. MIT Press Cambridge MA.   Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms 2nd ed. MIT Press Cambridge MA."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/776322.776348"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/776322.776333"},{"volume-title":"Proceedings of the IEEE International Conference on Image Processing (ICIP'04)","author":"Dai M.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/dac.v18:5"},{"key":"e_1_2_1_9_1","first-page":"73","article-title":"Linear programming","volume":"1","author":"Goldfarb D.","year":"1989","journal-title":"Handbook Oper. Res. Manage. Sci. Optimiz."},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"CollectCast: A peer-to-peer service for media streaming","volume":"11","author":"Hefeeda M.","year":"2005","journal-title":"ACM\/Springer Multimed. Syst. J."},{"volume-title":"Tech. Rep. TR 2006-12","year":"2006","author":"Hsu C.","key":"e_1_2_1_11_1"},{"volume-title":"Tech. Rep. TR 2006-20","year":"2006","author":"Hsu C.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","unstructured":"ISO\/IEC 14496-2. 2004. Coding of audio-visual objects - Part 2: Visual.  ISO\/IEC 14496-2. 2004. Coding of audio-visual objects - Part 2: Visual."},{"key":"e_1_2_1_14_1","unstructured":"ISO\/IEC 14496-5. 2004. MPEG-4 Visual reference software.  ISO\/IEC 14496-5. 2004. MPEG-4 Visual reference software."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/76.911157"},{"key":"e_1_2_1_16_1","first-page":"6","article-title":"Adaptive receiver-driven streaming from multiple senders","volume":"11","author":"Magharei N.","year":"2006","journal-title":"ACM\/Springer Multimed. Syst. J."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00158-003-0368-6"},{"volume-title":"Proceedings of the Multimedia Computing and Networking (MMCN'02)","author":"Nguyen T.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C.","year":"1998","edition":"1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/6046.909594"},{"volume-title":"Proceedings of the European Symposium on Mobile Media Delivery (EuMob'06)","author":"Schwarz H.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the Data Compression Conference (DCC'03)","author":"Sermadevi Y.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","first-page":"5","article-title":"Sequence of linear programming for transmission of fine-scalable coded content in bandwidth-limited environments","volume":"11","author":"Su X.","year":"2006","journal-title":"ACM\/Springer Multimed. Syst. J."},{"volume-title":"Proceedings of the SPIE International Conference on Visual Communication and Image Processing (VCIP'05)","author":"Sun J.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","unstructured":"Wang Y. Ostermann J. and Zhang Y. 2002. Video Processing and Communications. Prentice Hall Englewood Cliffs NJ.   Wang Y. Ostermann J. and Zhang Y. 2002. Video Processing and Communications. Prentice Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_26_1","unstructured":"Web Page of Network Systems Lab. 2006. http:\/\/nsl.cs.surrey.sfu.ca\/projects\/fgs\/.  Web Page of Network Systems Lab. 2006. http:\/\/nsl.cs.surrey.sfu.ca\/projects\/fgs\/."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSVT.2002.808437"},{"volume-title":"Proceedings of the the IEEE International Workshop on Quality of Service (IWQoS'03)","author":"Zink M.","key":"e_1_2_1_28_1"}],"container-title":["ACM Transactions on Multimedia Computing, Communications, and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324287.1324289","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1324287.1324289","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:58:26Z","timestamp":1750258706000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324287.1324289"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1145\/1324287.1324289"],"URL":"https:\/\/doi.org\/10.1145\/1324287.1324289","relation":{},"ISSN":["1551-6857","1551-6865"],"issn-type":[{"type":"print","value":"1551-6857"},{"type":"electronic","value":"1551-6865"}],"subject":[],"published":{"date-parts":[[2008,1]]},"assertion":[{"value":"2006-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}