Transcript ppt
ECE 526 – Network Processing Systems Design Packet Processing II: algorithms and data structures Chapter 5: D. E. Comer Goal and Outline • Goal: ─ Understand basic network processing operations ─ Learn how to perform operations – data structures & algorithms • Outline: ─ ─ ─ ─ ─ IP fragmentation and reassembly IP forwarding and routing TCP connection recognition and splicing Summary For next class Ning Weng ECE 526 2 IP Fragmentation • Needed when datagram larger than network MTU ─ Ethernet 1500 Byte • FLAGs bits in datagram header Ning Weng ECE 526 3 Fragmentation Example • How to identify a fragment ─ Flags ─ Offset: multiple of 64 bit ─ Ident: unique to send machine Ning Weng ECE 526 4 IP Fragmentation Algorithm Ning Weng ECE 526 5 IP Reassembly • Process to join fragments and produce original datagram • Only ultimate destination perform IP reassembly (NAT: exception) • Four factors influencing reassembly ─ ─ ─ ─ Out of order delivery Duplication Loss Concurrent reception • Key fields help reassembly ─ Source IP address ─ ID field ─ Flags and Offset Ning Weng ECE 526 6 Reassembly Algorithm Ning Weng ECE 526 7 Reassembly Data Structure • Two parts ─ Buffer larger enough to hold original datagram ─ Linked list of pieces that have arrived Ning Weng ECE 526 8 IP Datagram Forwarding • Conceptual mapping ─ (next hop, interface) f(datagram, routing table) • Routing table ─ one entry per destination ─ entry contents: IP address, address mask, next-hop address and N-bit interface number • Example IP routing table Ning Weng ECE 526 9 IP Forwarding Algorithm Assuming: routing table sorted from most specific to less specific Can I use hashing? Ning Weng ECE 526 10 High-Speed Forwarding • Example routing tree Ning Weng ECE 526 11 Routing Exercises • Draw tire of the following prefixes: ─ ─ ─ ─ ─ ─ ─ A: 0010* B: 010* C: 0101* D: 0* E: 10* F: 1011* G: 100* • Which prefixes match the following lookups? ─ ─ ─ ─ 01 101 0001 1 Ning Weng ECE 526 12 TCP Connection Recognition • Key function of traffic monitors, firewalls and NAT • State of TCP connection ─ ─ ─ ─ Being established Completely established Being terminated Completely terminated (remove from record) • Code bits in TCP header: ─ Reset: • error occurred when one end has no record connection • regarded as a completely terminated here ─ Syn: • to start new connection • completely established need “see” syn from both sides ─ Fin: • to terminate connection • completely terminated need “see” fin from both sides Ning Weng ECE 526 13 TCP Connection Recognition Algorithm Ning Weng ECE 526 14 TCP Splicing • Join two TCP connections ─ Allow data to pass between them ─ To avoid termination overhead ─ By translating segment header fields • Acknowledgment number; sequence number Ning Weng ECE 526 15 TCP Splicing Algorithm Ning Weng ECE 526 16 Summary • Packet processing operations and algorithms ─ ─ ─ ─ Ethernet bridging (layer 2) IP fragmentation, reassembly and forwarding (layer 3) TCP splicing, connection recognition (layer 4) Flow classification (mixed layer) • Important data structure ─ ─ ─ ─ Linked list Hashing table Routing table Tire • Table lookup ─ Hashing ─ Full match for layer 2 ─ Longest prefix match (LPM) for layer 3 Ning Weng ECE 526 17 For Next Class • “Networking Algorithmics” ─ Chapter 17: Network Security (handout) Ning Weng ECE 526 18 Backup Ning Weng ECE 526 19