Akamai Technologies, Inc.

Carnegie Mellon University

Gary Lee Miller

Ravi Sundaram

Satish Balusu Rao

Claudson F Bornstein

Timothy K Canfield

Ioannis Koutis

Robert M Hibdon

David Tolliver

Claudson F Borenstein

Methods and apparatuses for constructing a multi-level solver, comprising decomposing a graph into a plurality of pieces, wherein each of the pieces has a plurality of edges and a plurality of interface nodes, and wherein the interface nodes in the graph are fewer in number than the edges in the graph; producing a local preconditioner for each of the pieces; and aggregating the local preconditioners to form a global preconditioner.

Method and apparatuses for solving weighted planar graphs

A method of partitioning a weighted combinatorial graph representative of a dataset consists of the steps of generating a generalized Laplacian matrix corresponding to the combinatorial graph, computing the eigenstructure of the generalized Laplacian matrix, determining if an end criterion is satisfied using the eigenstructure, and if the end criterion is not satisfied, calculating new values for at least some of the plurality of weighting factors using the eigenstructure, updating the combinatorial graph with the new values for at least some of the weighting factors, and returning to the generating step.

Method for partitioning combinatorial graphs

Methods and apparatuses for solving a system on a symmetric diagonally dominant matrix. The method includes constructing an equivalent symmetric diagonally dominant linear system Ax=b from the system on a symmetric diagonally dominant matrix, wherein the matrix A of the equivalent linear system Ax=b has negative off-diagonal entries and zero row sums; constructing a graph of the matrix A of the equivalent linear system; constructing a decomposition of the graph; constructing a two-level process using the decomposition of the graph, wherein the two-level process includes reducing the equivalent linear system Ax=b to a linear system By=c; and extending the two-level process to a multi-level process having more than two levels.

Methods and apparatuses for solving graph Laplacians

A routing mechanism operable in a distributed networking environment, such as a content delivery network (CDN), provides improved connectivity back to an origin server, especially for HTTP traffic. The technique enables an edge server operating within a given edge region to retrieve content (cacheable, non-cacheable and the like) from an origin server more efficiently by selectively routing through the network's own nodes, thereby avoiding network congestion and hot spots. The technique enables an edge server to fetch content from an origin server through an intermediate edge server or, more generally, enables an edge server within a given first region to fetch content from the origin server through an intermediate edge region.

Optimal route selection in a content delivery network

A routing mechanism, service or system operable in a distributed networking environment. One preferred environment is a content delivery network (CDN) wherein the present invention provides improved connectivity back to an origin server, especially for HTTP traffic. In a CDN, edge servers are typically organized into regions, with each region comprising a set of content servers that preferably operate in a peer-to-peer manner and share data across a common backbone such as a local area network (LAN). The inventive routing technique enables an edge server operating within a given CDN region to retrieve content (cacheable, non-cacheable and the like) from an origin server more efficiently by selectively routing through the CDN's own nodes, thereby avoiding network congestion and hot spots. The invention enables an edge server to fetch content from an origin server through an intermediate CDN server or, more generally, enables an edge server within a given first region to fetch content from the origin server through an intermediate CDN region.

A routing mechanism, service or system operable in a distributed networking environment. One preferred environment is a content delivery network (CDN) wherein the present invention provides improved connectivity back to an origin server, especially for HTTP traffic. In a CDN, edge servers are typically organized into regions, with each region comprising a set of content servers that preferably operate in a peer-to-peer manner and share data across a common backbone such as a local area network (LAN). The inventive routing technique enables an edge server operating within a given CDN region to retrieve content (cacheable, non-cacheable and the like) from an origin server more efficiently by selectively routing through the CDN's own nodes, thereby avoiding network congestion and hot spots. The invention enables an edge server to fetch content from an origin server through an intermediate CDN server or, more generally, enables an edge server within a given first region to fetch content from the origin server through an intermediate CDN region. As used herein, this routing through an intermediate server, node or region is sometimes referred to as 'tunneling.'

Growing community of inventors

Pittsburgh, PA, United States of America

Gary Lee Miller