公开(公告)号：US20150131655A1

公开(公告)日：2015-05-14

申请号：US14080202

申请日：2013-11-14

Applicant: Cisco Technology, Inc.

Inventor： Deepak Dayama ,  Raghava Sivaramu ,  Dhananjaya Rao ,  Nataraj Bacthu

IPC: H04L12/18 ,  H04L12/761 ,  H04L12/947 ,  H04L12/933 ,  H04L12/931 ,  H04L12/54 ,  H04L12/753

CPC classification number: H04W72/005 ,  H04L12/18 ,  H04L12/185 ,  H04L12/1886 ,  H04L12/189 ,  H04L12/4675 ,  H04L12/5601 ,  H04L45/00 ,  H04L45/02 ,  H04L45/16 ,  H04L45/48 ,  H04L49/1569 ,  H04L49/203 ,  H04L49/256 ,  H04W24/02 ,  H04W48/16

Abstract: Techniques are provided for optimizing multicast routing in a network. At a router device, a message is sent to one or more physical devices. The message is configured to solicit a response indicating a network assignment for each of the physical devices. A response message is received from each of the physical devices. The response message comprises network assignment information for each of the physical devices. For each of the physical devices, the network assignment information is translated into a segment identifier. The segment identifier is distributed to other router devices in the network

Abstract translation: 提供技术来优化网络中的多播路由。 在路由器设备上，向一个或多个物理设备发送消息。 消息被配置为请求指示每个物理设备的网络分配的响应。 从每个物理设备接收到响应消息。 响应消息包括用于每个物理设备的网络分配信息。 对于每个物理设备，网络分配信息被转换成段标识符。 分段标识符分发给网络中的其他路由器设备

公开(公告)号：US11570105B2

公开(公告)日：2023-01-31

申请号：US17244936

申请日：2021-04-29

Applicant: Cisco Technology, Inc.

Inventor： Ankan Ghosh ,  Nataraj Bacthu ,  Apurup Reddy Chevuru ,  Laxmi Kant Agrawal ,  Swaminathan Narayanan

IPC: H04L45/7453 ,  G06F3/06 ,  H04L45/00

Abstract: The present disclosure involves systems and methods for managing a trie routing table for a networking device of a communication or computer network. In one implementation, the networking device may utilize a dynamic algorithm for associating hashing functions with pivot tiles of the routing table to improve hash utilization and avoid hash collisions. Further, route prefixes may be relocated from pivot tiles in an attempt to free the tiles for reallocation to other prefix base width or may be relocated to other possible pivot tiles or to a general storage space when a hash collision is detected. This provides for even distribution of pivots within tiles which have base widths in range of a pivot route. The above implementations may occur together or separately to improve the operation of the networking device and provide faster route lookup.

公开(公告)号：US20210250296A1

公开(公告)日：2021-08-12

申请号：US17244936

申请日：2021-04-29

Applicant: Cisco Technology, Inc.

Inventor： Ankan Ghosh ,  Nataraj Bacthu ,  Apurup Reddy Chevuru ,  Laxmi Kant Agrawal ,  Swaminathan Narayanan

IPC: H04L12/743 ,  G06F3/06 ,  H04L12/701

Abstract: The present disclosure involves systems and methods for managing a trie routing table for a networking device of a communication or computer network. In one implementation, the networking device may utilize a dynamic algorithm for associating hashing functions with pivot tiles of the routing table to improve hash utilization and avoid hash collisions. Further, route prefixes may be relocated from pivot tiles in an attempt to free the tiles for reallocation to other prefix base width or may be relocated to other possible pivot tiles or to a general storage space when a hash collision is detected. This provides for even distribution of pivots within tiles which have base widths in range of a pivot route. The above implementations may occur together or separately to improve the operation of the networking device and provide faster route lookup.

公开(公告)号：US10404596B2

公开(公告)日：2019-09-03

申请号：US15723713

申请日：2017-10-03

Applicant: Cisco Technology, Inc.

Inventor： Ankan Ghosh ,  Nataraj Bacthu ,  Apurup Reddy Chevuru ,  Laxmi Kant Agrawal ,  Swaminathan Narayanan

IPC: G06F3/06 ,  H04L12/743

Abstract: The present disclosure involves systems and methods for managing a trie routing table for a networking device of a communication or computer network. In one implementation, the networking device may utilize a dynamic algorithm for associating hashing functions with pivot tiles of the routing table to improve hash utilization and avoid hash collisions. Further, route prefixes may be relocated from pivot tiles in an attempt to free the tiles for reallocation to other prefix base width or may be relocated to other possible pivot tiles or to a general storage space when a hash collision is detected. This provides for even distribution of pivots within tiles which have base widths in range of a pivot route. The above implementations may occur together or separately to improve the operation of the networking device and provide faster route lookup.

公开(公告)号：US20190104067A1

公开(公告)日：2019-04-04

申请号：US15723713

申请日：2017-10-03

Applicant: Cisco Technology, Inc.

Inventor： Ankan Ghosh ,  Nataraj Bacthu ,  Apurup Reddy Chevuru ,  Laxmi Kant Agrawal ,  Swaminathan Narayanan

IPC: H04L12/743 ,  G06F3/06

CPC classification number: H04L45/7453 ,  G06F3/061 ,  G06F3/0638 ,  G06F3/0673 ,  H04L45/00

Abstract: The present disclosure involves systems and methods for managing a trie routing table for a networking device of a communication or computer network. In one implementation, the networking device may utilize a dynamic algorithm for associating hashing functions with pivot tiles of the routing table to improve hash utilization and avoid hash collisions. Further, route prefixes may be relocated from pivot tiles in an attempt to free the tiles for reallocation to other prefix base width or may be relocated to other possible pivot tiles or to a general storage space when a hash collision is detected. This provides for even distribution of pivots within tiles which have base widths in range of a pivot route. The above implementations may occur together or separately to improve the operation of the networking device and provide faster route lookup.

公开(公告)号：US20190104066A1

公开(公告)日：2019-04-04

申请号：US15724092

申请日：2017-10-03

Applicant: Cisco Technology, Inc.

Inventor： Venkata Naga Ramesh Ponnapalli ,  Ayan Banerjee ,  Raghava K. Sivaramu ,  Nataraj Bacthu

IPC: H04L12/745 ,  H04L12/721 ,  H04L12/743

Abstract: In one embodiment, longest prefix matching (LPM) operations are performed on a value in multiple interspersed prefix length search spaces to determine an overall longest prefix matching result in a packet switching system. A first LPM lookup unit performs a first LPM operation on the particular lookup value in a first search space finding a first longest matching prefix, and a second LPM lookup unit performs a second LPM operation on the particular lookup value in a second search space finding a second longest matching prefix. The longer of the first and second longest matching prefixes determines the overall LPM. In one embodiment, the first search space and the second search space include non-default route prefixes with interspersed prefix lengths matching a same value, such as, but not limited to the particular lookup value (e.g., a destination address of a packet).

公开(公告)号：US10250399B1

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

申请号：US14734987

申请日：2015-06-09

Applicant: CISCO TECHNOLOGY, INC.

Inventor： Ayan Banerjee ,  Raghava K. Sivaramu ,  Srinivasan Ramabadran ,  Mehak Mahajan ,  Nataraj Bacthu

IPC: H04L12/18 ,  H04L12/931 ,  H04L12/741

Abstract: In accordance with one example embodiment, a system configured for programming a network layer multicast address entry in a routing table of an ingress line card module is disclosed. The network layer multicast address entry includes a network layer address associated with at least one egress line card. The system is further configured for programming a data link layer multicast routing address entry in a routing table of a fabric card module in which the data link layer multicast routing address entry corresponds to the network layer multicast address entry.

公开(公告)号：US20180212876A1

公开(公告)日：2018-07-26

申请号：US15414589

申请日：2017-01-24

Applicant: CISCO TECHNOLOGY, INC.

Inventor： Nataraj Bacthu ,  Ayan Banerjee ,  Raghava Sivaramu ,  Ankan Ghosh

IPC: H04L12/745 ,  H04L29/12 ,  H04L12/743

CPC classification number: H04L45/748 ,  H04L45/7457

Abstract: In one embodiment, a method includes receiving a request to add a prefix to memory for a route lookup at a forwarding device, the memory comprising a plurality of pivot tiles for storing pivot entries, each of the pivot entries comprising a plurality of prefixes and a pointer to a trie index, searching at the forwarding device, a dynamic pool of the pivot tiles based on a base-width associated with the prefix, allocating at least a portion of the pivot tile to the base-width and creating a pivot entry for the prefix and other prefixes with a corresponding base-width, and dynamically updating prefixes stored on the pivot tiles based on route changes to optimize storage of prefixes on the pivot tiles. An apparatus and logic are also disclosed herein.

公开(公告)号：US09504016B2

公开(公告)日：2016-11-22

申请号：US15040090

申请日：2016-02-10

Applicant: Cisco Technology, Inc.

Inventor： Deepak Dayama ,  Raghava Sivaramu ,  Dhananjaya Rao ,  Nataraj Bacthu

IPC: H04L12/18 ,  H04W72/00 ,  H04L12/54 ,  H04L12/761 ,  H04L12/753 ,  H04L12/933 ,  H04L12/931 ,  H04L12/947 ,  H04L12/701 ,  H04L12/751 ,  H04W24/02 ,  H04W48/16 ,  H04L12/46

CPC classification number: H04W72/005 ,  H04L12/18 ,  H04L12/185 ,  H04L12/1886 ,  H04L12/189 ,  H04L12/4675 ,  H04L12/5601 ,  H04L45/00 ,  H04L45/02 ,  H04L45/16 ,  H04L45/48 ,  H04L49/1569 ,  H04L49/203 ,  H04L49/256 ,  H04W24/02 ,  H04W48/16

Abstract: Techniques are provided for optimizing multicast routing in a network. At a router device, a message is sent to one or more physical devices. The message is configured to solicit a response indicating a network assignment for each of the physical devices. A response message is received from each of the physical devices. The response message comprises network assignment information for each of the physical devices. For each of the physical devices, the network assignment information is translated into a segment identifier. The segment identifier is distributed to other router devices in the network.

Abstract translation: 提供技术来优化网络中的多播路由。 在路由器设备上，向一个或多个物理设备发送消息。 消息被配置为请求指示每个物理设备的网络分配的响应。 从每个物理设备接收到响应消息。 响应消息包括用于每个物理设备的网络分配信息。 对于每个物理设备，网络分配信息被转换成段标识符。 分段标识符分发给网络中的其他路由器设备。