公开(公告)号：US07397761B2

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

申请号：US10357558

申请日：2003-02-04

申请人： Koushik Kar ,  Muralidharan S. Kodialam ,  Tirunell V. Lakshman

发明人： Koushik Kar ,  Muralidharan S. Kodialam ,  Tirunell V. Lakshman

IPC分类号： G01R31/08 ,  H04J1/16 ,  H04L1/00

CPC分类号： H04L45/08

摘要： A packet network employs restorable routing with service level guarantees. Restorable routing generates two disjoint paths through a network of nodes interconnected by links for a connection request demand between and ingress-egress node pair. Restorable routing employs minimum interference criteria to generate the two disjoint paths such that two disjoint paths cause little or no interference with demands of future connection requests between different ingress-egress pairs. Restorable routing generates maximum 2-route flows for the network ingress-egress node pairs to determine corresponding sets of 2-critical links. A reduced network is formed, its links are weighted based on criticality indices generated from the sets of 2-critical links, and the relatively optimal two disjoint paths are computed for the connection request. One of the two disjoint paths is selected as an active path for routing data of the connection request, and the other disjoint path is selected as the backup path.

摘要翻译： 分组网络采用具有服务级别保证的可恢复路由。 可恢复的路由通过通过链路互连的节点网络生成两条不相交的路径，用于连接请求和出入口节点对之间的连接请求。 可恢复路由采用最小干扰标准来生成两个不相交路径，使得两个不相交路径对不同入口到出口之间的未来连接请求的需求几乎没有干扰或没有干扰。 可恢复的路由为网络入口 - 出口节点对生成最大的2路由流，以确定相应的2关键链路集。 形成减少的网络，其链路基于从两个关键链路的集合产生的关键性指数进行加权，并且针对连接请求计算相对最佳的两个不相交路径。 选择两个不相交路径中的一个作为用于路由连接请求的数据的活动路径，并且选择另一个不相交路径作为备份路径。

公开(公告)号：US07359384B2

公开(公告)日：2008-04-15

申请号：US10348385

申请日：2003-01-21

申请人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Dimitrios Stiliadis

发明人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Dimitrios Stiliadis

IPC分类号： H04L12/56

CPC分类号： H04L47/521 ,  H04L47/28 ,  H04L47/50 ,  H04L47/56 ,  H04L49/254

摘要： A switch schedules guaranteed-bandwidth, low-jitter-traffic characterized by a guaranteed rate table (GRT) method. A rate matrix generated from collected provisioning information is decomposed into schedule tables by a low jitter (LJ) decomposition method. The LJ decomposition method imposes a set of constraints for the schedule tables: schedule tables are partial permutation matrices, weighted sum of the partial permutation matrices is greater than or equal to the weighted sum of the rate matrix, and each entry in the rate matrix belongs to one element of the LJ decomposition schedule matrices. An integer LJ decomposition programming problem is employed to generate the schedule tables that are scheduled for each time slot of the period of the switch. Schedule tables are selected in turn based upon selecting eligible tables having the earliest finishing time. If necessary, the rate matrix is updated prior to decomposition for a subsequent period.

摘要翻译： 交换机调度保证带宽，低抖动流量，其特征在于保证速率表（GRT）方法。 从收集的配置信息生成的速率矩阵通过低抖动（LJ）分解方法分解为调度表。 LJ分解方法对调度表施加一组约束：调度表是部分置换矩阵，部分置换矩阵的加权和大于或等于速率矩阵的加权和，并且速率矩阵中的每个条目都属于 到LJ分解调度矩阵的一个元素。 采用整数LJ分解编程问题来生成为交换周期的每个时隙调度的调度表。 根据选择具有最早完成时间的合格表，依次选择计划表。 如果需要，速率矩阵在分解之前在随后的时间段内被更新。

公开(公告)号：US06996065B2

公开(公告)日：2006-02-07

申请号：US09899508

申请日：2001-07-05

申请人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman

发明人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman

IPC分类号： G01R31/08

CPC分类号： H04L45/28 ,  H04L45/12 ,  H04L45/123 ,  H04L45/22

摘要： A packet network of interconnected nodes employing dynamic backup routing of a Network Tunnel Path (NTP) allocates an active and backup path to the NTP based upon detection of a network failure. Dynamic backup routing employs local restoration to determine the allocation of, and, in operation, to switch between, a primary/active path and a secondary/backup path. Switching from the active path is based on a backup path determined with iterative shortest-path computations with link weights assigned based on the cost of using a link to backup a given link. Costs may be assigned based on single-link failure or single element (node or link) failure. Link weights are derived by assigning usage costs to links for inclusion in a backup path, and minimizing the costs with respect to a predefined criterion.

摘要翻译： 采用网络隧道路径（NTP）的动态备份路由的互连节点的分组网络基于网络故障的检测，为NTP分配活动和备用路径。 动态备份路由使用本地恢复来确定主/主路径和辅助/备用路径之间的切换和运行。 从活动路径切换基于通过迭代最短路径计算确定的备份路径，其中链路权重基于使用链接备份给定链路的成本而分配。 可以基于单链路故障或单个元件（节点或链路）故障分配成本。 链路权重是通过将使用成本分配给用于包含在备份路径中的链接而导致的，并且使得相对于预定义准则最小化成本。

公开(公告)号：US20130060601A1

公开(公告)日：2013-03-07

申请号：US13225878

申请日：2011-09-06

申请人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sarit Mukherjee

发明人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sarit Mukherjee

IPC分类号： G06Q30/00

CPC分类号： G06Q30/02

摘要： A distribution and scheduling system for advertisements that targets ads to users and maximizes service-provider revenue without having full knowledge of user-profile information. Each user device stores a user profile and is pre-loaded with a set of ads that could possibly be shown during a timeslot. Each user device selects and displays an ad based on the user profile but does not identify the selected ad to the service provider. Instead, the user devices provide perturbed user-profile information in the form of Boolean vectors, which the service provider uses in conjunction with a guaranteed-approximation online algorithm to estimate the number of users that saw a particular ad. Thus, the service provider can charge advertisers for the number of times their ads are viewed, without knowing the users' profiles or which ads were viewed by individual users, and users can view the targeted ads while maintaining privacy from the service provider.

摘要翻译： 用于向用户展示广告的广告的分发和调度系统，并且在不了解用户简档信息的情况下最大化服务提供商收入。 每个用户设备存储用户简档，并且预先加载可能在时隙期间显示的一组广告。 每个用户设备根据用户配置文件选择并显示广告，但不将所选广告标识给服务提供商。 相反，用户设备以布尔向量的形式提供扰动的用户简档信息，服务提供商结合保证近似在线算法来估计看到特定广告的用户数量。 因此，服务提供商可以在不知道用户的个人资料或哪些广告被个人用户查看的情况下向广告客户收取广告的次数，并且用户可以在维护来自服务提供商的隐私的同时查看有针对性的广告。

公开(公告)号：US08018940B2

公开(公告)日：2011-09-13

申请号：US12190633

申请日：2008-08-13

申请人： Fang Hao ,  Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Haoyu Song

发明人： Fang Hao ,  Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Haoyu Song

IPC分类号： H04L12/56

CPC分类号： H04L45/00 ,  H04L45/745 ,  H04L45/7457

摘要： In one embodiment, IP lookup into a routing table having prefixes of different prefix lengths is performed using a Bloom filter that was programmed with the prefixes corresponding to all of the different prefix lengths without having to expand any of the prefixes programmed into the Bloom filter. Membership probes are performed into the Bloom filter using candidate prefix values of a given network address. The Bloom filter can be implemented in a distributed manner using Bloom sub-filters, where each Bloom sub-filter is hashed based on a set of hash functions, where each different hash function in the set corresponds to a different prefix length in the routing table. Each Bloom sub-filter can in turn be implemented using a plurality of practically realizable multi-port memory devices controlled by a port scheduler. False-positive matches can be detected and next-hop information for true-positive matches retrieved using an off-chip, hash-based prefix table.

摘要翻译： 在一个实施例中，使用具有与所有不同前缀长度相对应的前缀编程的布隆过滤器来执行具有不同前缀长度的前缀的路由表的IP查找，而不必将编程到布隆过滤器中的任何前缀扩展。 使用给定网络地址的候选前缀值对Bloom过滤器进行成员资格探测。 Bloom过滤器可以使用Bloom子过滤器以Bloom子过滤器实现，其中每个Bloom子过滤器基于一组散列函数进行散列，其中集合中的每个不同的散列函数对应于路由表中的不同的前缀长度 。 可以使用由端口调度器控制的多个实际可实现的多端口存储器件来实现每个Bloom子滤波器。 可以检测到假阳性匹配，并使用片外基于散列的前缀表检索真正匹配的下一跳信息。

公开(公告)号：US07957266B2

公开(公告)日：2011-06-07

申请号：US11106410

申请日：2005-04-14

申请人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sudipta Sengupta

发明人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sudipta Sengupta

IPC分类号： H04L12/26

CPC分类号： H04L45/12 ,  H04L45/04 ,  H04L45/24 ,  H04L47/125

摘要： A scheme for routing packets of traffic to their destination after ensuring that they pass through one or more pre-determined intermediate nodes, thereby permitting all permissible traffic patterns to be handled without knowledge of the traffic matrix, subject to edge-link capacity constraints. In one embodiment, a request for a path with a service demand for routing data between the ingress point and the egress point is received. A set of two or more intermediate nodes between the ingress point and the egress point is selected. Based on a bandwidth of the network, respective fractions of the data to send from the ingress point to each node of the set of intermediate nodes are determined. The data is routed in the determined respective fractions from the ingress point to each node of the set of intermediate nodes, and routed from each node of the set of intermediate nodes to the egress point.

摘要翻译： 一种用于在确保它们通过一个或多个预定中间节点之后将流量分组路由到其目的地的方案，从而允许所有允许的业务模式在不了解业务矩阵的情况下被处理，而不受边缘链路容量限制。 在一个实施例中，接收到对于在入口点和出口点之间路由数据的服务需求的路径的请求。 选择入口点和出口点之间的两个或多个中间节点的集合。 基于网络的带宽，确定从入口点向中间节点集合中的每个节点发送的数据的各个分数。 将数据以确定的各个分数从入口点路由到中间节点集合中的每个节点，并从中间节点集合的每个节点路由到出口点。

公开(公告)号：US07633867B2

公开(公告)日：2009-12-15

申请号：US10357557

申请日：2003-02-04

申请人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman

发明人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman

IPC分类号： G01R31/08

CPC分类号： H04L45/12 ,  H04L45/124 ,  H04L45/38

摘要： Capacity design of an optical network for demands of connections forms a linear programming sizing problem for a optimal routing. A dual of the linear programming sizing problem is formed and solved with an approximation algorithm. Edge lengths are initialized based on i) the inverse of the edge's capacity and ii) a scalar constant. Then, the approximation algorithm proceeds in phases to route each commodity over the edges of a graph. During each phase, the demand's flow is sent from the source to destination via multiple iterations. During each iteration, the shortest length-bounded path from the source to the destination is determined, a portion of the flow is sent, and the lengths of the edges that carry the flow are updated. The value employed to scale the network is generated after the last phase from the maximum ratio of edge flow to edge capacity.

摘要翻译： 用于连接需求的光网络的容量设计形成用于优化路由的线性规划大小问题。 线性规划大小问题的双重形成并用近似算法求解。 边缘长度基于i）边缘容量的倒数初始化，以及ii）标量常数。 然后，近似算法逐步进行，以在图的边缘上路由每个商品。 在每个阶段，需求流通过多次迭代从源到目的地发送。 在每个迭代期间，确定从源到目的地的最短长度有界的路径，发送流的一部分，并且更新携带流的边的长度。 用于缩放网络的值是在从边缘流量到边缘容量的最大比率的最后一个阶段之后生成的。

公开(公告)号：US20130254248A1

公开(公告)日：2013-09-26

申请号：US13427958

申请日：2012-03-23

申请人： Hyunseok Chang ,  Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sarit Mukherjee ,  Limin Wang

发明人： Hyunseok Chang ,  Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sarit Mukherjee ,  Limin Wang

IPC分类号： G06F17/30 ,  G06F15/167

CPC分类号： H04L67/1021 ,  G06F16/182 ,  H04L67/101

摘要： Various embodiments provide a method and apparatus of providing a distributed network file system in a cloud network that provides performance guarantees in cloud storage that are independent of the accessed files and the access locations. A client's file system is provisioned using a file placement strategy that is based on client's access locations and determined maximum access bandwidths and does not require knowledge of file access patterns.

摘要翻译： 各种实施例提供了一种在云网络中提供分布式网络文件系统的方法和装置，其在云存储中提供独立于所访问的文件和访问位置的性能保证。 使用基于客户端访问位置和确定的最大访问带宽的文件放置策略来配置客户端的文件系统，并且不需要知道文件访问模式。

公开(公告)号：US08194535B2

公开(公告)日：2012-06-05

申请号：US11141257

申请日：2005-05-31

申请人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sudipta Sengupta

发明人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sudipta Sengupta

IPC分类号： G01R31/08

CPC分类号： H04L45/12 ,  H04L45/04 ,  H04L45/24 ,  H04L47/125

摘要： In one embodiment, a method for supporting recovery from failure of a node in a network of nodes interconnected by links A set of two or more intermediate nodes (excluding the failed node) between an ingress point and an egress point is selected. Next, based on available bandwidth of the network, a non-zero fraction of the service level to route from the ingress point to each intermediate node is determined. Packets are then routed in two phases by: (1) determining one or more paths from the ingress point to each intermediate node for routing the corresponding fraction of the service level, and (2) determining one or more paths from each intermediate node to the egress point for routing the corresponding fraction of the service level.

摘要翻译： 在一个实施例中，选择用于支持通过链路互连的节点网络中的节点从在入口点和出口点之间的两个或多个中间节点（不包括故障节点）组成的恢复的方法。 接下来，基于网络的可用带宽，确定从入口点到每个中间节点路由的服务级别的非零分数。 然后，分组通过以下两个阶段路由分组：（1）确定从入口点到每个中间节点的一个或多个路径，用于路由服务级别的相应部分，以及（2）确定从每个中间节点到 出口点用于路由服务级别的相应部分。

公开(公告)号：US20100069074A1

公开(公告)日：2010-03-18

申请号：US12209655

申请日：2008-09-12

申请人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman

发明人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman

IPC分类号： H04W72/00

CPC分类号： H04W28/16

摘要： In one embodiment, a wireless-resource broker employs a self-enforcing spectrum-sharing policy, e.g., the expected utility (e.g., rate) a user obtains by following the policy provided by the broker is not less than the expected utility that the user obtains by switching to some other strategy. Each user is associated with one or more transmitter-receiver pairs, e.g., a transmitter of a wireless device and a receiver of a base station in communication via a wireless channel. The broker receives, as input, user parameters characterizing one or more of the transmitters and/or receivers and resource parameters characterizing one or more available spectrum blocks. The broker solves a linear-programming problem to generate and transmit a recommended policy for one or more users. The policy for each user includes information such as the spectrum block(s) to which the user is assigned, the transmission power for the user, and the transmission rate for the user.

摘要翻译： 在一个实施例中，无线资源代理使用自强制频谱共享策略，例如，用户通过遵循由代理提供的策略获得的预期效用（例如，速率）不小于用户所期望的效用 通过切换到其他策略获得。 每个用户与一个或多个发射机 - 接收机对相关联，例如无线设备的发射机和经由无线信道进行通信的基站的接收机。 代理人接收表征一个或多个发射机和/或接收机的用户参数以及表征一个或多个可用频谱块的资源参数作为输入。 经纪人解决了线性规划问题，为一个或多个用户生成和传送推荐的策略。 每个用户的策略包括诸如用户所分配的频谱块，用户的发送功率和用户的传输速率等信息。