6.02 - Dictionary of common networking terms
Katrina LaCurts - lacurts@mit.edu

These entries are here to give you intuition, not precision.  For
detailed explanations of any term, please see the course notes or
lecture notes.

======================================================================

ACK-clocking - A term given to the phenomenon in sliding-window where
the rate that ACKs are received dictates, to an extent, the rate at
which data is sent (because a sliding-window sender only puts a new
packet into the network once it has received an ACK).  ACK-clocking
prevents the sender from sending too fast.

Acknolwedgments (ACKs) - A technique used in reliable transport
protocols.  When the reliable receiver receives a packet, it will
acknowledge the receipt of the packet by sending an acknowledgment, or
ACK, back to the sender.  An ACK packet will contain the sequence
number of the packet it is acknowledging, so the sender will be able
to differentiate an ACK for packet 1 from an ACK for packet 2, e.g.

Addressing - The process of naming entities (typically nodes and
links) in a network

(Routing) Advertisements - The messages sent by distributed routing
protocols such as distance-vector and link-state to propagate
information about the network topology throughout the network.  The
format and process by which these are sent depends on the protocol.

ALOHA - A method of channel access where nodes each send with
probability p.  In Stabilized ALOHA, p is increased or decreased
depending on whether a transmission succeeds or collides.

Application - The software that runs "on top" of the network.
Netflix, Facebook, etc. are examples of applications.  Applications
generally require reliable transport.

Backlogged - A node is backlogged if it has packets to send.

Bandwidth-delay Product - B * RTT_min, where B is the rate of the
bottleneck link on the path, and RTT_min is the minimum RTT (i.e., the
RTT when queueing delay = 0).  In a sliding-window protocol with a
fixed window size, the best case is to have W = B * RTT_min (or
slightly higher in the presence of loss).

Burst - In many networks, data is sent in bursts: a node might send a
series of packets back-to-back, and then no packets for a few second,
and then another "burst" of packets, etc.  Contrast this to a
continuous workload, where nodes have one packet to send every x
seconds.

Capture Effect - When a node captures the channel, i.e., continually
sends on it at the expense of other nodes not sending (typically the
capture effect in one node causes starvation in another).

Carrier Sense - When nodes listen on the channel before sending, to
check whether the channel is idle (they only send if it's idle).

Circuit Switching - a method of sharing networks common in land-line
phone networks.  Involves explicit setup/teardown phases, most useful
when traffic in the network is sent at a constant rate.

Chebyshev's Inequality - States that if X is a random variable with a
finite mean mu and a finite non-zero variance sigma^2, then for any
real number k, then P(|X - mu| >= k*sigma) <= 1/k^2.  This is a
conservative theorem, but its virtue is that it holds for all
distributions.  We use it to help set the retransmission timeout,
since we do not know the underlying RTT distribution.

Collision - If we are sharing the channel via time-division, two
packets collide when they are sent at the same time on the same
channel.

Congestion - A network is congested if many of the queues in the
network are full (and thus packets are dropped).  Informally, we will
sometimes use the term congestion when queues are almost full, such
that packets aren't dropped, but are experiencing high delays.

Connected - Two nodes are connected if they can communicate with one
another.

Contention/Contention Protocol - A channel access protocol where
allocation is *not* pre-determined; nodes _contend_ for the medium.
ALOHA is an example of a contention protocol.

Contention Windows - An alternate way to implement Stabilized ALOHA;
see PS7.

Convergence - A routing protocol has converged if route validity and
path visibility are satisfied at all nodes.

Convergence Time - The time it takes a routing protocol to converge
after a series of changes have been made (assuming no further changes
and no lost advertisements or HELLO messages).

Count-to-Infinity Problem - The problem that occurs in certain
distance-vector topologies when a link goes down.  A particular
sequence of advertisements can lead to nodes assuming they have routes
to a destination when they don't; as advertisements continue, the cost
of these supposed routes will increase until they reach INFINITY.  See
Lecture 21 for numerous examples.

CSMA - Carrier Sense Multiple Access.  In CSMA, nodes sense the
channel before transmitting (and only transmit if they sense the
channel to be idle).

Deadlock - A state when both endpoints in a connection are waiting for
something to happen and neither can proceed.

Delay - The amount of time it takes a single packet to traverse the
network.  Includes propagation delay, transmission delay, queueing
delay, and processing delay.

Demultiplexing - The reverse process of multiplexing (see the
multiplexing entry).

Distance-Vector Routing - A distributed routing protocol.  Nodes send
advertisements to their neighbors with their current best costs to all
nodes in the network.  Integration is via Bellman-Ford.

Draining - The term we typically give to removing packets from a queue
(i.e., packets are drained from a queue; the queue drains packets,
etc.)

Dynamism - The ability to handle variability in user behavior.

Eventual Convergence - A routing protocol satisfies eventual
convergence if it converges in a finite amount of time after a series
of changes have happened in the network (assuming no further changes
and no lost advertisements/HELLO messages).

Exponentially-weighted Moving Average (EWMA) - A different way to
average, where ewma[n] = alpha * new_sample + (1-alpha)ewma[n-1].  0
<= alpha <= 1.  The great alpha is, the more influence the most recent
sample has on the average.  EWMAs come up a lot in networking.  For
our context, they're used to set the retransmission timeout.

Fairness - In 6.02, a protocol is fair if all nodes get an equal share
of the channel.  We measure it as F = ( sum_i=1^N x_i )^2   / ( N *
sum (x_i^2) ), and F = 1 implies perfect fairness.  Outside of 6.02,
there are many other definitions of fairness, though ours is a common
one.

Forwarding - When a switch receives a packet, it must decide what to
do with it.  It uses information in the header of the packet, as well
as information in the routing table, to determine which outgoing
interface to send the packet on; this process is known as forwarding
(it also decrements the packet's hop-count).  Forwarding is related to
routing, but is not the same (notably, forwarding happens per-packet;
routing is done in the background on longer timescales).

Frames - The units of data that are sent during circuit switching.
Like packets, except they don't include a header, and so have no
information about the source or destination address of the data.

HELLO Protocol - The protocol that nodes use to discover failures
between themselves and their neighbors.

Hop-limit - A field in the packet header that specifies how many hops
a packet is allowed to travel in the network before being discarded.
This is meant to lessen the effects of routing loops.

Latency - A loaded term.  In 6.02, we will often use it as a synonym
for propagation delay, but in reality, it's the term used for the
entire one-way (or round-trip) delay of a packet.  Because of this
confusion, we will try to be very precise when using it.

Link-state Routing - A distributed routing protocol.  Nodes'
advertisements contain the link costs to their neighbors, and are
received by all other nodes in the network via flooding.  Integration
is via Dijkstra's Algorithm.

Link Cost - How expensive it is for a packet to traverse a link.  In
minimum-cost routing protocols, nodes prefer the route with the lowest
cost.  In reality, link costs can reflect things like network
congestion, delay, etc.  Link costs cannot be negative, they do not
need to obey the triangle inequality, and they can change.

Little's Law - Relates the average number of packets in a queue, N, the
average per-packet delay, D, and the average arrival/departure rate,
lambda: N = lambda * D.

Minimum-cost Path - Of all possible paths between A and B, the
minimum-cost path is the one with the lowest cost (we calculate path
cost by summing up the cost of the links on the path).

Multiplexing - Combining multiple signals into one.  In networking,
this term often comes up in the context of combining multiple
connections into one stream of traffic.

Multiplicative Decrease - When we take a variable and decrease it by a
multiplicative constant, e.g., p = p/2 in Stabilized ALOHA.  In more
advanced network protocols that we won't cover in 6.02, the decrease
rule for a variable, and whether it's multiplicative, is of large
concern.

Network Layer - In layered models of the Internet, the network layer
contains routing, addressing, and forwarding.  It is the "glue" that
holds networks together.  It takes us from point-to-point connections
to interconnected networks.

Node - The entities that make up a network; the things that are
connected together.  Often nodes are computers.  If you think of a
network as a graph (in the graph-theoretic sense), nodes are
represented by vertices.

Offered Load - The packets available for transmission.

Overprovisioned - A system is overprovisioned if it has more resources
available than it needs.  E.g., a network that is capable of handling
1Gbps of traffic, but only has 10Mbps of traffic flowing through it.
Overprovisioned systems are bad because they waste resources.

Packet Switching - A method of sharing a network; compare to circuit
switching.  Data is sent in packets, and header information in the
packets allows for per-packet forwarding.  These networks are more
resilient to failure than circuit-switched networks, and can handle
variable data rates and bursts of data, but are necessarily more
complicated.

Packets - The units of data that we transmit in a network
packet-switched network.  A packet is usually about 1500 bytes (though
this size is allowed to change).  Packets contain a header, which
contains information such as the source and destination addresses and
the length of the packet data.

Path - A path from node X to node Y in a graph is the sequence of
nodes that one can traverse to get from X to Y.

Path Visibility - A routing protocol satisfies path visibility if all
reachable destinations in the network are in the routing table.

Path-vector Routing - An extension of distance-vector routing where
nodes include full paths in their routing advertisements.  Nodes
integrate routing advertisements only if they are not in the path
contained in that advertisement.  Solves the counting-to-infinity
problem.

Protocol - The rules that govern a particular type of network
communication.  TDMA, ALOHA, etc. are all protocols.

Queue - If the outgoing interface is busy, any arriving packets are
stored in a queue until they can be sent on the outgoing interface.
Queues absorb bursts in traffic, but also add delay.  If a packet
arrives when a queue is full, the packet is dropped.

Reliable transport protocol - A protocol by which, the receiving
application receives all data bytes in exactly the same order that the
sending application sent them.  Best-effort networks alone *don't*
provide such a service.

Resilience to Failure - A system is resilient to failure if it can
continue doing its job even when components of the system fail.  In
the context of networking in 6.02, we say that networks are resilient
to failure if we can still route packets from a source to a
destination even when links or nodes fail (provided that the network
is still connected).

Round-trip-time (RTT) - The time between sending a packet and
receiving its ACK.

Route - The route from node X to node Y is the outgoing link that X
uses to send packets to Y.

Route Validity - A routing protocol satisfies route validity if all of
the routes in its table are valid (i.e., sending a packet to D on the
route to D will indeed get the packet to D).

Routing - The process of determining the paths in the network that
data should take.  In 6.02 we study distributed, minimum-cost routing
protocols.  At the end of these protocols, each node should have a
routing table that satisfies route validity and path visibility, and
where route_table[dst] contains the minimum-cost route to dst.

Routing Loop - A routing loop can happen when at least one routing
table is invalid.  A packet will traverse the same sequence of
switches over and over and over, never reaching its destination.

Routing Table - The data structure switches use to store their route
information.  Can optionally contain the route costs as well, or that
can be stored in a separate table.

Scalability - The ability of a system to be suitable for a large
number of users

Sequence numbers - A technique used in reliable transport protocols.
Sequence numbers are stored in the packet header.  In a particular
connection, they start at 1,  and increase incrementally for each
packet in the connection.  These numbers help the receiver to put
packets in order, and for the sender to know which packets haven't
been received yet.

Sliding-window Protocol - A reliable transport protocol that allows W
outstanding packets at a time.  To handle multiple outstanding
packets, the sender must keep track of the sequence numbers and times
sent for every outstanding packet, and the receiver must buffer any
out-of-order packets.

Split Horizon - A "fix" to the count-to-infinity where if node A uses
B to reach C, A does not advertise about its route to C to B.  This
solves count-to-infinity issues when only two nodes are involved, but
doesn't fix larger routing loops.

Spurious Retransmission - Retransmitting a packet when neither the
packet nor its ACK were actually lost.  These happen when the
retransmission timeout is too short.  Spurious retransmission are bad
because they add congestion to the network.

Stabilize - A system is stabilized when it continues to operate at or
near a desired operating point.  (Cf. Stabilized ALOHA)

Starvation - A node is starved if it is able to utilize very few
network resources (i.e., if it has data to send, and can almost never
send it).  Starvation is a bad thing.

Statistical Multiplexing - When many bursty connections are
aggregated (or multiplexed), the bursts smooth out.

Stop-and-wait Protocol - A reliable transport protocol where there is
at most one outstanding packet at a time.  Has poor utilization.
Equivalent to a sliding-window protocol with W = 1.

Switches - Nodes in the middle of the network.  They don't initiate
communications, but forward data within the network.

TDM - Time Division Multiplexing.  A multiplexing technique in
circuit-switched networks, where a link is shared in a similar way as
the channel is shared in TDMA.  The difference is that this is not an
access protocol; nodes can send at any point, but the switch is
multiplexing their connections according to time division.

TDMA - Time Division Multiple Access.  A channel access protocol where
a node transmits in time slot t iff t % N == node_id (there are N
nodes).  Bad for bursty data.

Throughput - The amount of data a node transfers over some period of
time.  Often measured in megabits-per-second, Gigabits-per-second,
etc.

Time-to-live - See "Hop Limit".

Timeout (or Retransmission Timeout) - The amount of time a reliable
sender waits before retransmitting a packet (assuming it has not
received an ACK for that packet)

Topology - What the network looks like, in terms of a graph.  The
representation of the nodes and their connections.

Unstable - In the context of 6.02, this term typically refers to
queues.  A queue is unstable if packets are arriving faster than they
are drained (and so the queue is growing without bound).

Utilization - A measure of how much of the channel the nodes are
using.  U = (total throughput over all nodes) / (maximum data rate of
the channel).