ECE 358

1: Introduction

1.1 What is the Internet?

Millions of connected computing devices.

Protocols define format, order of messages sent and received among network entities, and actions taken on message transmission, receipt.

1.2 Network Structure

Wired Access Networks

Shared wireless access network connects end systems to router via a base station (access point).

Wireless LANs: Within building (100ft), 802.11 b/g (WiFi), 11 / 54 Mbps transmission rate.

Wide-Area Wireless Access: Provided by telco (cellular) operator. 1-10 Mbps transmission rate.

Hosts break application message into smaller chunks known as packets, of length L bits. Packets are transmitted across the network at a transmission rate T. The transmission delay is then \frac{L}{R}.

1.3 Physical Media

1.4 Network Core

Mesh of interconnected routers.

Packet Switching

Hosts break application-layer messages into packets. Packets are forwarded from one router to the next, across links on a path from source to destination.

The two key network core functions are routing and forwarding.

Circuit Switching

Packet Switching vs. Circuit Switching

Packet switching allows for more users to use the network.

1.4 Loss and Delay in Networks

Four sources of packet delays.

  1. Nodal Processing: Checking bit errors, determining the output link. Usually < 1ms.
  2. Queueing Delay: Time waiting at output link for transmission. Depends on the level of congestion at the router.
  3. Transmission Delay: \frac{L}{R}, where L is the packet length and R is the link bandwidth.
  4. Propagation Delay: \frac{d}{s} where d is the length of the physical link and s is the propagation speed in the medium.

Throughput: Rate at which bits are transferred between the sender and receiver.

Internet protocol stack

Application: Running the network applications that you want (HTTP, FTP, SMTP). Implemented using software only.
Transport: Responsible for communication of processes between layers (TCP, UDP). Mainly implemented using software.
Network: Responsible for routing from source to destination. Implemented using software and hardware.
Link: Transferring to data between physically connected (adjacent) hubs (e.g. Computer -> Router, Router -> Router …). Hardware.
Physical: How you are transferring physical bits on the wire. Not covered in this course.

Before the internet, there were two extra section that were planned.

Presentation: Applications to interpret meaning of data (e.g. encryption, compression, etc.).
Session: Synchronization, checkpointing.

If you want these features, it must be implemented in the application layer.

Encapsulation

Switch: Link and physical layers. Router: Network, link, and physical layers.

Information is added from the above layer to the lower.

Transport: Segment
Network Layer: Datagram
Link Layer: Frame

When passing data through, you need to pop the stack (decapsulation) and then replace (encapsulation).

Network Security

Internet was not designed with security in mind. How can bad guys attack and how can we defend? How can we design architectures that are immune to attacks.

In real life: Hackers hack your system and then you fix the error and catch up.

Malware any harmful software.

Virus: Interaction required.
Worm: Weakness in application you are already running.
Spyware: Record keystrokes, web sites, etc.

Infected hosts can be enrolled in botnet to help in future attacks.

Examples of Attacks

Denial of Service (DoS): Attackers infect local computers with a worm in order to all send messages to the target at the same time. Target will be busy services request so they cannot service normal customers.

Packet “sniffing”: Passive program that is on the link which listens to and records packets.

IP spoofing: Send a message with a false source address.

Routers: Implements the bottom 3 layers (network, data link, physical).

Switches: Implements the bottom 2 layers (data link, physical).

2: Application Layer

2.1: Principles of network applications

Creating a network app

Only write to run on end systems (not on the internal network). Does not matter if they are servers or clients. We also only care about what we want to do on the application layer and then push to the transport layer which will take care of transmitting the data. This allows for fast development.

Client-Server: Server is always on with a static IP. Client will communicate with servers (intermittent). Client IP addresses will be dynamic.

P2P: Arbitrary end systems directly communicate. Peers request service from other peers and provide service in return (self scalability). There is more complex management because there is no central network that controls all uses. Security is also a big issue.

Process Communication

Process: program running within a host.

Client process: Process that initiates communication.

Server process: Process that waits to be contacted.

Sockets

Process sends / recieves messages to / from it’s socket.

Socket: The gate between the application layer and the transport layer. Sockets are similar to doors. Sending process shoves message out of door and relies on the other side of the door to deliver message to the socket at the receiving process.

Example: Chrome tabs. How do we know which tab to put data? There is an identifier for each socket to route the data to the correct tab (You will always talk to port 80 of a server for HTTP requests but you will use a random port).

Sockets consists of two parts (for now).

  1. Address of host.
  2. Port number.

The combination of the two parts will create a unique identifier for the socket. Each process has it’s own unique socket (there are over 65k ports).

Application Layer Protocol Defines …

Rules for when and how process send and respond to messages.

Types of messages exchanged: Request, response.

Message syntax: What does each field mean and how fields are delineated.

Message semantics: What do you want the information in the fields to mean.

Examples of open protocols are HTTP and DNS which are defined in RFCs (Request For Comments is a formal document from the Internet Engineering Task Force). An example of a proprietary protocol is Skype.

What Transport Services Does an Application Need?

Will be implemented at the application level.

  1. Data Integrity. Some applications require 100% data transfer whereas other applications (e.g. audio) can tolerate some loss.
  2. Timing. Time sensitive applications (e.g. Internet telephone, interactive games) require low delay to be effective.
  3. Throughput (How fast the data can be transferred). Some applications require a minimum amount to be effective.
  4. Security. Encryption.
Application Data Loss Throughput Time Sensitive
File Transfer No Elastic No
E-Mail No Elastic No
Web Documents No Elastic No
Real-Time AV Tolerant Minimum requirements Yes, 100’s ms
Stored AV Tolerance Minimum requirements Yes, few seconds
Interactive Games Tolerant Minimum requirements Yes, 100’s ms
Text Messaging No Elastic Yes and No

Internet transport protocol services

What is offered by the transport layer? Which protocol should I Use? There are two main protocols …

  1. TCP (Transport Control Protocol)
  2. UDP (User Datagram Protocol)

Why bother with UDP?

Application Application Protocol Transport Protocol
Email SMTP TCP
Remote Terminal Access Telnet TCP
Web HTTP TCP
File Transfer FTP TCP
Streaming Multimedia HTTP, RTP TCP or UDP (Usually UDP)
Internet Telephone SIP, RTP TCP or UDP

Securing TCP

TCP and UDP have no encryption. Plaintext passwords send into sockets.

If you want security, you can use SSL (secury socket layer) which provides encryption for TCP connection. SSL is used at the application layer (need to use a SSL library such as OpenSSL).

2.2: Web and HTTP

A web page consists of objects. (HTML, JPEG, Java applet, auto file, …).

HTTP (hypertext transfer protocol): We have a client / server model. The client sends requests to the server and the server replies with an HTTP request.

  1. HTTP uses TCP. The client initiates TCP connection (creates socket) to server, port 80. (A random port is used on the client side).
  2. Server accepts TCP connection from client.
  3. HTTP messages (application-layer protocol messages) exchanged between browser (HTTP client) and Web server (HTTP server).
  4. TCP connection closed.

HTTP is “stateless”. The server maintains no information about past client requests.

Protocols that maintain “state” are complex. Past history must be maintained and if the client / server crashes, their views of the “state” may be inconsistent.

Types of HTTP Connections

  1. Non-Persistent HTTP
  2. Persistent HTTP

Response Time

RTT (Round Trip Time): Time it takes a small packet to travel from client to server and back.

HTTP Response Time

Non-Persistent HTTP Response Time = 2RTT + transmission time.
Persistent HTTP Response Time = RTT + n(RTT + transmission time).

For non-persistent HTTP, we require 2 RTT per object. There is OS overhead for each TCP connection. Browsers often open parallel TCP connections to fetch referenced objects.

For persistent HTTP, subsequent HTTP messages between client / server will be over the same connection so the client will sent requests as soon as it encounters a referenced object. There is as little as on RTT per referenced object.

HTTP Request

HTTP/1.0

HTTP/1.1

HTTP Response

Cookies

Used to identify users. ID is stored in client side which is sent in the header of subsequent messages.

  1. Cookie header line in HTTP response from server.
  2. Cookie header line in next HTTP request from client.
  3. Cookie file kept client-side.
  4. Back-end database for server.

Cookies are used to keep state.

Web Caches (Proxy Server)

Satisfy client request without involving the original server.

All requests are sent through a proxy server instead which caches requests and responses. If the request is already cached, it does not have to travel all the way to the original server.

Example:

Average object size: 100\ K bits.
Average request rate: 15\ /\ sec.
RTT from institutional router to original server: 2\ sec
Access link rate: 1.54\ Mbps

We then have LAN utilization: \frac{1.5\ Mbps}{1\ Gbps} = 0.15\%
Access link utilization: \frac{1.5\ Mbps}{1.54\ Mbps} = 97.4\%
Total Delay = Internet Delay + Access Delay + LAN Delay
Access Delay: \frac{100\ K}{(1 - 0.974)1.54\ Mbps}. (New users can only use whatever is left of the access link).
LAN Delay: \frac{100\ K}{(1 - 0.0015)1\ Gbps}
Total Delay = 2 + 2.5 + 0.0001

Solutions:

  1. Get a faster access link. If the access link rate was increased to 154\ Mbps, the access link delay drops to 0.0007 so the total delay is only 2 sec.

  2. Caching. If the cache hit rate was 0.4, 40% of requests are satisfied at the cache. The data rate to browsers over the access link is 0.6 \cdot 1.50\ Mbps = 0.9\ Mbps. Utilization becomes 0.58. Total Delay = 0.6 \cdot(delay from original servers) + 0.4 \cdot(delay when satisfied by the cache) = 0.6(2.15) = 1.29\ sec.

Conditional GET - If the cache has an up-to-date version, don’t send the object. - The web server sends a conditional get with the If-modified-since. - Response code 304 Not Modified if the cached version is fine. - Response code 200 OK will send the updated data.

2.3: DNS

Domain Name System.

Internet uses 32-bit IP address to identify hosts connected to the internet. The public cannot remember the real address so we use easy to remember names.

For complex objects, we push complexity to the edge (host systems).

DNS Services

Why Not Centralize DNS?

Not scalable.

Hierarchy

If the client wants the IP for www.amazon.com.

  1. Queries root domain server to find com DNS server.
  2. Queries .com DNS server to get amazon.com DNS server.
  3. Queries amazon.com DNS server to get IP address for www.amazon.com.

TLD Servers

Authoritative DNS Servers

Local DNS Name Server

If the host at cis.poly.edu wants IP address for gaia.cs.umass.edu.

Iterated Query: - Contacted server replies with name of server to contact. - “I don’t know this name, but ask this server”.

Recursive Query: - Puts burden of name resolution on contacted name server. - Heavy load at upper levels of hierarchy?

Once (any) name server learns the mapping, it caches mapping.

DNS Records

Distributed database storing resource records (RR).

RR Format: (Name, Value, Type, TTL).

DNS Protocol, Messages

Query and reply messages have the same message format.

msg Header:

Chapter 2 slides have a better visualization for format.

Attacking DNS

  1. DDoS Attacks.
  2. Redirect Attacks.
  3. Exploit DNS for DDoS.

3: Transport Layer

3.1: Transport-Layer Services

Transport Layer vs. Network Layer

Household Analogy

12 kids in Ann’s house sending letters to 12 kids in Bill’s house. - hosts: houses. - processes: kids. - app messages: letters in envelopes. - transport protocol: Ann and Bill who demux to in-house siblings. - network protocol: postal service.

Internet Transport-Layer Protocols

3.2: Multiplexing / Demultiplexing

Multiplexing at sender: Handle data from multiple sockets, add transport header (later used for demultiplexing).

Demultiplexing at receiver: Use header info to deliver received segments to the correct socket.

How Demultiplexing Works

Connectionless Demultiplexing

Connection-oriented Demux

3.3 Connectionless Transport: UDP

When we want the speed to be as fast as possible and we are loss tolerant.

UDP adds a segment header of 64 bits. The first 32 are used for the source port number and the destination port number. The next 16 are used for the length in bytes of the segment (including header), and the final 16 are used for checksum.

UDP Checksum

We want to detect “errors” (e.g. flipped bits) in transmitted segmet.

The sender treats the segment’s contents as a sequence of 16-bit integers. The checksum is the addition (one’s complement sum) of segment contents. The receiver then computes their own checksum and compares. (When adding numbers, a carryout from the msb gets re-added to the result).

3.4 Principles of Reliable Data Transfer

rdt_send() is called from the application layer whenever we have data to send which passes udt_send() to transfer the packet over the unreliable channel to receiver. It is received by rdt_rcv() which gets passed to the protocol on the transport layer. After some processing, it is passed to the upper application layer through deliver_data().

RDT 1.0: Reliable transfer over a reliable channel.

Underlying channel is perfectly reliable. There are no bit errors and no loss of packets.

We have separate Finite State Machines (FSMs) for sender, receiver. The sender sends data into the underlying channel and the receiver reads data from the underlying channel.

RDT 2.0: Channel with Bit Errors

Underlying channel may flip bits in packet which is detected by the checksum.

RDT 2.1

Stop and Wait protocol: sender sends 1 packet and then waits for receiver response.

RDT 2.2: NAK-free

RDT 3.0: Channels with Errors and Loss

Now the underlying channel can also lose packets (data, ACKs).

The sender will wait a “reasonable” amount of time for ACK. It will retransmit if no ACK is received in time.

Pipelined Protocols

Sender allows multiple, “in-flight”, packets. - The range of sequence numbers must be increased. - There is buffering at the sender and / or receiver.

Go-Back-N

Selective Repeat

Sender

Receiver

Selective Repeat: Dilemma: While sliding windows, we may accidentally accept old data as new. The problem is that the receiver knows nothing about the sender. We can fix this by setting the window size to be equal to less than half of the sequence number space.

Performance of Sliding Window

No Errors: \rho = \min(1, \frac{W\frac{L}{C}}{t_T}).

Automatic Repeat Request (ARQ) Protocols

Applied at the transport and link layers.

  1. Stop-and-Wait Protocol.
  2. Go-Back-N.
  3. Selective Repeat.

3.5 Connection-Oriented Transport: TCP

TCP Segment Structure

Default header length is 20 bytes compared to UDP 8 bytes.

Acknowledgements include the sequence number of the next byte expected from the other side (cumulative ACK). The TCP spec doesn’t say how to handle out-of-order segments, it is up to the implementer. There are two choices, discard or buffer. Buffering is used in practice.

TCP Round Trip Time, Timeout

How to set TCP timeout value?

It should be longer than the RTT, but the RTT varies. If it is too short, we will have unnecessary retransmissions. If it is too long, we will have slow reactions to segment loss.

We estimate RTT by sampling from segment transmissions. SampleRTT is the measured time from segment transmission to ACK receipt (ignoring retransmissions). We use an exponential weighted moving average, EstimatedRTT = (1 - \alpha)\cdot EstimatedRTT + \alpha \cdot SampleRTT. The typical value is \alpha = 0.125.

Is this estimation enough? We want to add a safety margin so that a large variation in EstimateRTT results in a larger safety margin. We use 4 standard deviations. DevRTT = (1 - \beta)\cdot DevRTT + \beta \cdot |SampleRTT - EstimatedRTT|. The typical value is \beta = 0.25.

The timeout interval is then TimeoutInterval = EstimatedRTT + 4 \cdot DevRTT.

TCP Reliable Data Transfer

TCP Created a RDT service on top of IP’s unreliable service. It uses pipelined segments, cumulative ACKs, and single retransmission timer (similar to Go-Back-N). Retransmission are triggered by timeouts or duplicate ACKs.

Let’s initially consider a simplified TCP sender with no duplicate ACKs and ignoring flow / congestion control.

TCP Sender Events:

Three major events in sender.

  1. Data received from application layer.
  2. Timeout.
  3. ACK received.

TCP ACK Generation

Event At Receiver TCP Receiver Action
Arrival of in-order segment with expected sequence number. All data up to the expected sequence number are already ACKed. Delayed ACK. Wait up to 500ms for the next segment. If no next segment, send ACK.
Arrival of in-order segment with expected sequence number. One other segment has ACK pending. Immediately send single cumulative ACK, ACKing both in-order segments.
Arrival of out-of-order segment (heigher than expected sequence number). Gap detected. Immediately send duplicate ACK, indicating sequence number of the next expected byte.
Arrival of segment that partially or completely fills the gap. Immediate send ACK, provided that the segment starts at the lower end of the gap.

TCP Fast Retransmit

If you receive 3 duplicate ACKs, it is an indicator that a packet has been lost. The sender will retransmit immediately instead of waiting for the timeout.

TCP Flow Control

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

Applications may remove data from TCP socket buffers slower than the TCP receiver is delivering (sender is sending).

Connection Management

Before exchanging data, the sender and receiver “handshake” (agree to establish connection, agree on connection parameters).

3.6 Principles of Congestion Control

Too many sources sending too much data too fast for the network to handle.

Causes / Costs of Congestion

  1. Infinite buffer, 2 senders and 2 receivers use the same link with an output link capacity of R.
  2. Finite buffer. Input and output rates are the same.
  3. Multiple routers.

Approaches to Congestion Control

Two broad approaches.

  1. End-End Congestion Control.
  2. Network-Assisted Congestion Control.

3.7 TCP Congestion Control

Additive increase, multiplicative decrease (AIMD).

TCP Slow Start

Detecting, Reacting to Loss

Switching from Slow Start to CA (Congestion Avoidance)

When should the exponential increase switch to linear?
When cwnd gets to \frac{1}{2} of its value before timeout.

Implemented with a variable ssthresh. On a loss event, ssthresh is set to \frac{1}{2} of cwnd before loss event.

TCP Throughput

Example: Average Throughput = 10 Gbps, 100ms RTT, 1500 byte segment = 3/4 W/RTT bytes/sec Solve for W, Number of segments is W / 1500

Throughput in terms of segment loss probability L = \frac{1.22 \cdot MSS}{RTT \sqrt L}, MSS -> Maximum Segment Size.

To achieve a 10gbps throughput, we need a lost rate of L = 2\cdot10^{-10} which is a very small loss rate.

We need a new version of TCP for high-speed. It is hard to implement TCP because there are hardware that implement and are hard to change.

TCP Fairness

Fairness goal: If K TCP sessions share the same bottleneck link of bandwidth R, each should have average rate of \frac{R}{K}.

Two competing sessions will have additive increase which gives slope of 1, as throughput increases. Multiplicative decrease decreases throughput proportionally.

Multimedia apps often do not use TCP because they do not want the rate throttled by congestion control. They send audio / video at constant rate, tolerate packet loss.

This is fair over each connection, but you can cheat the system by having multiple TCP connections.

4. Network Layer

Unlike the application and transport layers, the network layer is implemented every host and router.

Recall: Transport layer encapsulates the data by breaking it into segments and adding headers.

The network layer further encapsulates segments by adding it’s own headers.

Two Key Functions

  1. Forwarding: Move packets from router’s input to appropriate router output.
  2. Routing: Determining route taken by packets from source to destination.

Some network architectures require connection setup. Before datagrams flow, two end hosts and intervening routers establish virtual connection.

Recall: Network layer connection service is between two hosts (may also involve intervening routers in case of VCs). Transport layer connection service is between two processes.

Network Service Model

ATM: Asynchronous Transfer Mode

Datagram network provides network-layer connectionless service.

Datagrams include the IP address of the receiver. Virtual circuit cells include a virtual circuit number.

ATM, VC forwarding table includes some info specific to the call between sender and receiver.

VC Implementation

  1. Path from source to destination.
  2. VC numbers, one number for each link along path.
  3. Entries in forwarding tables in routers along path.

VC numbers change in order to have unique numbers between each router’s connections.

VC: Signaling Protocols

Datagram Networks

Connectionless.

Datagram Forwarding Table

What happens when the ranges don’t divide up nicely?

Longest Prefix Match: Match the IP address to an entry in the forwarding table based on the longest prefix that matches.

Datagram or VC Network?

Datagram (Internet)

VC (ATM)

4.3 Router

Input ports, output ports, high-seed switching fabric, routing processor.

  1. Running routing algorithms / protocol (RIP, OSPF, BFP).
  2. Forward datagrams from incoming to outgoing link.

Every router has three layers (network, link, physical).

Input Port Functions

Line termination -> Link layer protocol -> Lookup, forwarding, queueing.

Switching Fabrics

Switching via Memory

First generation routers.

Switching via Bus

We can still only send one packet on the bus at a time.

Switching via Interconnection Network

Output Ports

How Much Buffering?

4.4 IP: Internet Protocol

In the network layer, we have routing protocols, IP protocol, and ICMP protocol (error reporting and router signalling).

IP Datagram Format

IP Fragmentation, Reassembly

IPV4 Addressing

Subnets

CIDR (Classless InterDomain Routing)

IP Address: How To Get One?

DHCP Overview

DHCP can return more than just the allocated IP address on subnet.

By doing bitwise & between a host IP address and subnet mask, you will get the subnet portion of the host IP address.

How does network get subnet part of IP address? It gets an allocated portion of its provider ISP’s address space.

Heirarchical Addressing

Hierarchical addressing allows for efficient advertisement of routing information. Longest prefix match is used.

How does an ISP get a block of addresses? ICANN (Internet Corporation for Assigned Names and Numbers) allocates addresses, manages DNS, assigns domain names, and resolves disputes.

NAT (Network Address Translation)

Households with one router only has one IP address. There may be multiple devices that need to connect, so the router does translation between local IP addresses and the outside world.

All datagrams leaving the network have same single source NAT IP address.

Motivation: local network uses just one IP address as far as the outside world is concerned.

Implementation: a NAT router must.

NAT has a 16-bit port number field which allows for 60000 simultaneous connections with a single LAN-side address!

NAT is controversial.

NAT Traversal Problem

ICMP (Internet Control Message Protocol)

Traceroute and ICMP

We want to know which router I go through and the delays.

Stopping Criteria:

IPv6

IPv6 Datagram Format

Changes from IPv4

Transition from IPv4 to IPv6

IPv6 Adoption

4.5 Routing Algorithms

Routing algorithm determines end-end path through the network. Forwarding table determines local forwarding at this router.

Routing Algorithm Classification

Global: All routers have complete topology and cost information (link state algorithms).

Decentralized: Router knows only physically-connected neighbours. There is a iterative process of computation (distance vector algorithms).

Static: Routes change slowly over time.

Dynamic: Periodic updates in response to link cost changes.

Dijkstra’s algorithm is used to compute least cost paths from one node (source) to all other nodes. Tracing predecessor nodes gives a forwarding table for that node.

Oscillations are possible, when the support link cost is equal to the amount of carried traffic.

Distance Vector Routing Algorithm

Bellman-Ford equation is used to compute least cost paths at each node. The node v that achieves the minimum cost for y is the next-hop in the forwarding table.

d_x(y) = \min_v\{c(x, v) + d_v(y)\}

Each node x knows the cost to each neighbour v and maintains its neighbours distance vectors. For each neighbour v, x maintains \mathbf{D}_v = [D_v(y), y \in N]. x also maintains a distance vector for itself.

From time-to-time, each node sends its own distance vector estimate to its neighbours. When x receives a new distance vector estimate from a neighbour, it updates its own distance vector using the Bellman-Ford equation. Under minor, natural conditions, the estimate D_x(y) will converge to the actual least cost d_x(y).

D_x(y) = \min_v\{c(x, y) + D_v(y)\}, \text{ for each node } y \in N

  1. Iterative, Asynchronous: Local iterations are caused by.
  2. Distributed: Each node notifies neighbours only when its distance vector changes.

Distance Vector Problems

When link cost changes, the node needs to update routing information, and recalculate the distance vector. If the distance vector changes, it must notify neighbours.

Bad news travels slow. There can be a routing loop between two nodes if a cost update reverses the minimum cost path. In order to broadcast the distance vector to its neighbours, nodes will keep passing information back to each other and updating distance vectors. Counting to infinity problem.

We used poisoned reverse in order to solve the problem of routing loops. If Z routes through Y to get to X, Z tells Y that D_y(x) = \infty. This does not completely solve the problem, we need to poison every node from source to destination.

Heirarchical Routing

In real life, all routers are not identical, and the network is not flat.

With 600 million destinations, storing all destinations in routing tables would not be scalable. Routing table exchange would swamp links.

The internet is a network of networks, and each network admin may want to control routing in its own network.

Inter-AS Tasks

Example: Single AS.

Example: Multiple ASes.

Hot Potato Routing: We want to get rid of our package as fast as possible, so we choose the gateway that has the lowest local cost.

4.6 Routing in the Internet

Intra-AS Routing

Interior Gateway Protocols (IGP).

RIP (Routing Information Protocol)

If no advertisement is heard after 180s, the neighbour / link is declared dead.

RIP routing tables are managed by application-level process called route-d (daemon).

OSPF (Open Shortest Path First)

Hierarchical OSPF

Inter-AS Routing (BGP)

Border Gateway Protocol. De facto inter-domain routing protocol, the glue that holds the Internet together.

BGP Messages

Path Attributes and BGP Routers

BGP Route Selection

We only continue to the next step if there are still ties.

  1. Local preference value attribute, policy decision.
  2. Shortest AS-PATH.
  3. Closest NEXT-HOP (OSPF).
  4. Additional criteria.

BGP Routing Policy

Why Intra-AS and Inter-AS Routing?

Entry in Forwarding Table

  1. Router becomes aware of prefix.
  2. Router determines output port for prefix.
  3. Router enters prefix-port in forwarding table.

4.7 Broadcast Routing

Controller Flooding

Node only broadcasts packet if it has not broadcasted the same packet before.

5: Link Layer

Responsible for transferring datagram from one node to physically adjacent node over a link.

5.2 Error Detection and Correction

Parity Checking

Detect and correct single bit errors.

Internet Checksum (Review)

Cyclic Redundancy Check

Example: D = 101110, G = 1001.

|G| = 4 = r + 1. Shift D left by r, 101110000.

5.3 Multiple Access Protocols

  1. Point-to-Point.
  2. Broadcast.

Multiple Access Protocol

Distributed algorithm that can determine how nodes share channel, determine when node can transmit.

Ideal Protocol

Given a broadcast channel rate R bps.

  1. When one node wants to transmit, it can send at rate R.
  2. When M nodes want to transmit, each can send at average rate \frac{R}{M}.

  3. Fully decentralized.

  4. Simple.

MAC Protocol Taxonomy

Three broad classes.

  1. Channel Partitioning.
  2. Random Access.
  3. Taking Turns.

Channel Partitioning

  1. TDMA: Time Division Multiple Access.

  2. FDMA: Frequency Division Multiple Access.

  3. CDMA: Code Division Multiple Access.

Random Access Protocols

Slotted ALOHA

Collisions can be detected in physical medium based on superposition.

Assumptions.

Operation.

Pros.

Cons.

The efficiency is the long-run fraction of successful slots.

Pure (Unslotted) ALOHA.

No synchronization between nodes.

CSMA (Carrier Sense Multiple Access)

Listen before retransmit.

CSMA/CD (Collision Detection)

  1. NIC (Network Interface Card) receives datagram, encapsulates into creates frame.
  2. If NIC senses channel is busy, waits until idle, then transmits.
  3. If NIC transmits entire frame without detecting another transmission, then we are done.
  4. If NIC detects another transmission, abort and send a jam signal.

  5. After aborting NIC enters binary (exponential) backoff.

Assume that T_{prop} is the maximum propagation delay between 2 nodes in LAN, and t_{trans} is the time to transmit a max-size frame.

\text{efficiency} = \frac{1}{1 + 5\frac{t_{prop}}{t_{trans}}}

Taking Turns

We look for the best mix of channel partitioning and random access.

  1. Polling.
  2. Token Passing.

Cable Access Network

An example of how we can use multiple access.

5.4 LANs

MAC Addresses and ARP

Analogy: MAC address like SSN, IP address like postal address.

LAN Addresses

ARP (Address Resolution Protocol)

How to determine interface’s MAC address, knowing its IP address.

ARP Table: Each IP node (host, router) on LAN has table.

Consider A wants to send a datagram to B but B’s MAC address is not in A’s ARP table.

Example: Sending a datagram from A to B via R. Assume that A knows B’s IP address, IP address of first hop router R (DHCP), and R’s MAC address (ARP).

- A creates IP datagram with IP source A, destination B. - A creates link-layer frame with R’s MAC address at destination, frame contains A-to-B IP datagram. - Frame sent from A to R, upon arrival, datagram is removed and passed up to IP. - R forwards datagram with IP source A, destination B. - R creates link-layer frame with B’s MAC address as destination, frame contains A-to-B IP datagram.

Ethernet

“Dominant” wired LAN technology. Family of protocols.

Physical Topology

Frame Structure

Sending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet frame.

Ethernet is unreliable, connectionless.

There are many difference Ethernet standards. They each have common MAC protocol and frame format. Offer different speeds, and different physical layer media.

Ethernet Switches

Implement the bottom two levels.

Switches allow for multiple simultaneous transmissions.

Switch Forwarding Table

How does the switch know A^\prime is reachable via interface 4, etc.

How are entries created and maintained in the switch table?

Interconnecting Switches

Switches can be connected in order to create a hierarchy.

Switches vs. Routers

Both are store-and-forward.

Both have forwarding tables.

A router has multiple IP addresses. There is one for every interface.

VLANS

We want to achieve some sort of traffic isolation. Switch(es) supporting VLAN capabilities can be configured to define multiple virtual LANS over single physical LAN infrastructure.

Port-based VLAN

Switch ports grouped (by switch management software) that a single physical switch operates as multiple virtual switches.

Multiprotocol Label Switching.

MPLS Capable Routers

Label-switched router.

MPLS Signaling

5.6 Data Center Networking

5.7 Web Request Example

A student attaches a laptop to a campus network, requests / receives www.google.com.

Client now has IP address, knows name and address of DNS server, and the IP address of its first-hop router.