# US 8,473,998 B1 · Network coding for multi-resolution multicast > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,473,998 B1 - Document ID: US8473998B1 - Status: Granted - Kind: B1 - Application number: 12/846,292 - Filed: 2010-07-29 - Granted: 2013-06-25 - Earliest claimed: 2009-07-29 - Assignees: Massachusetts Institute of Technology - Applicants: Daniel E. Lucani; Minji Kim; Fang Zhao; Xiaomeng Shi; Muriel Medard; Marie-Jose Montpetit - Inventors: Daniel E. Lucani; Minji Kim; Fang Zhao; Xiaomeng Shi; Muriel Medard; Marie-Jose Montpetit - Web page: https://patentgrep.com/patent/US8473998B1 ## CPC - H04N 21/440227: {by decomposing into layers, e.g. base layer and one or more enhancement layers} - H04L 12/1859: {adapted to provide push services, e.g. data channels} - H04N 21/234327: {by decomposing into layers, e.g. base layer and one or more enhancement layers} - H04N 21/234363: {by altering the spatial resolution, e.g. for clients with a lower screen resolution} - H04N 21/437: Interfacing the upstream path of the transmission network, e.g. for transmitting client requests to a VOD server {(flow control in data networks H04L47/10; streaming protocols, e.g. RTP or RTCP, H04L65/65; scheduling or organising the servicing of application requests in data packet switching networks H04L67/60)} - H04N 21/6371: directed to network - H04N 21/6405: Multicasting {(data broadcast and multicast in packet switching networks H04L12/18)} - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method, apparatus and computer program product for utilizing network coding for multi-resolution multicast is presented. A network source partitions source content into a base layer and one or more refinement layers. The network source receives a respective one or more push-back messages from one or more network destination receivers, the push-back messages identifying the one or more refinement layers suited for each one of the one or more network destination receivers. The network source computes a network code involving the base layer and the one or more refinement layers for at least one of the one or more network destination receivers, and transmits the network code to the one or more network destination receivers in accordance with the push-back messages. ## Claims ### Claim 1 A method of network coding comprising: partitioning, at a network source, source content into a base layer and one or more refinement layers, wherein the base layer provides a lowest resolution associated with the source content and the one or more refinement layers provide a respective one or more resolutions associated with the source content that are at respective higher resolutions than the base layer, wherein the one or more refinement layers are at a respective one or more progressively higher resolutions; receiving, at said network source, a respective one or more push-back messages from one or more network destination receivers; computing, at said network source, a network code involving said base layer and said one or more refinement layers for at least one of said one or more network destination receivers, wherein said network code comprises a random linear network code, said random linear network code comprising random linear combinations of at least a portion of said base layer and zero or more of said refinement layers; and transmitting, by said network source, said network code to said one or more network destination receivers in accordance with said push-back messages. ### Claim 2 (depends on 1) The method of claim 1 wherein said computing a network code is done across a plurality of layers. ### Claim 3 (depends on 1) The method of claim 1 wherein the push-back messages identify the one or more refinement layers suited for each one of the one or more network destination receivers, respectively. ### Claim 4 (depends on 1) The method of claim 1 wherein said pushback message initiated by said network destination receiver is pushed up to said network source allowing upstream nodes to gather information on the demands of any network destination receiver reachable from them. ### Claim 5 (depends on 4) The method of claim 4 wherein initially each of said network destination receivers requests for said base layer and said one or more refinement layers to an upstream node at a rate equal to said network destination receivers min-cut, wherein said min-cut is defined as the minimum rate on the link between said network destination receiver and said upstream node. ### Claim 6 (depends on 5) The method of claim 5 wherein an intermediate node computes a pushback message dependent upon the value of min-cut for said intermediate node and the requests from children nodes of said intermediate node and pushes said pushback message to parent nodes of said intermediate node, said pushback message indicating the layers said parent node should encode together. ### Claim 7 A non-transitory computer readable storage medium having computer readable code thereon for utilizing network coding for multi-resolution multicast, the medium including instructions in which a computer system performs operations comprising: partitioning, at a network source, source content into a base layer and one or more refinement layers, wherein the base layer provides a lowest resolution associated with the source content and the one or more refinement layers provide a respective one or more resolutions associated with the source content that are at respective higher resolutions than the base layer, wherein the one or more refinement layers are at a respective one or more progressively higher resolutions; receiving, at said network source, a respective one or more push-back messages from one or more network destination receivers; computing, at said network source, a network code involving at least one of said base layer and said one or more refinement layers for at least one of said one or more network destination receivers wherein said network code comprises a random linear network code, said random linear network code comprising random linear combinations of at least a portion of said base layer and zero or more of said refinement layers; and transmitting, by said network source, said network code to said one or more network destination receivers in accordance with said push-back messages. ### Claim 8 (depends on 7) The computer readable storage medium of claim 7 wherein said computing a network code is done across a plurality of layers. ### Claim 9 (depends on 7) The computer readable storage medium of claim 7 wherein the push-back messages identify the one or more refinement layers suited for each one of the one or more network destination receivers, respectively. ### Claim 10 (depends on 7) The computer readable storage medium of claim 7 wherein a pushback message initiated by said network destination receiver is pushed up to said network source allowing upstream nodes to gather information on the demands of any network destination receiver reachable from them. ### Claim 11 (depends on 10) The computer readable storage medium of claim 10 wherein initially each of said network destination receivers requests for said base layer and said one or more refinement layers to an upstream node at a rate equal to said network destination receivers min-cut, wherein said min-cut is defined as the minimum rate on the link between said network destination receiver and said upstream node. ### Claim 12 (depends on 11) The computer readable storage medium of claim 11 wherein an intermediate node computes a pushback message dependent upon the value of min-cut for said intermediate node and the requests from children nodes of said intermediate node and pushes said pushback message to parent nodes of said intermediate node, said pushback message indicating the layers said parent node should encode together. ### Claim 13 A computer system comprising: a memory; a processor; a communications interface; an interconnection mechanism coupling the memory, the processor and the communications interface; and wherein the memory is encoded with an application utilizing network coding for multi-resolution multicast, that when performed on the processor, provides a process for processing information, the process causing the computer system to perform the operations of: partitioning, at a network source, source content into a base layer and one or more refinement layers, wherein the base layer provides a lowest resolution associated with the source content and the one or more refinement layers provide a respective one or more resolutions associated with the source content that are at respective higher resolutions than the base layer, wherein the one or more refinement layers are at a respective one or more progressively higher resolutions; receiving, at said network source, a respective one or more push-back messages from one or more network destination receivers; computing, at said network source, a network code involving at least one of said base layer and said one or more refinement layers for at least one of said one or more network destination receivers, wherein said network code comprises a random linear network code, said random linear network code comprising random linear combinations of at least a portion of said base layer and zero or more of said refinement layers; and transmitting, by said network source, said network code to said one or more network destination receivers in accordance with said push-back messages. ### Claim 14 (depends on 13) The computer system of claim 13 wherein said computing a network code is done across a plurality of layers. ### Claim 15 (depends on 13) The computer system of claim 13 wherein the pushback messages identify the one or more refinement layers suited for each one of the one or more network destination receivers, respectively. ### Claim 16 (depends on 13) The computer system of claim 13 wherein a pushback message initiated by said network destination receivers is pushed up to said network source allowing upstream nodes to gather information on the demands of any network destination receiver reachable from them. ### Claim 17 (depends on 16) The computer system of claim 16 wherein initially each of said network destination receivers requests for said base layer and said one or more refinement layers to an upstream node at a rate equal to said network destination receivers min-cut, wherein said min-cut is defined as the minimum rate on the link between said network destination receiver and said upstream node. ### Claim 18 (depends on 17) The computer system of claim 17 wherein an intermediate node computes a pushback message dependent upon the value of min-cut for said intermediate node and the requests from children nodes of said intermediate node and pushes said pushback message to parent nodes of said intermediate node, said pushback message indicating the layers said parent node should encode together.