Patent Publication Number: US-9408044-B2

Title: Video multicast optimization

Description:
FIELD 
     An embodiment of the invention relate generally to wireless digital networks, and more particularly, to managing video distribution in a wireless network. 
     BACKGROUND 
     Data networks, particularly IEEE 802.11 wireless data networks, have become an expected or necessary resource in an increasing number of situations. Once present only in the workplace environment, these data networks are becoming ubiquitous. They are encountered in schools, libraries, retail environments, and other gathering locations. As the use of these networks moves from a business setting to a consumer oriented setting, the static web pages of yesterday are being overwhelmed by the mixing of media streams, particularly with the addition of video streams. While the solutions have evolved for handling video distribution, particularly using multicast, many of these solutions were developed for wired networks, and do not translate adequately to the wireless environment. 
     Wired (IEEE 802.3) and wireless (IEEE 802.11) networks implement two data transfer models: unicast and multicast. In the unicast model, packets are sent from a source to a particular single destination. Unicast is a one-to-one data transmission. Unicast protocols, such as those based on Transmission Control Protocol (TCP), provide for error detection and packet retransmission to recover from missing or damaged packets arriving at the destination. 
     In contrast, the multicast model allows for one-to-many distribution of data. Multicast uses User Datagram Protocol (UDP), which is a connectionless protocol that does not support retransmission of packets. Multicast distribution of video streams allows for a single stream including a single set of packets to be sent to a plurality of devices. For example, in a University lecture hall setting, multiple devices such as student laptops or tablets may subscribe to a single multicast video stream of the lecture. Multicast allows multiple users (e.g., students) to be supported by transmitting one multicast stream of packets (e.g., a video stream of the lecture). In contrast, unicast requires multiple individual sets of packets (e.g., multiple identical video streams of the lecture) to be sent to each of the users (e.g., each student). A disadvantage of multicast is that it does not support retransmission. Accordingly, the client devices must use other strategies to overcome dropped, damaged, or out-of-order multicast packets. 
     In the current systems, where a wireless access point is sending multicast transmissions to a set of wireless clients, the data rate of the multicast transmissions are being decreased in order to attempt to increase the reliability (or probability of reception) of multicast transmissions. While using a lower data rate for multicast increases reliability, it also dramatically increases the time required to transmit a data stream. For instance, a multicast stream may be transmitted at an 11 Megabyte per second (Mb/sec) data rate while the full high-throughput 802.11 unicast connection is capable of delivering 450 Mb/sec data rates. 
     Current adaptations of the multicast systems include (i) increasing the multicast transmission rate and (ii) converting the single multicast stream to a plurality of unicast streams. Both adaptations present disadvantages. In the first adaptation, increasing the multicast transmission rate may decrease required transmission times, but it also increases data loss for client devices that are located farther from the access point or for client devices that are dealing with compromised signal conditions. Given that there are no automatic retries or retransmission in multicast, this adaptation results in increased data loss which leads to stuttering video, drop-outs, etc. In the second adaptation, the conversion of a single multicast stream targeting multiple client devices into multiple unicast streams, each being addressed to a single client, results in an increased transmission time and this adaptation cannot accommodate a large number of client devices. 
     SUMMARY 
     In one embodiment of the invention, a method begins with a network device receiving a multicast stream that may include a frame. The network device may determine whether to send the frame unicast or multicast based on characteristics of the frame. The characteristics of the frame may include characteristics of a key frame such as an I-frame. In that embodiment, the frame that includes characteristics of an I-frame is determined to be transmitted unicast. The network device may then transmit the frame unicast or multicast based on the determination. 
     In another embodiment of the invention, a network device includes a communication interface and a processor. The communication interface may receive a multicast stream that includes a frame. The processor is coupled to the communication interface and may determine whether to send the frame unicast or multicast. The communication interface transmits the frame unicast or multicast based on the determination by the processor. The determination by the processor may be based on characteristics of the frame. If the characteristics of the frame include characteristics of a key frame such as an I-frame, the processor may determine to transmit the frame unicast. The determination may also be based on a predetermined state of client devices that are to receive the frame. If a client device is in a predetermined state such as a power save state, the processor may determine to transmit the frame unicast to that client device. 
     In yet another embodiment of the invention, a non-transitory computer-readable medium has stored thereon instructions, which when executed by a processor of a network device, causes the network device to perform a method. This method starts by receiving a multicast stream including a frame. The network device then determines whether to send the frame unicast or multicast based on characteristics of the frame and transmits the frame unicast or multicast based on the determination. In one embodiment, the frame is inspected to determine if the characteristics of the frame include characteristics of an I-frame and if so, the frame is transmitted unicast. 
     The above summary does not include an exhaustive list of all aspects of the present invention. It is contemplated that the invention includes all systems, apparatuses and methods that can be practiced from all suitable combinations of the various aspects summarized above, as well as those disclosed in the Detailed Description below and particularly pointed out in the claims filed with the application. Such combinations may have particular advantages not specifically recited in the above summary. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The embodiments of the invention are illustrated by way of example and not by way of limitation in the figures of the accompanying drawings in which like references indicate similar elements. It should be noted that references to “an” or “one” embodiment of the invention in this disclosure are not necessarily to the same embodiment, and they mean at least one. In the drawings: 
         FIG. 1  shows exemplary block diagram of a system in which one embodiment of the invention may be implemented. 
         FIG. 2  shows exemplary block diagram of a network device according to one embodiment of the invention. 
         FIG. 3  shows a flowchart illustrating a process performed by a network device according to one embodiment of the invention. 
         FIG. 4  shows a flowchart illustrating the details of the process of Block  103  from  FIG. 3  according to one embodiment of the invention. 
         FIG. 5  shows a sequence diagram illustrating an example of the process of performed by a network device according to an embodiment of the invention. 
         FIG. 6  shows a flowchart illustrating an additional step in the process from  FIG. 3  performed by a network device according to one embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     In the following description, numerous specific details are set forth. However, it is understood that embodiments of the invention may be practiced without these specific details. In other instances, well-known circuits, structures, and techniques have not been shown to avoid obscuring the understanding of this description. 
       FIG. 1  shows exemplary block diagram of a system in which one embodiment of the invention may be implemented. System  1 , as illustrated in  FIG. 1 , is a digital system that includes a network  10  which may be the Internet, a network device  20  and a plurality of client devices  30   1 - 30   n  (n&gt;1). For clarity,  FIG. 1  does not show other typical elements such as switches, routers, firewalls, etc. 
     The network device  20  is coupled to the network  10  via a transmission medium to receive and examine data streams. The data streams may be, for instance, video data streams. The transmission medium may be a wired or a wireless connection. The network device  20  may be a device such as a wired or wireless access port, a switch, a router, or any combination thereof. 
     The client devices  30   1 - 30   n  are coupled to the network device  20  via a wireless connection. The client devices  30   1 - 30   n  may be digital devices including a processor, memory hierarchy, and input/output (I/O) interfaces including a wireless interface such as an IEEE 802.11 wireless interface. The wireless interface may be used to communicate with the network device  20  (e.g., a wireless access point). The client devices  30   1 - 30   n  may be wireless electronic devices capable of receiving the video data streams such as personal computers, laptop computers, netbook computers, wireless music players, portable telephone communications devices, smart phones, tablets, digital televisions, etc. 
       FIG. 2  shows exemplary block diagram of a network device according to one embodiment of the invention. The network device  20  may be a purpose-build digital device that comprises a processor  21 , data storage  22 , and an I/O interface  23 . 
     The data storage  22  of the network device  20  may include a fast read-write memory for storing programs and data during the network device  20 &#39;s operations and a hierarchy of persistent memory such as ROM, EPROM, and Flash memory for storing instructions and data needed for the network device  20 &#39;s startup and a file system for the network device  20 &#39;s operations. 
     The I/O interface  23  may include a wired network interface such as an IEEE 802.3 Ethernet interface and a wireless interface such as an IEEE 802.11 WiFi interface. The I/O interface  23  may receive a multicast stream that includes at least one frame and may transmit each of the frames as a unicast frame or as a multicast frame to at least one of the client devices  30   1 - 30   n . The multicast stream may be, for instance, a video multicast stream. 
     As shown in  FIG. 2 , the processor  21  is coupled to the data storage  22  and the I/O interface  23 . The processor  21  may be any processing device including, but not limited or restricted to a MIPS-class processor, a microprocessor, a digital signal processor, an application specific integrated circuit, a microcontroller, a state machine, or any type of programmable logic array. 
     In one embodiment, the I/O interface  23  receives video multicast stream and sends the stream to the processor  21 , which determines whether to send the frame unicast or multicast. The determination by the processor  21  may be based on characteristics of the frame. In one embodiment, the processor  21  performs deep packet inspection (DPI) on each of the frames to analyze the characteristics of the frame. Based on the determination by the processor  21 , the communication interface  23  may then transmits the frame unicast or multicast. In one embodiment, the determination is based on a predetermined state of client devices  30   1 - 30   n  that are to receive the frame. If a client device  30   1  is in a predetermined state such as a power save state, the processor  21  may determine to transmit the frame unicast to that client device  30   1 . In another embodiment, if the characteristics of the frame include characteristics of a key frame, and thus revealing that the frame is a key frame, the processor  21  may determine that the frame is to be transmitted unicast. Examples of key frames include, but are not limited, to frames such as I-frames or I-slices in video standards such as H.264/MPEG4. In some embodiments, the processor  21  may convert the frame that is determined to be sent unicast into a unicast frame. 
     As is known in the digital arts, multimedia and video streams are highly compressed. In the form of compression that is used in MPEG-2 video streams and in DVDs, the video image stream is encoded as a series of key (or reference) frames each followed by frames containing changes (“change frames”) to these key frames. These change frames are typically much smaller than the key frames. In MPEG-2, for example, the key frames are referred to as I-frames, and the change frames are referred to as P-frames and B-frames. In some embodiments, the slices may be used instead of frames, such that the key slices are I-slices and the change slices are P-slices and B-slices. 
     For example, in a scene where a ball rolls across a fixed background, a key frame or I-frame would contain the complete detail of the image, while subsequent P-frames would only contain those elements of the image that have changed from the previous frame. In practice, key frames are sent periodically (e.g., once per second) and used to establish reference points. The intervening P- and B-frames are numerous and smaller in size since these frames only represent the changes. 
     Accordingly, during reception of a video data stream, if one or more P- or B-frames are lost, the image reconstruction may still be performed, although with sub-optimal results. In contrast, if a key frame such as an I-frame is lost, image reconstruction using subsequent B- and/or P-frames cannot be performed given that the reference (i.e., the I-frame) on which the changes identified in these B- and/or P-frames are based is not available. Image reconstruction cannot continue until the next key frame is successfully received. Thus, since the key frames are the foundation of the series of images, the reception of these key frames by the client devices  30   1 - 30   n  is critical. Accordingly, in one embodiment, the processor  21  may determine based on DPI that a frame is a key frame and determine that this (key) frame is to be transmitted unicast. 
     In this embodiment of the invention, the I/O interface  23  transmits the frame unicast to each of the client devices  30   1 - 30   n . When the key frames are sent as unicast frames, the key frames may be transmitted at the full data rate supported by the client device  30   1 - 30   n  rather than at the typically much slower multicast rate. As unicast frames, in addition to being transmitted at higher data rates, the key frames are also transmitted with full error control, which assures delivery of these key frames to the client devices  30   1 - 30   n . Further, since the change frames are sent as multicast frames to the client devices  30   1 - 30   n , the data rate of transmission may be increased such that the total transmission time of the video data stream may be decreased. 
     In one embodiment, the network device  20  may be a wireless access point that operates under the control of software or an operating system (OS), such as Linux, running specific programs to provide for access point operation. The OS may be stored in the data storage  22  and executed by the processor  21  to cause the network device  20  to perform access point operations. 
     The following embodiments of the invention may be described as a process, which is usually depicted as a flowchart, a flow diagram, a structure diagram, or a block diagram. Although a flowchart may describe the operations as a sequential process, many of the operations can be performed in parallel or concurrently. In addition, the order of the operations may be re-arranged. A process is terminated when its operations are completed. A process may correspond to a method, a procedure, etc. 
       FIG. 3  shows a flowchart illustrating a process performed by a network device according to one embodiment of the invention. 
     Method  100  starts by receiving a multicast stream by a network device at Block  110 . The video multicast stream may comprise at least one frame, which may include key frames and change frames. At Block  120 , the network device may determine whether to send the frame unicast or multicast based on the characteristics of the frame. At Block  130 , the network device may transmit the frame unicast or multicast based on the determination in Block  120 . This method  100  allows for the network device to optimize the video multicast by transmitting some frames as unicast and others as multicast. 
       FIG. 4  shows a flowchart illustrating the details of the process of Block  120  from  FIG. 3  according to one embodiment of the invention. As discussed above, at Block  120 , the network device determines whether to send the frame unicast or multicast. As illustrated in  FIG. 4 , to make this determination, the network device performs deep packet inspection on the frame at Block  121 . Based on the DPI, the network device then determines whether the frame is a key frame at Block  122 . In one embodiment, the network device analyzes the characteristics of the frame which may include characteristics of a key frame such as an I-frame or include an I-slice. In that embodiment, the frame that includes characteristics of an I-frame is determined to be a key frame at Block  122  and is to be transmitted unicast at Block  104 . In some embodiments, if the network determine determines that the frame is not a key frame at Block  122 , the method  100  continues to Block  123  where the network device assesses each of the client devices to determine if any of the client devices are in a predetermined state. For instance, referring to  FIG. 1 , the network device  20  assesses client devices  30   1 - 30   n  to determine if any of the client devices  30   1 - 30   n  are in a predetermined state. If network device  20  determines that client device  30   1  is in a predetermined state, the frame is determined to be sent unicast to the client device in the predetermined state at Block  104 . In one embodiment, the predetermined state is a power save state. In the power save state, the client device may not be able to buffer multicast traffic. Referring to  FIG. 4 , if at Block  123 , if none of the client devices are in a predetermined state, the method  100  continues to Block  104  where the frame is transmitted multicast. 
       FIG. 5  shows a sequence diagram illustrating an example of the process of optimizing the video multicast by a network device according to an embodiment of the invention. As illustrated in  FIG. 5 , in one embodiment, the network device  20  receives a multicast video data stream from a network  10  (not shown). Only one copy of the multicast video stream is being transmitted. In this embodiment, the network device  20  transmits the packets included in the video data stream to the client devices  30   1 - 30   n . 
     Method  500  starts with the network device  20  receiving a video data stream at sequence  501 . The video data stream in  FIG. 5  includes packets B 1 , B 2 , I 1 , and B 3 . The packets B 1 , B 2 , and B 3  are B-packets while the packet I 1  is an I-packet, which is a key packet. The B-packets are shown schematically shorter than the I-packet to be indicative of the difference in time required to transmit frames at the multicast rate, which may default to as low as 11 Mb/sec, as compared to a high-throughput 802.11n unicast rate of 300 Mb/sec. 
     At sequence  502 , the network device  20  determines based on DPI that B 1  is not a key packet and the network device  20  transmits B 1  to client devices  30   1 - 30   n  as a multicast packet. At sequence  503 , the network device  20  receive B 2  and at sequence  504 , determines based on DPI that B 2  is not a key packet and the network device  20  transmits B 2  to client devices  30   1 - 30   n  as a multicast packet. At sequence  505 , the network device  20  receives I 1 . The network device  20  determines based on DPI that I 1  is a key frame and the network device  20  transmits I 1  as a unicast frame to client device  30   1  at sequence  506 , transmits I 1  as a unicast frame to client device  30   2  at sequence  507 , transmits I 1  as a unicast frame to client device  30   3  at sequence  508 , and transmits I 1  as a unicast frame to client device  30   n  at sequence  509 . At sequence  510 , the network device  20  determines based on DPI that B 3  is not a key packet and the network device  20  transmits B 3  to client devices  30   1 - 30   n  as a multicast packet at sequence  511 . 
     In another embodiment of the invention, non-key frames such as the B- and P-frames in MPEG-2 may also be converted to unicast as bandwidth and/or channel loading permits. 
       FIG. 6  shows a flowchart illustrating an additional step in the process from  FIG. 3  of optimizing the video multicast by a network device according to one embodiment of the invention. 
     In this embodiment, prior to receiving the multicast video stream at Block  110  of  FIG. 3 , the network device analyzes and stores a client posture associated with each of the plurality client devices (Block  101 ). In one embodiment, the analyzing and storing of the client posture (Block  101 ) is performed during authentication of each of the client devices. The client posture may include, for example, information on a type of application installed on the client device. In this embodiment, at Block  107 , the network device may determine determining if the client device is a potential threat based on the type of application installed on the one of the plurality of client devices. The client posture may also include, for instance, a version of an application installed on the client device. In this embodiment, at Block  107 , the network device may determine a signature set for DPI based on the version of an application installed on the one of the plurality of client devices. 
     An embodiment of the invention may be a machine-readable medium having stored thereon instructions which program a processor to perform some or all of the operations described above. A machine-readable medium may include any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer), such as Compact Disc Read-Only Memory (CD-ROMs), Read-Only Memory (ROMs), Random Access Memory (RAM), and Erasable Programmable Read-Only Memory (EPROM). In other embodiments, some of these operations might be performed by specific hardware components that contain hardwired logic. Those operations might alternatively be performed by any combination of programmable computer components and fixed hardware circuit components. 
     An embodiment of the present invention also may be embedded in non-transitory manner in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which when loaded in a computer system is able to carry out these methods. Computer program in the present context means any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after either or both of the following: a) conversion to another language, code or notation; b) reproduction in a different material form. 
     An embodiment of the present invention may be realized in hardware, software, or a combination of hardware and software. A typical combination of hardware and software may be a network server or access point with a computer program that, when being loaded and executed, controls aspects of the host device such that it carries out the methods described herein. 
     While the invention has been described in terms of several embodiments, those of ordinary skill in the art will recognize that the invention is not limited to the embodiments described, but can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of limiting. There are numerous other variations to different aspects of the invention described above, which in the interest of conciseness have not been provided in detail. Accordingly, other embodiments are within the scope of the claims.