×

Determining a maximal set of dependent software updates valid for installation

  • US 7,568,195 B2
  • Filed: 05/01/2004
  • Issued: 07/28/2009
  • Est. Priority Date: 12/16/2003
  • Status: Active Grant
First Claim
Patent Images

1. In a computing system having an operating system installed, the operating system being divided into a plurality of discrete packages, and wherein a plurality of version updates are available to update a first package of the installed operating system, a method for selecting an optimal set of available versions to allow for maximal version updates of the first package in the fewest update steps possible, while honoring package dependency constraints, the method comprising:

  • downloading, to a mobile computing device, a collection of update packages for updating an operating system that is installed on the mobile computing device, wherein the operating system is divided into a plurality of discrete packages that may each be updated independently from the other packages, and wherein the collection of update packages includes a plurality of update packages that correspond to different versions of the installed first package of the installed operating system on the mobile computing device, and wherein each update package includes an associated manifest file that describes the contents and related dependency information of the update package, including the version of the update package;

    for each package of the installed operating system on the mobile computing device, generating a graph having a node for the installed version of the package, the graph being generated from a manifest file corresponding to the installed version of the package;

    for each of the update packages to be installed, accessing the associated manifest file to determine on which installed package the update package depends, wherein each update package may depend on an installed package by being directly dependent on the installed package or by being recursively dependent on another update package which in turn is dependent either directly on the installed package or on another update package, and upon determining on which installed package the update package depends, adding a new node to the graph, the new node corresponding to the version of the update package, such that upon adding a new node for each of the update packages, each graph is formed as a tree having the node for the installed version at the base of the graph and branches for each of the new nodes, each new node being linked to another node on which it depends, and each new node of the same graph corresponding to a different version of the installed package that the graph represents;

    subsequent to generating the graphs, determining that the graph corresponding to the first package of the installed operating system includes two paths that each include a node corresponding to the highest final version to which the first package may be updated;

    subsequent to identifying the two paths, traversing each path and validating each node traversed;

    upon validating each node of both paths, selecting the path that has the lowest cost of installation wherein each version in a path has a cost of installation and wherein the cost of installation of each path comprises the sum of the cost of installation of each version in the path; and

    installing the update package corresponding to each node of the selected path to update the first package of the installed operating system.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×