Automated Secure Pairing for Wireless Devices
Claim Score by NHIP
Abstract
Systems, methods, and/or techniques (“tools”) are described herein that relate to automated secure pairing for devices, and that relate to parallel downloads of content using devices. The tools for pairing the devices may perform authentication protocols that are based on addresses and on keys. The address-based authentication protocol may operate on address book entries maintained by the devices. The key-based authentication protocol may operate using a key exchange between the devices.
Term
0.5 yearsto projected expiry
Projected expiry 15 March 2027, counted from filing; an application has no term until it is granted.
- Priority
- Filed
- Published
- Today
- Projected expiry
20 claims: 3 independent, 17 dependent
- 1A method for pairing at least two devices, the method comprising:performing, via a direct connection between the at least two devices, a first authentication protocol including: receiving a pairing request that includes an identifier;and comparing the identifier to entries previously stored in an address book;performing, via an indirect connection between the at least two devices, a second authentication protocol including: generating a randomly generated nonce using a security key;encrypting the randomly generated nonce using the security key;sending a challenge that includes the encrypted randomly generated nonce;receiving a challenge response that includes the randomly generated nonce that is decrypted;and comparing the randomly generated nonce that is decrypted and received in the challenge response to the randomly generated nonce that is generated;and determining to accept the pairing request based in part on whether the identifier coincides with at least one of the entries stored in the address book and the randomly generated nonce that is decrypted matches the randomly generated nonce that is generated based at least in part on the comparing.
- 12A computer-readable storage media comprising machine-readable instructions that, when executed by the machine, cause the machine to:receive a pairing request containing an identifier of an initiating device over the direct communication link between the initiating device and a target device;perform a first authentication protocol via the direct communication link, the first authentication protocol comprising verifying that the identifier coincides with at least one previously stored entry in an address book of the target device;and perform a second authentication protocol via an indirect communication link between the initiating device and the target device, the second authentication protocol to: generate a first nonce and a second nonce;encrypt the first nonce using an authentication key;send a challenge to the initiating device, the challenge including the first nonce in an encrypted form and the second nonce in a decrypted form;and receive a challenge response containing the first nonce in a decrypted form and the second nonce in an encrypted form.
- 20Broadest claimClaim Score 64, broad(NHIP)A computer-readable storage media comprising machine-readable instructions that, when executed by the machine, cause the machine to:receive a pairing request that includes an identifier via a direct connection between the at least two devices;compare the identifier to previously stored entries in an address book;and generate a randomly generated nonce using a security key;encrypt the randomly generated nonce using the security key;send, via an indirect connection between the at least two devices, a challenge that includes the encrypted randomly generated nonce;receive, via the indirect connection, a challenge response that includes the randomly generated nonce that is decrypted;compare the randomly generated nonce that is decrypted to the randomly generated nonce that is generated;and determine to accept the pairing request if the identifier coincides with at least one of the previously stored entries in the address book and the randomly generated nonce that is decrypted matches the randomly generated nonce that is generated.
Independent claims3
213 paragraphs in 7 sections, as filed
CROSS REFERENCE TO RELATED APPLICATIONS
0001This application is a continuation of prior pending U.S. patent application Ser. No. 11/555,093, filed Oct. 31, 2006, which is herein incorporated by reference in its entirety. Any disclaimer that may have occurred during the prosecution of the above-referenced application(s) is hereby expressly rescinded, and reconsideration of all relevant art is respectfully requested.
BACKGROUND
0002As wireless devices become more prevalent, users continually demand more functions and capabilities from these devices. More recently, wireless devices are increasingly available with broadband internet connectivity. This availability opens new opportunities for users of such wireless devices. For example, in emerging markets around the world, users may not have access to personal computers with broadband internet connections, or may not wish to pay for general packet radio service (GPRS) connections. Instead, these users may opt to receive digital content via, for example, Bluetooth connections established between phones.
0003To pair two phones using conventional Bluetooth approaches, the users would typically put their respective phones into a discovery mode and locate the phones in proximity to one another. The users would then exchange pass codes, and enter the pass codes into the phones.
0004While adequate for their intended uses, these conventional approaches suffer drawbacks, chiefly the manual steps taken by the respective users in obtaining and entering the pass codes. Accordingly, automated approaches have been proposed, in which the devices automatically pair themselves with any devices in close enough proximity. While an improvement over manual approaches, these automated approaches may expose users and devices to viruses and other forms of malware. More specifically, these automated approaches may not authenticate the devices with which they are pairing. In this sense, the connections between the paired devices are not secured, and any malicious content stored on one paired device may readily migrate to another paired device over this unsecured connection.
SUMMARY
0005Systems, methods, and/or techniques (“tools”) are described herein that relate to automated secure pairing for devices, and that relate to parallel downloads of content using devices. The tools for pairing the devices may perform authentication protocols that are based on addresses and on keys. The address-based authentication protocol may operate on address book entries maintained by the devices. The key-based authentication protocol may operate using a key exchange between the devices.
0006This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. The term “tools,” for instance, may refer to system(s), method(s), computer-readable or machine-readable instructions, and/or technique(s) as permitted by the context above and throughout the document.
BRIEF DESCRIPTIONS OF THE DRAWINGS
0007Tools related to performing automated secure pairing for wireless devices are described in connection with the following drawing figures. The same numbers are used throughout the disclosure and figures to reference like components and features. The first digit in a reference number indicates the drawing figure in which that reference number is introduced.
0008<figref idref="DRAWINGS">FIG. 1</figref> is a combined block and flow diagram of an operating environment suitable for implementing automated secure pairing for wireless devices.
0009<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram illustrating further details of address books or other contact lists suitable for implementing automated secure pairing for wireless devices.
0010<figref idref="DRAWINGS">FIG. 3</figref> is a combined block and flow diagram illustrating direct and indirect communication links and authentication components suitable for securely pairing the wireless devices.
0011<figref idref="DRAWINGS">FIG. 4</figref> is a flow diagram, illustrating a process for performing address-book based authentication between an initiating device and a target device.
0012<figref idref="DRAWINGS">FIG. 5</figref> is a flow diagram, illustrating further details of the authentication process shown in <figref idref="DRAWINGS">FIG. 4</figref>.
0013<figref idref="DRAWINGS">FIG. 6</figref> is a flow diagram, illustrating a process for performing key-based authentication between the initiating device and the target device.
0014<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram of an operating environment including a device pairing architecture and one or more related applications.
0015<figref idref="DRAWINGS">FIG. 8</figref> is a combined block and data flow diagram illustrating an operating environment for performing parallel downloads among a plurality of paired devices.
0016<figref idref="DRAWINGS">FIG. 9</figref> is a combined block and data flow diagram illustrating components and data flows related to a first device, when performing parallel downloads distributed among one or more other devices that are paired with the first device.
0017<figref idref="DRAWINGS">FIG. 10</figref> is a combined process and data flow diagram, illustrating a process for forming a collaborative network of two or more wireless mobile devices for performing parallel downloads among the devices.
0018<figref idref="DRAWINGS">FIG. 11</figref> is a combined process and data flow diagram, illustrating a process for dividing and distributing work among members of the collaborative network.
0019<figref idref="DRAWINGS">FIG. 12</figref> is a combined process and data flow diagram, illustrating a process for a learning phase algorithm performed in connection with the parallel downloads.
0020<figref idref="DRAWINGS">FIG. 13</figref> is a combined process and data flow diagram, illustrating a process for a one-time assignment algorithm performed in connection with the parallel downloads.
0021<figref idref="DRAWINGS">FIG. 14</figref> is a combined process and data flow diagram, illustrating a process for a periodic assignment algorithm that may be performed as part of the parallel downloads.
0022<figref idref="DRAWINGS">FIG. 15</figref> is a combined process and data flow diagram, illustrating a process for a failure handling mechanism.
DETAILED DESCRIPTION
Overview
0023The following document describes tools capable of performing and/or supporting many techniques and processes. The following discussion describes exemplary ways in which the tools provide for automated secure pairing for wireless devices. This discussion also describes other techniques and/or processes that may be performed by the tools.
0024<figref idref="DRAWINGS">FIG. 1</figref> illustrates an operating environment <b>100</b> suitable for performing automated secure pairing for wireless devices. The operating environment <b>100</b> may include one or more wireless devices <b>102</b>. These devices <b>102</b> may be cellular telephones, smart phones, Personal Digital Assistants (PDAs), or the like. It is understood that implementations of the operating environment may include any number of different wireless devices, although <figref idref="DRAWINGS">FIG. 1</figref> shows two wireless devices <b>102</b>A and <b>102</b>N only for convenience of illustration. Although <figref idref="DRAWINGS">FIG. 1</figref> denotes these devices with similar reference numbers, it is noted that the two wireless devices <b>102</b>A and <b>102</b>N may be different types, makes, models, or brands of devices.
0025The wireless devices <b>102</b> are associated with respective users <b>104</b>. For convenience of illustration, <figref idref="DRAWINGS">FIG. 1</figref> shows two users at <b>104</b>A and <b>104</b>N, but the operating environment may support any number of users.
0026In general, the wireless devices <b>102</b> may be computer-based systems that include one or more processor(s) <b>106</b>. <figref idref="DRAWINGS">FIG. 1</figref> shows two processors <b>106</b>A and <b>106</b>N, associated respectively with the wireless devices <b>102</b>A and <b>102</b>N.
0027The wireless devices may include one or more instances of computer-readable storage media <b>108</b>, which are coupled to communicate with the processors. The computer-readable media may contain instructions that, when executed by the processor, perform any of the tools or related functions as described herein. The processor may be configured to access and/or execute the instructions embedded or encoded onto the computer-readable media. The processor may also be categorized or characterized as having a given architecture. The processors <b>106</b>A and <b>106</b>N may be different types of processors, depending on the architecture of the devices <b>102</b>.
0028Computer-readable media includes, at least, two types of computer-readable media, namely computer storage media and communications media.
0029Computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, computer storage devices such as RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information for access by a computing device.
0030In contrast, communication media may embody computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave, or other transmission mechanism. As defined herein, computer storage media does not include communication media.
0031The computer-readable media <b>108</b> may include one or more instances of automatic secure pairing components <b>110</b>. <figref idref="DRAWINGS">FIG. 1</figref> shows respective automatic secure pairing components <b>110</b>A and <b>110</b>N, associated respectively with the devices <b>102</b>A and <b>102</b>N. The automatic secure pairing components may be implemented as one or more software modules that, when loaded into the processors <b>106</b> and executed, cause the devices <b>102</b> to perform the various functions described herein.
0032The wireless devices may be associated with respective unique identifiers <b>112</b>N, by which communications may be addressed to the wireless devices. For example, if the wireless devices include telephone capabilities, the unique identifier may be a telephone number. Other examples of unique identifiers may include e-mail addresses, user names or screen names for instant messaging (IM) applications, electronic serial numbers (ESNs), or the like. In any event, the computer-readable media may store representations of the unique identifiers associated with the wireless devices, denoted respectively at <b>112</b>A and <b>112</b>N.
0033The computer-readable media <b>108</b> may also include one or more instances of data structures that store contents of an address book or other similar list of contacts. <figref idref="DRAWINGS">FIG. 1</figref> denotes these data structures as address books <b>114</b>, and shows address books <b>114</b>A and <b>114</b>N associated respectively with wireless devices <b>102</b>A and <b>102</b>N. The term “address book” is chosen only for ease of description, but not to limit possible implementations of the operating environment <b>100</b>. Generally, these data structures store one or more addresses or other unique identifiers corresponding to the devices <b>102</b>.
0034As an example, assume that the wireless devices <b>102</b> have telephone capabilities, and that the users <b>104</b>A and <b>104</b>N have exchanged unique identifiers <b>112</b>, e.g., telephone numbers. In this case, the address book <b>114</b>A may include the telephone number of the device <b>102</b>N, and the address book <b>114</b>N may include the telephone number of the device <b>102</b>A. In this example, the users may be assumed to know and trust each other, at least to the extent that they are willing to exchange personal information, such as phone numbers.
0035The wireless devices may communicate with one another via one or more direct communication links <b>116</b> and one or more indirect communication links <b>118</b>. The direct communication links <b>116</b> enable the wireless devices to communicate with one another in peer-to-peer (P2P) fashion, without the communications passing through an intermediate network. Examples of technologies suitable for implementing the direct communication links include, but are not limited to, Bluetooth and WiFi technologies.
0036Turning to the indirect communication links <b>118</b>, these links enable the wireless devices to communicate with one another through some intermediate network or service provided and/or maintained by a third party. <figref idref="DRAWINGS">FIG. 1</figref> denotes such a network or service generally at communication service <b>120</b>. Thus, communications from one wireless device to another passes through the communication service. For convenience only, <figref idref="DRAWINGS">FIG. 1</figref> denotes communications between the wireless device <b>102</b>A and the communication service at <b>118</b>A, and communications between the communication service and the wireless device <b>102</b>N communication service at <b>118</b>N. For ease of discussion only, but not limitation, examples of the indirect communication links may include links that enable telephones to communicate with one another, links that enable devices to communicate using the Short Message Service (SMS), e-mail links, or the like.
0037Having described the operating environment <b>100</b> in <figref idref="DRAWINGS">FIG. 1</figref>, the discussion now turns to a more detailed description of the address books and other related data structures, now presented with <figref idref="DRAWINGS">FIG. 2</figref>.
0038<figref idref="DRAWINGS">FIG. 2</figref> illustrates further details of address books or other contact lists suitable for implementing automated secure pairing for wireless devices. Elements previously described in <figref idref="DRAWINGS">FIG. 1</figref> are denoted by the same reference numbers in <figref idref="DRAWINGS">FIG. 2</figref> for convenience only.
0039Turning to the address books <b>114</b> in more detail, the address books may contain one or more entries <b>202</b> and <b>204</b>. For convenience only, <figref idref="DRAWINGS">FIG. 2</figref> shows the address book <b>114</b>A having two entries <b>202</b>A and <b>202</b>M, and the address book <b>114</b>N having two entries <b>204</b>A and <b>204</b>P, but it is noted that the address books may contain any number of entries. From the perspective of a given address book <b>114</b>, respective ones of the entries may correspond to other devices <b>102</b> or other users <b>104</b>. For example, turning to the address book <b>114</b>A in particular, one of the entries <b>202</b> may contain contact information for the device <b>102</b>N, and/or the user <b>104</b>N.
0040Turning to the entries <b>202</b> and <b>204</b> in more detail, the entries may respectively contain one or more fields for storing contact details related to another device <b>102</b> and/or another user <b>104</b>. These fields are denoted generally in <figref idref="DRAWINGS">FIG. 2</figref> as contact details fields <b>206</b> and <b>208</b>. More specifically, <figref idref="DRAWINGS">FIG. 2</figref> shows the entry <b>202</b>A associated with the contact details field <b>206</b>A, and the entry <b>202</b>M associated with the contact details field <b>206</b>M. Additionally, <figref idref="DRAWINGS">FIG. 2</figref> shows the entry <b>204</b>A associated with the contact details field <b>208</b>A, and the entry <b>204</b>P associated with the contact details field <b>208</b>P. Generally, the contact details fields <b>206</b> and <b>208</b> may contain any unique identifiers suitable for addressing the devices <b>102</b> and/or the users <b>104</b>. Examples of such unique identifiers are shown at <b>112</b> in <figref idref="DRAWINGS">FIGS. 1 and 2</figref>, and may include e-mail addresses, user names or screen names for instant messaging (IM) applications, electronic serial numbers (ESNs), or the like. Additional examples of these unique identifiers may include telephone numbers, or any other identifier related to a network that offers addressable security.
0041In a non-limiting example as shown in <figref idref="DRAWINGS">FIG. 2</figref>, the entry <b>202</b>A in the address book <b>114</b>A includes a contact details field (e.g., <b>206</b>A) that contains at least the unique identifier <b>112</b>N associated with the device <b>102</b>N, as indicated by the dashed line <b>210</b>. Additionally, the entry <b>204</b>A in the address book <b>114</b>N includes a contact details field (e.g., <b>208</b>A) that contains at least the unique identifier <b>112</b>A associated with the device <b>102</b>A, as indicated by the dashed line <b>212</b>. The roles placed by these address book entries in securely pairing the wireless devices <b>102</b> are described herein.
0042Having described the address books <b>114</b>, the discussion now turns to a description of different authentication schemes for automated secure pairing of wireless devices, now presented with <figref idref="DRAWINGS">FIG. 3</figref>.
0043<figref idref="DRAWINGS">FIG. 3</figref> illustrates a combined block and flow block diagram <b>300</b>, showing communication links and authentication components suitable for securely pairing the wireless devices. As shown in <figref idref="DRAWINGS">FIG. 3</figref>, at least the devices <b>102</b>A and <b>102</b>N are coupled to communicate via the direct communication link <b>118</b> and via the indirect communication link <b>118</b>. More specifically, <figref idref="DRAWINGS">FIG. 3</figref> shows the respective automatic secure pairing components <b>110</b>A and <b>110</b>N as engaged in the pairing operation.
0044It is noted that the term “pairing” is used herein only for convenience, but not for limitation. It is specifically noted that two or more devices <b>102</b> may be securely coupled to communicate with one another using the tools and techniques described herein. Thus, <figref idref="DRAWINGS">FIGS. 1-3</figref> shows two devices <b>102</b> only for ease of illustration and description.
0045Turning to the direct communication link <b>116</b>, the device <b>102</b>A may include a component <b>302</b>A for authenticating one or more other devices <b>102</b>N based on entries in address books or other similar data structures as contained within the device <b>102</b>A. Similarly, the device <b>102</b>N may include a component <b>302</b>N for authenticating one or more other devices <b>102</b>A based on entries in address books or other similar data structures as contained within the device <b>102</b>N. For convenience only, these address book authentication components <b>302</b> are shown as part of the automatic secure pairing component <b>110</b>, but it is noted that the components <b>302</b> may be implemented separately from the components <b>110</b>.
0046Turning to the indirect communication link <b>118</b>, the device <b>102</b>A may include a component <b>304</b>A for authenticating one or more other devices <b>102</b>N using keys exchanged with the device <b>102</b>A. Similarly, the device <b>102</b>N may include a component <b>302</b>N for authenticating one or more other devices <b>102</b>A using keys exchanged with the device <b>102</b>N. For convenience only, these key-based authentication components <b>304</b> are shown as part of the automatic secure pairing component <b>110</b>, but it is noted that the components <b>304</b> may be implemented separately from the components <b>110</b>.
0047Having introduced the address book-based authentication components <b>302</b> and the key-based authentication components <b>304</b>, the discussion now turns to a more detailed description of process and data flows related to these components, presented with <figref idref="DRAWINGS">FIGS. 4-6</figref>. More specifically, <figref idref="DRAWINGS">FIGS. 4-5</figref> pertain to process and data flows that may be performed by the address book-based authentication components <b>302</b>, while <figref idref="DRAWINGS">FIG. 7</figref> pertains to process and data flows that may be performed by the key-based authentication components <b>304</b>.
0048<figref idref="DRAWINGS">FIG. 4</figref> illustrates process and data flows <b>400</b> for performing address-book based authentication between the devices <b>102</b>. Put differently, <figref idref="DRAWINGS">FIG. 4</figref> illustrates an authentication protocol that is based on address book entries. The protocol shown in <figref idref="DRAWINGS">FIG. 4</figref> may be performed by components such as the address book-based authentication components <b>302</b>A and <b>302</b>N and devices <b>102</b>A and <b>102</b>N, as shown in <figref idref="DRAWINGS">FIG. 3</figref>. However, it is noted that aspects of the process flow <b>400</b> and related protocols may be performed with other components without departing from the scope and spirit of the description herein.
0049For convenience only, <figref idref="DRAWINGS">FIG. 4</figref> shows the device <b>102</b>A as initiating a request to couple or pair with the device <b>102</b>N. Thus, <figref idref="DRAWINGS">FIG. 4</figref> shows the device <b>102</b>A as an initiating device, and the device <b>102</b>N as a target device. However, it is noted that the authentication protocols shown herein may be mutual in nature, in that the device <b>102</b>A may authenticate the device <b>102</b>N, and the device <b>102</b>N may authenticate the device <b>102</b>A. Additionally, these authentications may proceed sequentially, or simultaneously. Finally, the data flows represented in dashed lines in <figref idref="DRAWINGS">FIG. 4</figref> may travel via the direct communication link <b>116</b> described above.
0050For convenience only, the blocks as shown in <figref idref="DRAWINGS">FIG. 4</figref> are arranged in two columns, generally corresponding to the initiating device <b>102</b>A and the target device <b>102</b>N. This arrangement is presented only to indicate processing that may be performed by the initiating device <b>102</b>A and the target device <b>102</b>N for the purposes of this description, but not to limit possible implementations of this description.
0051Turning to the process flow in more detail, block <b>402</b> represents sending a pairing request to the target device. In the example shown in <figref idref="DRAWINGS">FIG. 4</figref>, the initiating device <b>102</b>A may send a pairing request <b>404</b> to the target device <b>102</b>N. Block <b>402</b> may be performed in response to, for example, the initiating device <b>102</b>A detecting the target device <b>102</b>N within a certain proximity.
0052Block <b>406</b> represents receiving the pairing request. In the example shown in <figref idref="DRAWINGS">FIG. 4</figref>, the target device <b>102</b>N may receive the pairing request <b>404</b> from the initiating device <b>102</b>A.
0053Block <b>408</b> represents sending a challenge to the initiating device in response to receiving the pairing request. In the example shown in <figref idref="DRAWINGS">FIG. 4</figref>, the target device <b>102</b>N may send a challenge <b>410</b> to the initiating device <b>102</b>A in response to the pairing request. The challenge <b>410</b> enables the target device <b>102</b>N to authenticate the initiating device <b>102</b>A.
0054Block <b>412</b> represents the initiating device <b>102</b>A receiving the challenge <b>410</b> sent by the target device <b>102</b>N in block <b>408</b>. By responding appropriately to the challenge, the initiating device <b>102</b>A may authenticate itself to the target device <b>102</b>N.
0055Block <b>414</b> represents the initiating device sending a response <b>416</b> to the challenge. For example, the initiating device <b>102</b>A, may perform block <b>414</b> in response to receiving the challenge in block <b>412</b>.
0056Recall that the address book-based authentication scheme shown in <figref idref="DRAWINGS">FIG. 4</figref> exchanges data between the devices <b>102</b>A and <b>102</b>N via the direct communication link <b>116</b>. In the authentication scheme shown in <figref idref="DRAWINGS">FIG. 4</figref>, the initiating device <b>102</b>A may receive a secret key <b>416</b> from the target device <b>102</b>N via the indirect communication link <b>118</b>. More specifically, the initiating device <b>102</b>A may receive the secret key <b>416</b> as a result of successfully participating in a key-based authentication process between the initiating device <b>102</b>A and the target device <b>102</b>N, carried out over the indirect communication link <b>118</b>. A non-limiting example of such a key-based authentication process is shown in <figref idref="DRAWINGS">FIG. 6</figref> and described in connection therewith.
0057In any event, block <b>414</b> may include using the secret key received from the target device <b>102</b>N to process the challenge, and to formulate a response <b>418</b> thereto. If the key-based authentication process between the initiating device <b>102</b>A and the target device <b>102</b>N (e.g., as shown in <figref idref="DRAWINGS">FIG. 6</figref>) is not successful, then the initiating device <b>102</b>A does not receive the secret key, and cannot respond appropriately to the challenge <b>410</b> issued by the target device <b>102</b>N as part of the address book-based authentication protocol shown in <figref idref="DRAWINGS">FIG. 4</figref>.
0058Block <b>418</b> represents receiving the response <b>416</b> to the challenge <b>410</b>. Block <b>418</b> may represent the target device <b>102</b>N receiving the response <b>416</b>. Having received the response <b>416</b> to the challenge, the target device <b>102</b>N may perform decision block <b>422</b>, which represents evaluating whether the received response is valid. In some implementations, block <b>422</b> may include determining whether a response to the challenge was received at all, or was received within some expected timeframe for response. In other implementations, where some response <b>418</b> is received, block <b>422</b> may include evaluating the challenge as received, to assess its validity.
0059In any event, if the target device <b>102</b>N receives no response to the challenge, or if the target device <b>102</b>N receives a response that is invalid, the process flow <b>400</b> may take No branch <b>424</b> to block <b>426</b>, which represents denying the pairing request <b>404</b>. In some instances, the target device <b>102</b>N may communicate the denial of this pairing request to the initiating device <b>102</b>A. <figref idref="DRAWINGS">FIG. 4</figref> denotes this denial at <b>428</b>. In other instances, the target device <b>102</b>N may deny the pairing request without communicating this denial to the initiating device <b>102</b>A.
0060Returning to the decision block <b>422</b>, if the target device <b>102</b>N has received a valid or expected response <b>418</b> to the challenge <b>410</b>, then the process flow <b>400</b> may take Yes branch <b>430</b> to block <b>432</b>, which represents granting the pairing request <b>404</b>. In this case, the target device <b>102</b>N may communicate approval of the pairing request to the initiating device <b>102</b>A, as denoted at <b>434</b>.
0061At the initiating device <b>102</b>A, block <b>436</b> represents receiving a response to the pairing request. As described above, this response may take the form of an approval (e.g., <b>434</b>) or a denial (e.g., <b>428</b>). Recall that the denial may be considered optional in nature.
0062Having described the process flow <b>400</b> for performing address book-based authentication in <figref idref="DRAWINGS">FIG. 4</figref>, the discussion now turns to a more detailed description of the address book-based authentication protocol, now presented with <figref idref="DRAWINGS">FIG. 5</figref>.
0063<figref idref="DRAWINGS">FIG. 5</figref> illustrates further details of the address book-based authentication process shown in <figref idref="DRAWINGS">FIG. 4</figref>, represented generally as process and data flows <b>500</b>. The processing blocks as shown in <figref idref="DRAWINGS">FIG. 5</figref> are arranged similarly to <figref idref="DRAWINGS">FIG. 4</figref>, once again for convenience only in describing a possible process flow between the initiating device <b>102</b>A and the target device <b>102</b>N.
0064Block <b>502</b> represents hashing a unique identifier assigned to or associated with the initiating device <b>102</b>A. Examples of the unique identifier are shown and described above at <b>112</b>. Generally, the unique identifier may represent any identifier by which communications may be addressed to the initiating device <b>102</b>A, for example, communications originating from the target device <b>102</b>N. An example of the unique identifier may be a telephone number assigned to the initiating device <b>102</b>A.
0065Block <b>502</b> may use any suitable one-way hash function, such that it is very difficult to calculate the unique identifier, given the hashed unique identifier. The unique identifier may be considered private or sensitive information that users may not want exposed openly to unauthorized third parties. A one-way hash function enables execution of the protocol shown in <figref idref="DRAWINGS">FIGS. 4 and 5</figref> without exchanging the actual identifiers in the clear, and thus may avoid compromising the identifiers.
0066Block <b>504</b> represents sending the hashed identifier, denoted at <b>506</b>, to the target device <b>102</b>N. Referring briefly back to <figref idref="DRAWINGS">FIG. 4</figref>, the pairing request <b>404</b> may include the hashed identifier <b>506</b>. As shown in <figref idref="DRAWINGS">FIG. 5</figref>, the initiating device <b>102</b>A may send the hashed identifier to the target device <b>102</b>N, with which the initiating device <b>102</b>A wishes to pair.
0067At the target device <b>102</b>N, block <b>508</b> represents receiving the hashed identifier <b>506</b>. Having received the hashed identifier, the target device <b>102</b>N may determine whether it should grant the pairing request from the initiating device <b>102</b>A.
0068Block <b>508</b> represents searching an address book or other similar data structure maintained by the target device <b>102</b>N. The target device may perform block <b>508</b> in response to receiving the hashed identifier <b>506</b>. Examples of the address book are shown in <figref idref="DRAWINGS">FIGS. 1 and 2</figref> at <b>114</b>. The target device <b>102</b>N may compare the incoming hashed identifier to contact details stored in, for example, the address book <b>114</b>N. To facilitate this comparison, the target device may compute hashes of all contact details stored in its address book, using the same hash function employed by the initiating device <b>102</b>A. In this manner, the target device <b>102</b>N can determine whether its address book contains an entry for the initiating device <b>102</b>A.
0069Block <b>510</b> represents determining whether the search performed in block <b>508</b> results in a match between the incoming hashed identifier and any entries in the address book of the target device <b>102</b>N. If not, then the process flow <b>500</b> takes No branch <b>512</b> to block <b>426</b>, which denies the pairing request.
0070In this scenario, the target device <b>102</b>N has determined that its address book contains no entry corresponding to the initiating device <b>102</b>A. This may indicate that a user (e.g., <b>102</b>N) of the target device <b>102</b>N has not entered contact information associated with a user (e.g., <b>102</b>A) of the target device <b>102</b>A. Therefore, the user <b>102</b>N may not know or trust the user <b>102</b>A well enough to exchange telephone numbers, for example. On that basis, the target device <b>102</b>N may reject or deny the pairing request, as denoted at <b>428</b>.
0071Returning to block <b>510</b>, if the target device <b>102</b>N finds a match in its address book for the incoming hashed identifier, then the process flow may take Yes branch <b>514</b> to block <b>516</b>. In this scenario, the users <b>102</b>A and <b>102</b>N have exchanged unique identifiers, such as telephone numbers, thereby indicating that at least some degree of familiarity or trust may exist between the two users.
0072Block <b>516</b> represents determining whether the target device <b>102</b>N has authenticated the initiating device <b>102</b>A under, for example, a key-based authentication scheme performed via the indirect communication link <b>118</b>. An example of such a key-based authentication scheme is described in <figref idref="DRAWINGS">FIG. 6</figref>. In but one possible example, the initiating device <b>102</b>A and the target device <b>102</b>N may exchange secret keys over the indirect communication link <b>118</b>.
0073As described further below in connection with <figref idref="DRAWINGS">FIG. 6</figref>, this key exchange may prevent an imposter, who may be impersonating a legitimate user of the initiating device <b>102</b>A, from pairing with the target device <b>102</b>N. For example, the imposter may have found an identifier belonging to the initiating device <b>102</b>A, and may wish to use that identifier to attempt to pair with the target device <b>102</b>N. If the initiating device <b>102</b>A and the target device <b>102</b>N used only the address book-based authentication protocol, this imposter may successfully pair with and compromise the target device <b>102</b>N.
0074If the target device <b>102</b>N has not yet authenticated the initiating device <b>102</b>A, then the process flow <b>500</b> may take No branch <b>518</b> to decision block <b>520</b>. The process flow <b>500</b> may include setting a timeout period applicable to authenticating the initiating device <b>102</b>A over, for example, the indirect communication link <b>118</b>.
0075Block <b>520</b> evaluates whether the timeout period has expired. If not, then the process flow <b>500</b> may take No branch <b>522</b>, and return to decision block <b>516</b>. The process flow <b>500</b> may loop between blocks <b>516</b> and <b>520</b>, until, for example, the timeout period expires without the target device <b>102</b>N authenticating the initiating device <b>102</b>A. In this case, the process flow <b>500</b> may take Yes branch <b>524</b> from block <b>520</b> to block <b>426</b>, which denies the pairing request.
0076Returning to block <b>516</b>, if the target device <b>102</b>N does authenticate the initiating device <b>102</b>A before the timeout period expires, then the process flow <b>500</b> may take Yes branch <b>526</b> to block <b>432</b>, which represents granting the pairing request. In this case, the target device <b>102</b>N may communicate approval <b>434</b> of the pairing request to the initiating device <b>102</b>A.
0077If, for example, both the initiating device <b>102</b>A and the target device <b>102</b>N mutually authenticate each other, under both the address book-based authentication protocol and the key-based authentication protocol, then the two devices <b>102</b> may be paired with one another.
0078Returning to the initiating device <b>102</b>A, after it sends the hashed identifier in block <b>504</b>, it may await a response from the target device <b>102</b>N, as represented in block <b>528</b>. When the initiating device <b>102</b>A receives a response from the target device <b>102</b>N, the process flow <b>500</b> may move to block <b>530</b>. If the response is affirmative, the devices <b>102</b> may be paired. If no response is received, or if the response is negative, the devices <b>102</b> are not paired.
0079Having described the address book-based authentication protocols with <figref idref="DRAWINGS">FIGS. 4 and 5</figref>, the discussion now proceeds to a description of a key-based authentication protocol, now presented with <figref idref="DRAWINGS">FIG. 6</figref>.
0080<figref idref="DRAWINGS">FIG. 6</figref> illustrates process and data flows <b>600</b> for performing key-based authentication between the initiating device <b>102</b>A and the target device <b>102</b>N. The devices <b>102</b>A and <b>102</b>N may include respective key-based authentication components <b>304</b>A and <b>304</b>N that perform aspects of the process and data flows <b>600</b> shown in <figref idref="DRAWINGS">FIG. 6</figref>. As with <figref idref="DRAWINGS">FIGS. 4 and 5</figref> above, <figref idref="DRAWINGS">FIG. 6</figref> arranges the processing blocks in columns corresponding to the devices <b>102</b>A and <b>102</b>N, for convenience only. Data flows between the devices <b>102</b>A and <b>102</b>N are again shown by dashed lines, and these data flows may travel along the indirect communication link <b>118</b>.
0081Block <b>602</b> represents sending an authentication request <b>604</b>. Block <b>602</b> may include sending a key-based authentication request from the initiating device <b>102</b>A to the target device <b>102</b>N.
0082Block <b>606</b> represents receiving the authentication request <b>604</b>, for example, by the target device <b>102</b>N. In response to receiving the authentication request, the target device <b>102</b>N and the initiating device <b>102</b>A may agree on a secret key <b>608</b>. The actions taken by the initiating device <b>102</b>A and the target device <b>102</b>N in agreeing on the secret key <b>608</b> are represented respectively by blocks <b>610</b>A and <b>610</b>N. The devices may, for example, agree on the secret key by generating secret numbers, and exchanging them via the indirect link. In example non-limiting implementations, the devices may use Diffie Hellman Key Agreement protocol (or its Elliptic curve variant) for the key agreement process.
0083In possible implementations, the initiating device <b>102</b>A may generate a first secret number, and send it to the target device <b>102</b>N via the indirect link. Similarly, the target device <b>102</b>N may generate a second secret number, and sent it to the initiating device <b>102</b>A via the indirect link. In this event, both devices may combine the secret numbers to form a mutually-known, shared secret key that is used to formulate a challenge, as now described.
0084Block <b>612</b> represents formulating and sending a challenge <b>614</b> to the initiating device <b>102</b>A. This challenge may include a randomly-generated nonce, and the target device <b>102</b>N may encrypt the challenge with the key <b>608</b>. As detailed further below, the initiating device <b>102</b>A may decrypt the challenge and return the nonce to the target device <b>102</b>N only if the initiating device <b>102</b>A has received the key <b>608</b>.
0085At the initiating device <b>102</b>A, block <b>616</b> represents receiving the nonce-challenge <b>614</b> from the target device <b>102</b>N. With the initiating device <b>102</b>A and the target device <b>102</b>N having agreed on the secret key <b>608</b>, and with the initiating device <b>102</b>A having received the nonce-challenge <b>614</b>, block <b>618</b> represents decrypting the nonce-challenge <b>614</b>. Block <b>618</b> may include using the secret key <b>608</b>, as represented by the line <b>620</b>, to extract the nonce from the challenge.
0086Block <b>622</b> represents returning the nonce as a response to the challenge <b>614</b>. <figref idref="DRAWINGS">FIG. 6</figref> denotes the nonce-response at <b>624</b>.
0087At the target device <b>102</b>N, block <b>626</b> represents receiving the nonce-response <b>624</b>. Decision block <b>628</b> represents evaluating the validity of the response. More specifically, block <b>628</b> may include comparing the nonce as received in block <b>626</b> to the nonce that was included in the challenge in block <b>612</b>. If these nonces match, then the process flow <b>600</b> may take Yes branch <b>630</b> to block <b>632</b>, which represents approving the key-based authentication request <b>604</b>. <figref idref="DRAWINGS">FIG. 6</figref> denotes this approval generally at <b>634</b>.
0088Returning to the decision block <b>628</b>, if the nonces do not match, or if the target device <b>102</b>N receives no response <b>624</b> at all, then the process flow <b>600</b> may take No branch <b>636</b> to block <b>638</b>. Block <b>638</b> represents denying the key-based authentication request <b>604</b>. <figref idref="DRAWINGS">FIG. 6</figref> denotes this denial generally at <b>640</b>.
0089On the initiating device <b>102</b>A, block <b>642</b> represents receiving a response to the authentication request <b>604</b>. This request may include the approval <b>634</b>, or the denial <b>640</b> (in instances where the target device <b>102</b>N affirmatively reports the denial).
0090On the target device <b>102</b>N, the key-based authentication component <b>304</b>N may report the status of the key-based authentication request, once determined, to the address book-based authentication component <b>302</b>N, as indicated by the dashed line passing into decision block <b>516</b> in <figref idref="DRAWINGS">FIG. 5</figref>. Additionally, if the protocol shown in <figref idref="DRAWINGS">FIG. 6</figref> completes successfully to approve the key-based authentication request, then the initiating device <b>102</b>A may use the secret key <b>608</b>, as agreed to with the target device <b>102</b>N, to respond to the challenge <b>410</b>, as indicated by line <b>416</b> in <figref idref="DRAWINGS">FIG. 4</figref>.
0091Given the above description of the key-based authentication protocols and the address-based authentication protocols, several observations are now noted. Assume, for example, that a device belonging to a user Alice wishes to pair her device with a device belonging to a user Bob. Assume that Alice's telephone number is (555) 555-1212, that she has given Bob her number, and that Bob has entered Alice's number into his address book. Thus, Alice may begin the address-based authentication protocols by hashing her telephone number, and sending this hashed value to Bob via the direct communication link <b>116</b>.
0092Additionally, the parties may begin the key-based authentication protocol, if they haven't already exchanged keys successfully. However, the key-based authentication protocol occurs over the indirect communication link <b>118</b>, which may be, for example, a relatively secure service, such as SMS. Thus, Bob may send his secret key via SMS to (555) 555-1212, which purportedly is Alice's telephone number. However, Alice cannot obtain Bob's secret key unless she truly has access to what is sent to (555) 555-1212. Further, without obtaining Bob's secret key, Alice cannot complete the address-based authentication protocol. Thus, the key-based authentication protocol complements the address-based authentication protocol. Considering both protocols as operating in concert as described herein, the combined protocols as a whole are typically at least as secure as the indirect communication link <b>118</b>.
0093Assume, for example, that a malicious user Ian intercepts Alice's hashed telephone number, as sent to Bob as part of the address-based authentication protocol. With Alice's hashed telephone number in hand, Ian might be able to impersonate Alice, and trick Bob into thinking that Ian is Alice, because Bob's address book may show Alice's phone number. However, unless Ian has access to the Alice's telephone number, Ian cannot complete the key-based authentication protocol. Thus, despite the fact that Ian has, in some sense, compromised the address-based authentication protocol, Ian is not likely to compromise the key-based authentication protocol, unless Ian can undermine or hack, for example, the SMS system.
0094Having described the above operating environments with <figref idref="DRAWINGS">FIGS. 1-6</figref>, the discussion now turns to a description of applications and related models that the above operating environments may facilitate, now presented beginning with <figref idref="DRAWINGS">FIG. 7</figref>.
0095<figref idref="DRAWINGS">FIG. 7</figref> illustrates an operating environment <b>700</b> including a device pairing architecture <b>702</b> and one or more related applications <b>704</b>. The device pairing architecture enables two or more paired devices <b>102</b> to share data and applications. For convenience only, but not to limit possible implementations of the subject matter described herein, the devices <b>102</b> and the users <b>104</b> are carried forward from <figref idref="DRAWINGS">FIGS. 1-6</figref>. However, it is noted that the operating environment <b>700</b> may include devices other than those denoted herein at <b>102</b>.
0096As noted above with <figref idref="DRAWINGS">FIGS. 1-6</figref>, the term “pairing” as used herein does not limit the description herein to connecting two devices <b>102</b> to communicate directly with one another. Instead, the term “pairing” is chosen only for convenience, and two or more devices <b>102</b> may be connected to communicate directly with one another.
0097The device pairing architecture <b>702</b> may be implemented using the tools and techniques described above in <figref idref="DRAWINGS">FIGS. 1-6</figref> in connection with providing automated secure pairing for wireless devices. As such, the device pairing architecture may include components that are distributed across the devices <b>102</b>A and <b>102</b>N. Examples of such components may include the address book-based authentication components <b>302</b> and the key-based authentication components <b>304</b>. However, it is noted that the device pairing architecture <b>702</b> may operate with any scheme suitable for connecting the devices <b>102</b> to communicate directly with one another, and is not limited to the tools and techniques described above in <figref idref="DRAWINGS">FIGS. 1-6</figref>.
0098Once the devices <b>102</b> are coupled or paired, the devices may share data and applications with one another. <figref idref="DRAWINGS">FIG. 7</figref> illustrates several non-limiting examples of such applications <b>704</b>, which may be loaded and configured on one or more of the devices <b>102</b>. As described herein, the devices <b>102</b> may share data between themselves, and/or share processing using any of the applications <b>704</b>.
0099A parallel download application <b>704</b>A enables a first device (e.g., the device <b>102</b>A) to share the burden of downloading data over a network with one or more second or other paired devices (e.g., the device <b>102</b>N). In this manner, if the first device has limited connectivity to the network or suffers from limited bandwidth, and if the other paired devices have more bandwidth, then the other devices may assist the first device by shouldering parts of the download task. This feature is described further herein.
0100A network sharing application <b>704</b>B enables a first device (e.g., the device <b>102</b>A), which has connectivity to a given network, to share that network connection with one or more other paired devices (e.g., the device <b>102</b>N). In this manner, the device <b>102</b>N may piggyback onto the network connection of the device <b>102</b>A.
0101A file sharing application <b>704</b>C enables a first device (e.g., the device <b>102</b>A), which contains one or more files of interest, to share these files of interest with one or more paired devices (e.g., the device <b>102</b>N).
0102A people tracking application <b>704</b>D enables a user associated with a first device (e.g., the device <b>102</b>A) to track how much time the user has been connected or paired with one or more other devices (e.g., the device <b>102</b>N). The people tracking application may, for example, indicate with whom the first device paired, how long the devices were paired, and when the pairing relationships began and ended for different instances of pairing.
0103A chat or conferencing application <b>704</b>E enables two or more paired devices <b>102</b> to establish a private chat session among themselves. For example, if users <b>104</b> are engaged in a meeting in which the users are located in reasonable physical proximity to one another, they may use the devices <b>102</b> to set up a mini-conference within the context of the meeting. Using this mini-conference capability, these users may privately chat or otherwise communicate with one another.
0104Other aspects of the conferencing application <b>704</b>E enable a first device (e.g., the device <b>102</b>A) to share an incoming or outgoing call with one or more other devices (e.g., the device <b>102</b>N). For example, assume that the users <b>104</b> are attending a family function together. At some point, the user <b>104</b>A receives a call from a relative who isn't attending the function. If the user's device <b>102</b>A is paired with one or more other devices <b>104</b>N, then conferencing application may bridge or conference-in the other users (e.g., <b>104</b>N), so that the absent family member may converse with both users <b>104</b>A and <b>104</b>N.
0105An interactive gaming application <b>704</b>F may enable the users <b>104</b> to play interactive games with one another. In this manner, two or more users <b>104</b> associated with paired devices <b>102</b> may play games together, whether in a collaborative mode, or competing against one another.
0106A digital rights module <b>704</b>G may cooperate with a media player application <b>704</b>N to enable a first device (e.g., the device <b>102</b>A) to share digital media content with one or more paired devices (e.g., the device <b>102</b>N). For example, the device <b>102</b>A may store digital content in the form of music, video, software, or the like that may be subject to digital rights management policies. Put differently, the digital content may be licensed from third parties, and subject to copyright or other intellectual property protections. Under suitable restrictions, the device <b>102</b>A may share such content with one or more other devices <b>102</b>N, as permitted under policies established and/or enforced by the digital rights module. For example, the device <b>102</b>A may enable the media player <b>704</b>N on the paired device <b>102</b>N to play a song stored on the first device <b>102</b>A, but only once or only for a predefined interval of time, or the like.
0107Having described the operating environment <b>700</b> in <figref idref="DRAWINGS">FIG. 7</figref>, the discussion now proceeds to a more detailed description of the parallel download application <b>704</b>A, now presented with <figref idref="DRAWINGS">FIG. 8</figref>.
0108<figref idref="DRAWINGS">FIG. 8</figref> illustrates an operating environment <b>800</b> for performing parallel downloads among a plurality of paired devices. For convenience, but not limitation, some components are carried forward from previous drawings, and denoted by identical reference signs. For example, <figref idref="DRAWINGS">FIG. 8</figref> shows the device <b>102</b>A paired to communicate directly with at least paired devices <b>102</b>B and <b>102</b>N. As shown in <figref idref="DRAWINGS">FIG. 8</figref>, the device <b>102</b>A is associated with the user <b>104</b>A.
0109<figref idref="DRAWINGS">FIG. 8</figref> illustrates a scenario in which the user wishes to download or access one or more files or streams <b>802</b> over a wide area network, such as the Internet <b>804</b>. The user may also wish to access one or more websites <b>806</b> over the Internet. Assume that the device <b>102</b>A has limited or no connectivity to the Internet, as denoted by the link <b>808</b>. However, the device <b>102</b>A may communicate directly with the paired devices <b>102</b>B and <b>102</b>N over respective paired links <b>810</b>B and <b>810</b>N. The paired links <b>810</b>B and <b>810</b>N are assumed to have higher bandwidth than the link <b>808</b>.
0110The paired devices <b>102</b>B and <b>102</b>N may connect to the Internet via respective broadband links <b>812</b>B and <b>812</b>N. For the purposes of describing <figref idref="DRAWINGS">FIG. 8</figref>, assume that the bandwidths of the broadband links <b>812</b>B and <b>812</b>N exceed the bandwidth of the link <b>808</b>. It is noted that, to promote clarity, the various links <b>808</b>, <b>810</b>, and <b>812</b> shown in <figref idref="DRAWINGS">FIG. 8</figref> represent any network adapters, drivers, and other hardware and software that enable the various devices to connect to the various networks.
0111In this scenario, if the device <b>102</b>A downloads the entire file <b>802</b>, or accesses the website <b>806</b>, only through the link <b>808</b>, then this download or access may take a relatively long time. If the link <b>808</b> has no connectivity to the Internet, the download or access may not be possible, at least until the link <b>808</b> restores some connectivity to the Internet. However, as described further herein, the device <b>102</b>A may partition this download or access across the paired devices <b>102</b>B and <b>102</b>N. In this manner, the device <b>102</b>A may enlist the help of the devices <b>102</b>B and <b>102</b>N to accomplish the download or access from the Internet, despite the low-bandwidth link <b>808</b>. More specifically, the device <b>102</b>A may take advantage of the paired links <b>810</b> and the broadband links <b>812</b>, to overcome the limitations of the low-bandwidth link <b>808</b>.
0112The devices <b>102</b>A, <b>102</b>B, and <b>102</b>N may include one or more respective processors <b>814</b>A, <b>814</b>B, and <b>814</b>N (collectively, processors <b>814</b>). The foregoing description of the processors <b>106</b> may apply equally to the processors <b>814</b>, although the processors <b>814</b> may be of different types or models than the processors <b>106</b>.
0113The devices <b>102</b>A, <b>102</b>B, and <b>102</b>N may include one or more instances of respective computer-readable storage media <b>816</b>A, <b>816</b>B, and <b>816</b>N (collectively, computer-readable storage media <b>816</b>). The foregoing description of the computer-readable storage media <b>108</b> may apply equally to the media <b>816</b>, and is not repeated here in the interests of conciseness.
0114The parallel download application <b>704</b>A as shown in <figref idref="DRAWINGS">FIG. 7</figref> may be distributed across respective components included in the devices <b>102</b>A, <b>102</b>B, and <b>102</b>N. As shown in <figref idref="DRAWINGS">FIG. 8</figref>, the devices <b>102</b>A, <b>102</b>B, and <b>102</b>N may include respective parallel download components <b>818</b>A, <b>818</b>B, and <b>818</b>N. These parallel download components may be implemented as one or more software modules stored in the media <b>816</b>. These modules may be loaded into the processors <b>814</b> and, when executed, may cause the respective devices <b>102</b>A, <b>102</b>B, and <b>102</b>N to perform the various functions described herein, to perform parallel downloads among the paired devices.
0115The parallel download component <b>818</b>A may enable the device <b>102</b>A to request that the devices <b>102</b>B and <b>102</b>N assist in, for example downloading files or accessing websites over the Internet. More specifically, the parallel download component <b>818</b>A may communicate with corresponding parallel download components <b>818</b>B and <b>818</b>N on the devices <b>102</b>B and <b>102</b>N in completing these functions, as detailed further herein. In this manner, the devices <b>102</b>A, <b>102</b>B, and <b>102</b>N may form a mobile community of wireless devices that share network and processing resources with one another.
0116Having described the operating environment <b>800</b>, the discussion proceeds to a more detailed description of components and data flows related to the device <b>102</b>A, when performing parallel downloads among the paired devices, now presented with <figref idref="DRAWINGS">FIG. 9</figref>.
0117<figref idref="DRAWINGS">FIG. 9</figref> illustrates components and data flows related to the device <b>102</b>A, when performing parallel downloads distributed among the paired devices <b>102</b>B and <b>102</b>N. For convenience only, some features illustrated above are carried forward, and denoted by identical reference numbers.
0118As shown in <figref idref="DRAWINGS">FIG. 9</figref>, the user <b>104</b>A may submit, through the device <b>102</b>A, a request to download or access content over the Internet (e.g., <b>804</b> in <figref idref="DRAWINGS">FIG. 8</figref>). <figref idref="DRAWINGS">FIG. 9</figref> denotes this request generally at <b>902</b>, and the user may interact with a browser application <b>904</b> to submit this request <b>902</b>. As described above, the content sought by the user may include files, streaming content such as audio and/or video, software, access to websites and related HTML pages, or the like.
0119The browser may forward the download request <b>902</b> to a network stack component <b>906</b>, which provides an interface to an Internet connectivity layer <b>908</b> and to a paired connectivity layer <b>910</b>. The Internet connectivity layer <b>908</b> provides interfaces to any adapters, drivers, or other hardware and/or software components related to the link <b>808</b>. Recall that the link <b>808</b> enables the device <b>102</b>A to communicate with the Internet <b>804</b>. For example, the device <b>102</b>A may access the Internet via a GPRS component <b>912</b>, a WiFi component <b>914</b>, a WiMax component <b>916</b>, or other components that implement any suitable access technologies. As shown in <figref idref="DRAWINGS">FIG. 9</figref>, these components <b>912</b>-<b>916</b> may provide respective links <b>808</b>A, <b>808</b>B, and <b>808</b>N to the Internet <b>804</b>.
0120Turning to the paired connectivity layer <b>910</b>, this layer provides interfaces to any adapters, drivers, or other hardware and/or software components related to the paired link or links <b>810</b>. Recall that the link <b>810</b> enables the device <b>102</b>A to communicate directly with one or more paired devices (e.g., devices <b>102</b>B and <b>102</b>N). For example, the device <b>102</b>A may be paired with one or more other devices via a BlueTooth (BT) component <b>918</b>, a WiFi component <b>920</b>, or other components that implement any suitable pairing technologies. It is noted that, for example, WiFi technologies may be suitable for enabling access to the Internet <b>804</b> or to the paired devices <b>102</b>B and <b>102</b>N.
0121Returning to the network stack <b>906</b>, the parallel download component <b>818</b>A may cooperate with the network stack to partition the download request <b>902</b> into a plurality of download portions <b>922</b>A and <b>922</b>N (collectively, download portions <b>922</b>). More specifically, the parallel download component <b>818</b>A may receive notification of the download request <b>902</b>, determine bandwidth capacities of one or more paired links and related broadband links (e.g., <b>810</b> and <b>812</b>), determine bandwidth capacities of one or more local Internet links (e.g., <b>808</b>), partition the download request <b>902</b> into the one or more portions <b>922</b>, and assign one or more of the portions <b>922</b> to paired devices (e.g., <b>102</b>B and <b>102</b>N). In some instances, where the device <b>102</b>A has at least some connectivity, it may download one or more of the portions itself.
0122It is noted that the various download portions <b>922</b> need not be equal. Instead, the parallel download component may size the download portions, depending on the capacity of the available links that may perform the downloads. For example, if combination of a given broadband link (e.g., <b>812</b>B) and a given paired link (e.g., <b>810</b>B) offers relatively high bandwidth, then the parallel download component may allocate a larger portion of the overall download to this combination of links. Similar logic may apply to links having lower bandwidth.
0123In any event, the parallel download component <b>818</b>A may formulate download requests <b>924</b> and <b>926</b>, which correspond respectively to the download portions <b>922</b>A and <b>922</b>N. These download requests <b>924</b> and <b>926</b> may be viewed as a subset of the download request <b>902</b>. The network stack may route these requests <b>924</b> and <b>926</b> to, respectively, the paired connectivity layer <b>910</b> and the Internet connectivity layer <b>908</b>.
0124The devices <b>102</b>A, <b>102</b>B, and <b>102</b>N may be viewed as forming a network or community of mobile wireless devices for parallelizing the download process. As such, the devices <b>102</b>A may be viewed as an initiator node within this network or community. The initiator node <b>102</b>A may form the network to include, for example, the paired devices <b>102</b>B and <b>102</b>N as additional nodes. After forming the group, the initiator node may initially estimate the speeds of the nodes, and then may vary the workload allocated to these nodes depending on their speeds.
0125Having described the components and data flows in <figref idref="DRAWINGS">FIG. 9</figref>, the discussion now turns to a description of a process flow for forming groups or networks of devices to perform parallel downloads among paired devices, now presented in <figref idref="DRAWINGS">FIG. 10</figref>.
0126Group Formation Protocols
0127<figref idref="DRAWINGS">FIG. 10</figref> illustrates a combined process and data flow <b>1000</b> for forming a group or network of two or more mobile wireless devices, or nodes, for performing parallel downloads among the devices. While this process flow <b>1000</b> is described with certain components illustrated herein, it is noted that at least some of this process flow <b>1000</b> may be performed with other components without departing from the scope and spirit of the description herein. Additionally, the order of the process blocks as presented in <figref idref="DRAWINGS">FIG. 10</figref> is shown for convenience only, but not limitation.
0128The process and data flow <b>1000</b> as shown in <figref idref="DRAWINGS">FIG. 10</figref> may provide a mechanism or protocol by which an initiating node (e.g., device or node <b>102</b>A) may request help from one or more other recipient nodes (e.g., device or node <b>102</b>N) in performing the initiating node's activities. More specifically, the node <b>102</b>A may ask the other nodes <b>102</b>N to collaborate with it, in parallelizing some activity undertaken by the node <b>102</b>A.
0129Block <b>1002</b> represents sending out a controlled broadcast request packet <b>1004</b>, asking for collaborators. The initiator node <b>102</b>A may send out the controlled broadcast request packet <b>1004</b>. The request packet <b>1004</b> may indicate the content <b>1006</b> sought by the initiator node <b>102</b>A. For example, this content <b>1006</b> may be a file to be downloaded, a website to be accessed, or an audio or video stream to be received. The packet <b>1004</b> may indicate the resource location of the content <b>1006</b>.
0130As represented in block <b>1008</b>, one or more recipient nodes (e.g., <b>102</b>N) may receive the request packet <b>1004</b>. Upon receiving the request packet, the recipient node may check to see whether it has an up-to-date copy of the content <b>1006</b> indicated in the request packet, as represented in decision block <b>1010</b>. If it does, then the process flow <b>1000</b> may take Yes branch <b>1012</b> to block <b>1014</b>.
0131Block <b>1014</b> represents sending content <b>1016</b> to the initiator node, in response to the request packet <b>1004</b>. In this manner, the initiator node may obtain the content from this recipient node via, for example, a high-speed WLAN link (e.g., <b>810</b>N), as represented generally at block <b>1018</b>.
0132Returning to decision block <b>1010</b>, if the recipient node does not contain the requested content locally, the process flow <b>1000</b> may take No branch <b>1020</b> to decision block <b>1022</b>, which evaluates whether the recipient node wishes to join in the collaborative effort proposed by the initiator node.
0133From decision block <b>1022</b>, if the recipient node is interested in joining the collaborative effort, then the process flow may take Yes branch <b>1024</b> to block <b>1026</b>. Block <b>1026</b> represents sending or unicasting an affirmative reply <b>1028</b> to the initiator node.
0134At the initiator node, block <b>1030</b> represents receiving the affirmative reply from the recipient node. Block <b>1032</b> represents adding this recipient node to a network of collaborating mobile devices or nodes.
0135All nodes that receive the request packet <b>1004</b> may re-broadcast this packet up to a maximum number of hop-counts set by the initiator node. The initiator node may collect all affirmative replies, and these affirmative replies indicate those recipient nodes that are willing to collaborate with the initiator node, and are thus willing become members of the collaborative community or network.
0136Returning to decision block <b>1022</b>, if the recipient node does not wish to collaborate with the initiator node, the process flow <b>1000</b> may take No branch <b>1034</b> to block <b>1036</b>. Block <b>1036</b> represents sending a negative response <b>1038</b> to the initiator node.
0137At the initiator node, block <b>1040</b> represents receiving the negative response <b>1038</b>. However, in some instances, if the recipient node does not wish to collaborate with the initiator node, the recipient node may opt to not respond to the request packet <b>1004</b>. In this case, the initiator node would not receive an affirmative response <b>1028</b> from this recipient node, resulting in the recipient node not joining the collaborative network.
0138The initiator node may invoke the above protocol when it wishes to download content via its WWAN link (e.g., link <b>808</b>), and determines that it wishes to request the help of other mobile devices in downloading this content. In the description below, this initiator node is denoted by S. If any of the local nodes have the content, then S may obtain it from that particular node via its WLAN interface. Otherwise, S tries to form a collaborative group to help in the download.
0139The group formation protocols may proceed as follows: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0140">1. Initiator node S prepares a collaboration request packet CREQ. CREQ may contain the following: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0141">a. collaborative flag set</li><li id="ul0003-0002" num="0142">b. address (resource locator) of the file it needs to download</li><li id="ul0003-0003" num="0143">c. hop_count field set to max_hop_count—a maximum hop-count for the packet</li></ul></li><li id="ul0002-0002" num="0144">2. S broadcasts the CREQ packet and sets a timer for max_rep_time units.</li><li id="ul0002-0003" num="0145">3. Any recipient node i that receives the CREQ packet may perform the following: <ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0146">a. Node i checks its local cache for the file mentioned in the CREQ. If i has the file in its cache, and if it is up-to-date, then it unicasts a reply back to S informing it of the availability of the file. S can now get the file over the WLAN link from i.</li><li id="ul0004-0002" num="0147">b. If i does not have the file, it does the following <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0148">i. If it is interested in joining the collaborative effort, it unicasts a reply CREP back to S informing it of its willingness to join the group.</li><li id="ul0005-0002" num="0149">ii. Decrements the hop_count value by 1 and if the hop_count is greater then zero, re-broadcasts the packet.</li></ul></li></ul></li><li id="ul0002-0004" num="0150">4. If S has a reply from any node informing it of the presence of the file in its local cache, S gets the file from that node over the WLAN link.</li><li id="ul0002-0005" num="0151">5. S collects all the CREPs it receives within the max_rep_time time period. All the nodes that replied in this time period are now counted by S as nodes which are willing to take part in the collaborative effort.</li></ul></li></ul>
0152Sub-process <b>1</b><i>c </i>helps to ensure that the collaboration request is flooded restrictively. In sub-process <b>3</b><i>a</i>, the node i uses the standard if-modified-since HTTP request mechanism to ascertain whether the file in its local cache is consistent with the version on, for example, a server hosting an external website. In sub-process <b>4</b>, if more than one node has the file in its local cache, then S may obtain the file from the node whose reply came in first. At the end of the group formation mechanism, the node S has a list of the n nodes that are willing to collaborate. These are the nodes from which it got CREPs.
0153Having described the above protocols for forming the collaborative network, the discussion now turns to a description of approaches for allocating or dividing the workload among the members of the collaborative network, now presented with <figref idref="DRAWINGS">FIG. 11</figref>.
0154Work Division and Distribution Algorithms
0155<figref idref="DRAWINGS">FIG. 11</figref> illustrates a combined process and data flow <b>1100</b> for dividing and distributing work among members of a collaborative network. The collaborative network may be formed, for example, using the protocols shown above in <figref idref="DRAWINGS">FIG. 10</figref>. However, other approaches for forming the collaborative network may be suitable, as well, without departing from the scope and spirit of the description herein.
0156Having formed a collaborative network including an initiator node S and one or more (n) collaborator nodes, the initiator node S would have a list of the n collaborator nodes. The initiator node S (denoted at <b>102</b>A in <figref idref="DRAWINGS">FIG. 11</figref>) wishes to divide or distribute the work of downloading the content among the n collaborator nodes (denoted at <b>102</b>N in <figref idref="DRAWINGS">FIG. 11</figref>) in proportion to the capabilities of the collaborator nodes (e.g., their network speeds, processing power, and the like). To enhance overall performance, the initiator node would like the more powerful collaborator nodes to do a larger portion of the work. As detailed further below, the network speed of the collaborator nodes may be dynamically estimated, and the work distribution allocated in proportion to these estimated speeds.
0157Possible implementations of the work distribution algorithms may be based on the model of the work-queue. As shown in <figref idref="DRAWINGS">FIG. 11</figref>, block <b>1102</b> represents the initiator node obtaining the total size of the content that it wishes to download. The initiator node may perform block <b>1102</b>.
0158Block <b>1104</b> represents forming a work-queue having a plurality of items. Block <b>1106</b> represents assigning, to these items, equal-sized byte ranges of the content to be downloaded.
0159Block <b>1108</b> represents sending items <b>1110</b> from the work-queue to the members of the community. At the collaborator nodes, block <b>1112</b> represents downloading the content corresponding to the item from, for example, a server associated with a website. Block <b>1116</b> represents returning the downloaded items <b>1118</b> to the initiator node.
0160At the initiator node, block <b>1120</b> represents receiving the downloaded items <b>1118</b>. Block <b>1122</b> represents assembling the downloaded items <b>1118</b> with one or more other downloaded items to constitute the overall downloaded content.
0161In some instances, servicing of the items in the work-queue may entail opening and closing a connection with the server. Aggregated over a plurality of collaborator nodes, opening and closing these connections may involve significant overhead, and may slow down the download process. Thus, other algorithms may allocate or allot larger portions of the content to the collaborator nodes, based on past performance of the collaborator nodes.
0162These algorithms may include at least two phases: a learning phase, and a work distribution phase. In most instances, the network speeds of the collaborator nodes are not known before beginning the download process. Thus, the learning phase may treat all of the collaborator nodes as equals, and estimate the speeds of the different collaborator nodes. Afterwards, in the work distribution phase, the collaborator nodes are assigned to download portions of the content in proportion to their estimated speeds.
0163This description provides at least two algorithms dividing the work load based on the network dynamics. A one-time assignment algorithm assigns the work load for each collaborator nodes based on the initial estimate of the speeds obtained from the learning phase, as described above. This one-time assignment algorithm assigns work only once, and so may be useful in scenarios where the connection speeds of the collaborator nodes do not vary significantly during the overall download process. Under this one-time assignment algorithm, the work assignment may entail relatively little processing for the initiator node, and may be suitable for network environments in which the speeds and performance of the collaborator nodes are relatively static over time.
0164A periodic assignment algorithm may be suited for a more dynamic network environment, in which the network speeds of the collaborator nodes may change more frequently over time. More specifically, the periodic assignment algorithm may be agile enough to react to any changes in the bandwidths of the collaborator nodes. In response to these changes, the periodic assignment algorithm may dynamically rebalance the loads on these collaborator nodes.
0165Note that the dynamism of the network can be due to at least three factors. First, the speeds of the individual nodes may vary. Second, because the nodes are mobile, some of the nodes may go out of range, thereby affecting bandwidth and throughput. Third, the nodes may shut down or run out of power.
0166The variables suitable for describing the algorithms are defined next, followed by the algorithms for the learning and the work distribution phases.
VARIABLE DEFINITIONS
01671. Number of collaborator nodes: n
0168The number of CREPs received by the initiator node S. The initiator node S itself may be included in this list.
01692. Total Size of the file: fs
0170This variable represents the total amount of work to be done in downloading the content or file. The initiator node S may use this value to determine the amount of work to be assigned to the collaborator nodes. The initiator node S may query the appropriate server hosting the content or file to obtain metadata of the content or file. This metadata would indicate the total size of the content or file.
01713. Initial chunk size: cs
0172The amount of data to be downloaded is in proportion to the capacity (network speed) of the nodes, which are calculated dynamically. Initially, since the initiator node does not know the network speeds for the collaborator nodes, the initiator node may assign a standard chunk size for all the collaborator nodes. This standard chunk size may be used until time ts.
01734. Weighted Average Speed Array: LS={s1, s2 . . . sn}
0174This array contains the values of the measured speeds of all the nodes in the group. Initially, this array may be empty, and afterwards filled in and updated dynamically. Hence, this array provides a reasonably reliable estimate of the connection speeds of the nodes.
01755. Time after which the network speeds of the nodes are available: ts
0176To start with, the algorithm may assign all the nodes equal amounts of work to be done (see 3). After the nodes return their assigned parts at least once, the algorithm would have more definite values of the connection speeds of the nodes. This is assumed to take ts time units.
01776. Safe-chunk size: p
0178Assuming that the overall environment in which the algorithms operate is highly mobile and varying, reliability may be a challenge. If the algorithms assign a large portion of the content or file to be downloaded by a single node, afterwards waits for this large portion to download to completion, the algorithms may run the risk of losing out on valuable data if that node moves off in the middle of its download. To avoid this risk, the algorithms may distribute chunks of size p among the nodes. In this manner, the algorithms may avoid concentrating too much work on one node, and exposing the overall process excessively to a single point of failure. In this approach, the amount of data assigned to the nodes is less then equal top.
0179Learning Phase
0180<figref idref="DRAWINGS">FIG. 12</figref> illustrates a combined process and data flow <b>1200</b> for the learning phase algorithm described above. The initiator node may perform the learning phase initially when starting a download process. The learning phase may last for ts time units. The initiator node may use the learning phase initially to estimate the speeds of the nodes within the collaborative group. In this learning phase, the algorithm assigned the nodes an equal amount of data to be downloaded (of chunk size cs). The chunk size is invariant in this learning phase. Faster nodes may download multiple chunks in this phase. Since the overhead associated with every connection establishment process may be significant (e.g. HTTP over TCP), it may be desirable to choose an optimal value for cs. If cs is set too low, then the algorithm might obtain misleading and incorrect values about the connection speed of the nodes.
0181The initiator node may perform the following in this phase, as now described. Block <b>1202</b> represents assigning a chunk <b>1204</b> of size cs for the n collaborator nodes to download. Block <b>1206</b> represents the collaborator nodes downloading the assigned chunks.
0182Block <b>1208</b> represents the collaborator nodes returning their assigned chunks, as denoted at <b>1210</b>. At the initiator node, block <b>1212</b> represents receiving the chunks from the collaborator nodes. Block <b>1214</b> represents determining the network speed of the collaborator nodes, based on the time it took the nodes to download and return the chunks.
0183After receiving a chunk from a given collaborator node, the initiator node may determine whether it has received at least one chunk from all of the collaborator nodes, as represented in decision block <b>1216</b>. If the initiator node has not received a chunk from at least one node, then the process flow <b>1200</b> may take No branch <b>1218</b>, returning to block <b>1202</b> to assign the node to retrieve another chunk. This keeps faster nodes busy, while the initiator node waits for one or more slower nodes to return their chunks.
0184Returning to block <b>1216</b>, if the initiator node has received chunks from all of the collaborator nodes, then the process flow <b>1200</b> may take Yes branch <b>1220</b> to block <b>1222</b>. At this point, the initiator node has received chunks from all collaborator nodes, which takes ts time units. At this point, the initiator node has definite values of the speeds for all the elements in the array LS, and has computed network speeds for all the collaborator nodes, as represented generally at block <b>1222</b>.
0185The fact that faster nodes can download multiple chunks ensures that the other nodes are not idling away, waiting for the slowest node to complete its job. ts is the time taken for the slowest node to download and pass the chuck of size cs to the initiator node.
0186Work Distribution Phase
0187In the work distribution phase, the initiator node has an initial idea of the connection speeds of the collaborator nodes, and can then assign the amount of data they have to download in proportion to their speeds. As noted above, this description provides two algorithms for this phase, based on the dynamism of the environment: the one-time assignment algorithm shown in <figref idref="DRAWINGS">FIG. 13</figref>, and the periodic assignment algorithm shown in <figref idref="DRAWINGS">FIG. 14</figref>.
0188One-Time Assignment
0189<figref idref="DRAWINGS">FIG. 13</figref> illustrates a combined process and data flow <b>1300</b> for the one-time assignment algorithm that may be performed as part of the learning phase described above. The one-time assignment algorithm may be suitable for network environments that are relatively static, or not dynamic.
0190After the learning phase described in <figref idref="DRAWINGS">FIG. 12</figref>, the initiator node has an initial estimate of the speeds of the collaborator nodes. As represented in block <b>1302</b>, the initiator node may calculate the portion of the content or file remaining to be downloaded after running the learning phase.
0191As shown in block <b>1304</b>, the initiator node obtains the network speeds of the various collaborator nodes, as estimated during the learning phase. Block <b>1306</b> represents dividing or apportioning the remaining part of the content or file among the collaborator nodes, in proportion to their respective speeds from the learning phase. Block <b>1308</b> represents assigning the respective portions <b>1310</b> of the download to the various collaborator nodes.
0192At the collaborator nodes, block <b>1312</b> represents receiving the assignments <b>1310</b> from the initiator node. Block <b>1314</b> represents downloading the assigned portions of the download, and sending the downloaded portions <b>1316</b> to the initiator node. At the initiator node, block <b>1318</b> represents receiving the downloaded portions <b>1316</b> from the recipient nodes.
0193Having described the one-time assignment algorithm in <figref idref="DRAWINGS">FIG. 13</figref>, the discussion now turns to a description of the periodic assignment algorithm, now presented in <figref idref="DRAWINGS">FIG. 14</figref>.
0194Periodic Assignment Algorithm
0195<figref idref="DRAWINGS">FIG. 14</figref> illustrates a combined process and data flow <b>1400</b> for the periodic assignment algorithm described herein. The periodic assignment algorithm is highly agile, and may appropriate for dynamic network environments. At this stage, having performed the learning phase, the initiator node has definite measured values for the elements in the array LS, and also has downloaded a certain amount of the content or file while performing the learning phase.
0196In the periodic assignment algorithm, the initiator node S assigns work to the periodic assignment algorithm based on the following two criteria: <ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0000"><ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0197">a. The amount of work done by a node is in proportion to its network speed as indicated in LS; and</li><li id="ul0007-0002" num="0198">b. The amount of work assigned to a node is not very high in a single round—this may help to ensure that the amount of salvaging work is minimal in the event of any of the nodes going down at any stage.</li></ul></li></ul>
0199Block <b>1402</b> represents calculating the portion of the content or file remaining to be downloaded, after completion of the learning phase. Block <b>4104</b> represents dividing this remaining portion into fixed-size partitions of size p each. The initiator node S treats every partition individually, and block <b>1406</b> represents assigning single partitions <b>1408</b> to corresponding nodes to download.
0200The collaborator nodes handle and download the assigned partitions <b>1408</b> sequentially, as represented at block <b>1410</b>. Block <b>1412</b> represents downloading the assigned partitions, and block <b>1414</b> represents returning the downloaded partitions <b>1416</b> to the initiator node.
0201At the initiator node, block <b>1418</b> represents receiving a downloaded partition from a given collaborator node. After the given collaborator node completes downloading a given partition, the process flow <b>1400</b> proceeds to decision block <b>1420</b>, to determine whether any more partitions remain to be downloaded.
0202From decision block <b>1420</b>, if no partitions remain to be downloaded, then the process flow <b>1400</b> takes Yes branch <b>1422</b> to completion state <b>1424</b>. Otherwise, if one or more partitions remain to be downloaded, the process flow <b>1400</b> takes No branch <b>1426</b> to block <b>1428</b>, which represents accessing a performance history of a given node, as indicated by entries in the array LS, to determine the amount of data that should be assigned to the node to download next. Afterwards, the process flow <b>1400</b> may return to block <b>1406</b> to assign the next partition of data to be downloaded by the node.
0203If there are r bytes of the file remaining to be downloaded, S partitions it into c chunks of size p each. So, c*p=r. Now, for any node i, the periodic assignment algorithm can calculate the data it may download as follows:
02041. The amount of data to that the node may download is given by:
0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><msub><mi>d</mi><mi>i</mi></msub><mo>=</mo><mrow><mrow><mo>(</mo><mfrac><msub><mi>s</mi><mi>i</mi></msub><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><msub><mi>s</mi><mi>j</mi></msub></mrow></mfrac><mo>)</mo></mrow><mo>×</mo><mi>p</mi></mrow></mrow><mo>,</mo></mrow></math></maths><img file="US2012094635A1_D0001.tif" />
0000where s<sub>j</sub>ε LS, and s<sub>i </sub>is the speed of the i<sup>th </sup>node and
02052. d<sub>i </sub>is added to the appropriate offset of the current partition (the partitions are handled sequentially) to get the starting and ending byte count of the data to be downloaded.
0206The maximum amount of data theoretically possible to assign to a node for downloading in a single round is p. This ensures that there is not too much work assigned to a single node (see b above).
0207Updating the Speeds in LS
0208After every iteration of the periodic assignment algorithm for a given node, when the node returns the data it has downloaded, the corresponding s value for that node in LS is updated to store the weighted average speed value of that node. If the present value of s is sp, and the latest speed is sc, then the new value of s is given by:
0000<br /><i>w*sc</i>+(1−<i>w</i>)*<i>sp</i>(0<<i>w<</i>1)
0209The value of w can be varied depending on whether the algorithm is to apply more weight to the latest data acquired for the node, or to the overall history of the node. If the network is highly mobile, a high value for w is desirable. For relatively stable networks, the low value of w may be appropriate. In any event, block <b>1430</b> in <figref idref="DRAWINGS">FIG. 14</figref> represents updating the speed of the various nodes in the collaborative network.
0210Having described the periodic assignment algorithm in <figref idref="DRAWINGS">FIG. 14</figref>, the discussion now turns to a description of failure handling mechanisms, now presented in <figref idref="DRAWINGS">FIG. 15</figref>.
0211Failure Handling
0212<figref idref="DRAWINGS">FIG. 15</figref> illustrates a combined process and data flow <b>1500</b> for a failure handling mechanism. Assuming that these algorithms may operate in a highly dynamic network environment, the failure mechanism may handle scenarios in which nodes do not complete their assigned jobs. A node is considered to have failed to complete the job assigned to it if it does not return its downloaded data within an estimated time.
0213Block <b>1502</b> represents assigning a chunk of the download to a given node. After every node is assigned its job, the initiator node calculates a time-out period for the node, as represented in block <b>1504</b>. The initiator node may calculate this value based on the node's speed, as indicated by LS. If the initiator node expects the node to take time T to complete its job, based on its speed value in LS, then the initiator node may set the time-out period as, for example, 2T.
0214Block <b>1506</b> represents evaluating whether a given node has returned its downloaded chunk. If a downloaded chunk arrives from the given node, then the process flow <b>1500</b> may take Yes branch <b>1508</b> to a completion state <b>1510</b>. However, no chunk has yet arrived from the given node, then the process flow <b>1500</b> may take No branch <b>1512</b> to decision block <b>1514</b>.
0215Decision block <b>1514</b> evaluates whether the timeout period set in block <b>1504</b> has expired. If the timeout period has not expired, then the process flow <b>1500</b> may take No branch <b>1516</b> to return to decision block <b>1506</b>. If the timeout period has expired, then the process flow <b>1500</b> may take yes branch <b>1518</b> to return to block <b>1520</b>.
0216If the node fails to complete its job in this time-period, then the failure handling mechanism may append information about that chunk to a failed download queue, as represented in block <b>1520</b>. As shown in <figref idref="DRAWINGS">FIG. 15</figref>, elements or entries in the failed download queue may contain information indicating the position of the chunk within the content or file to be downloaded, as represented in block <b>1522</b>. Elements of the failed download queue may also contain information indicating the size of the chunk, as represented in block <b>1524</b>.
0217Block <b>1526</b> represents sorting the failed download queue. Block <b>1526</b> may include sorting the failed download queue in, for example, ascending order, according to the position of the chunk within the file, as indicated in block <b>1522</b>.
0218Block <b>1528</b> represents assigning entries from the failed download queue to other nodes for downloading. Entries in the failed download queue may be given highest priority, such that servicing this queue is prioritized over other downloading chunks. After the nodes return their assigned chunks of the download, if this failed download queue is not empty, then block <b>1528</b> de-queues an element from the queue, and assigns that element to that node for download.
0219If a given node fails to return a chunk that it was assigned to download, then the failure handling mechanism may assign a zero value as the latest reported speed of this failed node, as represented in block <b>1530</b>. As represented in block <b>1532</b>, the s value of that failed node is re-calculated with this latest-reported speed value. In this manner, the failure handling mechanism may accommodate scenarios where a given node goes down temporarily. The temporary failure of the nodes may be due to scenarios in which the nodes become overloaded with their individual work. In such cases, the collaborative download tasks may be relegated to the background, or paused temporarily or indefinitely. Since these nodes are voluntarily donating their bandwidth, these scenarios may occur relatively often.
0220The group formation algorithm may also be run periodically to ensure that the initiator node is dealing only with currently active nodes. Additionally, new iterations of the group formation algorithm may help to clean up stale groups, and purge them of failed or unresponsive nodes.
0221Having provided the above description of tools for forming the groups and for distributing the work among the members of these groups, it is noted that, in some implementations, the tools may form these collaborative groups without the involvement of any content servers and/or proxy servers from which the content is downloaded. Instead, the initiator nodes and the recipient nodes may themselves perform all of the functions related to forming the groups or distributing the work among the members. More specifically, the initiator nodes and the recipient nodes may perform these functions without the assistance of, for example, any content servers or any proxy servers.
CONCLUSION
0222Although the systems and methods have been described in language specific to structural features and/or methodological acts, it is to be understood that the system and method defined in the appended claims is not necessarily limited to the specific features or acts described. Rather, the specific features and acts are disclosed as exemplary forms of implementing the claimed system and method.
0223In addition, regarding certain data and process flow diagrams described and illustrated herein, it is noted that the processes and sub-processes depicted therein may be performed in orders other than those illustrated without departing from the spirit and scope of the description herein. Also, while these data and process flows are described in connection with certain components herein, it is noted that these data and process flows could be performed with other components without departing from the spirit and scope of the description herein.
Contents7
17 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15 Sheet 16 Sheet 17
Every citation, both ways
| Document | Relation | Office | Cited during |
|---|---|---|---|
| US2020134600A1 | Cited by | United States of America | Search report |
| KR20160096805A | Cited by | Republic of Korea | Applicant |
| US10588175B1 | Cited by | United States of America | Applicant |
| US2016360412A1 | Cited by | United States of America | Pre-grant |
| US2016360412A1 | Cited by | United States of America | Search report |
| US9094370B2 | Cited by | United States of America | Search report |
| US10212596B2 | Cited by | United States of America | Search report |
| US11494757B2 | Cited by | United States of America | Applicant |
| US10079885B1 | Cited by | United States of America | Search report |
| US10917791B2 | Cited by | United States of America | Applicant |
| TWI769120B | Cited by | Taiwan Province of China | Examiner |
| US2010330976A1 | Cited by | United States of America | Pre-grant |
| US2002178385A1 | Cites | United States of America | Pre-grant |
| US2005113069A1 | Cites | United States of America | Pre-grant |
| US2005266798A1 | Cites | United States of America | Pre-grant |
| US2005282578A1 | Cites | United States of America | Pre-grant |
| US2006083187A1 | Cites | United States of America | Pre-grant |
| US2007106894A1 | Cites | United States of America | Pre-grant |
| US2007178882A1 | Cites | United States of America | Pre-grant |
| US2007178884A1 | Cites | United States of America | Pre-grant |
| US7643817B2 | Cites | United States of America | Pre-grant |
| US7796945B2 | Cites | United States of America | Pre-grant |
| US8116733B2 | Cites | United States of America | Pre-grant |
4 members in 1 office
Priority claims6
| Document | Office | Kind | Date |
|---|---|---|---|
| 55509306 | United States of America | A | |
| 55509306 | United States of America | A | |
| 201113335454 | United States of America | A | |
| 11555093 | – | – | – |
| US20060555093 | – | – | – |
| US201113335454 | – | – | – |
Members4
| Document | Office | Kind | |
|---|---|---|---|
| US2008102793A1 | United States of America | A1 | |
| US8103247B2 | United States of America | B2 | |
| US2012094635A1 | United States of America | A1 | |
| US8989706B2 | United States of America | B2 |
5 legal events, as the office reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | |
|---|---|---|
| Maintenance fee paymentMAFP | MAFP | |
| Maintenance fee paymentMAFP | MAFP | |
| Information on status: patent grantGrantedPATENTED CASESTCF | STCF | |
| AssignmentAS | AS | |
| AssignmentAS | AS |
Numbers
- Publication
- 20120094635
- Publication, DOCDB
- 2012094635
- Publication, EPODOC
- US2012094635
- Application
- 13335454
- Application, DOCDB
- 201113335454
- Application, EPODOC
- US201113335454
Titles
- English
- Automated Secure Pairing for Wireless Devices
Classification
- CPC, 5
- H04W12/06
- H04L63/18
- H04W84/18
- H04W12/50
- H04W12/04
- IPC, 1
- H04W12 00
- USPC, 1
- 455411000