公开(公告)号：US07647281B2

公开(公告)日：2010-01-12

申请号：US10782687

申请日：2004-02-19

申请人： Kamal Jain ,  Mohammad Mahdian ,  Amin Saberi

发明人： Kamal Jain ,  Mohammad Mahdian ,  Amin Saberi

IPC分类号： G06F17/00

CPC分类号： G06Q30/06 ,  G06Q30/0283 ,  G06Q40/04

摘要： The present invention leverages demarcation of an agent into both a demander and a supplier to provide a polynomial-time method of approximating a supply and demand system's equilibrium value. This provides, in one instance of the present invention, a simplified means to iteratively extract the equilibrium value. By providing demarcated data, the present invention accounts for both demand and supply effects of an agent within a modeled supply and demand system. In one instance of the present invention, a market equilibrium price vector is approximated by employing a revenue value generated for an agent in a current market equilibrium price iteration as a budget value for the agent in the next iteration. This permits market equilibrium value modeling that encompasses an agent's contributions to a market both as a buyer and a seller within the same market for a given good and/or service.

摘要翻译： 本发明利用代理商对需求者和供应商的划分，以提供近似供需系统的均衡值的多项式时间方法。 这在本发明的一个实例中提供了迭代地提取平衡值的简化方法。 通过提供划分的数据，本发明考虑了在建模的供应和需求系统内的代理的需求和供应效应。 在本发明的一个实例中，通过使用在当前市场均衡价格迭代中为代理产生的收入值作为下一次迭代中的代理的预算值来近似市场均衡价格向量。 这允许市场均衡价值模型，其包括代理人作为买方和卖方在同一市场中作为给定的商品和/或服务的贡献。

公开(公告)号：US20050180329A1

公开(公告)日：2005-08-18

申请号：US10780262

申请日：2004-02-17

申请人： Lili Qiu ,  Kamal Jain ,  Ranveer Chandra ,  Mohammad Mahdian

发明人： Lili Qiu ,  Kamal Jain ,  Ranveer Chandra ,  Mohammad Mahdian

IPC分类号： H04L12/26 ,  H04L12/28 ,  H04L12/56

CPC分类号： H04W16/18 ,  H04L45/122 ,  H04L45/20 ,  H04W74/08 ,  H04W80/00 ,  H04W88/16 ,  H04W92/02

摘要： Disclosed is a method for determining the placement of ITAPs in wireless neighborhood networks. The method disclosed provides for efficient integration of multi-hop wireless networks with the Internet by placing ITAPs at strategic locations. Initially the method provides for the formulation of the ITAP placement problem under three wireless models. For each model, methods are developed to efficiently place ITAPs in the networks. The methods aim to minimize the number of required ITAPs while guaranteeing users' bandwidth requirements. Next, a fault tolerance version of the placement method is presented that provides bandwidth guarantees in the presence of failures. Finally the methods are extended to take into account variable traffic demands by developing an approximation algorithm to simultaneously optimize ITAP placement based on demands over multiple periods.

摘要翻译： 公开了一种用于确定ITAP在无线邻域网络中的位置的方法。 所公开的方法通过将ITAP放置在战略位置来提供多跳无线网络与因特网的有效集成。 最初，该方法提供了三种无线模型下ITAP放置问题的制定。 对于每个模型，开发了有效地将ITAP放置在网络中的方法。 这些方法旨在最大限度地减少所需的ITAP数量，同时保证用户的带宽需求。 接下来，介绍了在出现故障时提供带宽保证的布局方法的容错版本。 最后，通过开发近似算法来扩展方法以考虑可变流量需求，以便在多个时期内根据需求同时优化ITAP布局。

公开(公告)号：US20050075104A1

公开(公告)日：2005-04-07

申请号：US10680549

申请日：2003-10-07

申请人： Kamal Jain ,  Jitendra Padhye ,  Venkata Padmanabhan ,  Lili Qiu

发明人： Kamal Jain ,  Jitendra Padhye ,  Venkata Padmanabhan ,  Lili Qiu

IPC分类号： H04L12/28 ,  H04L12/56 ,  H04W16/14 ,  H04Q7/20

CPC分类号： H04W16/14

摘要： Disclosed is a general model and method for computing performance bounds in multi-hop wireless networks. Rather than focusing on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, the present invention accommodates any given network, technology, interference model, routing paradigm, and workload. Using a conflict graph to formally characterize the impact of wireless interference on the performance of multi-hop wireless networks, methods for computing upper and lower bounds on the capacity of a given wireless network are detailed. Besides computing network capacity, the model and method disclosed can also enable or benefit other applications including maximizing fairness and minimizing maximum link utilization.

摘要翻译： 公开了一种用于计算多跳无线网络中的性能界限的通用模型和方法。 本发明不考虑在网络拓扑和/或工作负载中的均匀性或随机性假设下计算渐近性能界限，而是适应任何给定的网络，技术，干扰模型，路由范例和工作负载。 使用冲突图形式表征无线干扰对多跳无线网络性能的影响，详细描述了计算给定无线网络容量的上限和下限的方法。 除了计算网络容量之外，所公开的模型和方法还可以实现或受益于其他应用，包括最大化公平性并最小化最大链路利用率。

公开(公告)号：US08315196B2

公开(公告)日：2012-11-20

申请号：US10780262

申请日：2004-02-17

申请人： Lili Qiu ,  Kamal Jain ,  Ranveer Chandra ,  Mohammad Mahdian

发明人： Lili Qiu ,  Kamal Jain ,  Ranveer Chandra ,  Mohammad Mahdian

IPC分类号： H04H20/71

CPC分类号： H04W16/18 ,  H04L45/122 ,  H04L45/20 ,  H04W74/08 ,  H04W80/00 ,  H04W88/16 ,  H04W92/02

摘要： Disclosed is a method for determining the placement of ITAPs in wireless neighborhood networks. The method disclosed provides for efficient integration of multi-hop wireless networks with the Internet by placing ITAPs at strategic locations. Initially the method provides for the formulation of the ITAP placement problem under three wireless models. For each model, methods are developed to efficiently place ITAPs in the networks. The methods aim to minimize the number of required ITAPs while guaranteeing users' bandwidth requirements. Next, a fault tolerance version of the placement method is presented that provides bandwidth guarantees in the presence of failures. Finally the methods are extended to take into account variable traffic demands by developing an approximation algorithm to simultaneously optimize ITAP placement based on demands over multiple periods.

摘要翻译： 公开了一种用于确定ITAP在无线邻域网络中的位置的方法。 所公开的方法通过将ITAP放置在战略位置来提供多跳无线网络与因特网的有效集成。 最初，该方法提供了三种无线模型下ITAP放置问题的制定。 对于每个模型，开发了有效地将ITAP放置在网络中的方法。 这些方法旨在最大限度地减少所需的ITAP数量，同时保证用户的带宽需求。 接下来，介绍了在出现故障时提供带宽保证的布局方法的容错版本。 最后，通过开发近似算法来扩展方法以考虑可变流量需求，以便在多个时期内根据需求同时优化ITAP布局。

公开(公告)号：US07860506B2

公开(公告)日：2010-12-28

申请号：US12273082

申请日：2008-11-18

申请人： Kamal Jain ,  Jitendra D. Padhye ,  Venkata N. Padmanabhan ,  Lili Qiu

发明人： Kamal Jain ,  Jitendra D. Padhye ,  Venkata N. Padmanabhan ,  Lili Qiu

IPC分类号： H04W40/00

CPC分类号： H04W16/14

摘要： Disclosed is a general model and method for computing performance bounds in multi-hop wireless networks. Rather than focusing on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, the present invention accommodates any given network, technology, interference model, routing paradigm, and workload. Using a conflict graph to formally characterize the impact of wireless interference on the performance of multi-hop wireless networks, methods for computing upper and lower bounds on the capacity of a given wireless network are detailed. Besides computing network capacity, the model and method disclosed can also enable or benefit other applications including maximizing fairness and minimizing maximum link utilization.

摘要翻译： 公开了一种用于计算多跳无线网络中的性能界限的通用模型和方法。 本发明不考虑在网络拓扑和/或工作负载中的均匀性或随机性假设下计算渐近性能界限，而是适应任何给定的网络，技术，干扰模型，路由范例和工作负载。 使用冲突图形式表征无线干扰对多跳无线网络性能的影响，详细描述了计算给定无线网络容量的上限和下限的方法。 除了计算网络容量之外，所公开的模型和方法还可以实现或受益于其他应用，包括最大化公平性并最小化最大链路利用率。

公开(公告)号：US20090086652A1

公开(公告)日：2009-04-02

申请号：US12273082

申请日：2008-11-18

申请人： Kamal Jain ,  Jitendra D. Padhye ,  Venkata N. Padmanabhan ,  Lili Qiu

发明人： Kamal Jain ,  Jitendra D. Padhye ,  Venkata N. Padmanabhan ,  Lili Qiu

IPC分类号： H04W84/00

CPC分类号： H04W16/14

摘要： Disclosed is a general model and method for computing performance bounds in multi-hop wireless networks. Rather than focusing on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, the present invention accommodates any given network, technology, interference model, routing paradigm, and workload. Using a conflict graph to formally characterize the impact of wireless interference on the performance of multi-hop wireless networks, methods for computing upper and lower bounds on the capacity of a given wireless network are detailed. Besides computing network capacity, the model and method disclosed can also enable or benefit other applications including maximizing fairness and minimizing maximum link utilization.

摘要翻译： 公开了一种用于计算多跳无线网络中的性能界限的通用模型和方法。 本发明不考虑在网络拓扑和/或工作负载中的均匀性或随机性假设下计算渐近性能界限，而是适应任何给定的网络，技术，干扰模型，路由范例和工作负载。 使用冲突图形式表征无线干扰对多跳无线网络性能的影响，详细描述了计算给定无线网络容量的上限和下限的方法。 除了计算网络容量之外，所公开的模型和方法还可以实现或受益于其他应用，包括最大化公平性并最小化最大链路利用率。

公开(公告)号：US07469143B2

公开(公告)日：2008-12-23

申请号：US10680549

申请日：2003-10-07

申请人： Kamal Jain ,  Jitendra D. Padhye ,  Venkata N. Padmanabhan ,  Lili Qiu

发明人： Kamal Jain ,  Jitendra D. Padhye ,  Venkata N. Padmanabhan ,  Lili Qiu

IPC分类号： H04Q7/20

CPC分类号： H04W16/14

摘要： Disclosed is a general model and method for computing performance bounds in multi-hop wireless networks. Rather than focusing on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, the present invention accommodates any given network, technology, interference model, routing paradigm, and workload. Using a conflict graph to formally characterize the impact of wireless interference on the performance of multi-hop wireless networks, methods for computing upper and lower bounds on the capacity of a given wireless network are detailed. Besides computing network capacity, the model and method disclosed can also enable or benefit other applications including maximizing fairness and minimizing maximum link utilization.

公开(公告)号：US07409217B2

公开(公告)日：2008-08-05

申请号：US11474666

申请日：2006-06-26

申请人： Kamal Jain ,  Jitendra D. Padhye ,  Venkata N. Padmanabhan ,  Lili Qiu

发明人： Kamal Jain ,  Jitendra D. Padhye ,  Venkata N. Padmanabhan ,  Lili Qiu

IPC分类号： H04Q7/20

CPC分类号： H04W16/14

摘要： Disclosed is a general model and method for computing performance bounds in multi-hop wireless networks. Rather than focusing on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, the present invention accommodates any given network, technology, interference model, routing paradigm, and workload. Using a conflict graph to formally characterize the impact of wireless interference on the performance of multi-hop wireless networks, methods for computing upper and lower bounds on the capacity of a given wireless network are detailed. Besides computing network capacity, the model and method disclosed can also enable or benefit other applications including maximizing fairness and minimizing maximum link utilization.

摘要翻译： 公开了一种用于计算多跳无线网络中的性能界限的通用模型和方法。 本发明不考虑在网络拓扑和/或工作负载中的均匀性或随机性假设下计算渐近性能界限，而是适应任何给定的网络，技术，干扰模型，路由范例和工作负载。 使用冲突图形式表征无线干扰对多跳无线网络性能的影响，详细描述了计算给定无线网络容量的上限和下限的方法。 除了计算网络容量之外，所公开的模型和方法还可以实现或受益于其他应用，包括最大化公平性并最小化最大链路利用率。

公开(公告)号：US20060240835A1

公开(公告)日：2006-10-26

申请号：US11474666

申请日：2006-06-26

申请人： Kamal Jain ,  Jitendra Padhye ,  Venkata Padmanabhan ,  Lili Qiu

发明人： Kamal Jain ,  Jitendra Padhye ,  Venkata Padmanabhan ,  Lili Qiu

IPC分类号： H04Q7/20

CPC分类号： H04W16/14

摘要： Disclosed is a general model and method for computing performance bounds in multi-hop wireless networks. Rather than focusing on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, the present invention accommodates any given network, technology, interference model, routing paradigm, and workload. Using a conflict graph to formally characterize the impact of wireless interference on the performance of multi-hop wireless networks, methods for computing upper and lower bounds on the capacity of a given wireless network are detailed. Besides computing network capacity, the model and method disclosed can also enable or benefit other applications including maximizing fairness and minimizing maximum link utilization.

摘要翻译： 公开了一种用于计算多跳无线网络中的性能界限的通用模型和方法。 本发明不考虑在网络拓扑和/或工作负载中的均匀性或随机性假设下计算渐近性能界限，而是适应任何给定的网络，技术，干扰模型，路由范例和工作负载。 使用冲突图形式表征无线干扰对多跳无线网络性能的影响，详细描述了计算给定无线网络容量的上限和下限的方法。 除了计算网络容量之外，所公开的模型和方法还可以实现或受益于其他应用，包括最大化公平性并最小化最大链路利用率。

公开(公告)号：US10540665B2

公开(公告)日：2020-01-21

申请号：US12490413

申请日：2009-06-24

申请人： Eric Horvitz ,  Kamal Jain

发明人： Eric Horvitz ,  Kamal Jain

IPC分类号： G06Q30/02 ,  G06F16/41 ,  G06F16/958

摘要： A content provider may provide public access to a content item set, but may be unable to achieve sufficient revenue to sustain the administrative costs and ongoing development of the content item set. Instead, the content provider may develop relationships with one or more referrers (e.g., search engines.) When a user requests a content item, the content provider may determine whether the request results from a referral by a sponsoring referrer, and based on this determination may provide either a full version or a limited version of the content item. The referrer benefits by providing its users with free access to the content item set, which may be unavailable from non-sponsoring competitors, and in exchange may share advertising revenue with the content provider. This arrangement achieves sustaining sponsorship of the content provider while extending full and free access to the content item set to users of sponsoring referrers.