公开(公告)号：US08179898B2

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

申请号：US12482533

申请日：2009-06-11

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

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

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

CPC分类号： H04L45/00 ,  H04L45/742

摘要： Packets are processed (e.g., routed or classified) in accordance with a braided trie, which represents the combination of two or more different original tries (e.g., representing different forwarding/classification tables). The different tries are combined by twisting the mappings for specific trie nodes to make the shapes of the different tries more similar. Each node in the braided trie contains a braiding bit for at least one original trie indicating the mapping for that trie's node. Trie braiding can significantly reduce the number of nodes used to represent the different original tries, thereby reducing memory usage and improving scalability. Braided tries can be used for such applications as virtual routers and packet classification in which different forwarding/classification tables are represented by a single braided trie stored in shared memory.

摘要翻译： 数据包根据编织特技进行处理（例如，路由或分类），其代表两个或多个不同的原始尝试的组合（例如，表示不同的转发/分类表）。 通过扭转特定特里节点的映射来组合不同的尝试，使不同尝试的形状更相似。 编织特技中的每个节点包含至少一个原始特里的编织位，指示该特里节点的映射。 Trie编织可以显着减少用于表示不同原始尝试的节点数量，从而减少内存使用并提高可扩展性。 编织的尝试可以用于虚拟路由器和分组分类等应用，其中不同的转发/分类表由存储在共享存储器中的单个编织线索表示。

公开(公告)号：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.

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

公开(公告)号：US20110016206A1

公开(公告)日：2011-01-20

申请号：US12503265

申请日：2009-07-15

申请人： Muralidharan Sampath Kodialam ,  Tirunell V. Lakshman ,  Sarit Mukherjee ,  Limin Wang

发明人： Muralidharan Sampath Kodialam ,  Tirunell V. Lakshman ,  Sarit Mukherjee ,  Limin Wang

IPC分类号： G06F7/10 ,  G06F17/30 ,  G06F15/16

CPC分类号： G06Q30/02

摘要： Example methods include monitoring Internet traffic for a user, analyzing content of the Internet traffic, correlating the analyzed content with a simplified classifier set, ranking each correlated simplified classifier in the simplified classifier set, and storing the ranked simplified classifiers in a user interest profile for the user. Customer premise equipment may include a residential gateway, such as a wireless router, and user equipment such as a personal computer. Example systems may be configured from customer premise equipment or Internet service providers to generate user interest profiles in accordance with example methods.

摘要翻译： 示例性方法包括监视用户的互联网流量，分析因特网流量的内容，将所分析的内容与简化分类器集相关联，对简化分类器集合中的每个相关联的简化分类器进行排序，以及将排序的简化分类器存储在用户兴趣模式中 用户。 客户驻地设备可以包括诸如无线路由器的住宅网关以及诸如个人计算机的用户设备。 示例性系统可以由客户驻地设备或因特网服务提供商配置以根据示例方法生成用户感兴趣的简档。

公开(公告)号：US07710953B2

公开(公告)日：2010-05-04

申请号：US11693825

申请日：2007-03-30

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

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

IPC分类号： H04L12/50 ,  H04Q11/00

CPC分类号： H04L49/254 ,  H04L47/50 ,  H04L47/564 ,  H04L49/3045

摘要： The invention includes an apparatus and method for switching packets through a switching fabric. The apparatus includes a plurality of input ports and output ports for receiving arriving packets and transmitting departing packets, a switching fabric for switching packets from the input ports to the output ports, and a plurality of schedulers controlling switching of packets through the switching fabric. The switching fabric includes a plurality of virtual output queues associated with a respective plurality of input-output port pairs. One of the schedulers is active during each of a plurality of timeslots. The one of the schedulers active during a current timeslot provides a packet schedule to the switching fabric for switching packets through the switching fabric during the current timeslot. The packet schedule is computed by the one of the schedulers active during the current timeslot using packet departure information for packets departing during previous timeslots during which the one of the schedulers was active and packet arrival information for packets arriving during previous timeslots during which the one of the schedulers was active.

摘要翻译： 本发明包括一种用于通过交换结构交换分组的装置和方法。 该装置包括多个输入端口和输出端口，用于接收到达的分组并发送离开的分组，用于将分组从输入端口切换到输出端口的交换结构，以及多个调度器，用于控制通过交换结构的分组交换。 交换结构包括与相应的多个输入 - 输出端口对相关联的多个虚拟输出队列。 其中一个调度器在多个时隙的每一个期间是活动的。 在当前时隙中活动的调度器之一为交换结构提供了一个分组调度，用于在当前时隙内通过交换结构交换数据包。 分组调度由当前时隙中活动的调度器之一使用分组离开信息来计算，所述分组离开信息用于在之前的时隙期间离开的分组离开信息，在该时隙期间，一个调度器处于活动状态，并且分组到达信息用于在之前的时隙期间到达的分组 调度器是活跃的。

公开(公告)号：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）标量常数。 然后，近似算法逐步进行，以在图的边缘上路由每个商品。 在每个阶段，需求流通过多次迭代从源到目的地发送。 在每个迭代期间，确定从源到目的地的最短长度有界的路径，发送流的一部分，并且更新携带流的边的长度。 用于缩放网络的值是在从边缘流量到边缘容量的最大比率的最后一个阶段之后生成的。

公开(公告)号：US06341130B1

公开(公告)日：2002-01-22

申请号：US09146122

申请日：1998-09-02

申请人： Tirunell V. Lakshman ,  Dimitrios Stiliadis

发明人： Tirunell V. Lakshman ,  Dimitrios Stiliadis

IPC分类号： H04L1266

CPC分类号： H04L45/00 ,  H04L45/54 ,  H04L45/742 ,  H04L63/0263

摘要： A packet filter for a router performs generalized packet filtering allowing range matches in two dimensions, where ranges in one dimension at least one dimension is defined as a power of two. To associate a filter rule with a received packet EP, the packet filter employs a 2-dimensional interval search and memory look-up with the filter-rule table. Values of sm of filter-rule rm=(sm,dm) in one dimension are desirably ranges that are a power of two, such as prefix ranges, which are represented by a binary value having a “length” defined as the number of bits to of the prefix. The dm may be single points, ranges defined as prefix ranges, and/or ranges defined as continuous ranges. The packet filter employs preprocessing of the filter-rules based on prefix length as a power of 2 in one dimension and decomposition of overlapping segments into non-overlapping intervals in the other dimension to form the filter-rule table. A preprocessing algorithm searches in one dimension through filter rules and arranges the corresponding filter-rule rectangle segments according to prefix length. Then, in the other dimension, the overlapping filter rectangle segments are decomposed into non-overlapping intervals, and the highest priority filter-rule overlapping each non-overlapping interval is associated with that interval. A filter-rule table is then constructed with entries ordered according to prefix length and non-overlapping interval, each entry associated with a particular filter-rule. A packet classification algorithm then matches the field or other parameter information in the packet to the filter-rule table entries to identify the filter-rule rectangle associated with the filter-rule to be applied to the packet.

摘要翻译： 用于路由器的分组过滤器执行广义分组过滤，允许在二维中进行范围匹配，其中一维中的至少一维的范围被定义为二的幂。 为了将过滤规则与接收到的分组EP相关联，分组过滤器采用二维间隔搜索和存储器查找与过滤规则表。 一维中滤波器规则rm =（sm，dm）的sm的值优选为2的幂，例如前缀范围的范围，前缀范围由具有定义为位数的“长度”的二进制值表示 到前缀。 dm可以是单点，定义为前缀范围的范围，和/或定义为连续范围的范围。 分组过滤器使用基于前缀长度的过滤规则的预处理作为一维中的2的幂，并且将重叠段的分解在另一维度中的非重叠间隔中以形成过滤规则表。 预处理算法通过过滤规则在一维中进行搜索，并根据前缀长度排列相应的过滤规则矩形段。 然后，在另一个维度上，重叠的过滤器矩形段被分解成非重叠的间隔，并且与每个非重叠间隔重叠的最高优先级过滤器规则与该间隔相关联。 然后，根据前缀长度和不重叠间隔排序的条目构建过滤规则表，每个条目与特定过滤规则相关联。 然后，分组分类算法将分组中的字段或其他参数信息与过滤器规则表条目匹配，以标识与要应用于分组的过滤规则相关联的过滤规则矩形。

公开(公告)号：US5537446A

公开(公告)日：1996-07-16

申请号：US153538

申请日：1993-11-15

申请人： Tirunell V. Lakshman ,  Teunis J. Ott ,  Mohammed A. J. Tabatabai-Yazdi

发明人： Tirunell V. Lakshman ,  Teunis J. Ott ,  Mohammed A. J. Tabatabai-Yazdi

IPC分类号： H04L12/56 ,  H04N21/236 ,  H04N21/434 ,  H04Q11/04 ,  H04L7/00

CPC分类号： H04N21/434 ,  H04N21/236 ,  H04Q11/0478 ,  H04L2012/5616 ,  H04L2012/5636 ,  H04L2012/5649

摘要： A methodology and concomitant circuitry for smoothing delay sensitive traffic utilizes short term traffic forecasts and guarantees meeting a prespecified delay constraint. The pattern of incoming traffic is used to forecast estimates of future incoming data from the present and past incoming data. Corresponding to the estimate is a data rate for propagating stored data to produce a smoothed outgoing data rate, and the interval of time over which such a rate is used so as to satisfy the delay constraint. The estimation procedure is then re-invoked at the end to the time interval, which takes into account data arriving during the time interval, so as to determine the next succeeding data rate and a new time interval for propagating stored data.

摘要翻译： 用于平滑延迟敏感业务的方法和并发电路利用短期业务量预测和保证满足预先指定的延迟约束。 传入流量的模式用于预测来自当前和过去传入数据的未来传入数据的估计。 与估计相对应的是用于传播存储的数据以产生平滑的输出数据速率的数据速率，以及使用这种速率以满足延迟约束的时间间隔。 然后在时间间隔结束时重新调用估计过程，该时间间隔考虑了在时间间隔期间到达的数据，以便确定下一个后续数据速率和用于传播存储的数据的新的时间间隔。

公开(公告)号：US20180324082A1

公开(公告)日：2018-11-08

申请号：US15587649

申请日：2017-05-05

申请人： Fang Hao ,  Murali Kodialam ,  Tirunell V. Lakshman

发明人： Fang Hao ,  Murali Kodialam ,  Tirunell V. Lakshman

IPC分类号： H04L12/721 ,  H04L12/733 ,  H04W40/02

CPC分类号： H04L45/123 ,  H04L41/0823 ,  H04L43/0882 ,  H04L43/16 ,  H04L45/126 ,  H04L45/14 ,  H04L45/70 ,  H04W40/02

摘要： The present disclosure generally discloses improvements in computer performance for supporting use of shortest path routing in a communication network. The shortest path routing capability may be configured to support setting of link weights for use in shortest path routing. The shortest path routing capability may be configured to support setting of link weights for use in shortest path routing based on inverse optimization. The shortest path routing capability may be configured to support setting of link weights for use in shortest path routing based on distance between traffic matrices (e.g., distance between a requested traffic matrix and a routed traffic matrix). The shortest path routing capability may be configured to determine, based on the distance between a requested traffic matrix and a routed traffic matrix, whether to accept or reject a set of link weights for a network.

公开(公告)号：US09906460B2

公开(公告)日：2018-02-27

申请号：US14985652

申请日：2015-12-31

申请人： Randeep S. Bhatia ,  Fang Hao ,  Tirunell V. Lakshman ,  Harish Viswanathan

发明人： Randeep S. Bhatia ,  Fang Hao ,  Tirunell V. Lakshman ,  Harish Viswanathan

IPC分类号： H04L12/863 ,  H04L12/26 ,  H04L12/741 ,  H04L12/823 ,  H04L12/861

CPC分类号： H04L47/626 ,  H04L43/16 ,  H04L45/64 ,  H04L45/745 ,  H04L47/25 ,  H04L47/30 ,  H04L47/32 ,  H04L49/9036 ,  H04L49/9084

摘要： The present disclosure generally discloses a data plane configured for processing function scalability. The processing functions for which scalability is supported may include charging functions, monitoring functions, security functions, or the like.