Computer Networking Notes

Computer Networking: A Top-Down Approach

1. Computer Networks and the Internet

What is the Internet

A Nuts and Bolts Description

The internet is a computer network interconnecting hundreds of millions of computing devices. These computing devices have traditionally been desktop PCs, linux workstations, servers - but increasingly nontraditional devices such as smartphones/ tablets/ TVs/ web cams/ automobiles/ etc. The devices are all called hosts or end systems, which are connected by a network of communication links and packet switches. Different links can transmit data at different rates, with the transmission rate of a link measured in bits/second. When end systems transmit data to other end systems, the sending end system segments the data and adds header bytes to each segment. These packages of information known as packets are sent through the network to the end system, where they are reassembled.

Packet switches take packet arriving on incoming communication link and forwards to an outgoing link. Most common types of packet switching devices are routers and link-layer switches. Both forward packets, but link-layer switches are typically used in access networks while routers are used in the network core. The sequence of communication links and packet switches traversed by a packet from the send to receiving end systems is known as a route or path.

End systems access the Internet through Internet Service Providers (ISPs). ISPs themselves are networks of packet switches and communication links, provide a variety of types of network access, such as high-speed LAN, wireless, 56 kbps dial-up modem access. Also provide access to content providers, connecting web sites directly to internet. ISP's are also interconnected, lower tier ISPs connect to national and international upper-tier ISPs. Upper tier ISPs manage high-speed routers interconnected with fiber-optic links, all ISPs run IP protocol.

All pieces of the internet run protocols that control the sending and receiving of information within the internet, the two most important being Transmission Control Protocol (TCP) and Internet Protocol (IP) - IP specifies the format of the packets that are sent and received amoung routers and end systems.

Given the importance of protocols in running the internet, standards are agreed upon as to how they are created. The Internet Engineering Task Force (IETF) develops internet standards, called Request for Comments (RFCs).

A Services Description

So far our description of the internet has been in terms of the components that comprise the internet. It is also possible to describe the internet as infrastructure that provides services to applications. The applications - email, web surfing, VoIP, video streaming, gaming, etc. - are distributed applications, since they involve multiple end systems exchanging data with each other. Internet application run on end systems, but are facilitated by packet switches, who are not concerned with the specifics of the data they transport.

End systems attached to the internet provide an Application Programming Interface (API) that specifies how a program running on one end system asks the internet infrastructure to deliver data to a specific program running on another end system - a set of rules the sending program must follow to be correctly interpreted by the receiving program.

What is a Protocol?

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

End systems are referred to as such because they sit at the end of the network. Also known as hosts because they host application programs, these two terms are used interchangeably. Hosts can be further subdivided into clients and servers. Informally, clients are systems like desk/laptops and mobile devices, whereas servers are more powerful systems that store and distribute content. Nowadays, most servers reside in data centers.

Access Networks

Access networks are the networks that physically connect an end system to the first router (a.k.a the edge router) on a path from the end system to any other distant end system.

Home Access

The two most prevalent types of broadband residential access are digital subscriber line (dsl) and cable. Residences usually obtain DSL internet access through a telco/ISP. DSL modems use existing phone line (twisted pair copper wire) to exchange data with a Digital Subscriber Line Access Multiplexer (DSLAM) in the ISPs Central Office (CO). DSL modem takes digital data and translates it high-frequency tones for transmission over telephone wires to the CO; analog signals from houses are translated back into digital form at DSLAM. Residential telephone line carries both data and traditional telephone signals simultaneously, encoded at different frequencies. This approach makes the signel DSL link appear as if there were three separate links (down/upstream and telephone channel). On the customer side a splitter separates the data and telephone signals arriving into the house and forwards the data signal to the DSL modem. On the telco side, the DSLAM in the CO separates data and phone signals and forwards the data onward to the internet.

While DSL uses telephone infrastructure, cable internet access uses the television companies infrastructure. Fiber optics connect the cable head end to neighborhood junctions, where coaxial cable is used to reach individual houses. Cable internet access requires as special modem, at the cable head end the cable modem termination system (CMTS) serves a similar function as the DSL networks DSLAM - turns the analog signal from cable modems into digital format. Like DSL, divides the network into two asymmetric channels, where downstream transmission rate > upstream transmission rate. Important characteristic of cable internet access is that it is a shared broadcast medium - every packet sent by the head end travels downstream on every link to every home, and vice verse. If several users are simultaneously downloading a video file on the downstream channel, actual rate users receive video will be slower than the aggregate cable downstream rate. Because upstream channel is also shared, a distributed multiple access protocol is needed d to coordinate transmissions and avoid collisions.

Fiber to the Home (FTTH), marketed by verizon as FiOS, connects residences to the internet though optical fibers. Distribution networks can have a dedicated fiber line per household, more commonly fibers are shared by homes and split relatively close to the home. Two competing optical-distribution network architectures that perform this splitting: active optical networks (AONS) and passive optical networks (PONs).

With PONs, each home has an optical network terminator (ONT), connected by a dedicated optical fiber to a neighborhood splitter. Splitter cominbes a number of homes onto a signel, shared optical fiber, connects to an optical line terminator (OLT) in the CO. OLT provides conversion between optical and electrical signals, connects to the internet via a telco router. In the home, users connect to a home router to the ONT and access the internet via this home router. In PON architecture, all packets sent from OLT to the splitter are replicated at splitter.

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

On corporate/university campuses (and more home settings), a local area network (LAN) is used to connect an end system to the edge router. Although there are man y LAN technologies, Ethernet is by far the most prevalent access technology. Ethernet users use twisted-pair coppper wire to connect to an ethernet switch. The Ethernet switch, or a a network of such interconnected switches, is then in turn connected into the larger internet.

In a wireless lan setting, wireless users transmit/receive packets to/from an access point that is connected into the enterprise'se network (usually wired Ethernet), which in turn is connected to the wired Internet. Wirelss LAN access based on IEEE 802.11 techonology called WiFi.

Wide-Area Wireless Access: 3G and LTE

Mobile Devices use wireless infrastructure used for cellular telephony to send/receive packets through base stations operated by cellular network providers. 3G networks provide packet-switched wide-area wireless internet access, 4G and LTE are evolved from this and faster than 3G.

Physical Media

When a system transmits a bit and it is recieved by another system, the bit is snet by propagating electromagnetic waves or optical pulses across a physical medium. Physical medium can take many shapes and doesn't need to be same type for each transmitter/receiver pair along the path. Phhysical media classified into two categoreies: guided media (waves are guided along a solid medium, like copper wire), or unguided media (waves propagate throughout atmosphere and outer space). Capital costs of guided media usually minor in comparison to labor costs of installation.

• Twisted-Pair Copper Wire

  Least expensive, most common guided medium. Pairs of insulated copper wires in spiral pattern, bundled together in a protective shield. Wire pair constitutes a single communication link. Dominant solution for high-speed LAN networking.

• Coxial Cable

  Concentric rather than parallel copper conductors - with this construction and special shielding, can achieve high data transmission rates, common in television sets. Transmitter shifts the digital signal to a specific frequency bad, resulting analog signal is sent from the transmitter to one or more receivers. Coaxial cable can be used as a shared medium. A number of end systems can be connected directly to the cable, with each of the end systems receiving whatever is sent by the other end system.

• Fiber Optics

  Thin, flexible medium that conducts pulses of light, each pulse representing a bit. Support high transmission bit rates, immune to electromagnetic interference, with very low signal attenuation. Preferred medium for long ranger and overseas transmission, but higher costs of optical devices hinders deployment for short-haul development.

• Terrestrial Radio Channels

  Radio channels carry signals in the electromagnetic spectrum. No physical installations, propagate through walls, provide mobility and long distance connections. Environmental considerations determine path loss and shdow fading (decress signal strength over distances and obstructions), multi-path fading (signal reflection off of interfering objects), and interference (duo to other transmissions and other signals). Can be subdivided into short, local and wide area ranges.

• Satellite Radio Channels

  Communication satellites link two or more Earth-based microwave transmitter/recievers, a.k.a ground stations. Satellite recieves transmissions from one frequency band, regenerates signal using a repeater, and transmits signal on another frequency. Two types of satellites used in communications:

  • geostationary satellites

    Permanently remain above same spot on earth, huge distance from ground station introduces substantial delay, but can have high bandwidth.

  • low-earth orbiting satellites

    Closer to earth but not stationary, rotate around earth and may communicate with each other. To provide continuous coverage to an area, many satellites may need to be placed in orbit.

The Network Core

Packet Switching

Internet application messages are broken into packets, each packet travels through communication links and packet switches (two predominant types being routers and link-layer switches). Packets transmitted over each link at a rate equal to the full transmission rate of the link - if an end system or packet switch is sending a packet of L bits over a link with transmission rate R, the time to transmit is L/R seconds.

Store-and-Forward Transmission

Most packet switches use store-and-forward tranmission at the inputs to the inks - packet switch receives full entire packet before transmitting on the outbound link. Introduces a delay which scales by the amount of links packet must traverse: time d over N routers for L bits with R transmission rate:

$$d_{end-to-end}=N \frac{L}{R}$$

Queuing Delays and Packet Loss

Each packet switch has multiple links attached, each with an output buffer/queue, which stores packets router is about to send into that link. Output buffers play a key role in packet switching - if arriving packet needs to be transmitted onto a link but finds the link busy transmitting another packet, arriving packet must wait in output buffer. This introduces queuing delays, which are variable and depend on amount of congestion in network. Since buffer space is finite, a full buffer may also introduce packet loss.

Forwarding Tables and Routing Protocols

When packets arrive at a router in a network, the router examines a portion of the packet's destination address and forwards the packet to an adjacent router - each router has a forwarding table that maps destination addresses (or portions thereof), to that router's outbound links. When packets arrive at a router, the router examines the address and searches its forwarding table to find the appropriate outbound link. The internet has a number of routing protocols that are used to automatically set the forwarding tables - some may determine the shortest path from each router to each destination and use the shortest path results to configure the forwarding tables in the router.

Circuit Switching

There are two fundamental approaches to moving data through a network of links and switches: circuit switching and packet switching. In circuit switched networks, the resources needed along a path to provide communication between two end systems are reserved for the duration of the communication session. In packet switched networks these resources are not reserve: a session's messages use the resources on demand, and may have to wait for access to a communication link. Traditional telephone networks are circuit switched, the connection being called a circuit. When established, it also reserves a constant transmission rate in the network links, consuming a portion of the networks transmission capacity.

Multiplexing in Circuit-Switched Networks

A circuit in a link is implemented with either:

• frequency division multiplexing (FDM)

  Frequency spectrum of a link is divided up among the connections established across the link - the link dedicates a frequency band to each connection for their duration. The width of this band is the bandwidth. FM radio stations also use FDM to share the frequency spectrum between 88 and 108 MHz, each station being allocated a specific frequency.

• time division multiplexing (TDM)

  Time is divided into frames of fixed duration, and each frame is divided into a fixed number of time slots. When network establishes a connection across a link, the network dedicates one time slot in every frame for use in this connection.

Proponents of packet-switching often complain circuit switching is wasteful because dedicated circuits are idle during silent periods - when one person on a circuit-switched telephone network stops talking, the network resources cannot be used by other calls.

A Network of Networks

Connecting people & organizations to the internet is only one part of an ISP - must also interconnect with other ISPs.

• Tier 1 ISPs: Large, internationally reaching ISPs capable of directing traffic to large parts of the globe. Charge smaller ISPs for rights to send it traffic.
• Regional ISPs: Smaller, localized ISPs that pay for the right to send traffic to Tier 1's.
  • Can multi-home, or connect to two or more provider ISPs.
• Points of Presence (POP): group of one or more routers at same location in the providers (Tier 1) network where customer (regional) ISPs can connect to provider ISP.
• Peering: ISPs of the same hierarchy can directly connect their networks together so that all traffic between them passes over the direct connection rather than through upstream intermediaries. Typically settlement (fee) free.
• Internet Exchange Point (IXP): third party company meeting point where multiple ISPs can peer together.
• Content Provider Networks: Private TCP/IP networks dedicated to serving traffic to endpoints operated by private organizations - google's data centers network exclusively with other google data centers. May also connect to Tier 1 and regional ISPs.

Delay, Loss, and Throughput in Packet-Switched Networks

Overview of Delay in Packet-Switched Networks

Types of Delay

• Nodal Processing Delay

  Time required to examine a packets header and determine where to direct it, includes time needed to check for bit-level errors in the packet that occurred during transmission.

• Queuing Delay

  Delay caused when packet waits to be transmitted onto the link, depends on the congestion on the link

• Transmission Delay

  If packets are transmitted in a first-come-first-served manner, packets can be transmitted only after all the packets that have arrived before it have been transmitted. Time to push out a packet.

• Propagation Delay

  Once pushed onto link, packet needs to propagate from router A to router B. Transmission speed depends on the medium. Travel time of packet.

Queuing Delay and Packet Loss

Unlike other delays, may vary from packet to packet. Because of variability, usually expressed in statistical measures - average queuing delay, variance of queuing delay, etc.

Packet Loss will occur when size of queue is exceeded by the amount of incoming traffic and excess packets are dropped by the router.

End-to-End Delay

So far discussion has centered on nodal delay, or the delay introduced by a single router. But total delay can only be estimated by accounting for the sum of delays introduced by all routers between the source and destination of a packet.

End System, Application, and Other Delays

In addition to processing, transmission and propagation delays, other delays can be introduced by applications and local protocols.

Throughput in Computer Networks

Instantaneous Throughput: rate at any time at which system is receiving data.

Average Throughput: rate it took system to receive F bits in T seconds, or F/T.

A networks throughput is constrained by the transmission rate of its slowest component. Most of today's core internet is overprovisioned and experiences very little delay, most bottlenecks occur around access networks.

Protocol Layers and Their Service Models

Layered Architecture

To provide structure to the design of network protocols, network designers organize protocols - and the network hardware and software that implement them - in layers. Each protocol belongs to a layer, and offers services to the layer above- the service model of a layer. Protocols of various layers are called the protocol stack. The internet protocol consists of five layers:

• Application Layer

  Where network applications and their protocols reside. Includes HTTP, SMTP, FTP, DNS.

  Packets of information in this layer called messages.

• Transport Layer

  Transports application layer messages between application endpoints. Two protocols, TCP or UDP.

  Packets of information in this layer called segments.

• Network Layer

  Moves segments from one host to another → the transport layer provides an IP address, network layer provides the service of delivering segment to the destination host. Includes the IP protocol, also contains routing protocols that dictate path that packets follow.

  Packets of information in this layer called datagrams.

• Link Layer

  To move a packet between nodes (hosts or routers), the network layer relies on the service of the link layer. At each node, the network layer passes the datagram down to the link layer, which delivers the datagram to the next node along the route. Services provided by the link layer depend on the specific protocol deployed over the link. Ether, WiFi are examples of link layer protocols.

  Packets of information in this layer called frames.

• Physical Layer

  While Link layer moves frames between nodes, physical layer moves individual bits within the frame from one node to the next. Protocols in this layer are link dependent and depend on the transmission medium - Ether has one protocol for twisted-pair copper wire, one for coaxial cable, etc.

  

  Networks Under Attack

  • Risk of malware via the internet
  • Attack servers & infrastructure: DDoS attacks
  • Can sniff packets
  • Can masquerade as trusted user: IP spoofing

2. Application Layer

Network Application Architectures

• client - server architecture
• p2p architecture

Processes Communicating

Processes place and receive messages using sockets, which transfer them across network to other systems sockets. Hosts are identified by ip address, processes by the port number at the given ip address.

Transport Services Available to Applications

• Reliable data transfer

  Processes can pass data into a socket and with confidence the data will be transmitted without error. When transport-layer protocols do not provide this, all data may not be delivered to process, which may be acceptable for fault-tolerant applications.

• T*hroughput*

  In the context of a communication session between two processes along a network path, throughput is the rate at which the sending process can deliver bits to the receiving process. Transport layer protocols can guarantee throughput at specific rates. Applications with throughput requirements are said to be bandwidth-sensitive, while elastic applications can use available throughput.

• T*iming*

  Can provide timing guarantees to applications that have tight timing constraints

• Security

  Can provide confidentiality, integrity, and authentication.

Transport Services Provided by the Internet

TCP Services

• Connection-oriented service

  TCP has client and server exchange control information before messages are exchanged - this handshake prepares client and server. After handshake, a tcp connection exists between the two hosts. Once finished, it must tear down this connection

• Reliable Data Transfer Service

  TCP can deliver data sent without error and in proper order.

UDP Services

• Lightweight, minimal transport protocol - no ordering or congestion controls.

Application Layer Protocols

Application Layer Protocols Define

• Types of messages exchanged
• Syntax of message types
• Semantic meaning of fields
• Rules for determining when and how processes send and respond to messages

The Web and HTTP

Overview of HTTP

HyperText Transfer Protocol allows client and server programs on different systems to exchange messages. HTTP is a stateless protocol, because servers maintain no information about the clients.

Non-Persistent and Persistent Connections

Non-persistent connections send messages across separate TCP connections - after sending responses, connections are left up. Persistent connections sends all requests between to hosts over the same connection. TCP connections are initiated with a 3-way response/acknowledgement process.

HTTP Message Format

File Transfer: FTP

FTP Session: User agent logs into the FTP Server, causing the FTP client process to establish a TCP connection with the FTP server process on the remote host. Uses two parallel TCP connections to transfer a file, a control connection and a data connection. Control is used for sending control information, while data connection transfers files. Because of this separate control connection, FTP is said to send it out-of-band, as opposed to the in-band control connection of HTTP. Is a stateful service, maintains knowledge of every connection.

FTP Commands and Replies

• User userrname
• Pass password
• LIST: list of all files on remote directory
• RETR filename: get a file from current directory of remote host
• STOR filename: put a file into the current directory of the remote host

Electronic Mail in the Internet

Simple Mail Transfer Protocol (SMTP) maintains mailboxes for users on mail servers. Users compose and send emails through their user-agents, to the senders email server, which is sent to the recipients mail server, able to be downloaded by the recipients user-agent. Most mail servers maintained by ISPs, Companies, SysAdmins

POP3 is a simple mail access protocol allowing user-agents to manipulate their mailbox on their mail server. IMAP is more complex, allowing for manipulation of mail on the mail server, creating and moving between floders.

DNS - Internet's Directory Service

Hostnames are alphanumeric identifiers for websites, map to IP addresses.

Services Provided by DNS

• Host Aliasing: hosts can have one or more aliases (with one canonical hostname). DNS can be invoked to find the canonical hostname as well as the IP Address.
• Mail Server Aliasing: Can be invoked by a mail application to obtain the canonical hostname for a supplied alias hostname. The MX record permits a company's mail server and Web server to have identical (aliased) hostnames.
• Load Distribution: When clients make a DNS query, server responds with the entire set of IP addresses, but rotates the ordering of the addresses within each reply. This rotation helps distribute traffic among replicated servers.

How DNS Works

A distributed, hierarchical database:

• Root DNS Servers

• Top-Level Domain (TLD) Servers

  Responsible for domains like .com, .org, .net, .edu. and .gov

• Authoritative DNS Servers

  Every organization with publicly accessible hosts on the internet must provide publicly accessible DNS records that map the names of those hosts to IP addresses - an organizations authoritative DNS server houses these DNS records.

DNS works by querying the root server for the addresses of the TLD server, the TLD servers for the addresses of the authoritative DNS servers, which can be queried for the IP address matching a hostname. This process can be iterative, with each query performed and returned to the local dns server, or recursive, where each server performs and returns the next query. This process benefits from heavy caching.

DNS Records and Messages

DNS Servers store resource records, each DNS reply message carries one or more resource records. A resource record is a four-tuple that contains the fields:

(Name, Value, Type, TTL)

• TTL: Time To Live
• Type: The type of record being stored
• Type=A, Name is a hostname and Value is IP address
• Type=NS, name is a domain and value is the hostname of an authoritative DNS server, used to route DNS queries further along in the query chain.
• Type=CNAME, Value is a canonical hostname for the alias hostname Name
• Type=MX, value is the canonical name of a mail server that has an alias Name.

If a DNS server is authoritative for a particular hostname, then the DNS server will contain a Type A record for the hostname - if not it will contain a Type NS record for the domain that includes the hostname, also a Type A record that provides the IP address of the DNS server in the Value field of the NS record.

DNS Messages

Web Caching

Network entities that satify HTTP requests on behalf of a web server, has own disk storage and caches requests. Lessens traffic load of origin server, network, and reduces the trip time between client and proxy - they are known as content distribution networks.

The Conditional Get

Caching can improve perceived speed for users, but introduces another issue - the copy of the object in the cache may be stale. HTTP has a mechanism to allow cache to verify the object is fresh, the conditional get. These are get messages with a If-Modified-Since: <date>, which allows the cache to determine if it needs to query the origin and refresh the object. The origin server can respond with a fresh object or 304 Not Modified if no new object is needed.

Video Streaming and Content Distribution Networks

Netflix and YouTube were 37% and 16% of internet traffic in 2015. Streamed video has a high bit rate, with higher bit videos giving higher traffic. The video must be streamed with an average throughput at least as large as the bit rate of the compressed video.

HTTP Streaming and DASH

With HTTP video streaming, video is stored as a file under a URL. Once TCP connection is established, the video is sent to the client where it is stored in a buffer, where it can begin streaming once a certain buffer is reached. With Dynamic Adaptive Streaming over HTTP, the client requests seconds at a time and the server responds with highest bit rate that can be transmitted with available throughput. These differing bit rate files are stored under different URLs, which are transmitted in an intial manifest file.** The client can choose which bit rate to request.

Content Distribution Networks

Manage servers in multiple geographically distributed regions to serve content to users. May be a private CDN, owned by the content provider, or a third party CDN, managing conent on behalf of multiple providers. CDNs typically adhere to one of two placement philosophies:

• Enter Deep: Server clusters are deployed in access ISPs , closer to users.
• Bring Home: Server clusters deployed in IXPs, easier to manage at a higher cost to user speed.

CDNs use DNS to intercept requests for servers. At the core of a DNS cluster is the cluster selection strategy, a mechanism for dynamically selecting a server to respond to a query. Simple strategy is the geographically closest or least hops. Can also perform real-time measurements to find best servers for clients.

3. Transport Layer

The transport layer provides communication services directly to the application processes running on different hosts.

Introduction & Transport Layer Services

Transport layer provides for logical communication - abstraction that allows hosts to feel as if they are directly connected, not through layers of links and routers. Breaks up messages from application layer into segments and passes them to the network layer.

Relationship between Transport and Network Layers

Transport layer provides logical communication to processes running on different hosts, the network layer provides logical communication between hosts. Different transport layer protocols can provide differing services to the application layer.

Overview of the Transport Layer in the Internet

Two distinct protocols defined in the transport layer:

• User Datagram Protocol (UDP): unreliable, connectionless service
• Transmission Control Protocol (TCP): reliable, connection-oriented service

The Internet Protocol is protocol defined on the Network layer, providing services to the transport layer. IP service model is a best-effort delivery service, and tries but does not guarantee any delivery between connected hosts - is said to be an unreliable service. Each host has an IP address.

UPD and TCP extend IP's delivery service between two end systems to a delivery service between two processes running on said end systems. Extending host-to-host delivery to process-to-process is called transport-layer multiplexing and demultiplexing. Also provide integrity checking by including error-detection fields in the segment headers. Error-checking and process-to-process delivery are the only services UDP provides.

In addition to the guarantees, TCP also provides reliable data transfer - TCP ensures data is delivered correctly and in order, converting IP's unreliable service to a reliable one. Also provides congestion control, preventing any one TCP connection from swamping links and routers between hosts with excess traffic, by regulating the rate of sending TCP connections, and so gives each connection an equal share of the link bandwidth.

Multiplexing and Demultiplexing

At a high level, demultiplexing involves inspecting the assigned port number by the incoming segment and directing the segment to the socket associated, to pass through to the underlying process. Uses the source port number and destination port number to achieve this direction, the port numbers 0 → 1023 are well-known port numbers and reserved for use in well-known protocols.

Connectionless Multiplexing and Demultiplexing

When creating a UDP socket with python:

client = socket(socket.AF_INET, socket.SOCK_DGRAM)

Transport layer automatically assigns a port number in range 1024 ≤ 65535. Typically the client side allows transport layer to assign port number, whereas server side assigns specific port number. With port numbers attached, multiplexing and demultiplexing are simple: data passed into sockets are assigned source and destination port numbers, passed to network layer which assigns an IP address and then delivered to the receiving host. This host accepts the datagram and extracts the segment to deliver to the specified socket. This socket passes the message onto the receiving process. A UDP socket is fully identified by a two-tuple consisting of a destination IP address and destination port number (contains four values, but other two are neglible).

Connection-Oriented Multiplexing and Demultiplexing

TCP socket is fully identified by a four-tuple: (source IP, source port, destination IP, destination port). TCP servers have a handshake socket running to accept new incoming connections, part of establishing process moves the communication to another port on the server. This new port is set in the four-tuple and used in subsequent communication. As a result, two connections to the same server would have traffic directed to separate ports, whereas in UDP these connections could be made to the same port.

Web Servers and TCP

If accepting server uses non-persistent TCP sessions, incoming connections will have to perform new handshake for subsequent requests - this could severely impact performance.

Connectionless Transport: UDP

Provides very little above the services offered by the network layer: error checking and multi/demultiplexing. Used by DNS and few other applications, provides finer application level control over data sent, no connection established, no connection state, and smaller packet headers.

UDP Segment Structure

Principles of Reliable Data Transfer

Within a reliable channel, no bits are corrupted or lost, and all are delivered in the order in which they are sent - reliable data transfer protocols guarantee these services. TCP uses tools to allow the use of the unreliable network protocol in a reliable way. Unidirectional data transfer involves only the sending of data one way, as opposed to bidirectional data transfer.

Building a Reliable Data Transfer Protocol

Reliable Data Transfer over a Perfectly Reliable Channel

If underlying channel is perfect, a protocol is simple. A Finite State Automata for the senders and receivers would only have one state: waiting for call - which an incoming or outgoing message would invoke to perform a transition back onto itself.

Reliable Data Transfer over a Channel with Bit Errors

Two more states would be needed: one to acknowledge that message has been received intact (OK), and another to acknowledge that message was corrupted and retransmission is needed (REPEAT). Reliable data transfer protocols based on retransmission are known as Automatic Repeat reQuest (ARQ) protocols. These protocols require:

• Error detection: receiver needs means to determine whether the message has been corrupted (checksums)
• Receiver Feedback:** sender needs means to determine whether to retransmit data if last transmission corrupted.
• Retransmission

Protocols that will not send next piece of data until the positive acknowledgement of the last transmission are known as stop and wait protocols.

In case of errors in ACK/NAK packets, there are different possibilites:

• Add enough checksum bits to allow the sender not only to detect but also recover from bit errors - solves cases of corrupted packets but not lost packets.
• Resend current packet when it receives a garbled ACK/NAK response - introduces duplicate packets into the channel.

A simple solution involves adding a new field to the data packet and having send number packts by putting a sequence number into this field. Reciever only need check this number to determine whterh or not received packet is a retransmission. ACK/NAK responses need to record which packet the are acknowleding. Out of order packets can be handled by sending an ACK for a received packet - if sender gets two ACK's in a row (duplicate ACKs) it knows that the last packet was not received.

Reliable Data Transfer over a Lossy Channel with Bit Errors

In addition to corrupting bits, if the underlying channel can lose packets, a protocol must address how to detect packet loss and how to handle it. Handling packet loss can be managed with the mechanisms detailed previously. Detecting packet loss involves deciding a time threshold above which packet loss was likely and then retransmitting, at the risk of introducing duplicate packets into the channel. Senders do not know whether a packet, or ACK, or NAK was lost, but all cases dictate retransmission. This means setting a countdown timer t that can interrupt the sender after a period of time, so the sender can start the timer after a packet is sent, interrupt the timer after ACK/NAK received, or stop the timer.

Pipelined Reliable Data Transfer Protocols

The protocol as it stands is functionally correct, but it's stop and wait nature gives it significant perfomance problems. To solve this performance issue a technique pipelining is employed. Pipelining has consequences for reliable data protocols:

• range of sequence numbers must be increased, since each in-transit packet must have a unique sequence number
• send and receivers may have to buffer more than one packet - sender must buffer packets that have been transmitted but not yet acknowledged. Buffering of correctly received packets may also be needed.
• Range of sequence numbers needed and buffering requirements will depend on the manner in which protocol responds to lost/corrupted/overly delayed packets. Two approaches toward pipelined error recovery: Go-Back-N and selective repeat.

Go-Back-N (GBN)

With this protocol the sender is allowed to transmit multiple packets without waiting for an acknowledgement - constrained to have no more than some maximum allowable number N of unacknowledged packets in the pipeline. The range of permissible sequence numbers for transmitted but not yet acknowledged packets can be viewed as a window of size N over the range of sequence numbers. As the protocol operates, this window slides forward over the sequence number space - often referred to as the window size and GBN as a sliding-window protocol. GBN sender must respond to three types of events:

1. Invocation from above: when called from above, sender first checks to see if window is full. If not full, packet is created and sent - if full, send returns data back to upper layer to try again later.
2. Receipt of ACK: acknowledgements for a packet with sequence number n will be taken to be a cumulutative acknowledgement, indicating that all packets with sequence number ≤ n have been correctly received.
3. A timeout event: If a timeout occurs, all packets that have been previously sent but not acknowledged are resent. If there are no packets outstanding, timer is reset.

When packets are received correctly and in order, receiver sends an ACK for packet n and delivers te data portion of the packet to the upper layer. In all other cases, the receiver discardsd the packet and resends an ACK for the most recently received in order packet. Out-of-order packets are discarded.

Selective Repeat

There are scenarios in which GBN itself suffers from performance problems - when window size and bandwidth-delay product are large, many packets can be in the pipeline and retransmission can be expensive. Selective Repeat protocols avoid unnecessary transmission by having the sender transmit only those packets it thinks were lost/corrupt. Requires receiver to individually acknowledge correctly received packets. Window of size N again used to limit number of outstanding, unacknowledged packets in pipeline. Unlike GBN, send will have already received some ACKs from for some of the packets. SR receiver acknowledges correctly received packets regardless of whether it is in order - out of order packets are buffered. Receiver will also reacknowledge already received packets with certain sequence numbers below the current window base, so the sender window will move forward. The size of the window must be at most 1/2 of N.

Connection-Oriented Transport: TCP

The TCP Connection

TCP is said to be connection-oriented because before two processes can communicate, the two must handshake by sending some preliminary segments to establish the parameters of the ensuing data transfer. This connection state resides entirely in the two end systems, since the TCP protocol only runs in the end systems and not in the intermediate network elements.

A TCP connections provides a full-duplex service: if there is a TCP connection between Process A and Process B on another, application-layer data can flow from both, to both, simultaneously. It is also point-to-point, meaning between exclusively two processes.

To establish a connection, two processes perform a three-way handshake: client identifies IP and port of the server it would like to connect to, the server responds to this, then the client responds to the acknowledgement.

Data sent over the network is placed into the socket and into TCPs send buffer, which was set aside during the initial 3-way handshake. TCP will periodically take data off the send buffer and pass data into the network layer. Maximum amount of data that can be taken is limited by the maximum segment size (MSS), typically determined by taking the length of the largest link-layer frame that can be sent by the local sending host (maximum transmission unit, or MTU). and then setting the MSS to that value, less the length of the TCP/IP headers. TCP pairs chunks of client data with TCP headers, forming TCP Segments. Upon reception, these segments are placed into the receivers buffer.

TCP Segment Structure

• sequence and acknowledgement number are used by TCP in establishing a reliable data transfer service
• receive window is used for flow control
• header length field specifies the length of the TCP header in 32-bir words - can be of variable length because of the options field (usually empty, so typically 20 bytes)
• options field used when sender/receiver negotiate the MSS or as a window scaling factor in high-speed networks
• flag field contains 6 bits:
  • ACK used to indicate that value in acknowledgement field is valid
  • RST, SYN, FIN used for connection setup and teardown
  • PSH indicates receiver should pass data to the upper layer immediately
  • URG marks there is data in this segment that send-side upper layer has marked 'urgent'.

Sequence and Acknowledgement Numbers

TCP views data as unstructured and ordered stream of bytes - the sequence number for a segment is the byte-stream number of the first byte in the segment. The acknowledgement number is the sequence number of the next byte that is expected from the sender. Because TCP only acknowledges bytes up to the first missing byte in the stream, TCP provides cumulative acknowledgements.Typically when given out-of-order packets, TCP clients will buffer these packets until an orderly stream is created. Acknowledgements for data are piggybacked - included in data transmissions to the other system.

If no ACK is received within the timeout interval, the sender will retransmit the smallest sequence number packet in the window. If the receiver detects a missing packet, it may resend an ACK for the last received packet. If three ACKs are received for the same packet, the sender interprets this to meant that the next packet was lost and will trigger a fast retransmit, resending the lost packet before the timeout has expired.

Flow Control

F*low control service* eliminates the possibility of the sender to overflow the receivers buffer. Its a speed matching service - matches the rate at which the sender sends with the rate the receiver can receive. Sender maintains a variable called the receive window, gives sender an idea of the free space avaialable in the receiver buffer.

TCP Connection Management

Setup:

1. Client-side TCP sends a special TCP segment to server-side TCP with SYN bit == 1, chooses a random initial sequence number and places into sequence number field. Known as the SYN segment.
2. Server allocates the TCP buffers and variables, sends a connection granted segment to client, this segment has SYN==1, acknowledgement field to sequence number + 1, chooses own sequence number and places into its sequence number field. Known as the SYNACK segment.
3. Client allocates buffers and variables for the connection, sends server segment acknowledging the servers chosen sequence number, SYN == 0, known as the ACK, may contain client-server data.

Teardown:

1. Client TCP send segment with FIN == 1
2. Server sends acknowledgement segment, then sends own shutdown segment with FIN == 1.
3. Client acknowledges server shutdown.
4. Deallocation complete

Typical States of a TCP Connection

If host receives a TCP segment which does not match any open sockets, an RST segment is sent. For UDP, a host sends a special ICMP datagram.

Syn Flood Attacks are DoS attacks in which an attacker sends a server SYN packets forcing them to allocate buffers which are never used. Guarded against with SYN cookies: when server receives a SYN segment, creates a TCP sequence number with hash of source + destination IP addresses - the cookie. Server does not remember the cookie or any other state information. Legitimate clients will return an ack reponse with the cookie + 1 value, and the server will verify this value and allocate resources for subsequent communications. SYN attacks will fail, as the server has not allocated any resources to the original, bogus SYN segment.

NMap works by sending a TCP SYN segment to the port on the target host. If a SYNACK segment is received, the port is open. If an RST segment is received, SYN reached the target port but no application is running on this port, but not blocked by a firewall. If nothing is received, likely blocked by a firewall.

Principles of Congestion Control

Causes and Costs of Congestion

• Cost: Large queuing delays are experienced as the packet arrival rate nears the link capacity.
• Cost: Sender must perform retransmissions in order to compensate for dropped packets due to buffer overflow.
• Cost: Unneeded retransmissions by the sender in the face of large dealys may cause a router to use its link bandwidth to forward unneeded copies of a packet.
• Cost: When a packet is dropped along a path, the transmission capactiyt that was used at each of the upstream links to forward that packet to the point it was dropped were wasted.

The rate at which the transport layer sends segments into the network is sometimes refered to as the offered load into the network.

Approaches to Congestion Control

End to End Congestion Control

Network layer provides no explicit support to the transport layer for congestion control. Heuristics (round trip time) of the observed network behavior are used to infer network congestion. Typical behavior of TCP.

Network-Assisted Congestion Control

Network-layer components provide explicit feedback to the transport layer to help determine congestion. Feedback typically takes form of choke packet, other form could include router marking a field in packet to indicate congestion, and receive sends an acknowledgement to router.

TCP Congestion Control

Approach taken by TCP involves each sender limit the rate at which it sends trafffic into its connections, as a function of perceived network congestion. The amount of unacknowledged data a sender may transmit may not exceed last_byte_sent - last_byte_acked <= min{congestion window, receive window. This constraint limits the amount of unacknowledged data the sender, indirectly limiting the sender's send rate. When there is excess congestion, router buffers along the path overflow, dropping datagrams. The receipt of triplicated ACKs in response to this loss is perceived as an indication of congestion by the sender. The timely receipt of ACKs and lack of dropped packets is indicative of an underutilized network by the sender, causing it to increase its congestion window and transmission rate - this self-modulation is called self-clocking. TCP determines transmission rates in accordance with some principles:

• A lost segment implies congestion, decreasing senders rate
• An acknowledged segment indicates network delivery, increasing transmission rate when an ACK arrives for a previously unacknowledged segment
• Bandwidth Probing: Senders increase transmission rates until experience dropped packets, then back off and slowly begin increasing rates again.

TCP Congestion Control Algorithm

Slow Start

When TCP connection begins, congestion window is initialized to small value of 1 MSS, so initial sending rate roughly MSS/RTT. Increases by 1 MSS every time a segment is first acknowledged. So one segment is sent and ACKed, leading two segments sent, then four - rate doubles every RTT. If a loss event occurs, congestion window reset to 1 and slow start threshold set to half of congestion window, or doubling may stop when congestion window reaches or surpasses the value of the slow start threshold. TCP then transitions into congestino avoidance mode. If triplicate ACKs are received, TCP retransmits packet and enter fast recovery state.

Congestion Avoidance

When this state started, congestion window set to half of previous value. Instead of doubling rate in this mode, TCP increases rate by 1 MSS every RTT. When loss occurs, congestion window set to half its previous value, and records value of slow start threshold to be half the value of the congestion window when triplicate ACKs were received. Fast recovery state entered.

Fast Recovery State

Value of congestion window increased by 1 MSS for every duplicate ACK received for the missing segment that caused transition into this state. When ACK arrives for missign segment, TCP enters the congestion avoidance state after deflating congestion window. If a timeout occurs, fast recovery transitions into slow-start state after setting congestion window to 1 MSS, and slow start threshold to half of congestion window value when loss occurred.

Macroscopic Description of TCP Throughput

The network drops a packet from the connection when the rate increases to W/RTT, where W is value of window size bytes when loss event occurs. The rate is cut in half and the increases by MSS/RTT every RTT until it again reaches W/RTT, this process repeats indefinitely.

$$\text{Avg Connection Throughput} = \frac{0.75 \cdot W}{RTT}$$

Fairness

Because of these congestion control mechanisms, TCP connections will naturally gravitate towards fairly sharing available throughput. UDP, with no congestion control, runs the risk of crowding out TCP connections.

TCP Splitting

A technique to improved perceived performance by deploying front-end servers closer to the user, and breaking the TCP connection at the front-end server. Client establishes a TCP connection to the nearby frontend, and the front maintains a persistent TCP connection to the back-end data center with a very large TCP congestion window. Also helps reduce retransmissions caused by losses in access networks.

Explicit Congestion Notification (ECN)

Recent extensions to TCP & IP have been implemented that allow the network to explicitly signal congestion. Two bits in the Type of Service field of the IP datagram header. one setting of the ECN bits used by router to indicate congestion. This is received by the receiving host and communicated to the sending host. Second bit used by hosts to indicate to router that they are ECN capable. On reception, the host receiving the congestion bit notifies the sending hosts TCP, which halves the congestion window - same as if it had lost a TCP segment.

4. The Network Layer

Introduction

The network layer has two important functions, forwarding and routing. Some network architectures also have a third function, connection setup, which requires the routers along the chosen path to handshake with each other before data will flow. Control of forwarding/flow tables can be organized with two approaches:

• per-router control: both forwarding and routing functions maintained inside router
• logically centralized control: logically centralized controller computes and distributes forwarding tables to be used by routers. SDN controllers allow these tables to implement the actions it computed in the flow table.

Forwarding and Routing

• forwarding: When a packet arrives at a router's input link, it must be moved to the appropriate output link.
• routing: Network layer must determine the route or path taken by packets as they flow from sender → receiver, the algorithms that calculate these paths are routing algorithms.

Every router has a forwarding table, whose entries indicate the outgoing link interface that packet will be forwarded to. Link-layer switches base their forwarding decisions on values in the fields of the link-layer frame, also known as link layer devices. Routers base their decision on the values in their forwarding tables.

Network Service Models

Possible services of the network layer:

• guaranteed delivery: packets will arrive at their destination
• guaranteed delivery with bounded delays: both guarantees delivery and within certain time thresholds

Services could also be provided to a flow of packets:

• in-order packet delivery
• guaranteed minimal bandwidth
• guaranteed maximum jitter: amount of time between the transmission of two packets at the sender is the same (or differs by no more than some value) as the amount of time between their receipt.
• security services: Using encryption to provide confidentiality, integrity and authentication

The Internet's network layer provides a single service: best-effort service - timing nor receipt of packets is guaranteed. The internet makes minimal demands on its network service model, simplifying it as much as possible. Other network architectures are the C*onstant Bit Rate (CBR) ATM network service* (providing transmission for audio/visual traffic), or Available Bit Rate (ABR) ATM network service, providing for ordering and transmission rate guarantees.

Virtual Circuit and Datagram Networks

Computer networks that provide only a connection service at the network layer are called vritual circuits, whereas networks that provide only a connectionless service at the network layer are datagram networks.

Virtual-Circuit Networks

Consists of a path (series of links and routers) between source → destination hosts, VC numbers, one number for each link along the path, and entries in the forwarding tables in each router along the path. Packets within a VC will carry their number in their header, intervening routers will replace this number. In such a network, routers maintain connection state information for the ongoing connections - every time a new connection is established & released the forwarding table is updated. There are three phases in a VC - setup, teardown, data transfer.

The messages that systems send into a VC to begin or end a session are called signalling messages, and their protocols signalling protocols. Forwarding tables are modified at connection setup/teardown.

Datagram Networks

Transmitting a packet involves addressing it with the desired destination address and pushing into the network - no VC setup and routers do not maintain state information. Routers use their forwarding tables and packets destination address to find appropriate output link interface. Routers find the longest matching prefix of the packet's destination address to an entry in their forwarding tables. Forwarding tables are modified by routing algorithms, typically every 1-5 minutes.

Whats Inside a Router?

Performs the forwarding function of the network service layer, the actual transfer of incoming link interfaces to the appropriate outgoing link interfaces. Four router components can be identified:

1. Input ports

   Terminates an incoming physical link at a router. Performs link-layer functions neded to interoperate with the link layer at the other side of said link. Lookup function is performed at the input port, where the forwarding table is consulted and outgoing link interface is chosen, also forwards control packets to the routing processor.

2. Switching Fabric

   Connects input ports → output ports

3. Output Ports

   Receives packets from switching fabric and transmits to the outgoing link by performing link and physical layer functions.

4. Routing Processor

   Executes routing protocols, maintains routing tables and attached link state information, along with network management functions.

The forwarding functions are are called the router forwarding plane, often implemented in hardware for speed, while control functions in software.

Input Processing

Provides line termination, data link processing (protocol, decapsulation), and lookup, forwarding, and queuing function of the input link interface. The forwarding table typically kept in a shadow copy local to each port for speed, copied from the router processor via a PCI bus. In short, readies the packet for the switching fabric.

Switching Fabric

• Switching via memory: earliest and simplest model, still done today.
• Switching via a bus: input port transfers a packet directly to output port over a shared bus with no input from routing processor. Typically done by prepending a switch-internal header to packet, stripped at output port. Bottlenecks the router, as only one packet can travers bus at a time.
• Switching via an interconnection network: 2N buses connecting N input/output ports. Horizontal and vertical buses at a crosspoint, which can be opened or closed by fabric controller. Can forward multiple packets at a time, but not to the same output port.

Output Processing

Selects and de-queues packets for transmission, performing link-layer and physical-layer transmission functions.

Where does Queuing Occur?

Packet loss occurs are queues are filled and routers forced to drop packets. Depending on the switching fabric and output transmission rates, queuing may occur at input and output queues. A consequence of output port queuing is that a packet scheduler at the output port must choose which packet should be transmitted, and there are many algorithms that have been developed to determine which packets to prioritize - known as Active Queue Management (AQM). If switch fabric is too slow, input port queuing may occur. This can be exacerbated by head-of-line (HOL) blocking, where packets must wait in their input queue for the switching fabric to become available - even if their path to the output link interface is clear.

Packet Scheduling

First In First Out (FIFO) scheduling discipline selects packet in the same order in which they arrive.

Priority Queuing classifies incoming packets into priority classes

Routing Control Plane

Many of today's routers are decentralized - the control plane reside and executes fully within individual routers. New research is experimenting with control planes external to the router, with updates via an API.

The SDN Control Plane

Four key characteristics of an SDN architecture:

1. Flow based forwarding: Packet forwarding by SND packet switches can forward based on any number of header fields in the transport/network/link layers
2. Separation of data and control planes: Data planes are switches implementing match + action rules from their flow tables. Control planes compute and propagate these flow tables.
3. Network control functions: external to data-plane switches: Software computing flow tables executes on servers that are distinct and remote from switches. Control plane consists of SDN controllers that maintains accurate network state information and provides it to network-controlled devices.
4. A programmable network: The network accepts programming from applications running in the control plane - the 'brains' of the network, using the APIs provided by the SDN controller.

The SDN Control Plane: SDN Controller and SDN Network-control Applications

The Internet Protocol: Forwarding and Addressing in the Internet

IPv4 Datagram Format

• Version: The IP version of the packet
• Header Length: needed because of the options, typically 20 bytes
• Type of Service (TOS): allows for datagrams to be discriminated against at the preference of the router administrator.
• Datagram length: Typically no larger than 1.5kb
• Identifier, flags, fragmentation offset: involved in the ip fragmentation of an IPv4 datagram
• Time to live (TTL): ensures datagrams do not live forever, decremented every time it is processed by a router, dropped if 0.
• Protocol: Used only when datagram reaches final destination, indicating TCP/UDP traffic.
• Header checksum: aids in detection of bit errors in datagram header - not the data
• Options: rarely used

IP Datagram Fragmentation

Amount of data link-layer frame can vary, labeled the maximum transmission unit (MTU). Because datagrams are encapsulated in link-layer frames, the MTU places a hard limit on length of an IP datagram. This could be problematic, as different links along route can use different protocols, each with differing MTUs. When a link with smaller MTU encountered, the packet fragments, broken up into smaller pieces to be reassembled by the end host. Each fragment datagram stamped with source, destination and ID of original datagram. Flag bit set to 1 for nonterminal datagrams, 0 for the last fragment. Offset field used to specify where the fragment fits into the original datagram.

IPv4 Addressing

The boundary between a host and the physical link is called an interface, IP addresses are associated with interfaces, rather than with the host or router containing said interface. IPv4 addresses are 32 bits long, ~ 4 billion possible IPv4 addresses. Written in dotted decimal notation, each byte separate by a peiod. Every interface in the global internet has a unique IP address, portion of the address determined by the subnet it belongs to. The network interconnecting hosts without routers (could be ethernet lan, WiFi, etc.) is a subnet, IP addressing assign an address to a subnet, e.g., 223.1.1.0/24, where the /24 (can be any 0 ≤ n ≤ 31) is a subnet mask: indicating that the left 24 bits define the subnet address, the right 8 bits the host. Additional hosts connected to this subnet would have the same 24 leftmost bits and a unique 8 rightmost bits.

The Internets address assignment strategy is called Classless Interdomain Routing (CIDR), which generalizes the notion of subnet addressing. The 32bit IP address is didvided into two parts of form a.b.c.d/x,** where x indicates the number of bits in the first part of the address. The x most significant bits constitute the network portion of the address (called the prefix or network prefix). Organizations typically assigned a block of contiguous addresses (addresses with common prefix). When routers outside the organization route traffic to it, only this prefix is considered. The remaining 32 - x ****bits distinguish among devices within the organization, considered when routing traffic within the organization, may have additional subnetting structure. The IP broadcast 255.255.255.255 destination would cause the datagram to be delivere to all hosts on the same subnet.

Obtaining a Block of Addresses

Network Admin would contact ISP, which would allocate from within its own allocation. ISPs or other organizations obtain these addresses from Internet Corporation for Assigned Names and Numbers (ICANN), who both allocates IP addresses but also manages DNS root servers and resolving domain name disputes. ICANN allocates addresses to regional registries.

Obtaining a Host Address: Dynamic Host Control Protocol

Once a block of IPs is obtained, an organization can assign individual IPs to the host and router interfaces in organization. Admins typically manually configure the IP addresses into routers with a network configuration management tool, but hosts typically rely on Dynamic Host Control Protocol (DHCP), which allows a host to be allocated an IP address automatically - host can be given same IP every time it connects or it can receive a temporary IP address. Because of the ability to automate network related aspects of connecting hosts into the network, known as a plug-and-play protocol. DHCP is a client-server protocol, where client is a new host wanting network configuration information (including IP for itself). Subnets typically have own DHCP server, or a DHCP relay agent (typically a router) will know the address of the server.

DHCP protocol is a 4 step process:

1. Server Discovery: DHCP Discover Message is broadcast to the subnet (IP address 255.255.255.255) on port 67, with source address 0.0.0.0
2. DCHP Server Offer: DHCP Offer Message is broadcast by server to all nodes on the subnet, containing transaction ID of discover message, proposed IP of the client, network mask, and IP addres lease time.
3. DHCP Request: Client responds with DHCP Request Message, echoing back the configuration parameters.
4. DHCP ACK: server reponds with DHCP ACK Message, confirming the parameters.

Network Address Translation (NAT)

If IP addresses in the contiguous allocation have already been exhausted, subnet can be grown by implement NAT. NAT enabled routers have a public IP address, and a realm with private addresses,** where these private addresses only have meaning within that network. Hosts within this network can communicate with each other using these private addresses, but to the outside internet they appear as only a single device with single address. To communicate with the outside internet, NAT routers use a NAT Translation Table to record traffic. NAT records the private IP and port of the host to an arbitrary port number: when receiving incoming traffic, NAT uses this port number to lookup the address and port of the private host where the traffic should be directed.

Internet Control Message Protocol (ICMP)

ICMP used by hosts and routers to communicate network-layer information - most often error reporting. Considered part of IP but technically lays just above IP, as ICMP messages are carried inside IP datagrams and is specified and demultiplexed from datagrams just as TCP and UDP are.

ICMP messages have a type and code fied, and contain the header and first 8 bytes of the IP datagram that caused the message to be generated. The ping program uses ICMP type 8 code 0 messages to the specified host - who send back a type 0 code 0 ICMP echo reply. Traceroute is also implemented with ICMP packets. Traceroute sends a series of ICMP messgaes, beginning with a TTL of one and incrementing for each subsequent message. When these datagrams reach Nth router, the TTl is 0 and the router responds with an ICMP warning message containing the information of the router. When the datagrams reach the destination, the address of an unlikely port casuses the host to respond with a separate error message.

IPv6

Created because fo the foreseen exhaustion of the IPv4 address space and augment the original IPv4 protocol.

IPv6 Datagram format

Has expanded addressing capabilities, as the addresses are 128 bits long. Also contain an anycast address, allowing the datagram to be delivered to any one of a group of hosts. Streamlined header has a fixed length, allowing for faster router processing. Flow labeling and priority allows router discrimination of traffic.

• Next Header: protocol of the data payload
• Hop limit: similar to TTL

IPv6 does not allow for fragmentation, if datagram is too big it return an ICMP "Packet Too Big" Error. There is no header checksum, nor options.

Transitioning IPv4 → IPv6

Dual Stack: Enabling devices to handle both IPv4 and IPv6 traffic. Can lead to situations where two IPv6 capable nodes interact in IPv4.

Tunneling: Creating an IPv4 datagram with the IPv6 datagram as its data, addressed to the next node in the route. This node will extract the IPv6 datagram and process it as normal.

Routing Algorithms

The job of routing is to determine good paths (or routes), from senders to receivers, through the network of routers. Hosts usually directly attached to one router (the default router) for the host (also called the first-hop router for the host). When hosts send a packet they are forwarded to its default, or source router, to be delivered to the default router of the destination host, or the destination router. The purpose of a routing algorithm is to find a 'good' path from source to destination router, where good is the least cost. Real-world concerns (policy issues, packet x should not traverse network y) also complicate the question of routing.

Routing algorithms are models as graphs, where the edges have costs to be assigned by the creator (this could be physical length of the link, link speed, or cost). Given two nodes interconnected by paths, one or more of these paths is a least-cost path. The least-cost problem involves finding a path between source and destination - if if all the edges have the same cost, the least-cost path is also the shortest path. Broadly, routing algorithms can be classified by whether they are global or decentralized:

• global routing algorithm: computes the least-cost path between a source and destination using complete, global knowledge about the network. The algorithm obtains this information before performing the calculation - it can be run at one site (a centralized global routing algorithm) or replicated at multiple sites. The key feature is that a global algorithm has complete information about connectivity and link costs. They are often referred to as link-state (LS) algorithms.
• decentralized routing algorithm: calculation of the least-cost path is carried out in an iterative, distributed manner. No node has complete information about all the costs, each node begins with only the knowledge of the costs of its only directly attached links. A node gradually calculates the least-cost path to a destination through an iterative process of calculation and exchange of information with its neighboring nodes.

A second broad way to classify routing algorithms is according to whether they are static or dynamic. In static routing algorithms, routes change very slowly, often as a result of human intervention. Dynamic Routing Algorithms change the paths as the network traffic loads or topology changes. While they are more responsive to network changes, they are also more susceptible to problems such as routing loops and oscillations in routes.

A third way to classify routing algorithms is according to whether they are load-sensitive or load-insensitive. Load-sensitive algorithms vary the link costs dynamically to reflect the current level of congestion in the underlying link. Modern load-insensitive algorithms do not explicitly change the link's cost to reflect congestion.

Link-State (LS) Routing Algorithms

For algorithms that require the network topology to be known, this is accomplished by having each node broadcast link-state packets to all other nodes in the network, each packet containing the identities and costs of its attached links. The result of this broadcast is that all nodes have an identical and complete view of the network, and each node can run the algorithm and compute the same paths. The best known of these algorithms is Dijkstra's Algorithm. **

Distance Vector (DV) Routing Algorithm

Where the LS algorithm uses global information, the distance-vector (dv) algorithm is iterative (process continues on until no more information is exchanged between neighbors), asynchronous (does not require nodes to operate in lockstep with each other), and distributed (each node receives some information from one or more of its directly attached neighbors). If d_x(y) is the cost of the least-cost path from nodes x and y, the cost of path (x_1, ... x_p) is the sum of the edge costs, or c(x_1, x_2, ... x_p). The least costs are related by the Bellman-Ford Equation:

$$d_x(y)=\text{min}{c(x,v) + d_v(y)}$$

Where min_v is taken over all of x's neighbors. After traveling from x to v, if we take the least-cost path from v to y, the path cost will be x(c,v) + d_v(y). This solution to the Bellman-Ford equation provides the entries in node x's forwarding table. It also suggests the form of neighbor-to-neighbor communication that will take place in the DV algorithm. The algorithm remains quiescent until a link cost changes. DV-like algorithms are used in many routing protocols in practice, including RIP and BGP.

DV Algorithm: Link-Cost Changes and Link Failure

When a node running DV detects a change in the link cost from itself to a neighbor, it updates its distance vector - if there is a change in the least-cost path, it informs its neighbors. If the cost of a link decreases, the algorithm will reach a quiescent state in linear time. If the cost a link increases, there is a possibility of a routing loop where the packet will remain stuck. This scenario can be avoided using a technique known as poisoned reverse - if node z routes through y to get to x, then z will advertise to y that its distance to x is infinity. Although poisoned reverse solves the problem between two nodes, it will not fix loops of larger than three nodes.

LS vs DV Routing Algorithms

• routing: LS requires each node to communicate with all others via broadcast, but DV each node only needs to talk to their neighbor.
• message complexity: LS requires N * E messages to be sent, DV requires message exchanges between directly connected neighbors at each iteration.
• speed of convergence: LS in N^2 requiring N * E messages. DV converges slowly while potentially suffering from count to infinity problems.
• r*obustness*: Under LS, a router could broadcast an incorrect cost, or could corrupt or drop any packets it received as part of a broadcast. Since LS nodes only compute their own forwarding tables; other nodes perform similar computations. This means route calculations are somewhat separated under LS, which provides some robustness. Under DV, a node can advertise incorrect least-cost paths to any/all destinations. Widely circulated, this bad routing information could crash the internet.

Neither algorithm is an obvious winner, both algorithms are used on the internet.

Other Routing Algorithms

LS and DV are essentially the only routing algorithms used today in practice. Another set of algorithms are used on circuit-switched networks, called circuit-switched routing algorithms.

Hierarchical Routing

Naive implementations of DV and LS are two simplistic for real-world solutions for multiple reasons. The overhead needed to compute, store, and communicate routing information becomes prohibitively large at the scale of hundreds of millions of hosts and routers.Additionally these algorithms ignore administrative autonomy, prohibiting administrators from controlling networks as they desire.

Both of these issues can be solved by organizing routers into autonomous systems (ASs), with each AS consisting of a group of routers that are typically under the same administrative control (ISP, company network). Routers within an AS all run the same routing algorithm and have information on each other - just as in the idealized case. These intra network routing algorithms are called an intra-autonomous system routing protocol. These ASs connect to each other, with one or more routers in an AS being responsible for forwarding packets to destinations outside of the AS - these are the gateway routers. The i*nter-AS routing protocol* (BGP) manages routing traffic between networks, each with multiple gateways - routers receive information from their inter/intra-routing protocols and use that to decide where to forward their traffic. One approach routers use to decide how to forward traffic is hot-potato routing - routers seek to forward their traffic with as little router-to-gateway cost as possible. Neighboring ASs can advertise routing information to each other, with BGP they have flexibility in what they advertise to their neighbors. ISPs can constitute a single AS, or they may break their networks up into multiple networks. The problems are scale and administrative authority are solved by defining autonomus systems, where routers inside networks run intra-AS protocols and ASs run inter-network protocols - intra-AS routers need only know about the routers within their network.

Steps in adding an outside-AS destination in a router's forwarding table:

1. Learn from inter-AS protocol that subnet x is reachable via multiple gateways.
2. Use routing info from intra-AS protocol to determine costs of least-cost paths to each of the gateways.
3. Hot potato routing: choose the gateway that has the smallest least cost.
4. Determine from forwarding table the interface I that leads to least-cost gateway. Enter (x, I) in forwarding table.

Routing in the Internet

Intra-AS Routing in the Internet: RIP

Also known as interior gateway protocols. Two protocols have been used for routing with autonomous systems: Routing Information Protocol (RIP) and Open Shortest Path First (OSPF), which is also closely related to the IS-IS protocol.

RIP is a distance-vector protocol that uses hop count as a cost metric, each link has a cost of 1 (from source router to subnet). The maximum cost of a path is limited to 15, so RIP cannot be used to route networks more than 15 routes in diameter. Routing updates are exchanged between neighbors every ~30 seconds using a RIP response message, these contain a list of up to 25 destination subnets within the AS and the senders distance to each of these subnets. These are also called RIP advertisements. Each intra-AS router maintains a RIP table called a routing table advertising destinations and their hop distance for each subnet in the AS (RIPv2 allows subnet entries to be aggregated). If routers are not heard from every 180 seconds they are considered unreachable, either the neighbor has dies or the connecting link is down and RIP modifies the routing tables accordingly. Routers may also request information from their neighbors regarding routes, RIP requests and responses are send over UDP on port 520. RIP is implemented in an application-layer process (named routed on UNIX), it exchanges messages with neighbors over a standard socket.

Intra-AS Routing in the Internet: OSPF

Typically deployed in upper-tier ISPs (along with related IS-IS), whereas RIP is found in lower-tier ISPs and enterprise networks. A sucessor to RIP, it is a LS protocol using flooding of link-state information and a Dijkstra least-cost path algorithm. OSPF constructs a topological map of the AS, routers locally run Dijkstra to dtermine a shortest-path tree to all subnets (with self as the rot node). Individual link costs can be configured by the adminstrator - some may prefer minimum hops while others attempt to avoid low-bandwidth links.

OSPF protocol broadcasts routing information to all other routers in AS, not just neighbors, broadcasts when there is a change in a link's state, also broadcasts a link's state periodically. Advertisements are contained is OSPF pessages carried directly by IP, protocol itself implements reliable message transfer and link-state broadcast. Also individually checks status of links, and has mechanisms for accessing neighboring router's database of network widw link-state. Routers can be authenticated, preventing maliciuos injection of incorrect information. If multiple paths to same destination exist, all traffic need not be routed through same path. Extensions exist to multicast routing. Can structure AS hierarchically into areas.

Each OSPF AS hierarchical area runs its own OSPF link-state routing algorithm, with each router in an area broadcasting its link state to others in area. Area border routers are responsible for routing packets outside the area. One area is designated the backbone area, which routes traffic between other areas. Inter-area routing requires packets are first routed to an area border router (intra-area routing), then routed through backbone to destination area border router, then on to the destination.

Inter-AS Routing: BGP

Border Gateway Protocol is the de facto standard inter-AS routing protocol in today's internet. Provides ASs means to:

• obtain subnet reachability from neighbors
• propogate reachability from internal AS routers
• determine 'good' routes to subnets w.r.t. reachability and AS policy
• allows each subnet to advertise existence to internet writ large

BGP Basics (simplified - this is extremely complex!)

Pairs of routers exchange information over semipermanent TCP connections, port 179. Typically one such BGP TCP connection for each link that directly connects two routers in separate ASs. Semipermanent BGP TCP connections exist in routers within an AS, creating a mesh of TCP connections - the routers at ends of connections known as peers and the connection a session. Sessions that span ASs called external BGP (eBGP) session, as opposed to internal BGP (iBGP) sessions. BGP allows each AS to learn which destination are reachable - these destinations are CIDR prefixes, each prefix respresenting a subnet or collection of subnets. To distribute prefix reachability over sessions routers share their reachable prefixes, iBGP session distribute these prefixes within AS. When routers learn of new prefix they create an entry in their forwarding table.

Path Attributes and BGP Routes

ASs are identified by globally unique autonomous system number (ASN)(although not every AS has ASN - stub AS exist that only carry traffic for which they are a source or destination, **multi-home stubs also exist that are connected to network through multiple points). When a router advertises a prefix across a BGP session, it also includes a number of BGP attributes - a prefix along with attributes is called a route, so peers advertise routes to each other. Two important routes include AS-PATH, containing the ASs through which the advertisement has passed (detects looping advertisements), and NEXT-HOP, the router interface that begins the AS-PATH (used by routers to properly configure forwarding tables). Also contain attributes allowing routers to assign preferences to metrics to routes, and attribute that indicates how the prefix was inserted into BGP at the origin AS. Gateway routers use their import policy to decide whether to accept or filter the route and whether to set attributes - may omit a route because it does not want to send traffic over one of the ASs in the AS-PATH, or because it has a preferable route to the same prefix.

BGP Route Selection

After routes are distributed using eBGP and iBGP, routes are selected using elimation rules (a simplified summary):

• Routes are assigned a local preference value as an attribute
• Route with shortest AS-PATH is selected
• Closest NEXT-HOP is selected
• If multiple routes still exist, BGP identifiers used

Routing Policy

Peering agreements typically exist between network maintainers stipulating the types of traffic they accept. ISPs often have a rule of thumb stating traffic must either originate or be destined to a host on their network, seek to avoid free riders.

Broadcast and Multicast Routing

In Broadcast Routing, the network layer provides a service delivering a packet sent from a source node to all other nodes in the network; multicast routing enables packets to be sent from a single source to a subset of the network.

Broadcast Routing Algorithms

N-way-unicast approache sends a separate packet from the source to each destination. This is inefficient however - duplicates packet traffic, but also complicates estimation of how many hosts avaible.

Uncontrolled Flooding

Flooding involves each recipient of a packet duplicating and forwarding packet to every neighbor. Could create broadcast storm, where loops in network cause multiple packets to be forwarded.

Controlled Flooding

Sequence-number-controlled flooding has source node put its address and a broadcast sequnce number into a broadcast packet, which is sent to all of its neighbors. Each node maintains a list of source address and sequence numbers it has received, filters incoming packets through them before retransmitting.

Reverse Path Forwarding (RPF) transmits packets only if packet arrived at links only on shortest path back to source.

Spanning Tree Broadcast

A minimum spanning tree can be contructed from the router nodes in the graph, source sends packet to all incident links that belong to the spanning tree, which forward to all their incident links. Creating this tree can be complex, center-based approach is used by creating a rendezvous point, or core. Nodes then unicast tree joins until packet arrives at a node that already belongs to the tree or is the center.

Multicast

Delivers packets to only a subset of network. Needs to identify both the receivers of packet and their addresses. Multicast packets are addressed using address indirection, single identifier is used for a group of receivers, which all receive of a copy of the packet.

Internet Group Message Protocol (IGMP)

Operates between a host and its directly attached router, provides the means for host to inform its router that it wants to join a multicast group. Network-layer multicast algorithms coordinate the multicast routing. IGMP has three message types, inside IP datagrams. Membership query messages determine the set of all multicast groups that have been joined by hosts on that interface. Hosts respond to queries with membership report messages to join the group. Hosts can leave via a leave group message, or by timeout after no longer responding to queries (a soft state).

Multicast Routing Algorithms

Tree of routers constructed that spans all connected hosts and their routers, packets will be routed along this tree.

Packet Scheduling

FIFO

Schedules packets for link transmission the same order they were received.

Priority Queuing

Arriving packets are sorted into classes used to prioritize traffic. Under non-preemptive priority queues, a lower priority packet is not preempted once it begins transmission.

Round Robin and Weighted Fair Queuing (WFQ)

Under round robin scheduling priority is given in an order among the classes. Work conserving queuing never allows the link to idle while there are packets to transmit.

WFQ is a generalized form of round robin where the different classes can have different priorities.

Generalized Forwarding and Software Defined Networking (SDN)

Router forwarding decisions have traditionally been based solely on destination addresses. There has also been a spread of middleware boxes that perform layer-3 functions, re-writing headers or dropping packets. Software Defined Networking has unified many of these network-layer (and some link-layer) functions in an integrated manner. Traditional forwarding performed two steps: matching a destination address and acting by switching the packet to the correct output link. SDNs match plus action paradigm is more generalized, allowing these packet switches (use both layer 2 & 3 addressing, so more generalized than a router or switch) to multi/broadcast, routing packets across multiple hosts like a load balancer, rewriting header values like a NAT, dropping packets like a firewall, or forwarding packets for further Deep Packet Inspection (DPI). Match-plus-switch capability is implemented via a remote controller that computes, installs and updates these tables. OpenFlow is one of the most well-known SDN programs, implementing flow tables that perform the match plus action lookups. Entries in the flow table include header field values to match packets, a set of counters that get updated as packets are matched, and a set of actions to take when a packet is matched. These actions can forward the packet to a specified destination, drop the packet, or modify a field within the packet.

SDN Control Plane

SDN Control Plane is the network-wide logic that control packet forwarding logic. These devices are known as packet switches, as they make forwarding decisions based on information from transport/network/link layers. There are four key features of an SDN architecture:

1. Flow-based forwarding: Packet switch forwards based on values from transport/network/link layers.
2. Separation of data and control planes: Data plane are the network switches that execute decisions of control plane, the servers and software that determine these decisions.
3. Network Control Functions external to Data Plane Switches: SDN Control Plane software that computes the flow tables runs on servers that are distinct and remote from the Data Plane. Control Plane itself is separated into an SDN Controller that maintains & provides accurate network state information, and network-control applications that can control underlying devices.
4. A Programmable Network: Network-control applications are the "brains" of the SDN Control Plane, can control the network devices using APIs offered by the SDN Controller.

The SDN Control Plane: SDN Controller & SDN Network-Control Applications

SDN Controller

1. A Communication Layer: transfers information between the controller and the underlying network device. Devices must also be able to communicate locally-observed events to their controllers, to provide up-to-date views of the network state. This protocol is the lowest layer of the controller architecture, constituting the "southbound" interface, dictating the communication between the controller and the controlled interface.
2. A Network-Wide State-Management Layer: The forwarding decisions copmuted by the control layer require information about the state of the network.
3. Interface to the network-control application layer: Controller interacts with network-control applications through its "northbound" interface. API allows network-control applications to r/w network state and flow tables within state-management layer. Applications can register for notifications to state-changes so they may take action in response to network notification events sent from SDN-controlled devices.

SDN Controllers can be abstracted to be logically centralized, viewed externally as a service offered by a single server - in reality this is a decentralized service implemented by many servers.

OpenFlow Protocol

OpenFlow Protocol operates between an SDN Controller and an SDN-Controlled switch, or other device implementing OpenFlow API over TCP port 6653.

Several types of messages are sent from the controller to the controlled switch:

• Configuration: Controllers can query and manage switch configuration options
• Modify-State: Controllers may add/modify/delete entries in the switches flow table, set switch port properties.
• Read-State: Controllers can collect stats and counter values from switches flow tables and ports.
• Send-Packet: Controller can send specific packets, with specific payloads, out of specific ports. Message itself contains the packet to be contained.

Several types of messages flow from the switch to the controller:

• Flow-Removed: switch informs the controller that an entry has been removed.
• Port-Status: switch can inform controller of change in port status
• Packet-In: Packets arriving at the switch not matching any entries is forwarded to the controller for additional processing, may also be forwarded to the controller by an action.

5. The Link Layer: Links, Access Networks, LANs

Introduction to the Link Layer

Communication channels that connect adjacent nodes (any device running a link-layer protocol) with links. Nodes encapsulate datagrams into link-layer frames and transmit them across their links.

Service Provided by the Link Layer

Link layer protocols all have the same job - moving datagrams between nodes - but services can vary according to the protocol.

• Framing: encapsulation of datagram before transmission
• Link Access: a medium access control (MAC) protocol specifies rules by which frames are transmitted across links. While point-to-point communication is simple to coordinate, coordination between multiple nodes is more complex.
• Reliable Delivery: Guarantees to move datagrams across the link without error. Often used for links prone to high error rates, to avoid forcing a retransmission of a datagram by the host. Can be unnecessary overhead for low bit-error links like fiber/coax/twisted-pair copper and then not provided.
• Error detection and recovery: Receiving node hardware can decide that bits in datagram are incorrect - errors the product of signal attenuation and electromagnetic noise. The inclusion of error-detection bits in the frame allows for detection of such errors, and error correction has the ability to reverse these bits.

Where is the Link Layer Implemented?

The link layer is mostly implemented in network adapters, or network interface cards. Usually a special, single-purpose chip that implements link layer services - so much of the link layer functionality is implemented in hardware. On the sending side, controllers receive datagrams and encapsulates them for transmission across the link. The receiver accepts the frame and extracts the network layer datagram. Error detection is set at the sender and performed by receiver. Most of the functionality implemented in hardware, though some like link layer addressing and activation of the controller hardware implemented in software. On receivers the arrival of a frame triggers a software interrupt that is handled by software.

Error-Detection and Correction Techniques

Bit level error-detection and correction are two services often provided by link layer protocols. Even with such services there is still the possibility of undetected bit errors, so corrupted packets may still be delivered to the network layer. As more sophisticated and better performing techniques incur larger overheads, there is a tradeoff between error-detection and performance.

Parity Checks

Simplest form of error detection is the parity bit. For a message of d bits, an additional one bit is transmitted, whose value is chosen such that number of 1's in the d + 1 bits is even, or odd for odd parity bits. If receiver detects that the parity bit is not correct, it knows there are an odd number of errors, but even numbers of bit errors would be undetected. Errors often do not occur independently, so single-bit parity checks are often not sufficient. In a two-dimensional parity scheme, the d bits are divided into i rows and j columns, and a parity value calculated for each row and column. With this scheme receivers can both detect and correct single bit errors, and detect two bit errors. The ability to both detect and correct errors is known as forward error correction (FEC). They decrease the number of errors received and the round-trip cost of a retransmission.

Checksumming Methods

In checksumming, d bits of data are treated as a sequence of k bit integers. These integers are summed over, with the sum treated as the error-detection bits. The internet checksum carries the 1s complement of this in the segment header. The receiver verifies the data by taking the 1s complement of the sum and checking whether the result is all 1 bits - if any are 0, an error is indicated. Checksumming requires relatively little overhead, but provide relatively weak protections.

Cyclic Redundancy Check (CRC)

Cyclic Redundancy Checks are a widespread error detection technique. CRC codes are also called polynomial codes, since its possible to view the bit string to be sent as a polynomial whose coefficients are the 0/1 values - operations on the bit string interpreted as polynomial arithmetic.

Before sending d bits, both nodes agree on an r + 1 generator bit pattern, G - the leftmost bit of this value must be a 1. For a given piece of data, D, the send will choose r additional bits, R, and append them to D such that d + r is exactly divisible by G. To check, receiver divides d + r to check whether quotient is 0.

Multiple Access Links and Protocols

Point-to-point links directly connect sender and receiver through a single link.

Broadcast links allow multiple sending and receiving nodes to share a common broadcast channel - broadcast because when any one node transmits a frame, the channel broadcasts it, each node receiving a copy. Ethernet and wireless LANs are two broadcast link layer technologies. Broadcast protocols must address the multiple access problem, or how to coordinate the transmissions of multiple sending nodes in the same channel. Two nodes simultaneously transmitting frames results in collisions, with the contents of both frames being combined into one uninterpretable frame. Multiple Access Protocols governing a channel of rate R bits/second should have some characteristics:

• When only one node has data to send, that node has a throughput of R bps.
• When M nodes have data to send, each of these nodes has a throughput of R/M bps - need not have an instantaneuos rate, but average over some time frame.
• Must be decentralized
• Simple and inexpensive to implement

Channel Partitioning Protocols

Time division multiplexing (TDM) is a technique that partitions a broadcast channel's bandwidth among all nodes sharing that channel. TDM divides time into time frames and divides these into time slots, which are then assigned to nodes, who can transmit during these slots - usually divided such that a node can transmit a single packet in one slot. TDM eliminates collisions and i perfectly fair, but nodes are limited to the average rate even when it is the only node with packets to send, and must wait their turn even if they are the only ones to send.

Frequency division multiplexing (FDM) divides the R bps channel into different frequencies, each with a bandwidth of R/N. Each node is assigned a frequency and avoids collisions and divides the bandwidth fairly, but like TDM limits nodes bandwidth even if they are the only node transmitting.

Code Division Multiple Access (CDMA) assigns a different code to each node, which use code to encode the data bits it transmits. Carefully choosing the code allows node to transmit simultaneously yet have their receivers correctly accept their sender's encoded bits despite interference.

Random Access Protocols

Class of protocols in which nodes transmit at the full channel rate, collisions handled by retransmitting frame after waiting a randomly assigned timeout period.

Slotted ALOHA

We assume that:

• All frames consist of L bits
• Time is divided into slots of L/R seconds (time to transmit one frame)
• Nodes start transmissions only at beginning of slots
• Nodes are synchronized such that they know when slots begin.
• If two or more frames detect a collision, all nodes detect collision event before slot ends.

With these assumptions, Slotted ALOHA operates by assiging a probability, 0 ≤ p ≤ 1. Then when node has a frame to transmit, it transmits the entire frame in the next slot. If there is a collision, the frame is retransmitted in each subsequent slot with probability p until a successful transmission. Allows nodes to transmit at the full channel rate and highhly efficient with one active node, but wastes slots with multiple active nodes. Suffers from low throughput.

ALOHA

In the original ALOHA protocol, all nodes synchronize their transmissions at to start the beginning of a slot. Frames are immediately transmitted, if collision detected it will either immediately retransmit with probability p or wait a timeout perioud. Also suffers from low throughput.

Carrier Sense Multiple Access

In both ALOHAs, a nodes decision to transmit is independent of other activity on the channel. Do not implement carrier sensing (ability to listen to channel for current transmissions before beginnning own transmissions), or collision detection (if a transmitting node decides a collision is occurring, it stops transmission). Even with carrier sensing, channel propagation delay (time it takes for a signal to propagate to nodes), may cause a collision in transmissions.

These rules are embodied in the family of protocols carrier sense multiple access (CMSA) and CSMA with collision detection (CSMA/CD). CSMA/CD attempts to transmit a packet fully, if a collision is detected employs an exponential backoff - the more collisions experienced by a frame, the larger the amount of time it waits.

Taking-Turns Protocols

Inspired by research into attempting to allow nodes to communicate with R/N throughput when multiple nodes active. Polling protocol requires a designated master node, who polls each of the nodes in a round-robin fashion. Eliminates collisions and empty slots, but introduces a polling delay is a single point of failure. Token passing protocol allows nodes to exchange a token in a fixed order, bearing the token allows a node to transmit frames.

DOCSIS: Link Layer Protocol for Cable Internet Access

Cable access networks typically connect several thousand residential cable modems to a termination system (CMTS) at the cable network headend. Data-Over-Cable Service Interface Specification specifies the cable data network architecture. Uses FDM to divide downstream and upstream network segments into multiple frequency channels, with downstream being 6MHz wide with 40Mbps throughput; upstream channels are 6.4MHz with 30Mbps throughput. Each channel is a broadcast channel, but downstream has no multiple access problems as there is a single sender and multiple receivers. Upstream channels are divided into intervals of time (TDM-style), where the CMTS grants permission to broadcast on the channel by sneding a control message (a MAP message) on a downstream channel to specify the modems which may transmit. Modems signal they wish to transmit by sending mini-slot request frames to the CMTS during a special interval of request slots.

Switched Local Networks

Switched local networks are connected through switches, which operate at the link layer and switch link layer frames. They do not recognize network layer addresses nor use routing algorithms, instead using link layer addresses to forward frames through networks of switches.

Link Layer Addressing and ARP

Hosts and router adapters (their network interfaces) have link-layer addresses - a host with multiple interface will have multiple addresses. Link layer switches, however, do not have addresses associated with those interfaces connected to hosts or routers - job of the switch is to carry datagrams between hosts and routers. They do this transparently, without the host/router having to explicitly address the frame to the intervening switch. A link layer address is called a physical address, a LAN address, or a MAC address, which is 6 bytes long, expressed in hexadecimal notation. Once fixed, these addresses are now possible to change via software. Since IEEE manages the MAC address space, each is unique. When a company wishes to manufacture adapters, it purchases an address range, where IEE fixes the first 24 bits and the companies assign the last 24 bits.

Whereas IP addresses have a hierarchical structure (having a network part and a host part), MAC addresses have a flat structure.When an adapter wants to send a frame to some other adapter, the sender inserts the destination MAC address into the frame and transmits the frame to the LAN. Switches can broadcast frames to the entire network, so adapters first verify the destination address is meant for them before extracting the datagram up the protocol stack. Adapters can also specify a broadcast address, FF-FF-FF-FF-FF-FF, into the address field.

Address Resolution Protocol (ARP)

ARP translates between IP → MAC addresses. To send message on the LAN, sources specify the IP and the MAC address of their destinations. Each host and router contain an ARP table that permits ARP to perform its translations. If the table entry of the desired IP address is blank, an ARP packet is constructed and sent to the switch for broadcast to the subnet using the MAC broadcast address.

Sending a Datagram off the Subnet

To send a datagram to another subnet, the packet is addressed to the destination IP address and the MAC address of its own router. Its router, then receiving the frame, can consult its forwarding table to decide which router to retransmit this packet to, placing the next MAC address in the frame header. On the router for the destination hosts subnet, the router can place find and place the MAC address of the destination host to finish routing the frame.

Ethernet

Most prevalent wired LAN technology, it is a broadcast LAN with (originally) a bus topology - all frames are processed by all adapters connected to the bus. In the 90s the Ethernet was installed using a hub-base start topology - when a hub receives a bit from one of its interfaces, it sends a copy out on all of its other interfaces. In the early 00s the hub was replaced with a switch, which are both collision-less and store-and-forward switches that operate on layer 2.

Ethernet Frame Structure

Source and destination are both MAC addreses, the data is the encapsulated network layer segment. CRC is the error correction infromation, and the preamble serves as "wake up" signal to the receiver that helps to synchronize their clocks. Ethernet provides an unreliable delivery service to the network layer - when a frame fails the CRC it is discarded without notifying the sender of success nor failure.

Ethernet Technologies

Can come in many variations, with a name syntax of [speed][BASE: baseband ethernet, physical media only carries ethernet traffic][physical medium used]. Originally wires were limited in length, repeaters are phsyical layer devices a regenerate signal received to boost them. Todays intsallations usually connect nodes to switches via point-to-point segments made of twisted-pair copper wires or fiber-optic cables.Use gigabit ethernet (IEEE 802.3z) uses standard frame format. Allows for point-to-point links with switches or broadcast channels with hubs. Uses CSMA/CD and allows for full-duplex operation at 1000Mbps in both directions for point-to-point channels. In switch based Ethernet LAN there are no collisions, and no need for a MAC protocol.

Link Layer Switches

Switches are designed to be transparent: hosts/routers address frames to other hosts/routers in the subnet, unaware that frames will be handled by a switch.

Forwarding and Filtering

Filtering is the switch function that determines whether a frame should be forwarded or dropped. Forwarding is switch function that determines the interfaces to which a frame should be directed, both functions performed with a switch table, which operate on MAC addresses as opposed to IP addresses. If there is no entry for the destination MAC in the table, this frame is broadcast to all other interfaces except the originating interface. If the MAC is associated with the LAN segment it originated from it is discarded, else it is forwarded attached to the associated interface.

Self-Learning

Switches build their tables automatically, dynamically, and autonomously. Every incoming frame is examined and its source address, interface, and time is logged into the table if not already existing.

Properties of Link Layer Switching

• Elimination of collisions: Switches buffer frames and never transmit more than one frame on a segment at a time.
• Heterogenous links: different interfaces can run at different speeds
• Management: can detect and disconnect from malfunctioning adapters. Gather infomation on bandwidth usage, collision rates, traffic types.

Switches vs Routers

Routers are a layer-3 packet switch, while switches operate on layer-2. Small networks can often suffice with a switch, while larger networks should configure routers. Routers provide more robust isolation of traffic, control broadcast storms, and use more intelligent routing of traffic.

Virtual Local Area Networks (VLANs)

While connecting LANs via a hierarchical switch topology works well in theory, but in reality has several problems:

• Lack of traffic isoation: broadcast traffic traverses entire network
• Inefficient use of switches
• Managing users: If employees move between switch groups, physical cabling must be changed to connect the user to a new group.

Switches that support Virtual Local Area Networks (VLANs) allow multiple virtual local area networks to be defined over a single physical host LAN infrastructure. Hosts within a VLAN communicate as if they (and no other hosts) were connected to a switch. In a port-based VLAN, switch's ports divided into groups by the network manager, each group constituing a VLAN, the ports in each VLAN fromring a broadcast domain (broadcast traffic can only reach other ports in the group). To communicate between groups, traffic is forwarded to a router. A more scalable approach to connect VLANs is VLAN trunking - a special port on each switch port is configured as a trunk port (belonging to all VLANs, frames sent to any VLAN are forwarded to the trunk port). To determine whether a frame was intended for a VLAN, an extended Ethernet frame format is defined containing a four byte VLAN tag. VLANs can also be define based on MAC addresses, or by network protocols like IPv4 or IPv6.

Link Virtualization: A Network as a Link Layer

Multiprotocol Label Switching (MPLS)

A link layer technology that serves to interconnect IP devices - a packet-switched virtual circuit network with own packet formats and forwarding behaviors. Evolved from mid-to-late 90s industry efforts to obtain augment destination-based IP datagram forwarding by selectively labeling datagrams and allowing routers to forward datagrams based on fixed-length labels (rather than destination IP adresses) when possible. These techniques work hand-in-hand with IP, using IP addresing and routing. The format of a link layer frame handled by MPLS capable routers is as follows:

Frames transmitted by MLPS enabled routers have a small header inserted between PPP and IP headers. MLPS only works between enabled routers, often called label-switched routers, since they forward MLPS frames by referring to the labels entry in its forwarding table. The true advantage of MPLS is how it enable traffic engineering, so network operators can override normal IP routing and force traffic headed towards a destination along wone path, and other traffic to same place along a different route. Also used to implement Virtual Private Networks (VPNs) for customers, where ISPs use MPLS networks to connect together customers various networks, can be used to isolate both the resources and addresses of the VPNs from other traffic crossing the network.

Data Center Networking

Data centers hose ten to hundreds of thousands of hosts, concurrently supporting many cloud applications. Each data center has its own data center network, interconnecting hosts and the data center to the internet. The ~$12+ million cost of a data center typically breaks down along these lines:

• ~45% to the hosts themselves (need to be replaced every 3-4 years)
• ~25% to infrastructure: uninterruptible power supply, generators, cooling systems
• ~15% to electric utility costs
• ~15% for networking, including both gear and transit traffic costs

Hosts in data centers, called blades, are generally commodity hosts including CPU, memory and storage and stacked in racks of 20-40 blades. At the top of each rack is a switch, the Top of Rack (TOR) switch, interconnecting hosts in the rack with each other and other switches in the data center.Each host in the rack has a NIC connected to the TOR, each TOR has ports to connect to other switches. Data center networks suport two types of traffic: intra data-center, and from hosts to the external network. Border routers enable host communication with the public internet

Load Balancing

To outside clients, applications send their data to an IP address from which they receive responses. Inside the data center, requests are first directed to load balancers (or layer 4 switches, since they make forwarding decision based on the port number - layer 4 - as well as the destination IP address), who distribute requests to the hosts, balancing the load across hosts. Provides not only load-balancing services, but also NAT-like functionality, transalting public IP addresses into internal data-center IP addresses.

Hierarchical Architecture

For simple data centers of a few thousand hosts, a border router, load balancer, and single ethernet switch could probably suffice. To scale to hundreds of thousands of hosts a hierarchy of routers and switches is emplyed. At the top of the hierarchy a border router connects to access routers, who themselves are connected to tiers of switches. Top tier switches connect to multiple second tier switches and load balancers. Second tier switches connects to the TOR switches (third tier switch) of multiple racks. Because availability is critical, data centers also include redundant network equipment and links in their designs. Hosts below each access router form a single subnet, and each of these if further partitioned into smaller VLAN subnets to localize ARP traffic. This conventional hierarchical strucutre suffers from limited host-to-host capacity - one possible solution is emplying higher-capacity switches and routers, but this increases the costs significantly.

Trends in Data Center Networking

One new approach is replacing hierachy of switches and routers with a fully connected topology - each tier 1 switch connects to all tier 2 switches, which can improve host-to-host capacity.

Another approach is to ship and deploy modular data centers containing a few thousand hosts. Multiple containers can be deployed and interconnected within a data center. Though difficult to srevice, they are designed to fail gracefully and can be replaced wholesale once a threshold of service is breached.

New approaches in routing between switches are also being explored, from rnadom routing to deploying multiple NICs in each host, connected to cheap switches.

A Day in the Life of a Webpage Request

What happens when a person connects to an ethernet network and requests webpage?

Getting Started: DHCP, UDP, IP and Ethernet

At connection time, the computer will run the DHCP protocol to obtain an IP address.

1. The computer sends a DHCP request message, inside a UDP segment, which is placed inside a IP datagram with destination 255.255.255.255 and source 0.0.0.0.
2. IP datagram placed in Ethernet frame with broadcast destination FF:FF:FF:FF:FF:FF, with the MAC address of the computer.
3. Broadcast ethernet frame containing the DHCP request is sent on the link to the ethernet switch, to be broadcast to all outgoing ports.
4. The router receives broadcast DHCP request frame, and extracts the IP datagram, which then demultiplexes the segment to UDP, and the DHCP server receives the message.
5. The router can allocate IP addresses within its allowed CIDR block. It creates a DHCP ACK message with an assigned IP address, the default gateway, the subnet block (the network mask), and the DNS server to be encapsulated in an IP datagram inside an ethernet frame.
6. This reply frame is unicast back to the switch. Because the swithc is self-learning it understand the interface associate with the destination mac address.
7. The computer receives this frame and extracts the IP datagram, demultiplexing the UDP segment to the DHCP host. It recognizes this IP address as the one assigned to it, also install address of the dns server and default gateway into IP forwarding table.
8. Operating system of computer creates a DNS query message, placed in UDP segment and IP datagram with dns server as destination
9. Datagram placed in ethernet frame to be addressed to the gateway routers MAC address. To obtain the MAC address it uses the ARP.
10. Computer creates an ARP query with destination gateway as destination, places inside broadcast ethernet frame, sends to switch, which broadcasts to all connected interfaces.
11. Gateway router receives frame of arp query and matches the destination IP to the IP on its interface. Prepares an ARP reply with MAC address of interface, place in frame and sends to switch, who forwards to computer.
12. Computer receives ARP reply and extracts MAC address of the default gateway.
13. Can now address dns query ethernet frame to gateway routers mac address - the frame has a destination address of the DNS server, while the destination mac address is the gateway router.
14. Gateway router receives frame and extracts IP datagram containing DNS query. Uses destination ip and forwarding table to determine the router to forward the datagram to - placed inside another frame with the address of this router and transmitted on the associated interface.
15. Router in ISP receives frame and examines the datagrams destination address for use in the forwarding table (filled by RIP, OSPF and BGP) to determine the outgoing interface and destination mac address.
16. Proceeds in this manner until the DNS query datagram received by DNS server. Server extracts the query, looks up the name in its DNS database to find the dns resource record - this cached data originated in the authoritative dns server. Server prepares a dns reply message inside a udp segment addressed to the computer.
17. Computer extracts the IP address of the server from the DNS message. Can address traffic to the desired website.
18. Opens a TCP socket used to send the HTTP get message. Creating the TCP socket performs the 3-way handshake first, sending a TCP SYN segment.
19. Frame is fowarded to the gateway router, ISP routers, to routers of website who deliver the message to the server. Forwarding again performed by RIP, OSPF and BGP filling values in the routing forwarding table.
20. TCP SYN delivered to the website server, who replies with a SYNACK message.
21. SYNACK received by computer, connection created. Last ACK message created with an HTTP GET message to return the specified document.
22. Website receives GET, passes document into the TCP socket to be transmitted to the computer.

6. Wireless and Mobile Networks

Wireless networks have several components:

• Wireless hosts: End-system devices that run applications
• Wireless links: Used by hosts to communicate with base stations.
• Base station: Responsible for sending and receiving data (e.g., packets) to and from wireless host, no wired counterpart. Often responsible for coordinating transmission of multiple wireless hosts with which they are associated - hosts within wireless communication distance from base station, being used by that host to transmit data into larger network. Cell towers in cellular networks and access points in 802.11 wireless LANs are examples of base stations. Hosts associated with a base station are operating in infrastructure mode, where all traditional network services are provided by the network to which the host is associated. This contrasts to ad hoc networks, where wireless hosts themselves provide network services.
• When mobile hosts move beyond range of an access point and into the range of another, it will change its point of attachment into the larger network in a process called a handoff.
• Network infrastructure, the larger network which the host communicates with.

These pieces can be composed multiple ways to form different types of wireless networks, principally categorized by whether they have one or multipe wireless hops, or there is infrastructure.

• single hop infrastructure based: base station connected into larger wired network, all communication occurs over single wireless hop.
• single hop, infrastructure-less: No base station, one of the nodes may coordinate transmissions of the other nodes.
• multi-hop, infrastructure based: Some wireless nodes in network may have to relay their communication through other wireless nodes to base station. Wireless mesh networks are an example of this.
• multi-hop, infrastructure-less: No base station, nodes may have relay messages several times to reach a destination. Nodes may also be mobile, with connectivity changing among nodes.

Wireless Links and Network Characteristics

There are a number of important differences between wired and wireless links:

• Decreasing signal strength: Electromagnetic radiation attenuates as it passes through matter - even in free space, signal will disperse as distance increases, introducing signal strength loss known as path loss.
• Interference from other sources: Radio sources transmitting in the same frequency band will interfere with each other, electromagnetic noise from the environment will also cause interference.
• Multipath propagation: occurs when portions of the electromagnetic wave reflect off objects and the ground, taking paths of different lengths between nodes and blurring signal at the receiver.

All of these factors mean that bit errors will be more common in wireless links, introducing the need for methods to detect and correct corrupted frames, and also link-level reliable-data-transfer protocols to retransmit corrupted frames.

Hosts receive an electromagnetic signal that is a combination of a degraded form of the original signal transmitted by the sender (degraded from attenuation, multipath propagation, etc.). The signal-to-noise ratio is a relative measure of the strength of the signal vs. the noise. Larger SNR make it easier to extract transmitted signals. Bit Error Rate (BER) shows the probability that a transmitted bit is received in error at the receiver.

Modulation techniques encode information for transmission across wireless channels. The BER and SNR will vary according to the modulation technique, along some principles:

• For a given modulation scheme, higher SNR lowers BER. Since a sender can increase the SNR by increasing its transmission power, a sender can decrease erroneous frames received by increasing transmission power. There is little practical gain in increasing power beyond a certain threshold, there are also disadvantages associated - more energy must be expended and sender's transmission are more likely to interfere with transmissions of another sender.
• For a given SNR, a modulation technique with higher bit transmission rate will have a higher BER.
• Dynamic selection of the physical-layer modulation technique can be used to adapt the modulation technique to channel conditions. SNR and BER may change, adaptive modulation and coding are used in 802.11 WiFi and 3G cellular networks. This allows for selection of modulation technique that provides highest transmission rate possibe.

Another issue that occurs exclusively in wireless networks is the hidden terminal problem, wherein two nodes outside of each others range each attempt to communicate with a shared base point, successfully interfering with each others transmissions.

Code Division Multiple Access Protocols

A channel partioning protocol, prevelant in wireless LAN and cell technologies. Each bit sent is encoded by multiplying the bit by a signal (the code), that changes at rate faster than the original sequence of bits (the chipping rate). A CDMA protocol is similar to having patrygoers speak multiple languages; people are good at listening to one conversation and filtering out other. CDMA partitions the codespace (as opposed to time or frequency) and assigns nodes a piece of the codespace.

WiFi: 802.11 Wireless LANs

Different WiFi standards have been developed, they all have some similar underlying characteristics. They all use the same medium access protocol, CSMA/CA, frame structure, allow for ad hoc/infrastructure mode and have ability to reduce their transmission rate in order to reach out over greater distances.

802.11 Wireless Standard

Standard b's frequency range competes with 2.4GHz phones and microwave ovens.Standard a achieves higher bit rate by operating at a higher frequency, at the cost of shorter transmission distance and more multipath propagation. Standard n uses multiple-input multiple-output (MIMO) antennas, 2+ antennas on the sending and 2+ on the receiving side.

802.11 Architecture

The fundamental building block of the 802.11 Wireless LAN Architecture is the basic service set (BSS), containing one or more wireless stations and a central base station, known as an access point (AP). Each base station has a MAC address for its wireless interface administered by IEEE and globally unique. When an AP is installed the operator assigns an Service Set Identifier (SSID) to the access point and a channel number. Within the frequency range 2.4-2.485GHz 802.11 defines 11 partially overlapping channels - any two channels are non-overlapping if and only if they are separated by four or more channels. In particular, the set of channels {1, 6, 11} are the only 3 non-overlapping channels. A WiFi jungle is any physical location where a wireless station receives a sufficiently strong signal from two or more APs. To join a subnet, a host needs to associate with exactly one AP, so that only the associated AP will send data frames to your wireless station, and frames will be sent to the internet only through the associated AP. 802.11 standard requires that an AP periodically send beacon frames, each of which includes the APs SSID and MAC addresses. Passive Scanning allows a host to join a subnet by waiting for these beacon frames on the different channels. Can also perform active scanning, broadcasting a probe frame to be received by all APs within the wireless host's range. APs respond to the probe request frames with a probe response frame. Hosts can choose among available APs by a set of criteria. Once associated with AP, host can send a DHCP discovery message to subnet and obtain an IP address

802.11 MAC Protocol

Multiple Access Control Protocols are needed to coordinate channel access among stations (either a wireless station or AP). There are 3 classes of MAC protocols: channel partitioning, random access or taking turns. Carrier Sensing Multiple Access with Collision Avoidance (CSMA/CA) is the protocol used on 802.11. It uses a link-layer acknowledgement (ARQ) because of the relatively high bit error rates of wireless networks. It uses collision avoidance techniques in lieu of collision detection. The ability to detect collisions requires sending and receiving at the same time, which is costly to build for wireless adapters - and even if feasible, hidden terminal problem would still allow for collisions. Frames are sent in their entirety.

802.11 uses a link-layer acknowledgement scheme where received frames that pass CRC trigger an acknowledgement frame after the Short Inter-frame Spacing (SIFS) timeou - if not received a duplicate transmission is generated. This random value helps avoid hidden terminal problems. Also allows a station use of Request to Send (RTS) and Clear to Send (CTS) control frames, which reserve channel access. Can also be used as a point-to-point link with directional antennas.

The IEEE 802.11 Frame

Although they share many similarities with Ethernet frames, they have fields specific to wireless links.

Three address fields are needed for transmitting network-layer datagrams from wireless stations through an AP to another interface, four if frames are forwarded to each other in ad hoc mode.

• MAC address 1: wireless station that will receive the frame
• MAC address 2: station that transmits the frames. If an AP transmits the frame, the APs MAC address is inserted in address 2 field.
• MAC address 3: address of router connecting subnet to larger network.

Sequence Control Number allows the receiver to distinguish between a newly transmitted frame and retransmission of a previous frame.

Mobility in the Same IP Subnet

When hosts wish to move between BSSs in the same subnet, it may do so automatically - a host may detect the signal from its original AP weakening and the signal from a new AP strengthening. The host may disassociate with the weaker AP and associate with the stronger AP. The new AP may then send a frame to any associated switches so that they may update their forwarding tables and know the host may be reached via that AP.

Advanced Features in 802.11

802.11 Rate Adaptation

As different modulation techniques provide different SNR scenarios. Some 802.11 implementations have capability to select underlying physical-layer modulation techniques in response to failure to receive acknowledgements for sent packets.

802.11 Power Management

Nodes have the ability to minimize the amount of time that their sense, transmit and receive functions and other circuitry need to be on. Can indicate to AP that it will be going to sleep by setting the power management bit in the frame header. A timer in the node wakes it up shortly before scheduled to receive a beacon signal from the AP. The beacon frame will contain a list of nodes who have frames have been buffered at the AP - if present, it will stay awake and request new frames be sent.

Cellular Internet Access

An Overview of Cellular Network Architecture

The Global System for Mobile Communications (GSM) standards were developed to implement a pan-European digital cellular telephony system to replace the analog cellular telephony networks. Cellular networks are classified by their generation: 1G systems were analog FDMA designed exclusively for voice-only communication. The 2G systems were also designed for voice data, but 2.5-3G systems support data.

Cellular Network Architecture, 2G: Voice Connections to the Telephone Network

Cellular refers to the fact that regions covered by cellular networks are partitioned into number of geographic coverage areas, called cells. Each cell contains a base transceiver station (BTS) that transmits to and from mobile stations in its cell.

The 2G cellular system uses combined FDM/TDM (radio) for the air interface. This partitions the channel into a number of sub-bands; within each sub-band time is partitioned into frames and slots, the channel can support frames * slots simultaneous connections. A GSM networks base station controller (BSC) will service several tens of BSSs. The role of the BSC is to allocate BTS radio channels to mobile subscribers and perform paging (finding the cell in which a mobile user is resident). The BSS controler and controlled BTSs constitute a GSM base station system (BSS). Mobile switching centers (MSC) contain up to five BSCs, or ~200k subscribers/MSC, with cell providers managing special gateway MSCs connecting the cellular network to the larger public network. The MSC is central in managing user authorization, call establishment, teardown and sendoff.

Extending the Internet to Cellular Subscribers

3G Core Network interoperates with components of the existing cellular voice networks Mobile Switching Center. The design of the 3G data services is to leave the existing core GSM cellular voice network untouched, adding additional cellular data functionality in parallel to the existing cellular voice network.

There are two types of 3G core network nodes:

• Serving GPRS Support Nodes (SGSNs): Responsible for delivering datagrams to/from the mobile nodes in the radio access netowrk to which the SGSN is attached. Interacts with the MSC for their area, providing user authorization and handoff, maintaining location information abot actice mobile nodes, performing datagram forwarding between mobile nodes in the access network and a GGSN. GPRS was an early 2G network data service.
• Gateway GPRS Support Nodes (GGSNs): Acts as a gateway, connecting multiple SGSNs into the larger internet. It is the last piece of 3G infrastructure that a datagram originating at a mobile node encounters before entering the larger internet. From the outside they appear as any other gateway router; mobility of the 3G nodes within the network is hidden to the outside world.

3G Radio Access Network: The Wireless Edge

Radio Access Networks are the first-hop network that a 3G user sees. Radio Network Controller (RNC) typically control several cell BTS similar to the base stations in 2G networks, each cell's wireles links operates between the mobile nodes and a BTS, just as in 2G networks. RNC connects circuit-switched cellular voice networks via an MSC, packet-switched Internet via an SGSN. 3G cellular voice and data services use different core networks, but share a common first/last-hop radio access network.

A large change between 3G and 2G networks is their MAC. 2G uses GSMs FDMA/TDMA scheme, UMTS uses a CDMA technique known as Direct Sequence Wideband CDMA (DS-WCDMA) within TDMA slots available on multiple frequencies. The data service associated with WCDMA specification is known as High Speed Packet Access (HSPA) which provides downloads up to 14Mbps.

On the 4G: LTE

Improves on the 3G network with an all-IP core network and an enhanced radio access network.

An All-IP Core Network

3G network has separate components for voice and data traffic; 4G architecture carries both voice and data in IP datagrams to/from the wireless device (User Equipment, or UE) → gateway → packet gateway (P-GW) that connects the 4G edge network to the rest of the network, thus achieving universal IP service.

Clear separation of the 4G data and control planes

Clear separation between radio access network and all-IP-core network.

IP datagrams with user data are forwarded between UE and P-GW over internal 4G IP network to the external internet. Control packets are exchanged over this same internal network among 4G control service components.

The eNodeB is the logical descendant of the 2G base station and the 3G radio network controller (Node B) and again plays a central role here. Its data-plane role is to forward datagrams between UE and the P-GW. UE datagrams are encapsulated and tunneled to P-GW through the 4G networks all-IIP enhanced packet core (EPC). Tunneling between the two is similar to the tunneling between IPv4 and IPv6, may have quality of service guarantees. 4G networks may guarantee ceilings on voice traffic delays and packet loss rates between UE and P-GW. Handles registration and mobility signaling traffic on behalf of the UE. Packet Data Network Gateway (P-GW) allocates IP addresses to the UEs and performs QoS enforcement. As a tunnel endpoint it also performs datagram encapsulation/decapsulation when forwarding a datagram to/from a UE.

Serving Gateway (S-GW) is the data-plane mobiliity anchor ponit - all UE traffic will pass through, also performs charging/billing functions and lawful traffic interception.

Mobility Management Entity (MME) performs connection and mobility management on behalf of the UEs resident in the cell controlled. It receives UE subscription information from the HHS.

Home Subscriber Service (HSS) contains UE information including roaming access capabilities, QoS profiles, and authentication information, using information obtained from UEs home cellular provider.

LTE Radio Access Network

Uses a combination of FDM/TDM on downstream channel known as Orthogonal Frequency Division Multiplexing (OFDM) (signals sent on different frequency channels are created so that they interfere very little with each other, even when channel frequencies are tightly spaced). Each active mobile LTE node is allocated 1 or more 0.5 ms time slots in one time in one or more of the channel frequencies. Increasing allocations allow for higher transmission rates. Decision on nodes allowed transmissions is made by scheduling algorithms provided by the LTE equipment vendor or network operator, allowing radio network controller to make best use of spectrum, or prioritize transmissions according to contracted levels of service. LTE-Advanced allows for downstream bandwidths of hundreds of Mbps by allocated aggregated channels to mobile nodes. 4G WiMAX is a family of 802.16 stadards differing from LTE.

Mobility Management: Principles

Degrees of mobility present different sets of challenges to the network layer. On the low end users carry devices with wireless network interfaces around, making them immobile from the networks pov - especially if the devices does not cross into other access points. Users at the high end of the spectrum may be moving at vehicle or airplane speeds, passing through multiple wireless acess points and need to maintain an uninterrupted TCP connection to a remote application.

In a network setting, permanent home of a mobile node is the home network, entity that performs mobility management functions on behalf of the mobile node is the home agent. Network in which the mobile node is currently residing is the foreign (visited) network. A correspondent is the entity wishing to communicate with the mobile node.

Addressing

For user mobility to be transparent to network applications, it is desirable for a mobile node to keep it address as it moves between networks. Mobility functionality is pushed from the network core to the mobile edge - the home agent can track the foreign network where the node resides. The foreign agent creates a care-of-address (COA) for the mobile node, with the network portion of the COA matching the foreign network, also has a permanent address. COA is used to reroute datagrams to the mobile node via the foreign agent. Mobile nodes can also assume the responsibilities of the foreign agent.

Routing to a Mobile Node

Indirect Routing to a Mobile Node

Correspondent addresses the datagram to the mobile node's permanent address and sends the datagram into the network, blind to whether node is resident in its home network or visiting a foreign network. Home agent intercepts traffic to the mobile node and forwards in a two step process: forwards to the foreign agent using the COA, the from the foreign agent to the mobile node. Home agent encapsulates the correspondent's original complete datagram within a new datagram, addressed to the mobile node COA, to be decapsulated by the foreign agent. Mobile node can address datagrams to the correspondent using its address and its permanent address as the source address. Indirect routing requires several protocols:

• Mobile-node-to-foerign-agent protocol to register with foreign agent, deregister when leaving foreign network
• foreign-agent-to-home-agent registration protocol to register mobile node COA with the home agent. Foreign agent need not explicitly deregister a COA when it leaves its network, subsequent registration of a new COA handles this
• home-agent datagram encapsulation protocol forwarding of the correspondent's original datagram within a datagram addressed to the COA
• foreign-agent decapsulation protocol extraction of the correspondent's original datagram from the encapsulating datagram, and the forwarding of the original datagram to the mobile node

Direct Routing to a Mobile Node

Suffers from triangle routing problem - datagram addressed to the mobile node must first get routed to the home agent before the foreign network, even if not the most efficient.

Direct routing avoids this problem at the cost of additional complexity. A correspondent agent in the correspondent's network first learns the COA of the mobile node (correspondent agent can query the home agent, also the correspondent itself to perform the function of its agent). Correspondent agent then tunnels datagrams directly to the mobile nodes COA. Introduces two additonal challenges:

• Mobile-user location protocol is needed for correspondent agent to query the home agent to obtain the mobile node's COA
• When mobile node moves between foreign agents, the foreign agent in the foreign network is first located is called the anchor foreign agent. Mobile nodes moving between networks registers with new foreign agent, who update the COA with the anchor foreign agent- this anchor can receive and forward encapsulated datagrams.

Mobile IP

Mobile IP architecture consists of three main pieces:

Agent Discovery

Mobile IP node arriving to a new network must learn the identity of the corresponding foreign/home agent. Discovery of a new foreign agent alows mobile node to learn that it has moved into a new foreign agent. Can be accomplished by:

Agent advertisement

Foreign or home agent advertise their services using an extension to the existing router discovery protocol - agent can periodically broadcast an ICMP mesage with a router discovery type containing the IP address of the router, allowing a mobile node to then learn the agent's IP address and the mobility agent advertisement extension with addtional needed information:

• Home agent bit
• Foreign agent bit

• Registration required bit

  Mobile user cannot obtain care-of-address in the foreign network and assume foreign agent functionality without first registering.

• M, G encapsulation bits

• Care-of address (COA) fields

Agent Solicitation

Mobile nodes can proactively learn about agents without waiting to receive an advertisement, can broadcast an agent solicitation message - an ICMP message, to directly unicast an agent advertisement.

Registration with the Home agent

Defines protocols used by the mobile/foreign agents to de/register COAs with a mobile node's home agent

Indirect routing of datagrams

Also defines the manner in which datagrams are forwarded to mobile nodes by a home agent, including rules for forwarding and handling error conditions.

Managing Mobility in Cellular Networks

Like mobile IP, GSM adopts an indirect routing approach, first routing the correspondent's call to the mobile user's home netework and then to the visited network - in GSM terminology, the home is the home public land mobile network (home PLMN), the home network and the visited network where the node currently resides.

The home network maintains a database - the home location register (HLR) - storing the permanent cell phone number, subscriber profile information and data for the current location of these subscribers. Has enough info to obtain the address of the foreign network. The Gateway Mobile services Switching Center (GMSC), or home MSC switch is contacted by a correspondent when a call is placed to a mobile user.

Visited networks maintain a database known as the visiotr location register (VLR), containing entries for each mobile user currently serverd by the VLR.

Routing Calls to a Mobile User

1. First leg of call: Correspondent dials mobile phone number, the leading numbers of which globally identify the mobile's home network. Call is routed from correspondent through the PSTN to the home MSC in the mobile's home network.
2. Home MSC receives call and interrogates HLR to determine location. In simplest case returns mobile station roaming number (MSRN), the roaming number. Roaming numbers serve same purpose as COA: ephemeral numbers assigned when visiting a network.
3. With the roaming number, home MSC sets up second leg of call through the network to the MSC of the visited network.

Handoffs in GSM

Handoffs occur when a mobile station changes its association from one base station to another during a call. Calls change base station through which they are routed during the process. Mobile devices periodically measure the strength of beacon signals and occasionally switch to a stronger signal.

Wireless and Mobility: Impact on Higher-Layer Protocols

TCP retransmits lost or corrupted segments - for mobile users can happen from network congestion or during handoff. In all cases, TCP's receiver-to-sender ACK indicates error, not specifying the type. TCP congestion-control response is the same in all cases - TCP decreases its congestion window, implicitly assumes loss is from congestion. Bit errors are also much more common in wireless networks. Three approaches are used to deal with the problem:

• Local recovery protocols recover from bit errors when & where they occur - ARQ is used in 802.11, or more sophisticated approaches that use ARQ & FEC
• TCP sender awareness of wireless links allowing TCP senders and receiver to be aware of wireless links helps distinguish betwen congestive losses ocurring in the wired network and corruption ocurring at the wireless link, and invoke congestion control only in response to congestive wired-network losses.
• Split-connection approaches the end-to-end connection between mobile user and the other end point is broken into two transport-layer connections: one from the mobile host to the wireless access point, and one from the AP to the other communication end point. Widely used in cellular data networks.

For application layer protocols, they may have to consider that wireless or mobile links may have lower bandwidth throughput, and treat bandwidth as a scarce resource.

Security in Computer Networks

What Is Network Security?

When security is provided for a specific application-layer protocol, the application using the protocol will enjoy one or more security services. Security at the network layer can offer "blanket coverage" by encrypting all the data in the datagrams, it can't provide user-level security. It is also generally easier to deploy new Internet services (including security services) at the higher levels of the protocol stack.

Confidentiality - only the sender and receiver should be able to understand the contents of the transmitted message

Integrity - contents of communications should not be altered, maliciously or accidentally.

Authenticity - senders and receivers should be able to confirm the others identities.

Attackers may eavesdrop or tamper with messages, necessitating countermeasures.

Public Key Encryption

Works by giving sender and receiver a public key available to all and a private key only known to themselves. Senders may encrypt their message with the public key of the recipient, which may be decrypted with the corresponding private key.

RSA is nearly synonymous with public key encryption. It relies on the fact there are no quick or easy methods for quickly factoring a number in primes.

• Chooses two large prime numbers, p and q.
• Computes n = pq and z = (p - 1)(q - 1).
• Choose a number e where e < n, that has no factors in common with z.
• Find a number d such that ed - 1 is exactly divisible by z.
• Public key made available is {n, e}, private key {n, d}.

Encryption and decryption are performed as follows:

• To send a bit pattern, m, it is first exponentiated by m ^ e, then computes the integer remainder when m ^e is divided by n. Thus, the ciphertext is c = me mod n
• Decryption the receiver computes m = cd mod n

Session Keys

The exponentiation required by RSA is resource intensive - DES is ~100x faster in software and ~10000x in hardware. Because of this, often used in practice with symmetric key cryptography. A sender encodes a session key, to be encrypted with the receivers public key, to be decrypted by the receiver. This key is used in subsequent symmetric encryption for the data transfer.

Diffe Hellman is not as versatile as RSA, but can be used to establish a symmetric session key.

Message Integrity and Digial Signatures

Integrity is used to show message originated from sender, and was not tampered with in transit.

Message Authentication Code

To perform message integrity, nodes will need a cryptographic hash function and a shared secret s. This shared secret is called the authentication key.

• Sender creates a message m, concats s into m+s, and calculates the hash H(m+s), the message authentication code (MAC).
• Sender appends MAC to message and sends the extended message
• Receiver receives extended message, and knowing s, can calculate MAC to verify the integrity of the message.

Digital Signatures

A verifiable, nonforgable signature for electronic documents. To sign document m we take the hash of the message and encrypt the message with the private key.

PUublic Key Certification

Certifies that a public key belongs to a specific entity. A certificate authority is responsible for binding the keys. Verifies that entities identity, the creates a certificate binding the public key to the identity - containing the public key and a globally unique information about the entity, to be signed by the CA.

End-Point Authentication

Process of one entity proving its identity to another over a computer network - authentication is performed solely on the basis of messages and data exchanged as part of an authenticaiton protocol. These run before two entities start communicating.

Authentication Protocol

1. Alice sends the message "I am Alice" to Bob
2. Bob chooses a nonce, R, and sends it to Alice
3. Alice encrypts the nonce using Alice and Bob's symmetric secret key, sends the encryted nonce back to Bob - nonce is used to ensure Alice is live.
4. Bob decrypts the received message. If the decrypted nonce equals the nonce he sent Alice, then Alice is authenticated.

Securing Email

Comments

[Nadeem Taj]

Good for beginners. Is possible to adjust pictures in the topic.