Abstract:
A video redirection system redirects an incoming video stream to a remote console. The video redirection system samples the video stream to generate a currently sampled frame comprising a plurality of tiles, and calculates a current hash value for each of the tiles. The video redirection system compresses the tile if the current hash value is different from a reference hash value locally stored inside the video redirection system. A difference in the hash value indicates that there is a change in the tile of the currently sampled frame from the corresponding tile of the previously sampled frame. Thus, it is no longer necessary to compare the currently sampled frame with a reference frame in the memory. Accordingly, the amount of memory access is reduced.

Description:
BACKGROUND 
     Keyboard, video, and mouse (KVM) redirection refers to the redirection of signals from a keyboard, a video source, or a mouse to a site remote to the keyboard, the video source, or the mouse. KVM redirection is typically used for the maintenance and configuration of computers at a remote site. In an enterprise environment, KVM redirection allows an information technology (IT) team to administer and maintain corporate servers and desktop computers through a network without being physically present at the location of the computers. In a server environment, it is unlikely to allocate a console to each server where the servers are clustered in a computer room. KVM redirection allows an IT team to manage the servers through a network from one single remote location. 
     One of the most common implementations of video redirection is based on tile compression algorithms. These algorithms typically split the screen into rectangles of pixel data (e.g., tiles of 64×64 pixels each), and look for changes in the corresponding tiles between subsequently sampled frames. If a change is detected, the tile from the currently sampled frame is compressed and sent, or redirected, to a remote console. Otherwise, no action is taken with respect to that tile. An example of an algorithm and network protocol is the Virtual Network Computing (VNC) based on the Remote Frame Buffer (RFB) protocol. 
       FIG. 1  shows an example of a video redirection system  11  which implements the tile compression algorithm mentioned above. Video redirection system  11  redirects a video stream from a video source  14  to a remote console via a network interface  13 . Video redirection system  11  is coupled to a memory  12  via a memory bus  15 . Memory  12  includes a current frame buffer  121  for storing a currently sampled frame, a reference frame buffer  122  for storing a reference sampled frame (hereinafter “a reference frame”), and a compressed tile buffer  123  for storing compressed tiles of the currently sampled frame. 
     When a new screen shot of video stream is to be redirected to a remote viewer, a frame sampler  111  of video redirection system  11  grabs a frame and saves it into current frame buffer  121 . Grabbing a frame may involve sampling the video at a pre-determined rate to comply with a desired resolution. After an entire frame is sampled and saved, a tile comparator  112  of video redirection system  11  reads the frame from current frame buffer  121  and a reference frame from reference frame buffer  122  via memory bus  15 . Tile comparator  112  compares the two frames, tile by tile, to determine if any tile of the currently sampled frame is different from the corresponding tile of the reference frame. If a tile is different, the tile is sent to a compression module  113  for compression. The compressed tiles are buffered in compressed tile buffer  123  before being sent to a network module  114  of video redirection system  11  for transmission to the remote console. Thereafter, the content of current frame buffer  121  becomes the reference frame as a new frame cycle begins. 
     The aforementioned operations make heavy use of memory bus  15 . In every frame cycle, both the currently sampled frame and the reference frame are read from memory  12 . This creates a burden to the memory bandwidth and requires a high performance memory to be used. A fast and wide memory array may accommodate the bandwidth required by the above operations but the cost is high. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments 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 in this disclosure are not necessarily to the same embodiment, and such references mean at least one. 
         FIG. 1  is a block diagram of a prior art video redirection system; 
         FIG. 2  is a block diagram of an embodiment of a video redirection system performing a hash operation on incoming video streams; and 
         FIG. 3  is a flowchart showing an embodiment of the operations performed by the video redirection system of  FIG. 2 . 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 2  shows an embodiment of a video redirection system  21  coupled to a memory  22  via a memory bus  25 . In one embodiment, video redirection system  21  may be a video server dedicated to online delivery of streaming videos. Alternatively, video redirection system  21  may be part of a server or client system for processing video streams transmitted to or generated by the server or client. Video redirection system  21  may receive video streams from a video source  24 , e.g., the screen output of a computer video controller, a content provider, a camera, or a broadcaster, and may be controllable by a remote console via a network interface  23 . The remote console may be directly coupled to network interface  23 , or indirectly coupled to network interface  23  via a network, e.g., local area network (LAN), wide area network (WAN), the Internet, or similar wired or wireless networks. Memory  22  may be a volatile memory, e.g., a static random access memory (SRAM), an array of memory devices, or other similar memory devices that may or may not be on the same chip or package as video redirection system  21 . Memory  22  may be dedicated to video redirection system  21 , a shared memory, or any other data storage devices. In the embodiment as shown, memory  22  contains a frame buffer  225  for storing a currently sampled frame and a compressed tile buffer  226  for storing compressed tiles of the currently sampled frame. In an alternative embodiment, frame buffer  225  and compressed tile buffer  226  may be located in different memory devices accessible by video redirection system  21 . 
     Video redirection system  21  includes a frame sampler  211  for sampling incoming video streams. The sampled frame is stored in frame buffer  225  in memory  22 . In contrast to memory  11  of video redirection system  11  ( FIG. 1 ) where both a currently sampled frame and a reference sampled frame are stored, memory  22  merely stores a currently sampled frame. This is because video redirection system  21  does not use a reference sampled frame for tile comparisons. Instead, video redirection system  21  uses a hash module  212  for determining whether a tile of a currently sampled video frame is different from a corresponding tile in a reference sampled frame. 
     Hash module  212  implements a hash algorithm which maps an input of a relatively large domain (e.g., a tile) into to a hash value of a relatively small domain. The mapping into a smaller domain means that there are fewer bits in a hash value than in a tile. Thus, these smaller hash values may be stored locally in video redirection system  21 . These hash values represent the newly sampled tiles and may be compared with hash values of the tiles of a reference frame. As a result, the number of memory reads may be reduced because there is no longer a need to retrieve a reference frame from memory  22  for the purpose of tile comparisons. 
     Hash module  212  may implement any known hash algorithms. Logic circuits and software for implementing hash algorithms are known in the art. For example, the Secure Hash Algorithm (SHA-1) algorithm, often adopted by security algorithms for user authentication and signature verification, may be used to map a tile of any size into 160-bit output. Thus, for a tile of 16×16 pixel with 24 bits per pixel, the reduction ratio is 160:(16×16×24)=1:38.4. The reduction in the domain size may sometimes cause collision, meaning that different inputs are mapped to the same output. A collision may cause missed detection of a tile change because different tiles are mapped to the same hash value. The SHA-1 algorithm has a low probability of collision (2 −160 ). Thus, the probability of missing a tile change because of hash collision is negligible. Alternative hash algorithms, e.g., SHA-2 or Message-Digest Algorithm 5 (MD5), may have different probability of collision and achieve different reduction ratio in the output bits. 
     In one embodiment, hash module  212  may store the hash values output in a hash value buffer  219  of video redirection system  21 . Hash value buffer  219  may designate a current buffer  213  for storing the hash values of the tiles of the currently sampled frame, and a reference buffer  214  for storing the hash values of the tiles of a reference frame. At the end of a frame cycle, the content of current buffer  213  may be copied into the reference buffer  214  to become the new reference hash values. Alternatively, buffers  213  and  214  may be implemented as a double buffer. At the end of a frame cycle, the designation of current buffer  213  and reference buffer  214  may be swapped to avoid the copying operations. 
       FIG. 3  is an embodiment of a flowchart  30  illustrating the operations of video redirection system  21 . Referring also to  FIG. 2 , at block  31 , frame sampler  211  of video redirection system  21  samples the incoming video stream to obtain information bits of a frame, and stores the frame in frame buffer  225  of memory  22 . In parallel, frame sampler  211  sends the frame to hash module  212 . In one embodiment, frame sampler  211  may send the samples of the frame to frame buffer  225  and hash module  212  as the information bits are sampled. 
     A video stream carries pixel information of the frame sequentially in a line by line manner. Thus, the sampled bits are also sequentially ordered. In one embodiment, hash module  212  includes an internal buffer to accumulate the sampled bits. As a tile is usually a square or rectangular block of image, hash module  212  may accumulate several lines of a frame before forming one or more tiles. Hash module  212  computes the hash values for each of the tiles as the tiles are accumulated, and temporarily stores the hash values in current buffer  213  of video redirection system  21 . 
     Video redirection system  21  may also include a hash value comparator  215  which compares two hash values to determine whether there is a difference. Hash value comparator  215  may be implemented by logic circuits or a software module executable by a microcontroller. At block  32 , hash value comparator  215  compares the hash values in current buffer  213  with the corresponding reference hash values in reference buffer  214 . A corresponding reference hash value is the hash value of a tile of a previously sampled frame that occupies the same location in a frame as the tile of the currently sampled frame. If hash value comparator  215  determines there is a difference between the current hash value and the corresponding reference hash value, hash value comparator  215  signals a changed tile reader  216  with an identifier or an address of the tile to enable a memory read. If hash value comparator  215  determines there is no difference between the two hash values, no memory read is enabled for the tile. Changed tile reader  216  may be implemented as a hardware or software interface for reading specific data locations from memory  22 . In one embodiment, changed tile reader  216  may be implemented as a standard memory interface for reading specific addresses of data units in memory  22 . 
     In one embodiment, hash value comparator  215  may signal changed tile reader  216  with an identifier or address of a tile every time a difference in hash values is detected. Alternatively, hash value comparator  215  may compile a list of all the tiles having different hash values from the corresponding reference hash values. Hash value comparator  215  may send the entire list to changed tile reader  216  after all the tiles of the currently sampled frame are processed. The choice of implementation may depend on the speed of compression module  217  and the bandwidth of memory bus  25 . 
     At block  33 , changed tile reader  216  reads the tiles having changed hash values from frame buffer  225 , and forwards the tiles to a compression module  217  of video redirection system  21 . At block  34 , compression module  217  compresses the tiles, using any lossless compression algorithms, e.g., run-length coding or Lempel-Ziv coding. Compression circuits or software for implementing the lossless compression algorithms are well known in the art. Compression module  217  may alternatively implement lossy compression algorithms, e.g., moving picture experts group (MPEG) or similar algorithms, for applications that can tolerate data loss. However, the common video compression standards such as MPEG may not be adequate for the compression of a computer screen where textual images predominate, because these standards suffer from information loss as a result of the reduced compression ratio. Textual images generally have sharper edges than a typical video application and thus may not be a suitable candidate for lossy compressions. However, in applications where textual images do not predominate, lossy compression algorithms may be used. 
     Following the compression, compression module  217  temporarily stores the compressed tiles in compressed tile buffer  226 . In an alternative embodiment, compressed tile buffer  226  may be internal to compression module  217  if space allows. At block  35 , a network module  218  of video redirection system  21  retrieves the compressed tiles from compressed tile buffer  226  and transmits the compressed tiles to a remote console via network interface  23  according to a pre-determined protocol, e.g., the Virtual Network Computing (VNC) based on the Remote Frame Buffer (RFB) protocol, or other proprietary protocols. 
     At block  36 , video redirection system  21  designates the current hash values in current buffer  213  as the reference hash values. Video redirection system may replace the entire content of reference buffer  214  with the content of buffer  213 , or replace only the hash values of the changed tiles. Alternatively, the designation of current and reference buffers  213  and  214  may be swapped without making a real copy of the hash values. Thereafter, at block  37 , video redirection system  21  repeats the operations of blocks  31 - 36  for the next frame cycle. In one embodiment, the video redirection system  21  may repeat the operations when prompted by a request from a viewer program at the remote management console. The speed at which the video streams are redirected may depend on the processing speed of the remote console and the connection thereto. 
     The aforementioned embodiments have the advantages of speed, efficiency, and cost-effectiveness. The size of memory  22  may be reduced, as the memory is no longer required to store a reference frame. Memory bandwidth is also reduce because only the tiles different from the reference frame are read from memory  22 . As a consequence, power consumption at the memory interface is minimized. 
     In the foregoing specification, specific embodiments have been described. It will, however, be evident that various modifications and changes can be made thereto without departing from the broader spirit and scope of the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.