Method and apparatus for using a network appliance to manage media communications

A method and apparatus for managing communication of encoded media from a plurality of media sources. In one embodiment, the method comprises determining, by a network appliance, an available bandwidth of a shared computer network connection used in the communication of the encoded media; communicating, by the network appliance, a common perception index value to the plurality of media sources; determining, by the network appliance, a required accumulated bandwidth for the encoded media communicated by the plurality of media sources; and adjusting, by the network appliance, the common perception index value based on a comparison of the available bandwidth and the required accumulated bandwidth; wherein the common perception index value defines a frame rate and a quantization level associated with the communication of the encoded media.

BACKGROUND OF THE INVENTION

1. Field of the Invention

Embodiments of the present invention relate generally to techniques for managing the flow of encoded media from various virtual machines to various associated clients through common packet switching and communication infrastructure. More specifically, a network appliance provides a common perceptual index to media encoders in order to manage the aggregate perceptual quality of media communicated across a shared channel.

2. Description of the Related Art

The pursuit for improved efficiencies in corporate computer infrastructure has resulted in an emerging trend to replace desktop computers with virtualized desktop infrastructure (VDI), where low complexity client devices connect to virtualized desktop computers located in a corporate data center via Local Area Network (LAN) or Wide Area Network (WAN). In such a model, high performance server computers in the data center each play host to many virtualized desktops and some form of remote computing protocol is deployed to facilitate the communication of the graphical user interface (GUI) from each virtualized desktop, typically to a corresponding remote client device. One challenge with such an approach relates to enabling network infrastructure to support the simultaneous communication of massive quantities of encoded media associated with many concurrent remote computing sessions without excessive network congestion. Such congestion causes packet loss or increased latency, either of which contributes to a degradation in the remote computing user experience. This is of particular significance to network protocols such as user datagram protocol (UDP) which lack inherent congestion control mechanisms.

Various explicit methods for managing network congestion related to continuous media streams, usually video, are known to the art. In the case of ACTIVE QUEUE MANAGEMENT (AQM), a network router drops packets when its buffers overflow. The specific AQM algorithm used in the Internet is called “Random Early Detection” (RED). Explicit Congestion Notification (ECN) is another method in which a bit in a packet en route to a client device is set by a network switch in the presence of congestion. The receiver then signals the congestion state to the transmitter during the packet acknowledgement process. In a related Forward Explicit Congestion Notification (FECN) method proposed for datacenter Ethernet networks, sources periodically generate probe packets that are modified by the switches along the path and then reflected by the receivers back to the sources. The sources react to the feedback received in the returning probes and set their video rate accordingly. If there are multiple congestion points on the path of a flow, multiple backward control messages will be sent back while only one of these—one with the highest level of congestion indication—will dominate the future rate of the flow. Backward Congestion Notification (BCN) is an alternative scheme proposed for congestion notification in datacenter Ethernet networks (under IEEE 802.1Qau group) in which congestion points signal the sender in the event of congestion, rather than requiring the receiver to reflect probe packets.

Datagram congestion control protocol (DCCP) and Dynamic Video Rate Control (DVRC) are other methods used in streaming video applications which rely on sender and receiver interaction to determine bandwidth and round trip time (RTT) estimates to facilitate adjusting the rate of the transmitted video stream.

The Asynchronous Transfer Mode (ATM) network architecture enables multimedia transport at guaranteed service levels using various traffic classes with different service policies. Constant bit rate (CBR) and variable bit rate (VBR) modes provide guaranteed cell rates negotiated during connection establishment, while available bite rate (ABR) mode uses available bandwidth to achieve further network utilization and the possibility of bandwidth renegotiation during transmission. Multimedia ATM architectures support continuous adjustment of the source rate based on congestion feedback information provided from the network while the connection remains active. In the presence of multiple video connections, fair bandwidth sharing or bandwidth scheduling methods may be used to allocate the bandwidth. However, such schemes lack flexibility to adjust to the time-varying nature of video.

Generally, methods directed to rate control of multiple media streams have not been optimized to meet the specific requirements of a VDI deployment in which network bandwidth and user experience associated with multiple concurrent remote computing sessions should be managed at a system level. Therefore, there is a need in the art for managing network congestion associated with multiple concurrent remote computing sessions.

SUMMARY OF THE INVENTION

Embodiments of the present invention generally relate to a method and apparatus for managing communication of encoded media from a plurality of media sources. In one embodiment, the method comprises determining, by a network appliance, an available bandwidth of a shared computer network connection used in the communication of the encoded media; communicating, by the network appliance, a common perception index value to the plurality of media sources; determining, by the network appliance, a required accumulated bandwidth for the encoded media communicated by the plurality of media sources; and adjusting, by the network appliance, the common perception index value based on a comparison of the available bandwidth and the required accumulated bandwidth; wherein the common perception index value defines a frame rate and a quantization level associated with the communication of the encoded media.

DETAILED DESCRIPTION

The invention may be implemented in numerous ways, including as a process, an article of manufacture, an apparatus, a system, and as a set of computer-readable descriptions and/or instructions embedded on and/or in a computer-readable medium such as a computer-readable storage medium. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. The Detailed Description provides an exposition of one or more embodiments of the invention that enable improvements in features such as performance, power utilization, cost, scalability, efficiency, and utility of use in the field identified above. The Detailed Description includes an Introduction to facilitate the more rapid understanding of the remainder of the Detailed Description. Additionally, the invention encompasses all possible modifications and variations within the scope of the issued claims.

The term processor as used herein refers to any type of processor, CPU, microprocessor, microcontroller, embedded processor, media processor, graphics processor, or any other programmable device capable of executing and/or interpreting instructions in a form of software (such as microcode, firmware and/or programs).

The term software as used herein refers to any type of computer-executable instructions for any type of processor, such as programs, applications, scripts, drivers, operating systems, firmware, and microcode. Computer-executable instructions include any types of instructions performed by a processor, such as binary instructions that are directly performed, instructions that are translated and/or decoded prior to being performed, and instructions that are interpreted.

FIG. 1illustrates selected details of an embodiment of a networked media communication system100(“system100”) comprising multiple host computers shown as a host computer110-1and a host computer110-2, each comprising multiple media sources. In various embodiments, each media source comprises a virtual machine (VM), illustrated as VM120-1through120-G in a memory114-1for host computer110-1and as120-H through120-K in a memory114-2for host computer110-2. Alternative media sources such as streaming video or audio sources are contemplated in alternative embodiments. Two host computers (referred to as host computers110) and four virtual machines (referred to as VMs120) are depicted for convenience but system100supports many host computers and tens or hundreds of virtual machines in different embodiments. Those of ordinary skill in the art will appreciate that the various data structures (including source image122, encoded media data queue124, Perceptual Quality Index (Pdx)126, Queue Index (Qdx)127and required transmission rate128(i.e., a bandwidth forecast) and machine executable software components (including encoder130and traffic manager140) of VM120-1are also present in the other VMs of system100, although not expressly illustrated. Each VM120is communicatively coupled via a communication session to one of a plurality of clients180or182(illustrated as clients180-1,180-P,182-1and182-Q) by a common appliance160(i.e., ‘appliance160’, also referred to as ‘network appliance160’) and a computer network170. In an exemplary embodiment, a server platform (i.e., a host computer110) hosts up to 128 VMs120, each coupled to one of 128 clients180or182via network170.

In an embodiment, each VM120is an independent computer or part of a computing platform, such as a computer server or the like, coupled to and enabled to communicate with one or more communication endpoints, such as one or more of the plurality of clients180or182. Each client180or182typically comprises an image decoder function, one or more computer display devices, and various I/O devices, such as a keyboard, mouse, and the like. Each VM120establishes a communication session with one of the plurality of clients180or182and uses the communication session to communicate media, such as digitized audio data and encoded image updates, to the associated client180or182(i.e., each VM120is typically associated with one client180or182by means of the communication session).

VM120is an environment generally designated for running software associated with a user interface located at client180or182. In various embodiments, the VM120comprises software components such as operating system, driver software, virtualized network interface and application software located in memory114for execution by a processor sub-system112(illustrated as a processor system112-1and a processor system112-2) configured to execute machine readable instructions. In an exemplary embodiment, each VM120comprises an operating system, such as a WINDOWS operating system from MICROSOFT, Inc. (e.g., WINDOWS XP or WINDOWS 7), a LINUX operating system available from many vendors, or a UNIX operating system, also available from many vendors including HEWLETT-PACKARD, Inc., or SUN MICROSYSTEMS, Inc. The application software, (e.g., word processing software, spreadsheets, financial data presentation, video or photo display or editing software, graphics software such as Computer Aided Design (CAD) software, Desktop Publishing (DTP) software, digital signage software, or the like) executes in conjunction with graphics drivers (e.g., OPENGL from SILICON GRAPHICS corporation, DIRECTX from MICROSOFT CORPORATION, ADOBE FLASH) or image composition software (e.g., the WINDOWS VISTA Desktop Windows Manager (DWM), or QUARTZ or COCOA from APPLE CORPORATION) to generate source image122. In an embodiment of system100in which desktop display images are compressed and transmitted, source image122comprises a 2D array of pixel values suitable for display presentation. In an embodiment comprising an audio system, source image122comprises audio data. Source image122is generally maintained in one or more designated regions of memory114, such as one or more frame buffer regions or alternative suitable image storage memory. It will be recognized by those skilled in the art that embodiments of VM120generally include other application software, operating system components, drivers, administrative software and the like, not depicted inFIG. 1so as not to obscure aspects of the present invention.

Memory114comprises any one or combination of volatile computer readable media (e.g., random access memory (RAM), such as dynamic random access memory (DRAM), static random access memory (SRAM), extreme data rate (XDR) RAM, Double Data Rate (DDR) RAM and the like) and nonvolatile computer readable media (e.g., read only memory (ROM), hard drive, tape, CDROM, DVDROM, magneto-optical disks, Erasable Programmable Read-Only Memory (EPROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Flash EPROM and the like). Moreover, memory114may incorporate electronic, magnetic, optical, and/or other types of storage media. Each VM120further comprises additional elements, such as a programmable encoder130(‘encoder130’) and a traffic manager140executed by the processor system112in the context of the associated VM120. In some embodiments, at least part of the encoder130and traffic manager140are implemented as hardware elements (such as part of an Application Specific Integrated Circuit (ASIC) or integrated hardware function of a processor sub-system), or as software components in memory114(such as one or more virtual appliances executed by a hypervisor or as a combination of virtual appliances and software components executed in the domain of a VM120), a software function executed by a processor external to processor system112(such as a Reduced Instruction Set Computer (RISC) processor integrated in an ASIC), or as a combination of software and hardware components.

The processor system112(illustrated as a processor system112-1and a processor system112-2) typically comprises one or more central processing units (CPUs) each comprising one or more CPU cores, one or more graphical processing units (GPUs) or a combination of CPU and GPU processing elements. Examples of a well known suitable CPU include workstation or server class processors such as 32-bit, 64-bit, or other CPUs including OPTERON or ATHLON class microprocessors manufactured by AMD Corporation; XEON, ‘Core i7’ or X86 class processors manufactured by INTEL; or a microprocessor such as a PowerPC or SPARC processor. However, any other microprocessor platform designed to perform the data processing methods described herein may be utilized.

The network interface150(illustrated as a network interface150-1and a network interface150-2) provides a high bandwidth and low latency packet interface such as Gigabit Ethernet, 10 Gigabit Ethernet or Fiber Channel coupling between the processor system112and the appliance160(in the case of encoded media communications between a VM120and a client180or182) or between the processor system112and a network (such as a LAN, WAN or the like) in the case of general data communications between a VM120and an endpoint such as a file server, web server or the like. Network interface150typically provides physical (PHY) and Media Access Layer (MAC) network services for processor system112. In some embodiments, network interface150is dedicated to supporting communications between VMs120and clients180or182and additional network interfaces are deployed to support other general data communications. Typically, higher layer network services such as TCP/IP and/or UDP/IP encapsulation, communication setup and teardown service, authentication functions, and security protocols such as provisioning of secure channels and packet encryption are provided by functions of VM120but one or more such services may be provided by an underlying hypervisor, a software appliance or implemented as functions of network interface150. In an embodiment, the processor system112and network interface150are coupled to memory114by one or more bus structures, such as memory, image, and/or I/O busses known to the art.

The collective VMs120-1through120-G of host computer110-1are generally scheduled for execution by a hypervisor function omitted fromFIG. 1. Such a hypervisor may be one of several commercially available hypervisor products including VMWARE ESX SERVER from VMWARE corporation, XENSERVER from CITRIX Corporation, or HYPER-V from MICROSOFT Corporation.

Generally, the encoder130(detailed inFIG. 2) is an image stream encoder that uses various encoding techniques (e.g., image transformations) defined by a set of encoding parameters to encode source image122and generate encoded media data. Typically, a packet management function of VM120(not shown inFIG. 1) segments the encoded media data into packets, applies packet headers and queues the encoded media in encoded media data queue124(‘queue124’) for transmission. The queue124comprises one or more regions of memory114designated for the storage of encoded media data, e.g., in the form of compressed pixels, progressive refinement updates, video descriptors and/or drawing commands generated by encoder130.

Traffic manager (TM)140is generally a data management and scheduling function that manages bandwidth allocation and regulates the flow of encoded media data between queue124and appliance160by setting the relative transmission priority for encoded media data against competing data such as connection management data, Universal Serial Bus (USB) or audio peripheral device data or file transfers. Traffic manager140assembles one or more transfer command queues comprising prioritized Direct Memory Access (DMA) instructions. The DMA instructions are consumed by list processing (i.e., DMA) functions of network interface150to ensure the scheduled transfer of encoded media at the specified bit rate. Traffic manager140enables queue124to be emptied at the specified bit rate by providing a time base periodically synchronized with real time clock services from the underlying hypervisor. In various methods described herein, traffic manager140is tasked with temporary adjustment of the transmission rate or suspension of encoded media data flow in response to Qdx messages received from the appliance160.

In various embodiments, processor system112, memory114and network interface150are coupled with the aid of support circuits, including at least one of north bridge, south bridge, chipset, power supplies, clock circuits, data registers, I/O interfaces, and network interfaces. In other embodiments, the support circuits include at least one of address, control, interrupt and/or data connections, controllers, data buffers, drivers, repeaters, and receivers to enable appropriate communications between the CPU processor, memory114and network interface150. In some embodiments, the support circuits further incorporate hardware-based virtualization management features, such as emulated register sets, address translation tables, interrupt tables, Peripheral Component Interconnect (PCI) I/O virtualization (IOV) features, and/or I/O memory management unit (IOMMU) to enable DMA operations.

The appliance160comprises a processing function (e.g. a combination of processor, switch queue monitoring facilities, and machine-readable software) designated to execute a control method that generates a common perceptual quality index (Pdx)126(also referred to as Pdx value126) and, in some embodiments, a Qdx127(also referred to as Qdx value127) in response to bandwidth forecasts provided by the various VMs120. An embodiment of such a network appliance is depicted inFIG. 3.

The network170comprises a communication system (e.g., the Internet, LAN, WAN, and the like) or similar shared packet switched network that employs various well-known protocols (e.g., TCP/IP, UDP/IP and the like) to connect computer systems completely by wire, cable, fiber optic, and/or wireless links facilitated by at least one appliance160. Embodiments of the present invention may also comprise well-known network elements, such as hubs, switches, and/or routers (such as router162coupled to appliance160by shared computer network connection172(‘link172’) and router164coupled to appliance160by link174.) between the appliance160and a client180or182. In other embodiments, routers162and/or164are replaced or augmented by layer2switching devices known to the art. In various embodiments links172and174represent different constrained network paths such as WAN links between a data center and different facilities such as branch offices, with clients180located at one facility and clients182located at a different facility. The processing methods disclosed herein anticipate at least one such shared link, typically to a facility, although multiple such links, each operating under different constraints are generally anticipated (e.g., a combination of separate shared T1, 10 Mb/s, 100 Mbps and/or DS3 links, and the like) to different facilities. As one specific deployment example, link172comprises a T1 link for 5 clients180at a first facility and shared link174comprises a DS3 link for 120 clients182at a second facility. In some cases, links172or174might provide unreliable bandwidth (e.g. Digital Subscriber Line (DSL) service) and network appliance160adjusts the perceptual quality experienced at the clients180or182responsive to the varying available bandwidth.

Clients180and182are generally any form of computing device that can display or store media, such as image data, and connect to network170. For example, in an embodiment, clients180and182are remote terminals in a networked computer system (e.g., in an embodiment, system100is a remote computing system). Such remote terminals include zero clients, thin clients, personal or tablet computers, workstations, Personal Digital Assistants (PDAs), wireless devices, storage systems, and the like. In some embodiments, each client180and/or182incorporates an image decoder that decodes image information for presentation on one or more local display devices, such as a remote Graphical User Interface (GUI). In other embodiments, clients180and/or182also comprise one or more peripheral devices such as mouse, keyboard, and/or other well known peripherals such as printers, webcams, microphones and speakers.

FIG. 2is a block diagram200of the encoder130coupled between source image122and an encoded media data queue124in accordance with one or more embodiments of the present invention. Different regions of source image122are typically updated at different times by any of the installed software applications in an asynchronous manner. Unlike a constant frame rate video sequence, these image updates may be sporadic from both spatial and temporal perspectives.

The encoder130is an image encoder typically comprising a decomposition function230, a lossy encoder function202and a lossless encoder function210under control of encoder manager220. Decomposition function230classifies changed regions of source image122according to encoding requirements, for example high contrast regions (e.g., text) or monotone backgrounds are designated for lossless encoding by encoder function210while pictures (e.g., JPEG image representations) or frames associated with video sequences are designated for lossy encoding by encoder function202. In some embodiments, the lossy encoder function202comprises progressive encoding capabilities in which an initial lossy reproduction (i.e., an inexact replica) of a display image is refined over a period of time, culminating in a lossless reproduction of the display image. In an embodiment, the lossy encoder function202includes a transform function204, a quantize function206, and an entropy encoder function208which transform changed regions of source image122, quantize the resulting transform coefficients to a quantization level specified by quantization level224and perform entropy encoding on the quantized values.

The transform function204applies a transform function to changed regions of source image122using Discrete Wavelet Transform (DWT), Discrete Cosine Transform (DCT), Discrete Fourier Transform (DFT), or alternative comparable image transform methods known to the art. The quantize function206reduces the number of bits of the resulting transformed coefficients by reducing a precision for each resulting transformed coefficient. The entropy coder function208further compresses the quantized values using lossless coding methods such as Huffman encoding, Golomb coding, variable length coding (VLC), context-adaptive VLC, context-adaptive binary arithmetic coding (CABAC) or comparable methods.

Encoder manager220initiates a scan of source image122(or a portion thereof) for pixel changes, typically responsive to queue124reaching a ‘near empty’ state but alternatively at a specified frame encoding rate determined by encoding parameters222in some embodiments. In certain embodiments, the frame rate for all or part of source image122(e.g. a part of the image associated with user typing activity) may be increased temporarily to support improved interaction between the user and computer110(e.g., based on detection of cursor events, keystrokes or mouse movement associated with a client180or182). Such an increase in frame rate may require a corresponding temporary decrease in static image quality (i.e., increased image quantization level) to maintain a transmission bandwidth level in accordance with a bandwidth forecast provided by encoding manager220to appliance160. In some embodiments, encoder manager220specifies different encoding rates for different specified regions of source image122. In one embodiment, one or more regions for which minimum latency is desirable, such as select regions associated with a cursor or mouse pointer location, are assigned a higher encoding rate or prioritized over other regions of source image122. In embodiments where content types are specified for encoding at a reduced quality, for example as determined by administrative policies (e.g., video content specified for reduced quality), image frames are subjected to temporal filtering before encoding. Such sub-sampling may be strictly periodic, or based on knowledge of the image content, or based on change characteristics or a combination thereof. In some embodiments, encoding priorities are further determined by image update attributes (e.g., time elapsed since updated image content has been transmitted), media type (e.g., lossless content updates prioritized over residual updates for natural image types), or device-dependent attributes (e.g., pointer updates or updates related to cursor position prioritized over other content updates.

Encoding parameters222comprise a quantization level224and a frame rate that determine the optimum operation of encoder130for a specified Pdx126. The Pdx126determines quantization level224, using for example the Pdx vs. compression ratio curves provided in graph600described below. In an embodiment, the quantization level224is based at least in part on the number of pixels of source image122that have changed since a previous encoding of source image122(i.e. the updated portion of source image122). The quantization level224changes the image quantization level which in turn adjusts the compression ratio for one or more specified changed image regions, changes the fill rate of queue124, and increases or decreases perceptual image quality. A high compression ratio is accomplished by setting aggressive coefficient values in one or more quantization tables so that compressed media consumes a limited available bandwidth. High image quality is accomplished by reducing the quantization level to produce perceptually lossless or near-lossless representations of the source image122. Parameters222may also comprise additional encoder specifications such as a defined initial quality level and progressive refinement rate for a progressive encoder.

Lossless encoder function210comprises at least one of a Golomb encoder, Rice encoder, Huffman encoder, variable length encoder (VLC), context-adaptive VLC Lempel-Ziv-Welch (LZW) encoder or context-adaptive binary arithmetic encoder (CABAC) suited to lossless encoding of image regions designated for lossless encoding. In some embodiments, lossless encoder function210is also enabled for residual encoding of unchanged image sections, previously designated for lossy encoding and a specified (lossy) quality level has been reached.

The encoder manager220is generally a controller, such as an embedded processing core (e.g., a microprocessor core from MIPS Technologies), and related software functions and/or a logic circuit configured to manage the various functions of encoder130. Encoder manager220configures the lossy and lossless encoder functions202and210, manages the scanning of source image122for changes (e.g., utilizing a dirty mask to record changed pixel values) and provides Direct Memory Access (DMA) resources for accessing source image122or storing encoded media data in queue124. In some embodiments, encoder manager220monitors drawing commands issued by application software of VM120to determine changed areas of source image122or determine content type (e.g., video, photograph or text content types). By identifying the content type, encoder130is enabled to select the most appropriate encoder function and optimum compression level.

The traffic manager140generally determines a required transmission bandwidth128(i.e., bandwidth forecast) which is communicated to appliance160. The bandwidth forecast is based on the size of an encoded data set generated by encoder130in view of the current frame rate or a predicted size of an encoded data set associated with a forthcoming encoding operation. Such a prediction might be based on determination of changed image area, historic bandwidth, determination of image content type and so on. In some embodiments, appliance160periodically provides traffic manager140with an updated Qdx value127, where after traffic manager140responds by one of i) temporarily suspending media transmission from queue124to network interface150; ii) temporarily reducing or increasing the packet rate from queue124to network interface150or iii) resuming a media transmission packet rate from queue124to network interface150equivalent to the rate at which queue124is filled by encoder130.

In one or more embodiments, components of the encoder130and traffic manager140are implemented as a set of computer-executable instructions in a VM120, a digital media processor or virtualized appliance, an Application Specific Integrated Circuit (ASIC) configured, at least in part, as a logic circuit to perform image encoding, field-programmable Gate Array (FGPA), and/or electronic hardware suitable for performing image encoding or any combination thereof.

FIG. 3is block diagram300of an embodiment of network appliance160, generally enabled to execute the method400described below. Appliance160maximizes the use of available bandwidth on each shared link (ref. links172and174), minimizes transmission delay by optimizing queue depths between the media source and the client and enables all users of a shared link to share the available bandwidth such that each user is provided an optimum user experience consistent with other users of the shared link. Appliance160comprises ingress and egress interfaces310and330, respectively, each interface comprising physical, data-link, and network layer interfaces known to the art that provide compatibility with network170. In one embodiment, appliance160comprises a physical apparatus such as an access switch workgroup switch, or network router. In another embodiment, at least part of appliance160comprises virtualized elements executed as machine readable instructions in the hypervisor domain or a virtual machine of a server platform. In some such virtualized embodiments, input and/or output physical layer interfaces are substituted with interfaces to memory of the server platform.

Shared memory320generally comprises data buffers enabled to queue encoded media and other data types traversing the appliance160. Such data buffers include receivers for receiving encoded media from active media sources (such as VM120-1through VM120-K of system100) and egress channels326(shown as an egress channel326-1and an egress channel326-2) allocated to queue encoded media en route to client endpoints. Egress channels326comprise physically or logically separated memory structures reserved for encoded media from queues124. While only two egress channels326are depicted in illustration300, typically each shared computer network connection (ref. link172and link174) associated with appliance160, identified by a common IP or sub-net address, a VLAN identifier, proprietary address information in packet headers or the like, is allocated a separate egress channel (i.e., in an embodiment, egress interface330may comprise multiple physical interfaces connected to different downstream routers or switches).

Packet processor340generally provides switching and/or routing functions including network protocol processing, bandwidth allocation, scheduling, traffic shaping, packet header inspection and generic traffic management functions for managing the flow of encoded media traffic and other network data from ingress interface310to egress interface330. In an embodiment, packet processor340comprises one or more processing engines, such as advanced RISC machine (ARM), Microprocessor without Interlocked Pipeline Stages (MIPS), serial data processor (SDP), and/or other RISC cores enabled to execute buffer management, table lookup, queue management, fabric processing, and host processing functions known to the art. In an exemplary embodiment, processor340comprises an XSCALE processor from MARVEL Corporation or similar switch processor from BROADCOM Corporation, operating in conjunction with a suitable host processor such as a POWERPC processor.

Management function350generally comprises processing functions enabled to execute select steps of method400such as determination of required accumulated bandwidth and available bandwidth, adjustment of Pdx value126, determination of Qdx127, monitoring queue levels of egress channels326and setting egress traffic shapers. In an embodiment, function350comprises a logic sequencer, an independent processor (such as a MIPS or PowerPC processor) with a set of machine readable instructions stored in local memory or a set of machine readable instructions executed by a function of a physical or virtualized packet processor340. Management function350is enabled to configure and manage source list324which provides a view of currently subscribed VMs120to which Pdx values126are communicated. In one embodiment, management function350manages the subscriptions based on the presence or absence of content from particular host domains (i.e., VMs120) in the egress channels326. If a particular media source stops transmitting encoded media data for a defined period, the subscription expires and the communication of Pdx values126ends until a new communication session is established. Such an embodiment addresses the case of a user disconnecting from a client180or182for a short period (e.g., a few minutes) and establishing a different network path when the communication session is re-established.

FIG. 4is a flow diagram of a method400for managing communication of encoded media from a plurality of media sources (e.g. a plurality of VMs120) as may be executed by appliance160in accordance with one or more embodiments of the present invention. Generally, method400manages bandwidth associated with shared computer network connections (such as link172and link174) at a system level by providing feedback from appliance160to encoders (ref. encoder130) and, in some embodiments, traffic managers (ref. TM140), thereby enabling relatively consistent packet rates for encoded media streams.

Method400starts at step401and proceeds to step402(“Initialize”). Initialization comprises allocation of resources in the appliance160, including initialization of receivers, egress channels, switching resources, address tables, processing resources, memory bandwidth, and the like. A source list that maps each VM120to an egress channel (e.g., an egress channel162) is established so that individual bandwidth forecasts can be aggregated and tracked as accumulated bandwidth forecasts associated with each egress channel. Communication sessions that share an egress channel may be logically grouped so that the corresponding media sources can be managed as a group (i.e., communication of a common Pdx value126to the group of media sources associated with each egress channel). In some embodiments, one or more VMs pre-subscribe with appliance160during client session establishment. The pre-subscription step provides each VM an opportunity to forecast bandwidth requirements, for example according to historic bandwidth usage or administrative settings, in advance of media transmission. It also enables appliance160to estimate a meaningful start Pdx value126based on the number of media sources subscribed and initial available bandwidth. In some embodiments, appliance160observes packet headers (presented as non-encrypted ‘clear text’ headers in some embodiments) for transport protocol information such as VM source IP address or alternative VM identifier and destination client IP address of packets communicated through the appliance160in order to determine the identity of media sources mapped to each egress channel.

Method400proceeds to step410(“Determine available bandwidth”). In select embodiments, characteristics including available channel bandwidth, and optionally round trip latency are determined for each egress channel326by observing the steady state aggregate bandwidth (or variations therein) of all the communication sessions associated with each egress channel. In an exemplary embodiment in which User Datagram Protocol (UDP) is utilized at the network transport layer, packet loss metrics are used to determine available bandwidth. Appliance160observes transport protocol information such as existence and timing of anticipated response acknowledgement messages (i.e., ‘transport acknowledgement’) associated with packets used to transport the encoded media. The application layer is monitored for No Acknowledgement ‘flack’ messages (e.g., as communicated by a client180or182to a VM120) when an expected packet, typically identified by a sequence number, is dropped by network170. The measured available bandwidth at which such ‘nack’ messages become statistically significant (e.g., a packet loss determined to be greater than the target packet loss stipulated in a Service Level Agreement (SLA) for the network170) generally determines the available bandwidth associated with the shared link. In other embodiments, available channel bandwidth is predetermined based on known network characteristics or historic usage patterns.

Method400proceeds to step420(“Communicate perception index”) where a common Pdx value126is communicated from appliance160to each VM120associated with a common egress channel326. On an initial pass, each VM may be issued an initial Pdx value126, such as a default value (e.g., 50) or a value based on communication history, pre-registration information, a predicted accumulated bandwidth, initial accumulated bandwidth or the like. On subsequent passes, the updated Pdx126determined at step450(described below) is communicated. For efficiency purposes, the Pdx value126may be appended in a packet header of unrelated communications between the client180or182and a VM120.

Method400proceeds to step430(“Receive bandwidth forecasts”). Step430comprises receiving a bandwidth forecast from each of the VMs120associated with a particular egress channel326, each bandwidth forecast indicating the bandwidth required to communicate the media data in an encoded media queue (e.g., encoded media data queue124) ready for communication (i.e., a respective portion of the encoded media comprising an encoded image frame or partial encoded image frame) or predicted encoded media associated with a forthcoming encoding operation. The bandwidth forecast may be calculated at each VM120by dividing the size of the encoded media data set in queue124(typically expressed as megabits) by the frame period (i.e., an inverse of the present frame rate) specified by the present Pdx value126. In an embodiment, a predicted bandwidth forecast is incorporated with one of the last encoded media packets associated with an encoded frame (e.g., as an extractable value) and communicated to appliance160, providing appliance160an opportunity to respond to the bandwidth forecast by adjusting Pdx value126(step450described below) before the next frame is encoded. In another embodiment, the calculated bandwidth forecast is incorporated with a first packet of an already encoded frame, providing appliance160an opportunity to broadcast an updated Pdx to other VMs120before the encoded frame is transmitted at the forecasted bandwidth.

Method400proceeds to step440(“Determine Required Accumulated Bandwidth”). In an embodiment, the required accumulated bandwidth is the sum of bandwidth forecasts associated with individual communication sessions tied to a particular egress channel326. In other embodiments, the required accumulated bandwidth may be derived, at least in part, from the recent fill rate of the pertinent egress channel326.

Method400proceeds to step450(“Adjust Perception Index”). In an embodiment, appliance160adjusts Pdx126in proportion to the difference between available bandwidth determined at step410and required accumulated bandwidth determined at step440. If the bandwidth difference is unchanged, Pdx value126is unchanged, if the accumulated bandwidth forecast (i.e., the ‘required accumulated bandwidth’) exceeds the available bandwidth as determined at step410, the Pdx value126is lowered in proportion to the difference and if the accumulated bandwidth forecast is less than the available bandwidth as determined at step410, the Pdx value126is increased in proportion to the difference. In some embodiments, Pdx126need not be communicated on every iteration of step450in the interest of reducing control traffic received by VM120. For example, in one embodiment, Pdx126is communicated less frequently when the required or forecasted accumulated bandwidth and/or egress channel queue depths are within acceptable limits, but is communicated more frequently when the specified limits are violated.

Method400proceeds to step460(“Queue and Transmit Media”) in which packets in the various egress channels326are transmitted across respective shared links, shaped to rates determined in step410that match the bandwidth of the respective shared links.

In some embodiments in which additional control using Qdx127is used, method400proceeds to step470(“Determine and Communicate Qdx”), else method400may proceed directly to step480. If a specified queue level, such as a 75% full level, for an egress channel326is detected (generally signaling an increased latency on the shared link), a Qdx value is transmitted to the VMs120associated with the egress channel. The Qdx indicates a requirement for the VMs to adjust their respective packet rates for the encoded media data for a defined period of time. In an embodiment, the Qdx127is a binary value that instructs all VMs to suspend all media communications for a pre-determined period (e.g. a fixed 2 ms time period or partial frame period which may differ for different VMs dependent on the current frame rate). In another embodiment, the Qdx127specifies a proportional reduction (e.g. 50% reduction) in current packet rate. In another embodiment, the Qdx127specifies both a time period and a proportional reduction in packet rate.

Method400proceeds to step480(“End?”). If any communication sessions associated with an egress channel remain active (i.e., at least one media source continues to transmit packets associated with the communication session), method400proceeds to step484(“Update source list”) and thereafter returns to step410. At step484, the current status of each communication session is verified, for example by conducting an audit of the status of each active communication session (e.g. observing transport protocol information from packets communicated through appliance160) or auditing packets in the egress channel326. The source list is updated to reflect any subscription changes such as additional VMs utilizing defined egress channels, additional VMs demanding new egress channels associated with new shared links, recently terminated sessions and so on. If new sessions have been established, network appliance160may provide the new users with current bandwidth availability and number of other active users sharing the egress channel in order for new users to establish appropriate initial encoding parameters. In some embodiments, inactive sessions are terminated following a defined period of inactivity and the media source is notified that a new subscription will be required in order to re-allocate appliance resources. If all communication sessions have been terminated and associated packets processed, method400ends at step482.

FIG. 5is a block diagram of a method500for communicating media data from a media source to a client via an appliance160in accordance with one or more embodiments of the present invention. The steps of method500are generally executed by each of a plurality of VMs120sharing a computer network connection such that each VM transmits media data at its own determined packet rate set in response to a common Pdx value126provided by the appliance160.

Method500starts at step501and proceeds to step502(“Initialize”) in which a VM120initializes encoder130, traffic manager140and data structures including source image122, queue124and initial Pdx value126. Pdx126may be initialized to a default value, an historic setting or provided by appliance160during establishment of a communications session between VM120and a client180or182.

Method500proceeds to step510(“Receive Pdx Value or Update”) in which an updated Pdx value126(as transmitted by appliance160at step450of method400) is received and utilized to adjust the encoding parameters222. In a typical embodiment, step510comprises a background event handler of encoder130receiving updated Pdx values independent of the encoding and packet transmission process.

Method500proceeds to step520(“Encode Image Update”) in which an updated portion of an image frame, such as a portion of source image122with pixel values that have changed since a previous execution of step520, is encoded by encoder130and stored in queue124. It is generally recommended that different areas of an image frame maintain a consistent quantization level to minimize quality variations across a single image which may deteriorate the perceived image quality. The current frame rate is determined by the size of an image update (i.e., number of pixels to be encoded), for example following frame rate associations in graph800as described below.

Method500proceeds to step530(“Determine Required Transmission Bandwidth and Packet Rate”). The required transmission bandwidth128is a direct function of the selected frame rate and number of bits to be generated at step520stored in queue124. In some embodiments, the number of bits generated at step520is predicted based on size of changed portion of source image122and/or image content type so that a required transmission bandwidth can be determined ahead of actual encoding performed at step520. The packet rate set by traffic manager140sets an operating transmission rate based on the combination of required transmission bandwidth128and a slow start algorithm (e.g. a ramped packet rate or delayed transmission) that enables appliance160to broadcast an updated Pdx126before the operating transmission bandwidth is reached.

Method500proceeds to step540(“Provide Bandwidth Forecast”), which comprises communicating required transmission bandwidth128to appliance160, either as a separate message, as a message appended to the next (i.e., subsequent) transmitted packet, an initial packet associated with the next encoded frame or one of the last packets of a previously encoded frame. In some embodiments, the required transmission bandwidth128(i.e., an indication of the required transmission bandwidth) is communicated in a clear-text segment of one of the packets. In select embodiments where the forecasted required transmission bandwidth128is greater than the present required transmission bandwidth (e.g., as previously communicated to appliance160), the transition to the increased packet rate associated with the forecasted required transmission bandwidth128may be delayed by a specified period such as a sufficient time to ensure appliance160has received the updated bandwidth forecast and broadcast an updated Pdx value126.

Method500Proceeds to step550(“Qdx State?”). In various embodiments in which a queue index is used to control packet rate, process500proceeds to step560if a Qdx value127is defined (as determined at step470of method400) or proceeds to step570if no Qdx value is defined. At step560(“Update Packet Rate”), the packet rate defined at step530is temporarily adjusted. For example, transmission may be suspended for a defined partial frame period

Method500proceeds to step570(“Transmit at Packet Rate”) in which the current encoded frame (stored in queue124) is transmitted to appliance160as a series comprising one or more packets at the packet rate determined at step530.

Method500proceeds to step580(“End?”), following which method500returns to step510if additional media is available in queue124for transmission, or method500ends at step582, for example on termination of the communication session. On each subsequent pass of method500, a subsequent updated portion of the source image122is encoded. A subsequent required transmission bandwidth128is determined based on the size of the subsequent updated portion and the frame rate defined by the Pdx value126. The subsequent encoded frame is transmitted as subsequent packets at a subsequent packet rate based on the subsequent required transmission bandwidth (i.e. bandwidth forecast128).

FIG. 6illustrates graph600showing an ideal range of compression ratios expressed in terms of compressed bits per pixel (bpp) for a range of Pdx values spanning the range 0 through 100 in accordance with one or more embodiments of the present invention. For any specified Pdx value, encoder130achieves the corresponding compression ratio by adjusting the quantization of the lossy encoder (ref. quantization level224) or reducing the update frame rate. In graph600, a Pdx of “0” determines an illegible image (for example, as defined using a subjective Mean Opinion Score (MOS) index) while a Pdx of “100” determines a lossless image. Plot610shows a compression range from 0 bpp for an illegible image determined by a Pdx of “0” through approximately a compression ratio of 20 bpp for a Pdx of “100” for a video display image (i.e., an image frame of picture type). Plot620shows a compression range from 0 bpp for an illegible image determined by a Pdx of “0” through a compression ratio of 7 bpp for a Pdx of “100” for a display image of mixed image type (i.e., an image frame comprising different areas of text, background and picture image types). The image of mixed image type achieves better compression when the different image types are subjected to different encoding methods (e.g., background image types are highly compressed by lossless encoder function210, text image types are suited to color cache encoding methods, and picture image types are suited to transform encoding methods such as wavelet or Discrete Fourier Transform (DCT) encoding executed by lossless encoder function202). In other embodiments, different lossy compression ratios are applied according to content characteristics, either by changing the encoder or by adjusting the quantization.

FIG. 7illustrates graph700showing two related video metrics as a function of Pdx for a set of Pdx values spanning the range 0 through 100 in accordance with one or more embodiments of the present invention. Plot710shows the Peak Signal to Noise ratio (PSNR) for a video image frame across the span of Pdx values. Plot720is an overlay of plot610fromFIG. 6which shows the compression ratio required to achieve the PSNR of plot710. The divergence between PSNR and bpp for Pdx values in the range of 90-100 is attributed to the fact that perceived image quality of a video frame sequence or picture image types does not correlate with the image PSNR in a linear manner.

FIG. 8illustrates graph800showing required compression ratios in terms of specified frame rate, expressed in terms of frames per second (fps) for a set of video sequences over the range of Pdx values between 0 and 100 in accordance with one or more embodiments of the present invention. Graph800provides a mapping for encoder manager220to determine update frame rates from Pdx126. Plot810depicts fps for a 50p progressive display video (i.e., 50 lines video type), plot820depicts fps for a 100p progressive display video, plot830depicts fps for a 200p progressive display video, plot840depicts fps for a 480p progressive display video, plot850depicts fps for a 720p progressive display video, and plot860depicts fps for a 1080p progressive display video.

FIG. 9is an illustration of a source image900associated with a single VM120shown during two time periods, illustrating one embodiment in which encoder130adjusts encoding parameters222for a given Pdx value126(shown as a period950and a period960) during which a source image is changing.FIG. 9Aillustrates period950during which source image900undergoes a series of consecutive frame updates. During period950, section902of source image900is changing but section904of source image900remains unchanged (i.e. static). Period950might be exemplified by a small 50p video window (section902) comprising pixels updated at 60 fps overlaid on a large static photograph (section904).FIG. 9Billustrates period960during which source image900undergoes a different series of consecutive frame updates in which section912of source image900remains unchanged but section914source image900is changing. Period960might be exemplified by a large 720p video display (section914) changing at a 30 fps video frame rate behind a static window (section912). In both time periods950and960, the selected frame encoding rate is dependent on the size of the changed image as defined by graph800in addition to the current Pdx value126. For example, given a Pdx value126of 55, section902will be encoded at approximately 30 fps during period950but section914will be encoded at approximately 5 fps, thereby taking approximately 6 times longer to complete each encoded frame update. Fair sharing of a common network link (e.g., shared computer network connection172or174) is accomplished by allocating more bandwidth to larger image updates than smaller image updates, but such larger image updates take longer to complete.

FIG. 10illustrates one embodiment of a sequence1020comprising a first time period1050in which a source image1000associated with a single VM120is changing, followed by a second time period1060in which the source image1000continues to change and a second source image1010associated with a second VM120sharing a constrained network link also changes. Sequence1020illustrates the manner in which two encoders use a common (dynamic) Pdx value126to determine separate encoding parameters in order to achieve fair sharing of a common network link.

Period1050might be exemplified by a period in which a small 50p video window (section1002) of source image1000is updated at 60 fps. During period1050, the Pdx126is determined by the queue level of an egress channel326associated with a single user of the common network link. A Pdx of 55 might generate an encoded frame rate of 30 fps as for period1050described.

Period1060might be exemplified by a period in which the small 50p video window (section1002) of source image1000continues to change at 60 fps but a large 720p video display changing at a 30 fps video frame rate (section1012) associated with the second source image1010of the different VM shares the common network link. At the start of period1060, the Pdx value126is decreased, responsive to an increased accumulated bandwidth forecast and/or an increase in the queue level of the egress channel326. The first encoder associated with source image1000responds to the decreased Pdx by reducing the frame rate (following curve810) and adjusting the quantization level (following curve610) to increase the compression ratio. The second encoder associated with source image1010adjusts encoding parameters according to the decreased Pdx value126, the frame rate following curve850and the quantization level following curve610. While the frame rate of section1002is reduced in period1060, it remains higher than the frame rate of the larger section1012. For example, by evaluating graph800, if the Pdx value126is decreased from 55 to 40, the 50p image frame rate (section1002) falls from approximately 30 fps to approximately 20 fps, while the 720p image frame rate (section1012) falls from approximately 5 fps to approximately 3 fps.

FIG. 11is a block diagram1100of a host computer1110which is an alternative embodiment of host computer110inFIG. 1. Host computer1110comprises processor system1112coupled to memory1114and User Interface (UI) Session Processor1140. Unlike host computer110in which encoder130and traffic manager140are executed at least in part as software functions, encoding is performed by one or more hardware-optimized encoders1130and traffic management is performed by one or more hardware-optimized traffic managers1170. In an embodiment, processor1140comprises a dedicated network interface1160. In other embodiments, processor1140utilizes network interface facilities provided by processor system1112. In one such embodiment, encoded media data is transferred back to VM1120where traffic management resources of VM1120regulate the transmission of encoded media data to appliance160.

The virtual machines VM1120-1and VM1120-2comprise source images1122-1and1122-2, respectively, equivalent to those for VMs120. However, queue124, Pdx126and Qdx127reside in memory1150of UI session processor1140, collectively labeled VM Data1152-1(queue124, Pdx126and Qdx127associated with VM1120-1) and VM Data1152-2(queue124, Pdx126and Qdx127associated with VM1120-2). An embodiment of UI session processor1140is disclosed in commonly assigned, co-pending U.S. patent application Ser. No. 12/657,618, filed Jan. 22, 2010, entitled “System and Method for Managing Multiple User Interface Sessions”, which is incorporated herein by reference in its entirety. In other embodiments in which processor1140is located on a different physical computing platform to host computer1110, each host computer comprising a media source stream source images to processor1140over one or more image busses, such as one or more Digital Visual Interface (DVI), THUNDERBOLT, PCI-EXPRESS or DISPLAYPORT interconnects.