CN1823503A - Electronic device connection resource management - Google Patents

Abstract

In a connection arrangement including two or more electronic devices, wherein information can be exchanged among the electronic devices through a plurality of communication links between the electronic devices, at least one of the electronic devices being configurable for communicating with a data source, a method for presenting a multi-channel message originating from the data source, the multi-channel message including a two or more components, includes the steps of allocating each of at least a portion of the components in the multi-channel message to at least one electronic device and, for each allocated component, determining possible communication paths between the data source and the at least one electronic device allocated to the corresponding component. The method further includes the steps of selecting, based at least in part on one or more selection criteria, at least one of the possible communication paths for the allocated components, each of the selected communication paths representing an optimal route between the data source and the at least one electronic device allocated to the corresponding component, and routing each of the allocated components in the multi-channel message according to the selected communication paths for presentation of the allocated components by the corresponding electronic device(s).

Description

Electronic device connection resource management

Cross References to Related Applications

This invention is related to U.S. Patent Application No. .10/442,218, the disclosure of which is hereby incorporated by reference.

technical field

The present invention relates generally to wireless communication systems, and in particular to techniques for managing resources among multiple electronic devices in a wireless connection arrangement.

Background technique

Recent advances in mobile computing technology, coupled with the increased demand for "transparent mobility" (ie, mobility with a minimal amount of pre-planning), has led to a proliferation of mobile computing devices and applications. Some of these devices, such as notebook computers, notebooks, etc., can be used in a variety of applications and thus can be considered general purpose devices. However, because of the generality of these devices, they are not well suited for any dedicated application out of the box. As a result, various types of task-specific electronic devices have emerged, such as personal digital assistants (PDAs), mobile cellular telephones, digital music players (eg, MP3 devices), and the like. Each of these specialized devices is generally optimized for immediate use, albeit for a limited set of applications. Mobile users often own and frequently use both general-purpose mobile computing devices and task-specific mobile devices. Many of these devices are capable of communicating independently with other electronic devices, eg, using a Wide Area Network (WAN), a Local Area Network (LAN), a short-range Personal Area Network (PAN), and the like.

With few exceptions, today's mobile devices are designed for standalone use. However, as PANs such as Bluetooth( ^R) (registered trademark of Bluetooth SIG, Inc.) become more common, it is envisaged that mobile users can use their electronic devices in a more coordinated manner. For example, a mobile user may watch a music video clip on his cell phone while simultaneously listening to a streaming download of related music on his digital music player. This type of communication is often referred to as "multi-channel" communication because a single logical message (eg, a music video) may include multiple media types sent over multiple communication links to multiple end-user devices. Multi-channel communication differs from multimedia messaging (e.g., Moving Picture Experts Group 4 (MPEG-4)) in that multimedia messaging generally standardizes messages carried on the same communication channel and sent to a single device, which A single device is capable of rendering at least one of its components, while multi-channel communication involves coordinating activities on multiple communication channels and/or devices simultaneously.

One of the disadvantages associated with conventional multi-channel communication environments is that one or more communication links required to access a given message may not be available. Furthermore, the message delays associated with each communication link may vary independently of each other at any time and thus generally do not match each other. When two or more components of a multi-channel message experience different delays, they will be presented to the user asynchronously, which may not be perceived as desirable.

Therefore, there is a need in the field of mobile communication technologies for improved methods of coordinating resources among multiple electronic devices and/or communication links, particularly in a multi-channel communication environment.

Contents of the invention

The present invention provides techniques for providing connection resource management between two or more electronic devices and/or communication links in a wireless connection arrangement. The technique of the present invention substantially eliminates the need to manually select at least how the components of a multi-communication message are received, which links these components traverse from their respective sources to their respective destinations, and when configured in a wireless communication system How to reconfigure when changes and/or failures occur in .

The invention disclosed herein implements methods for automatically and dynamically evaluating and/or selecting communication paths for packets currently carrying multi-channel messages, typically received from multiple communication links and destined for multiple electronic devices multiple presence sources for the presentation of these multi-channel messages.

According to an embodiment of the invention, in a connection arrangement comprising two or more electronic devices, wherein information can be exchanged between the electronic devices via a plurality of communication links between the electronic devices, at least one electronic device can be Configured for communicating with a data source, a method for presenting a multi-channel message originating from the data source comprising two or more components comprises the steps of: at least one of the components in the multi-channel message Each of the portions is assigned to at least one electronic device, and for each assigned component, a possible communication path between the data source and the at least one electronic device assigned to the corresponding component is determined. The method further comprises the step of selecting at least one possible communication path for the assigned component based at least in part on one or more selection criteria, each selected communication path representing the data source and at least one communication path assigned to the corresponding component An optimal path between electronic devices, and routing each assigned component of the multi-channel message according to the selected communication path for presentation of the assigned component by the corresponding electronic device.

These and other objects, features and advantages of the present invention will become apparent from the following detailed description of exemplary embodiments of the present invention with reference to the accompanying drawings.

Description of drawings

Fig. 1 is a block diagram illustrating an exemplary mobile communication system in which the method of the present invention may be implemented.

FIG. 2 is a process flow diagram illustrating an exemplary communication path enumeration method according to one embodiment of the present invention.

FIG. 3 is a process flow diagram illustrating an exemplary method for enumerating communication paths between electronic devices according to one embodiment of the present invention.

FIG. 4 is a process flow diagram illustrating an exemplary overall routing method according to one embodiment of the present invention.

FIG. 5 is a process flow diagram illustrating an exemplary method for selecting an optimal routing path according to one embodiment of the present invention.

Detailed ways

The present invention will be described herein in the context of an exemplary electronic device connection arrangement comprising a plurality of electronic devices associated with one or more particular users. However, it should be understood that the invention is not limited to this or any particular connection arrangement. Rather, the present invention is more generally applicable to techniques for optimally routing components of a multi-channel message among multiple electronic devices in a device connection arrangement.

Figure 1 illustrates an exemplary device connection arrangement 100, which may be referred to herein as a personal workspace, in which the techniques of the present invention may be implemented. The connection arrangement 100 includes a plurality of electronic devices such as a notebook computer 1 , a personal data assistant (PDA) 2 , a notebook computer 3 , a pager 4 and a cellular telephone 5 . These electronic devices are preferably configured as portable (ie, mobile devices), although such electronic devices are not required to be portable in order to benefit from the inventive techniques described herein. The set of electronic devices 1, 2, 3, 4, 5 may represent eg devices that are commonly used at a given location or by a given user. Information can be exchanged between the plurality of electronic devices 1, 2, 3, 4 and 5 in a variety of ways, only some of which are described in the drawings and this description.

By way of example only, information may be exchanged between notebook computer 1 and notebook mini computer 3 via an infrared link 6 (eg, an Infrared Data Association (IrDA) link). Alternatively, a standard communication protocol such as the Institute of Electrical and Electronics Engineers (IEEE) 802.11b standard can be used, between the notebook computer 1 and the notebook computer 3, between the notebook computer 1 and the notebook computer 3 through wireless local area network (WLAN) links 7, 8 and 9, respectively. 3 and PDA 2, between PDA 2 and notebook computer 1 to exchange information. As will be understood by those skilled in the art, other standard WLAN communication protocols (eg, IEEE 802.11a, IEEE 802.11g, etc.), as well as non-standard communication protocols, may be used with the present invention. Likewise, information can be exchanged between PDA 2 and pager 4, between PDA 2 and cell phone 5, and between cell phone 5 and pager 4 via Bluetooth ^(R) radio links 10, 11 and 12, respectively.

As this figure clearly shows, the exemplary connectivity arrangement 100 may include a plurality of WAN communication links 13 , 14 , 15 and 16 . These communication links 13, 14, 15 and 16 are preferably configurable to provide, for example, information via Internet services between a data source which may include the Internet (not shown) and the corresponding electronic device 5, 4, 1, 3. (ISP) or other gateways to transfer data in both directions. Communication link 13 may include, for example, a cellular radio link, communication link 14 may include, for example, a paging radio link, communication link 15 may include, for example, a Digital Subscriber Line (DSL) link, and communication link 16 may include, for example, a modem link. As used herein, the term "communication link" is intended to refer to a wireless communication channel, such as but not limited to radio frequency (RF), infrared (IR), microwave, etc., or a wired communication channel, such as but not limited to telephone, cable, etc., although Use other communication media.

As will be appreciated by those skilled in the art, messages between the Internet and the various electronic devices in this exemplary connection arrangement 100 can be communicated in a variety of ways. For example, a message including text information may be transmitted from the Internet over paging radio link 14 and received by pager 4, relayed to PDA 2 over ^Bluetooth® radio link 10, and then relayed over IEEE 802.11b WLAN link 9 to Notebook 1. This was judged to be the optimal communication route between pager 4 and notebook computer 1, because any other communication route traverses more links and includes additional electronic equipment, each additional electronic equipment acts as a relay point, thus increasing This increases the delay and increases the overall power consumption in the entire connection arrangement 100.

It should be understood that one or more communication links and/or relay points (devices) making up a given path may be considered unreliable, and thus the preferred communication path is not necessarily the shortest path. For example, Bluetooth ^(R) radio link 10 may be found to be unreliable, and in this case a better path may include Bluetooth(R ⁾ radio links 11 and 12 instead of link 10. In this path, the cellular telephone 5 acts as an additional relay point.

By way of example only, an application of the exemplary connection arrangement 100 according to an aspect of the present invention will now be described. Consider a multi-channel message that includes a video component and an audio component, both originating from the Internet. Moreover, assuming that it has been determined (e.g., by using the method proposed in a related application entitled "Techniques for Providing a Virtual Workspace Composed of a Multiplicity of Electronic Devices") that the optimal distribution of multichannel message components among electronic devices is The video component of the message is presented on 2, and the audio component is presented on the cell phone 5.

Assuming all devices and links are reliable, the optimal path for this video component is from the Internet to the notebook computer 1 via the DSL link 15, and then to the PDA 2 via the IEEE 802.11b WLAN link 9. The audio component of the message can also travel this same path and is then relayed by the PDA 2 to the cellular phone 5 via the Bluetooth ^(R) radio link 11. However, this will add additional delay between the video and audio components, at least in part due to the increased delay associated with the relay process and communication link 11 between the PDA 2 and cell phone 5 . Instead, the optimal route for the audio component may be from the Internet directly to the cellular telephone 5 via the cellular radio link 13 . The actual delay difference between that path and another communication path is preferably evaluated, and the path is preferably selected for the audio component with a delay that substantially matches the delay associated with the video component. In this way, the presentation of the audio component and the video component of the multi-communication message can advantageously be synchronized with each other.

In order to describe the method of the present invention more clearly, the link to the Internet is denoted as Li _ik , where i is the number of an electronic device, and k enumerates all links between the Internet and the electronic device. For example, DSL link 15 may be denoted as _L11 , the first (and only) link between notebook computer 1 and the Internet. Furthermore, a path between electronic devices can be denoted as M _ijk , where i is the number of the first electronic device, j is the number of the second electronic device, and k enumerates all links between the two devices . For example, the IEEE 802.11b WLAN link 8 between the PDA 2 and the notebook computer 3 may be denoted _M231 , the first (and only) link between the two devices. Optionally, the IRDA link 6 between the notebook computer 1 and the notebook computer 3 may be denoted as M ₁₃₂ , the second link between the two devices. The values of Li _ik and _Mijk can be specified as attributes of a given link. Other attributes may also be assigned to links including, for example, delay, bandwidth, cost, reliability records, and the like.

An enumeration of all paths between the Internet and a given electronic device p in this exemplary connection arrangement 100 may be formed as the following sequence:

L _ia M _abc M _bde ...M _dpf

In cases where there is only one link between each pair of devices, a simpler sequence can be formed as follows:

L _ia M _ab1 M _bc1 ...M _cp1

In each case, circular paths are not allowed. This requires that for a given sequence of M _ijk , the actual values of i and j are not allowed to appear more than twice. Paths containing other paths as subsets are also removed from further consideration.

In the general case involving any number of electronic devices, enumeration of all paths can be time consuming and memory intensive. In practice, however, the number of electronic devices in a given personal workspace is typically small (eg, less than about 10), and the number of possible communication links is usually also small (eg, less than about 20). For example, there are 15 possible communication paths between the Internet and pager 4 in this exemplary connection arrangement 100 . Specifically, there are 6 paths involving L ₁₁ , 6 paths involving L ₃₁ , 2 paths involving L ₅₁ , and 1 path involving L ₄₁ . For example, one of the 6 paths involving L ₁₁ is L ₁₁ M ₁₃₂ M ₃₂₁ M ₂₅₁ M ₅₄₁ . It is likely that this path is inferior to the other of the 6 paths involving L ₁₁ , the path L ₁₁ M ₁₂₁ M ₂₄₁ , at least from a delay point of view.

Figures 2 and 3 illustrate an exemplary method for determining all possible communication paths in any personal workspace, given a selection of communication links and selection of a destination electronic device p, according to an embodiment of the present invention. Specifically, FIG. 2 is a process flow diagram illustrating an exemplary path enumeration method 200 of the present invention. It should be understood that other methods for determining possible communication paths in a personal workspace are similarly contemplated by the present invention. For ease of explanation with reference to FIGS. 2 and 3 , it is assumed that there is only one communication path between any two electronic devices and between the Internet and any electronic device. Generalizations based on this assumption will be readily appreciated by those skilled in the art. Using this simpler case, the representations Li _ik and _Mijk defined above can be replaced by the simplified representations Li and _Mij since the value of k will always be one.

Referring to FIG. 2, given an input communication link number i and a destination electronic device number p, the exemplary path enumeration method 200 determines all paths from the given link to the destination electronic device. At block 20, the link number i and the destination electronic device number p are entered. The exemplary method 200 continues at block 21, which initializes an index j, where j is a positive integer, eg, j is initially set to 1, but not equal to the input link number i. When the input link number i is 1, j is preferably initialized to 2. Block 22 determines whether there is a communication path Mij directly between electronic device i, the device to which the incoming link is connected, and electronic device _j . When no path M _ij is found between devices i and j, process flow branch 24 is taken to block 25 where index j is incremented by 1 with the constraint that j is not equal to i. The example path enumeration method 200 is complete when j, after incrementing, exceeds the largest electronic device number. Process flow control returns to block 22 when index j does not exceed the largest electronic device number in the connection arrangement.

Process flow branch 23 to block 27 is taken when a path M _ij is found directly between electronic device i and electronic device j. Block 27 determines all communication paths from device j to destination device p excluding device i. FIG. 3 shows an exemplary method 300 for determining a communication path between two electronic devices according to an embodiment of the present invention. Excluding device i is necessary in order to exclude cycles in the path. When all paths have been found, process control passes to block 28 where the prefix L _i M _ij is added to each communication path determined at block 27 . Block 28 additionally generates an output list including all paths. When all paths have been appropriately prefixed and added to the output list, process control continues to block 25 where index j is incremented and evaluated as explained above.

Referring now to FIG. 3 , an exemplary path determination method 300 will be described. Method 300 , which may be implemented in block 27 of the exemplary path enumeration method 200 shown in FIG. 2 , is similar to method 200 except that method 300 basically only involves discovering communication paths between electronic devices. The example path determination method 300 begins at block 30, where an initialization process is performed. The initialization process may include receiving as input an initial electronic device number i and a destination electronic device number p. Any output path will start with device i and end with device p. Furthermore, block 30 receives as input an exclusion list e. Any electronic device numbers in the exclusion list will not be included in the route generated by the route determination method 300 . The exemplary method 200 of FIG. 2 preferably uses the method 300 of FIG. 3 with an exclusion list comprising a single number.

After performing the initialization process in block 30, method 300 continues to block 40, which determines whether input device i and destination device p are the same. When i equals p, process control branch 41 is taken and the example path determination method 300 is complete. Process control may then return to the calling process, which may be located in block 27 of the example method 200 of FIG. 2 as described above. When j is not equal to p, block 31 is entered, which initializes the index j so that it is either 1 or the smallest device number not in the exclusion list e. When index j is initialized, process control continues to block 32, which determines whether a communication path exists directly between electronic devices i and j. When no path is found, process control branch 34 is taken to block 35 which increments index j by 1 with the constraints that j is not in the exclusion list e and j is not greater than the largest electronic device number in the connection arrangement. When, after incrementing index j, it is determined that j exceeds the maximum electronic device number, control process branch 36 is taken and the example path determination method 300 is considered complete. At this point, process control may return to block 27 in FIG. 2 . When j does not exceed the maximum electronic device number, enter block 32 again.

When block 32 determines that there is indeed a communication path directly between devices i and j, control process branch 33 is taken and the method 300 continues by entering block 37 . Block 37 determines all paths from device j to device p excluding device i, again with the constraint that j is not in the exclusion list e to which device i was added. Note that the exemplary path determination method 300 in FIG. 3 describes a general path determination process. Therefore, block 37 may be considered to be a recursive call to path determination method 300 . Once all communication paths from device j to device p have been found, the process continues at block 38 where the prefix M _ij is added to each path determined at block 37 . When all prefixes have been properly added, block 35 is entered and process control continues as described above.

FIG. 4 shows an exemplary overall routing decision method 400 according to one embodiment of the present invention. As this figure clearly shows, the exemplary routing decision method begins when at block 50 a multi-channel message arrives or notification is received that a multi-channel message is available. Each component _Cj constituting the multi-channel message is preferably identified in the notification, where j is an integer representing a component number. Process flow then continues to block 51 where each component C _j of the received multi-channel message is operatively assigned to one or more specific electronic devices p _j . The assigning step is preferably performed in an automated fashion and may be based at least in part on one or more characteristics of the electronic device itself (e.g., memory size, display resolution, etc.), one or more characteristics of the communication link (e.g., , speed, bandwidth, etc.), user preferences, etc., although other techniques for distributing the components of a multi-channel message are contemplated by the present invention.

The distribution of components C _j of a multi-channel message to appropriate electronic devices p _j may be performed once, for example upon receipt of the multi-channel message. However, in a preferred embodiment of the invention, the allocation process may be performed periodically (e.g., once a minute) to determine whether the conditions on which the allocation decision was originally based are still valid, and when the conditions in the connection arrangement Dynamically update allocated resources when they have changed. In this way, if an electronic device to which a particular component of the multi-channel message has been assigned fails or is otherwise unreliable, it can be replaced by a new electronic device. Furthermore, as devices are added to or removed from the connectivity arrangement (eg, as a user's wireless communication network expands or contracts), the allocation of components of the multi-channel message can be dynamically changed accordingly. One or more electronic devices _pj may be found using the methods described in the above-mentioned related application entitled "Techniques for Providing a Virtual WorkspaceComprised of a Multiplicity of Electronic Devices" to present component _Cj in the multichannel message.

Block 52 is entered after each component C _j of the received multi-channel message has been assigned in block 51 to a corresponding electronic device p _j for presentation to the user. At block 52, for each component _Cj of the multi-channel message, all communication paths between the Internet (or other data source) and the electronic device _pj corresponding to component _Cj are found. Block 52 preferably utilizes the exemplary methods 200, 300 described above with reference to FIGS. 2 and 3, respectively, although other path enumeration and evaluation techniques are also contemplated by the present invention. Once block 52 has been completed, process control continues at block 53 where an optimal communication path for each component is operatively selected. The example routing decision method 400 is terminated at block 54 when block 53 has completed its process.

FIG. 5 illustrates an example routing method 500 for selecting an optimal communication path for each component in a received multi-channel message. The exemplary routing method 500 is preferably utilized at block 53 in the exemplary routing decision method 400 shown in FIG. 4, although other routing techniques may similarly be used. As this figure clearly shows, the path selection method 500 begins at block 60, which receives as input a plurality of communication paths to be compared, and a policy for path comparison. The policy input to block 60 defines a set of criteria (ie, rules) by which to evaluate and compare various communication paths. For example, in a preferred embodiment of the present invention, the strategy may include one or more path characteristics, such as but not limited to delay, bandwidth, reliability, etc. that can be used to determine the optimal path.

Once the set of communication paths and policies have been entered at block 60, the routing method 500 continues to block 61 where an initialization process is performed. Block 61 preferably initializes at least two indexes, index i, where i corresponds to the current communication path being evaluated, and an index variable best, which holds the index number i of the best path found so far. The phrase "best path" as used herein preferably refers to the communication path that more closely matches the selection criteria associated with the policy. Once initialization has been performed, block 62 is entered. Block 62 determines whether index i exceeds the number of paths input to block 60 . When the index i exceeds the number of paths, control process branch 63 is taken and the path selection method 500 is complete. Process control may then return to the calling routine, which may be block 53 in the exemplary decision method 400 shown in FIG. 4 .

When the index i evaluated at block 62 does not exceed the number of communication paths entered at block 60 , process control continues via control process branch 64 at block 65 . Block 65 computes what may be called the "summary attribute" of a communication path. Specifically, each link in a given path is preferably characterized by a set of attributes. These attributes may be stored, at least temporarily, in some electronic computing device or determined when the path is to be determined. Typically, one or more electronic computing devices on which a link terminates maintains attributes corresponding to the link. These properties may be, for example, an estimate of the link's delay, a distribution of link delays, an estimate of the link's bandwidth, the number of packets dropped on the link as a proportion of the number of packets sent, or various other properties that can help characterize the link. One property of some importance is the power required to send a packet of a given length over the link.

Block 65 preferably uses the attributes of the links making up a given communication path i to compute a single aggregate attribute set for that path. The method used to calculate this aggregate attribute set may depend on the type of attribute. For example, if the attribute is power, the aggregate attribute can be calculated as the sum of the power consumed on the constituent links making up path i. Similarly, if the attribute is bandwidth, the aggregate attribute may be calculated as the minimum of the bandwidth available on each constituent link. Also, if the property is delay, the aggregate property can be calculated as the sum of the corresponding delays over the constituent links, unless the delay is known to be a common type of distribution. In this case, the aggregate delay can be estimated as the square root of the sum of the squares of the average delays on each constituent link. Those skilled in the art will know techniques for computing aggregate attributes.

After calculating the aggregate attribute corresponding to route i, the example routing method 500 continues at block 66 . Block 66 determines if one path is better than the other. This can be done by comparing the aggregate attributes of the two communication paths according to the criteria set in the policy. The policy may be expressed using a standard information model, such as Internet Engineering Task Force (IETF) RFC 3060, entitled "Policy Core Information Model -- Version 1" (February 2001), and extensions thereof, including the IETF RFC 3460 for "Policy Core InformationModel (PCIM) Extension" (January 2003), which are incorporated herein by reference. As an example only, a user may a priori set a policy that requires the best reproduction fidelity. In this case, the properties of the two paths being compared may include characteristics such as delay, delay variability, dropped packets, and/or bandwidth. Where the user has set a policy requiring power minimization, the properties of the two paths to be compared may include, for example, an estimate of the total power required to transmit each packet over the two paths.

When block 66 determines that the path currently being considered is better than the path whose index is currently being stored in said index variable best, process control branch 67 is taken to block 68 where the index variable best is set to the current path and the index i is incremented by 1 in block 69. When block 66 determines that the path currently being considered is not better than the path whose index is stored in the index variable best, then the index variable best is not changed, and the process continues to block 69, which increments the index i by 1 to evaluate the next a path. Process control then continues at block 62 which checks to determine if the index i has exceeded the number of paths entered at block 60 as explained above. The method continues until the index i exceeds the number of paths entered at block 60 . When the method completes, the number of the best communication path will be stored in the index variable best.

It may be the case that the criterion (i.e. policy) used to select a path is not necessarily whether some aggregate attribute is better than the aggregate attribute of all other paths, but whether one aggregate attribute is equal to the aggregate attribute of another path Attributes. An important example of this situation is when it is desired to substantially match the delays of two or more paths. For example, as noted above, in a multi-channel communication environment involving the simultaneous coordination of activities on multiple communication paths, it is beneficial for the delays of each path to substantially match each other in order to ensure communication between the various electronic devices used to present the various components. proper synchronization between them. In this case, there is no need for the delay of a given path to be minimal.

Therefore, according to a preferred embodiment of the present invention, the exemplary routing decision method of FIG. 4 can be modified. For each component of a multi-channel message, a set of feasible communication paths is preferably determined, rather than just one path. A final path selection method then includes comparing the members of the corresponding set of feasible paths corresponding to each component. For example, a first component may have associated with it a set comprising feasible paths p ₁ with delay l ₁ , p ₂ with delay l ₂ , and p ₃ with delay l ₃ , while the second component may There is associated with it a set comprising feasible paths _p4 with delay _l4 , _{p5 with delay l5 ,} and _p6 with delay _l6 . It may be the case that l ₂ is substantially equal to l ₆ and l ₁ is substantially equal to l ₄ , both l ₁ and l ₄ being smaller than l ₂ . In this case, the path p ₁ is optionally selected for the first component and the path p ₄ is preferably selected for the second component. Techniques for accomplishing such comparisons are readily understood by those skilled in the art. Therefore, a detailed description of such an implementation will not be presented here.

According to another aspect of the invention, there are several optimizations that can be used with the methods described above with reference to Figures 2 and 3 and are related to path attributes. For example, when it is known that the user policy for path selection is to maximize fidelity and when a particular component of a multi-channel message requires B of bandwidth in order to reproduce that component with the required fidelity, the path enumeration and selection described above During methods 200, 300 (see Figures 2 and 3), when any link with bandwidth less than B is encountered, the communication path is immediately rejected. This can significantly reduce the number of communication paths to compare (eg, at block 53 of FIG. 4 ), and thus speed up the overall routing decision method.

In addition to policies, hints can be used to reduce the number of communication paths to compare. By way of example only, when it is known that a particular electronic device, such as a pager 4 (see FIG. 1 ), has low battery capacity, then any paths through that device should be within the path enumeration and selection methods 200, 300 (see FIGS. Not be considered. When there are multiple links between two electronic devices (for example, links 6 and 7 between devices 1 and 3 in Figure 1), if it is known that all properties associated with one link are better than those associated with the other link-related attributes, the path evaluation and selection method can also be simplified. For example, consider a serial cable link and a high-speed infrared link. Assuming that the infrared link is superior to the cable link in essentially every respect, the cable link can be excluded from any communication path evaluation.

For successive receptions of multi-channel messages using the same device configuration, the same communication path may be used when the multi-channel messages have substantially the same components. Optionally, the exemplary electronic device arrangement may be configurable to maintain a history of device assignments and/or communication paths corresponding to a given set of message components. In this way, when the configuration for receiving a new multi-channel message matches a past configuration, and the components of the multi-channel message are the same as those of a previously received message, the optimal communication path/path can be selected from this history list. Electronic device configuration, instead of using the method described above, thus significantly speeds up the entire routing decision method.

During normal operation of the exemplary device connection arrangement 100 shown in FIG. 1, one or more links and/or electronic devices may fail or be otherwise removed from the connection arrangement. Additionally, new devices may become active in the connection arrangement, for example, when a user powers on a particular device that has wireless connectivity to other devices and/or the Internet. A given set of communication routes for each component of a multi-channel message may or may not be affected by such spontaneous configuration changes. For example, a given route may become unavailable in the event of a device failure or removal. Similarly, with new equipment, a better route may become available.

According to one embodiment of the present invention, the first case is considered, i.e. the occurrence of a device and/or link failure or removal from a connection arrangement which preferably first determines that any Whether routing has been affected, and, if so, an alternate routing is provided for that component of the message. This can be facilitated by maintaining information derived during the path enumeration and characterization method described above with reference to FIG. 2 (eg, stored in a table in memory).

Some of the communication paths determined as a result of the path enumeration and characterization method may already be used to communicate other components of the multi-channel message. Additionally, one or more paths are assumed to be no longer available due to failure or removal of equipment. Of the paths still available, the path selection method shown in block 53 in Figure 4 (and described further with reference to Figure 5) is preferably repeated in order to select a best alternative communication path. An important difference here is that the initialization process performed in block 60 of Figure 5 that receives as input the set of paths need only consider those paths that are now available, rather than the entire set of paths that were available at setup time.

Considering the second case, where a device and/or communication link is added to a connection arrangement, the connection arrangement preferably first determines whether the currently selected set of communication paths is functioning properly. It may be the case that the original routing method of Fig. 5 still meets all the criteria for delivering the multi-channel message. If so, no changes to the connection arrangement are required. In some cases, however, adding new equipment and/or communication links provides a better route than the currently selected route. In such a case, the example selection method of FIG. 5 may be repeated with an added new communication path that becomes available due to the addition of the new device and/or link. In this way, the exemplary device assignment and routing method can be dynamically changed to take advantage of these new communication paths. It should be appreciated that the exemplary path selection method shown in FIG. 5 may be facilitated as described above by maintaining (eg, in memory) information derived during the path enumeration and characterization method of FIG. 2 .

According to a preferred embodiment of the present invention, a database is used to hold at least a portion of the information derived from the exemplary path enumeration method shown in FIG. 2 . Preferably, each allocated communication path whose aggregate properties do not satisfy satisfactorily the criteria for delivering the multi-channel message component to which it is allocated is marked. Thus, when performing the exemplary path selection method shown in FIG. 5, only marked communication paths need be considered when new paths become available.

According to another embodiment of the present invention, the routing decision method of the present invention may be fully or partially implemented in a circuit (not shown). The circuitry may include a controller 102 as shown in FIG. 1 , which may be configured to perform at least part of the methods of the invention described herein. The controller 102 may be implemented as a separate device (as shown in Figure 1 ) external to the electronic devices 1 to 5 in the connection arrangement 100 and operatively connected to the one or more devices. Alternatively, the controller 102 may be part of one, more or all of the devices 1-5.

The term controller as used herein is intended to include any processing device, such as one including a central processing unit (CPU) and/or other processing circuitry (eg, a microprocessor). Controllers and/or processing blocks may also be implemented as dedicated circuits in hardware. Furthermore, it should be understood that the term "controller" may refer to more than one controller device and that units associated with one controller device may be shared by other controller devices. Furthermore, circuitry for performing the methods of the present invention as described herein may be at least partially implemented in a semiconductor device, which may include at least one such circuitry, as will be understood by those skilled in the art.

It will be appreciated that, in accordance with the present invention, the exemplary connection arrangement is preferably configured such that routing is performed in each electronic device included in the connection arrangement. Alternatively, routing may be performed by a subset of the one or more devices, eg routing data traffic to or from the Internet on behalf of all other devices in the connection arrangement. The decision of which route or routes to select may be made in hardware, software, hardware, software, or other devices associated with the one or more electronic devices, or alternatively, a dedicated device (e.g., a gateway to the Internet, a router, etc.). or a combination of hardware and software. But because links between electronic devices are often point-to-point (eg, infrared), routing is preferably performed at each device as described above.

Although exemplary embodiments of the present invention have been described herein with reference to the accompanying drawings, it should be understood that the present invention is not limited to these precise embodiments, and that various other changes and modifications may be made therein by those skilled in the art without departing from scope of the appended claims.

Claims (22)

1. A method for presenting a multi-channel message originating from a data source in a connection arrangement comprising a plurality of electronic devices, wherein information is available on said plurality of electronic devices via a plurality of communication links between said electronic devices Exchanged between devices, at least one of said electronic devices may be configured to communicate with the data source, the multi-channel message includes a plurality of components, the method comprising the steps of: distributing each of at least a portion of the plurality of components in the multi-channel message to at least one electronic device for presentation to a user; for each assigned component, determining a possible communication path between the data source and at least one electronic device assigned to the corresponding component; selecting at least one possible communication path for each assigned component based at least in part on one or more selection criteria, each selected communication path representing a communication between the data source and at least one electronic device assigned to the corresponding component the optimal path for ; and Each assigned component of the multi-channel message is routed according to the selected communication path for presentation by the corresponding electronic device. 2. The method according to claim 1, wherein said step of determining possible communication paths comprises the steps of: designating one of the communication links as an input communication link for receiving the multi-channel message from the data source; designating one of the electronic devices as a destination device for presenting one of the components in the multi-channel message; evaluating whether a communication path exists between a first electronic device and a second electronic device, the first electronic device being connected to the incoming communication link; When a communication path exists between the first electronic device and the second electronic device, determining substantially all possible communication paths between the second electronic device and the destination device that do not include the first electronic device; and repeating said steps of evaluating whether a communication path exists and determining a possible communication path for each electronic device in the connection arrangement other than the first electronic device, wherein another of said electronic devices that has not been evaluated is substituted the second electronic device. 3. The method of claim 2, wherein said step of determining communication paths further comprises associating an indication with each of said possible communication paths. 4. The method of claim 3, wherein said indication associated with a given communication path represents at least one of: (i) each electronic device that constitutes the given communication path; and (ii) Each of at least one intermediate communication link making up the given communication path. 5. The method according to claim 2 , wherein said step of determining a communication path further comprises generating an output list that includes communication between each electronic device and said destination device that does not include said first electronic device. Basically all possible communication paths. 6. The method of claim 1, wherein said step of selecting a communication path for a distributed component comprises: For each allocated component in said multi-channel message, determining a delay associated with each possible communication path corresponding to the allocated component in the connection arrangement; and Communication paths are selected for the assigned components such that delays associated with each selected communication path substantially match each other. 7. The method according to claim 1, further comprising the step of storing, at least temporarily, information about possible communication paths between said data sources and electronic devices assigned to respective components in said multi-channel message. 8. The method of claim 1, wherein said step of selecting a communication path for an assigned component comprises, for a given allocated component in said multi-channel message: receiving a plurality of possible communication paths between said data source and at least one electronic device corresponding to the given assigned component; receiving at least one characteristic associated with the plurality of possible communication paths; determining a set of aggregate attributes corresponding to each of the plurality of possible communication paths; comparing aggregate attribute sets for the plurality of possible communication paths; and An optimal communication path for the given assigned component is determined based at least in part on the at least one characteristic associated with each of the plurality of possible communication paths. 9. The method of claim 8, wherein said aggregate attribute set corresponding to a given one of said plurality of possible communication paths includes Include at least one communication link related feature. 10. The method according to claim 9, wherein said characteristic associated with said at least one communication link comprises power of said at least one link, an estimate of link delay, a distribution of link delay, the at least one link At least one of an estimate of the bandwidth of the at least one link, and a ratio of the number of packets dropped on the at least one link to the number of packets sent on the at least one link. 11. The method of claim 1, wherein said data source comprises at least one of said plurality of electronic devices in said connection arrangement. 12. The method of claim 1, wherein said data source comprises the Internet. 13. The method of claim 1, wherein the selection criteria includes delay. 14. An apparatus for presenting a multi-channel message originating from a data source, the multi-channel message comprising a plurality of components, the apparatus comprising: at least one controller operable to: (i) assign each of at least a portion of the plurality of components in the multi-channel message to at least one electronic device for presentation to a user; (ii) for each an assigned component, determining a possible communication path between the data source and at least one electronic device assigned to the corresponding component; (iii) based at least in part on one or more selection criteria, for each assigned a component selects at least one possible communication path, each selected communication path representing an optimal path between the data source and at least one electronic device assigned to the corresponding component; and (iv) routing the Each assigned component in the multi-channel message for presentation of the assigned component by the corresponding electronic device. 15. The apparatus according to claim 14, wherein said controller is further operable to: (v) designate one of said communication links as an incoming communication link for receiving said multi-channel message from said data source; (vi ) designating one of the electronic devices as a destination device for presenting one of the components in the multi-channel message; (vii) evaluating whether a communication path exists between the first electronic device and the second electronic device, the first An electronic device is connected to the input communication link; (viii) when there is a communication path between the first electronic device and the second electronic device, it is determined that the first electronic device and the destination device do not include the first electronic device. substantially all possible communication paths of the electronic devices; and (ix) repeating said steps of evaluating whether a communication path exists and determining a possible communication path for each electronic device in the connection arrangement other than the first electronic device, wherein the second electronic device is replaced by another one of the electronic devices that has not yet been evaluated. 16. The apparatus of claim 15, wherein said controller is further operable to associate an indication with each of said possible communication paths. 17. The apparatus of claim 15, wherein said controller is further operable to generate an output list including basic information between each electronic device and said destination device excluding said first electronic device. all possible communication paths. 18. The apparatus according to claim 14 , wherein said controller is further operable to: (v) determine a delay associated with each possible communication path in the connection arrangement corresponding to the assigned component; and (vi) Communication paths are selected for the assigned components such that delays associated with each selected communication path substantially match each other. 19. The apparatus of claim 14, wherein, for a given assigned component in the multi-channel message, the controller is further operable to: (v) receive the data source and the corresponding (vi) receiving at least one characteristic associated with the plurality of possible communication paths; (vii) determining a plurality of possible communication paths corresponding to the plurality of possible communication paths; (viii) comparing the aggregate attribute sets for the plurality of possible communication paths; and (ix) based at least in part on correlating each of the plurality of possible communication paths The at least one characteristic of the determined optimal communication path for the given assigned component. 20. The apparatus according to claim 19, wherein said aggregate attribute set corresponding to a given one of said plurality of possible communication paths comprises Include at least one communication link related feature. 21. The apparatus of claim 14, wherein the apparatus is at least partially implemented in a semiconductor device. 22. An article of manufacture for presenting a multi-channel message originating from a data source, the multi-channel message comprising a plurality of components, the article of manufacture comprising a machine-readable medium containing one or more programs that when executed When performing the following steps: distributing each of at least a portion of the plurality of components in the multi-channel message to at least one electronic device for presentation to a user; for each assigned component, determining a possible communication path between the data source and at least one electronic device assigned to the corresponding component; selecting at least one possible communication path for each assigned component based at least in part on one or more selection criteria, each selected communication path representing a communication between the data source and at least one electronic device assigned to the corresponding component the optimal path for ; and Each assigned component of the multi-channel message is routed according to the selected communication path for presentation by the corresponding electronic device.

Images