Network Architecture Exam 2

flow control

receiver controls sender, so sender won’t overflow receiver’s buffer by transmitting too much, too fast

How flow control works

TCP receiver “advertises” free buffer space in rwnd field in TCP header
Sender limits amount of unACKed (“in-flight”) data to received rwnd

Guarantees receive buffer will not overflow

TCP congestion control: AIMD

Approach: senders can increase sending rate until packet loss (congestion) occurs, then decrease sending rate on loss event
Additive Increase: increase sending rate by 1 maximum segment size every RTT until loss detected

Multiplicative Decrease: cut sending rate in half at each loss event

Subnets

Device interfaces that can physically reach each other without passing through an intervening router

Dynamic Host Configuration Protocol (DHCP)

dynamically get IP address from a server

Hosts can renew the allocated IP addresses

Can return more than just allocated IP address:

Address of first-hop router for client

Name and IP address of DNS server

Network mask

NAT: network address translation

All devices in local network have 32-bit addresses in a “private” IP address space (10/8, 172.16/12, 192.168/16 prefixes) that can only be used in local network

Destination-based forwarding

Forward based only on destination IP address

Routing (forwarding) table: determine where data packets traveling over an IP network will be directed

Longest prefix matching

when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.

Scheduling policies

FCFS: packets transmitted in order of arrival to output port

Priority scheduling: Multiple queues with different classes

Round Robin (RR) scheduling: Multiple queues. Send packets from each in turn

Dijkstra’s link-state routing algorithm

Centralized: network topology, link costs known to all nodes

Computes least cost paths from one node (“source”) to all other nodes

Iterative: after k iterations, know least cost path to k destinations

Bellman-Ford algorithm

Distance vector algorithm: router knows physically connected neighbors, link costs to neighbors (Distributed)

Routing decisions are made at each node in a cooperative manner. Information is exchanged with neighbors.

Intra-AS

Routing among routers within same AS (“network”)

All routers in AS must run same intra-domain protocol

Routers in different AS can run different intra-domain routing protocols

Gateway router: at “edge” of its own AS, has link(s) to router(s) in other AS’es

Inter-AS

Routing among AS’es

Gateways perform inter-domain routing (as well as intra-domain routing)

Intra-AS routing

RIP: Routing Information Protocol [RFC 1723]

OSPF: Open Shortest Path First [RFC 2328]

EIGRP: Enhanced Interior Gateway Routing Protocol

OSPF(Open Shortest Path First)

Classic link-state

Each router floods OSPF link-state advertisements (LSA) to all other routers in entire AS

Each router has full topology, uses Dijkstra’s algorithm to compute forwarding table

RIP (Routing Information Protocol)

each router sends its whole routing table to its neighbors about every 30 seconds.

Internet inter-AS routing: BGP

Allows subnet to advertise its existence, and the destinations it can reach, to rest of Internet

Provides each AS a means to:

obtain/advertise destination network reachability info from neighboring ASes (eBGP)

Determine routes to other networks based on reachability information and policy

propagate reachability information to all AS-internal routers (iBGP)

Path attributes and BGP routes

prefix + attributes

Path prefix: destination being advertised

Two important attributes:

AS-PATH: list of ASes through which prefix advertisement has passed

NEXT-HOP: indicates specific internal-AS router to next-hop AS

Policy-based routing:

Gateway receiving route advertisement uses import policy to accept/decline path

AS policy also determines whether to advertise path to other neighboring ASes

hot potato routing

choose local gateway that has least intra-domain cost. Ignore inter-domain cost

eBGP

Between routers in different ASes. Peers are usually directly connected.

Purpose: learn about prefixes reachable through neighboring ASes, and advertise your own AS’s prefixes to them.

AS-PATH is prepended at each AS hop. A router rejects any route whose AS-PATH already contains its own AS number, which prevents loops.

NEXT-HOP is set to the advertising router’s interface.

iBGP (internal BGP)

Between routers in the same AS

distribute eBGP-learned routes to all routers inside the AS, so interior routers know how to reach external prefixes

Why AIMD?

optimize congested flow rates network wide!

has desirable stability properties

What is sthresh

TCP’s slow start threshold, a congestion-control variable. It marks the congestion window (cwnd) size at which TCP switches from slow start to congestion avoidance

How does sthresh work

Slow start (cwnd < ssthresh): cwnd roughly doubles every RTT, growing by 1 MSS for each ACK received.

Congestion avoidance (cwnd ≥ ssthresh): cwnd grows linearly, by about 1 MSS per RTT.

Timeout: ssthresh = cwnd/2, then cwnd = 1 MSS and TCP restarts slow start.

Network Layer: Forwarding

move packets from a router’s input link to appropriate router output link

Network Layer: Routing

determine route taken by packets from source to destination

IP addressing: CIDR

Subnet portion of address of arbitrary length

Address format: a.b.c.d/x, where x is # bits in subnet portion of address

DHCP interactions

Discover: the new host has no IP address and doesn’t know where a server is. It broadcasts “is there a DHCP server out there?”

Offer: a server replies with “your ip addr“ and the lease time

Request: the client picks one offer and broadcasts a request to accept it

Acknowledge: the chosen server confirms the assignment and the lease

Input port queuing

If switch fabric slower than input ports combined -> queueing may occur at input queues

Queueing delay and loss due to input buffer overflow!

Output port buffering

required when datagrams arrive from fabric faster than link transmission rate

Queueing (delay) and loss due to output port buffer overflow!

Hierarchical addressing

A structured way of assigning addresses to network devices in multiple levels or layers, similar to a postal address system

Aggregating addresses

Efficient routing: reduces the size of routing tables, easy to lookup

Limits broadcast traffic

Easier administration and troubleshooting