Routing Flashcards
Lowest OSI layer that deals with end to end transmissions
Network Layer
What determines the path the network takes
Routing Algorithms
What do Routing Algorithms do
Decide what path the network takes AND decides which output line an incoming packet should be transmitted on
Store and Forward
Packets sent to nearest router and that router verifies it and sends it onto the next router until it arrives at destination
Implementation of connectionless service
Packets injected into datagram network individually and routed independently. Packets called datagrams.
Implementation of connection oriented service
AKA Label-Switching. Path from source to destination setup for packets to be sent.
What does a connection oriented service avoid (In comparison to connectionless)
Avoids having to choose a new route for each packet
Differences between VC and Datagram
VC needs setup phase, Datagram wastes space with address. VCs guarantee QoS but are vulnerable to crashes.
Routing vs Forwarding
Which routers to use vs What happens when packet arrives.
Handles incoming packets
Routing
Handles routing tables
Forwarding
Routing Algorithm Features
Correctness, Simplicity, Robustness, Stability, Fairness, Efficiency.
Routing Algorithms should handle changes of
topography and traffic
Two classes of routing
Nonadaptive and Adaptive
Non-Adaptive
Do not base their decisions over estimates of network topology. Don’t respond to failures. Route computed in advance
Adaptive
Vary routing decisions according to changes in topology and traffic. Dynamic routing algorithms differ in where they obtain info from.
Optimality Principle
If Router A is on the optimal path from router B to router C then the optimal path from A to C falls on the same route
Sink trees
Used by algorithms, not necessarily unique.
Shortest Path Algorithm
Build a graph of the network with each node being a router and each edge being a communication line. Measure length by hops.
Dijkstra Algorithm
Finds shortest path between source and all destinations. Labeled by distance. Uses temporary and permanent paths
Permanent Path
A path is made permanent when they are 100% known to be the shortest route.
Flooding
Every incoming packet is sent out on every outgoing line besides the one it arrived on.
Problem with flooding
generates a lot of duplicate patterns and will become infinite without countermeasures
Shortest Path first protocol uses
Flooding
How to fix flooding
Add a hop count in packet header, decrement it at every hop and discard when = 0
If sender doesnt know path length
Initialize it to worst case
A better flooding technique
Flood Damming
Flood Damming
Having routes keep track of which packets have already been flooded. Can do this by putting a sequence of numbers on packet.
Flooding uses
ensures packets are delivered to every node, all messages transmitted can be received by other stations in range
Flooding Benefit
No other algorithm can produce shorter delay
Load balancer
Distributes incoming HTTP requests amongst servers in server farm to avoid overloading any one server
Load balancer in UNIX
Generates 3 load average numbers
System Load
Amount of computational work that a computer system performs.
Load Average
Represents average system load over a period of time
Idle computer load number
- Each process using or waiting for CPU increases by 1
Load average in single CPU systems
percentage of system utilization
How to get percentage system utilization with multiple CPUs
Load average/No. of CPUS
Why do busy sites employ 2 web servers
Can switch between them if one gets swamped
Facebook load balancer computes
load and determines which cluster to point each ISP’s user to. Handles traffic balancing and network optimization.
Components of Load balancer
DNS load balancer and Software load balancer
TinyDNS
by Bernstein Handles. Contains authorative nameserving. Only Clients are recursive nameserving - interpolates with relevant DNS standards.
Authorative Nameserving
via UDP, no recursive nameserving and does not respond to TCP
Facebook decision engine
Cartographer
Cartographer
Gathers info on topology, latency, bandwidth etc to determine best cluster point for each ISP. Pushes new DNS maps to server when cluster load is to be adapted to. Reacts to internal FB network problems and can deal with localized outages.
DNS Load Balancer consists of
central GLB decision engine, and open source C DNS server
Central GLB decision engine
making all traffic balancing decisions and generates DNS map.
Open Source C DNS Server
DNS traffic, directs users to clusters based on lookup table on DNS map.
Authorative DNS Service
Allows others to find your domain
Recursive DNS
allows you to resolve other people’s domains
When choosing a load balancer keep in mind:
Sticky or Stateless, and Software or Hardware
Sticky
routes user back to same server during the life of a session
Stateless
routes to most available server, based on internal algorithms
Software Load Balancer
Like NLB, effective but not fine grained like hardware
Hardware Load Balancer
Offloads all processing off web servers but can be complex to configure and administer
Web accelerators
Can cache pages, static assets and do RR load balancing for backend
Factor for sites with growing traffic
availability of solution into hosting provider selection process.
