A Top-Down Approach Studying Notes

A Top-Down Approach is a classic textbook in the field of computer networking. Hope this studying note can help you get the key points when you read the textbook!

Chapter 1 - What is the Internet?

A Nuts-and-Bolts Description

basic concepts

Devices connected to the Internet: hosts or end system

End systems are connected together by a network of communication links and packet switches.

Made up of different types of physical media

Different links have different transmission rate, measured in bits/seconds

When one end system has data to send to another end system, the sending end system segments the data and adds header bytes to each segment. The resulting packages of information, known as packets, are then sent through the network to the destination end system, where they are reassembled into the original data

packet switch

Takes a packet arriving on one of its incoming communication links and forwards that packet on one of its outgoing communication links

  • routers

used in the network core

  • link-layer switches

used in access networks

The sequence of communication links and packet switches traversed by a packet from the sending end system to the receiving end system is known as a route or path through the network.

Protocols

End systems, packet switches, and other pieces of the Internet run protocols that control the sending and receiving of information within the Internet.

  • TCP(Transmission Control Protocol)

  • Internet Protocol (IP)

specifies the format of packets

  • TCP/IP

A services Description

Definition

The Internet is an infrastructure that provides services to distributed applications.

socket interface

Socket interface is a set of rules that the sending program must follow so that the data can be delivered to destination program.

What is a Protocol?

A Human Analogy

Network Protocols

A protocol defines the format and the order of messages exchanged between two or more communicating entities, as well as the actions taken on the transmission and/or receipt of a message or other event.

The Network Edge

hosts:

  • clients

desktops, laptops, smartphones…

  • servers

powerful machines that store and distribute Web pages, stream video, relay e-mail…

in large data centers

Access Networks

Home Access

DSL Internet access
  • DSL modem

Translate between digital data and high-frequency tones.

Data and telephone signals are encoded at different frequencies.

  • DSLAM

On the telco side, DSLAM separates the data and phone signals and sends the data into the Internet.

  • Splitter

On the customer side, a splitter separates the data and telephone signals arriving to the home and forwards the data signal to the DSL modem.

Asymmetric: downstream transmission rate is larger than upstream transmission rate

cable Internet access

Frequency division multiplexing(FDM): different channels transmitted in different frequency bands

Asymmetric: downstream transmission rate is larger than upstream transmission rate

CMTS‘s function is similar to DSLAM

fiber to the home (FTTH)

even faster!

provide an optical fiber path from the CO directly to the home

FTTH using the PON distribution architecture (passive optical networks):

packets sent from OLT are replicated at the splitter (similar to a cable head end)

5G fixed wireless

without installing costly and failure-prone cabling

Access in the Enterprise (and the Home): Ethernet and WiFi

  • Home Network

Wide-Area Wireless Access: 3G and LTE 4G and 5G

Employ the same wireless infrastructure used for cellular telephony to send/receive packets through a base station that is operated by the cellular network provider.

Physical Media

guided media / unguided media.

  • Twisted-Pair Copper Wire

Twisted pair is the dominant solution for high-speed LAN networking

  • Coaxial Cable

Coaxial cable can be used as a guided shared medium

  • Fiber Optics

  • Terrestrial Radio Channels

Require no physical wire to be installed, can penetrate walls, provide connectivity to a mobile user, and can potentially carry a signal for long distances.

  • Satellite Radio Channels

The Network Core

Packet Switching

R: transmission rate (bps)

L: length of a packet

transmission delay:

Store-and Forward Transmission

it takes 2L/R(time) for a packet to be sent from Source to Destination

it takes 4L/R(time) for all three packets to be sent from Source to Destination

More general form: N links each of rate R

end-to-end delay:

end-to-end delay

Queuing Delays and Packet Loss

output buffer (output queue): the arriving packet wait here

result in output buffer queuing delays

if the output buffer is full, packet loss occurs

Forwarding Tables and Routing Protocols

How do forwarding tables get set?

The Internet has a number of special routing protocols that are used to automatically set the forwarding tables

Circuit Switching

When two hosts want to communicate, the network establishes a dedicated end-to-end connection.

Why is circuit switching less efficient than packet switching?

Circuit switching pre-allocates use of the transmission link regardless of demand, with allocated but unneeded link time going unused

Packet switching allocates link use on demand

Internet is a "network of networks"!

Interconnection of ISPs:

Delay, Loss, and Throughput in Packet-Switched Networks

Four delays:

  • transmission delay: time to push the entire packet onto the link
  • processing delay
  • propagation delay
  • queueing delay -> congestion and packet loss

Four network delays

Throughput:

analogy to pipes

rate(bits/time unit) at which bits are being sent from sender to receiver

Layering, encapsulation, service models

Layering and encapsulation:

The switches and routers only implement the lower layer of the protocol stack:

Chapter 2 - Application Layer

2.1 Principles of Network Applications

Network Application Architectures

  • client-server architecture
  • peer-to-peer (P2P) architecture

Processes Communicating

Processes on two different end systems communicate with each other by exchanging messages across the computer network.

The Interface Between the Process and the Computer Network

A process sends messages into, and receives messages from, the network through a software interface called a socket.

Transport Services Available to Applications

reliable data transfer, throughput, timing, and security

Transport Services Provided by the Internet(TCP/IP networks)

  • TCP Services

Connection-oriented Service(handshaking)

Reliable data transfer

congestion-control mechanism

TCP congestion control attempts to limit each TCP connection to its fair share of network bandwidth.

  • UDP Services

Application-Layer Protocols

An application-layer protocol defines how an application’s processes, running on different end systems, pass messages to each other.

The Web’s application-layer protocol, HTTP, defines the format and sequence of messages exchanged between browser and Web server.

2.2 The Web and HTTP

HTTP Message Format

HTTP Request Message

1
2
3
4
5
GET /somedir/page.html HTTP/1.1
Host: www.someschool.edu
Connection: close
User-agent: Mozilla/5.0
Accept-language: fr

The first line of an HTTP request message is called the request line; the subsequent lines are called the header lines.

General format:

If the value of the method field is POST, then the entity body contains what the user entered into the form fields.(e.g. when a user provides search words to a search engine)

HTTP Response Message

1
2
3
4
5
6
7
8
HTTP/1.1 200 OK
Connection: close
Date: Tue, 18 Aug 2015 15:44:04 GMT
Server: Apache/2.2.3 (CentOS)
Last-Modified: Tue, 18 Aug 2015 15:11:03 GMT
Content-Length: 6821
Content-Type: text/html
(data data data data data ...)

General Format:

Cookies

Cookies allow sites to keep track of users.

Web Caching

Web caching

Conditional GET

HTTP/2

  • Framing

The ability to break down an HTTP message into independent frames, interleave them, and then reassemble them on the other end is the single most important enhancement of HTTP/2.

  • Message Prioritization
  • Server Pushing

2.3 Email

2.4 The Domain Name System: DNS

DNS is a distributed, hierarchical database.

2.5 Peer-to-Peer File Distribution

2.6 Video Streaming and Content Distribution Networks

DNS redirects a user’s request to a CDN server:

2.7 Socket programming with UDP and TCP

UDP client:

1
2
3
4
5
6
7
8
9
10
from socket import *
serverName = 'hostname'
serverPort = 12000
# create UDP socket for server
clientSocket = socket(AF_INET, SOCK_DGRAM)
message = raw_input('Input lowercase sentence:')
clientSocket.sendto(message.encode(), (serverName, serverPort))
modifiedMessage, serverAddress = clientSocket.recvfrom(2048)
print modifiedMessage.decode()
clientSocket.close()

UDP server:

1
2
3
4
5
6
7
8
9
10
from socket import *
serverPort = 12000
serverSocket = socket(AF_INET, SOCK_DGRAM)
# bind socket to local port number 12000
serverSocket.bind(('', serverPort))
print("The server is ready to receive")
while True:
    message, clientAddress = serverSocket.recvfrom(2048)
    modifiedMessage = message.decode().upper()
    serverSocket.sendto(modifiedMessage.encode(), clientAddress)

TCP client:

1
2
3
4
5
6
7
8
9
10
11
from socket import *
serverName = 'hostname'
serverPort = 12000
# create TCP socket for server
clientSocket = socket(AF_INET, SOCK_STREAM)
clientSocket.connect((serverName, serverPort))
sentence = raw_input('Input lowercase sentence:')
clientSocket.send(sentence.encode())
modifiedSentence = clientSocket.recv(1024)
print modifiedSentence.decode()
clientSocket.close()

TCP server:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from socket import *
serverPort = 12000
serverSocket = socket(AF_INET, SOCK_STREAM)
# bind socket to local port number 12000
serverSocket.bind(('', serverPort))
serverSocket.listen(1);
print("The server is ready to receive")
while True:
    connectionSocket, addr = serverSocket.accept()

    sentence = connectionSocket.recv(1024).decode()
    capitalizedSentence = sentence.upper()
    connectionSocket.send(capitalizedSentence.encode())

    connectionSocket.close()

Chapter 3 – Transport Layer

3.1 Introduction and Transport-Layer Services

UDP services:

  • process-to-process data delivery(multiplexing and demultiplexing)
  • error checking

TCP additional services:

  • reliable data transfer

  • congestion control

3.2 Multiplexing and Demultiplexing

The transport layer in the receiving host delivers data to an intermediary socket.

The job of delivering the data in a transport-layer segment to the correct socket is called demultiplexing.

The job of gathering data chunks at the source host from different sockets, encapsulating each data chunk with header information to create segments, and passing the segments to the network layer is called multiplexing.

Connectionless/connection-Oriented Multiplexing and Demultiplexing

A UDP socket is fully identified by a two-tuple consisting of a destination IP address and a destination port number.

A TCP socket is identified by a four-tuple: (source IP address, source port number, destination IP address, destination port number)

3.3 Connectionless Transport: UDP

Why UDP over TCP?

  • Finer application-level control over what data is sent, and when.
  • No connection establishment.
  • No connection state.
  • Small packet header overhead.

DNS: Use UDP to avoid TCP's connection-establishment delays.

Multimedia applications: tolerate packet loss

3.4 Principles of Reliable Data Transfer

Reliable Data Transfer over a Perfectly Reliable Channel: rdt1.0

Reliable Data Transfer over a Channel with Bit Errors: rdt2.0

stop-and-wait protocols:

Introduce a sequence number field:

Reliable Data Transfer over a Lossy Channel with Bit Errors: rdt3.0

Deal with packet loss:

Go-Back-N (GBN) protocol

sliding-window protocol:

If a timeout occurs, the sender resends all packets(base ~ nextseqnum - 1) that have been previously sent but that have not yet been acknowledged.

The receiver discards out-of-order packets instead of buffering them.

For the case of a window size of 4 packets:

Selective Repeat (SR) protocol

Problems of GBN protocol?

When the window size is big and as the probability of channel errors increases, the pipeline can become filled with unnecessary retransmissions.

3.5 Connection-Oriented Transport: TCP

What is MSS(Maximum Segment Size)?

The maximum amount of application-layer data in each segment, not the maximum size of the TCP segment including headers.

TCP segment structure

The acknowledgment number is the sequence number of the next byte of data that the host is waiting for.

TCP flow control

The sender maintains: LastByteSent – LastByteAcked <= rwnd(spare room in rcvbuffer)

TCP three-way handshake

How to close a TCP connection?

TCP Congestion Control

The sender maintain: LastByteSent – LastByteAcked <= min{cwnd, rwnd}

Because TCP uses acknowledgments to trigger (or clock) its increase in congestion window size, TCP is said to be self-clocking.

TCP Reno and TCP CUBIC:

Explicit Congestion Notification(ECN):

Why is TCP's AIMD algorithm fair?

TCP results in an equal share of bandwidth among connections.

Chapter 4 - The Network Layer: Data Plane

Forwarding and Routing

Control Plane

  • Traditional approach:

The routing algorithm determines the contents of the routers’ forwarding tables.

The routing algorithm function in one router communicates with the routing algorithm function in other routers to compute the values for its forwarding table by exchanging routing messages containing routing information according to a routing protocol.

  • SDN approach:

A physically separate, remote controller computes and distributes the forwarding tables to be used by each and every router.

Control-plane routing functionality is separated from the physical router.

Inside a Router

Router architecture

Input Port Processing

The forwarding table is either:

  1. computed and updated by the routing processor (using a routing protocol to interact with the routing processors in other network routers)
  2. or is received from a remote SDN controller.

Input Queueing:

  1. switch fabric slower than input ports combined

  2. HOL blocking

Switching

  • switching rate:

rate at which packets can be transfer from inputs to outputs

N inputs: switching rate N times line rate desirable

  • Three switching techniques:
  • Parallelism:
  1. Multistage switch

fragment datagram into fixed length cells at the input port

switch cells through the fabric, reassemble datagram at the output port

  1. multiple switching planes in parallel

Output Port Processing

  • Output port queuing:
  • Packet Scheduling:
  1. FIFO
  2. Priority Queuing
  1. Round Robin and Weighted Fair Queuing (WFQ)

IP Protocol

IPv4

Network layer functions:

IPv4 datagram format:

IP Addressing

An IP address is technically associated with an interface, rather than with the host or router containing that interface.

What is a subnet?

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

Address Aggregation:

How to obtain a block of IP addresses?

  1. Contact its ISP
  1. Contact global authority (ICANN)

How to obtain a Host Address?

Dynamic Host Configuration Protocol (DHCP): plug-and-play capability

DHCP is a client-server protocol:

DHCP protocol is a four-step process:

  1. Broadcast DHCP discover message to all nodes attached to the subnet.(Discover the DHCP server)
  2. A DHCP server receiving a DHCP discover message broadcasts DHCP offer message to all nodes on the subnet.
  3. The newly arriving client choose from among one or more server offers and respond to its selected offer with a DHCP request message, echoing back the configuration parameters.
  4. The server responds to the DHCP request message with a DHCP ACK message, confirming the requested parameters.

Network Address Translation (NAT)

In essence, the NAT-enabled router is hiding the details of the home network from the outside world.

The router gets its address from the ISP’s DHCP server, and the router runs a DHCP server to provide addresses to computers within the NAT-DHCP-router-controlled home network’s address space.

Generalized Forwarding and SDN

OpenFlow: flow table entries

Middleboxes

Definition: Any intermediary box performing functions apart from normal, standard functions of an IP router on the data path between a source host and destination host

  • THE IP HOURGLASS

The IP protocol hides the detailed differences among the various underlying technologies and present a uniform service interface to the applications above.

Chapter 5 - The Network Layer: Control Plane

Routing Algorithm

Centralized Routing Algorithm (link-state (LS) algorithm): the algorithm has complete information about connectivity and link costs.

Decentralized Routing Algorithm (distance-vector (DV) algorithm): each node maintains a vector of estimates of the costs (distances) to all other nodes in the net work.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* Link-State (LS) Algorithm for Source Node u */
Initialization: 
 N’ = {u}
 for all nodes v
   if v is a neighbor of u
     then D(v) = c(u,v)
   else D(v) = infinity

Loop
 find w not in N’ such that D(w) is a minimum
 add w to N’
 update D(v) for each neighbor v of w and not in N’:
       D(v) = min(D(v), D(w)+ c(w,v) )
  /* new cost to v is either old cost to v or known
  least path cost to w plus cost from w to v */
until N’= N

The implementation of this LS algorithm has worst-case complexity of order n squared: O(n2)O(n^2)​

How to avoid oscillations with congestion-sensitive routing?

Ensure that not all routers run the LS algorithm at the same time.

Randomize the time each router sends out a link advertisement in order to avoid the self-synchronization of the algorithm execution instance.

Distance-Vector (DV) Routing Algorithm

Bellman-Ford equation:

dx(y)=minv{c(x,v)+dv(y)}d_{x}(y) = min_v \{c(x, v) + d_v(y)\}

Dx=[Dx(y):y in N]Dx = [D_x(y): y\ in\ N] is node x’s distance vector

From time to time, each node sends a copy of its distance vector to each of its neighbors. When a node x receives a new distance vector from any of its neighbors w, it saves w’s distance vector, and then uses the Bellman-Ford equation to update its own distance vector as follows:

Dx(y)=minv{c(x,v)+Dv(y)} for each node y in ND_{x}(y) = min_v \{c(x, v) + D_v(y)\}\ for\ each\ node\ y\ in\ N

If node x’s distance vector has changed as a result of this update step, node x will then send its updated distance vector to each of its neighbors, which can in turn update their own distance vectors.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* Distance-Vector (DV) Algorithm 
 * At each node, x:
 */
Initialization:
   for all destinations y in N:
      Dx(y)= c(x,y)/* if y is not a neighbor then c(x,y)= infinity */
   for each neighbor w
      Dw(y) = ? for all destinations y in N
   for each neighbor w
      send distance vector  Dx = [Dx(y): y in N] to w

loop 
    wait  (until I see a link cost change to some neighbor w              or until I receive a distance vector from some                neighbor w)
    
    for each y in N:
        Dx(y) = minv{c(x,v) + Dv(y)}
    /* for each destination y, node x also determines v*(y)          and updates its forwarding table for destination y. */

if Dx(y) changed for any destination y
        send distance vector Dx  = [Dx(y): y in N] to all             neighbors

forevers

How to avoid the count-to-infinity problem?

Poisoned reverse: If z routes through y to get to destination x, then z will advertise to y that its distance to x is infinity, that is, z will advertise to y that Dz(x)=infinityD_z(x) = infinity

Intra-AS Routing in the Internet: OSPF

The routing algorithm running within an AS(autonomous system) is called an intra-autonomous system routing protocol.

Open Shortest Path First (OSPF)

OSPF is a link-state protocol that uses flooding of link-state information and a Dijkstra’s least-cost path algorithm.

A router broadcasts link-state information whenever there is a change in a link’s state. It also broadcasts a link’s state periodically, even if the link’s state has not changed.

OSPF runs directly over IP.

OSPF supports hierarchy within a single AS

An OSPF autonomous system can be configured hierarchically into areas.

Within each area, there are one or more area border routers.

Within an AS, there is exactly one backbone area.

Inter-area routing within the AS requires that the packet be first routed to an area border router (intra-area routing), then routed through the backbone to the area border router that is in the destination area, and then routed to the final destination.

Routing Among the ISPs: BGP

Each BGP route is a list with three components: NEXT-HOP; AS-PATH; destination prefix

Route-Selection Algorithm

  1. A route is assigned a local preference value as one of its attributes (in addition to the AS-PATH and NEXT-HOP attributes). The routes with the highest local preference values are selected.
  2. From the remaining routes (all with the same highest local preference value), the route with the shortest AS-PATH is selected.
  3. From the remaining routes, hot potato routing is used, that is, the route with the closest NEXT-HOP router is selected.
  4. If more than one route still remains, the router uses BGP identifiers to select the route

IP-Anycast

IP-anycast is extensively used by the DNS system to direct DNS queries to the closest root DNS server.

Chapter 6 - The Link Layer and LANs

A typical host architecture:

Switched Local Area Networks

  • ARP

ARP resolves IP addresses only for hosts and router interfaces on the same subnet.

Ethernet

switches are self-learning:

  1. The switch table is initially empty.
  2. For each incoming frame received on an interface, the switch stores in its table (1) the MAC address in the frame’s source address field, (2) the interface from which the frame arrived, and (3) the current time.
  3. The switch deletes an address in the table if no frames are received with that address as the source address after some period of time (the aging time). In this manner, if a PC is replaced by another PC (with a different adapter),

Switches are plug-and-play devices.

Computer Networking
#ELEC331 #Computer Networking #Top-Down Approach
A Top-Down Approach Studying Notes
http://oooscar8.github.io/2024/12/16/Top-down-approach/
作者
Alex Sun
发布于
2024年12月16日
许可协议