公开(公告)号：WO2019199615A1

公开(公告)日：2019-10-17

申请号：PCT/US2019/026153

申请日：2019-04-05

Applicant: CISCO TECHNOLOGY, INC.

Inventor： HASANI, Naader ,  GUPTA, Shishir ,  WARD, David Delano ,  TATAR, Mohammed Ismael ,  HABIBI, Shahin ,  RAVIPALLI, Sreedhar ,  BARACH, David Richard

IPC: H04L12/743 ,  H04L12/745

Abstract: One embodiment performs longest prefix matching operations in one or more different manners that provides packet processing and/or memory efficiencies in the processing of packets. In one embodiment, a packet switching device determines a set of one or more mask lengths of a particular conforming entry of a multibit trie or other data structure that matches a particular address of a packet via a lookup operation in a mask length data structure. A conforming entry refers to an entry which has less than or equal to a maximum number of different prefix lengths, with this maximum number corresponding to the maximum number of prefix lengths which can be searched in parallel in the address space for a longest matching prefix by the implementing hardware. The packet switching device then performs corresponding hash table lookup operation(s) in parallel in determining an overall longest matching prefix for the particular address.

公开(公告)号：WO2016060715A1

公开(公告)日：2016-04-21

申请号：PCT/US2015/040078

申请日：2015-07-12

Applicant: CISCO TECHNOLOGY, INC.

Inventor： HASANI, Naader

IPC: H04L12/743 ,  H04L12/745

CPC classification number: H04L45/7453 ,  H04L45/748

Abstract: In one embodiment, a packet switching device comprises: a lookup chip including one or more processors and on lookup chip memory, and off lookup chip memory. In one embodiment, the lookup chip is configured to determine processing information for packets including performing a longest prefix match on a destination address of packets using progressive, exact matching of one or more single prefix length hash keys generated from the packets with entries in one or more hash tables until a matching hash table entry is found. The matching hash table entry is associated with particular information identifying how to process (e.g., manipulate, forward, drop) the corresponding packet. In one embodiment, entries of a hash table are distributed between said on lookup chip memory and said off lookup chip memory. In one embodiment, signatures of lookup keys are included in a hash table entry to quickly evaluate whether there is a match.

Abstract translation: 在一个实施例中，分组交换设备包括：查找芯片，其包括一个或多个处理器和查找芯片存储器，以及关闭查找芯片存储器。 在一个实施例中，查找芯片被配置为确定分组的处理信息，包括使用从分组产生的一个或多个单个前缀长度散列密钥与一个或多个条目中的条目进行逐个精确匹配，对分组的目的地地址执行最长前缀匹配 更多的哈希表，直到找到匹配的哈希表条目。 匹配哈希表条目与识别如何处理（例如，操纵，转发，丢弃）相应分组的特定信息相关联。 在一个实施例中，散列表的条目分布在所述查找芯片存储器和所述关断查找芯片存储器之间。 在一个实施例中，查找密钥的签名被包括在散列表条目中，以快速评估是否存在匹配。

公开(公告)号：EP3777055A1

公开(公告)日：2021-02-17

申请号：EP19720230.2

申请日：2019-04-05

Applicant: Cisco Technology, Inc.

Inventor： HASANI, Naader ,  GUPTA, Shishir ,  WARD, David Delano ,  TATAR, Mohammed Ismael ,  HABIBI, Shahin ,  RAVIPALLI, Sreedhar ,  BARACH, David Richard

IPC: H04L12/743 ,  H04L12/745

公开(公告)号：EP3337110A1

公开(公告)日：2018-06-20

申请号：EP17183240.5

申请日：2017-07-26

Applicant: Cisco Technology, Inc.

Inventor： HASANI, Naader ,  TATAR, Mohammed Ismael ,  WARD, David Delano

IPC: H04L12/761 ,  H04L12/18 ,  H04L12/46

CPC classification number: H04L45/16 ,  H04L12/18 ,  H04L12/1886 ,  H04L45/74

Abstract: In embodiments, multicast packets including, but not limited to, Bit Index Explicit Replication (BIER) multicast packets, are forwarded in a network. An independent lookup operation is performed on each destination node identified in the received packet to determine a nexthop to which to forward a copy of the packet. Typically, some or possibly all of these lookup operations are performed in parallel, in contrast to the sequential lookup and bit masking operations of previous BIER packet forwarding specifications and implementations. In embodiments, the selection of a nexthop for a destination node is made from a set of two or more nexthop nodes on different Equal-Cost MultiPaths (ECMPs). In embodiments, compact data structures are used in determining how to forward the received multicast packet, with these compact data structures providing requisite forwarding information without allocating space to unassigned destination nodes.