Problem of switching and bridging
How hosts find each other on a subnet, how subnets are interconnected
How 2 hosts connect
- Connected by 2 ethernet adapters, or network interfaces, each with its own LAN or physical/MAC address
- Host sends data packet via its ethernet adapter with destination MAC address
- Destination could be broadcast destination (sent to every host it was connected to on the LAN)
- Typically, a host knows the DNS or IP address of the destination, but not the MAC address. How can it learn the MAC address? A solution is ARP (Address Resolution Protocol)
ARP
- Address Resolution Protocol
- A host queries with an IP address, broadcasting that query to every other node on the network. The query is of the form “Who has a particular IP address?”
- That host will respond with the appropriate MAC address
- The response is unicast.
- The host builds an ARP table when it gets the response.
- Now, the host can simply consult its ARP table going forward.
Encapsulation
Host puts IP packet in an ethernet frame with the corresponding destination MAC address from the ARP table, as well as its own source MAC address
What are the queries and responses in ARP?
Query: broadcast asking about IP
Response: unicast with MAC address
Simplest way a LAN can be connected
A hub (the simplest form of interconnection). In some sense they don’t even exist in networks anymore today. uses broadcast medium.
- Lots of flooding and chances for collision, which introduces additional latency.
- Vulnerable to failures or misconfiguration because one misconfigured device can cause problems for every other device on the LAN. Need to improve it by imposing some amount of isolation (Switches!).
Switches
- Traffic isolation
- Partition the LAN into separate broadcast domains or collision domains
- Might break subnet into multiple LAN segments
- Isolation requires some kind of switch table or state at the switch which maps destination MAC address to output ports
Learning switch
Maintains a table between destination addresses and output port so that it knows how to forward
- Do not eliminate all forms of flooding. Must still flood when there’s no corresponding entry.
- Also must forward broadcast frames such as ARP queries. Because of this, need to be careful of network topology loops. These are usually present for reasons of redundancy (in case a link fails). If a packet is sent as broadcast, it can lead to forwarding loops and broadcast storms.
- Need to make sure that switches don’t always flood all packets on all outgoing ports. We need some kind of forwarding tree!
Spanning tree
A loop-free topology that covers every node in a graph.
- Instead of flooding to every host, send along the spanning tree.
- Every switch forwards on the port that’s part of the tree, and omit other ports.
- Steps to construct tree:
1) Elect root (usually smallest ID)
2) Exclude any link if that link is determined not to be on the shortest path to the root. Basically, how many “hops” to the root. Tie-breaker: lower ID. - Initially, every node thinks it’s the root. Neighboring nodes update their view – determine their distance to the root simply by adding 1 to any message they receive.
Switches operate at layer…
- A common protocol at layer 2 is Ethernet.
- Switches are typically automatically configuring.
- Forwarding tends to be quite fast since packets only need to be processed through layer 2 on flat lookups.
Routers operate at…
layer 3, where IP is common protocol.
-Router level topologies are not restricted to a spanning tree.
Multi-path rounding
a single packet could be sent along one of multiple possible paths in underlying router level topology.
-In many ways, layer 2 switching is a lot more convenient, but one of the major limitations is broadcast.
Buffer sizing
-Fairly well-known that routers and switches need packet buffers to accommodate for statistical multiplexing, but unclear just how much is necessary
The only variable of packet delay on the internet
Queueing delay
Buffering equation
2T is the roundtrip propagation delay
Capacity is C (bottleneck link)
2TC was the rule of thumb, and the guideline mandated in routers for many years. Turns out it’s incorrect and doesn’t apply in practice.
-Really only holds if all flows perfectly synchronized. Helps with central limit theorem: the more variables we have (in this case, unique congestion windows), the narrower the Gaussian will be. Width decreases with 1/root(n) where n is the number of unique congestion windows of flows that we have. We can get away with way less buffering (2TC/root(n)) where n is the # of flows passing through the router
AIMD
Additive increase, multiplicative decrease
-For every W acks received, we send W+1 packets
