HK1152810A

HK1152810A - Automated real-time data stream switching in a shared virtual area communication environment

Info

Publication number: HK1152810A
Application number: HK11106751.3A
Authority: HK
Inventors: David Van Wie; Paul J. Brody
Original assignee: Social Communications Company; David Van Wie; Paul J. Brody
Priority date: 2007-10-24
Filing date: 2008-10-16
Publication date: 2012-03-09

Description

Automated real-time data stream exchange in a shared virtual area communication environment

Background

When face-to-face communication is impractical, people often rely on one or more technical solutions to meet their communication needs. These schemes are typically designed to simulate one or more aspects of face-to-face communication. Conventional telephone systems enable voice communication between callers. Instant messaging (also known as "chat") communication systems enable users to communicate text messages in real-time through instant messaging computer clients interconnected by instant messaging servers. Some instant messaging systems additionally allow a user to be represented by a user-controllable graphical object (referred to as an "avatar") in a virtual environment. An interactive virtual reality communication system enables users in remote areas to communicate over multiple real-time channels and interact with each other by manipulating their respective avatars in a shared three-dimensional virtual space.

Interest in avatar-based virtual reality communication systems grows with the increased availability of computer systems with high processing power and high bandwidth network connections. The primary purpose of such virtual reality systems is to create a virtual space in which users can communicate and interact using real-time data streams (e.g., audio, video, and text chat streams). The virtual space is typically defined by a computer graphics specification that describes the visual geometry of the space, the colors and textures that are mapped onto the visual geometry, the nature of the collision that controls how the user maneuvers within the space, and the auditory properties of the space such as reverberation and sound absorption properties.

In a typical virtual reality system, each of the users communicates through an interface that is a source, sink, or both of one or more of the real-time data streams supported by the system. By default, the virtual reality system typically connects each source represented in the virtual space to each sink represented in the virtual space, subject to conditions specified in the global exchange rules, local user preferences, and properties of objects within the virtual space. These conditions are typically specified in terms of relative distance between objects. For example, some system configurations cause a real-time data stream connection not to be established if the separation between avatars exceeds a maximum threshold distance. In addition, some objects have been designed to affect how the data stream is rendered. For example, a barrier object blocks view and sound from a particular direction. The other objects are designed to affect the interaction zone associated with the user's avatar when the user's avatar is within the interaction zone of the objects. For example, the platform adapter object increases the size of the audio interaction space of avatars within the interaction space of the virtual platform, and the table adapter object folds the interaction spaces of all avatars located in the virtual table to a common interaction space across the virtual table.

Disclosure of Invention

In one aspect, the invention features a method of exchanging real-time data stream connections between network nodes sharing a virtual area. According to the method, a set of real-time data streams is ascertained. The real-time data streams enable a given one of the network nodes associated with the respective location in the virtual area to participate in a collaborative communication session with one or more other of the network nodes associated with the respective location in the virtual area. One or more real-time data stream connections that communicate a set of real-time data streams to a given network node are determined based at least in part on a bandwidth capability of the given network node. A real-time data flow connection is established between a given network node and one or more other network nodes in the network node.

Embodiments in accordance with this aspect of the invention may include one or more of the following features.

The process of determining the real-time data stream connections may comprise determining a respective form to be taken for receiving each of the real-time data streams, wherein each of the determined real-time data streams is in the form of an unmixed real-time data stream or a mixed real-time data stream derived from a combination of real-time data streams sent from network nodes of the other network nodes.

The process of determining the real-time data stream connections may include determining a network route over which each of the real-time streams is received, wherein the determined network route is a direct peer-to-peer network route or a network route that is mediated by one or more of the other network nodes.

The virtual area specification may be stored. The virtual area specification includes a specification of one or more switching rules, each defining a respective connection between a source of a respective real-time data stream type and a sink of the real-time data stream type according to a location in the virtual area, wherein at least one of the ascertaining and the determining is based on the switching rules.

A list of one or more mixed real-time data streams derived from real-time data streams transmitted from network nodes of the other network nodes may be transmitted to a given network node.

The process of determining the real-time data stream connections may include discovering bandwidth capabilities of one or more of the other network nodes and selecting one or more real-time data stream connections based on the discovered bandwidth capabilities.

The one or more determined real-time data flow connections may involve exchanging real-time data flows between network nodes in the first set through the central network node and exchanging real-time data flows between network nodes in the second set over the direct peer-to-peer network connection. The one or more determined real-time data stream connections may involve sending a mixed real-time data stream to the given network node, the mixed real-time data stream comprising the requested real-time data stream data and being derived from real-time data streams sent from network nodes of the other network nodes.

The process of determining real-time data stream connections may include determining one or more real-time data stream connections that maximize delivery of the unmixed real-time data streams to the given network node.

In another aspect, the invention features a method of exchanging real-time data stream connections between network nodes sharing a virtual area. According to the method, for each of one or more receiving network nodes in the network node, a respective link of a respective transmit set on which to transmit one or more real-time data streams is determined. Each of the links has a respective link bandwidth. For each of the links, allocating a respective link bandwidth between one or more lanes respectively allocated to the one or more real-time data streams in the respective transmit set and transmitting the one or more real-time data streams in the respective transmit set to the respective receiving network node on the respectively allocated lanes.

The process of determining the respective link may include, for each of the links, ascertaining one or more respective bandwidth levels for each of the one or more real-time data streams in the respective transmit set and allocating a respective link bandwidth to the link based on the ascertained bandwidth levels. For each of the links: the ascertaining of the respective bandwidth levels may include identifying a respective minimum bandwidth level for each of the real-time data streams in the respective transmission set; and calculating a respective minimum link bandwidth level from the one or more identified respective minimum bandwidth levels. The method may include dropping an arbitrary link in response to determining that the bandwidth available for the arbitrary link fails to meet a corresponding minimum link bandwidth level. For each of the links: the ascertaining of the respective bandwidth levels may include, for each of one or more of the real-time data streams in the respective transmit set, identifying at least two respective bandwidth levels in a respective priority order ordered from a respective first preferred bandwidth level to a respective second preferred bandwidth level; and calculating a corresponding target link bandwidth level based at least in part on the identified first preferred bandwidth level and a corresponding fallback link bandwidth level based at least in part on the identified second preferred bandwidth level. The process of determining the respective link may include, for each of the receiving network nodes, attempting to establish the respective link to the receiving network node at the target link bandwidth level; and in response to a failure to establish a respective link to the receiving network node at the target link bandwidth level, attempting to establish the respective link to the receiving network node at a fallback link bandwidth level. The process of attempting to establish a respective link may include comparing the target link bandwidth level with a current amount of bandwidth available to transmit the respective transmit set and a current amount of bandwidth available to the respective receiving network node.

The process of determining the respective link may comprise, for each of the receiving network nodes: attempting to establish respective links to the receiving network node at respective candidate link bandwidth levels; and in response to a failure to establish a respective link to the receiving network node at the respective candidate link bandwidth level, forgoing transmitting at least one selectable real-time data stream in the data set.

The process of determining the respective link may comprise, for each of the receiving network nodes: attempting to establish respective links to the receiving network node at respective candidate link bandwidth levels; and responsive to a failure to establish a respective link to the receiving network node at a respective candidate link bandwidth level, establishing links for transmitting one or more real-time data streams in the respective transmit set to the receiving network node over one or more intervening network routes in the other network nodes.

The process of determining the respective link may comprise, for each of the receiving network nodes: attempting to establish respective links to the receiving network node at respective candidate link bandwidth levels; and responsive to a failure to establish a respective link to the receiving network node at a respective candidate link bandwidth level, establishing a link to deliver one or more of the real-time data streams in the respective transmission set to the receiving network node, wherein the one or more mixed real-time data streams are in the form of a combination of real-time data streams transmitted from other network nodes.

The process of determining the respective link may include, for each of the links, allocating a respective bandwidth in an amount determined based on an attribute associated with the respective receiving network node.

For each of the links, the assignment of the respective link bandwidth may be based on one or more stream priority levels respectively associated with one or more real-time data streams in the respective transmit set.

Each of the links may be a respective unidirectional link from a respective one of the network nodes transmitting the respective transmit set to a respective one of the receiving network nodes.

The invention also features an apparatus that includes a computer-readable memory storing computer-readable instructions and a processing unit coupled to the computer-readable memory and operable to execute the instructions and, based at least in part on the execution of the instructions, to perform operations comprising the elements of the method described above. The invention additionally features a computer-readable medium storing computer-readable instructions for causing a computer to perform operations including the elements of the method described above.

In another aspect, the invention features a network adapter for exchanging real-time data stream connections between network nodes sharing a virtual area. The network adapter includes a computer-readable memory storing computer-readable instructions and a processing unit coupled to the computer-readable memory and operable to execute the instructions and, based at least in part on execution of the instructions, to perform operations comprising the following. For each of the one or more receiving network nodes in the network node, the processing unit determines a respective link of a respective transmit set on which to transmit the one or more real-time data streams. Each link has a corresponding link bandwidth. For each of the links, the processing unit allocates a respective link bandwidth between one or more lanes respectively allocated to the one or more real-time data streams in the respective transmit set and transmits the one or more real-time data streams in the respective transmit set to the respective receiving network node on the respectively allocated lanes.

Other features and advantages of the invention will become apparent from the following description, including the drawings and claims.

Drawings

Fig. 1 is a diagrammatic view of an embodiment of a network node including a graphical user interface presenting a two-dimensional depiction of a shared virtual area.

FIG. 2A is a diagrammatic view of an embodiment of a shared virtual area communication environment in which network nodes communicate in a peer-to-peer architecture.

FIG. 2B is a diagrammatic view of an embodiment of a shared virtual area communication environment in which network nodes communicate using a server-centric architecture.

Fig. 3 is a block diagram of an embodiment of a shared virtual area communication environment including an exemplary set of real-time data stream connections between sources and sinks of three network nodes.

Fig. 4 shows a block diagram of an embodiment of a network node comprising an exemplary set of sources and an exemplary set of sinks.

FIG. 5 is a diagrammatic view of an embodiment of a graphical user interface showing a perspective view of a virtual area including partitions associated with respective real-time data stream exchange rules.

FIG. 6 is a diagrammatic view of an embodiment of a graphical user interface showing a plan view of the three-dimensional virtual area shown in FIG. 5.

Fig. 7 is a block diagram of an embodiment of a regional client network node connected to a regional server network node and two other regional client network nodes in an embodiment of a shared virtual regional communication environment.

Fig. 8 is a diagrammatic view of an embodiment of the shared virtual area communication environment shown in fig. 7.

Fig. 9 is a flow chart of an embodiment of a method performed by a regional client network node and a regional server network node.

Fig. 10 is a flow diagram of an embodiment of a method by which an embodiment of a stream switching manager processes configuration data received from a zone server.

Fig. 11 illustrates a plan view of the virtual area illustrated in fig. 6, in which there are four avatar objects therein.

Fig. 12 is a flow diagram of an embodiment of a method of determining a real-time data stream connection to deliver requested data stream data to a regional client network node.

Fig. 13 is a flow diagram of an embodiment of a method of exchanging real-time data stream connections between network nodes sharing a virtual area.

Fig. 14 is a flow diagram of an embodiment of a method of exchanging real-time data stream connections between network nodes sharing a virtual area.

FIG. 15 is a block diagram of a host system including a network adapter with enhanced link management functionality.

Fig. 16 is a block diagram of an embodiment of the network adapter shown in fig. 15.

Fig. 17 is a flow diagram of an embodiment of a method of determining one or more real-time data stream processing topologies to deliver requested data stream data to a regional client network node.

FIG. 18 is a diagrammatic view of an embodiment of a real-time data stream processing topology.

FIG. 19 is a diagrammatic view of an embodiment of a real-time data stream processing topology.

FIG. 20 is a diagrammatic view of an embodiment of a real-time data stream processing topology.

FIG. 21 is a diagrammatic view of an embodiment of a real-time data stream processing topology.

FIG. 22 is a diagrammatic view of an embodiment of a real-time data stream processing topology.

Fig. 23 is a block diagram of an embodiment of a shared virtual area communication environment including an embodiment of a network switch that manages real-time data flow connections according to switching rules defined in a virtual area specification.

Detailed Description

In the following description, like reference numerals are used to identify like elements. Furthermore, the drawings are intended to illustrate major features of exemplary embodiments in a diagrammatic manner. The drawings are not intended to depict every feature of actual embodiments nor relative dimensions of the depicted elements, and are not drawn to scale.

Summary of the invention

Embodiments described herein provide systems and methods for exchanging real-time data stream connections in a shared virtual area communication environment. These embodiments enable the switching rules for connecting real-time data flows between network nodes communicating over a shared virtual area to be explicitly dependent on the specifications of the virtual area.

These embodiments allow the designer of the virtual area to control not only the shape and form of the virtual area, but also the manner in which the communicants interconnect through the real-time data stream. In this way, the zone designer can optimize the real-time data stream connections established between communicants sharing a virtual zone for a particular communication purpose or for a particular communication environment (e.g., personal space, gallery, concert hall, auditorium, conference room, and convention hall).

In addition, by making the automatic switching rules dependent on location in the virtual area, these embodiments reduce the complexity involved in connecting and disconnecting correspondent nodes and increase the scalability of the system (as compared to systems that establish and terminate connections based on the attributes and properties of objects within the virtual space and systems that tightly associate signal processing functions with stream routing, connection and disconnection functions).

Definition of terms

A "virtual area" is a representation of a computer-managed space or scene. The virtual area may be a two-dimensional or three-dimensional representation. Often times, virtual areas are designed to simulate physical, real-world space. For example, using a conventional computer monitor, a virtual area may be visualized as a two-dimensional image of a three-dimensional computer-generated space. However, the virtual area does not require an associated visualization to implement the switching rules.

The "virtual area specification" is a virtual area specification used in creating a shared virtual area communication environment.

A "partition" is a region of a virtual area associated with at least one rule for exchanging (e.g., routing, connecting, and disconnecting) real-time data flows between network nodes communicating through a shared virtual area.

A "communicant" is a person who communicates or otherwise participates in a shared virtual area communication session.

An "object" is any type of discrete element in a virtual area that is independent of the geometry of the virtual area. Objects typically have attributes or properties that are separate and distinct from the attributes and properties of the virtual area.

An "avatar" is an object representing a correspondent in a virtual area.

"location" in a virtual region refers to the location of a point or area or volume in the virtual region. A point is typically represented by a single set of two-or three-dimensional coordinates (e.g., x, y, z) that define the point in the virtual area. The area is typically represented by three-dimensional coordinates of three or more coplanar vertices defining the boundaries of the closed two-dimensional shape in a virtual area. A volume is typically represented by three-dimensional coordinates of four or more non-coplanar vertices that define the boundaries of a closed three-dimensional shape in a virtual area.

A "network node" is a node or connection point in a communication network. Exemplary network nodes include, but are not limited to, terminals, computers, and network switches.

A "computer" is a machine that processes data according to machine-readable instructions (e.g., software) stored temporarily or permanently on a machine-readable medium. Such a set of instructions to perform a particular task is referred to as a program or software program.

A "real-time data stream" is data that is constructed and processed using a continuous stream and is designed to be received with no delay or only an imperceptible delay; real-time data streams include digital representations of voice, video, user movements, facial expressions, and other physical phenomena, as well as data within a computing environment (which may benefit from quick-send, quick-execute, or both quick-send and quick-execute), including, for example, avatar movement instructions, text chat, real-time data feeds (e.g., sensor data, machine control instructions, transaction streams, and inventory quota information feeds), and file transfers.

A "data source" (referred to herein simply as a "source") is any of a device, a portion of a device (e.g., a computer), or software that originates data.

A "data sink" (referred to herein simply as a "sink") is any of a device, a portion of a device (e.g., a computer), or software that receives data.

An "exchange rule" is an instruction that specifies one or more conditions that must be met in order to connect or disconnect one or more real-time data sources and one or more real-time data sinks.

A "stream mix" is a combination of two or more real-time data streams of the same type (e.g., audio, video, chat, and motion data).

A "transceiver switch" is a network device that cross-connects network nodes (e.g., clients, servers, and network devices) by receiving analog or digital signals from the network nodes and transmitting the received signals (or copies of the received signals) to one or more other network nodes.

A "stream processing topology" is an organization of network routes over which real-time data streams (each of which may be a mixed stream or an unmixed stream) are delivered to one or more network nodes.

III introduction

Embodiments described herein provide systems and methods for exchanging real-time data stream connections in a shared virtual area communication environment. Communicants typically access such environments from respective network nodes executing respective copies of the communication software program with two-dimensional and three-dimensional visualization capabilities. The communication software program controls client processes that present respective views of the virtual area at respective network nodes and establishes real-time data stream connections with other network nodes. The communicants are typically represented in the virtual area by respective avatars that move throughout the virtual area in response to input instructions entered by the communicants at their respective network nodes. The virtual area view of the communicant is typically presented from the perspective of the communicant's avatar, which increases the level of engagement experienced by the communicant. Each communicant is typically able to view any portion of the virtual area around his or her avatar.

Fig. 1 shows an embodiment of a network node 10, which is implemented by a computer system comprising a display monitor 12, a computer mouse 14, a keyboard 16, speakers 18, 20 and a microphone 22. The display monitor 12 displays a graphical user interface 24. The graphical user interface 24 is a windows-based graphical user interface that may include a plurality of windows, icons, and pointers 26. In the illustrated embodiment, the graphical user interface 24 presents a two-dimensional depiction of a shared three-dimensional virtual area 28 representing a gallery. The communicants are represented in virtual area 28 by respective avatars 30, 32, 34, where each avatar may have a respective character (e.g., manager, artist, and visitor).

As explained in detail below, the virtual area 28 includes partitions 36, 38, 40, 42, 44 that are associated with respective rules governing the exchange of real-time data streams between network nodes represented by avatars 30-34 in the virtual area 28. (during a typical communication session, the dashed lines demarcating the partitions 36-44 in FIG. 1 are not visible to the communicants, although there may be visible clues associated with such area boundaries.) the exchange rules specify how the local connection process performed on each of the network nodes establishes communication with other network nodes based on the location of the communicants' avatars 30-34 in the partitions 36-44 of the virtual area 28.

During the communication session, each of the correspondent network nodes generates a respective set of real-time data streams (e.g., a motion data stream, an audio data stream, a chat data stream, a file transfer data stream, and a video data stream). For example, each communicant operates one or more input devices (e.g., computer mouse 14 and keyboard 16) that generate a stream of motion data that controls the movement of his or her avatar within virtual area 28. In addition, the communicator's voice and other sounds generated locally in the vicinity of the network node 10 are captured by the microphone 22. The microphone 22 produces an audio signal that is converted to a real-time audio stream. The respective copies of the audio streams are transmitted to other network nodes represented by avatars in the virtual area 28. Sound generated locally at these other network nodes is converted to real-time audio signals and transmitted to the network node 10. The network node 10 converts the received locally generated audio streams into audio signals rendered by the loudspeakers 18, 20. The motion data stream and the audio stream may be transmitted from each of the correspondent nodes to the other correspondent network nodes, directly or indirectly. In some stream processing topologies, each of the correspondent network nodes receives a copy of the real-time data stream sent by the other correspondent network nodes. In other stream processing topologies, one or more of the correspondent network nodes receives one or more stream mixes derived from real-time data streams sourced (originated) at other ones of the network nodes.

Fig. 2A is a diagrammatic view of an embodiment of a shared virtual area communication environment 50 in which three network nodes 52, 54, 56 are interconnected by a communication network 58 in a peer-to-peer architecture. The communication network 58 may be a Local Area Network (LAN) or a global communication network (e.g., the internet). The network nodes 52-56 are represented by respective computers.

In this architecture, each of the network nodes 52-56 sends a state change, such as an avatar movement in the virtual area, to each of the other network nodes. One of the network nodes (typically the network node that initiates the communication session) operates as a regional server. In the illustrated embodiment, the network node 52 assumes the role of a zone server. The regional server network node 52 maintains global state information and acts as a data server for the other network nodes 54, 56. The global state information includes a list of all of the objects in the virtual area and their corresponding locations in the virtual area. The regional server network node 52 periodically sends global state information to the other network nodes 54, 56. The regional server network node 52 also registers and sends initialization information to other network nodes requesting to join the communication session. In this process, the area server network node 52 sends a copy of the virtual area specification 60 to each joining network node, which may be stored in a local or remote database. The area server network node 52 also ensures that the other network nodes 54, 56 can synchronize to a global state in the event of a communication failure.

As explained in detail below, the virtual area specification 60 includes a description of the geometric elements of the virtual area and one or more switching rules governing real-time streaming connections between network nodes. The description of the geometric elements allows respective communication applications running on the network nodes 52-56 to present respective views of the virtual areas to the communicants on respective display monitors. The switching rules specify how the connection process executing on each of the network nodes 52-56 establishes communication with other network nodes based on the location of the communicant's avatar in the virtual area.

Fig. 2B is a diagrammatic view of an embodiment of a shared virtual area communication environment 62 in which network nodes 52-56 (referred to in the architecture as "area client network nodes") communicate in an architecture that is interjacent by an area server 64. In this embodiment, the zone server 64 assumes the zone server functions performed by the network node 52 in the peer-to-peer architecture embodiment shown in fig. 2A. In this regard, the regional server 64 maintains global state information and acts as a data server for the regional client network nodes 52-56. As explained in detail below, this architecture allows real-time data stream exchanges between the regional client nodes 52-56 to be handled in a variety of topologies, including peer-to-peer topologies, full server-centric topologies (where the regional server 64 operates as a communication proxy between the network nodes 52-56), and hybrid topologies (which combine aspects of peer-to-peer and full server-centric topologies).

Fig. 3 illustrates an exemplary set of real-time data stream connections between sources and sinks of three network nodes 52-56 in an embodiment of a shared virtual area communication environment. For ease of illustration, each of the arrows in fig. 3 represents a respective set of one or more real-time data streams. According to embodiments described herein, the connection shown in FIG. 3 is established based on the switching rules defined in the specification of the shared virtual area, the location of the communicant's avatar in the shared virtual area, and the particular sources and sinks available on each of the network nodes 52-56.

Fig. 4 illustrates an exemplary embodiment of a network node 52 that includes an exemplary set of sources 66 and an exemplary set of sinks 68. Each source is a device or component of the network node 52 that originates the data and each sink is a device or component of the network node 52 that receives the data. The set of sources 66 includes an audio source 70 (e.g., an audio capture device such as a microphone, etc.), a video source 72 (e.g., a video capture device such as a video camera, etc.), a chat source 74 (e.g., a text capture device such as a keyboard, for example), a motion data source 76 (e.g., a pointing device such as a computer mouse, etc.), and "other" sources 78 (e.g., a file share source or a source of customized real-time data streams, for example). The set of sinks 68 includes an audio sink (e.g., an audio rendering device such as a speaker or headphones, etc.), a video sink 82 (e.g., a video rendering device such as a display monitor, etc.), a chat sink 84 (e.g., a text rendering device such as a display monitor, etc.), a motion data sink 86 (e.g., a mobile rendering device such as a display monitor, etc.), and "other" sinks 88 (e.g., a printer for printing shared files, a device for rendering real-time data streams different than those already described, or software that processes real-time streams for analysis or customized display).

As exemplified by the network node embodiment shown in fig. 4, each of the network nodes may have a wide variety of sources and sinks available. By enabling the zone designer to control how connections are established between sources and sinks, the embodiments described herein provide the zone designer with a number of controls over the communicants' sensory experience as they communicate and otherwise interact in the virtual zone. In this way, the region designer can optimize the virtual region for a particular communication purpose or for a particular communication environment (e.g., gallery, concert hall, auditorium, conference room, and convention hall).

Defining virtual areas

A. Introduction to

The shared virtual area is defined by a specification that includes a description of the geometric elements of the virtual area and one or more switching rules governing real-time streaming connections between the network nodes.

The geometric elements of the virtual area typically include the physical geometry and the collision geometry of the virtual area. The physical geometry describes the shape of the virtual area. The physical geometry is typically constituted by surfaces of triangles, quadrilaterals or polygons. The colors and textures are mapped onto the physical geometry to form a more realistic appearance of the virtual area. The lighting effects may be provided, for example, by painting the lights onto a visible geometry and modifying the texture, color, or intensity proximate the lights. The collision geometry describes the invisible surface that determines the way in which the object can move in the virtual area. The collision geometry may be consistent with the visual geometry, correspond to a simpler approximation of the visual geometry, or be related to the specific application requirements of the designer.

The switching rules typically include a specification of conditions for connecting sources and sinks of the real-time data stream according to the location in the virtual area. Each rule typically includes attributes defining the type of real-time data stream to which the rule applies and the location or locations in the virtual area in which the rule applies. In some embodiments, each of the rules optionally may include one or more attributes that specify a required role for the source, a required role for the sink, a priority level for the flow, and a required flow processing topology. In some embodiments, if there are no explicit switching rules defined for a particular portion of the virtual area, one or more implicit or default switching rules may be applied to that portion of the virtual area. One exemplary default exchange rule is a rule that connects each source to each compatible sink within a region, subject to policy rules. Policy rules may apply globally to all connections between regional clients or only to corresponding connections with individual regional clients. An example of a policy rule is a proximity policy rule that only allows connection of sources and compatible sinks associated with respective objects within a specified distance (or radius) of each other in a virtual area.

B. Exemplary ways of specifying virtual regions

1. Geometric elements defining virtual areas

A wide variety of different three-dimensional graphic design tools and game-level design editing programs may be used to specify the geometric elements of the virtual area. In general, the specification of the geometric elements of the virtual area may be described in any type of three-dimensional descriptive language, including, but not limited to, VRML (see, e.g., http:// www.web3d.org/X3d/specifications/VRML), X3D (see, e.g., http:// www.web3d.org/X3d/specifications/X3d), COLLADA (see, e.g., http:// www.COLLADA.org), and U3D (see, e.g., http:// www.w3. org).

In some embodiments, the virtual area specification describes the geometric elements of the virtual area in terms of COLLADA, which is an XML-based digital asset exchange schema that includes "tags" or "elements" (i.e., words enclosed by "<" and ">") and "attributes" (i.e., attribute name "value"). In some of these embodiments, the COLLADA description of the geometric elements of the virtual area is created using three-dimensional graphics tools such as SketchUp (available from Google corporation of Mountain View, california, usa), Maya, or 3ds Max (both available from Autodesk of San Rafael, california, usa).

2. Specifying switching rules associated with virtual zones

a. Overview

In some embodiments, the virtual area specification describes the following XML-based extended switching rules associated with the virtual area in accordance with the COLLADA schema. The model presented below is described as a suggested extension to COLLADA-the digital asset schema version 1.4.12006 month 4 specification (available from http:// www.khronos.org/COLLADA). This extension is referred to herein as the "COLLADA stream reference".

COLLADA stream referencing

Switching rules defined in accordance with the COLLADA flow reference refer to sources and sinks that are typically defined at the system level. In some embodiments, the extensibility features of the XML system that forms the basis for COLLADA are used to describe the types of streams for a particular application. In other embodiments, the supported stream types are updated in the system. The COLLADA stream reference allows the area developer to define new stream types for a given area. In these cases, if the correspondent's system encounters an unknown flow type when entering the area, the system activates developer-specified methods to update the system with the information necessary to process the flow type and configure the appropriate flow processing within the correspondent's system.

Typically, there is a connection between the type of stream source (e.g., "speech," etc.) and the actual local stream source (e.g., a particular microphone) and any signal processing or other stream processing plug-ins associated with that source (e.g., a compressor/limiter that generates avatar movements based on speech or a motion data stream source). The type "speech" is typically defined by the system so that any area designer can use it, without requiring each designer to define the type on their own. In another aspect, the specific insert that is preferred or required to be specified is a common component of the application design. The COLLADA stream reference enables a communicator to assign a stream source type like voice to a microphone, a recording or a music source; and define plug-ins within handlers (handles).

Similar situations work for sinks. A stream-type sink like "voice" is typically established at the system level (e.g., headphones or microphones). There may be additional plug-ins (e.g., distance-based attenuator levels and relative position-based stereo sounds) specified by the correspondent or region designer.

The elements of the COLLADA flow reference describing the partitions and the rules for connecting the flow sources and sinks (according to the partition) are defined below.

< zone _ mesh > (zone _ mesh)

The < zone _ mesh > tag defines the boundary of the partition.

(1) Introduction to

Contains or references information sufficient to describe the basic geometric mesh.

(2) Concept

< zone _ mesh > is defined the same as < mesh > except that instead of a full specification (< source >, < vertices >, < polygons >, etc.) it may simply point to another < geometry > to get its shape.

This is very useful because it allows the reuse of < mesh > (e.g., one for rendering) for stream processing to minimize document size and maintain a link to the original < mesh >. In this sense, < zone _ mesh > is similar to the COLLADA < covex _ mesh > element for the physics engine.

The required volume property indicates whether the partition is inside or outside the mesh volume.

The minimum way to describe < covex _ mesh > is to specify its vertices (by < vertices > elements and its corresponding sources) and let the inputter compute the convex hull of the point cloud.

(3) Properties

The < zone _ mesh > element has the following attributes:

volume of	Text	Indicating whether the partition boundary is outside or inside the volume of the mesh. What is required is.
			convex_hull_of	xs:anyURI	<geometry>For computing its convex hull. And (4) optional.

(4) Related elements

The < convex _ mesh > element relates to the following elements:

specific value the number of elements defined in a pattern

Geometric structure of parent element

Sub-elements see the following subsections

Others have

(5) Sub-elements

The sub-elements, if present, must appear in the following order: < source >, < vertics >, a base element, < extra > (where the base element is any combination of < lines >, < polygons >, < polylist >, < triangles >, < defas > or < strips >).

Name/example	Description of the invention	By default	Specific value
				<source>	Providing entirety of vertex data for a grid	1 or more
<vertices>	Describing mesh vertex attributes and establishing their topologyPortions are		1
				<lines>	Including line elements	0 or more
<linestrips>	Including line strip primitives		0 or more
				<polygons>	Including polygonal primitives that may include holes	0 or more
<polylist>	Containing polygon primitives that do not contain holes		0 or more
				<triangles>	Including triangle primitives	0 or more
<trifans>	Comprising triangular sector elements		0 or more

<tristrips>	Including a triangle strip primitive		0 or more
				<extra>			0 or more

(6) Examples of the invention

Here is an example of a basic < zone _ mesh > element.

<zone_mesh volume＝″interior″>

</zone_mesh>

</geometry>

Here is another example of a < zone _ mesh > element.

<mesh>

...

</mesh>

</geometry>

<zone_mesh volume＝″exterior″convex_hull_of＝″#myArbitraryMesh″/>

</geometry>

ii.<stream>

The < stream > tag defines a switching rule within < zone >.

The < stream > element has the following attributes:

type (B)	Stream types of sources within a partition
		From	Application specific role identifiers, by default, are all. (optional)
Priority level	Numerical priority values or references to logical trees that generate numerical priority values (optional)
		Topology	Allowing a flow to be server-mixed or default direct connection or referencing a logical tree that determines whether a flow should be server-mixed or default direct connection (optional)
Preferred bandwidth	Default bandwidth to allocate to stream types within partitions (optional)
		Minimum bandwidth	Minimum bandwidth required by stream type within partition (optional)

iii. < sink > (

The < sink > tag is a sub-element of < stream > that defines the destination of a stream by a partition and a user role.

The < sink > element has the following attributes:

id	name (R)
		zone	Name of destination partition
type	Type of flow of sink within destination partition (optional)
		to	Application specific role identifiers, by default, are all. (optional)
radius	At the distance (optional) at which the source and sink should be connected

COLLADA stream reference-example 1

Here two partitions: illustrative examples of zonename1 and zonename 2.

<zone_mesh volume＝″interior″convex_hull_of＝″#myArbitraryMesh″/>

</geometry>

...

<library_zones>

<sink id＝″voice_monitor″zone＝″zonename2″to＝″moderator″

radius＝10/>

</stream>

</stream>

</stream>

</zone>

...

</zone>

</library_zones>

In this example, the < geometry > element is a COLLADA element that describes the shape of a volume in a scene (e.g., a virtual room). The < zone _ mesh > element is the COLLADA stream reference element as defined above, which establishes the relationship between partition boundaries and the existing mesh. The < library _ zones > element declares a set of < zone > elements that contains partitions "zone name 1" and "zone name 2".

The boundaries of zonename1 correspond to the internal volume of the convex hull calculated by < geometry > referenced by the URI "# myarbitraryMesh". The boundaries of Zonename2 correspond to the geometric mesh defined by "anothermmesh".

A first exchange rule associated with zonename1 specifies that one copy of each voice data stream originating from zonename1 is sent to each object in zonename1 that is capable of converging the voice data stream and has a "participant" role attribute. The first exchange rule also specifies that a copy of each voice data stream originating from zonename1 be sent to each object in zonename2 that is capable of converging voice data streams and has an "arbitrator" role attribute. A second exchange rule associated with zonyname 1 specifies that one copy of each chat data stream originating from zonyname 1 is sent to each object in zonyname 1 that can converge the chat data streams. A third exchange rule associated with zonename1 specifies that one copy of each audio data stream originating from zonename1 and associated with an "arbitrator" role attribute is sent to each object in zonename1 that is capable of converging audio data streams and is not associated with an arbitrator role attribute.

COLLADA stream reference-example 2

Here is an example of a COLLADA stream reference description of a virtual area simulating a concert hall, which contains two partitions: StageZone (stage zone) and audiozone (audience zone).

<zone_mesh volume＝″interior″convex_hull_of＝″#FullRoomMesh″/>

</geometry>

<zone_mesh volume＝″interior″convex_hull_of＝″#StageMesh″/>

</geometry>

...

<library_zones>

</stream>

...

</zone>

</stream>

</stream>

</zone>

</library_zones>

In this example, the boundaries of the StageZone correspond to a geometric mesh defined by "StageMesh". The boundaries of the audiozone correspond to the geometric mesh defined by "RoomMesh".

The switching rule associated with the StageZone provides that one copy of each voice data stream originating from the StageZone and associated with the "lead _ singer" attribute is sent to each object in the audiozone that is capable of converging the voice data stream and that has the "audio" role attribute. A copy of the voice data stream will be sent with a priority level of 1 and with a preference for a direct stream processing topology. The switching rules also specify that a copy of each voice data stream originating from the StageZone and associated with the "lead _ singer" attribute is sent to each object in the StageZone that is capable of converging the voice data stream and has an "all _ tasks" role attribute.

The first switching rule associated with an audiozone provides that one copy of each voice data stream originating from the audiozone is sent with priority level 2 to each object in the audiozone that is capable of merging the voice data streams. The second exchange rule associated with audiozone provides that one copy of each chat data stream originating from audiozone is sent to each object in audiozone that can converge chat data streams with server mixed preferences.

C. Creating virtual region specifications

FIG. 5 illustrates an embodiment of a graphical user interface 90 of a three-dimensional graphical design tool for creating a specification of a virtual area. The graphical user interface 90 includes a drawing area 92, a menu 94, and a toolbar 96.

Menu 94 provides for the use of drawing tools, commands, and settings. The exemplary set of menus 94 shown in FIG. 5A includes files, edits, views, drawings, tools, windows, and help. The set of menus 94 also includes a Sococo partition menu 98 that provides for the use of tools for defining partitions and stream connections in the virtual area. These tools may be integral to the three-dimensional graphics design tool or may be provided as part of a plug-in extension to the three-dimensional graphics tool, such as SketchUp (available from Google corporation of Mountain View, Calif.), Maya or 3ds Max (both available from Autodesk of San Rafael, Calif., USA).

The toolbar 96 contains a user-defined set of tools and controls. The exemplary set of toolbars 96 shown in fig. 5 correspond to tools and commands typically found in three-dimensional graphic design tools (e.g., the SketchUp 6 three-dimensional graphic design software application).

Drawing region 92 is where the region designer creates a three-dimensional model of the virtual region. In fig. 5, the drawing area 92 of the graphical user interface 90 shows a perspective view of the three-dimensional virtual area 100. In fig. 6, the drawing area 92 of the graphical user interface 90 shows a plan view of the virtual area 100. The geometric elements of the virtual area 100 (e.g., walls, ceilings, floors, pillars, benches, and light fixtures) are typically defined using standard tools and commands typically found in three-dimensional graphic design tools, such as the SketchUp 6 three-dimensional graphic design software application.

As shown in fig. 5 and 6, in addition to the geometric elements, the virtual area 100 additionally comprises partitions 101, 102, 104, 106, 108, 110, 112, which are delimited by dashed line boundaries. Each of the partitions 101-112 is associated with one or more respective real-time data stream exchange rules. The partition 102 and 112 uses tools and command specifications that are available through the Sococo partition menu 98. In some embodiments, the region designer may specify the boundaries of each of the partitions 101-112 using standard three-dimensional graphic design tools and then select one or more of the Sococo partition design tools to associate the boundaries with the respective < zone _ mesh > tags and specify the attributes of the < zone _ mesh > tags. In some of these embodiments, the Sococo partition design tool guides the user through the process of defining each partition so that it can use the COLLADA stream reference specification representations described above (e.g., < zone >, < stream >, and < sink > tags).

First System architecture embodiment

A. General System overview

The communicants typically access the shared virtual area communication environment from respective network nodes. Each of these network nodes is typically implemented by a general-purpose computer system or a special-purpose communication computer system (or "console"). Each network node performs a communication process that presents a respective view of the virtual area at each network node and establishes real-time data stream connections with other network nodes.

Fig. 7 illustrates an embodiment of a server-mediated shared virtual area communications environment 120 in which network nodes 52-56 (referred to in this architecture as "area client network nodes" or simply "area clients") and area servers 64 are interconnected by a communications network 58. In this embodiment, each of the regional client network nodes 52-56 is implemented by a respective computer system of the type described below with respect to the regional client server network node 52; the zone server 64 is also implemented by the same type of general purpose computer system described below.

As shown in fig. 7, regional client network node 52 is implemented by a computer system that includes a processing unit 122, a system memory 124, and a system bus 126 that couples processing unit 122 to the various components of the computer system. The processing unit 122 may include one or more data processors, each of which may take the form of any of a variety of commercial computer processors. The system memory 124 may include Read Only Memory (ROM) that stores a basic input/output system (BIOS) containing the start-up routines of the computer system and Random Access Memory (RAM). The system bus 126 may be a memory bus, a peripheral bus, or a local bus, and may be compatible with any of a variety of bus protocols, including PCI, VESA, Microchannel, ISA, and EISA. The computer system also includes persistent storage 128 (e.g., hard disk drive, floppy disk drive, CD ROM drive, tape drive, flash memory device, and digital video disk) that is connected to the system bus 126 and contains one or more disks of computer-readable media that provide non-volatile or persistent storage of data, data structures, and computer-executable instructions. A communicant may interact (e.g., enter commands or data) with a computer system using one or more input devices 130 (e.g., one or more keyboards, computer mice, microphones, cameras, joysticks, physical motion sensors such as Wii devices, and touch pads). The information may be presented through any of a two-dimensional Graphical User Interface (GUI) or a three-dimensional GUI presented to the communicant on a display monitor 132 controlled by a display controller 134. The computer system can also include peripheral output devices such as speakers and printers. The computer system is connected to other area client network nodes 54, 56 and area server 64 through a network adapter 136 (also referred to as a "network interface card" or NIC).

A number of program modules may be stored in system memory 124, including, but not limited to, an operating system 140 (e.g., Windows, available from Microsoft corporation of Redmond, Wash., U.S.A.)An operating system), communication applications 142, GUI drivers 144, and data 146. Exemplary types of data 146 include input data, output data, and program data, such as a registry (or configuration database) 148.

Operating system 140 includes executive programs that provide basic operating system services (e.g., memory management, process and thread management, security, input/output, and interprocess communication) for creating a runtime execution environment on a computer system. The registry 148 typically contains the following information: starting and configuring parameters needed by the system; system-wide software settings that control the operation of the operating system 140; a secure database; and per user profile settings. A native Operating System (OS) Application Programming Interface (API)150 exposes the underlying operating system services of the executing program to the communication application 142 and other user applications. As used herein, the term "service" (or "service module") refers to a component of an operating system that provides a set of one or more functions.

In some embodiments, the communication application 142 includes processes to control the presentation of virtual areas and corresponding views of objects in the virtual areas on the display monitor 132 and processes to control the exchange of real-time data streams between the area client network node 52 and other area client network nodes 54, 56 and the area server 64. The communication application 142 interfaces with the GUI driver 144 and the user input 130 to present a view of the virtual area and allow the communicant to control the operation of the communication application 142.

Embodiments of the communication application 142 may be implemented by one or more separate modules (or data processing components) that are not limited to any particular hardware, firmware, or software configuration. In general, these modules may be implemented using any computing or data processing environment, including using digital electronic circuitry (e.g., application specific integrated circuits such as Digital Signal Processors (DSPs), etc.) or using computer hardware, firmware, device drivers, or software. In some embodiments, the functionality of the modules is combined into a single data processing component. In some embodiments, the respective functionality of each of one or more of the modules is performed by a respective set of multiple data processing components. In some implementations, the process instructions (e.g., machine readable code, such as computer software, etc.) for implementing methods performed by embodiments of the communication application 142 and the data it produces are stored in one or more machine readable media. Storage devices suitable for tangibly embodying these instructions and data include all forms of non-volatile computer-readable memory, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices, magnetic disks such as internal hard disks and removable hard disks, magneto-optical disks, DVD-ROM/RAM, and CD-ROM/RAM. Embodiments of the communication application 142 may be implemented using any of a wide variety of electronic devices, including personal computing devices (e.g., desktop computers, mobile computers, and communication devices), network devices (e.g., server computers, routers, switches, and hubs), gaming consoles, cable television and hybrid set-top boxes, and modems.

The execution environment stored in system memory 124 also includes a set of network transport protocols 152 for sending and receiving real-time data streams.

In some embodiments, communication over network 58 is carried out in accordance with the transmission control protocol/internet protocol (TCP/IP). The TCP portion of the protocol provides transport functions by dividing the message into smaller packets, reassembling the packets at the other end of the communication network, and resending any packets lost along the path. The IP portion of the protocol provides routing functionality by assigning addresses of the destination node and the destination network in the destination network to the data packets. Each data packet transmitted using the TCP/IP protocol includes a header portion containing TCP and IP information. The IP protocol does not provide guarantees that packets are passed to upper layers of the communication stack. In another aspect, the TCP protocol provides connection-oriented, end-to-end transport services with guaranteed in-order packet delivery. In this way, the TCP protocol provides a reliable transport layer connection.

In other embodiments, the communication over the network 58 may be carried out in accordance with the user datagram protocol/internet protocol (UDP/IP). UDP may be used instead of TCP when reliable delivery is not required. For example, UDP/IP may be used for real-time audio and video traffic flows, where lost packets are simply ignored for any of the following reasons: no time retransmission or any degradation in overall data quality is acceptable.

Some embodiments may use the Java Media Framework (JMF), which supports device capture, encoding, decoding, rendering, and real-time transport protocol (RTP). A variety of network protocols may be used in sending and receiving RTP data between regional client network nodes 52-56 (including a peer-to-peer networking framework, a centralized server using TCP sockets only or in combination with UDP or multicast protocols)

The execution environment also includes hardware link levels and access protocols, which may correspond to the data link and physical layers of the Open Systems Interconnection (OSI) reference model.

In the illustrated embodiment, communication between the regional client network nodes 52-56 and the regional server 64 is carried out in accordance with the TCP/IP protocol. In these embodiments, the computer system determines the IP address of each of its network interfaces before it uses TCP/IP communications. The process may involve contacting the server to dynamically obtain the IP address of one or more of its network interfaces. The computer system may use a Dynamic Host Configuration Protocol (DHCP) to make a request for an IP address to a DHCP server. In this regard, the computer system broadcasts a DHCP request packet at the system start-up requesting assignment of the IP address of the indicated network interface. Upon receiving the DHCP request packet, the DHCP server assigns an IP address to the computer system for use with the indicated network interface. The computer system then stores the IP address (in the response from the server) as the IP address associated with the network interface when communicating using the IP protocol.

B. Exemplary System architecture

FIG. 8 illustrates an embodiment 160 of the server-centric, shared virtual area communication environment 120 shown in FIG. 7, wherein the area client network nodes 52-56 communicate in an architecture that is mediated by an area server 64.

The regional server 64 maintains global state information and acts as a data server for the regional client network nodes 52-56. Among the global state information maintained by the zone servers is a current specification 180 of the virtual zone, a current register 182 of objects in the virtual zone, and a list 184 of any stream mixes that are currently being produced by the zone server 64.

As explained above, the virtual area specification 180 includes a description of the geometric elements of the virtual area and one or more exchange rules. Each of the switching rules defines a respective connection between a source of a respective real-time data stream type and a sink of that real-time data stream type in dependence on a position in the virtual area. In some embodiments, the geometric elements of the virtual area are described in accordance with the COLLADA-digital asset model version 1.4.1 specification, and the switching rules are described in accordance with the proposed COLLADA stream reference specification described above.

The object register 182 typically includes a respective object identifier (e.g., a tag that uniquely identifies the object) for each object in the virtual area, connection data (e.g., an IP address) that enables a network connection to be established with the network node associated with the object, and interface data that identifies the real-time data sources and sinks associated with the object (e.g., the sources and sinks of the network node associated with the object). The object register 182 also typically includes one or more optional role identifiers for each object, which may be explicitly assigned to the object by the correspondent or the zone server 64, or may be derived from other attributes of the object. In some embodiments, the object register 182 also includes the current location of each of the objects in the virtual area, as determined by analysis of the real-time motion data streams received by the area server 64 from the area client network nodes 52-56. In this regard, the zone server 64 receives real-time motion data streams from the zone client network nodes 52-56, tracking the communicant's avatars and other objects (entering, leaving, and moving around in the virtual zone) based on the motion data. The zone server 64 updates the object register 182 based on the current location of the tracked object.

In the embodiment illustrated in fig. 8, regional client network node 52 includes an embodiment of a communication application 142 (see fig. 7) that includes a communication module 162, a three-dimensional visualization engine 164, a chat engine 165, and an audio processing engine 166. Each of the other network nodes 54, 56 typically includes an embodiment of a communication application 142 that is the same as or similar to that described with respect to the regional client network node 52.

The communication module 162 controls the exchange of real-time data streams between the regional client network node 52 and the other regional client network nodes 54, 56 and the regional server 64. The communication module 162 includes a stream switching manager 168 and a bandwidth monitor 170. The stream switching manager 168 handles the entry and exit of avatars and other objects associated with the regional client network node 52 into and out of the virtual region. The stream switching manager 168 also automatically determines how to switch (e.g., route, connect and disconnect) real-time data streams between the regional client network node 52 and the other regional client network nodes 54, 56 and the regional server 64. The stream switching manager 168 makes these determinations based on the switching rules contained in the virtual area specification, the current locations of the avatars and other objects in the virtual area, and the real-time data stream types associated with the avatars and other objects in the virtual area. In some embodiments, the stream switching manager 168 also includes upload and download bandwidth constraints of any of the regional client network node 52, the other network nodes 54, 56, or the regional server 64 in these determinations. In addition, the stream switching manager 168 re-evaluates the current set of connections in response to events (e.g., upload and download bandwidth failures, and requests to enter or leave a virtual area), periodically, or both. As a result of the re-evaluation of the current connection, the flow switching manager 168 may take any of the following actions, for example: requesting stream mixing from the zone server 64, dropping stream mixing from the zone server, disconnecting one or more direct links with one or more of the other zone client network nodes 54, 56, or forming one or more direct links with one or more of the other zone client network nodes 54, 56.

In managing the exchange of real-time data stream connections, the stream exchange manager 168 maintains a configuration data set including interface data 186, partition lists 188, and the location 192 of objects currently in the virtual area. The interface data 186 includes a respective list of all sources and sinks of the real-time data stream type associated with each object associated with the regional client network node 52 for that object. The partition list 188 is a register of all partitions in the virtual area currently occupied by the avatar associated with the regional client network node 52. When the correspondent first enters the virtual area, the stream switching manager 168 typically initializes the current object location database 192 with the location initialization information downloaded from the area server 64. The stream switching manager 64 then updates the current object location database 192 with the current location of the object in the virtual area (as determined from analysis of real-time motion data streams received from, for example, one or more of the computer mouse 171, the area client network nodes 54, 56, and the area server 64). In some embodiments, the object location 192 incorporates an object register 190. The configuration data maintained by the stream switching manager 168 also includes copies 190, 192, 196 of the object register 182, the stream mix list 184, and the virtual area specification 180, respectively; these copies 190, 194, and 196 are typically downloaded from the regional server 64 and represent a local cache of such data.

The three-dimensional visualization engine 164 presents views of the virtual area and any objects in the virtual area on the display monitor 132. In this process, the three-dimensional visualization engine 164 reads the virtual region specification data 196, the object register 190, and the current object location database 192. In some embodiments, the three-dimensional visualization engine 164 also reads a correspondent avatar database 198 that contains images required in the virtual area to render the correspondent's avatar. Based on this information, the three-dimensional visualization engine 164 generates a perspective representation (i.e., an image) of the virtual area and the objects in the virtual area from the perspective (position and orientation) of the communicant's avatar in the virtual area. The three-dimensional visualization engine 164 then renders a perspective representation of the virtual area on the display monitor 132. In some embodiments, the three-dimensional visualization engine 164 determines the visibility of the communicant's avatar in order to limit the amount of data that must be exchanged, processed, and rendered to the portion of the virtual area that is visible on the monitor 132.

In some embodiments, the three-dimensional visualization engine 164 is additionally operable to generate a planar representation of the virtual area. In these embodiments, the communicant may direct the three-dimensional visualization engine 164 to render one or both of a perspective representation of the virtual area and a plan view representation of the virtual area on the display monitor 132.

The communicant may control the rendered view of the virtual area or the avatar's position within the virtual area by sending commands from an input device (e.g., computer mouse 171) to the communication module 162. The three-dimensional visualization engine 164 updates the view of the virtual region and the location of the object within the virtual region according to the updated location in the current object location database 192 and re-renders the updated version of the graphical representation of the virtual region on the display monitor 132. The three-dimensional visualization engine 164 may update the rendered image periodically or only in response to movement of one or more of the objects in the virtual area.

The chat engine 165 provides an interface for outputting chat (text) messages received from local text input devices (e.g., keypads) of the regional client network nodes 52 and inputting chat streams received from other regional client network nodes 54, 56. The chat engine 165 converts chat (text) messages entered by the correspondent through the text input device into a live chat stream, which can be sent to the other network nodes 54, 56. The chat engine 165 also converts the incoming chat stream into a text signal, which can be rendered on the display monitor 132.

The audio processing engine 166 produces audio signals that are rendered by speakers 172, 174 in the speaker 176 of the communicant, and converts audio signals produced by a microphone 178 in the speaker 176 into real-time audio streams that can be sent to the other regional client network nodes 54, 56.

Automated exchange of real-time data streams

A. Introduction to

As explained above, the shared virtual area is defined by a specification comprising a description of the geometrical elements of the virtual area and one or more switching rules governing real-time streaming connections between the network nodes. The switching rules typically include a specification of conditions that connect the source and sink of the real-time data stream according to location in the virtual area. Each rule typically includes attributes defining the type of real-time data stream to which the rule applies and the location or locations in the virtual area to which the rule applies. In some embodiments, each of the rules optionally may include one or more attributes that specify a required role for the source, a required role for the sink, a required priority level for the flow, and a required or preferred flow topology.

The exchange rules are implied when an object enters the virtual area, the object moves within the virtual area, and the object leaves the virtual area.

B. Virtual area entry

Fig. 9 illustrates an embodiment of a method by which a zone client (referred to in this section as an "entering zone client") enters a virtual zone.

The correspondent begins a communication session by launching the communication application 142 (see fig. 7) on the regional client network node (fig. 9, block 200). The communication application 142 presents the communicant with a graphical user interface through which the communicant can interact with the application 142. The graphical user interface typically provides the correspondent with the option to log into the shared virtual area.

In response to receiving the command to login to the shared virtual area, the communication application 142 sends a login message to the area server 64 (FIG. 9, block 202). The login message typically includes login information for identifying and authenticating the correspondent.

The zone server 64 verifies the login information contained in the login message (fig. 9, block 204) and notifies the zone client of the result (fig. 9, block 206).

If the verification is successful (FIG. 9, block 207), the communication application 142 sends interface data to the zone server 64 (FIG. 9, block 209). The interface data includes an identification of the source type and sink type of all real-time data streams that will enter the region and are respectively associated with the objects. If the authentication fails (FIG. 9, block 207), the communication application 142 stops the login session and notifies the correspondent of the failed login attempt (FIG. 9, block 208).

The zone server 64 updates the object register 190 (see fig. 9) to include the objects associated with the incoming zone client and the real-time data stream source and sink types associated with those objects (fig. 9, block 210). The zone server 64 sends configuration data to the incoming zone client (fig. 9, block 212). The configuration data includes a copy of the virtual area specification 180 (see fig. 8) and a copy of the updated object registers 182 (see fig. 8). In some embodiments, the configuration data additionally includes a copy of a stream mix list (see fig. 8) that identifies the mix (or combination) of the regional client real-time data streams currently being produced by the regional server 64. The zone server 64 also sends corresponding copies of the updated object register 180 to other zone clients associated with the objects in the virtual zone (FIG. 9, block 214). As explained above, the zone server 64 receives real-time motion data streams from the zone client nodes 52-56, tracks avatars and other objects of communicants entering and leaving the virtual zone based on the motion data, and updates the object register 182 according to the current location of the tracked objects. The zone server 64 periodically sends updated object registers 182 to the zone clients associated with the objects in the virtual zone.

The communication application 142 executing on the incoming regional client network node processes the virtual region specification and object registers as described in detail below (fig. 9, block 216). The communication application 142 then establishes one or more real-time data stream connections between the incoming regional client network node and one or more of the other regional clients listed in the object register based on the switching rules defined in the virtual region specification, the respective sources and sinks associated with the objects listed in the received copy of the object register 182, and the respective locations of the objects in the virtual region (fig. 9, block 218). In establishing these connections, the communication application 142 initiates and configures component modules that enable the capture, playback, streaming, and transcoding of real-time data streams available on the incoming regional client network nodes. These components typically include a chat engine 165, an audio processing engine 166, and other components (e.g., a video processing engine for encoding video data received from a local video capture device and decoding real-time video stream packets received from a remote network node).

C. Processing configuration data to determine a set of required real-time data stream connections

Fig. 10 is a flow diagram of an embodiment of a method according to which an embodiment of the stream switching manager 168 (fig. 8) processes configuration data received from the zone server 64 (in block 216 of the method of fig. 9) to determine a set of required real-time data stream connections. As explained above, the configuration data includes a copy of the virtual region specification 180 (see fig. 8) and a copy of the updated object registers 182 (see fig. 8). In some embodiments, the configuration data additionally includes a stream mix list (see fig. 8) that identifies a mix (or combination) of the regional client real-time data streams that are currently being produced by the regional server 64.

The stream switching manager 168 initializes the local object register 190 (see fig. 8) with the copy of the object register 182 received from the zone server 64 (fig. 10, block 220). The stream switching manager 168 also initializes the local stream mix list 194 (see fig. 8) with a copy of the stream mix list 184 received from the zone server 64 (fig. 10, block 222). Stream switching manager 168 additionally initializes local virtual region specification cache 196 (see fig. 8) with a copy of virtual region specification 180 received from region server 64 (fig. 10, block 220).

The stream switching manager 168 establishes a list of occupied partitions 188 (see fig. 8) from the virtual area specification 196 and the position of the communicant's avatar in the virtual area (fig. 10, block 226). In this process, the stream switching manager 168 retrieves the current location of the correspondent's avatar in the virtual area from the current object location database 192 containing the coordinates of the avatar's current location in the virtual area. These coordinates are determined from a real-time motion data stream received by an input device, such as a computer mouse 171 or the like. The stream switching manager 168 then compares the current position of the communicator's avatar with the partition definitions in the virtual area specification 196. The stream switching manager 168 compiles an occupied partition list 188 from all partitions in the virtual area specification that are consistent with the current location of the communicator's avatar. For example, in some embodiments, occupied partition list 188 is made up of all partitions whose mesh contains the current location of the communicator's avatar.

The stream switching manager 168 determines a set of target real-time data stream types defined for the partitions in the occupied partition list (fig. 10, block 228). The stream switching manager 168 then determines the set of real-time data stream data required from the set of target real-time data stream types, the location of the object in the virtual area, and the switching rules defined in the virtual area specification (fig. 10, block 230).

In some demonstrative embodiments, flow switching manager 168 ascertains an object excluding the given object in one or more of the partitions from which the real-time data flow type included in the target set originates and into which the real-time data flow type in the target set converges, as defined by the one or more switching rules. The stream switching manager 168 determines a connectable set of real-time data streams based on the ascertained objects. Each of the connectable streams is at least one of: (i) one or more of (i) originate from network nodes associated with the ascertained object and (ii) originate into network nodes associated with the ascertained object. The stream switching manager 168 then determines the set of real-time data stream data required based on a match of sources and sinks associated with the connectable set of real-time data streams.

In some of these embodiments, the set of required real-time data flow data corresponds to a real-time data flow that may sink into the partition occupied by the correspondent avatar (according to the exchange rules and sinks available on the regional client network node). In these embodiments, the flow switching manager 168 determines the sinks of these sinks that are defined by the occupied partition that has the ability to converge for the associated network node, and then determines all of the sources of those sinks based on the location of other objects in the virtual area and the switching rules. In this process, the stream exchange manager 168 compiles a set of target real-time data stream types from all real-time sink types (e.g., audio, chat, video, sports data) that are associated with the correspondent's avatar and defined as sink types for any partition occupied by the correspondent's avatar. The stream switching manager 168 then determines from the switching rules all target source partitions from which each of the target real-time data stream types may originate. The stream switching manager 168 identifies all objects in the target source partitions that are capable of retrieving one or more of the target real-time data stream types from their current locations according to the switching rules from the object registers 190 and the current object location database 192. The stream switching manager 168 compiles the set of required real-time data stream data from the connection data associated with the identified object in the object register 190.

In one illustrative example, FIG. 11 shows a plan view of a virtual gallery area 100 (see, e.g., FIGS. 5 and 6) when there are four avatar objects A, B, C, D therein. Avatars A and B are located in partition 101, while avatars C and D are located in partition 108. For the purpose of this illustrative example:

● each of avatars A-D is associated with a voice, video, and chat source type and sink type;

● the switching rules for partition 101 specify:

● each speech source associated with an avatar within partition 101 will be connected to each speech sink within partition 101,

● Each video source associated with an avatar within partition 101 will be connected to each video sink within partition 101, an

● each chat source associated with an avatar within partition 101 will be connected to each chat sink within partition 101;

● the exchange rules of partition 108 only state that each voice source associated with an avatar within partition 108 will be connected to each voice sink within partition 108; and is

● flow switching manager 168 implements a proximity policy rule on top of the partition switching rule that only allows a prescribed distance (or radius) r from each other in the virtual area_pConnection of the source and compatible sink associated with the respective object within.

In this example, the partition exchange rules and proximity policy rules provide respective exchange conditions that determine how to establish a connection between avatars A, B, C and D.

In operation, whenever avatar B is located in proximity partition 232, the instance of stream exchange manager 168 running on the area client node associated with avatar A will request to connect to real-time voice, video, and chat streams originating from the area client node associated with avatar B, the proximity partition 232 being defined by a prescribed distance r around avatar A_pAnd (4) limiting. Similarly, every time avatar A is located at a prescribed distance r of avatar B_pIn time, the instance of the stream switch manager 168 running on the zone client node associated with avatar B will request a connection to the real-time voice, video, and chat streams originating from the zone client node associated with avatar a. Since avatar B is currently outside of avatar a's proximity zone 232, and vice versa, the nodes associated with avatars a and B will not be connected to each other in the current exemplary state shown in fig. 11.

Since the partition 108 only allows voice connections, the instance of the stream switch manager 168 running on the zone client node associated with avatar C will request connections only to real-time voice streams originating from the zone client node associated with avatar D (assuming the proximity conditions specified in the proximity policy rules are satisfied). Similarly, the instance of the stream switch manager 168 running on the zone client node associated with avatar D will request to connect only to the real-time voice stream originating from the zone client node associated with avatar C (assuming the proximity conditions specified in the proximity policy rules are satisfied).

Since the exchange rules of partitions 101 and 108 do not allow for a connection between partitions 101 and 108, the sources and sinks associated with avatars A and B will not be connected to any of the sources and sinks associated with avatars C and D (even if the proximity conditions specified in the proximity policy rules are satisfied).

In some embodiments, at least one of the zone clients 52-56 includes a network adapter (e.g., an ethernet interface card) that provides connectivity to the network 58 and is further configured to perform one or more of the functions of the zone client stream switching manager 168, including the functions required to perform the method of fig. 10.

D. Establishing a real-time data stream connection

1. Determining required real-time data stream connections

In some demonstrative embodiments, after stream switching manager 168 determines the set of real-time data stream data, which enables network node 52 to participate in a collaborative communication session with other network nodes within the shared virtual area (fig. 10, block 230), stream switching manager 168 determines a real-time data stream connection that will result in the required data stream data being communicated to regional client network node 52.

In some of these embodiments, the stream switching manager 168 determines a real-time data stream processing topology that delivers the set of real-time data streams to the given network node based at least in part on the bandwidth capabilities of the given network node. In this process, the stream switching manager 168 determines the respective form in which each of the real-time data streams was received from the combined unmixed real-time data stream and the stream mix derived from the real-time data streams. The flow switching manager 168 also determines network routes over which each of the real-time flows is received from the direct peer-to-peer network routes and from one or more intervening network routes in the other network nodes. After the stream processing topology is determined, the stream switching manager 168 establishes real-time data stream connections between the given network node and other network nodes according to the determined stream processing topology.

Fig. 12 illustrates an embodiment of a method of determining the topology of a real-time data stream connection that delivers the required data stream data to a regional client network node.

According to the method, the stream switching manager 168 determines whether the regional client network node 52 has sufficient bandwidth to receive the set of required real-time data stream data 240 directly from other regional client network nodes (fig. 12, block 242). In this process, other regional client network nodes send link requests to the regional client network node 52. The link requests indicate respective bandwidth requirements for transmitting respective sets of real-time data streams required by regional client network node 52 (see § v.d.2, below). The stream switching manager 168 compares the total bandwidth required to establish the required direct connection with the download bandwidth currently available to the regional client network node 52 as reported by the bandwidth monitor 170 (see fig. 8).

If the available bandwidth is at least equal to the overall required bandwidth, the stream switching manager 168 establishes a direct connection with other regional client network nodes that provide the required real-time data stream data (fig. 12, block 244). In this process, the communication application 142 and its associated operating environment create a socket (e.g., a tcPsocket or a performance-optimized specialized real-time socket) between the regional client network node 52 and one or more of the other regional client network nodes 54, 56 and the regional server 64. The created socket typically includes, for each real-time data stream type, a socket for transmitting the real-time data stream and a socket for transmitting control information (e.g., quality of service information) associated with transmission and reception of the associated real-time data stream packet. The communication application 142 processes and encodes the real-time data streams, including recording them and rendering them into a client user interface. For example, locally generated audio data, video data, and chat data are typically captured, encoded, and divided into packets (e.g., RTP packets), which are sent to the network 58.

If the available bandwidth is less than the requested bandwidth (FIG. 12, block 242), the stream switching manager 168 checks the stream mix list 194 (see FIG. 8) to determine if a stream mix that provides the requested real-time data stream data is currently being generated by the regional server 64 (FIG. 12, block 246). If the required stream mix is available, the stream switching manager 168 establishes a connection with the regional server 64 over which a copy of the required real-time data stream mix is sent from the regional server 64 to the regional client network node 52 (FIG. 12, block 248). If the required stream mixing is not available, the stream switching manager 168 sends a stream mixing request to the zone server 64 (FIG. 12, block 250)

In some embodiments, the zone server 64 performs one or more of the functions of the zone client stream switching manager 168. In these embodiments, the regional server 64 establishes one or more real-time data stream connections between the network nodes 52-54, wherein the network nodes 52-56 are associated with respective objects, each of which is associated with at least one of a source and a sink for one or more of the real-time data stream types. The zone server 64 establishes one or more real-time data stream connections based on one or more switching rules, respective sources and sinks associated with the objects, and respective locations of the objects in the virtual zone according to one or both of the methods of fig. 10 and 12.

1. Real-time data stream connection

a. Introduction to

In some embodiments, the connections between network nodes are established in two layers: links and channels.

A link is established between two network nodes whenever there is at least one flow sent directly from one node to another. The link is typically unidirectional and is requested by the sender and received or rejected by the receiver. If rejected, uplink and downlink (respectively) communication with the zone server (hybrid or transceived, as described herein) may still be possible. A link represents the full bandwidth allocated by two nodes communicating in real time. The allocation is dynamically determined based on the total network bandwidth available, the amount of bandwidth desired at any given time, and the number of links. Adding and dropping links is an ongoing dynamic process. Movement within a complex area or from area to area is an example when link connection and disconnection play an important role in ongoing system behavior.

Each link is divided into channels carrying respective real-time data streams. A channel is assigned to a particular flow within the total bandwidth that has been allocated to the link. The channel bandwidth may be dynamically varied based on changes in the total link bandwidth and the number and priority of channels within the link. The activation or deactivation of the tunnel provides information that may be used by the link layer of the network node to change the desired bandwidth between the two nodes. This information may also be shared among the nodes to establish the level of bandwidth allocated to the link.

In the context of the requirement of bandwidth among all links of each node, the connection framework provided by the embodiments enables the sending and receiving network nodes to make decisions on how to use the available bandwidth for the set of flows that are needed at any given time between the two nodes. Decreasing or increasing the bit rate of the voice channel when increasing or decreasing the amount of bandwidth used for synchronizing file transfers or video feeds is an example of this allocation decision process. The connection framework also enables the receiving network node to make decisions regarding server mixing and individual stream sending based on the available channel bandwidth within the link.

The system settings, as optionally modified by the virtual area specification, provide parameters for determining relative bandwidth allocation and prioritization of flow types and topologies for links and lanes. Due to these variable and dynamic requirements, the uplink and downlink between the network node and the regional server (or other high bandwidth intermediate node) typically have a high priority of local bandwidth, as these links may be needed to transmit links and tunnels between the various different nodes. Due to bandwidth limitations at the nodes of a link, a lane, or both, it is possible for a virtual area designer to create virtual areas that cannot be run by a given node.

Bandwidth is often a scarce resource (compared to CPU time, hard disk space, graphics rendering capabilities, etc.). The layering of node connections into links and channels within links enables virtual area designers and system administrators to control how any given node involved in one or more real-time sessions will respond when bandwidth is saturated. Layering allows individual links to be efficiently managed for minimum and maximum bandwidth purposes. The hierarchy also provides control over which nodes are selected to receive the link (as compared to requiring the link through the regional server).

In one illustrative example, assume that a first network node and a second network node communicate over a shared virtual area. Each of the first and second nodes requires a voice stream and a motion data stream from the other. To meet this need, each of the first and second nodes establishes a respective uplink with the zone server, which is divided into a voice channel and a motion data channel. The regional server transceives voice streams it receives from the first and second network nodes and mixes the motion data streams it receives from the first and second network nodes. The zone server establishes respective downlinks with the first and second network nodes and transmits the voice and motion data streams in voice and motion data channels allocated in the respective downlinks. When the first and second nodes are connected, they may participate in the file transfer, which will then require a new channel in the link. If not enough bandwidth is available for a reasonable data transfer rate, the sender may reduce its bit rate for lower quality voice conversations, transceive file transfer streams over the zone server link, or otherwise adjust the channels and links according to logic in the respective system settings of the first and second network nodes or behaviors specified by the virtual zone specification.

If the third network node requests entry into the virtual area, each of the first and second network nodes will require a voice and motion data stream from the third network node and the third network node will require a voice and motion data stream from each of the first and second network nodes (if bandwidth allows). If the minimum amount of bandwidth is not available to receive the requested stream directly from the third network node, the first and second network nodes will increase the uplink bandwidth to the area server, the downlink bandwidth from the area server, or both. Alternatively, the first and second network nodes would require one or more servers to be mixed. If there is still insufficient bandwidth to establish all connections required by the virtual area specification, the third network node may be prevented from entering the virtual area, or one or both of the first and second network nodes may be dropped from the real-time session, in which case the dropped network node may need to retry or connect through a faster network connection.

Subsequently, when the third network node leaves the virtual area, each of the first, second and third network nodes needs to disconnect and release the link and bandwidth allocated to the connection with the first network node, which may cause the first and second network nodes to reallocate the available bandwidth to the link between them.

In some embodiments, the first and second network nodes have the ability to determine the priority of the links they have established with each other before allocating any bandwidth to the third network node. In some embodiments, switching rules in the virtual area specification determine the priority of the connection. For example, in some virtual area designs, network nodes associated with certain role attributes (e.g., arbiters) will have a higher connection priority than other network nodes and thus will always be allowed to link to the virtual area. In other virtual area designs, connections are ranked by their respective age, with older connections ranked higher than younger connections. In these virtual areas, the node associated with the oldest connection will be the last to drop from the communication session.

b. Creating links

Fig. 13 shows an exemplary embodiment of a method of exchanging real-time data stream connections between network nodes sharing a virtual area, wherein the links are established by links of the type described in the previous section. The method of fig. 13 is typically performed by the stream switching manager 168 of each of the network nodes that are the source of one or more of the real-time data streams required by the other network nodes sharing the virtual area.

For each of the one or more receiving network nodes, the stream switching manager 168 determines a respective link of a respective transmit set on which to transmit the one or more real-time data streams, wherein each of the links has a respective link bandwidth (fig. 13, block 440). Each of the links is typically a respective unidirectional link from a respective transmitting network node to a respective receiving network node. However, in some embodiments, one or more of the links may be bidirectional (e.g., half-duplex or full-duplex) links.

For each of the links, the stream switching manager 168 allocates a respective link bandwidth between the one or more lanes respectively allocated to the one or more real-time data streams in the respective transmit set and transmits the one or more real-time data streams in the respective transmit set to the respective receiving network node on the respectively allocated lanes (fig. 13, block 442). In some embodiments, the flow switching manager 168 allocates the respective bandwidths in amounts determined based on at least one attribute associated with the respective receiving network nodes. This attribute may correspond to any of the following exemplary attributes: a location in a virtual area occupied by an avatar associated with the receiving network node; a link priority level associated with the receiving network node; and a character identifier assigned to the avatar associated with the receiving network node. In some embodiments, the assignment of the respective link bandwidths is based on one or more stream priority levels respectively associated with one or more real-time data streams in the respective transmission sets.

In some embodiments, for each of the links, the stream switching manager 168 ascertains one or more respective bandwidth levels for each of the one or more real-time data streams in the respective transmission set and allocates respective link bandwidths to the links based on the ascertained bandwidth levels. In some embodiments, the stream switching manager 168 ascertains these bandwidth levels by examining the system level settings of the sending network node and examining the virtual area specification for any bandwidth level for any stream type within any partition assigned to the shared virtual area. Each real-time data stream type is typically associated with at least one system-level bandwidth level. For example, each of the regional client network nodes typically includes a voice codec that provides different levels of compression to the voice stream and a video codec that provides different levels of compression to the video stream. Each of these codecs may typically be set to provide a respective range of compression levels from a default low (e.g., preferred or target) compression level to a high compression level. The virtual region specification may specify a bandwidth level for one or more particular regions for each of one or more real-time data stream types. These levels may include a preferred bandwidth level, a minimum bandwidth level, and one or more bandwidth levels between the preferred and minimum bandwidth levels.

In some embodiments, for each of the links, the stream switching manager 168 identifies a respective minimum bandwidth level for each of the real-time data streams in the respective transmission set, and calculates a respective minimum link bandwidth level from the one or more identified respective minimum bandwidth levels. The stream switching manager 168 typically drops any link in response to determining that the bandwidth available for that link fails to meet the corresponding minimum link bandwidth level for a defined period of time.

In some embodiments, for each of the links, the stream switching manager 168 identifies, for each of one or more of the real-time data streams in the respective transmit set, at least two respective bandwidth levels in a respective priority order ordered from a respective first preferred bandwidth level (e.g., a default bandwidth level) to a respective second preferred bandwidth level (e.g., a minimum bandwidth level). The flow switching manager 168 calculates a respective target link bandwidth level based at least in part on the identified first preferred bandwidth level and a respective fallback link bandwidth level based at least in part on the identified second preferred bandwidth level. For each of the receiving network nodes, the stream switching manager 168 attempts to establish a respective link to the receiving network node at the target link bandwidth level. In this process, the flow switching manager 168 compares the target link bandwidth level to the current amount of bandwidth available to transmit the corresponding transmit set; the receiving network node also compares the target link bandwidth level with a current amount of bandwidth available to receive the corresponding transmit set. In response to a failed establishment of a corresponding link to the receiving network node at the target link bandwidth level, the flow switching manager 168 attempts to establish the corresponding link to the receiving network node at a fallback link bandwidth level.

Fig. 14 shows an exemplary implementation of the embodiment described in the preceding paragraph. According to this embodiment, the flow switching manager 168 determines a current respective candidate link bandwidth level (fig. 14, block 444) and one or more optional respective fallback candidate link bandwidth levels (fig. 14, block 446) for each link. The flow switching manager 168 attempts to establish the current link at the current corresponding candidate link bandwidth level (fig. 14, block 448). If a link is established (fig. 14, block 450), the flow switching manager 168 processes the next link (fig. 14, block 444). Otherwise, the flow switching manager 168 determines whether there are any other candidate link bandwidth levels available for the current link (fig. 14, block 452). If so, the flow switching manager 168 changes the current respective candidate link bandwidth level to the next lower link bandwidth level (FIG. 14, block 454) and attempts to establish the current link at the new candidate link bandwidth level (FIG. 14, block 448). If there are no more candidate link bandwidth levels (FIG. 14, block 452), the flow switching manager 168 reports an error for the current link and repeats the process for the next link (FIG. 14, block 444).

In response to a failure to establish any of the links, the receiving network node to which those links lead may attempt to abandon the sending of at least one optional real-time data stream in the data set in order to accommodate existing bandwidth limitations. Alternatively, such a receiving network node may attempt to establish a link that provides the required real-time data flow data on respective network routes that are interjacent by one or more of the other network nodes. For example, a receiving network node may request a link from a regional server 64, which regional server 64 provides the required real-time data streaming data in an unmixed format or a mixed format.

In some embodiments, the link may be secure. The secure link may have one or more of the following security properties: authentication, integrity and privacy. The authenticated links use authentication techniques (e.g., evaluating certificates that are part of a public key infrastructure, such as the one provided by Verisign) to help ensure that each node is actually connected to other nodes that are known, rather than to impersonated nodes. Integrity techniques (e.g., using a security hashing procedure associated with the SHA algorithm) are employed to ensure that any changes made to the link contents between transmission and reception are detectable. Privacy techniques (e.g., based on shared keys encrypting the link content with the AES encryption algorithm prior to transmission and decrypting the link content prior to use) help ensure that the content of the link cannot be readily known to eavesdroppers. These techniques may be selectively combined to achieve desired security properties for a particular communication session. When a secure link is employed, system settings and application design parameters may be adjusted to account for the overhead associated with establishing the secure link. For example, the link may be kept at a low (or even zero) bandwidth for a longer time to avoid the need to re-establish the link if bandwidth becomes available.

b. Exemplary embodiments with enhanced Link management functionality

The enhanced link management functionality of the stream switching manager 168 described in § v.d.2 may be implemented in any computing or data processing environment, including in digital electronic circuitry (e.g., an application specific integrated circuit such as a Digital Signal Processor (DSP) or the like), or in computer hardware, firmware, device driver, or software. In some embodiments, these functionalities are implemented using dedicated hardware modules, such as network adapters and network switches. Embodiments of such modules may be configured to provide accelerated performance of any of the following enhanced link management functions: creating a link; a link route; bandwidth allocation among a plurality of links transmitted from a given network node; and bandwidth management between lanes within a given link.

Fig. 15 illustrates an exemplary application environment 460 in which a network adapter 462 having enhanced link management functionality may operate. The network adapter 462 is incorporated within a host system 464 that includes a communication controller 466 and a Media Access Control (MAC) interface 468. The network adapter 462 transitions between the host system 464 and the network media 470. Network medium 470 is the physical medium upon which or through which links from host system 464 to one or more other network nodes 472 are established. Wires, fibers, electromagnetic waves in free space are three exemplary types of network media.

Each of the host system 464 and the other network nodes 472 can be any type of device or system connected to a network (e.g., personal computers, computer workstations, network switches, hubs, and network repeaters). The host communication controller 466 enables the host system 464 to share access to the network media 470. The MAC interface 468 connects the communication controller 466 to the network adapter 462. One exemplary type of MAC interface is a Media Independent Interface (MII) that provides a parallel interface that supports communication with a parallel communication controller 466. Another exemplary type of MAC interface is the IEEE 802.03 compliant universal serial interface (GPSI), which supports serial communication with the serial communication controller 466.

Fig. 16 illustrates an embodiment of a network adapter 462 that includes a host interface port 474, a network media interface port 476, a processing unit 478, a transceiver 480, and a memory 482. Host interface port 474 may be connected to MAC interface 468. The network media interface port 476 may be connected to network media 470. In the illustrated embodiment, network interface port 476 provides a physical interface between transceiver 480 and network medium 470.

Processing unit 478 is typically a MAC processing unit that performs MAC layer functions including, but not limited to, ensuring that host system 464 and one or more other network nodes 472 communicate with the correct frame format and protocol. Additionally, processing unit 478 is operable to perform link and path management functions described in § v.d.2. To facilitate the performance of these functions, the processing unit 478 stores copies 484 of the virtual area specification, link table 486, and channel table 488 in memory 482. As illustrated herein, the virtual area specification 484 may contain any of the following parameter values that affect the management of links and lanes: preferred, minimum and intermediate bandwidth levels according to stream type; a flow type priority; a stream processing topology priority; and a character identifier assigned to an object (e.g., an avatar) associated with a network node sharing the virtual area. Link table 486 contains a list of established current links with other network nodes 472, as well as allocations of bandwidth between the current links. The lane table 488 contains a list of the respective lanes assigned to the real-time data streams transmitted on each of the current links, as well as the allocation of bandwidth between the respective lanes within the link.

2. Managing real-time data stream connections

Fig. 17 illustrates an embodiment of a method of determining a real-time data stream connection that delivers required data stream data to a regional client network node. In this process, the regional server 64 determines an optimal streaming topology that provides the required real-time data stream data to the regional client network node 52.

The zone server 64 manages the connections between the zone client network nodes according to the current flow handling topology (fig. 17, block 251). At this point, the zone server 64 maintains global state data that includes the definition of the virtual zone and the current object state data for all avatars and other objects in the virtual zone. In this process, the zone server 64 tracks objects in the virtual zone and in some embodiments, the zone server 64 maintains a recent historical data cache, which is used for real-time synchronization of the zone client network nodes. The zone server 64 also re-evaluates the connection in response to the object entering the virtual zone, the object leaving the virtual zone, and the bandwidth failure.

In response to receiving (fig. 17, block 262) a request for real-time data flow data from a requesting regional client network node, the regional server 64 discovers (fig. 17, block 254) the bandwidth capabilities of the regional client network node associated with the object in the object register 190 (see fig. 8). In some embodiments, each of the regional client network nodes either dynamically or periodically sends its current upload bandwidth capabilities and its current download bandwidth capabilities to the regional server 64.

The regional server 64 selects a real-time data stream processing topology that delivers real-time data stream data to the requesting regional client network node (fig. 17, block 256). The regional server 64 typically selects a topology based on the discovered bandwidth capabilities of the regional client network nodes. In some embodiments, the area server 64 selects a stream processing topology in which the requesting network node and the other network nodes receive the maximum number of unmixed real-time data streams. Such unmixed real-time data streams enable regional client network nodes to render streams with higher quality and with the option of applying local processing to these streams (e.g., one or both of audio binaural sound processing or fader envelope processing (fader envelopment) to more realistic site avatars in a stereo scene) for a more immersive experience or specific application goal (e.g., 5.1 audio processing or specialized avatar movements).

In some embodiments, the virtual area specification specifies stream attribute values for one or more real-time data stream types in one or more partitions in the virtual area. In these embodiments, the zone server 64 selects a stream processing topology based on one or more stream attribute values specified by the virtual zone specification. In some exemplary virtual area designs, the virtual area specification assigns a first stream priority attribute value to a first real-time data stream type and a second stream priority attribute value different from the first stream priority attribute value to a second real-time data stream type. For example, in the second COLLADA stream reference example described above, a voice stream originating from a StageZone and associated with a "lead _ singer" role attribute is assigned a priority level of 1, while a voice stream originating from an audiozone is associated with a priority level of 2. With respect to these types of virtual area design specifications, area server 64 attempts to select a stream processing topology that prioritizes the first and second real-time data stream types differently based on different first and second stream priority attribute values. For example, with respect to the second COLLADA flow reference example, facing the bandwidth availability constraint, the Zone server 64 will mix the voice flow creation and sending flows originating from the audiozone before mixing the lead _ singer voice flow originating from the StageZone.

In some exemplary region designs, the virtual region specification assigns a first stream topology attribute value to a first real-time data stream type and a second stream topology attribute value, different from the first stream topology attribute value, to a second real-time data stream type. For example, in the second COLLADA flow reference example described above, a voice flow originating from a StageZone and associated with a lead _ singer role attribute is assigned a "direct" topology attribute value, while a chat flow originating from an audiozone is associated with a topology attribute value of "server _ mix". With respect to these types of virtual area design specifications, the area server 64 attempts to select different stream processing topologies for the first and second real-time data stream types based on different first and second stream topology attribute values. For example, in some cases, the area server 64 selects a stream processing topology for the first real-time data stream type that conveys the first type of real-time data stream to one or more of the given network node and the other network nodes (in a mixed stream format, e.g., a chat stream originating from an audiozone in the second COLLADA stream reference example), and selects a stream processing topology for the second real-time data stream type that conveys the second type of real-time data stream to one or more of the given network node and the other network nodes (in an unmixed stream format, e.g., a voice stream originating from a StageZone and associated with a leader _ singer role attribute in the second COLLADA stream reference example).

The zone server 64 negotiates with the zone client to reconfigure the stream processing topology to the selected topology (fig. 17, block 258). In this process, the zone server 64 negotiates with the zone client to establish a set of connections between the zone client and optionally the zone server 64 (which delivers the required data flow data to the requesting zone client network node). In some cases, the regional server 64 sends a respective request for one or more real-time data streams to the regional client that will be relayed to the requesting regional client node or combined with other real-time data streams into a stream mix that will deliver the required real-time data stream data to the requesting regional client network node.

If the selected topology does not require a flow from the regional server 64 (FIG. 17, block 260), the regional server 64 manages the connections between regional client network nodes according to the current flow topology (FIG. 17, block 251). For example, in some cases (see, e.g., fig. 22), the selected topology communicates the required real-time data streaming data directly from one or more of the regional client network nodes to the requesting regional client network node, eliminating the need for the regional server 64 to send the data.

If the selected topology does not require a stream from the regional server 64 (FIG. 17, block 260), the region determines from the stream mix list 184 (see FIG. 8) whether the required server stream is available (i.e., currently being generated) (FIG. 17, block 262). The required server flow may take the form of a copy of the real-time data stream originating from one of the other regional client network nodes, or a mix of streams currently being generated from two or more real-time data streams (the regional server 64 is receiving from a regional client network node other than the requesting regional client network node). If the required flows are available (FIG. 17, block 262), the regional server 64 sends a copy of the required server flows to the requesting regional client network node (FIG. 17, block 270) and manages the regional client connections according to the current flow handling topology (FIG. 17, block 251).

If the required stream is not available (FIG. 17, block 262), the zone server 64 obtains the required server stream (FIG. 17, block 264). In this process, the regional server 64 may generate a copy of the real-time data stream received from one of the other regional client network nodes, or it may generate a stream mix from two or more real-time data streams received from regional client network nodes other than the requesting regional client network node. If a new stream mix is generated (FIG. 17, block 266), the regional server 64 updates the stream mix list 184 (FIG. 17, block 268), sends the required server stream to the requesting regional client (FIG. 17, block 270), and manages the regional client connections according to the current stream processing topology (FIG. 17, block 251). If a new stream mix is not generated (FIG. 17, block 266), the regional server 64 sends the required server stream to the requesting regional client (FIG. 17, block 270) and manages the regional client connections according to the current stream processing topology (FIG. 17, block 251).

4. Exemplary real-time data stream processing topology

This section describes an exemplary topology of the stream processing topology that may be selected by the zone server 64 in block 256 of the method shown in fig. 17.

a. Exemplary Server Mixed stream processing topology

Fig. 18 illustrates an embodiment of a real-time data stream processing topology 280 in which the regional server 64 receives sets of real-time data streams 282, 284, 286 from regional client network nodes 52-56, respectively. These data stream sets 282-286 include all real-time data streams required to connect objects in the shared virtual area according to the virtual area specification and their locations. Each of these streams is packetized by the regional clients 52-56. Each packet includes a header that contains a source identifier field that identifies the source of the packet, a sequence number, and other information.

The regional server 64 generates sets 288, 290, 292 of respective stream mixes from the received data stream sets 282-286, where each set 288-292 includes real-time data stream types (e.g., audio, video, chat, and motion data) that are requested by a respective one of the regional client nodes 52-56. In this process, the zone server 64 separates the incoming real-time data stream packets by type (e.g., video, audio, chat, motion data, and control) and by source identifier and reassembles the packets by sequence number. The regional server 64 then combines the same type of streams into a respective one of the stream mixes and sends 292 the set of the respective stream mixes to the respective one of the regional client network nodes 52-56.

As compared to the peer-to-peer topology shown in fig. 19, topology 280 reduces the number of network connections required by each regional client, thereby reducing the load on each regional client and their network; however, the load on the zone server 64 increases.

b. Exemplary Peer-to-Peer client hybrid stream processing topology

Fig. 19 illustrates an embodiment of a peer-to-peer real-time data stream processing topology 300 in which each of the regional client network nodes 52-56 sends a respective copy of each of the required real-time data streams to each of the other regional client network nodes 52-56. Thus, in the example illustrated in fig. 19, zone client 52 sends a first set of streams 302 to zone client 54 and a second set of streams 304 to zone client 56; zone client 54 sends a first set of streams 306 to zone client 52 and a second set of streams 308 to zone client 56; and the zone client 56 sends a first set of streams 310 to the zone client 52 and a second set of streams 312 to the zone client 54. These flows 302 and 312 include all real-time data flows required to connect objects in the shared virtual area according to the virtual area specification and their locations. Each of the flows is divided into packets, each of which includes a header that contains a source identifier field that identifies the source of the packet, a sequence number, and other information.

Each of the regional client network nodes 52-56 generates a respective stream mix from the real-time data streams received from the other regional client network nodes for each desired real-time data stream type (e.g., audio, video, chat, and motion data). In this process, each regional client separates the incoming real-time data stream packets by type (e.g., video, audio, chat, motion data, and control) and by source identifier and reassembles the packets by sequence number. Each regional client then sequences the reassembled packet stream by the correlated timestamp and source ID to maintain synchronization between real-time data streams during rendering.

The scalability of the topology 300 is constrained by the re-upload requirements on the regional client network nodes. Topology 300 also places heavy load on the network when using unicast transmission to transmit the required real-time data stream, as shown in fig. 19. In some embodiments, local network loading is mitigated by configuring each of the regional client network nodes 52-56 to send a single respective multicast transmission of each of the required data streams to one or more switches that distribute copies of the multicast stream to other network nodes.

c. Exemplary Peer-to-Peer client hybrid stream processing topology

Fig. 20 illustrates an embodiment of a peer-to-peer real-time data stream processing topology 320 that minimizes the connections between the four regional client network nodes 52-56 and 322. In the topology 320, each of the regional client network nodes 52-56, 322 sends a respective copy of each of the required real-time data streams to two other network nodes of the regional client network nodes 52-56, 322. Thus, in the example illustrated in fig. 20, zone client 52 sends a first set of streams 324 to zone client 56 and a second set of streams 326 to zone client 322; the regional client 54 sends a first set of streams 328 to the regional client 322 and a second set of streams 330 to the regional client 56; zone client 56 sends first set of streams 332 to zone client 52 and second set of streams 334 to zone client 54; and zone client 322 sends first set of streams 336 to zone client 52 and second set of streams 338 to zone client 54. In addition, each of the regional clients 52-56, 322 acts as a transceiving switch that relays a set of real-time data streams received from one of the other regional clients to another of the regional clients. In particular, regional client 52 relays a copy 340 of set of streams 336 from regional client 322 to regional client 56; regional client 54 relays a copy 342 of set of streams 334 from regional client 56 to regional client 322; regional client 56 relays a copy 344 of set 324 of streams from regional client 52 to regional client 54; and regional client 322 relays copy 346 of set 328 of streams from regional client 54 to regional client 52. These stream sets 324 and 346 include all real-time data streams required to connect objects in the shared virtual area according to the virtual area specification and their locations. Each of these streams is divided into packets, each of which includes a header that contains a source identifier field that identifies the source of the packet, a sequence number, and other information.

Each of the regional client network nodes 52-56, 322 generates a respective stream mix from the real-time data streams received from the other regional client network nodes for each required real-time data stream type (e.g., audio, video, chat, and motion data). In this process, each regional client separates incoming real-time data stream packets by type (e.g., video, audio, chat, motion data, and control) and by source identifier, and reassembles the packets by sequence number. Each regional client then sequences the reassembled packet stream by the correlated timestamp and source ID to maintain synchronization between real-time data streams during rendering.

The scalability of the topology 320 is constrained by the re-upload requirements on the regional client network nodes. Topology 320 also places heavy load on the network when using unicast transmission to transmit the required real-time data stream, as shown in fig. 20. In some embodiments, local network load is reduced by configuring each of the regional client network nodes 52-56, 322 to send a single respective multicast transmission of each of the replicated required data streams to one or more switches that distribute copies of the multicast stream to other network nodes.

d. Exemplary Server-mediated client hybrid stream processing topology

Fig. 21 illustrates an embodiment of a server-mediated real-time data flow processing topology 350 in which the zone server 64 acts as a transceiving switch that relays real-time data flow between the zone client network nodes 52-56. In the topology 350, each of the regional client network nodes 52-56 uploads a respective set 352, 354, 356 of required real-time data streams to the regional server 64, which relays a required copy of the uploaded streams to the regional client network nodes 52-56 according to their respective requirements. Thus, in the example illustrated in fig. 21, the zone server 64 sends respective copies 358, 360 of the stream set 352 uploaded by the zone client 52 to each of the other zone clients 54, 56; the zone server 64 sends respective copies 362, 364 of the stream set 354 uploaded by the zone client 54 to each of the other zone clients 52, 56; and the zone server 64 sends respective copies 366, 368 of the stream set 356 uploaded by the zone client 56 to each of the other zone clients 52, 54. Stream set 358-. Each of these streams is divided into packets, each of which includes a header that contains a source identifier field that identifies the source of the packet, a sequence number, and other information.

Each of the regional client network nodes 52-56 generates a respective stream mix from the real-time data streams received from the regional server network node 64 for each desired real-time data stream type (e.g., audio, video, chat, and motion data). In this process, each regional client separates incoming real-time data stream packets by type (e.g., video, audio, chat, motion data, and control) and by source identifier, and reassembles the packets by sequence number. Each regional client then sequences the reassembled packet stream by the correlated timestamp and source ID to maintain synchronization between real-time data streams during rendering.

e. Exemplary dynamic stream processing topology

In some embodiments, the area server 64 dynamically determines a real-time data stream processing topology that delivers a prescribed set of real-time data streams to a given network node. In this process, the zone server 64 selects the topology as the stream handling topology that involves exchanging real-time data streams between network nodes in a first set through a central network node and exchanging real-time data streams between network nodes in a second set over a direct peer-to-peer network connection. The first set of nodes may be different from the second set of nodes. As explained above, each of the network nodes has at least one of a source and a sink of one or more of the at least one object and the real-time data stream type associated with a respective location in the virtual area. The area server 64 forwards the real-time data stream packets between the network nodes in the first set based on the one or more switching rules and the determined real-time data stream processing topology.

Fig. 22 illustrates an embodiment of a real-time data stream processing topology 370 that dynamically combines elements of the stream processing topology described above. In particular, in the exemplary topology shown in fig. 22, the regional client network nodes 52-56 receive the required real-time data streams through a dynamic combination of peer-to-peer connections and server-mediated connections, with the regional server 64 acting as a transceiver switch between the regional client network nodes as necessary.

In the topology 370, each of the regional client network nodes 52-56 uploads a respective set 372, 374, 376 of required real-time data streams to the regional server 64. In the example illustrated in fig. 22, the zone server 64 relays a copy 378 of the stream set 372 uploaded by the zone client 52 to the zone client 54; the zone server 64 relays the respective copies 380, 382 of the stream set 374 uploaded by the zone client 54 to each of the other zone clients 52, 56; and zone server 64 relays a copy 384 of stream set 376 uploaded by zone client 56 to zone client 54. In addition, the zone client 52 receives the required set of streams 386 directly from the zone client 54, and the zone client 56 receives the required set of streams 388 directly from the zone client 52. Stream set 378-. Each of these streams is divided into packets, each of which includes a header that contains a source identifier field that identifies the source of the packet, a sequence number, and other information.

The topology 370 enables the bandwidth available on the regional client network nodes 52-56 to be optimized such that the regional client network nodes 52-56 receive the maximum number of unmixed real-time data streams.

VII second System architecture embodiments

Fig. 23 illustrates an embodiment of a shared virtual area communication environment 400 that includes area client network nodes 52-56, an embodiment 402 of an area server network node 64, and a network switch 404. The structure and operation of the elements of the shared virtual area communication environment 400 are the same as those of the shared communication environment described above, except that one or more of the real-time data stream exchange functionality of at least one of the area server 64 and the client communication application 142 (see fig. 7) has been incorporated into the network switch 404, which enables the network switch 404 to perform automated real-time data stream exchange according to one or more of the methods described above.

The network switch 404 is a computer network device that includes a memory 405, a processing unit 407 that includes at least one computer processor, and a network adapter 403, the network switch 404 being connected to the area client network nodes 54, 56 and the area server 402 through the network adapter 403. In operation, the network switch 404 connects network sub-segments by inspecting data packets, determining the source of the packets, and forwarding the packets to their respective destinations. For each packet, the network switch compares the destination and source hardware addresses to a table of network subsegments and addresses. If the subsegments are the same, the packet is dropped; otherwise, the network switch 404 forwards the packet to the appropriate sub-segment. Network switch 404 determines the network destination to which the packet is forwarded, typically based on forwarding table 409, which forwarding table 409 contains the preferred route for packet forwarding. Network switch 404 generates forwarding table 409, typically by applying a routing algorithm to a routing table 411, which routing table 411 contains routes to network destinations in the vicinity of network switch 404. The routes in forwarding table 409 and routing table 411 are typically specified by information describing the network topology between network switch 404 and the network destination. The network switch 404 does not forward bad or off-directed packets. Network switch 404 may operate at one or more of the OSI layers, which include a physical layer, a data link layer, a network layer, and a transport layer. Exemplary implementations of network switch 404 include, but are not limited to, network switches, network routers, and network hubs.

In some embodiments, network switch 404 switches real-time data stream connections between network nodes sharing a virtual area. The network adapter 403 receives the virtual area specification 406 from the area server 402. The virtual area specification 406 includes a specification of one or more switching rules that respectively define respective connections between a source of a respective real-time data stream type and a sink of the real-time data stream type according to a location in the virtual area. The computer readable memory 405 stores a virtual area specification 406 and one or both of a routing table 411 and a forwarding table 409, wherein each of the tables 409, 411 includes network topology information describing a route to a network destination. The processing unit 407 forwards real-time data stream packets between two or more of the network nodes 52-56, wherein each of the network nodes 52-56 is associated with at least one of a source and a sink of one or more of the real-time data stream types and a respective location in the virtual area. The processing unit 407 forwards one or more real-time data stream packets based on the network topology information and the one or more switching rules.

In some embodiments, the network switch performs one or more of the functions of the regional client stream switching manager 168. In these embodiments, the processing unit 407 establishes one or more real-time data stream connections between the network nodes 52-54, wherein the network nodes 52-56 are associated with respective objects, each of which is associated with at least one of a source and a sink of one or more of the real-time data stream types. The processing unit 407 establishes one or more real-time data stream connections based on one or both of the methods of fig. 10 and 12-14, based on the one or more switching rules, the respective sources and sinks associated with the object, and the respective locations of the object in the virtual area.

In some embodiments, the network switch 404 performs one or more of the functions of an area server network node. In particular, the network switch 404 performs some or all of the real-time data stream switching functions of the zone server 64 (see, e.g., fig. 8). In this regard, the network switch 404 receives configuration data from the zone server 64. The configuration data includes a copy of the virtual area specification 180 (see fig. 8) and a copy of the object registers 182 (see fig. 8). The network switch 404 initializes the local virtual area specification cache 406 with a copy of the virtual area specification 180 and the local object registers 408 with a copy of the object registers 182. Periodically, in response to an event (e.g., avatar movement), or both, the network switch 404 updates the local object register 408 with information obtained from tracking the correspondents' avatars and other objects entering, leaving, and moving around in the virtual area based on motion data received from the area clients 52-56. The network switch 404 determines the real-time data stream connections that deliver the required data stream data to the regional client network nodes 52-56 according to the method of fig. 17. The process includes determining an optimal stream processing topology that provides the required real-time data stream data to the regional client network nodes 52-56.

In some embodiments, the network switch 404 dynamically determines a real-time data flow processing topology that delivers a prescribed set of real-time data flows to a given network node. In this process, the processing unit 407 selects as the stream processing topology a topology that involves exchanging real-time data streams between network nodes in a first set through a central network node and exchanging real-time data streams between network nodes in a second set (which is typically different from the first set) over a direct peer-to-peer network connection. As explained above, each of the network nodes is associated with at least one of a source and a sink of one or more of a respective location and a real-time data stream type in the virtual area. The processing unit 407 forwards the real-time data stream packets between the network nodes in the first set based on the one or more switching rules and the determined real-time data stream processing topology.

VIII, summary of

Embodiments described herein provide systems and methods for exchanging real-time data stream connections in a shared virtual area communication environment. These embodiments enable switching rules for connecting real-time data flows between network nodes communicating over a shared virtual area to be explicitly dependent on the specifications of the virtual area. These embodiments allow the designer of the virtual area to control not only the shape and form of the virtual area, but also the manner in which the communicants interconnect through the real-time data stream. In addition, by making the automatic switching rules dependent on location in the virtual area, these embodiments reduce the complexity involved in connecting and disconnecting correspondent nodes and increase the scalability of the system, as compared to systems that establish and terminate connections based on the attributes and properties of objects within the virtual space and systems that tightly associate signal processing functions with stream routing, connection and disconnection functions.

Other embodiments are within the scope of the following claims.

Claims

1. In a method of exchanging real-time data stream connections between network nodes sharing a virtual area, the improvement comprising:

ascertaining a set of real-time data streams that enable a given one of the network nodes (52, 54, 56, 64, 404) associated with respective locations in the virtual area (28) to participate in a collaborative communication session with one or more other of the network nodes (52, 54, 56, 64, 404) associated with respective locations in the virtual area (28);

determining one or more real-time data stream connections to communicate the set of real-time data streams to the given network node based at least in part on a bandwidth capability of the given network node; and

establishing a real-time data flow connection between the given network node and one or more other of the network nodes.

2. The method of claim 1, wherein the determining comprises determining a respective form in which to receive each of the real-time data streams, wherein each of the determined real-time data streams is in the form of an unmixed real-time data stream or a mixed real-time data stream derived from a combination of real-time data streams transmitted from network nodes of the other network nodes.

3. The method of claim 1, wherein the determining comprises determining a network route over which each of the real-time streams is received, wherein the determined network route is a direct peer-to-peer network route or a network route that is mediated by one or more of the other network nodes.

4. The method of claim 1, further comprising storing a virtual area specification (60, 180, 406) including a specification of one or more switching rules, each switching rule defining a respective connection between a source (66) of a respective realtime data stream type and a sink (68) of that realtime data stream type according to location in the virtual area (28), wherein at least one of the ascertaining and the determining is based on the switching rule.

5. The method of claim 1, further comprising sending a list of one or more hybrid real-time data streams to the given network node derived from real-time data streams sent from network nodes of the other network nodes.

6. The method of claim 1, wherein the determining comprises discovering bandwidth capabilities of one or more of the other network nodes and selecting the one or more real-time data stream connections based on the discovered bandwidth capabilities.

7. The method of claim 1, wherein the one or more determined real-time data flow connections involve exchanging real-time data flows between network nodes (52, 54, 56) in the first set and exchanging real-time data flows between network nodes (52, 54, 56) in the second set over direct peer-to-peer network connections through a central network node (64, 404).

8. The method of claim 1, wherein the one or more determined real-time data stream connections involve sending a mixed real-time data stream to the given network node, the mixed real-time data stream comprising the requested real-time data stream data and being derived from real-time data streams sent from network nodes of the other network nodes.

9. The method of claim 1, wherein the determining comprises determining one or more real-time data stream connections that maximize delivery of the unmixed real-time data streams to the given network node.

10. An apparatus for exchanging real-time data stream connections between network nodes sharing a virtual area, wherein the improvement comprises:

a computer readable memory (124, 128, 405) storing computer readable instructions; and

a data processing unit (122, 136, 403, 407) coupled to the memory that is operable to execute the instructions and is operable to perform operations based at least in part on execution of the instructions, including

establishing a real-time data flow connection between the given network node and the one or more other of the network nodes.

11. A computer readable medium storing computer readable instructions for exchanging real-time data stream connections between network nodes sharing a virtual area, wherein the improvement comprises computer readable instructions operable to cause a computer to perform operations comprising:

establishing a real-time data flow connection between the given network node and the one or more other of the network nodes (52, 54, 56, 64, 404).

12. In a method of exchanging real-time data stream connections between network nodes sharing a virtual area, the improvement comprising:

for each of one or more receiving network nodes of the network nodes (52, 54, 56, 64, 404), determining a respective link of a respective transmit set on which to transmit one or more real-time data streams, wherein each of the links has a respective link bandwidth; and

for each of the links, allocating a respective link bandwidth between one or more lanes respectively allocated to one or more real-time data streams in the respective transmit set and transmitting the one or more real-time data streams in the respective transmit set to a respective receiving network node on the respectively allocated lanes.

13. The method of claim 12, wherein the determining comprises, for each of the links, ascertaining one or more respective bandwidth levels for each of the one or more real-time data streams in the respective transmit set and allocating a respective link bandwidth to the link based on the ascertained bandwidth levels.

14. The method of claim 13, wherein for each of the links

Said ascertaining comprises identifying a respective minimum bandwidth level for each of the real-time data streams in said respective transmission set, an

A respective minimum link bandwidth level is calculated from the one or more identified respective minimum bandwidth levels.

15. The method of claim 14, further comprising dropping any link in response to determining that the bandwidth available for that link fails to meet a corresponding minimum link bandwidth level.

16. The method of claim 13, wherein, for each of the links:

said ascertaining comprises, for each of one or more real-time data streams in the respective transmit set, identifying at least two respective bandwidth levels in a respective priority order ordered from a respective first preferred bandwidth level to a respective second preferred bandwidth level; and

a respective target link bandwidth level is calculated based at least in part on the identified first preferred bandwidth level and a respective fallback link bandwidth level is calculated based at least in part on the identified second preferred bandwidth level.

17. The method of claim 16, wherein the determining comprises, for each of the receiving network nodes (52, 54, 56, 64, 404),

attempting to establish a corresponding link to the receiving network node at the target link bandwidth level, an

In response to a failure to establish a respective link to the receiving network node at the target link bandwidth level, attempting to establish a respective link to the receiving network node at the fallback link bandwidth level.

18. The method of claim 17, wherein the attempting comprises comparing the target link bandwidth level to a current amount of bandwidth available for transmitting the respective transmit set and a current amount of bandwidth available for the respective receiving network node.

19. The method of claim 12, wherein the determining comprises, for each of the receiving network nodes (52, 54, 56, 64, 404),

attempting to establish a respective link to the receiving network node at a respective candidate link bandwidth level, an

In response to a failure to establish a respective link to the receiving network node at the respective candidate link bandwidth level, abandoning at least one optional real-time data flow in the transmit data set.

20. The method of claim 12, wherein the determining comprises, for each of the receiving network nodes (52, 54, 56, 64, 404),

Establishing links for transmitting one or more real-time data streams in the respective transmission sets to the receiving network node over one or more intervening network routes in the other network nodes in response to a failure to establish respective links to the receiving network node at the respective candidate link bandwidth levels.

21. The method of claim 12, wherein the determining comprises, for each of the receiving network nodes (52, 54, 56, 64, 404),

attempting to establish respective links to the receiving network node at respective candidate link bandwidth levels; and

establishing links to the receiving network node that convey one or more of the real-time data streams in the respective transmission set in the form of one or more hybrid real-time data streams derived from a combination of real-time data streams transmitted from other ones of the network nodes in response to a failure to establish respective links to the receiving network node at the respective candidate link bandwidth levels.

22. The method of claim 12, wherein the determining comprises allocating, for each of the links, a respective bandwidth in an amount determined based on an attribute associated with the respective receiving network node.

23. The method of claim 12, wherein, for each of the links, the assignment of the respective link bandwidth is based on one or more stream priority levels respectively associated with the one or more real-time data streams in the respective transmit set.

24. The method of claim 12, wherein each of the links is a respective unidirectional link from a respective one of the network nodes (52, 54, 56, 64, 404) transmitting a respective transmit set to a respective one of the receiving network nodes.

25. An apparatus for exchanging real-time data stream connections between network nodes sharing a virtual area, wherein the improvement comprises:

For each of one or more receiving network nodes of the network nodes (52, 54, 56, 64, 404), determining a respective link of a respective transmission set on which to transmit one or more real-time data streams, wherein each of the links has a respective link bandwidth, an

For each of the links, allocating a respective link bandwidth between one or more lanes respectively allocated to the one or more real-time data streams in the respective transmit set and transmitting the one or more real-time data streams in the respective transmit set to a respective receiving network node on the respectively allocated lanes.

26. A computer readable medium (124, 128, 405) storing computer readable instructions for exchanging real-time data stream connections between network nodes sharing a virtual area, wherein the improvement comprises the computer readable instructions being operable to cause a computer to perform operations comprising:

for each of one or more receiving network nodes of the network nodes (52, 54, 56, 64, 404), determining a respective link of a respective transmit set on which to transmit one or more real-time data streams, wherein each of the links has a respective link bandwidth, an

27. A network adapter (462) for exchanging real-time data stream connections between network nodes sharing a virtual area, wherein the improvement comprises:

a computer readable memory (482) storing computer readable instructions; and

a processing unit (478) coupled to the computer-readable memory that is operable to execute the instructions and is operable to perform operations based at least in part on the execution of the instructions, including

For each of one or more receiving network nodes of the network nodes (464, 472), determining a respective link of a respective transmit set on which to transmit one or more real-time data streams, wherein each of the links has a respective link bandwidth, an