公开(公告)号：US10715439B2

公开(公告)日：2020-07-14

申请号：US16541931

申请日：2019-08-15

Applicant: Cisco Technology, Inc.

Inventor： Naader Hasani ,  Shishir Gupta ,  David Delano Ward ,  Mohammed Ismael Tatar ,  Shahin Habibi ,  Sreedhar Ravipalli ,  David Richard Barach

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.

公开(公告)号：US10212069B2

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

申请号：US15377871

申请日：2016-12-13

Applicant: Cisco Technology, Inc.

Inventor： Naader Hasani ,  Mohammed Ismael Tatar ,  David Delano Ward

IPC: H04L12/761 ,  H04L12/18 ,  H04L12/741

Abstract: In one embodiment, 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 one embodiment, the selection of a nexthop for a destination node is made from a set of two or more nexthop nodes on different Equal-Cost Multi-Paths (ECMPs). In one embodiment, 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.

公开(公告)号：US20190036832A1

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

申请号：US15663084

申请日：2017-07-28

Applicant: Cisco Technology, Inc.

Inventor： John J. Williams, JR. ,  Naader Hasani ,  Mohammed Ismael Tatar ,  David Delano Ward

IPC: H04L12/801 ,  H04L12/861 ,  H04L12/875

CPC classification number: H04L47/34 ,  H04L47/56 ,  H04L49/25 ,  H04L49/9057

Abstract: In one embodiment, for each distribution period of time, each packet flow is assigned to a path through a packet switching device (e.g., switch fabric) with all packets of the packet flow being sent in order over the assigned path. For a next distribution period, different paths are assigned for these packet flows, with all packets being sent in order over the new corresponding selected path. In one embodiment, these paths are switched often enough to prevent congestion, yet infrequent enough so as to minimize resources for reordering. In one embodiment, the reordering is done at the egress and only for predefined high bandwidth flows (e.g., elephant flows). A distribution period indication is typically associated with each packet to identify its corresponding distribution period. In one embodiment, each routing and egress switching stage in a switching fabric performs reordering.

公开(公告)号：US10389633B2

公开(公告)日：2019-08-20

申请号：US15918288

申请日：2018-03-12

Applicant: Cisco Technology, Inc.

Inventor： Naader Hasani

IPC: H04L12/743 ,  H04L12/745

Abstract: In one embodiment, processing is performed based on the result of a lookup operation that determines a matching hash bucket entry, with each of the entries of the hash table spanning at least two memories. A first portion of the matching hash bucket entry is retrieved from a first random access memory from a first hash bucket stored at a first location identified based on a first particular hash function applied to a hash key. First current information of the hash key is determined to match the first portion. A second portion of the matching hash bucket entry is retrieved from a second random access memory from a second hash bucket stored at a second location identified based on a second particular hash function applied to the hash key. Second current information of the hash key is determined to match the second portion.

公开(公告)号：US10715455B2

公开(公告)日：2020-07-14

申请号：US15663084

申请日：2017-07-28

Applicant: Cisco Technology, Inc.

Inventor： John J. Williams, Jr. ,  Naader Hasani ,  Mohammed Ismael Tatar ,  David Delano Ward

IPC: H04L12/801 ,  H04L12/947 ,  H04L12/861 ,  H04L12/875

Abstract: In one embodiment, for each distribution period of time, each packet flow is assigned to a path through a packet switching device (e.g., switch fabric) with all packets of the packet flow being sent in order over the assigned path. For a next distribution period, different paths are assigned for these packet flows, with all packets being sent in order over the new corresponding selected path. In one embodiment, these paths are switched often enough to prevent congestion, yet infrequent enough so as to minimize resources for reordering. In one embodiment, the reordering is done at the egress and only for predefined high bandwidth flows (e.g., elephant flows). A distribution period indication is typically associated with each packet to identify its corresponding distribution period. In one embodiment, each routing and egress switching stage in a switching fabric performs reordering.

公开(公告)号：US20190372896A1

公开(公告)日：2019-12-05

申请号：US16541931

申请日：2019-08-15

Applicant: Cisco Technology, Inc.

Inventor： Naader Hasani ,  Shishir Gupta ,  David Delano Ward ,  Mohammed Ismael Tatar ,  Shahin Habibi ,  Sreedhar Ravipalli ,  David Richard Barach

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.

公开(公告)号：US10397115B1

公开(公告)日：2019-08-27

申请号：US15949060

申请日：2018-04-09

Applicant: Cisco Technology, Inc.

Inventor： Naader Hasani ,  Shishir Gupta ,  David Delano Ward ,  Mohammed Ismael Tatar ,  Shahin Habibi ,  Sreedhar Ravipalli ,  David Richard Barach

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.

公开(公告)号：US20180205654A1

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

申请号：US15918288

申请日：2018-03-12

Applicant: Cisco Technology, Inc.

Inventor： Naader Hasani

IPC: H04L12/743 ,  H04L12/745

CPC classification number: H04L45/7453 ,  H04L45/748

Abstract: In one embodiment, processing is performed based on the result of a lookup operation that determines a matching hash bucket entry, with each of the entries of the hash table spanning at least two memories. A first portion of the matching hash bucket entry is retrieved from a first random access memory from a first hash bucket stored at a first location identified based on a first particular hash function applied to a hash key. First current information of the hash key is determined to match the first portion. A second portion of the matching hash bucket entry is retrieved from a second random access memory from a second hash bucket stored at a second location identified based on a second particular hash function applied to the hash key. Second current information of the hash key is determined to match the second portion.

公开(公告)号：US20180167311A1

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

申请号：US15377871

申请日：2016-12-13

Applicant: Cisco Technology, Inc.

Inventor： Naader Hasani ,  Mohammed Ismael Tatar ,  David Delano Ward

IPC: H04L12/761 ,  H04L12/18 ,  H04L12/741

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

Abstract: In one embodiment, 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 one embodiment, the selection of a nexthop for a destination node is made from a set of two or more nexthop nodes on different Equal-Cost Multi-Paths (ECMPs). In one embodiment, 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.