Cisco Technology, Inc.

Ramot at Tel-aviv University Ltd.

Ramot University Authority for Applied Research and Industrial

Interdisciplinary Center Herzliya

Ramot University Authority

Riverhead Networks Inc.

Yehuda Afek

Dan Touitou

Anat Bremler-Barr

Guy Pazi

Yishay Mansour

Alon Golan

Sariel Har-Peled

Zvi Ostfeld

Yaron Koral

Rephael Tzadikario

Rafi Tzadikario

Rafi Zadikario

Keren Horvitz

Anat Bremler Barr

Anat Bremler

A method for processing communication traffic includes receiving an incoming stream of compressed data conveyed by a sequence of data packets, each containing a respective portion of the compressed data. The respective portion of the compressed data contained in the first packet is stored in a buffer, having a predefined buffer size. Upon receiving a subsequent packet, at least a part of the compressed data stored in the buffer and the respective portion of the compressed data contained in the subsequent packet are decompressed, thereby providing decompressed data. A most recent part of the decompressed data that is within the buffer size is recompressed and stored in the buffer.

Efficient processing of compressed communication traffic

Methods and apparatus for protecting against and/or responding to an overload condition at a node ('victim') in a distributed network divert traffic otherwise destined for the victim to one or more other nodes, which can filter the diverted traffic, passing a portion of it to the victim, and/or effect processing of one or more of the diverted packets on behalf of the victim. Diversion can be performed by one or more nodes (collectively, a 'first set' of nodes) external to the victim. Filtering and/or effecting traffic processing can be performed by one or more nodes (collectively, a &#x201c;second set&#x201d; of nodes) also external to the victim. Those first and second sets can have zero, one or more nodes in common&#x2014;or, put another way, they may wholly, partially or not overlap. The methods and apparatus have application in protecting nodes in a distributed network, such as the Internet, against distributed denial of service (DDoS) attacks.

Methods and apparatus for protecting against overload conditions on nodes of a distributed network

An improved network device that controls throughput of packets received thereby, e.g., to downstream devices or to downstream logic contained within the same network device. The network device comprises a scheduler that schedules one or more packets of a selected class for throughput as a function of a weight of that class and weights of one or more other classes. The weight of at least the selected class is dynamic and is a function of a history of volume of packets received by the network device in the selected class. An apparatus for protecting against overload conditions on a network, e.g., of the type caused by DDoS attacks, has a scheduler and a token bucket mechanism, e.g., as described above. Such apparatus can also include a plurality of queues into which packets of the respective classes are placed on receipt by the apparatus. Those packets are dequeued by the scheduler, e.g., in the manner described above, for transmittal to downstream devices (e.g., potential victim nodes) on the network.

Weighted fair queuing-based methods and apparatus for protecting against overload conditions on nodes of a distributed network

A method for authenticating communication traffic includes receiving a first request, such as a DNS request, sent over a network from a source address, to provide network information regarding a given domain name. A response is sent to the source address in reply to the first request. When a second request is from the source address in reply to the response, the authenticity of the first request is assessed based on the second request.

Protecting against spoofed DNS messages

A method of routing a data packet from a forwarding router to a downstream router. The data packet header includes an address that includes a bit string. The forwarding router looks up, in a forwarding database, a prefix that best matches the bit string. The forwarding router then attaches to the data packet a clue that is related to the best matching prefix, and forwards the data packet to the downstream router. The downstream router looks up, in a downstream database, and with reference to the clue, another prefix that best matches the bit string. Because the databases of neighboring routers are similar, the clue either directly determines the best matching prefix at the downstream router or provides the downstream router with a good starting point for its lookup.

Method for routing with a clue

A simple and fast algorithm for multi-dimensional packet classification by solving the best matching filter problem. The substantial part of the algorithm includes the search of filters being concurrently stabbed by the packet using a KD-tree data structure. Another aspect of the present invention includes the classification of the packet according to its destination address using a second data-structure which preferably consists of a one dimensional segment tree. In a preferred embodiment of the present invention, the packet is first classified according to its protocol type, then the packet is classified according to its destination address using a one dimensional segment tree data structure, and finally, a 6 dimension KD-tree is used to find the filters being stabbed by the remaining 3 parameters of the packet. Among the filters, which comply with the packet, the filter which applies to the packet is the filter with the highest pre-determined priority. Theoretical analysis predicts and experimental results verify that in practice, the proposed data-structure can handle a lot of &ldquo;difficult&rdquo; filters quickly and efficiently.

Method for fast multi-dimensional packet classification

A method for multiplexing the buffer space used to store messages of backlogged flows at the output port of a switch. The buffer space is partitioned among queues of variable length, with the first queue long enough to accommodate the largest expected backlog, the second queue long enough to accommodate the second-largest expected backlog, etc. Messages are dequeued from the queues for transmission in Round-Robin order. Incoming messages are enqueued in a manner that guarantees that messages of heavily backlogged flows tend to be enqueued in the longer queues, while preserving FIFO message order. If the messages are all of the same length, then the queues are partitioned into locations, of the same length as the messages, each location having an ordinal index in its queue, and the messages are enqueued so that each message of a particular flow is enqueued in a location with a different ordinal index. If the messages are of different lengths, the queues are partitioned into bins large enough to accommodate the longest messages, one or more messages may be stored in each bin, the round in which each incoming message is to be transmitted is computed in advance, and a similar enqueueing algorithm is used that is based on matching successive transmission rounds of messages of a given flow to successively indexed bins of different queues. The present invention may be used in any application involving Round Robin scheduling.

Space efficient fair queuing by stochastic Memory multiplexing

A constant space algorithm for rate based flow control in large computer networks. The switches in the network dynamically measure their unused link capacity, and signal sessions with higher rates to reduce their rates to that unused link capacity. Sessions with lower rates are allowed to increase their rates. This algorithm is suitable for both ATM networks and suitably modified TCP networks.

Growing community of inventors

Hod Hasharon, Israel

Yehuda Afek