Patent Publication Number: US-9838463-B2

Title: System and method for encoding control commands

Description:
TECHNICAL FIELD 
     The present disclosure relates generally to the field of data processing systems and particularly to a system and method for encoding control commands. 
     BACKGROUND 
     Some current data processing devices such as the iPad provide for the connection of Bluetooth input devices such as keyboards, mice and microphones. However, support for devices is limited to those specified by the data processing device manufacturer. For example, Apple configures the iPad to recognize and accept a limited, specified set of Bluetooth input devices. 
     It would be beneficial to provide a mechanism for connecting input devices to data processing devices such as the iPad using the existing communication capabilities of these data processing devices. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present disclosure will be understood more fully from the detailed description that follows and from the accompanying drawings, which however, should not be taken to limit the disclosed subject matter to the specific embodiments shown, but are for explanation and understanding only. 
         FIG. 1  illustrates a system architecture for executing online video games according to one embodiment of the invention. 
         FIG. 2  illustrates different communication channels over which an online video game may be played in accordance with one embodiment of the invention. 
         FIG. 3  illustrates one embodiment of a system architecture for compressing audio/video generated by a video game. 
         FIG. 4  illustrates a system architecture on which one embodiment of the invention may be implemented. 
         FIG. 5  illustrates a manner in which the symbols are chosen to represent the control data. 
         FIGS. 6A-6F  illustrates data for one specific example. 
     
    
    
     DESCRIPTION OF EXAMPLE EMBODIMENTS 
     In the following description specific details are set forth, such as device types, system configurations, communication methods, etc., in order to provide a thorough understanding of the present disclosure. However, persons having ordinary skill in the relevant arts will appreciate that these specific details may not be needed to practice the embodiments described. 
     The assignee of the present application has developed an online video gaming and application hosting system. Certain embodiments of this system are described, for example, in U.S. patent application Ser. No. 12/538,077, filed Aug. 7, 2009, entitled S YSTEM AND  M ETHOD FOR  A CCELERATED  M ACHINE  S WITCHING  (hereinafter &#39;077 application) which claims priority to U.S. Provisional Application Ser. No. 61/210,888, filed, Mar. 23, 2009, and is a continuation-in-part (CIP) application of Ser. No. 10/315,460 filed Dec. 10, 2002 entitled, “A PPARATUS AND  M ETHOD FOR  W IRELESS  V IDEO  G AMING ”, which is assigned to the assignee of the present CIP application. These applications are sometimes referred to as the “co-pending applications” and are incorporated herein by reference. A brief description of certain pertinent aspects of the online video game and application hosting system described in the co-pending applications will now be provided, following by a detailed description of a system and method for managing audio channels such as voice chat channels for computer games. 
     An Exemplary Online Video Game and Application Hosting System 
       FIG. 1  illustrates one embodiment of a video game/application Hosting Service  210  described in the co-pending applications. The Hosting Service  210  hosts applications running on Servers  402 , that accept input from an Input device  421 , received by Home or Office Client  415 , and sent through the Internet  410  to Hosting Service  210 . The Servers  402  are responsive to the input, and update their video and audio output accordingly which is compressed through Low-Latency Video Compression  404 . The compressed video is then streamed through the Internet  410  to be decompressed by the Home or Office Client  415 , and then displayed on Monitor or SD/HDTV  422 . This system is an low-latency streaming interactive video system as more thoroughly described in the aforementioned “co-pending applications.” 
     As shown in  FIG. 2 , the network connection between the Hosting Service  210  Home and Office Client  415  may be implemented through a wide range of network technologies, of varying degrees of reliability, such as wired or optical fiber technologies that are typically more reliable and wireless technologies that may be subject to unpredictable interference or range limitations (e.g. Wi-Fi) and are typically less reliable. Any of these client devices may have their own user input devices (e.g., keyboards, buttons, touch screens, track pads or inertial sensors, position sensors, wands, video capture cameras and/or motion-tracking cameras, etc.), or they may use external input devices  421  (e.g., keyboards, mice, game controllers, inertial sensors, position sensor, wands, video capture cameras and/or motion tracking cameras, etc.), connected with wires or wirelessly. As described in greater detail below, the hosting service  210  includes servers of various levels of performance, including those with high-powered CPU/GPU processing capabilities. During playing of a game or use of an application on the hosting service  210 , a home or office client device  415  receives control signals  406  from input device  421  from the user, and then it transmits the controller input through the Internet  410  to the hosting service  210  that executes the gaming program code in response and generates successive frames of video output (a sequence of video images) for the game or application software (e.g., if the user presses a button which would direct a character on the screen to move to the right, the game program would then create a sequence of video images showing the character moving to the right). This sequence of video images is then compressed using a low-latency video compressor, and the hosting service  210  then transmits the low-latency video stream through the Internet  410 . The home or office client device then decodes the compressed video stream and renders the decompressed video images on a monitor or TV. Consequently, the computing and graphical hardware requirements of the client device  415  are significantly reduced. The client  415  only needs to have the processing power to forward the input device  421  control signals  406  through the Internet  410  and decode and decompress a compressed video stream received from the Internet  410 , which virtually any personal computer is capable of doing today in software on its CPU (e.g., a Intel Corporation Core Duo CPU running at approximately 2 GHz is capable of decompressing 720p HDTV encoded using compressors such as H.264 and Windows Media VC9). And, in the case of any client devices, dedicated chips can also perform video decompression for such standards in real-time at far lower cost and with far less power consumption than a general-purpose CPU such as would be required for a modern PC. Notably, to perform the function of forwarding controller input and decompressing video, home client devices  415  do not require any specialized graphics processing units (GPUs), optical drive or hard drives. 
     As games and applications software become more complex and more photo-realistic, they will require higher-performance CPUs, GPUs, more RAM, and larger and faster disk drives, and the computing power at the hosting service  210  may be continually upgraded, but the end user will not be required to update the home or office client platform  415  since its processing requirements will remain constant for a display resolution and frame rate with a given video decompression algorithm. Thus, the hardware limitations and compatibility issues seen today do not exist in the system illustrated in  FIG. 1 . 
     Further, because the game and application software executes only in servers in the hosting service  210 , there never is a copy of the game or application software (either in the form of physical optical media such as a DVD-ROM, or as downloaded software) in the user&#39;s home or office (“office” as used herein unless otherwise qualified shall include any non-residential setting, including, schoolrooms, for example). This significantly mitigates the likelihood of a game or application software being illegally copied (pirated), as well as mitigating the likelihood of a valuable database that might be use by a game or applications software being pirated. Indeed, if specialized servers are required (e.g., requiring very expensive, large or noisy equipment) to play the game or application software that are not practical for home or office use, then even if a pirated copy of the game or application software were obtained, it would not be operable in the home or office. 
     In one embodiment, the hosting service  210  provides software development tools to the game or application software developers (which refers generally to software development companies, game or movie studios, or game or applications software publishers) which design video games so that they may design games capable of being executed on the hosting service  210 . Such tools allow developers to exploit features of the hosting service that would not normally be available in a standalone PC or game console (e.g., fast access to very large databases of complex geometry (“geometry” unless otherwise qualified shall be used herein to refer to polygons, textures, rigging, lighting, behaviors and other components and parameters that define 3D datasets)). 
     Different business models are possible under this architecture. Under one model, the hosting service  210  collects a subscription fee from the end user and pays a royalty to the developers. In an alternate implementation, the developers collect a subscription fee directly from the user and pays the hosting service  210  for hosting the game or application content. These underlying principles are not limited to any particular business model for providing online gaming or application hosting. 
       FIG. 3  illustrates an embodiment of components of a server center for hosting service  210  utilized in the following feature descriptions. Inbound internet traffic  1501  from user clients  415  is directed to inbound routing  1502 . Typically, inbound internet traffic  1501  will enter the server center via a high-speed fiber optic connection to the Internet, but any network connection means of adequate bandwidth, reliability and low latency will suffice. Inbound routing  1502  is a system of network (the network can be implemented as an Ethernet network, a fiber channel network, or through any other transport means) switches and routing servers supporting the switches which takes the arriving packets and routes each packet to the appropriate application/game (“app/game”) server  1521 - 1525 . In one embodiment, a packet which is delivered to a particular app/game server represents a subset of the data received from the client and/or may be translated/changed by other components (e.g., networking components such as gateways and routers) within the data center. In some cases, packets will be routed to more than one server  1521 - 1525  at a time, for example, if a game or application is running on multiple servers at once in parallel. RAID arrays  1511 - 1512  are connected to the inbound routing network  1502 , such that the app/game servers  1521 - 1525  can read and write to the RAID arrays  1511 - 1512 . Further, a RAID array  1515  (which may be implemented as multiple RAID arrays) is also connected to the inbound routing  1502  and data from RAID array  1515  can be read from app/game servers  1521 - 1525 . The inbound routing  1502  may be implemented in a wide range of prior art network architectures, including a tree structure of switches, with the inbound internet traffic  1501  at its root; in a mesh structure interconnecting all of the various devices; or as an interconnected series of subnets, with concentrated traffic amongst intercommunicating device segregated from concentrated traffic amongst other devices. One type of network configuration is a SAN which, although typically used for storage devices, it can also be used for general high-speed data transfer among devices. Also, the app/game servers  1521 - 1525  may each have multiple network connections to the inbound routing  1502 . For example, a server  1521 - 1525  may have a network connection to a subnet attached to RAID Arrays  1511 - 1512  and another network connection to a subnet attached to other devices. 
     The app/game servers  1521 - 1525  may all be configured the same, some differently, or all differently, as previously described in relation to servers  402  in the embodiment illustrated in  FIG. 1 . In one embodiment, each user, when using the hosting service is typically using at least one app/game server  1521 - 1525 . For the sake of simplicity of explanation, we shall assume a given user is using app/game server  1521 , but multiple servers could be used by one user, and multiple users could share a single app/game server  1521 - 1525 . The user&#39;s control input, sent from client  415  as previously described is received as inbound Internet traffic  1501 , and is routed through inbound routing  1502  to app/game server  1521 . App/game server  1521  uses the user&#39;s control input as control input to the game or application running on the server, and computes the next frame of video and the audio associated with it. App/game server  1521  then outputs the uncompressed video/audio  1529  to shared video compression  1530 . App/game server may output the uncompressed video via any means, including one or more Gigabit Ethernet connections, but in one embodiment the video is output via a DVI connection and the audio and other compression and communication channel state information is output via a Universal Serial Bus (USB) connection. 
     The shared video compression  1530  compresses the uncompressed video and audio from the app/game servers  1521 - 1525 . The compression may be implemented entirely in hardware, or in hardware running software. There may a dedicated compressor for each app/game server  1521 - 1525 , or if the compressors are fast enough, a given compressor can be used to compress the video/audio from more than one app/game server  1521 - 1525 . For example, at 60 fps a video frame time is 16.67 ms. If a compressor is able to compress a frame in 1 ms, then that compressor could be used to compress the video/audio from as many as 16 app/game servers  1521 - 1525  by taking input from one server after another, with the compressor saving the state of each video/audio compression process and switching context as it cycles amongst the video/audio streams from the servers. This results in substantial cost savings in compression hardware. Since different servers will be completing frames at different times, in one embodiment, the compressor resources are in a shared pool  1530  with shared storage means (e.g., RAM, Flash) for storing the state of each compression process, and when a server  1521 - 1525  frame is complete and ready to be compressed, a control means determines which compression resource is available at that time, provides the compression resource with the state of the server&#39;s compression process and the frame of uncompressed video/audio to compress. 
     Note that part of the state for each server&#39;s compression process includes information about the compression itself, such as the previous frame&#39;s decompressed frame buffer data which may be used as a reference for P tiles, the resolution of the video output; the quality of the compression; the tiling structure; the allocation of bits per tiles; the compression quality, the audio format (e.g., stereo, surround sound, Dolby® AC-3). But the compression process state also includes communication channel state information regarding the peak data rate and whether a previous frame is currently being output (and as result the current frame should be ignored), and potentially whether there are channel characteristics which should be considered in the compression, such as excessive packet loss, which affect decisions for the compression (e.g., in terms of the frequency of I tiles, etc). As the peak data rate or other channel characteristics change over time, as determined by an app/game server  1521 - 1525  supporting each user monitoring data sent from the client  415 , the app/game server  1521 - 1525  sends the relevant information to the shared hardware compression  1530 . 
     The shared hardware compression  1530  also packetizes the compressed video/audio using means such as those previously described, and if appropriate, applying FEC codes, duplicating certain data, or taking other steps to as to adequately ensure the ability of the video/audio data stream to be received by the client  415  and decompressed with as high a quality and reliability as feasible. 
     Some applications, such as those described below, require the video/audio output of a given app/game server  1521 - 1525  to be available at multiple resolutions (or in other multiple formats) simultaneously. If the app/game server  1521 - 1525  so notifies the shared hardware compression  1530  resource, then the uncompressed video audio  1529  of that app/game server  1521 - 1525  will be simultaneously compressed in different formats, different resolutions, and/or in different packet/error correction structures. In some cases, some compression resources can be shared amongst multiple compression processes compressing the same video/audio (e.g., in many compression algorithms, there is a step whereby the image is scaled to multiple sizes before applying compression. If different size images are required to be output, then this step can be used to serve several compression processes at once). In other cases, separate compression resources will be required for each format. In any case, the compressed video/audio  1539  of all of the various resolutions and formats required for a given app/game server  1521 - 1525  (be it one or many) will be output at once to outbound routing  1540 . In one embodiment the output of the compressed video/audio  1539  is in UDP format, so it is a unidirectional stream of packets. 
     The outbound routing network  1540  comprises a series of routing servers and switches which direct each compressed video/audio stream to the intended user(s) or other destinations through outbound Internet traffic  1599  interface (which typically would connect to a fiber interface to the Internet) and/or back to the delay buffer  1515 , and/or back to the inbound routing  1502 , and/or out through a private network (not shown) for video distribution. Note that (as described below) the outbound routing  1540  may output a given video/audio stream to multiple destinations at once. In one embodiment this is implemented using Internet Protocol (IP) multicast in which a given UDP stream intended to be streamed to multiple destinations at once is broadcasted, and the broadcast is repeated by the routing servers and switches in the outbound routing  1540 . The multiple destinations of the broadcast may be to multiple users&#39; clients  415  via the Internet, to multiple app/game servers  1521 - 1525  via inbound routing  1502 , and/or to one or more delay buffers  1515 . Thus, the output of a given server  1521 - 1522  is compressed into one or multiple formats, and each compressed stream is directed to one or multiple destinations. 
     Further, in another embodiment, if multiple app/game servers  1521 - 1525  are used simultaneously by one user (e.g., in a parallel processing configuration to create the 3D output of a complex scene) and each server is producing part of the resulting image, the video output of multiple servers  1521 - 1525  can be combined by the shared hardware compression  1530  into a combined frame, and from that point forward it is handled as described above as if it came from a single app/game server  1521 - 1525 . 
     Note that in one embodiment, a copy (in at least the resolution or higher of video viewed by the user) of all video generated by app/game servers  1521 - 1525  is recorded in delay buffer  1515  for at least some number of minutes (15 minutes in one embodiment). This allows each user to “rewind” the video from each session in order to review previous work or exploits (in the case of a game). Thus, in one embodiment, each compressed video/audio output  1539  stream being routed to a user client  415  is also being multicasted to a delay buffer  1515 . When the video/audio is stored on a delay buffer  1515 , a directory on the delay buffer  1515  provides a cross reference between the network address of the app/game server  1521 - 1525  that is the source of the delayed video/audio and the location on the delay buffer  1515  where the delayed video/audio can be found. 
     System and Method for Encoding Control Signals 
     One embodiment of the invention encodes control signals for an input device of a client using the existing communication capabilities of the client. Specifically, in one embodiment, an input device such as a game controller which is not natively supported by the client is connected to the client by mimicking an input device that is supported by the client (e.g., such as a keyboard). In the embodiments described below, a Bluetooth communication channel is used to connect the game controller to the client device. It should be noted, however, that the techniques described herein are not limited to Bluetooth and are not limited to a game controller input device. 
       FIG. 4  illustrates one embodiment of the invention in which a game controller  421  is connected to a communication interface  440  such as a Bluetooth interface of a client  415  (e.g., an iPad). In one embodiment, the client  415  does not natively support the game controller  421  as an input device. Consequently, when pairing the input device  421  with the client  415 , the input device  421  mimics an input device which is supported by the client  415  such as a keyboard. That is, the input device  421  communicates in a way which causes the client  415  to think that the input device  421  it is a keyboard (or other input device which is supported). Specifically, in one embodiment, the input device  421  packs control commands into packet control fields designated for the mimicked input device which the client  415  is capable of receiving and processing. 
     As illustrated generally in  FIG. 4 , the control signals  406  are received and decoded by control signal decoding logic  445  and the decoded control signals  409  are sent to the hosting service  210  via a network interface  441  such as an Ethernet or WiFi interface. Application or video game servers on the hosting service  210  then execute the video game or application in response to the control signals as previously described and the video generated by the application or video game is compressed and streamed to the client as low-latency compressed video  450 . The compressed video  450  is received via the client&#39;s network interface  441 , decoded by video decoder  453  and displayed on the device&#39;s display  454 . It should be noted, however, that the underlying principles of the invention are not limited to an online application or video game hosting service  210 . 
     As mentioned above, in one embodiment of the invention, the communication interface  440  is a Bluetooth interface and the game controller  421  (or other input device) pairs with the client  415  over a Bluetooth channel (using known Bluetooth pairing techniques but with the game controller mimicking another device type such as a keyboard). Using Bluetooth, it is possible to send 6 bytes at a time. However, not just any byte value can be sent. There are a limited number of legal symbols which may be transmitted over the Bluetooth interface (e.g., 75 out of 256 possible values). Moreover, in one embodiment, the client is natively configured to sort the symbols transmitted over the Bluetooth interface. For example, if the input device  421  transmits a set of symbols in the form FEDBCA, the communication interface  440  will inherently sort the symbols in order—ABCDEF. 
     In one embodiment, the game controller  421  needs to transmit 64 bits at a time (i.e., a single controller event, such as a button press requires 64 bits). To encode the 64 bits, one embodiment of the invention transmits 3 Bluetooth packets with 22 bits of control data each and encodes the set of allowable symbols to be a 22-bit number in a way which is immune to the sorting performed by the client  415 . Said another way, the encoding scheme described herein squeezes 22 bits into multiple Bluetooth packets in a manner which is immune to reordering. 
     In one embodiment, the communication interface  440  is part of the operating system/driver layer on the client  415 . It receives each of the 3 Bluetooth packets and sorts the symbols as described above. For example, if the symbols in a packet are transmitted as FECDBA, then the communication interface  440  sorts the symbols as ABCDEF and provides the sorted symbols to the control signal decoding logic  445  which decodes the sorted symbols and provides the decoded control signals  409  to the hosting service  210 . 
     The specific manner in which the symbols are chosen to represent the control data (D) will now be described. In one embodiment, the number of data bits (B)=22, the size of the alphabet (N)=42, the number of symbols (K)=6.  FIG. 5  illustrates one specific example. (1) Decrement N and K. (2) The smallest available symbol is selected for transmission if and only if D&lt;(N choose K). (3) Otherwise, consider the next smallest symbol with (3a) D decremented by (N choose K) and (3b) decrement N. (4) Repeat (3) until a symbol is selected. (5) Repeat at (1) until all symbols are selected. In another embodiment, the algorithm may be optimized by precomputing the combinatorials (or sums of combinatorials) and storing them in tables. In other embodiments values, can be found efficiently in the tables using a sequential search, a binary search, or any other optimized method.  FIGS. 6A-6F  provides data for one specific example, but the underlying principles of the invention are not so limited. 
     In one embodiment, the various functional modules illustrated herein and the associated steps may be performed by specific hardware components that contain hardwired logic for performing the steps, such as an application-specific integrated circuit (“ASIC”) or by any combination of programmed computer components and custom hardware components. 
     In one embodiment, the modules may be implemented on a programmable digital signal processor (“DSP”) such as a Texas Instruments&#39; TMS320x architecture (e.g., a TMS320C6000, TMS320C5000, . . . etc). Various different DSPs may be used while still complying with these underlying principles. 
     Embodiments may include various steps as set forth above. The steps may be embodied in machine-executable instructions which cause a general-purpose or special-purpose processor to perform certain steps. Various elements which are not relevant to these underlying principles such as computer memory, hard drive, and input devices have been left out of some or all of the figures to avoid obscuring the pertinent aspects. 
     Elements of the disclosed subject matter may also be provided as a machine-readable medium for storing the machine-executable instructions. The machine-readable medium may include, but is not limited to, flash memory, optical disks, CD-ROMs, DVD ROMs, RAMs, EPROMs, EEPROMs, magnetic or optical cards, propagation media or other type of machine-readable media suitable for storing electronic instructions. For example, the present invention may be downloaded as a computer program which may be transferred from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of data signals embodied in a carrier wave or other propagation medium via a communication link (e.g., a modem or network connection). 
     It should also be understood that elements of the disclosed subject matter may also be provided as a computer program product which may include a machine-readable medium having stored thereon instructions which may be used to program a computer (e.g., a processor or other electronic device) to perform a sequence of operations. Alternatively, the operations may be performed by a combination of hardware and software. The machine-readable medium may include, but is not limited to, floppy diskettes, optical disks, CD-ROMs, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, magnet or optical cards, propagation media or other type of media/machine-readable medium suitable for storing electronic instructions. For example, elements of the disclosed subject matter may be downloaded as a computer program product, wherein the program may be transferred from a remote computer or electronic device to a requesting process by way of data signals embodied in a carrier wave or other propagation medium via a communication link (e.g., a modem or network connection). 
     Additionally, although the disclosed subject matter has been described in conjunction with specific embodiments, numerous modifications and alterations are well within the scope of the present disclosure. Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense.