US 10,855,621 B2 · Timestamp-based packet switching using a trie data structure

Abstract

System and method of network packet switching using a table representation of a trie data structure to identify a timestamp (TS) range (or time range) for a received packet based on the packet timestamp (TS). The trie data structure is programmed with a plurality of predetermined time ranges. Each node in the trie data structure corresponds to a TS prefix and is associated with a corresponding predetermined time range. A search engine in the network switch can use the packet TS as a key to traverse the trie data structure and thereby matching the packet TS to a predetermined time range according to a Longest Prefix Match (LPM) process. Provided with the TS ranges of the incoming packets, various applications and logic engines in the network switch can accordingly process the packets, such as determining a new destination IP address and performing channel switch accordingly.

Claims21

Dependent claims

A method of managing network traffic, said method comprising:

accessing a network packet that is received at an input interface of a network node of a communication network;
extracting a timestamp from said network packet;
generating a plurality of predetermined time ranges based on a user configuration;
traversing a table representation of a trie data structure to search for a predetermined time range from said plurality of predetermined time ranges, wherein said predetermined time range encompasses said timestamp, and wherein a respective node in said trie data structure corresponds to a timestamp prefix and is associated with a corresponding predetermined time range of said plurality of predetermined time ranges;
and
processing said network packet based on said predetermined time range.

3 more elements

A network switch comprising:

an ingress port configured to receive a network packet comprising a timestamp;
a trie generation unit configured to generate a plurality of predetermined time ranges based on a user configuration;
a memory configured to store a table representation of a trie data structure comprising nodes and links, wherein a respective node in said trie data structure corresponds to a timestamp prefix and is associated with a corresponding predetermined time range of said plurality of predetermined time ranges, and wherein each predetermined time range of said plurality of predetermined time ranges is defined by a start time and an end time;
a trie lookup engine configured to:
receive said timestamp;
and
traverse said table representation of said trie data structure to identify a predetermined time range matching said timestamp from said plurality of predetermined time ranges;
logic configured to process said network packet based on said predetermined time range;
and
an egress port configured to transmit said processed network packet over a communication link.

7 more elements

Dependencies are inferred from the claim text.

Timestamp-based packet switching using a trie data structure

Life of this patent

Timestamp-based packet switching using a trie data structure

Life of this patent

Abstract

Claims21