Forwarding vs Routing
Forwarding: data plane - Directing a data packet to an outgoing link - individual router using a forwarding table Routing: control plane - computing paths the packets will follow - Routers talking amongst themselves - individual router creating a forwarding table.
Link State vs Distance Vector:
- DV error propogates, LS only computes its own table. - DV: convertence times varies (count-to-infinity problem), LS: O(n^2) algo requires O(nE) messages
Flow control vs Congestion control
Flow control: keeping one fast sender from overwhelming a slow receiver Congestion control : keep a set of senders from overloading the network
Connectionless: No handshaking between sending and recieving adapter.
Unreliable: receiving adapter doesnt send ACKs or NACKs; Packets passed to network later can have gaps; Gaps will be filled if application using TCP
Carrier sense: wait for link to be idle
Channel idle: start transmitting; Channel Busy: wait until idle
Collision detection: listen while transmitting
No collision: transmission is complete; Collision: abort transmission and send jam signal
-Advertise entire path
-Distance vector: send distance metric per dest d
-Path vector: send the entire path for each dest d
BGP path selection
BGP uses both policy and shortest path based routing.
Route learned from customer preferred over route learned from peer, preferred over route learned fromprovider
Congestion cntrl is preventing a set of senders from overwhelming the network, flow cntrl is preventing one fast sender from overwhelming a slow receiver.
Drop one flow, buffer and send after one is gone, reschedule on flow, ask both to reduce flow
Increase in net load results in a decrease of useful work -Causes: False trans, undelivered pckts
Simple Resource Allocation
is FIFO queue, drop tail (incoming) if buf full.
TCP Congestion Control
feedback based, hosted based, congestion window. Send at rate of slowest component, window = min(congestion, receiver wndw) Increase linearly, but half if there is a loss. (w <- w + w/1 or <- w/2) never below 1 MSS though. Congestion window is rep in BYTES because of MSS. #packets per window : CWND/MSS Inc per ACK : MSS*(MSS/CWND) Sending rate = Congestion Window size / RRT. Exponential fast start, because linear is too slow to start and wasteful starting @ 1 MSS/RRT and 1MSS cwnd.
Triple dup ACKs
multiplicative decrease. Timeout – start over @ 1MSS.
buffer small data if less than 1 MSS while waiting for ACK of outgoing packet. Basically sending 1 small packet per RTT. Batching bytes!
send ACK as part of a data packet from B->A if data generated within wait time of 200 – 500 msec.
carrier sense multiple access w/ collision detection
is connectionless and unreliable
no loops in topology.(no cycles) Select switch with smallest ID as root. Initially each switch thinks its root and sends msg (X,0,X). add1 to distance from neighbor node from root. (Root, dist to root, self)
Cut thru switching
start transmitting as soon as possible. Overlapping transmissions (transmit head of packet while still receiving tail)
Switch over router
PnP, Fast filtering and fwd, cut thru
Interior Routing Protocols (IGP)
uses distance vector; updates sent every 30 seconds; no authentication; not used much anymore
Link-state updates sent (using flooding) as ad when required; Every router runs Dijkstra's algorithm; Authenticated updates; widely used
Different devices switch different things:
physical later: electrical signals (repeaters and hubs)
link layer: frames (bridges and switches)
network layer: packets (routers)
Link Layer / Error Detection / Correction
Low to high if 0, High to low if 1.
invert on every 1, do nothing if 0.
more efficient than Manchester, map data bits to code bits 80%
mark start and end of frames from stream of bits. Use a flag 0x7E
distance / speed of light, Transm D = message/rate bps
2 * one way delay (latency)
Prop + Trans + Queue = Arrival - Departure
measures data in flight = Bandwidth * latency
latency=M/R + SUM(Prop_i)
Actual end to end latency
SUM(Transp_i + Prop_i + Q_i)
detect and retransmit, typically at higher levels (Network +)
FEC (Forward error checking)
correct codes, good for real-time, less retransmissions.
CRC (cyclic redundancy check)
divide n bits of data by C(x), compare to k bits
tells us how much error can safely be tolerated. d+1 Detect. 2d+1 correction
Internet Topology and Routing
physical location access point to internet. Large dense population, part of backbone
>= 2 providers, better performance, extra reliability, financial leverage through competition
artificially inflate AS path length seen by others to convince some AS's to send traffic another way (Export policy)
Learn multiple routes, pick one with policy
distributes BGP info within AS, sessions between routers, maps an egress point to out link. BGP incremental updates, maps dest prefix to egress point
Causes of BGP routing
Topol changes, changes in routing policy, BGP session failure, conflicts in protocols in diff AS's
Software Defined Networking
Vertically integrated Closed, proprietary Slow innovation -> horizontal, open interface, rapid innovation. OS abst.
has global view of network to make decisions. Control plane is in one place. Distributed sys. Control program operates on top of network OS.
IP Tunneling - packet delivery service with new routing strategies
delivering same data to many receivers
resilient overlay network. Increase performance and reliability of routing, more than IP. Adapts to congestion
A logical network built on top of a physical network. tunnels between host computers. Hosts implement new protocols and services. Effective way to build networks on top of the internet. P2P
centralized directory, gnutella –query flooding, kazaa-super nodes, bittorrent- distributed downloading/no free loading BitTorrent prevents free riding: Allow the fastest peers to download from you. Occasionally let some free loaders download
availability, protection, authenticity, data integrity, privacy
Make so many sessions it runs out of memory
Attacker guesses TCP seq# for an existing connection. Attacker can send rst to close cnnctn.
make target trust attacker using reverse DNS, take control of DNS server that target talks to and find a trusted connection.
send short ttl for dns query, target requests IP of your domain, but feed IP of private server.
expose trusted connection, predict Seq # from SYN and predict port => guess state. Now Impersonate one end and send packets.
Stateful Packet Filter
only allow traffic initiated by client. Track all conn.
End to End principle
Design principle for the internet that says you should keep functionalities at the end-hosts (Application specific functions)
Random Early Detection (RED)
randomly drop packets to signal congestion before it happens as queue fills up. Probability is prop queue size. If below a threshold, don’t drop anything. Use average queue len to allow short term bursts. -RED is hard to use, must have the right parameters to work. -Desynchronizes senders to have stead aggregate flow, not bursty.
Explicit Congestion Notification (ECN)
router marks packets with ECN bit, 2 bits 1 for ECN enabled and 1 for congestion in IP TOS. Must be supported by end hosts and router to work. But better since it does not drop packets like RED.
NAT soft state
if no packets arrive in time window, then delete mapping.
filters packets based on src/dst IP addr, TCP/UDP src/dst port, ICMP type, TCP SYN and ACK bits
rate limiting certain traffic like p2p Inspecting every packet is challenging on high speed links. Place complicated firewall rules on edge low speed, and simple in core high speed.
users must login, only point that accepts telnet. (central, caching) 1-Detailed policies 2-Avoid rogue machines 3-central logging 4-caching
Pros: Fewer IPs, Blocking unwanted traffic, Making fair use of net resources, Improcing web performance. Cons: No longer globally unique, no longer assume simple delivery of packets