CS 636 InternetworkingRamana KompellaSome slides courtesy of Cristian Estan at University of WisconsinCS 636 InternetworkingNetwork Algorithmics Interdisciplinary solutions Systems thinking Algorithmic thinkingCS 636 Internetworking Definition: Network algorithmics is the use of an interdisciplinary systems approach seasoned with algorithmic thinking, to design fast implementations of network processing tasks at servers, routers, and other networking devices.Network Bottlenecks How to reconcile ease of use and performance in networking Ease of use achieved via abstractions (e.g., socket interfaces, prefix-based forwarding) Without care, such abstractions prone to performance penalty Network algorithmics seeks to address this gap.CS 636 InternetworkingEndnode algorithmics Computation vs Communication:◦ Endnodes are general purpose computers Vertical versus Horizontal Integration:◦ Many companies supply subsystems◦ Kernels tolerate unknown and buggy apps. Complexity of computation:◦ End-node protocol functions (e.g., TCP) more complex compared to routersCS 636 InternetworkingArtifacts of endnode software Structure: ◦ Complexity and vastness leads to structured modular code Protection:◦ Need to protect apps from one another Generality:◦ Core routines are most general Scalability:◦ Simple data structures that work well under few connections become bottlenecksCS 636 InternetworkingEndnode bottlenecksCS 636 InternetworkingRouter Algorithmics Router used generically for other network devices ◦ bridges, switches, gateways, monitors, security Typically, special purpose devices devoted to networking◦ Little structural overhead within a router◦ Light-weight operating system.CS 636 InternetworkingForces affecting Routers Scale:◦ Scaling in bandwidth and population Services:◦ Very success of Internet requires guarantees in performance, security and reliabilityCS 636 InternetworkingRouter bottlenecksCS 636 InternetworkingWarm-up example Observation: Large frequency of uncommon characters within code Problem: Can we flag such packets for further observation ?CS 636 InternetworkingStage1: Strawman solution Initialize 256 counters to 0 Increment right counter for each byte Check whether any counter is above the threshold Problem: Slow. Adds a second pass over large array.CS 636 InternetworkingStage2: Can we ask for less Idea: “Please Mr. Architect, can we relax specification so that we flag if any count is over threshold, w.r.t, current and not total length”. Problem: Still two reads and one write to memory per byteCS 636 InternetworkingStage 2: Use algorithms. Avoid second pass by keeping max counter Actually scale that by the threshold Simple check at the end Problem: Still two reads and one write to memory per byteCS 636 Internetworking If C[i]/T[i] > Max then Max= C[i]/T[i]Stage 3: Exploit hardwareCS 636 Internetworking  Can use wide memories and coalesce two arrays to reduce to one read + one write. Problem: Hard to do divisions in hardwareStage 4: ApproximateCS 636 Internetworking  Idea: Have false positives anyway. So, approximate using powers of two.  Replace division by shifts. Problem: How to initialize the counters ?Stage 5: Lazily initializeCS 636 Internetworking  Do not initialize counters Distinguish old counters values due to previous packets using generation numbers◦ Need “scrubbing” of generation numbersNetwork Algorithmics Better hardware◦ At Gigabits, Terabits, we would need better tools such as wide word access etc. Better system decomposition:◦ Relax system specifications, shift functions in space or time◦ Approximating thresholds as powers of 2, lazy initialization Better algorithms: Clever ways of solving with different metrics and models.CS 636 InternetworkingFor next class: Implementation models◦ Hardware and architecture◦ Simple models that have explanatory and predictive power Read Chapter 2 of the book.CS 636