Network Security - Implement L3 Routing Table & ACL in C/C++

Explore how access control lists operate in routers and firewalls, named ACLs of permit or deny rules evaluated by protocol, source and destination addresses, and masks via longest prefix match.

Analyze how an IP packet is evaluated against an access control list to determine permit or deny decisions using longest prefix match, with specific versus generic rules and don't-care fields.

Demonstrates how a layer three forwarding device uses longest prefix match on an IPv4 routing table to forward packets, selecting the best matched route and default when necessary.

Explore the best matched principle for access control lists and routing tables, including long list prefix match with wild card bits, and review data structures and designs for ACLs.

We explain the routing table design using key terms prefix, mask, and wildcard, and illustrate how an IPv4 1.2.3.4/24 translates to 255.255.255.0 and its wildcard.

Introduce the amtrie data structure for IPv4 routing tables, detailing nodes storing effective prefixes with bitmaps, parent/child pointers, and a root, to support insert, delete, search, and longest-prefix-match.

Construct an ipv4 routing table using a prefix trie. Insert routes from the root via first bit decisions, creating zero/one/don't-care children and performing node splits.

Walk through the six-step route insertion algorithm with a concrete example, showing how a new prefix causes a node split, subtree transfer, and prefix reassignment, and discuss time complexity O(K).

Analyze how routing entries populate a tree structure, creating leaf and internal nodes, with leaves holding data and internal nodes null, while paths from root to leaf reveal prefix sums.

Use a route search algorithm with exact bit-by-bit matching and don't-care bits on a data structure. Traverse from root by effective prefixes to locate the matching leaf or report absence.

Follow the route deletion algorithm by locating the exact-matching leaf using the root search algorithm, delete the leaf, and convert the parent from a half node to a full node.

Explore deleting routes from a routing trie, using exact-match search to remove leaf nodes, merge nodes, and update the effective prefix, returning the root to an initialized state for lookups.

Explore the longest prefix match route lookup algorithm for a routing table, using IP header addresses and next-hop forwarding, including default routes and don't-care bit matching.

The lecture shows a route lookup using longest prefix match: convert the IP to 32-bit binary, traverse the data structure via a stack, and find the longest matching prefix.

Explore route lookup using a prefix tree to perform the longest-prefix match for an IPv4 address such as 1.2.3.5, including handling of the default route via the root.